## 1. Устранение неоднозначности
Чтобы устранить неоднозначность, грамматику надо переписать
$A→B$  
$G=(N,T,P,S)$  
$T={if,then,else,other}$  
$N={S,E}$  
  
$S →$ $if$ $E$ $then$ $S/$  
 $if$ $E$ $then$ $S$ $else$ $S/$ $other$  
 ex: $if$ $E_1$ $then$ $if$ $E_2$ $then$ $S_1$ $else$ $S_2$  
 ![Устранение неоднозначности](06_01.%20Устранение%20неоднозначности.png)  
 Из этих 2 вариантов предпочтительнее 1 вариант, т.к. общее правило языка гласит: "сопоставить каждое else ближайшему не занятому then". Эта идея может быть встроена в грамматику для устранения неоднозначности. Основная идея заключается в том, что инструкция, появляющаяся между then и else, должна быть "сбалансированной", т.е. не должна оканчиваться на then, не соответствующее некоторому else.  
 $S→S_1/S_2$  
 $S_1→if$ $E$ $then$ $S_1$ $else$ $S_1/other$  
 $S_2→if$ $E$ $then$ $S/if$ $E$ $then$ $S_1$ $else$ $S_2$  
## 2. Левая факторизация
ex: $S → if$ $E$ $then$ $S$ $else$ $S/$  
$if$ $E$ $then$ $S$  
Продукции для терминала $A$ переписываются так, чтобы отложить принятие решения до тех пор, пока из входного потока не будет прочитано достаточное количество символов для правильного выбора
$A → αβ_1/αβ_2$  
$A → αA'$  
$A → β_1/β_2$  
  
$S → if$ $E$ $then$ $SS'$  
$S'→else$ $S/ε$  
$E→b$  
## 3. Устранение левой рекурсии
$S$-грамматика является левой рекурсивной, если в ней имеется нетерминал $A$ такой, что порождает цепочку $A+⇒Aα$  
$A→Aβ$  
↓  
$A→βA'$  
$A'→αA'/ε$  
  
$E→E+T/T$  
$T→T∗F/F$  
$F→(E)/id$  
↓  
$E → TE'$  
$E'→+TE'/ε$  
$T→FT'$  
$T'→∗FT'/ε$  
$F→(E)/id$  
  
$id+id∗id$  
$E ⇒ E+T ⇒ T+T ⇒ F+T⇒id+T⇒id+T∗F⇒id+F∗F⇒id+id∗F⇒id+id∗id$  
Если грамматика содержит некоторое количество леворекурсивных правил для одного и того же нетерминала, в общем виде это будет записано: $A→Aα_1/Aα_2/Aα_3/.../β_1/β_2/β_3/...$ 
Если таких правил несколько, на первом шаге группируются все леворекурсивные правила, а на втором заменяются $A$-продукции по правилам  
$A→β_1A'/β_2A'/β_3A'/...$  
$A'→α_1A'/α_2A'/α_3A'/.../ε$
## 4. Устранение недостижимых символов
Нетерминальный символ $X$ ($X∈N$) является **недостижимым**, если он не является стартовым ($X≠S$) и не существует вывода вида $S∗⇒αXβ$. Т.е., этот символ никогда не появляется в правой части выводимой цепочки
## 5. Устранение бесполезных символов
Нетерминальный символ $X$ ($X∈N$) является **бесполезным**, если не существует вывода вида $S∗⇒αXβ⇒αxβ$ ($α, β, x∈T∗$). Т.е., такие символы не играют никакой роли в построении правильных цепочек грамматики
## 6. Устранение ε-продукций
Контекстно-свободная грамматика называется **ε-свободной**, если в множестве ее продукций отсутствует правило вида $x→ε$, либо существует ровно одно правило, где из $S$ выводится $ε$, и $S$ не встречается в правых частях остальных продукций
## 7. Устранение цепных правил
КС-грамматика называется **грамматикой без циклов**, если в ней нет вывода вот такого вида: $A∗⇒A$ $(A∈N)$.  
 Эквивалентные преобразования в конечном итоге обеспечивают:
 1. Однозначность и детерминированность грамматического разбора
 2. Устранение лишних шагов в дереве разбора
 3. Простые критерии в выборе продукций из множества альтернативных  
## Проблемы разрешимости
Доказано, что проблема эквивалентности грамматик в общем случае алгоритмически неразрешима. Это означает, что не существует алгоритма, который бы позволял проверить, являются ли 2 заданные грамматики эквивалентными (такой алгоритм и не может быть создан).  
Не разрешима в общем виде и проблема однозначности грамматик. Это означает, что не существует и не будет существовать алгоритм, который позволял бы для произвольной грамматики ответить на вопрос "однозначна она или нет?". Но это не означает, что проблема не разрешима вообще. Для некоторых классов грамматик данная проблема разрешима. Например, для класса регулярных грамматик.  
Основные цели преобразования грамматик:
1. Упрощение правил грамматики
2. Облегчение создания распознавателя языка  

Грамматика, к которой применены эквивалентные преобразования в определенном порядке, называется **приведенной грамматикой**. Преобразования должны быть выполнены в следующем порядке:
1. Устранение бесполезных символов
2. Устранение недостижимых символов
3. Устранение ε-продукций
4. Удаление цепных правил