Re: Semantic actions in LR parser

karsten@tfl.dk (Karsten Nyblad)
Sat, 3 Apr 1993 09:37:19 GMT

          From comp.compilers

Related articles
Semantic actions in LR parser cosc19py@jane.uh.edu (1993-04-02)
Re: Semantic actions in LR parser roy@prism.gatech.edu (1993-04-02)
Re: Semantic actions in LR parser karsten@tfl.dk (1993-04-03)
Re: Semantic actions in LR parser mauney@csljon.csl.ncsu.edu (1993-04-05)
Semantic actions in LR parser clark@zk3.dec.com (1993-04-06)
Re: Semantic actions in LR parser wand@ccs.northeastern.edu (1993-04-07)
Semantic actions in LR parser clark@zk3.dec.com (1993-04-14)
Semantic actions in LR parser xorian@solomon.technet.sg (1993-04-15)
| List of all articles for this month |

Newsgroups: comp.compilers
From: karsten@tfl.dk (Karsten Nyblad)
Keywords: LR(1), parse
Organization: TFL
References: 93-04-008 93-04-010
Date: Sat, 3 Apr 1993 09:37:19 GMT

roy@prism.gatech.edu (Roy Mongiovi) writes:


>LR parsers can only perform semantic actions when the recognize a handle
>(right-hand side). You can either split up the right-hand sides into
>pieces so that the pieces end where you need the semantic actions, or you
>can stick in epsilon productions whose only purpose is to cause semantic
>actions.


Hi,


That is wrong. When there is only one item in the kernel of a state, the
production of that item will always be reduced at a later point. So, you
can allow for actions to be executed when you push a terminal or
nonterminal and that brings you to a state that has only one item in
kernel.


Even that can be generalized. All items of the kernel of a state has the
same symbol before the . of the item, where the . denotes the point until
which the parser has accepted the symbols of the production of the item.
If the same action has been specified on all productions of the items of
the kernel of a state on pushing the symbol before the ., then that action
can executed by the parser.


That can also the generalized. If the first terminals of the symbols
following . differs, then that can be used to select the actions to be
taken.


Example:


          Assume the productions A -> A B {action 1} C
                                                        B -> B { action 1 } D
                                                        C -> B { action 2 } E
          are part of the productions of a grammar.
          The actions are to be executed when B is pushed.


          In a state with the kernel


                              A -> A B . C
                              B -> B . D


          the action 1 can be taken.
          In a state with the kernel


                              B -> B . D
                              C -> B . E


          both action 1 and 2 could be taken and thus the
          grammar is ambigouos. That ambiguity can be solved if
          D and E do not start with the same terminals, e.g.
          are different terminals.


Karsten Nyblad
TFL, A Danish Telecommunication Research Lab.
karsten@tfl.dk
--


Post a followup to this message

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