Re: Parsing Expression Grammar

On 22 Sep 2005 23:51:43 -0400, Chris F Clark
<cfc@shell01.TheWorld.com> wrote:


>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.


That depends on your definitions ... syntactic predicates are extra
grammatic computation - meaning they are (generally) nicety rather
than necessity. Offhand I can't think of a case of a grammar that
could be written using a syntactic predicate but not without.




>> 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.


I beg to differ. The tokens may not yet have been *consumed* by the
parser, but they most definitely have already been constructed else
the rule reduction would not have been attempted.


And LR mid-rule actions require complete syntactic predication of the
rule head - if not the entire rule - because the user actions can't be
undone and should not be executed unless the parse is committing to
the rule. Operationally it makes the entire rule head a separately
matched sub-rule, which may be logically incorrect.




>> 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.


???


AFAICT I never said anything about which method has _more_ context
information available - whatever you think that means.


George

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