Lambda the Ultimate

Even with traditional tools you can't escape from algorithm-oriented syntax design. The most obvious difficulty comes from restrictions on left recursion or right recursion which cause problems expressing the correct associativity in the grammar.

Associativity is not a problem if you use an operator precedence based algorithm, like the Shunting Yard algorithm. And as current versions of gcc show, you can use the Shunting Yard algorithm alongside a traditional top-down parser, letting the Shunting Yard algorithm handle just the infix expression portions of the grammar.

A preprint PDF of the SP&E article is here. The Lua implementation is really interesting; it supports both a Snobol-style pattern language and a notation that combines Ford's with regular expression style. Both are translated into domain-specific virtual machine instructions.

PEGs don't need to be implemented in packrat parsers. One of the more popular PEG parser generators, Rats!, let's you specify that some productions should not be memoized.

In fact, this paper (on DCGs rather than PEG parser generators) runs a bunch of tests on a large body of Java code and concludes that that not memoizing is a better default for most productions. They speculate that human readable languages generally avoid the kind of excessive, large scale backtracking that packrat parsers are supposed to protect against. At large scales, we hate backtracking just as much as the parser does. It's only at very small scales, where we apparently see things more holistically, that backtracking can get excessive.

As someone who is working very hard on my next-gen parsing framework Gazelle, people often ask me why I'm not using PEGs. PEGs are all the rage right now.

Nice to see some people who are attempting to make real progress in a domain that was considered dead or case-closed for a while. Your criticism on PEGs is spot on btw.

Since we are at it I'm going to shamelessly advertise Trail which is part of EasyExtend. Currently I'm working on careful generalizations of Trail NFAs towards function networks. Those FunNets let Trail finally deal with left recursion / cycles in EBNF grammars without transforming the grammar.

The question of whether a nondeterministic choice operator (as is found in myriad LALR(1) tools such as yacc) or a deterministic choice operator (as found in PEG) is better--reminds me of similar arguments concerning if statements and the like in programming languages themselves.

Many of the same issues arise.

Virtually all production PLs have deterministic if statements; or something resembling them. (Chained ifTrue: ifFalse: methods and the like in Smalltalk have the same effect). Many programming languages don't have an unconstrained nondeterministic choice operator--the C-style switch statement is nondeterministic in its operation, but the langauge requires all the branches be disjoint (default: is handled as a special case which preserves this rule). Pattern-matching in functional programming languages is also deterministic. Two notable area where deterministic choice is generally not employed (because the choices are specified in separate modules, making establishment of an order problematic) are in multiple dispatch resolution, and multiple inheritance/delegation resolution. Both of those are thorny problems; which are generally dealt with either by arcane (and often surprising) rules to break ambiguity, or by making ambiguous cases an error which the programmer must explicitly resolve.

The advantage of deterministic choice is obvious--it permits using wildcards. The ubiquity of this in pattern-match in Haskell or ML needs no further comment. In the context of parsing, it allows the mixing of rules matching specific keywords, i.e. "true", with rules matching arbitrary alphanumeric strings, i.e. [a-zA-Z]*. In nondeterministic parser tools, one can't do that easily; so lexing is treated as a separate phase by a tool which is deterministic. (Or at least sort-of; the "longest leftmost" rule used by many lexers is positional-deterministic with regard to strings of equal length).

The main objection to determinism (besides the fact that deterministic choice is non-commutative) is that in many cases, the order is arbitrary--and if you think two productions are disjoint (or one is a subset of another) and they're not; you're potentially in for a surprise. You're still in for a surprise with nondeterministic choice (the tool might do whatever it wants), but in many cases you get warned by the tool that your language is ambiguous. Of course--one of the easiest ways to resolve such ambiguities is with--deterministic choice.

With many existing tools which don't have explicit deterministic choice, ambiguities (at the parser level) are handled by various other means, such as a) changing the grammar so that the ambiguity is no longer present, b) ignoring them and accepting the tool's default behavior (a common way of dealing with shift/reduce conflicts); c) using associativity annotations to resolve the ambiguity--something which works in yacc, but is kinda kludgy when the production in question isn't an infix binary operator, d) using the semantic rules to modify the parser's behavior (such as rejecting a production), or e) annotating the text to be parsed with a preprocessor (lex is, after all, just an entrenched case of getting around the limitations of yacc) or f) hope and prayer.

The conclusion to this rant: Why must we choose between deterministic and non-deterministic choice? Ignoring parsers that exploit parallelism when faced with multiple possible productions for a given nonterminal, the implementation has to choose which one to try first anyway... I think that there is ample room for both.

I had understood Joshua's comment PEGs define away ambiguity, which means that you don't know where the real ambiguity is to be making the same point I had made that non-determinism makes it easy to ask the right questions about language syntax, though making it rather better. Both of us, I think, are coming from the point of view of what classes of formal language provide the best basis for designing the syntax of fully-fledged programming languages.

Your comment about the advantages of cleaving to typical programming language semantics are fair enough, but they are not very appropriate for this design space, but are serve rather as a justification for tools such as Perl 6's rules. I agree, for these purposes, but this is not anything like making a case that PEGs are a substitute for traditional grammars.

Of course, once PEG-like engines are widely deployed, more and more domain specific languages will be designed using them, so we had better get used to the idea that they are de facto grammars for designing programming languages.

Given a parser design tool which permits both forms of determinism, you can have the following workflow:

1) Specify your grammar using ND choice, other than "obvious" cases like the keyword-vs-identifier case, which requires determinism to resolve.

2) If the tool informs you of an ambiguity, decide how to deal with it. If the solution is to modify the grammar to eliminate the ambiguity, do so, and go back to step one.

3) If, you decide to resolve the ambiguity by fiat (such as how the dangling else problem is resolved in C-ish languages), simply re-write the rule in question to use deterministic choice. In this case, the rule would be if {expr} else {expr} / if {expr}. If for some reason you prefer the else to bind to the outermost if, then if {expr} / if {expr} else {expr}.

I must admit, my in-depth understanding of the numerous useful subsets of the CFGs, and how efficient they are to parse, is a tad rusty; so there may be some Very Good Reason that determinism and nondeterminism might not mix well--a language needing both might no longer admit an efficient parser. If so, that is obviously a design issue to consider.

But if one is designing a formal language syntax for human programmers (the class of parsing most relevant to LtU)--where one must avoid ambiguity, but must provide the human with textual cues and respect certain stylistic conventions that we silly humans have come to expect--one is probably not dealing with terribly deep parse trees (and lots of backtracking) to begin with. (How much of a compiler's time and memory is spent parsing, vs. other things such as reading in the program text, or semantic analysis, code generation/optimization, etc?) Constructs which do "go deep" in most PLs tend to involve fully-bracketed forms, dangling else excluded.

Parsing natural language is another matter altogether; and here, nondeterminism *is* highly appropriate, given that natural languages themselves are inherently ambiguous. Even so, there are undoubtedly situations where a deterministic rule might be desireable. For machine-generated structural data, you shouldn't need to roll your own parser, just use XML or sexprs or some other unambiguous, fully-bracketed syntax and be done with it. :) Of course, I'm being a bit disingenuous here, as there is undoubtedly the need to parse existing data that wasn't generated with a nice easy-to-parse format...

Context-free grammars and parsing expression grammars are full of traps...

2) If the tool informs you of an ambiguity

But ambiguity in context-free grammars is undecidable. Your tool might tell there's something fishy about your grammar, like an LALR(1) conflict---and the absence of such warnings then indicates that the grammar is unambiguous. Or you've learned to stop worrying and to love generalized parsing, but then you'll learn about ambiguities at run time---or your users will, because your test cases did not unveil one particular ambiguity.

If for some reason you prefer the else to bind to the outermost if, then if {expr} / if {expr} else {expr}.

