What techniques can I use to hand-write a parser for an ambiguous grammar?

Question

I'm writing a compiler, and I've built a recursive-descent parser to handle the syntax analysis. I'd like to enhance the type system to support functions as a valid variable type, but I'm building a statically typed language, and my desired syntax for a function type renders the grammar temporarily* ambiguous until resolved. I'd rather not use a parser generator, though I know that Elkhound would be an option. I know I can alter the grammar to make it parse within a fixed number of steps, but I'm more interested in how to implement this by hand.

I've made a number of attempts at figuring out the high-level control flow, but every time I do this I end up forgetting a dimension of complexity, and my parser becomes impossible to use and maintain.

There are two layers of ambiguity: a statement can be an expression, a variable definition, or a function declaration, and the function declaration can have a complex return type.

Grammar subset, demonstrating the ambiguity:

basetype
  : TYPE
  | IDENTIFIER
  ;

type
  : basetype
  | basetype parameter_list
  ;

arguments
  : arraytype IDENTIFIER
  | arraytype IDENTIFIER COMMA arguments
  ;

argument_list
  : OPEN_PAREN CLOSE_PAREN
  | OPEN_PAREN arguments CLOSE_PAREN
  ;

parameters
  : arraytype
  | arraytype COMMA parameters
  ;

parameter_list
  : OPEN_PAREN CLOSE_PAREN
  | OPEN_PAREN parameters CLOSE_PAREN
  ;

expressions
  : expression
  | expression COMMA expressions
  ;

expression_list
  : OPEN_PAREN CLOSE_PAREN
  | OPEN_PAREN expressions CLOSE_PAREN
  ;

// just a type that can be an array (this language does not support
// multidimensional arrays)
arraytype:
  : type
  | type OPEN_BRACKET CLOSE_BRACKET
  ;

block
  : OPEN_BRACE CLOSE_BRACE
  | OPEN_BRACE statements CLOSE_BRACE
  ;

function_expression
  : arraytype argument_list block
  | arraytype IDENTIFIER argument_list block
  ;

call_expression
  : expression expressions
  ;

index_expression
  : expression OPEN_BRACKET expression CLOSE_BRACKET
  ;

expression
  : function_expression
  | call_expression
  | index_expression
  | OPEN_PAREN expression CLOSE_PAREN
  ;

function_statement
  : arraytype IDENTIFIER argument_list block
  ;

define_clause
  : IDENTIFIER
  | IDENTIFIER ASSIGN expression
  ;

define_chain
  : define_clause
  | define_clause COMMA define_chain
  ;

define_statement
  : arraytype define_chain
  ;

statement
  : function_statement
  | define_statement SEMICOLON
  | expression SEMICOLON
  ;

statements
  :
  | statement statements
  ;

Example parses:

// function 'fn' returns a reference to a void, parameterless function
void() fn() {}
// the parser doesn't know which of these are types and which are variables,
// so it doesn't know until the end that this is a call_expression
Object(var, var, var, var)
// the parser only finds out at the end that this is a function declaration
Object(var, var, var, var) fn2() {}
(Object(var, var, var, var) ())
(Object(var, var, var, var) () {})
// the parser could possibly detect the "string" type and figure out that
// this has to be a define statement or a function declaration, but it's
// still ambiguous to the end
Object(Object(string, Object), string[]) fn3() {}
Object(Object(string, Object), string[]) fn4 = fn3;

My basic approach has been to write functions that could parse the unambiguous components of this subset of the grammar, and then flatten the more complex control flow into individual functional blocks to capture state in function calls. This has proved unsuccessful, what techniques can one use to solve this kind of problem?

*There is likely a better word for this

Answer 1

This answer is based on the additional information you give that your problem might be more non-determinism than ambiguity, and that you think you could then solve it if you had some lookahead arbitrarily far away.

Since this case allows for quite different answer, I think it is clearer to answer it separately from my previous answer.

If unbounded lookahead is all you need, then you should investigate whether RLR parsing could do the job for you. The idea of RLR is that you use a finite state automaton to get information that can be arbitrarily far away. I am not sure about all the details of the technique in its general form, but it has been implemented in some freely available parser generators.

Given that you insist on a hand written parser, you might be able to apply that by hand to your own grammar.

The best way to explain it is on a well known example, because many languages actually need unbounded look ahead, but deal with the problem under the rug, so that you do not notice it.

