Изменения

Рассмотрим грамматику пример для языка правильных скобочных последовательностейследующей грамматики: {| border="1" cellpadding="3" cellspacing="0" style="text-align:center" width=60%!style="background:#f2f2f2"|Правило!style="background:#f2f2f2"|Грамматика после применения правила|-|style="background:#ffffff"|''0. Исходная грамматика''|style="background:#ffffff"|<tex>S\rightarrow aXbX|aZ</tex> <br> <tex>X\rightarrow aY|bY|\varepsilon</tex> <br> <tex>Y\rightarrow X|(S)|SScc</tex><br> <tex>Z\rightarrow ZX</tex>|-|style="background:#ffffff"|''1.Удаление длинных правил''|style="background:# Удалим длинные правила и получим грамматику ffffff"|<tex>S\rightarrow aS_{1}|aZ</tex> <br> <tex>S_{1}\beginrightarrow XS_{array2}</tex> <br> <tex>S_{l l2} S\rightarrow yX</tex> <br> <tex>X\varepsilonrightarrow aY|A)bY|SS\varepsilon</tex> <br> <tex>Y\ Arightarrow X|cc</tex> <br> <tex>Z\rightarrow (SZX</tex>|-|style="background:#ffffff"|''2. Удаление <tex>\end{array}varepsilon</tex>.-правил''|style="background:# Удалим &epsilon; правила - ffffff"|<tex>S\beginrightarrow aS_{array1}|aZ</tex> <br> <tex>S_{l l1} S\rightarrow XS_{2}|S_{2}</tex> <br> <tex>S_{2}\varepsilonrightarrow yX|S'y</tex> <br> <tex>X\rightarrow aY|bY</tex> <br> <tex>Y\ S'rightarrow aY|bY|cc</tex> <br> <tex>Z\rightarrow A)ZX</tex>|S-|style="background:#ffffff"|''3. Удаление цепных правил'S'\\ A|style="background:#ffffff"|<tex>S\rightarrow (S'|(\endaS_{array1}|aZ</tex>.# Удалим цепные правила - <br> <tex>S_{1}\beginrightarrow XS_{array2}|yX|y</tex> <br> <tex>S_{l l2} S\rightarrow yX|y</tex> <br> <tex>X\rightarrow aY|bY</tex> <br> <tex>Y\varepsilonrightarrow aY|A)bY|S'S'\cc</tex> <br> <tex>Z\rightarrow ZX</tex>|- S|style="background:#ffffff"|''\rightarrow A)|S4. Удаление бесполезных символов'S'\\ A|style="background:#ffffff"|<tex>S\rightarrow (S'|(\endaS_{array1}</tex>.# Заменим терминалы на нетерминалы - <br> <tex>S_{1}\beginrightarrow XS_{array2}|yX|y</tex> <br> <tex>S_{l l2} S\rightarrow yX|y</tex> <br> <tex>X\rightarrow aY|bY</tex> <br> <tex>Y\varepsilonrightarrow aY|bY|cc</tex>|AB-|Sstyle="background:#ffffff"|''5. Уберём ситуации, когда в правиле встречаются несколько терминалов.'S'\\ |style="background:#ffffff"|<tex>S'\rightarrow AB|S'S'S_{2}S_{1}</tex> <br> <tex>S_{2}\rightarrow a</tex> <br> <tex>S_{1}\ Arightarrow XS_{2}|S_{3}X|y</tex> <br> <tex>S_{2}\rightarrow CS'S_{3}X|(y</tex> <br> <tex>S_{3}\rightarrow y</tex> <br> <tex>X\ Crightarrow S_{2}Y|X_{1}Y</tex> <br> <tex>X_{1}\rightarrow (\\ Bb</tex> <br> <tex>Y\rightarrow )\endS_{2}Y|X_{1}Y|Y_{1}Y_{1}</tex> <br> <tex>Y_{array1}\rightarrow c</tex>.|}