Преобразования грамматик

Преобразования грамматик
1. Эквивалентные преобразования грамматик
2. Однозначность грамматики и языка.
3. Набор допустимых преобразований.
4. Достижимые свойства грамматик.
5. Автоматные языки
6. Бэкуса — Наура формы (БНФ)
Эквивалентные преобразования грамматик
С разных точек зрения может оказаться желательным преобразование заданной грамматики в такую эквивалентную ей грамматику (т. е. порождающую тот же язык, что и исходная грамматика), которая удовлетворяет определенным свойствам (заметим, что общего алгоритмического метода, осуществляющего любую желаемую модификацию грамматики, не существует). Например, может возникнуть необходимость исключить так называемую левую рекурсию или удалить все правила с пустой правой частью.
Однако для достижения той или иной цели не всякое эквивалентное преобразование грамматики будет допустимым, поскольку приходится заботиться о сохранении ряда свойств исходной грамматики. Например, переход от грамматики Г0 к эквивалентной грамматике, содержащей несколько другой набор правил Е → Е + Т|Е * Т\Т; Т → (Е)|а, нельзя признать допустимым, поскольку после такой модификации структура выражений а + а * а и а * а + а подразумевает тот же порядок выполнения операций, что и в выражениях (a + а) * а и (а * а) + а соответственно.