3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Do you need a parser, or do you want to train/learn the concepts? $\endgroup$ – Raphael Jul 2 '15 at 8:02
  • $\begingroup$ I'd rather understand the concepts. I'm running blind and no amount of complicated control structures is helping. $\endgroup$ – skeggse Jul 2 '15 at 8:11
  • 2
    $\begingroup$ Okay. Why do you need your grammar to be ambiguous? That's generally a bad idea (for programming languages). $\endgroup$ – Raphael Jul 2 '15 at 8:11
  • 1
    $\begingroup$ @Raphael So I fully approve the idea, though the OP's reasons for doing it have yet to be fully understood. What I think is a terrible idea is to do it by hand, since it is probably more work than using a generator, and very prone to errors and maintenance difficulties. General CF parsing has a technology of its own, and it can be very painful when you do not fully master its concepts. Also there are good and bad ways to go about it. But before going into more technical issues, I would have to understand what the OP is really after, and his question is very very long and technical. $\endgroup$ – babou Jul 2 '15 at 12:43
  • 1
    $\begingroup$ @skeggse: If you have an unambiguous grammar which requires unbounded lookahead to parse, then that is what you have; you need no more vocabulary than that. A lot of work has been done to create efficient algorithms for parsing such languages, but I don't know of any approach which attempts to compile the grammar into a computet program. My question is ewhy you don't want to make use of that research and use a parser generator (which will produce some kind of state machine)? Unbounded lookahead can, in many cases, be parsed efficiently. Have you tried bison's GLR parser? $\endgroup$ – rici Jul 3 '15 at 2:19
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hmmm that sounds promising. I couple my parser and lexer, does this mean I'd need to buffer a bunch of tokens for the FSA so I can actually parse them when it's finished? $\endgroup$ – skeggse Jul 3 '15 at 16:44
  • $\begingroup$ @skeggse Yes. Since you cannot produce a deterministic PDA to parse according to that grammar, you hav to consider something that is not a PDA, losing some of the PDA properties, such as its online behavior. So you will have to scan the input to find the information, and save it in a buffer to be scanned by your parser. But you should first make sure that the arbitrarily long structure separating the parser head from the relevant token can be identified in some precise way, even if it is not actually parsed. $\endgroup$ – babou Jul 3 '15 at 22:00
  • $\begingroup$ I ended up going with this answer, in part because I based my final solution upon your answer, and in part because your answer directly responded to my "actual question" (vs the original written question). I built something resembling a recursive descent parser, which did a quick run through ambiguous statements or expressions to figure out how it should be parsed, and simply signaled to the actual parser how to proceed. $\endgroup$ – skeggse Jul 5 '15 at 1:14
  • $\begingroup$ @skeggse RLR (Regular LR) is the DFA based method developed with a theoretical model. Your technique is using 2 passes, more like lexical analysis, but using a simplified PDA. That is a perfectly reasonable solution. It is harder to define a theoretical model for it because it should allow you to recognize some non context-free languages, possibly $\{a^nb^nc^n|n>0\}$ dependin on exact specification. Instead of a first pass, you can call the auxiliary automaton just when needed. There are other variations possible. $\endgroup$ – babou Jul 5 '15 at 8:18
  • 1
    $\begingroup$ @skeggse You may be interested in ANTLR, a (free) compiler generator. It generates LL parsers (conceptually close to recursive decent) and it can handle arbitrary lookahead. That is with separate lexing stage (big advantage) and nicely integrated features for working on the parse tree resp. AST. $\endgroup$ – Raphael Jul 8 '15 at 11:45
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I admit that my second paragraph was a tad imprecise, but "abusive" sounds kind of strong to me. Maybe this is just a human language issue. Anyway, I think I fixed it. (Or am I being egoistical in thinking that an offhand comment in your answer apparently unrelated to the OP might have to do with a usage in another answer?) Speaking of imprecise terminology, I'm not convinced by your usage of "online". The GLR parser will perform the reduction at precisely the same point in the input as it would have been performed by an LR() algorithm using an oracle. It is not in any way delayed... $\endgroup$ – rici Jul 3 '15 at 3:37
  • $\begingroup$ ... although the child reductions will be delayed (but not delayed with respect to a lazy implementation of the oracular algorithm). Here, of course, the oracle could be replaced by deleting the inapplicable parts of the grammar and using an LR(k) machine to parse the remainder. The Earley algorithm as presented in the paper is not online, since it produces the entire parse tree (if needed) at the end in a pass over the state list generated during the parse, but practical implementations don't work that way. $\endgroup$ – rici Jul 3 '15 at 3:40
  • $\begingroup$ @rici There are often approximations an unwarranted statements in parsers descriptions. That does not help cleaning up this cluttered technology. I did not mean "abuse" in he strong sense of human relations implying that you are cheating people, but in a more etymological and technical sense meaning "misuse". It feels more precise than "misuse" as I perceive it as meaning used beyond normal use (used up, etymologically), rather than simply wrong use. "Misuse" implies lack of meaning, while "abuse" indicates that it has meaning, but exceeding its usual limitation. $\endgroup$ – babou Jul 3 '15 at 7:26
  • $\begingroup$ @rici Regarding my use of online. I think we agree that deterministic parsers (i.e., PDAs) are online algorithms. This allows in particular starting the semantics phases of compiling in step with the parsing, before it terminates. What you disagree with is my use of the word "offline" in the GCF case. I was aware that some work is done, but not all, so I said more carefully "it is more an offline behavior", implying that there are things done online. But nothing can be certain in general before the end, so semantics processing cannot be started before the end in general. $\endgroup$ – babou Jul 3 '15 at 7:27
  • $\begingroup$ @rici Of course, this is only a first approximation assessment. There are techniques in the literature to separate the known parts of the result from the ambiguous or yet undetermined ones. Practical grammars are not supposed to be too badly behaved, so that this can be mitigated a lot. - - - BTW, Erley's algorithm is in no way the simplest one of these parsers. There are much simpler algorithms, and more perspicuous and shorter ways of explaining this parsing technology. It is great historically, but so are many great papers that few people read. $\endgroup$ – babou Jul 3 '15 at 7:32
3
$\begingroup$

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.
$\endgroup$

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.