Thursday, September 23, 2010

Parsers and grammars

A friend expressed an interest in an improved version of yacc. I think this fits the bill:

It's always re-entrant and thread-safe, with some other advantages and all the best lessons of
yacc (e.g. error-handling).

Anyway, I'm nearly sold on PEG (Parsing Expression Grammars).

Unlike LR parsers, a PEG parser does not require a separate tokenizer.  It's very elegant, much like BNF.  I want to do some runtime comparisons, but I expect it to be comparable.  I will try to attach a pegleg grammar that I wrote to solve this (with the added constraint of left-associativity):
Just install peg/leg, run 'leg' on the attached file (if I ever manage to post it to this blog), and compile.

Here is an interesting table:

To learn a ton about PEG:

In a nutshell, a Context-Free Grammar parser like
yacc is meant for natural language, based on Chomsky's work, not for an unambiguous computer language.  PEG simplifies the parser by eliminating ambiguity in the grammar.

No comments:

Post a Comment