4 ms·

asking as a total noob, how does a PEG grammar compare to ANTLR's grammar? seems very similar

• bad_user 16y ago
  ANTLR is a parser generator for CFGs and allows for flexibility in regards to ambiguity and context-dependent grammar by means of predicates. But the generated parsers are LL(k) (with enhancements, LL(star) they call it) and this brings certain problems with it, like the rules cannot be left-recursive. As Terrence Parr said "LL recognizers restrict the class of acceptable grammars somewhat". PEG rules cannot be ambiguous, as rules are tried out in order until one matches. Also recognizing tokens is part of processing rules, rather than having a separate lexer (which ANTLR does - lexer rules are separate from parser rules, and the code generated reflects that) - which means it is easier to deal with certain kinds of ambiguities. This can work to your disadvantaged however. For example languages where whitespace is significant, like in Python where blocks are delimited by indentation level, the lexer needs to be hacked by hand (i.e. you have to cheat somewhere, because that's context-dependent and a bitch to deal with). In general, ANTLR generated parsers are more efficient and allow for certain hacks to be implemented easily, but PEG grammars are easier to write and allow for certain context-dependent rules that are very hard to implement in ANTLR. And PEG grammars need backtracking as an implementation detail and although memoization reduces the impact of that, the result will have less performance. Basically for quick prototypes I would choose PEG grammars and for industrial strength something like ANTLR. Btw, here's a cool Java/Scala library for creating PEG parsers, and it's much lighter and easier to setup than ANTLR: https://github.com/sirthias/parboiled/wiki https://github.com/sirthias/parboiled/wiki And the syntax is basically Java/Scala: https://github.com/sirthias/parboiled/wiki/Simple-Java-Example https://github.com/sirthias/parboiled/wiki/Simple-Java-Examp... AND the Scala way of defining grammars is so cool I can't even describe it - basically you can create new grammars by inheriting existing grammars - say you have a general SQL syntax that you want to specialize for MySQL / PostgreSQL. Works like a charm ;)
• kragen 16y ago
  PEGs backtrack to handle multiple alternatives, and can bound their parsing time to linear by memoizing; ANTLR generates LL(*) parsers (despite its name!) which use a token-lookahead mechanism to bound their parsing time to linear (and, incidentally, run much faster).