- •1. Формальные языки и грамматики
- •1.1. Введение
- •1.1.1. Трансляторы, интерпретаторы и компиляторы
- •1.1.2. Стадии работы компилятора
- •1.1.3. Построение компилятора
- •1.2. Определение формальной грамматики и языка
- •1.2.1. Первичные понятия
- •1.2.2. Примеры, иллюстрирующие первичные понятия
- •1.2.3. Пустой язык
- •1.2.4. Резюме
- •1.3. Типы формальных языков и грамматик
- •1.3.1. Грамматики типа 0
- •1.3.2. Грамматики типа 1
- •1.3.3. Грамматики типа 2
- •1.3.4. Грамматики типа 3
- •1.3.5. Вывод в кс-грамматиках и правила построения дерева вывода
- •1.3.6. Синтаксический разбор
- •1.3.7. Левый и правый выводы
- •1.3.8. Неоднозначные и эквивалентные грамматики
- •1.3.9. Резюме
- •1.4. Способы задания схем грамматик
- •1.4.1. Форма Наура-Бэкуса
- •1.4.2. Итерационная форма
- •1.4.3. Синтаксическая диаграмма
- •1.4.4. Резюме
- •1.5. Построение грамматик и грамматики, описывающие основные конструкции языков программирования
- •1.5.1. Рекомендации по построению грамматик
- •1.5.2. Описание списков
- •1.5.3. Пример построения грамматик
- •1.5.4. Грамматики, описывающие целые числа без знака и идентификаторы
- •1.5.5. Грамматики для арифметических выражений
- •1.5.6. Грамматика для описаний
- •1.5.7. Грамматика, задающая последовательность операторов присваивания
- •1.5.8. Грамматики, описывающие условные операторы и операторы цикла
- •1.5.9. Резюме
- •2. Автоматные грамматики и распознаватели
- •2.1. Автоматные распознаватели
- •2.2. Недетерминированные распознаватели
- •2.3. Преобразование некоторых типов языков и грамматик к автоматному виду.
- •2.4 Построение распознавателя для заданного конечного языка
- •2.5 Минимизация числа состояний распознавателя
- •2.6 Резюме
- •3. Контекстно-свободные грамматики и магазинные автоматы.
- •3.1 Приведенные грамматики.
- •3.2.Преобразование кс-грамматик
- •3.3 Магазинные автоматы.
- •3.4. Нисходящие распознаватели, ll(k) и разделенные грамматики. Построение распознавателя.
- •3.5. Функции перв, след и выбор.
- •3.6. Слаборазделенные и ll(1) - грамматики. Преобразование грамматик к виду ll(1)
3.2.Преобразование кс-грамматик
Исключение леворекурсивных правил.
Определение. Правило вида <A> ® a <A> , где A Î VA , a Î(Vт ÈVA) * , называется праворекурсивным, а правило вида <A> ® <A>a - леворекурсивным. |
Утверждение. Для каждой КС-грамматики Г, содержащей леворекурсивные правила, можно построить эквивалентную грамматику Г', не содержащую леворекурсивных правил. |
Способ построения эквивалентной грамматики заключается в следующем. Допустим, что исходная грамматика Г содержит правила: <A> ® <A>a 1 | <A>a 2 | ... |<A>a m| , где ни одна цепочка b не начинается с <A> и a1, b1Î(Vт ÈVA) * . Введем новый нетерминал <A'> и преобразуем правила так:
<A> ® b 1 | b 2 |...| b n | b 1<A'> | b 2<A'>|...| b n<A'>, <A'> ®a 1 | a 2 |...| a m| a 1<A'> |a 2<A'>|...|a m<A'>.
Заменяя все правила с левой рекурсией в Г описанным способом, получим грамматику Г', причем L(Г)=L(Г') , поскольку каждая цепочка, выведенная в грамматике Г, может быть построена в грамматике Г'. Рассмотрим построение выводов в Г и Г'. В грамматике Г вывод цепочки имеет вид:
< A> Þ <A>a 1 Þ <A>a 1a 1 Þ <A>a 1a 1a 1 Þ b 1a 1a 1a 1,
в грамматике Г' эта же цепочка выводится так:
<A> Þ b 1<A'> Þ b 1a 1<A'> Þ b 1a 1a 1<A'> Þ b 1a 1a 1a 1.
Чтобы показать технику преобразования, рассмотрим пример. Требуется преобразовать грамматику Г1. 9 (рассмотренную ранее), которая задана схемой:
Г1. 9: R={<E> ® <E> + <T> | <T>, < T> ® <T> * <F> | <F>, <F> ® ( <E> ) | a}.
Следуя описанному способу, правила <E> ® <E> + <T> | <T> преобразуем в правила <E>® <T> | <T><E'> и <E'> ® +<T> | +<T><E'> , а правила <T> ® <T> * <F> | <F> преобразуем в правила <T> ® <F> | <F><T'> и <T'> ® *< F> | * <F><T'>. В результате получаем грамматику Г'1. 9, имеющую схему:
Г'1. 9 : R'= { <E> ® < T>,
<E> ® <T><E'>, < E'>® + <T>, <E'> ® + <T><E'>, <T> ® <F>, <T> ® <F><T'>, <T'> ® * <F>, <T'> ® * <F><T'>, < F> ® a, <F> ® (<E>) },
не содержащую леворекурсивных правил.
Исключение цепных правил.
Определение. Правило грамматики вида <A> ® <B>, где <A>,<B> ÎVA, называется цепным. |
Утверждение. Для КС-грамматики Г, содержащей цепные правила , можно построить эквивалентную ей грамматику Г', не содержащую цепных правил. |
Идея доказательства заключается в следующем. Если схема грамматики имеет вид
R = {...,<A> ® <B>,...,<B> ® <C>, ... , <C> ® a<X> },
то такая грамматика эквивалентна грамматике со схемой
R' = {...,<A> ® a<X>,...},
поскольку вывод в грамматике со схемой R цепочки a<X> :
<A> Þ< B> Þ <C> Þ a<X>
может быть получен в грамматике со схемой R' с помощью правила <A> ® a<X>. В общем случае доказательство последнего утверждения можно выполнить так. Разобьем R на два подмножества R1 и R2, включая в R1 все правила вида <A> ® < B>. Для каждого правила из R1 найдем множество правил S(<Ai>), которые строятся так: если <Ai> Þ * <Aj> и в R2 есть правило <Aj> ® a , где a - цепочка словаря (Vт ÈVA)* , то в S(<Ai>) включим правило <Ai> ® a . Построим новую схему R' путем объединения правил R2 и всех построенных множеств S(<Ai>). Получим грамматику Г' = {Vт ,Va , I , R'}, которая эквивалентна заданной и не содержит правил вида <A> ® <B>. В качестве примера выполним исключение цепных правил из грамматики Г1. 9 со схемой :
Г1. 9: R={<E> ® <E> + <T> | <T>, < T> ® < T> * <F> | <F>, <F> ® ( <E> ) | a}.
Вначале разобьем правила грамматики на два подмножества:
R1 = { <E> ® <T>,<T> ® <F> } , R2 = { <E> ® <E>+<T>, <T> ® <T>*<F>, <F>® (<E>) | a }
Для каждого правила из R1 построим соответствующее подмножество.
S(<E>) = { <E> ®< T>*<F>, <E> ® (<E>) | a }, S(<T>) = { <T> ® (<E>) | a}
В результате получаем искомую схему грамматики без цепных правил в виде:
R2 U S(<E>) U S(<T>) = { <E> ® --> <T>+<T> | <T>*<F> | (<E>) | a,
<T> ® <T>*<F> | (<E>) | a, <F> ® (<E>) | a }
Последний вид рассматриваемых преобразований связан с удалением из грамматики правил с пустой правой частью.
Определение. Правило вида <A> ® $ называется аннулирующим правилом. |
Преобразование неукорачивающих грамматик.
Определение. Грамматика называется неукорачивающей или грамматикой без аннулирующих правил, если либо 1)схема грамматики не содержит аннулирующих правил, 2)либо схема грамматики содержит только одно правило вида <I> ® $, где <I> - начальный символ грамматики, и символ I не встречается в правых частях остальных правил грамматики. |
Для грамматик, содержащих аннулирующие правила, справедливо следующее утверждение.
Утверждение. Для каждой КС-грамматики Г', содержащей аннулирующие правила, можно построить эквивалентную ей неукорачивающую грамматику Г, такую что L(Г')=L(Г). |
Построение неукорачивающей грамматики предполагает увеличение числа правил заданной грамматики путем построения дополнительных правил, получаемых в результате исключения нетерминалов аннулирующих правил. Чтобы построить дополнительные правила необходимо выполнить все возможные подстановки пустой цепочки вместо аннулирующего нетерминала во все правила грамматики. Если же в грамматике есть правило вида <I> ® $ и символ <I> входит в правые части других правил грамматики, то следует ввести новый начальный символ <I'> и заменить правило <I> ® $ двумя новыми правилами: <I'> ® $ и <I'>® <I> . В качестве иллюстрации способа построения неукорачивающих грамматик, исключим аннулирующие правила из следующей грамматики:
Г3. 3 : R = { <I> ® a<I>b<I>, <I> ® b<I>a<I>, <I> ® $ } Выполняя все возможные замены символа I в первом правиле грамматики, получаем четыре правила вида:
<I> ® a<I>b<I>, <I> ® ab<I>, <I>® a<I>b, <I>® ab .
Поступая аналогично со вторым правилом, имеем:
<I> ® b<I>a<I>, <I> ® ba<I>, <I> ® b<I>a, <I> ® ba.
Учитывая, что начальный символ, образующий аннулирующее правило, входит в правые части других правил грамматики, заменим правило <I> ® $ правилами вида <I'>® $ и <I'>® <I> . Построенная совокупность правил образует схему искомой неукорачивающей грамматики. Все приведенные выше преобразования грамматик могут быть использованы и оказаться полезными при построении как конечных, так и магазинных автоматов.