Legal derivation

A legal derivation (also legal canonical derivation , English rightmost derivation ) is in theoretical computer science a sequence of derivation steps in which the rightmost so-called non - terminal symbol is always replaced by the application of a production rule. It is important for the compiler construction because with it the syntax tree for a certain class of programming languages ​​( LR (k) languages ) can be calculated easily.

In order to generate formal languages such as programming languages, formal grammars are set up with which words can be derived and generated according to their production rules . The legal derivation is a series of steps which, starting from a start symbol, generates a word in formal language. In formal grammars, the so-called non-terminal symbols of derived words are used to describe the internal structure of the language. These non-terminals could (in context-free grammars ) at every point of a word replaced are. In the case of the right derivative, you commit yourself to always replacing the rightmost non-terminal. Whenever the one furthest to the left is replaced, it is called a left derivative .

example

Let it be a grammar with the non-terminal symbols , the terminal symbols , the start symbol and the following production rules : ${\displaystyle G=(N,T,P,S)}$ ${\displaystyle N=\{E\}}$ ${\displaystyle T=\{a,b,c,+,*,(,)\}}$ ${\displaystyle S=E}$ ${\displaystyle P}$

${\displaystyle {\begin{aligned}\\(1)E&\rightarrow E+E\\(2)E&\rightarrow E*E\\(3)E&\rightarrow (E)\\(4)E&\rightarrow \mathrm {a} \\(5)E&\rightarrow \mathrm {b} \\(6)E&\rightarrow \mathrm {c} \\\end{aligned}}}$

There are two legal derivatives for the word , which shows that the grammar is ambiguous. Therefore it should not be used to describe formal language . ${\displaystyle a+b*c}$

Legal derivative 1:

${\displaystyle {\begin{aligned}\\E&=(1)\rightarrow E+E\\&=(2)\rightarrow E+E*E\\&=(6)\rightarrow E+E*c\\&=(5)\rightarrow E+b*c\\&=(4)\rightarrow a+b*c\\\end{aligned}}}$

Legal derivative 2:

${\displaystyle {\begin{aligned}\\E&=(2)\rightarrow E*E\\&=(6)\rightarrow E*c\\&=(1)\rightarrow E+E*c\\&=(5)\rightarrow E+b*c\\&=(4)\rightarrow a+b*c\\\end{aligned}}}$

If there is no grammar for a language that has only one legal derivative for each word in the language described, it is called an inherently ambiguous language . With a clear grammar, the syntax tree that matches the derivation can be generated with an LR parser .

See also

• Legal reduction
• Inherently ambiguous language
• Syntax tree
• LR parser

swell

• Alfred V. Aho , Ravi Sethi, Jeffrey D. Ullman : Compilers. Principles, Techniques and Tools . Addison-Wesley, Reading MA et al. a. 1986, ISBN 0-201-10088-6 , pp. 196-197.
• Seppo Sippu, Eljas Soisalon-Soininen: Parsing Theory . 1: Languages ​​and Parsing . Springer Verlag, Berlin a. a. 1988, ISBN 3-540-13720-3 , ( EATCS monographs on theoretical computer science 15).
• Peter Rechenberg , Gustav Pomberger (Hrsg.): Informatik Handbuch 4th updated and expanded edition. Springer Hanser, Munich a. a. 2006, ISBN 3-446-40185-7 , p. 92.

Web links

• Informatik Handbuch - 3.1.3 Canonical derivatives and ambiguity