LR-Parser

In a compiler LR parser is a bottom-up parser for LR grammars. In this context-free grammar, the input is processed from left to right, right to calculate the reduction in the start symbol.

General

An LR parser is called LR ( k) parser, if he can look ahead k tokens during parsing k is a natural number. k is referred to as lookahead.

LR ( k) is an abbreviation for parsing from left to right with right reductions, k lookahead symbols.

LR- parser to write by hand holds a great risk of error, so here most parser generators are used.

Construction and operation of an LR parser

An LR parser includes a basement storage, an action table and a GoTo table. The top element in the basement is always the current state of the parser. When the program is started, only the initial state is in the basement. In the action table is indicated, what to do at each combination of state and input character. Possible actions are:

  • Shift (z): Move the pointer in the input stream one step further and put the current state into the basement. Then switch to the state for
  • Reduce ( s): Apply the rule to n. That is, take as many items from the basement, as the rule has symbols on the right side. Look then to the Goto table, which is the next state, and put it in the basement.
  • Accept: Accept the entry. That is, the input is valid, and terminates the parser.
  • Error: Is a state input constellation in the table are not described, then the input is rejected and terminated the parser.

Example of a parser

We consider the following grammar in BNF with start symbol E:

E :: = E "*" B | E " " B | B. B :: = "0" | "1". This grammar can be transformed into the following single reduction rules:

If you mark the end of input with a dollar sign ( $ rule e ← S; S is a new start symbol ), so see the action and GoTo table for an LR ( 0) parser to this:

How to create these tables from the grammar is described in the section Creating the action and goto table.

Example of a parse operation

The input is the string " 1 1 " is given.

1 The initial state here is 0, so the parser will only start with a 0 in the basement, and the read pointer is on the first character of the input.

2 We now look into the action table, what to do at state 0 and input "1": s2, ie we put the condition 2 in the basement and read the next character.

3 With the input " " should we apply rule 5 in state 2. The Rule 5 has an item on the right side. Therefore, we take an element out of the basement and see in the Goto- table the next state after. In state 0 ( the two we have just taken away ) is changed by application of a rule, on the left side B is in the state 4.

4 Now comes again a reduction. This time with Rule 3 We go to state 3

5 Now comes a shift. We change to the state 6

6 Shift, new state: 2

7 reduction with rule 5, new condition 8

8 reduction with rule 2 We therefore take three items from the basement. Then 0 is the top, and we switch to state 3, since the rule 2 has an E on the left.

9 Accept. The input part of the grammar, and we are done.

Creating the action and goto table

To obtain the box, a deterministic finite state machine is generated (DEA) and written the states and transitions in the table from the grammar. Depending on which type of LR parser is designed, there are slight changes in the design process. Such a procedure is described for example for SLR parser.

531197
de