EECS665 – Compiler Construction – Drew Davidson $\newcommand{\bigsqcap}{\mathop ⨅}$

    Shift/Reduce Parsing


    Contents


    LR Parsing Overview

    There are several different kinds of bottom-up parsing. We will discuss an approach called LR parsing, which includes SLR, LALR, and LR parsers. LR means that the input is scanned left-to-right, and that a rightmost derivation, in reverse, is constructed. SLR means "simple" LR, and LALR means "look-ahead" LR.

    Every SLR(1) grammar is also LALR(1), and every LALR(1) grammar is also LR(1), so SLR is the most limited of the three, and LR is the most general. In practice, it is pretty easy to write an LALR(1) grammar for most programming languages (i.e., the "power" of an LR parser isn't usually needed). A disadvantage of LR parsers is that their tables can be very large. Therefore, parser generators like Yacc and Java Cup produce LALR(1) parsers.

    Let's start by considering the advantages and disadvantages of the LR parsing family:

    Advantages

    • Almost all programming languages have LR grammars.
    • LR parsers take time and space linear in the size of the input (with a constant factor determined by the grammar).
    • LR is strictly more powerful than LL (for example, every LL(1) grammar is also both LALR(1) and LR(1), but not vice versa).
    • LR grammars are more "natural" than LL grammars (e.g., the grammars for expression languages get mangled when we remove the left recursion to make them LL(1), but that isn't necessary for an LALR(1) or an LR(1) grammar).
    Disadvantages
    • Although an LR grammar is usually easier to understand than the corresponding LL grammar, the parser itself is harder to understand and to write (thus, LR parsers are built using parser generators, rather than being written by hand).
    • When we use a parser generator, if the grammar that we provide is not LALR(1), it can be difficult to figure out how to fix that.
    • Error repair may be more difficult using LR parsing than using LL.
    • Table sizes may be larger (about a factor of 2) than those used for LL parsing.

    Recall that top-down parsers use a stack. The contents of the stack represent a prediction of what the rest of the input should look like. The symbols on the stack, from top to bottom, should "match" the remaining input, from first to last token. For example, earlier, we looked at the example grammar

    Grammar:

    $S$ $\longrightarrow$ $\varepsilon$ | ( $S$ ) | [ $S$ ]

    and parsed the input string ([]). At one point during the parse, after the first parenthesis has been consumed, the stack contains

        [ S ] ) EOF
    (with the top-of-stack at the left). This is a prediction that the remaining input will start with a '[', followed by zero or more tokens matching an S, followed by the tokens ']' and ')', in that order, followed by end-of-file.

    Bottom-up parsers also use a stack, but in this case, the stack represents a summary of the input already seen, rather than a prediction about input yet to be seen. For now, we will pretend that the stack symbols are terminals and nonterminals (as they are for predictive parsers). This isn't quite true, but it makes our introduction to bottom-up parsing easier to understand.

    A bottom-up parser is also called a "shift-reduce" parser because it performs two kind of operations, shift operations and reduce operations. A shift operation simply shifts the next input token from the input to the top of the stack. A reduce operation is only possible when the top N symbols on the stack match the right-hand side of a production in the grammar. A reduce operation pops those symbols off the stack and pushes the non-terminal on the left-hand side of the production.

    One way to think about LR parsing is that the parse tree for a given input is built, starting at the leaves and working up towards the root. More precisely, a reverse rightmost derivation is constructed.

    Recall that a derivation (using a given grammar) is performed as follows:

    1. start with the start symbol (i.e., the current string is the start symbol)
    2. repeat:
      • choose a nonterminal X in the current string
      • choose a grammar rule X $\longrightarrow$ $\alpha$
      • replace X in the current string with $\alpha$
      until there are no more nonterminals in the current string

    A rightmost derivation is one in which the rightmost nonterminal is always the one chosen.

    Rightmost Derivation Example

    CFG

    $E$ $\longrightarrow$ $E$ + $T$
    | $T$
    $T$ $\longrightarrow$ $T$ * $F$
    | $F$
    $F$ $\longrightarrow$ id
    | ( $E$ )

    Rightmost derivation

      $E$
      1. $\Longrightarrow$ $E$ + $T$
      2. $\Longrightarrow$ $E$ + $T$ * $F$
      3. $\Longrightarrow$ $E$ + $T$ * id
      4. $\Longrightarrow$ $E$ + $F$ * id
      5. $\Longrightarrow$ $E$ + id * id
      6. $\Longrightarrow$ $T$ + id * id
      7. $\Longrightarrow$ $F$ + id * id
      8. $\Longrightarrow$ id + id * id

    In this example, the nonterminal that is chosen at each step is in red, and each derivation step is numbered. The corresponding bottom-up parse is shown below by showing the parse tree with its edges numbered to show the order in which the tree was built (e.g., the first step was to add the nonterminal F as the parent of the leftmost parse-tree leaf "id", and the last step was to combine the three subtrees representing "id", "+", and "id * id" as the children of a new root node E).

    image/svg+xml E id F T E id id F T F T + * 2 1 3 4 5 6 7 8

    Note that both the rightmost derivation and the bottom-up parse have 8 steps. Step 1 of the derivation corresponds to step 8 of the parse; step 2 of the derivation corresponds to step 7 of the parse; etc. Each step of building the parse tree (adding a new nonterminal as the parent of some existing subtrees) is called a reduction (that's where the "reduce" part of "shift-reduce" parsing comes from).

    Basic LR Parsing AlgorithmL

    All LR parsers use the same basic algorithm:

      Based on:
      • the top-of-stack symbol and
      • the current input symbol (token) and
      • the entry in one of the parse tables (indexed by the top-of-stack and current-input symbols)
      the parser performs one of the following actions:
      1. shift: push the current input symbol onto the stack, and go on to the next input symbol (i.e., call the scanner again)
      2. reduce: a grammar rule's right-hand side is on the top of the stack! pop it off and push the grammar rule's left-hand-side nonterminal
      3. accept: accept the input (parsing has finished successfully)
      4. reject: the input is not syntactically correct

    The difference between SLR, LALR, and LR parsers is in the tables that they use. Those tables use different techniques to determine when to do a reduce step, and, if there is more than one grammar rule with the same right-hand side, which left-hand-side nonterminal to push.

    Example

    Here are the steps the parser would perform using the grammar of arithmetic expressions with + and * given above, if the input is

    id + id * id
      Stack Input Action
      id + id * id shift (id)
      id + id * id reduce by $F$ $\longrightarrow$ id
      $F$ + id * id reduce by $T$ $\longrightarrow$ $F$
      $T$ + id * id reduce by $E$ $\longrightarrow$ $T$
      $E$ + id * id shift(+)
      $E$ + id * id shift(id)
      $E$ + id * id reduce by $F$ $\longrightarrow$ id
      $E$ + $F$ * id reduce by $T$ $\longrightarrow$ $F$
      $E$ + $T$ * id shift(*)
      $E$ + $T$ * id shift(id)
      $E$ + $T$ * id reduce by $F$ $\longrightarrow$ id
      $E$ + $T$ * $F$ reduce by $T$ $\longrightarrow$ $T$ * $F$
      $E$ + $T$ reduce by $E$ $\longrightarrow$ $E$ + $T$
      $E$ accept

      (NOTE: the top of stack is to the right; the reverse rightmost derivation is formed by concatenating the stack with the remaining input at each reduction step)

    Note that in step 8 the top of the stack contained E + T, which is the right-hand side of the first grammar rule. However, the parser does not do a reduce step at that point; instead it does a shift, which is the right thing to do since (as you can see if you look back at the parse tree given above), that particular "E + T" is not grouped together (because the grammar reflects the fact that multiplication has higher precedence than addition).

    Parse Tables

    As mentioned above, the symbols pushed onto the parser's stack are not actually terminals and nonterminals. Instead, they are states, that correspond to a finite-state machine that represents the parsing process (more on this soon).

    All LR Parsers use two tables: the action table and the goto table. The action table is indexed by the top-of-stack symbol and the current token, and it tells which of the four actions to perform: shift, reduce, accept, or reject. The goto table is used during a reduce action as explained below.

    Above we said that a shift action means to push the current token onto the stack. In fact, we actually push a state symbol onto the stack. Each "shift" action in the action table includes the state to be pushed.

    Above, we also said that when we reduce using the grammar rule A → alpha, we pop alpha off of the stack and then push A. In fact, if alpha contains N symbols, we pop N states off of the stack. We then use the goto table to know what to push: the goto table is indexed by state symbol t and nonterminal A, where t is the state symbol that is on top of the stack after popping N times.

    Here's pseudo code for the parser's main loop:

      push initial state s0
      a = scan()
      do forever
          t = top-of-stack (state) symbol
          switch action[t, a] {
             case shift s:
                 push(s)
                 a = scan()
             case reduce by A → alpha:
                 for i = 1 to length(alpha) do pop() end
      	   t = top-of-stack symbol
                 push(goto[t, A])
             case accept:
                 return( SUCCESS )
             case error:
                 call the error handler
                 return( FAILURE )
          }
      end do
      

    Remember, all LR parsers use this same basic algorithm. As mentioned above, for all LR parsers, the states that are pushed onto the stack represent the states in an underlying finite-state machine. Each state represents "where we might be" in a parse; each "place we might be" is represented (within the state) by an item. What's different for the different LR parsers is:

    • the definition of an item
    • the number of states in the underlying finite-state machine
    • the amount of information in a state