3
$\begingroup$

One of the things I like about parsing expression grammars is that they're automatically unambiguous, and unambiguity is a very important property to have. However, context-free grammars are somewhat weak. Is there a generalization of parsing expression grammars that works for context-sensitive grammars? What I mean by that is whether there exist a generalization such that

  1. the generalization allows for nonterminal symbols to be on both sides of the production rule.

  2. the generalization preserves the property that an unambiguous parse is always produced.

$\endgroup$
2
$\begingroup$

PEGs are unambiguous exactly because at each choice point, i.e, alternatives of a grammar rule, you can choose one and never change it. Context-free grammars, or to be more precise general parsing algorithms like Early or GLR, explore all the alternatives which can lead to ambiguity.

We have to also distinguish between ambiguity and non-determinism. PEGs reduce non-determinism at runtime, which guarantee at most one parse result, but at the same time, they can lead to parse errors even when there is no ambiguity. For example, consider the grammar:

A ::= 'a'
    | 'a' 'b'

and the input 'ab'. This will lead to a parse error because the parser made a premature choice. This is the main shortcoming of PEGs.

About general parsing algorithms, it is not possible to guarantee un-ambiguousness, but at the same time guarantee that the correct (intended) parse tree is returned. There are many disambiguation techniques that try to reduce non-determinism at runtime, and as a result remove ambiguities, but there no guarantee. The underlying grammar may be ambiguous.

What do you mean by context-sensitive grammars? Something like Python that has indentation-sensitivity? If you are looking for such features, the answer to your first question is yes. You can take a look into monadic parser combinators (with limited backtracking). They are essentially PEGs and allow threading of values into the parsing state to simulate context-sensitiveness. I am not aware of any formalism that allows you to write arbitrary context-sensitive grammars with more than one nonterminal on the left-hand side.

The answer to the second question is also yes. If you always select one alternative and never backtrack, you will get at most one parse tree, but it may not be the one you want or you can get a parse error.

You can also look into one of my previous work on data-dependent GLL Parsing where we describe how to deal with context-sensitivity in general parsing. The paper has a good discussion (IMO) of different parsing techniques.

$\endgroup$
  • $\begingroup$ +1 why in the world was this answer downvoted? $\endgroup$ – Mehrdad Jan 2 '18 at 2:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.