Re: Parsing Expression Grammar

George Neuner <gneuner2@comcast.net> writes:


> The need to embed actions depends greatly on the language ...
> resolving context sensitivity requires predication and predication
> requires mid-rule computations.


I think predicates are wonderful. I don't know that predicates
"require" mid-rule computations. Syntactic ones don't. Semantic
predicates "are" mid-rule computations, so yes they require them.


> LR can be inefficient for a context sensitive language because
> reductions aren't applied until all the tokens have already been
> constructed. The usual LALR work around is either to defer
> everything until later [the approach you seem to favor] or to create
> back channels to the lexer and perform as much disambiguation as
> possible there. But neither of these approaches handle languages
> which must be lexed differently in different contexts.


Presuming one has mid-rule computations (and those are not hard to
implement in an LR parser generator), one can also determine context
before the dependent tokens have been constructed. It is a persistent
myth that LL parsers have inheriently more context information than LR
parsers. It is only true, if one has null productions that are used
in multiple contexts and then only if one is doing SLR or LALR
parsing, so that states with different lookahead sets are merged. If
one has an LL grammar for the language, an LR parser will also have
nicely disambiguated contexts. The myth persists because an LR
grammar that is not LL will have ambiguous contexts, which is why the
grammar is not LL. Note, when using mulitple lookahead (LL(k))
grammars, there are also places where the tokens have to be
constructed before the context is determined, i.e. for the first k
tokens of rules that need the lookahead for discrimination.


However, these are just minor quibbles. It isn't context that sells
most users on LL over LR parsing, it is recursive descent output.
That is a much more "transparent" output format than the best labelled
table driven approach. So, if you need to debug your grammar, you
will probably prefer an LL generator that outputs recusrive descent
code. (Now, I agree with Cleo Saulnier, that I personally prefer LR
table output, but I've had more than a little experience dealing with
it and the Yacc++ tables reflect my mental habits.)


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

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