This parsing expression does not match any if {expr} else {expr} construct: observe that the first part if {expr} is always matched by the first alternative, thus the expression matches this first part and leaves you with else {expr} on your hands, most likely ending up in a parse error. And, maybe because it's only fair that important usability issues should be equally hard for PEGs as for CFGs, the question whether one alternative of a PEG expression is "useless" (as the if {expr} else {expr} above), is not decidable in general.

I'm not sure anyone prefers not to use "longest match" in case of the dangling else disambiguation.

Organizing longest matches by hand can be become very tedious for larger grammars. So let's say we want a tool that organizes our pattern according to longest matches ( doing left factoring indeed ). Now the required analysis for those tools turns us back into the waters of CFG parsers with lookahead strategies ( or Thompson NFAs alternatively ). But that's precisely where we came from. PEGs are a step backwards that is advertised as a step forward.

though when dealing with parse trees containing some mixture of terminals and nonterminals, how one defines the "length" of something is an interesting question. In the case of shift/reduce conflicts, choosing to shift rather than reduce makes sense; but s/r conflicts are easy to deal with.

More generally, what we really need is better ways of dealing with disambiguity (at the specification level). Longest match is often times a good rule, though not always. Leftmost match--i.e deterministic choice--makes good sense for cases like keyword-vs-symbol; though what we probably really want there is "most specific match", something that is undecidable in the general case. (This is how, to a first approximation, multiple-dispatch issues are resolved in many languages). In still other cases, what we really want is to become context-dependent; the correct choice depends on some information on the semantic stack, but not directly expressible in the grammar itself. Ugly as it is, quite a few programming languages that start with the letter "C" work this way.

I don't see this as a battle of PEG vs classic LALR(1) vs classic LL parser strategies, and I'm a bit puzzled by the hostility to PEG or any other tool. (Perhaps PEG has been over-promoted by its proponents; I don't know). In the end, a parser is Just Another Computer Program, one takes text in and spits annotated syntax trees out (consuming some amount of time and temporary storage in the process). How it is implemented is of key importance to the developer, but of minimal importance to the user; who is mainly concerned that a) it works correctly on correct input; b) it produces reasonable error messages on invalid input (the hardest part of writing a production-grade parser is this); and c) has acceptable time/memory performance, with "acceptable" being highly application-dependent.

I'm a bit puzzled by the hostility to PEG or any other tool.

Making tools is also about making good things and for practitioners it can mean the distinction between a good and a bad day at work. So people struggle endlessly about their qualities and try to improve them and see how to not waste their time. They are certainly not indifferent even if the production process becomes invisible in the end product. I tend to think this is generally a good thing. At the downside are religious flame wars that are just another medium for acting out male aggression.

[...] In the context of parsing, it allows the mixing of rules matching specific keywords, i.e. "true", with rules matching arbitrary alphanumeric strings, i.e. [a-zA-Z]* [...] so lexing is treated as a separate phase by a tool which is deterministic

Having written a lexerless LALR(1) parser generator, I'd just like to say that this (important) problem can be resolved with a simple (maybe some would disagree with "simple") transformation of the grammar that's very easy to recover from when constructing the parse tree.

Essentially the solution I came up with was to build a trie out of the set of keywords, and use it to "remove" the keywords from the sort of regular expression you mentioned (yielding a set of regular expressions under "non-deterministic choice"). To avoid an explosion in table size, I also rewrite keyword references (and their substrings in the "chopped up" regex, along with some other related regexes) to maximize sharing of states.

Some might argue that the solution above is more complex than a lexer, but at this point I'm comfortable with it and I think that it's worth it to avoid having a lexer. I think that it's similar to the additional complexity of converting an LALR generator to GLR (with efficient sharing of stack prefixes and such), plus I can say that the parsers I generate are fully deterministic.

I don't think that your first point is valid, in principle anyway. We have a pretty good idea how to implement CFGs, but PEGs are still in their infancy. I'm not sure what the current state of the art is in PEG-land, or how close Aurochs is to that; but they've improved memory consumption by more than an order of magnitude since you've posted this comment. I don't think anybody really knows how good PEG-based implementations will become.

Arbitrary LL(1) grammars cannot be recognized in O(1) space in the worst case: matched parenthesis, for example, might require O(log n) if you use integers to represent the stack, but most parser generators would be O(n), basically using a Peano representation.

You are comparing worst-case to common-case performance, which is definitely a fallacy. Packrat parsing is only one possible way to implement PEGs. Even without venturing into the realm of entirely new algorithms, hybrid approaches integrating existing techniques should be able to greatly improve common-case performance.

More to the point, most parser generators are used to build an abstract syntax tree, so unless you offer the ability to fuse certain syntax-based computations into your parser, (the trivial case would build nothing if you just want to recognize the grammar) the overall result will be O(n) anyway, both best- and worst- case.

On the other hand, your second point is definitely good food for thought. My impression is that the popularity of PEGs are largely due to the perception that PEGs are more easily embedded as library-based DSLs; parsing combinators set off the whole PEG craze. My impression and/or this perception might be false, however.

is

A Grammatical view of Logic Programming by Deransart and Maluszynski (1993).

A lot of similarities exist, of course, between parsing (and writing parsers in a formalism such as BNF or similiar, augmented however you like) and logic programming in a Prologue like language (expressing a logical system as a set of Horn clauses). You've got terminals (facts), nonterminals (rules), etc. You have nondeterministic operators (the choice operator in parsing, the disjunction operator in Prolog) and various backtracking strategies.

At a more fundamental level, logic systems expressed in Horn clauses, and the class of languages expressed by CFGs, are both "compromises". They are proper subsets of the larger spaces of "interesting" logical systems/languages, which are commonly used as they are efficiently decideable. And in both cases, the constraints of the formal system are commonly "hacked around" in various ways--one wonders how one expresses a "cut" in Yacc. :) (%left or %right, skillfully employed, perhaps?)

