Изменения

<tex>\Gamma =\langle \Sigma, N, S \in N, P \subset N^{+}\times (\Sigma\cup N)^{*}\rangle</tex>, где <tex>\Sigma</tex> — [[Основные_определения: алфавит, слово, язык, конкатенация, свободный моноид слов|алфавит]], элементы которого называют '''терминалами''', <tex>N</tex> — множество, элементы которого называют '''нетерминалами''', <tex>S</tex> — начальный символ грамматики, <tex>P</tex> — набор правил вывода <tex>\alpha\rightarrow \beta</tex>.

# <tex>\alpha=\alpha_1\alpha_2\alpha_3</tex>;# <tex>\beta=\beta_1\beta_2\beta_3</tex>;# <tex>\alpha_1=\beta1</tex>, <tex>\alpha_3=\beta3</tex>, <tex>\alpha_2\rightarrow\beta2 \in P</tex>.

'''<tex>\beta</tex> выводится из <tex>\alpha</tex> за ноль или более шагов''' (<tex>\alpha \Rightarrow^* \beta</tex>):<br/><tex>\exists \gamma_1, \gamma_2,...,\gamma_n : \alpha \Rightarrow \gamma_1 \Rightarrow \gamma_2 \Rightarrow ... \Rightarrow \gamma_n \Rightarrow \beta</tex>.

<tex>\Sigma = \{(, )\}</tex>;

S \rightarrow (S);\\S \rightarrow SS;\\S \rightarrow \epsilon.

<tex>S\rightarrow(S)\rightarrow(SS)\rightarrow((S)S)\rightarrow((S)(S))\rightarrow(()(S))\rightarrow(()())</tex>.

<tex>\rightarrow((SS)((S)))\rightarrow (((S)S)((S))) \rightarrow ((()S)((S)))\rightarrow</tex><br/><tex>\rightarrow((()(S))((S)))\rightarrow ((()())((S)))\rightarrow ((()())(()))</tex>.

<tex>\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, *, /, -, (, )\}</tex>;

S \rightarrow S O S;\\S \rightarrow (S);\\S \rightarrow 0;\\S \rightarrow DN;\\O \rightarrow + | - | * | /;\\D \rightarrow 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9;\\N \rightarrow NN | \epsilon;\\N \rightarrow 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9.

Вывод строки <tex>2+2*2</tex>: <tex>S \rightarrow SOS \rightarrow SOSOS \rightarrow 2OSOS \rightarrow 2O2OS \rightarrow 2O2O2 \rightarrow 2+2O2 \rightarrow 2+2*2</tex>.

[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Левосторонний вывод]] для такой этой же строки: <tex>S \rightarrow SOS \rightarrow 2OS \rightarrow 2+S \rightarrow 2+SOS \rightarrow 2+2OS \rightarrow 2+2*S \rightarrow 2+2*2</tex>.