Semantic actions in LR parser (Chris Clark USSG)
Tue, 6 Apr 1993 15:26:32 GMT

          From comp.compilers

Related articles
Semantic actions in LR parser (1993-04-02)
Re: Semantic actions in LR parser (1993-04-02)
Re: Semantic actions in LR parser (1993-04-03)
Re: Semantic actions in LR parser (1993-04-05)
Semantic actions in LR parser (1993-04-06)
Re: Semantic actions in LR parser (1993-04-07)
Semantic actions in LR parser (1993-04-14)
Semantic actions in LR parser (1993-04-15)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Chris Clark USSG)
Keywords: LR(1), parse
Organization: Compilers Central
References: 93-04-008 93-04-010
Date: Tue, 6 Apr 1993 15:26:32 GMT

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

Post a followup to this message

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