More Powerful LR Parsers

cuishengli

More Powerful LR Parsers

<div class="postbody"><div id="cnblogs_post_body">4.7 More Powerful LR Parsers

  In this section, we shall extend the previous LR parsing techniques to use one symbol of lookahead on the input. There are two different methods:
  

   

• The "canonical-LR" or just "LR" method, which makes full use of the lookahead symbol(s). This method uses a large set of items, called the LR(1) items.   
  
• The "lookahead-LR" or "LALR" method, which is based on the LR(0) sets of items, and has many fewer states than typical parsers based on the LR(1) items. By carefully introducing lookaheads into the LR(0) items, we can handle many more grammars with the LALR method than with the SLR method, and build parsing tables that are no bigger than the SLR tables. LALR is the method of choice in most situations.
  

  After introducing both these methods, we conclude with a discussion of how to compact LR parsing tables for environments with limited memory.
  4.7.1 Canonical LR(1) Items

  We shall now present the most general technique for constructing an LR parsing table from a grammar. Recall that in the SLR method, state i calls for reduction by A -> α if the set of items Ii contains item [A -> α@] and a is in FOLLOW(A). In some situations, however, when state i appears on top of the stack, the viable prefix βα on the stack is such that βA cannot be followed by a in any right-sentential form. Thus, the reduction by A -> α should be invalid on input a.
  <div class="example">   Example 4.51: Let us reconsider Example 4.48, where in state 2 we had item R -> L@, which could correspond to A -> α above, and a could be the = sign, which is in FOLLOW(R). Thus, the SLR parser calls for reduction by R -> L in state 2 with = as the next input (the shift action is also called for, because of item S -> L@=R in state 2). However, there is no right-sentential form of the grammar in Example 4.48 that begins R = ... . Thus state 2, which is the state corresponding to viable prefix L only, should not really call for reduction of that L to R.