Re: Parsing Expression Grammar

Detlef Meyer-Eltz <Meyer-Eltz@t-online.de>
14 Sep 2005 21:25:08 -0400

          From comp.compilers

Related articles
[10 earlier articles]
Re: Parsing Expression Grammar gneuner2@comcast.net (George Neuner) (2005-09-10)
Re: Parsing Expression Grammar DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2005-09-10)
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)
generated code Meyer-Eltz@t-online.de (Detlef Meyer-Eltz) (2005-09-22)
[17 later articles]
| List of all articles for this month |

From: Detlef Meyer-Eltz <Meyer-Eltz@t-online.de>
Newsgroups: comp.compilers
Date: 14 Sep 2005 21:25:08 -0400
Organization: Compilers Central
References: 05-09-023 05-09-045
Keywords: parse, design

> "Paul Mann" <paul@highpersoft.com> wrote
>> "Chris F Clark" <cfc@shell01.TheWorld.com> wrote in message
>>> But, as a potential language designer, you need to think long and hard
>>> about why you want to create a language which has no LL(1) grammar.
>>
>> Answer: Readability for human's sake.


> First of all, readability in the grammar. Perhaps that is what I was
> thinking about, rather than readability in a programming language.
> But I might be able to find some cases where LALR(1) allows greater
> readability in the language being parsed also.


> 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.
There is a third aspect of the readability besides the readability of
a programming language and the readability of the grammar: the
readability of the generated code. LL(1) parser generators can make
extremely elegant code which is to read, to understand and to debug
very easily:


To take your example, a sketch of the code which e.g. the
TextTransformer creates for the StatementList-production would look
like:


return_type StatementList( paramter1, ... )
{
    do
    {


        return_type t = Statement( p1, ...);
        // consumes the tokens of the Statement


    } while( the next token is the beginning of a Statement )
}


Code for actions which shall be executed can be embedded into the
production and and appears in the generated code in the appropriate
places.




> Most of the action takes place when processing the AST anyway. So
> actions in the middle of a rule are not the main issue in compiler
> front ends.


> I don't like to see code in a grammar any more than I like to put
> assembly language code in my C++ programs.




The comparison limps (German idiom) and in my opinion it reveals a
point neglected by many designers of parser generators: a parser
generator produces a complete program only in the rarest cases. Only
in connection with the semantic actions a parsed text gets really
processed. And for this, without doubt, an AST often is useful or even
necessary. But sometimes the creation of an AST is shooting at
sparrows with cannons (German idiom again). Why create an AST, if the
text can be processed directly? The latter is more intuitive and
faster too. The user of a parser generator should be enabled to
understand the generated parser and he should be free to decide, how
he wants to complete the groundwork that is done by the parser
generator. The user should not be forced to do, what the parser
generator likes, but should be able to do, what he likes


I am interested to know, how the code for the different LR-Parsers
would look like. I only know yacc/bison code which for my feeling is
quite awful.




Regards


Detlef Meyer-Eltz


--
mailto:Meyer-Eltz@t-online.de


url: http://www.texttransformer.de
url: http://www.texttransformer.com


Post a followup to this message

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