Re: Parsing Expression Grammar

On the topic of context sensitive parsing (using mid-rule actions),
I replied to George Neuner:


c>Presuming one has mid-rule computations (and those are not hard to
c>implement in an LR parser generator), one can also determine context
c>before the dependent tokens have been constructed.




And he replied back:
g>I beg to differ. The tokens may not yet have been *consumed* by
g>the parser, but they most definitely have already been constructed
g>else the rule reduction would not have been attempted.
g>
g>And LR mid-rule actions require complete syntactic predication of
g>the rule head - if not the entire rule - because the user actions
g>can't be undone and should not be executed unless the parse is
g>committing to the rule. Operationally it makes the entire rule
g>head a separately matched sub-rule, which may be logically
g>incorrect.




If I understand you (the word "head" in your post implies I may not),
then you misunderstand the LR method. You don't have to wait for the
reduction of the entire rule to apply a mid-rule action. In fact, for
the "correct" semantics, you don't want to wait until the end of the
rule. A mid-rule action in an LR parser should occur at the point
where the lexer has only constructed the tokens preceding the mid-rule
action point. This is the same point the mid-rule action occurs in an
LL parser. If it occurs later, then it is not a mid-rule action; it
is an end-of-rule action written mid-rule.




If by rule head, you mean the part of the rule preceding the point
where the mid-rule action occurs, then yes the tokens preceding the
mid-rule action point have to be constructed before the mid-rule
action occurs, but none of the tokens after the action point.
However, that is exactly the point where you have specified that
action to occur. If it is not the correct point, then move the action
to the correct point.




Perhaps you are trying to suggest that moving the action earlier in
the rule can be problematic (i.e. it can introduce conflicts). That
is generally only true if the grammar is not LL(1). If the grammar is
LL(1), then an LR parser generator can have mid-rule actions inserted
anywhere in the grammar, except before the first item in a rule (and
it can even have them there if the generator is LR and not SLR or
LALR). Before the first position of the rule is a problem for SLR and
LALR generators because they don't handle the context dependence of
nullable rules correctly.




However, since the initial point you made was about advantages of
using LL over LR to do context sensitive lexing, I presume you were
talking about using the parser context to determine how tokens were to
be lexed. My point was that anything one can do with an LL parser
(which requires an LL grammar), one can do with feeding the same LL
grammar to an LR parser generator (with some slight caveats for
trailing context sensitive nullable rules and SLR and LALR
generators).




Moreover, I brought up mid-rule actions because, I presumed you were
suggesting using actions to change how the tokens were lexed and to
implement the context sensitivity. If you are not using actions to
change how the tokens are lexed, please explain further what feature
of LL parsing you are using to do so and why you don't think feeding
that LL grammar to an LR parser generator would achieve the same
result.




Thank you,
-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.