Re: Parsing Expression Grammar

On 11 Sep 2005 11:11:57 -0400, "Paul Mann" <paul@parsetec.com> wrote:


>Now LL(k) can handle anything in the universe, but the discussion is
>about which is easier to program and easy to read both.
>
>For me, LL(k) is not easier to program than LALR(1).


If you disregard mid-rule actions [more on that later], I think they
are equally easy ... or equally difficult if you prefer.




>About actions in the middle of a rule with LL(1) parsers ...
>
>I have hardly ever needed to do this. Usually, there is already a need
>for a nonterminal at this point in the rule and when reducing the
>nonterminal, I can have an action take place easily with LALR.
>
>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.


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


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.


LL handles such problems more efficiently because the context can be
decided before dependent tokens have been constructed. It minimizes
the work the parser has to do while maximizing the amount of
disambiguated information that can be provided to later stages.


I'm not claiming there are reasonable programming languages that
require such processing, but I can think of a lot of other uses for
parsing tools which would require context dependent lexing.


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


That's a fine philosophy so long as avoiding it isn't unnecessarily
complicating your life. The main reason for computing in the parser
[or lexer] is to reduce the ambiguities that later processing must
deal with.


George

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