Semantic actions in LR parser

I was asked:
> Ahh, this sounds like you've rediscovered a result similar to the one in
> Brown, C. & Purdom, P. "Semantic Routines and LR(k) Parsers,"
> Acta Informatica 14 (1980), 299--315.


And was courteously sent a copy of the paper by the authors.


It is a very interesting paper, and it details three types of places where
(shift) action code may or may not be placed--you can always place action
code, you can never place action code, and you can sometimes place action
code.


The set of places you can always place action code matches the places you
can put action code in your grammar with yacc and not produce a conflict.


The set of places you can sometimes place action code match the places
where in Yacc++(R) the action code must match on several possibilities.
(This is the same in Karsten Nyblad's parser generator.)


The set of places you can never place action code will always cause a
conflict. However, as Karsten describes, the parser generator can attempt
to postpone the action by one step of look-ahead without too much trouble.
(Yacc++ does this too, and there is a caution in the manual about
interactions with the lexer, since if the action code is designed to cause
the lexer to return a different token and it is postponed, the directive
to the lexer won't get to the lexer until after the lexer has returned the
token!)


The paper provides some interesting algorithms for calculating where
action code can be placed. Of course, in a pragmatic sense, it is just
easier to run it through the parser generator of your choice and find out
whether it gets conflicts. However, if you think the place where your
action code is placed should be legal, the algorithms in the paper could
either tell you that--you are right, but you need a better parser
generator; you need to put some other matching action code in; or you are
wrong and you need to rethink your semantics.


The most interesting aspect of the algorithms is that they will tell you
if adding matching action code into another production will have a
cascading effect producing new conflicts to be resolved with more matching
action code and whether the cascade will converge and eventually result in
a legal grammar or not. Our parser generator doesn't tell you that. For
most common cases, it isn't an issue, because the places to add action
code converges in one step, but for unusual grammars it would help.


I hope this was interesting.


Chris Clark


I am biased in favor of parser generators and work for,


Compiler Resources, Inc.
3 Proctor St.
Hopkinton, MA 01748
(508) 435-5016 fax: (508) 435-4847


For a technical literature packet (including a price list) send email
to: bz%compres@primerd.prime.com
--

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