Re: Parsing Expression Grammar

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

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