One difference that comes to mind between the two worlds is the effect of nondeterminism. It isn't as big of an issue in the logical programming world, as a statement in a system is true if it can be satisfied by any solution over the axioms in that system; having multiple such solutions doesn't cause a problems. (Until you try to change the system to reflect a new reality, which is why the RDBMS guys worry about normalization so much). If the only output of a parser was a yes/no decision--"is the string in the language?", then nondeterminism would similarly be harmless. But with parsers, the output of a parser is a syntax graph (tree) and not a boolean; and different ways of parsing the same text might produce different but valid parse trees. In some applications (natural language processing) that's OK; other (non-context-free) algorithms are used to decide what is meant; but in programming languages that's usually Not a Good Thing.

Kay: See OMeta Optimizer for an example. The object-based output of the compiler step is passed through the optimizer, which is just another "parser".

My understanding of the intent behind OMeta is that it seeks to use pattern matching and transformation as a control structure, generally. The "mood specific language" capability is an offshoot of that.

They're using OMeta now for naïve code generation (you know, the backend of a compiler), Piumarta's tiny TCP implementation, code analysis, and so on.

Writing a parser for an existing language is a bit different from designing a new one. Natural languages aren't context-free, likewise for many computer languages (including C/C++)--though many have a context-free "structure" that can be employed to do much of the work, with contextual clues (such as a symbol table lookup, in this case) used to handle ambiguity.

If you are designing a New Programming Language, and have control over its concrete syntax, one of the choices is to make it easily parseable (without ambiguity, or with ambiguity which is easily resolved both in the parser implementation and the language manual); knowledge of the limits of CFGs (and the subsets thereof supported by parser tools) is essential. Designing an ambiguity-free language isn't hard; S-expressions are a trivial example. However, such languages tend to look "artificial" to humans; who generally converse in context-sensitive and ambiguous languages. Natural languages like English or German being examples; the language of mathematics as well.

Syntax matters far less than semantics, ultimately. But it does matter.