Semantic Actions and LR(k)

"Paul Purdom" <>
Mon, 5 Apr 1993 17:45:48 GMT

          From comp.compilers

Related articles
Semantic actions in LR parser (1993-04-02)
Re: Semantic actions in LR parser (1993-04-02)
Semantic Actions and LR(k) (Paul Purdom) (1993-04-05)
| List of all articles for this month |

Newsgroups: comp.compilers
From: "Paul Purdom" <>
Keywords: LR(1), parse
Organization: Computer Science, Indiana University
References: 93-04-008 93-04-010
Date: Mon, 5 Apr 1993 17:45:48 GMT

I hear that there has been some discussion of LR(k) parsing and semantic
action routines concerning the question of where one can place calls to
the routines without causing parsing difficulties.

People interested in this question may wish to see the article Semantic
Routines and LR(k) Parsers by Cynthia Brown and myself, Acta Informatica
14 (1980) p299-315.

One might wish to call a routine before the first symbol of the right side
of a production (thereby simulating LL(k) with an LR(k) parser), or after
the i-th symbol for any i up to an including the length of the production.
The above paper shows that each position is either:

1. Forbidden, the grammar is no longer parseable (with an LR(k) parser) if a
      routine is called there. The only forbidden positions are the positions
      zero of left recursive productions.

2. Contingent, the grammar is parseable provided the same routine is called
      at certain other positions in the grammar.

3. Free, the grammar is parseable whether or not the same routine is called
      at other positions.

The paper has an algorithm for classifying positions.

A more refined analysis has been done by Michael R. Anderson. The last I
knew (1992), his email address was

Post a followup to this message

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