Re: Parsing Expression Grammar

Hans-Peter Diettrich <DrDiettrich@compuserve.de>
17 Sep 2005 13:55:17 -0400

          From comp.compilers

Related articles
[12 earlier articles]
Re: Parsing Expression Grammar paul@parsetec.com (Paul Mann) (2005-09-11)
Re: Parsing Expression Grammar paul@parsetec.com (Paul Mann) (2005-09-11)
Re: Parsing Expression Grammar DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2005-09-14)
Re: Parsing Expression Grammar gneuner2@comcast.net (George Neuner) (2005-09-14)
Re: Parsing Expression Grammar Meyer-Eltz@t-online.de (Detlef Meyer-Eltz) (2005-09-14)
Re: Parsing Expression Grammar cleos@nb.sympatico.ca (Cleo Saulnier) (2005-09-17)
Re: Parsing Expression Grammar DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2005-09-17)
Re: Parsing Expression Grammar Meyer-Eltz@t-online.de (Detlef Meyer-Eltz) (2005-09-18)
Re: Parsing Expression Grammar cleos@nb.sympatico.ca (Cleo Saulnier) (2005-09-22)
Re: Parsing Expression Grammar schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-09-22)
Re: Parsing Expression Grammar schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-09-22)
Re: Parsing Expression Grammar rsc@swtch.com (Russ Cox) (2005-09-22)
Re: Parsing Expression Grammar cfc@shell01.TheWorld.com (Chris F Clark) (2005-09-22)
[9 later articles]
| List of all articles for this month |

From: Hans-Peter Diettrich <DrDiettrich@compuserve.de>
Newsgroups: comp.compilers
Date: 17 Sep 2005 13:55:17 -0400
Organization: Compilers Central
References: 05-09-023 05-09-045 05-09-058
Keywords: parse
Posted-Date: 17 Sep 2005 13:55:16 EDT

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


Post a followup to this message

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