LR parser
In compiler construction , an LR parser is a bottom-up parser for LR grammars . In these context-free grammars , the input is from l processed inks to the right to the R genuine reduction to calculate the start symbol.
General
An LR parser is called an LR (k) parser if it can anticipate k tokens for a natural number k during parsing . k is referred to as lookahead .
LR ( k ) is an abbreviation for parsing l eft to right with R genuine reductions, k symbols lookahead.
Writing LR parsers by hand involves a great risk of errors, which is why parser generators are mostly used here.
Structure and mode of operation of an LR parser
An LR parser contains a stack , an action table and a GoTo table. The top element in the basement always indicates the current status of the parser. When the program starts, only the start state is in the basement. The action table records what needs to be done for each combination of status and input characters. Possible actions are:
- Shift (z) : Move the pointer in the input stream one step further and put the current state in the basement. Then change to the state z .
- Reduce (n) : Apply rule n . I.e. take as many items from the basement as the rule has icons on the right. Then look in the goto table to see what the next state is and put it in the basement.
- Accept : Accept the entry. I.e. the input is valid and the parser terminates.
- Error : If a status-input constellation is not described in the table, the input is rejected and the parser terminated.
Example of a parser
We consider the following grammar in BNF with the start symbol E:
E ::= E "*" B | E "+" B | B . B ::= "0" | "1" .
This grammar can be converted into the following individual reduction rules:
- E * B ← E
- E + B ← E
- B ← E
- 0 ← B
- 1 ← B
If you mark the end of the input with a $ sign (rule E $ ← S; S is the new start symbol), the action and GoTo table for an LR (0) parser look like this:
action | GoTo | ||||||
---|---|---|---|---|---|---|---|
Status | * | + | 0 | 1 | $ | E. | B. |
0 | s1 | s2 | 3 | 4th | |||
1 | r4 | r4 | r4 | r4 | r4 | ||
2 | r5 | r5 | r5 | r5 | r5 | ||
3 | s5 | s6 | acc | ||||
4th | r3 | r3 | r3 | r3 | r3 | ||
5 | s1 | s2 | 7th | ||||
6th | s1 | s2 | 8th | ||||
7th | r1 | r1 | r1 | r1 | r1 | ||
8th | r2 | r2 | r2 | r2 | r2 |
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 character string "1 + 1" is given as input.
1. The start state is 0 here, so the parser only starts with a 0 in the basement and the read pointer is on the first character of the input.
- Output: $ 1 + 1
Basement, cellar: | 0 | ||||
Input: | 1 | + | 1 | $ |
2. We now look in the action table to see what to do with state 0 and input "1": s2, i. H. we put state 2 in the basement and read the next character.
- Action: Put 2 in the basement
- Output: $ 1 + 1
Basement, cellar: | 0 | 2 | |||
Input: | 1 | + | 1 | $ |
3. By entering "+" we should apply rule 5 in state 2. Rule 5 has an element on the right. Therefore we take an element from the basement and look up the next state in the Goto table. In state 0 (we have just removed the 2) a change is made to state 4 after applying a rule with a B on the left.
- Action: Reduce
- Output:
Basement, cellar: | 0 | 4th | |||
Input: | B. | + | 1 | $ |
4. Now comes another reduction. This time with rule 3. We change to state 3.
- Action: Reduce
- Output:
Basement, cellar: | 0 | 3 | |||
Input: | E. | + | 1 | $ |
5. Now comes a shift. We change to state 6.
- Action: put + in the basement.
- Output:
Basement, cellar: | 0 | 3 | 6th | ||
Input: | E. | + | 1 | $ |
6. Shift, new state: 2
- Action: Put 1 in the basement.
- Output:
Basement, cellar: | 0 | 3 | 6th | 2 | |
Input: | E. | + | 1 | $ |
7. Reduction with rule 5, new status is 8
- Action: Reduce .
- Output:
Basement, cellar: | 0 | 3 | 6th | 8th | |
Input: | E. | + | B. | $ |
8. Reduction with rule 2. We therefore take three elements from the basement. Then the 0 is right at the top, and we switch to state 3, since rule 2 has an E on the left.
- Action: Reduce .
- Output:
Basement, cellar: | 0 | 3 | |
Input: | E. | $ |
9. Accept. The input is part of the grammar and we're done.
Creating the action and goto table
In order to obtain the table, a deterministic finite machine (DEA) is created from the grammar and its states and transitions are written into the table. Depending on which type of LR parser is constructed, there are slight changes to the construction process. Such a sequence is described, for example, for SLR parsers .
See also
Web links
- LR (k) analysis for pragmatists , detailed description of the LR analysis and the corresponding subforms (LR (0), SLR (1), LALR (1), LR (1)).