Semantic actions in LR parser

It was asked.


> I am just wondering if we have to put all semantic actions on the tail
> parts of some productions for LR grammar instead of any positions in LL
> grammar?


Most LR parsers (i.e. yacc) introduce pseudo productions only because it
is convenient to do so. It simplifies the LR engine, by allowing it to
fold the action selection into the reduction code. It's actually a fairly
clever hack to recognize that you can simulate shift actions by
introducing pseude productions. A similar hack gives you a "poor person's
ELR parser" allowing regular expressions on the RHS. However, in both
cases, I feel there is a better way, which we used in our product,
Yacc++(R) and the Language Objects Library.


In, Yacc++, we model our LR engine as an abstract machine, and the
generator outputs "assembly language" for it. Doing so, makes it
straight-forward to put actions with shifts as well as with reduces.


Essentially, as you are building your dotted items for a state, some of
them may include actions. You just encode those actions as part of your
shift transitions. If you model it right, it is fairly simple. When you
build the dotted productions for a state, you are essentially simulating
running a bunch of LL parsers in parallel. Thus, you can do anything in
an LR parser, that you can in an LL parser, except it's difficult to
program in recursive descent--because your programming language probably
does not allow running a bunch of routines in parallel and selecting the
one which succeeds. (I guess recursive descent in prolog would work fine
aside from the backtracking overhead.)


One curious feature which falls out, is that if you can detect two actions
are the same you can execute the action even if the eventual reduces are
parts of two distinct productions. That allows you to defer (and
eliminate) some conflicts. (In our model, two actions are the same if
they are character for character the same string.) Eliminating the pseudo
productions, also means smaller state tables.


I hope this helps.


Disclaimer, signature, et. al.


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.