Re: Parsing Expression Grammar

Detlef Meyer-Eltz wrote:


> > I find these LALR(1) grammar rules to be more readable and more
> > natural:
>
> > StatementList -> Statement
> > -> StatementList Statement
>
> > Than the LL(1) equivalent:
>
> > StatementList -> Statement
> > -> Statement StatementList
>
> > I know you do it like this:
>
> > StatementList : Statement+
>
> The last version seems to be the clearest of all to me.


The last version has several definite advantages:
- It doesn't imply any left/right recursion.
- It doesn't require to write down the repeated expression multiple
times.
- It looks like structured code, in contrast to the preceding spaghetti
code.


In this form the rules can be understood immediately by people favoring
either LL or LR grammars. An expansion into the preceding LALR or LL
equivalent can be automated easily, in contrast to the opposite
direction; the opposite direction requires to recognize and verify
first, that the Statement expression is the same in all lines, and that
the StatementList is the name of the rule itself, before one can know
for sure whether the rule describes a sequence of Statement or something
else. Every human reader has to perform these steps as well, so that the
last condensed form certainly is easier to read *and* understand.


To the writer the last form is preferable as well, it's not only
shorter, but it also doesn't leave a chance for typos in the required
repetitions of the same tokens or expressions - also a simplification of
grammar maintenance.
It's debatable whether the repeated item has to be a single token, or
can be an expression. In the given example the Statement rule may be so
complex, that it should become an explicit rule. In other cases, with
simpler expressions, an additional rule can be omitted, provided that
this rule is not used in multiple places in the grammar.


There may exist situations (do they?), where the recursion order is
important, but in the given example the Statements certainly have to be
processed in their input order (first to last).


DoDi

Return to the comp.compilers page.
Search the comp.compilers archives again.