- •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)
1.4. Способы задания схем грамматик
Схема грамматики содержит правила вывода, определяющие синтаксис языка, или, другими словами, возможные компоненты и конструкции цепочек порождаемого языка. Для задания правил используются различные формы описания: символическая, форма Наура-Бэкуса, итерационная форма и синтаксические диаграммы.
В работах, связанных с рассмотрением общих свойств грамматик, обычно применяют символическую форму задания правил. Эта форма была рассмотрена в предыдущем параграфе. Она предусматривает использование в качестве элементов нетерминального словаря отдельных символов и стрелки в качестве разделителя правой и левой частей правила.
1.4.1. Форма Наура-Бэкуса
При описании синтаксиса конкретных языков программирования приходится вводить большое число нетерминальных символов, и символическая форма записи теряет свою наглядность. В этом случае применяют форму Наура-Бэкуса (ФНБ), которая предполагает использование в качестве нетерминальных символов комбинаций слов естественного языка, заключенных в угловые скобки, а в качестве разделителя - специального знака, состоящего из двух двоеточий и равенства. Например, если правила <L> ® <L> и <L> ® <E> записаны в символической форме, и символ <L> соответствует синтаксическому понятию "список", а символ <E> - "элемент списка", то их можно представить в форме Наура-Бэкуса так:
<список>::= <элемент списка><список>, <список>::= <элемент списка>.
Чтобы сократить описание схемы грамматики, в ФБН разрешается объединять правила c одинаковой левой частью в одно правило, правая часть которого должна включать правые части объединяемых правил, разделенные вертикальной чертой. Используя объединение правил, для рассматриваемого примера получаем:
<список>::=<элемент списка><список>|<элемент списка>.
1.4.2. Итерационная форма
Для получения более компактных описаний синтаксиса применяют итерационную форму описания. Такая форма предполагает введение специальной операции, которая называется итерацией и обозначается парой фигурных скобок со звездочкой. Итерация вида {a}* определяется как множество, включающее цепочки всевозможной длины, построенные с использованием символа a, и пустую цепочку.
{a}* = {$, a, aa, aaa, aaaa,...}.
Иcпользуя итерацию для описания множества цепочек, задаваемых символическими правилами, для списка получаем:
<L> ® <E> {<E>}*.
Например, описание множества цепочек, каждая из которых должна начинаться знаком # и может состоять из произвольного числа букв x и y, может быть представлено в итерационной форме так:
<I> ® #{x | y}* .
В итерационных формах описания наряду с итерационными cкобками часто применяют квадратные скобки для указания того, что цепочка , заключенная в них, может быть опущена. С помощью таких скобок правила:
<A> ® x<A>y<B>z и <A> ® x<B>z
могут быть записаны так:
<A> ® x[<A>y]<B>z.
1.4.3. Синтаксическая диаграмма
Для того, чтобы улучшить зрительное восприятие и облегчить понимание сложных синтаксических описаний, применяют представление правил грамматики в виде синтаксических диаграмм. Правила построения таких диаграмм можно сформулировать в следующем виде:
1) Каждому правилу вида <A> ® a1 | a2 |...| ak ставится в соответствие диаграмма, структура которой определяется правой частью правила. 2) Каждое появление терминального символа x в цепочке ai изображается на диаграмме дугой, помеченной этим символом x, заключенным в кружок.
3) Каждому появлению нетерминального символа <A> в цепочке ai ставится в соответствие на диаграмме дуга, помеченная символом, заключённым в квадрат.
4) Порождающее правило, имеющее вид:
<A> ® a1a2...an
изображается на диаграмме следующим образом:
5) Порождающее правило, имеющее вид:
<A> ® a1 | a2 | ... | an
изображается на диаграмме так:
6) Если порождающее правило задано в виде итерации:
<A> ® {a}*,
то ему соответствует диаграмма:
Число синтаксических диаграмм, которые можно построить для заданной схемы грамматики, определяется числом правил. Чтобы сократить число диаграмм, их объединяют, заменяя нетерминальные символы, входящие в диаграмму, построенными для них диаграммами.
Правила 3-6 предусматривают, что в качестве цепочки a1 на объединенной диаграмме могут быть использованы диаграммы построенные для этих цепочек. В качестве примера рассмотрим следующую грамматику с начальным символом <A> :
Г1. 14: Vт = { x, +, (, ) }, Va = {<A>, <B>, <C>},
R = {<A> ® x | (<B>),
<B> ® <A><C>, <C> ® {+<A>}*}.
Синтаксические диаграммы для такой грамматики имеют вид:
Заменяя нетерминальные символы, соответствующими диаграммами, получаем объединенную диаграмму в виде: