|Semantic actions in LR parser firstname.lastname@example.org (1993-04-02)|
|Re: Semantic actions in LR parser email@example.com (1993-04-02)|
|Semantic Actions and LR(k) firstname.lastname@example.org (Paul Purdom) (1993-04-05)|
|From:||"Paul Purdom" <email@example.com>|
|Organization:||Computer Science, Indiana University|
|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 firstname.lastname@example.org.
Return to the
Search the comp.compilers archives again.