The usual name for the rug is lexical analysis.

Suppose the grammar includes the following rules:

U -> X Y
V -> X Y id
M -> U id foo
N -> V bar 
Z -> M | N

where id is any identifier, while foo and bar are language keywords.

and you have to parse ... xxxx yyy very_long_identifier foo ....

After reducing xxxx to X and yyy to Y, you have to decide whether to reduce X Y to U, or rather scan the coming identifier. It is quite visible that that depend on the keyword foo or bar that comes after the identifier. This can be easily dealt with with bounded lookahead, as the decisive keyword is only 2 tokens away when the decision is to be made.

But this assumes that the identifier is considered as a single keyword.

Some people assert that, since CF languages are closed under substitution by regular sets, lexical analysis is not really essential and CF parsers should be able to handle it with the rest of the CF syntax. This is true for a general CF parser (though disputable on practical grounds). But it requires some care and adaptation for classical deterministic parsing technology, because the theoretically unbounded length of identifiers raises lookahead problems.

In the example above, if the identifier has not been recognized as such by a lexical analyzer, then it is just an arbitrarily long sequence of alphanumeric tokens, so that the decisive keywords, foo and bar are unboundedly far away.

This shows that recognizing an intermediate structure through a pass with a simple finite state device can remove a problem such as unbounded lookahead, at least in some cases, which is all you ask for if you develop by hand a specific parser.

If is for you to analyze precisely your grammar to see what can be done, but the above suggest the following approach:

You state:

I cannot know definitively whether a given string of tokens represents a function statement, expression, or define statement until near the end of any of those structures in the worst case.

So the question is (up to some probably modifiable details): can you recognize that a sequence of symbols is one of these two constructs of your language, and identify which (without producing a parse-tree) by means of a simple finite state automaton (FSA)? If the answer is yes, than whenever you encounter the beginning of such a sequence, you activate the corresponding FSA to determine quickly which kind of sequence it is, and then you use the result to make your parsing decision.

Answer 2

I did not read in detail your grammar which is far too large for my available time, and short of an example that you should provide (since you assert it is ambiguous) I will not not attempt to check whether it is, which is in general undecidable.

This said, as already remarked by user rici there are general context-free (GCF) parsers that will parse any CF grammar, whether ambiguous ot not. (I am ignoring very old depth first, recursive decent parser). GCF parsing takes in general a time $O(n^3)$ where $n$ is the size of the input sentence. However, it will be only $O(n^2)$ for unambiguous, but possibly non-deterministic grammars. And they are usually linear for many grammars, or for a significant subset of the language defined by the grammars (see below).

I think it would be abusive to qualify these parsers as using unbounded lookahead. Actually they try simultaneously all parsing possibilities in parallel, and abandon some when further information from the input becomes incompatible with the attempted parse. This is not the same as not attempting a parse using some known facts about the rest of the string, which is what lookahead is about. Indeed, several of these algorithm may try not to attempt some parses, based on bounded lookahead information: this is true of Earley's, GLL and GLR. Furthermore, the concept of lookahead is meaningful for on-line algorithms, which is not really the case for GCF parsers.

The best way to survey this technology is probably a fast historical overview.

The (almost) oldest of GCF parser is the well known CYK algorithm. It is pure dynamic programming constructed directly on the grammar. It is extremely simple, but not best in performance.

The next one is Earley's algorithm (1968). Contrary to what is often said, it is not simple, at least in its general form, and there is no standard reference that I know regarding the format of the produced parse-trees (parse-forest). It is not clear that its performances are the best one might expect. Earley's algorithm is actually derived in a somewhat ad hoc fashion from Knuth's LR(k) parser construction. This of course diminishes in no way the importance of its contribution to introducing new parsing concepts.

This was generalized by Lang (1974), who proposed a general dynamic programming interpretation of any PDA, that could be combined with any PDA construction technique, such as LR, LL or precedence, giving techniques known as GLR or GLL parsing. When the technique an yield a derterministic automaton, the GCF parser works in linear time.

Tomita realized the first implementation of this technique, applied to LR(k) PDA construction in 1984, thus implementing the first GLR parser. Then it was also used for LL(k) PDA construction, in this millenium.

