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:

1. E * B ← E
2. E + B ← E
3. B ← E
4. 0 ← B
5. 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 ${\displaystyle 1\leftarrow B}$

Output: ${\displaystyle 1+1\$\Leftarrow _{r}B+1\$}$

Basement, cellar:	0	4th
Input:		B.	+	1	$

4. Now comes another reduction. This time with rule 3. We change to state 3.

Action: Reduce ${\displaystyle B\leftarrow E}$

Output: ${\displaystyle 1+1\$\Leftarrow _{r}B+1\$\Leftarrow _{r}E+1\$}$

Basement, cellar:	0	3
Input:		E.	+	1	$

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

Action: put + in the basement.

Output: ${\displaystyle 1+1\$\Leftarrow _{r}B+1\$\Leftarrow _{r}E+1\$}$

Basement, cellar:	0	3	6th
Input:		E.	+	1	$

6. Shift, new state: 2

Action: Put 1 in the basement.

Output: ${\displaystyle 1+1\$\Leftarrow _{r}B+1\$\Leftarrow _{r}E+1\$}$

Basement, cellar:	0	3	6th	2
Input:		E.	+	1	$

7. Reduction with rule 5, new status is 8

Action: Reduce . ${\displaystyle 1\leftarrow B}$

Output: ${\displaystyle 1+1\$\Leftarrow _{r}B+1\$\Leftarrow _{r}E+1\$\Leftarrow _{r}E+B\$}$

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 . ${\displaystyle E+B\leftarrow E}$

Output: ${\displaystyle 1+1\$\Leftarrow _{r}B+1\$\Leftarrow _{r}E+1\$\Leftarrow _{r}E+B\$\Leftarrow _{r}E\$}$

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

• LL parser
• LALR parser

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)).