Re: Parsing Expression Grammar

Sylvain Schmitz <schmitz@i3s.unice.fr>
22 Sep 2005 23:42:52 -0400

          From comp.compilers

Related articles
[15 earlier articles]
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)
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)
Re: Parsing Expression Grammar schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-09-22)
Re: Parsing Expression Grammar paul@parsetec.com (Paul Mann) (2005-09-22)
[12 later articles]
| List of all articles for this month |

From: Sylvain Schmitz <schmitz@i3s.unice.fr>
Newsgroups: comp.compilers
Date: 22 Sep 2005 23:42:52 -0400
Organization: Compilers Central
References: 05-09-023 05-09-045 05-09-058 05-09-071
Keywords: parse
Posted-Date: 22 Sep 2005 23:42:51 EDT

Detlef Meyer-Eltz wrote:
  > 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.


I think it's more a matter of optimized C style than a real problem on
the LR readability. Maybe you would like it better in a functional
version, like the CPS of Essence
[http://www.informatik.uni-freiburg.de/proglang/software/essence/].
      And clearly, my currently favorite piece of parser on the readability
level is LL-based, namely Parsec
[http://www.cs.uu.nl/~daan/parsec.html]; for instance, this piece of
Haskell code parses TeX environments:


      environment :: Parser ()
      environment = do{ name <- envBegin
                                        ; environment
                                        ; envEnd name
                                        }
                                <|> return ()


      envBegin :: Parser String
      envBegin = do{ reserved "\\begin"
                                        ; braces (many1 letter)
                                        }


      envEnd :: String -> Parser ()
      envEnd name = do{ reserved "\\end"
                                        ; braces (string name)
                                        }


Of course, everything comes with a price, so when Detlef Meyer-Eltz wrote:
  > I guess with "contortions" you mean the result of factorizing
  > tokens out, to make a grammar LL(1) conform. For compiler generators
  > with look ahead capabilities as ANTLR, Coco/R or the TextTransformer,
  > this isn't necessary any more.
I couldn't help thinking about the explosive parsing complexity
unbounded lookaheads and backtracking sometimes involve.


Cleo Saulnier wrote:
> SLR - no lookahead on reduce.
No, SLR parsers use the Follow sets as lookaheads.


> For me, SLR and LALR are a waste of time. LALR jumps through way too
> many hoops to not compute all the states that LR does. LR can simply
> merge states when it's appropriate and get close to the same table sizes
> with the benefit of handling more special cases. Yes, yes, LR will
> create more states, but not necessarilly that many more entries once
> compressed.
Yes, you can then compress the LR tables, but for this you need to
compute them first. Even now, this is not the kind of computations for
which one is happy to wait for termination. And if you compress on the
fly, then you are jumping through hoops as well.
      Then, I agree LR parsing is extremely nice, and that to spend more
time to generate a faster parser is overall better.


--
Regards,


      Sylvain


Post a followup to this message

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