Regarding performance, people have often tried to improve it by using sophisticated PDA construction techniques that have been designed to increase the number of grammars that can be parsed deterministically. This folk wisdom is apparently ill-advised, as analyzed by Billot and Lang (1989). That suggests that efficient GCF parsers can have a fairly simple structure.

All of these parser can work fast enough on modern computers. They produce all possible parse-trees, in a condensed form called parse-forest. One issue may be the representation of the parse-forest which may be more or less convenient depending on the implementation. Of course, if the CF grammar is unambiguous, there is only a single parse-tree, which may do away with this parse-forest problem.

A major difference with traditional deterministic parsers is that the production of the parses is online for deterministic parsers, producing the left part of the parse-tree in synchronization with the reading of the corresponding left part of the sentene being parsed. With the GCF parsers, it is more an offline behavior, as you may have to wait the very end of the parsing process before you know what parsing structure is relevant.

Another issue is that I do not know how well parsing errors can be handled by current implementation. I do know that some very interesting work has been done on that by the Natural Language community.

Regarding your own grammar, I think that trying to use these techniques in a hand written parser is just looking for trouble. You woud have to have an excellent mastery of the technology. There is just nothing to be gained. But, given the way you state your question, if you want a simple implementation that you can master, for testing purposes, you may try the CYK algorithm. It main advantage is that, like Earley's algorithm, it works directly on the grammar, which you may find more intuitive.

Many parser generation system now propose some form of GCF parsing, but I have no personnal experience with any of them, thus no recommendations.

Answer 3

It's not clear to me if your grammar is truly ambiguous or if it is simply unbounded lookahead, but I think it is the latter; all the comments in your example use the phrase "does not find out until the end" which implies that the parser can eventually uniquely parse any correct sentence.

The simplest parsing algorithm for context-free grammars (CFGs) requiring unbounded lookahead is probably the Earley algorithm, which runs in $O(n^2)$ for unambiguous grammars (It's $O(n^3)$ in the worst case if the grammar is ambiguous, but that doesn't include the time required to enumerate all possible parses.) It is particularly simple if you have no rules with empty right-hand sides; all of the complications you might read about in the literature have to do with nullable non-terminals.

In essence, the algorithm is simply a non-deterministic version of normal top-down parsing. It involves the same predict / scan / complete(reduce) steps, except that the prediction is not deterministic. At each step, more than one prediction may be possible; both possibilities (or all) need to be considered. The trick of the Earley algorithm is a (straight-forward) method of representing the possibilities which doesn't exhibit exponential blow-up.

The effect is that all possible parses are explored in parallel, making it a bit tricky to use recursive descent. (You'd need parallel stacks, one for each viable alternative.) Instead, the algorithm uses a classic dynamic programming structure. It maintains a vector of sets of parse states; the vector corresponds to the input sequence so each token in turn is associated with a set of states. Each state corresponds to a point in a hypothetical call stack, so it contains information about where it is (in some right-hand side) and where it would return to on completion of the right-hand side.

A similar technique is used in a Tomita GLR parser, but it is based on a bottom-up algorithm rather than a top-down algorithm. Again, instead of a single parser stack, the algorithm maintains a collection of stacks. In order to keep the performance guarantee (like the Earley algorithm, it is $O(n^3)$ for any CFG and $O(n^2)$ for unambiguous grammars), it uses a slightly complicated data structure which allows the parallel stacks to share common prefixes and suffixes. Implemented correctly, this allows deterministic (i.e. bounded lookahead) grammars to be parsed in $O(n)$. (The Earley algorithm can be modified to achieve this as well.) [See note 1]

As with the Earley algorithm, you'll find lots of references on the net about issues with the Tomita algorithm in corner cases; again, all of these have to do with nullable productions. If you can write your grammar without nullable productions, you'll find implementing it with either Earley or Tomita to be a simple enough exercise.

Having said that, I don't really see the point of doing so. There is no particular advantage to hand-writing a state machine if you've got a state machine compiler, and these days it's easy enough to find a parser generators which can cope with unbounded lookahead grammars. (Even the venerable bison has a perfectly usable GLR option.)

---

Notes

1. In practice, unbounded lookahead is usually resolved in a reasonably small number of tokens. If it weren't, the (programming) language would be hard for human readers, which is generally considered bad style. For an unambiguous grammar, a GLR parser (or modified Earley parser) only incurs a high cost when presented with a text which requires lots of lookahead, so it is quite a practical parsing technique.