Semantic Actions and LR(k)

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 mra@opal.idbsu.edu.
--

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