Re: Parsing Expression Grammar

George Neuner <gneuner2@comcast.net>
25 Sep 2005 12:51:36 -0400

          From comp.compilers

Related articles
[22 earlier articles]
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)
Re: Parsing Expression Grammar cfc@shell01.TheWorld.com (Chris F Clark) (2005-09-23)
Re: Parsing Expression Grammar gneuner2@comcast.net (George Neuner) (2005-09-25)
Re: Parsing Expression Grammar cfc@world.std.com (Chris F Clark) (2005-09-25)
Re: Parsing Expression Grammar cfc@TheWorld.com (Chris F Clark) (2005-09-27)
Re: Parsing Expression Grammar cfc@shell01.TheWorld.com (Chris F Clark) (2005-09-27)
Re: Parsing Expression Grammar gneuner2@comcast.net (George Neuner) (2005-09-30)
Re: Parsing Expression Grammar cfc@shell01.TheWorld.com (Chris F Clark) (2005-10-02)
| List of all articles for this month |

From: George Neuner <gneuner2@comcast.net>
Newsgroups: comp.compilers
Date: 25 Sep 2005 12:51:36 -0400
Organization: Compilers Central
References: 05-09-023 05-09-045 05-09-053 05-09-107
Keywords: parse

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


Post a followup to this message

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