LR ( k ) grammar

In theoretical computer science and compiler construction , LR ( k ) grammar refers to a special context-free grammar that forms the basis of an LR parser .

A context-free grammar is called a grammar if each reduction step is clearly defined by symbols of the input (so-called lookahead). This means that the question of which non-terminal symbol should be reduced to which rule with which rule can be clearly determined with the help of the next symbols in the input. ${\displaystyle \mathrm {LR} (k)}$ ${\displaystyle k}$ ${\displaystyle k}$

A difference in the language class that can be described with grammars can only be seen for the two cases and . The expressiveness of context-free grammars is not achieved by. This means that there are context-free grammars for everyone , for which there are no equivalent grammars , for example an inherently ambiguous language . The language class defined by grammars is also called deterministically context-free languages . ${\displaystyle \mathrm {LR} (k)}$ ${\displaystyle k=0}$ ${\displaystyle k>0}$ ${\displaystyle \mathrm {LR} (1)}$ ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle \mathrm {LR} (k)}$ ${\displaystyle \mathrm {LR} (k)}$

${\displaystyle {\mathcal {L}}(\mathrm {LR} (0))\subsetneq {\mathcal {L}}(\mathrm {LR} (1))={\mathcal {L}}(\mathrm {LR} (2))=\cdots ={\mathcal {L}}(\mathrm {DPDA} )\subsetneq {\mathcal {L}}(\mathrm {PDA} )}$(DPDA = Deterministic Push-Down Automaton, PDA = Push-Down Automaton )

Formal definition of LR (k) grammar

A context-free grammar is grammar if and only if for all legal reductions of the form ${\displaystyle G=\left(N,\Sigma ,P,S\right)}$ ${\displaystyle \mathrm {LR} \left(k\right)}$

${\displaystyle \alpha \beta w}$	${\displaystyle \Leftarrow _{r}\alpha Aw}$	${\displaystyle \Leftarrow _{r}^{*}}$
			${\displaystyle S}$
${\displaystyle \gamma \delta x}$	${\displaystyle \Leftarrow _{r}\gamma Bx}$	${\displaystyle \Leftarrow _{r}^{*}}$

with and applies: ${\displaystyle w,x\in \Sigma ^{*};\alpha ,\beta ,\gamma ,\delta \in (N\cup \Sigma )^{*};A,B\in N}$ ${\displaystyle first_{|\alpha \beta |+k}(\alpha \beta w)=first_{|\alpha \beta |+k}(\gamma \delta x)}$

${\displaystyle \alpha =\gamma }$, as well ${\displaystyle A=B}$ ${\displaystyle \beta =\delta }$

See also

• LL (k) grammar
• LL parser

Web links

• LR (k) analysis for pragmatists , detailed description of the LR analysis and the subforms LR (0), SLR (1), LALR (1), LR (1).