Цель работы:
Изучение основных форм представления метаязыков описания грамматик.

Порядок выполнения ДЛР:
1. Получить у преподавателя задание на выполнение ДЛР.
2. Составить описание заданного оператора в виде металингвистических формул Бэкуса-Науэра.
3. Составить описание заданного оператора в виде синтаксических диаграмм.
4. Составить фрагменты программной реализации формальных элементов синтаксических диаграмм на языке С или С++ по приведенным в методичке программным фрагментам на языке C.
5. Составить на С или С++ программу реализации транслятора языка по созданному описанию в виде синтаксических диаграмм.
6. Разработать самостоятельно тест на проверку работоспособности разработанного транслятора.
7. Отладить разработанную программу.
8. Составить отчет по домашней лабораторной работе, который должен включать:
- описание исходного задания;
- описание задания в виде формул Бэкуса-Науэра;
- описания задания в виде синтаксических диаграмм;
- программные фрагменты отдельных модулей синтаксических диаграмм на языке С или С++;
- текст программной реализации созданного транслятора на языке C или С++;
- результаты тестирования программной реализации транслятора.
9. Составить описание задания на получение обратной польской записи алгебраического выражения в виде управляемых таблиц:
- получить фрагменты перевода формальных блоков управляемых таблиц, используя генераторы LEX и YACC на языке С;
- протестировать созданную программную реализацию разработанного транслятора на языке С;
- разработать самостоятельно тест на проверку работоспособности программы.
10. Защитить отчет по ДЛР у преподавателя.

Методическое пособие для проведения домашней лабораторной работы

1.Структура языков и трансляторы. Определение и структура языка
Можно сделать попытку разработать транслятор для простого, «рудиментарного» языка программирования. Такая разработка может послужить примером систематического, хорошо структурированного подхода при написании программы нетривиальной сложности и размера. При этом можно продемонстрировать практическое применение методов, рассмотренных ранее. Кроме того, постараемся дать общее представление о структуре трансляторов и принципах их работы. Знание этого предмета позволит лучше разобраться в искусстве программирования на языках высокого уровня, а также облегчит программисту разработку собственных систем, предназначенных для конкретных целей и областей применения. Но, поскольку теория трансляторов - сложный и обширный предмет, в этом отношении данное пособие будет носить лишь вводный и обзорный характер. Главное, что следует уяснить, - это что структура транслятора отражает структуру языка и сложность - или простота - языка решающим образом влияет на сложность его транслятора. Поэтому начнем с описания строения языка, а затем сосредоточим внимание исключительно на простых структурах, для которых можно построить простые, модульные трансляторы. Такие простые языковые конструкции оказываются достаточными для удовлетворения практически всех потребностей, возникающих при использовании языков программирования.
В основе каждого языка лежит словарь. Его элементы обычно называют словами, но в теории формальных языков их называют символами. Языки характеризуются тем, что некоторые последовательности слов считаются правильными предложениями языка, а другие - неправильными, или не принадлежащими данному языку. Чем же определяется, является ли некоторая последовательность слов правильным предложением? Обычно это определяется грамматикой, синтаксисом (можно сказать - структурой) языка. Синтаксис определяется как множество правил или формул, которые задают множество (формально правильных) предложений. Такое множество синтаксических правил не только позволяет установить, принадлежит ли некоторая заданная последовательность слов множеству предложений языка, но при этом определяет структуру предложения, которая устанавливает его смысл. Поэтому ясно, что синтаксис и семантика (==смысл) тесно связаны между собой. Следовательно, определения, связанные со структурой, всегда следует рассматривать как средство распознавания смысла. Но это не помешает изучить вначале исключительно структурные аспекты языка, отвлекаясь от их связи со смыслом, т. е. от их интерпретации.
Рассмотрим, например, предложение «Кошки спят». Слово «кошки» - подлежащее, а «спят» - сказуемое. Это предложение принадлежит языку, который можно описать, например, при помощи следующих синтаксических правил:

<предложение>::=<подлежащее> <сказуемое>
<подлежащее> ::= кошки \ собаки
<сказуемое> ::= спят \едят

Смысл этих трех строчек таков:
  1. Предложение состоит из подлежащего, за которым следует сказуемое.
  2. Подлежащее состоит либо из одного слова «кошки», либо из одного слова «собаки».
  3. Сказуемое состоит либо из слова «спят», либо из слова «едят».

Идея заключается в том, что любое предложение можно получить из начального символа <предложение> последовательным применением правил подстановки.
Формализм, или нотация, использованный при написании этих правил, называется Бэкус-Науровой формой (БНФ).
Синтаксические единицы <предложение>, <подлежащее> и <сказуемое> называются нетерминальными символами, слова кошки, собаки, спят и едят - терминальными символами, а правила - порождающими правилами.
Символы ::= и | - это метасимволы языка БНФ. Метасимволы не принадлежат описываемому языку, а относятся к языку описания. Метасимволами являются также < > - скобки нетерминальных символов.
Если для краткости мы будем использовать отдельные заглавные, буквы для нетерминальных символов, то данный пример можно переписать следующим образом:

Пример 1:
S::=AB
А::=х|у (1.1)
B::=z|w

и язык, определенный этим синтаксисом, будет состоять из четырех предложений xz, yz, xw, yw.

Приведем теперь более точные, математические определения:

1. Пусть язык L = L(T, N, P, S) задан:


2. Язык L(T,N,P,S) есть множество всех цепочек терминальных символов ξ, которые могут порождаться из S по правилу 3 (приведенному ниже):

L={ ξ | S ⇒* ξ, ξ ∈ T*} (1.2)

3. Последовательность σn может порождаться последовательностью σ0 в том и только в том случае, если имеются последовательности σ1, σ2,…, σn-1, такие, что каждое σi может непосредственно порождаться σi-1 по правилу 4 (приведенному ниже) :

0* σn) ⇔ ( σi-1* σi) i=i…n (1.3)

4. Последовательность η может непосредственно порождаться последовательностью ξ в том и только в том случае, если существуют последовательности α', β', ξ', η', такие, что:


Примечание. Правило вида α ::= β12|…|βn, используется как сокращенная запись для множества порождающих правил:
α ::= β1, α ::= β2, ..., α ::= βn

Например, последовательность xz из примера 1 можно получить с помощью следующих шагов непосредственного порождения:
S ⇒ AВ ⇒ xB ⇒ xz;
следовательно, S ⇒* xz, и поскольку xz ∈ T*, то xz есть предложение языка, т. е. xz ∈ L.

Грамматические правила называются порождающими, потому что они определяют, как новые последовательности могут формироваться, или порождаться.
Язык называется контекстно-свободным в том и только в том случае, если он может быть определен с помощью контекстно-свободного множества порождающих правил. Множество порождающих правил контекстно-свободно тогда и только тогда, когда все его члены имеют вид

A ::= ξ (A ∈ N, ξ ∈ (N U T)*),

т. е. если его левая часть состоит из одного нетерминального символа, который может заменяться на последовательность, стоящую в правой части, независимо от контекста, в котором он встречается.

Если порождающее правило имеет вид

αAβ ::= αξβ

то оно называется контекстно-зависимым, так как замена А на ξ может иметь место только в контекстах α и β. Далее мы ограничим рассмотрение только контекстно-свободными языками.
Из примера 2 видно, как при помощи рекурсии конечное множество порождающих правил может задавать бесконечное множество предложений
Пример 2:
S ::= xA (1.4)
A ::= z|yA

Начальный символ S может порождать следующие предложения:
xz
xyz
хууz
xyyyz и т.д.

2. Анализ предложений
Задача трансляторов, или «языковых процессоров», - это в первую очередь не порождение, а распознавание предложений и их структуры. Это означает, что шаги порождения, которые формируют предложение, должны реконструироваться при чтении предложения, т. е., проходиться в обратном порядке. В принципе это очень трудная, а иногда и невыполнимая задача. Ее сложность сильно зависит от правил порождения, которые определяют язык. Разработка алгоритмов распознавания для языков с достаточно сложной структурой - задача теории синтаксического анализа. Здесь же наша цель - разработать метод построения алгоритмов распознавания, достаточно простых и эффективных для практического применения. Это значит, что вычислительные затраты на анализ предложения должны находиться в линейной зависимости от длины предложения, в самом худшем случае функция зависимости может быть n*log n, где n - длина предложения. Разумеется, мы не можем ставить задачу поиска алгоритма распознавания для любого заданного языка, будем реалистами и поступим наоборот: построим некоторый эффективный алгоритм, а затем определим, с каким классом языков он может работать.
Из основного требования эффективности следует в первую очередь, что каждый очередной этап анализа должен выбираться лишь в зависимости от текущего состояния процесса и от одного следующего читаемого символа. Другое наиболее важное требование - чтобы ни к какому этапу не было повторного обращения. Эти два требования известны как технический термин просмотр на один символ вперед без возврата.
Основной метод, который мы здесь разберем, называется нисходящим грамматическим разбором, поскольку, применяя этот метод, мы будем пытаться реконструировать этапы порождения (которые в принципе образуют дерево) от начального символа к конечному предложению, т. е. сверху вниз.
Вернемся к примеру 1: нам дано предложение "Собаки едят", и мы должны определить, принадлежит ли оно языку. По определению предложение принадлежит языку, только если оно может порождаться из начального символа <предложение>. Из грамматических правил следует, что предложение должно состоять из подлежащего, за которым следует сказуемое. Теперь мы можем разделить задачу на две подзадачи: вначале нужно определить, может ли какая-либо начальная часть предложения порождаться из символа <подлежащее>. Действительно, собаки может непосредственно порождаться из этого символа, поэтому мы убираем символ собаки из входного предложения (т. е. сдвигаемся на один шаг) и переходим к следующей подзадаче: определить, может ли оставшаяся часть предложения порождаться из символа (сказуемое). Поскольку ответ вновь положительный, результат анализа положительный. Процесс работы можно изобразить такой схемой, где слева показаны стоящие задачи, а справа - еще не прочитанная часть входного предложения:

|<предложение> |
|<подлежащее> | <сказуемое> собаки едят
|собаки | <сказуемое> собаки едят
|<сказуемое> | собаки едят
|едят | едят
| | едят

Вторая схема демонстрирует процесс анализа предложения xyyz в соответствии с порождающими правилами примера 2:
S xyyz
хА xyyz
A yyz
уА yyz
A yz
уА yz
А z
z z
- -

Поскольку обратное прослеживание этапов порождения предложения называется грамматическим разбором, описанный выше алгоритм есть алгоритм грамматического разбора. В обоих примерах отдельные подстановки можно производить однозначно при проверке одного очередного символа во входном предложении. К сожалению, это не всегда бывает возможно, что видно из следующего примера:

Пример 3:
S ::= A|B
А ::= хА|у (1.5)
B ::= xB|z

Мы пытаемся, проанализировать предложение xxxz

S xxxz
A xxxz
хА xxxz
А xxz
хА xxz
А xz
хА xz
A z

и попадаем впросак. Трудность возникает на самом первом шаге, когда решение о замене S на А или В нельзя принять на основе лишь первого символа. Можно прослеживать один из возможных выборов, а затем возвращаться, если этот путь не дает нужного решения. Такое действие называется возвратом. В языке примера 3 число возможных шагов, на которые приходится иногда возвращаться, не ограничено. Понятно, что подобная ситуация крайне нежелательна; следовательно, нужно избежать таких особенностей языка, которые приводят к возврату при грамматическом разборе. Поэтому мы принимаем решение, что будем рассматривать только такие грамматические системы, в которых начальные символы альтернативных правых частей порождающих правил различны.

Ограничение 1:
Если дано порождающее правило

A ::= ξ12|…|ξn,

то множества начальных символов всех предложений, которые могут порождаться из различных ξj, не должны пересекаться, т. е.

first (ξi) ∩ first(ξj) = Ø для всех i ≠j.

Множество first (ξj) есть множество всех терминальных символов, которые могут встречаться в начале предложений, полученных из ξj.

Пусть это множество вычисляется согласно следующим правилам:
1. Если первый символ аргумента терминальный. то
first (αξ) ={α}

2. Если первый символ нетерминальный и стоит в левой части порождающего правила
A ::= α1 | α2 | ... | αn, то
first (αξ) = first (α1) U first (α2) U ... U first (αn).

В примере З можно заметить, что х ∈ first (А) и x ∈ first(B). Следовательно, в первом порождающем правиле нарушено ограничение 1. На самом деле, легко найти синтаксис для языка примера 3, удовлетворяющий ограничению 1. Нужно отложить разделение на части до тех пор, пока не будут пройдены все х. Следующие порождающие правила эквивалентны правилам (1.5) в том смысле, что они порождают то же множество предложений:

S ::= C |xS, (1.5a)
C ::= y|z

К сожалению, ограничение 1 недостаточно сильно, чтобы избавить нас от дальнейших неприятностей. Рассмотрим Пример 4:

S ::= Ax, (1.6)
A ::= x|ε

Здесь ε обозначает нулевую последовательность символов. Если мы попытаемся разобрать предложение х, то можем попасть в следующий «тупик»:

S х
Ах х
xx x
x -

Трудность возникает из-за того, что мы должны были следовать правилу А ::= ε вместо А ::= х. Эта ситуация называется проблемой пустой строки, она связана со случаем, когда нетерминальный символ может порождать пустую последовательность. Чтобы ее избежать, мы вводим

Ограничение 2:
Для любого символа А ∈ N, который порождает пустую последовательность (А ::= ε), множество начальных символов не должно пересекаться со множеством символов, которые могут появляться в предложениях языка справа от какой-либо последовательности, порождаемой А (внешними символами А), т. е.

first(A) ∩ follow (A) = 0

Множество follow (А) определяется так: берутся все порождающие правила Pi вида
X :: = ξAη,

затем для каждой последовательности ηi, стоящей справа от А, определяется ее множество начальных символов Si = first(ηi). Множество follow(A) - объединение всех таких множеств Si. Если хотя бы одна ηi может порождать пустую последовательность, то множество follow(X) следует также включить в follow(A). В примере 4 ограничение 2 нарушается для символа А, поскольку

first(A) = follow(A) = {х}

Повторение подобных последовательностей символов в предложениях обычно задается в порождающих правилах с помощью рекурсии. Например, порождающее правило
А ::= В|АВ

описывает множество предложений В, ВВ, ВВВ ... Однако использование такого правила теперь запрещено ограничением 1, так как
first(B) ∩ first(AB) = first(B) ≠ 0

Если мы заменим это правило его слегка модифицированной версией
А ::= ε|АВ,

порождающей последовательности ε, В, ВВ, ВВВ, ..., то нарушим ограничение 2, поскольку
first(A) = first(B) и, следовательно,
first(A) ∩ follow(A) ≠ 0

Очевидно, что два эти ограничения запрещают использование определений с «левой рекурсией». Простой способ избежать таких форм - это либо использовать правую рекурсию, либо расширить БНФ-нотацию с тем, чтобы она допускала явное выражение повторений.
Поэтому определим {В} как множество последовательностей
ε, В, ВВ, ВВВ ...

Конечно, нужно учитывать, что каждая такая конструкция может порождать пустую последовательность. (Фигурные скобки { } являются метасимволами расширенной БНФ.).
Эти рассуждения, а также пример преобразования порождающих правил (1.5) в (1.5а) могут навести на мысль, что «трюки» с преобразованием грамматик позволяют решить все проблемы синтаксического анализа. Но не следует забывать, что структура предложений связана с их смыслом и что смысл синтаксических конструкций обычно выражается через смысл их компонент. Рассмотрим, например, язык, состоящий из выражений, которые включают операнды а, b, с и знак минус, обозначающий вычитание:
S ::= A|S - A,
А ::= а|b|c

Согласно этой грамматике, предложение а - b - с имеет структуру, которую с использованием скобок можно выразить следующим образом: ((а - b ) - с). Но если эту грамматику преобразовать в эквивалентную, но свободную от левой рекурсии
S ::= A| A - S,
A ::= а|b|c

то это же предложение получит другую структуру, которую можно выразить как (а-( b - с)).
Учитывая принятое значение вычитания, мы видим, что эти две формы вовсе не эквивалентны с точки зрения семантики.
Следует сделать вывод, что при определении языка, обладающего смыслом, нужно всегда принимать во внимание его семантическую структуру, поскольку синтаксис должен ее отражать.

3. Построение синтаксического графа
В предыдущем разделе был описан алгоритм нисходящего распознавания, применимый к грамматикам, которые удовлетворяют ограничениям 1 и 2. Теперь мы перейдем к реализации этого алгоритма в виде конкретной программы. При этом можно использовать два различных метода. Один из них- это написать универсальную программу нисходящего грамматического разбора, пригодную для всех возможных грамматик (удовлетворяющих ограничениям 1 и 2). В этом случае конкретные грамматики задаются этой программе в виде данных некоторой структуры, которая в каком-то смысле управляет ее работой. Поэтому такая программа называется таблично-управляемой. Другой метод - разрабатывать программу нисходящего грамматического разбора специально для заданного конкретного языка; при этом его синтаксис по определенным правилам отображается в последовательность операторов, т. е. в программу. Мы по очереди рассмотрим оба этих метода, каждый из которых имеет свои преимущества и недостатки. При построении транслятора для конкретного языка программирования вряд ли потребуется высокая гибкость и параметризация, свойственные универсальной программе, тогда как программа грамматического разбора, предназначенная специально для данного языка, обычно оказывается более эффективной и с ней легче работать, поэтому такой подход предпочтителен. В обоих случаях полезно представлять заданный синтаксис в виде так называемого синтаксического графа, или графа распознавания, Такой граф отражает управление ходом работы при грамматическом анализе предложения.
Для нисходящего грамматического разбора характерно, что цель анализа известна с самого начала. Эта цель - распознать предложение, т. е. последовательность символов, которая может порождаться из начального символа. Применение порождающего правила, т. е. замена одного символа последовательностью символов, соответствует расщеплению одной цели на некоторое число подцелей, которые должны следовать в определенном порядке. Поэтому нисходящий метод можно называть также целеориентированным грамматическим разбором. При построении программы грамматического разбора можно воспользоваться этим очевидным соответствием между нетерминальными символами и целями: для каждого нетерминального символа строится своя процедура грамматического разбора. Цель каждой такой процедуры - распознавание части предложения, которая может порождаться, из соответствующего нетерминального символа. Поскольку мы хотим построить граф, представляющий всю программу грамматического разбора, то каждый нетерминальный символ будет отображаться в подграф. Поэтому мы приходим к таким правилам построения синтаксического графа:

Правила построения графа:
А1. Каждый нетерминальный символ A с соответствующим множеством порождающих правил

А ::= ξ1|ξ2|…|ξn

отображается в синтаксический граф А, структура которого определяется правой частью порождающего правила в соответствии с А2 - А6.

А2. Каждое появление терминального символа х в ξi соответствует оператору распознавания этого символа во входном предложении. На графе это изображается ребром, помеченным символом х, заключенным в кружок.
Рис. 1.  
A3. Каждому появлению нетерминального символа В в ξi,- соответствует обращение к процедуре распознавания В. На графе это изображается ребром, помеченным символом В, заключенным в квадрат:
Рис. 2.  
А4. Порождающее правило, имеющее вид

А ::= ξ1|ξ2|…|ξn

отображается в граф, где каждый квадрат получен применением правил А2-А6 к ξi.

Рис. 3.  
А5. Строка ξ, имеющая вид

ξ = α1 α2… αn

отображается в граф
Рис. 4.  
где каждый квадрат получен применением правил А2-А6 к αi

А6. Строка ξ, имеющая вид
Рис. 5.  
ξ = {α}

отображается в граф

где α получено применением правил А2-А6 к α.

Пример 5:
А ::= х|(В),
B ::= AC, (1.7)
C ::= {+A}

Здесь «+», х, (, и ) - терминальные символы, а { и } принадлежит расширенной БНФ и, следовательно, являются мета-символами. Язык, порождаемый из А, состоит из выражений с операндами х, знаком операции «+» и скобками. Примеры предложений:

х
(x)
(x+x)
((х))
...

Графы, полученные с помощью применения шести правил построения графов, показаны на рис. 1.1. Заметим, что эту систему графов можно свести в один граф, подставив соответственно С в В и В в А (см. рис. 6).
Рис. 6.  Синтаксические графы для синтаксиса прим. 5
Синтаксический граф является эквивалентным представлением грамматики языка; его можно использовать вместо множества порождающих правил БНФ. Это очень удобная форма, и во многих (если не в большинстве) случаев она предпочтительнее БНФ.
Граф является подходящим представлением, которое может служить отправной точкой для разработчика языка.
Рис. 7.   Сводный синтаксический граф, соответствующий прим. 5
Граф дает более ясное и точное представление о структуре языка, а также позволяет лучше представить себе процесс грамматического разбора.
Для того чтобы обеспечить детерминированный грамматический разбор с просмотром вперед на один символ, были установлены ограничения I и 2. Как проявляются эти ограничения при графическом представлении синтаксиса? Здесь особенно наглядно видны удобство и ясность такого представления.
  1. Ограничению 1 соответствует требование, чтобы при каждом разветвлении можно было выбрать ветвь, по которой будет идти дальнейший разбор по очередному символу на этой ветви. Это означает, что никакие две ветви не должны начинаться с одного и того же символа.
  2. Ограничению 2 соответствует требование, чтобы если какой-либо граф А можно пройти, не читая вообще никаких, входных символов, то такая «нулевая ветвь» должна помечаться всеми символами, которые могут следовать за А. (Это влияет на решение о переходе на эту ветвь.)
Легко проверить, удовлетворяет ли некоторая система графов этим двум ограничениям, не обращаясь к представлению грамматики с помощью БНФ. В качестве вспомогательного шага для каждого графа А определяются множества first(А) и follow(А). Затем непосредственно можно проверить выполнение ограничений 1 и 2. Систему графов, которая.удовлетворяет этим двум ограничениям, мы будем называть детерминированным синтаксическим графом.

4. Построение программы грамматического разбора для заданного синтаксиса
Программу, которая распознает какой-либо язык, легко построить на основе его детерминированного синтаксического графа (если такой граф существует). Этот граф фактически представляет собой блок-схему программы. Но при ее разработке рекомендуется строго следовать правилам преобразования, подобным тем, с помощью которых можно предварительно получить из БНФ графическое представление синтаксиса. Эти правила перечислены ниже. Они применяются в определенном контексте, который предполагает наличие основной программы, содержащей процедуры, которые соответствуют различным подцелям, а также процедуру перехода к очередному символу.
Для простоты мы будем считать, что предложение, которое нужно анализировать, представлено входным файлом input и что терминальные символы - отдельные значения типа char. Пусть символьная переменная char ch всегда содержит очередной читаемый символ. Тогда переход к следующему символу выражается оператором: ch = fgetc(input);
Следует отметить, что функция char fgetc (FILE *fp) является стандартной функцией языка С для чтения символа из файла и для ее использования необходимо в начале программы подключить соответствующий заголовочный файл директивой

#include <stdio.h>

Основная программа будет состоять из оператора чтения первого символа, за которым следует оператор активации основной цели грамматического разбора. Отдельные процедуры, соответствующие целям грамматического разбора или графам, получаются по следующим правилам. Пусть оператор, полученный с помощью преобразования графа S, обозначается через Т(S).

Правила преобразования графа в программу:
В1. Свести систему графов к как можно меньшему числу отдельных графов с помощью соответствующих подстановок.
В2. Преобразовать каждый граф в описание процедуры в соответствии с приведенными ниже правилами ВЗ-В7.
В3. Последовательность элементов
Рис. 8.  
переводится в составной оператор
{T(S1);
T(S2);
...;
T(Sn)
}

В4. Выбор элементов
Рис. 9.  
переводится в условный оператор

if (belongsTo (ch, L1)) T(S1);
else if (belongsTo(ch, L2)) T(S2);
else ...
if (belongsTo (ch, Ln)) T(Sn);
else error();

где Li означает множество начальных символов конструкции Si (Li = first (Si)).где L означает множество начальных символов конструкции Si (Li=first(Si)), а функция belongsTo (ch, Li) возвращает истинное значение, если символ ch принадлежит соответствующему множеству начальных символов Li и ложное значение в противном случае.

В5. Цикл вида
Рис. 10.  
переводится в оператор

while (belongsTo (ch, L)) T(S);

где T(S) есть отображение S в соответствии с правилами ВЗ-В7, a L есть множество L=first(S) (см. предыдущее примечание).

В6. Элемент графа, обозначающий другой граф А
Рис. 11.  
переводится в оператор обращения к процедуре А.
В7. Элемент графа, обозначающий терминальный символ
Рис. 12.  
переводится в оператор

if(ch == 'x')   
  ch = fgetc(input);
else error (); 

где error() - функция, к которой обращаются при появлении неправильной конструкции.
Теперь покажем применение этих правил на примере преобразования редуцированного графа, изображенного на рис. 7.

char  ch;
void A ()
{
if (ch == 'x') ch = fgetc(input); 
else
  if (ch == '(' )
  {
   ch = fgetc(input);
   A ();
   while (ch == '+' )
   {
    ch = fqetc(input);
    А ( );
   }
   if(ch == '}') ch=fgetc(input);
   else error();
  }
else error();
}

void main(int argc, char **argv) {
ch = fgetc (input); 
/* ... */}

При этом преобразовании свободно применялись некоторые очевидные правила программирования, позволяющие упростить программу. Например, при буквальном переводе четвертая строка имела бы вид:

if (ch == 'x' )
if (ch == 'х') ch = fgetc (input ); else error (); 
else ...

Ясно, что ее можно сократить, как это сделано в программе. Операторы чтения в восьмой и двенадцатой строках тоже получены с помощью такого же упрощения.
Полезно определить, когда вообще возможны подобные упрощения, и показать это непосредственно в виде графов. Два основных случая покрываются следующими дополнительными правилами:

В4а
Рис. 13.  

if (ch == 'xl')
{
  ch = fgetc (input);
  T(S1);
}
else
if (ch == 'x2')
{
  ch = fgetc(input);
  T(S2);
}
else
...
if(ch = 'xn')
{
   ch = fgetc(input);
   T(Sn);
}
else error ( );

B5a
Рис. 14.  

while(ch == 'x')
{
ch = fgetc (input); 
T(S);
}

Кроме того, часто встречающуюся конструкцию

ch = fgetc(input);
T(S);
while(W)
{
ch = fgetc(input);
Т(S);
}

можно выразить короче:

do {
   ch = fgetc (input};
   Т(S);
} while(W);

Мы намеренно не описываем пока функцию error(). Поскольку сейчас нас интересует лишь, как определить, правильно ли входное предложение, мы можем считать, что эта процедура заканчивает работу программы. Конечно, на практике в случае появления неправильных конструкции нужно использовать более тонкие приемы.

5. Построение таблично-управляемой программы грамматического разбора
Вместо того чтобы для каждого языка составлять специальную программу по правилам, изложенным в предыдущем разделе, можно построить одну, универсальную программу грамматического разбора. Конкретные грамматики задаются этой универсальной программе в виде исходных данных, предшествующих предложениям, которые нужно разобрать. Универсальная программа работает в строгом соответствии с методом простого нисходящего грамматического разбора; поэтому она довольно проста, если основана на детерминированном синтаксическом графе, т. е. если предложения можно анализировать с просмотром вперед на один символ без возврата.
В данном случае грамматика (предположим, что она представлена в виде детерминированного множества синтаксических графов) преобразуется в подходящую структуру данных, а не в структуру программы. Естественный способ представить граф - это ввести узел для каждого символа и связать эти узлы с помощью ссылок. Следовательно, "таблица" - это не просто массив. Узлы этой структуры представляют собой структуры (struct) с объединениями (union). Объединение позволяет идентифицировать тип узла. Первый идентифицируется терминальным символом, который он обозначает (tsym), второй ссылкой на структуру данных, представляющую соответствующий нетерминальный символ (nsym). Оба варианта объединения содержат две ссылки: одна указывает па следующий символ, последователь (suс), а другая связана со списком возможных альтернатив (alt).
Графически узел можно изобразить как
Рис. 15.  
Также нужен элемент, представляющий пустую последовательность, символ "пусто". Мы обозначим его с помощью терминального элемента, называемого empty

struct  node;
typedef node *pointer;
struct node {
pointer suс;
pointer alt;
int isTerminal;
union {
       char tsym;
       hpointer nsym;
};
}

Правила преобразования графов в структурах данных (аналогичны правилам В1-В7)

С1. Свести систему графов к как можно меньшему числу отдельных графов с помощью соответствующих подстановок.
С2. Преобразовать каждый граф в структуру данных согласно правилам СЗ-С5, приведенным ниже.
СЗ. Последовательность элементов (см. рисунок к правилу ВЗ) преобразуется в следующий список узлов:
Рис. 16.  
С4. Список альтернатив (см. рисунок к правилу В4) преобразуется в такую структуру данных:
Рис. 17.  
С5. Цикл (см. рисунок к правилу В5) преобразуется в следующую структуру:
Рис. 18.  
В качестве примера рассмотрим построение структуры данных для сводного синтаксического графа, приведенного выше на рис. 10.2.
Структура данных идентифицируется узлом-заголовком, который содержит имя нетерминального символа (цели), к которому относится структура. Вообще говоря, заголовок не является необходимым, так как можно вместо поля цели указывать непосредственно на "вход" в соответствующую структуру. Однако заголовок можно использовать для хранения выводимого на печать имени структуры:

struct header;
typedef header *hpointer;
struct header {
pointer entry;
char sym;
};

Программа, производящая грамматический разбор предложения, представленного в виде последовательности символов входного файла, состоит из повторяющегося оператора, описывающего переход от одного узла к следующему узлу.
В поле sym для терминального символа помещается сам символ, для нетерминального ссылка на соответствующую структуру. Она оформлена как процедура, задающая интерпретацию графа; если встречается узел, представляющий нетерминальный символ, то интерпретация графа, на который ссылается данный узел, предшествует завершению интерпретации текущего графа. Следовательно, процедура интерпретации вызывается рекурсивно. Если текущий символ (sym) входного файла совпадает с символом в текущем узле структуры данных, то процедура переходит к узлу, на который указывает поле suc, иначе - к узлу, на который указывает поле alt. Полученная структура данных приведена на рис. 12.1.
Рис. 19.  

void parse (hpointer goal, int &match)
{
  pointer s;
  s = goal->entry;
  do
  {
   if (s->isTerminal)
     {
      if (s->tsym == sym)
        {
          match = 1;
          sym = fgetc (input) ;
        }
      else
          match = (s->tsym == empty)? 1 : 0;
    }
   else
      parse(s->nsym, match);
   if(match)
     s = s->suc;
   else
     s=s->alt;
} while (s != NULL);
}

Программа грамматического разбора, приведенная выше, "стремится" к новой подцели G, как только она появляется, не проверяя даже, содержится ли текущий символ входного файла во множестве начальных символов соответствующего графа first(G). Это предполагает, что в синтаксическом графе не должно существовать выбора между несколькими альтернативными нетерминальными элементами. В частности, если какой-либо нетерминальный символ может порождать пустую последовательность, то ни одна из правых частей соответствующих ему порождающих правил не должна начинаться с нетерминального символа.
При такой организации грамматического разбора программа обычно считывает представленную в определенном формате грамматику языка, заполняя при этом соответствующие структуры данных, и только после этого читает текст на разбираемом языке и выполняет его синтаксический анализ.
На основе этой программы грамматического разбора можно построить более сложные таблично-управляемые программы грамматического разбора, которые могут работать с более широкими классами грамматик. Небольшая модификация позволяет также осуществлять и возвраты, но это будет сопровождаться значительной потерей эффективности.

6. Преобразование БНФ в структуры данных, управляющие грамматическим разбором
Транслятор, распознающий порождающие правила БНФ и преобразующий их в какое-то другое представление, как раз служит примером программы, входные данные которой можно рассматривать как предложения, принадлежащие некоторому языку. Действительно, саму БНФ можно считать некоторым языком, имеющим свой собственный синтаксис, который, разумеется, также можно описать с помощью порождающих правил БНФ. Следовательно, его транслятор может служить примером распознавателя, который помимо этого преобразует входные данные, т. е., вообще говоря, является процессором. Поэтому мы будем действовать следующим образом:

Шаг 1. Определим синтаксис метаязыка, называемого РБНФ (расширенной БНФ).
Шаг 2. Построим распознающую программу для РБНФ
Шаг 3. Расширив эту программу, превратим ее в транслятор и объединим с таблично-управляемой программой грамматического разбора.

Пусть метаязык, т. е. язык, на котором пишутся синтаксические правила, описан следующими порождающими правилами:

<правило> ::= <символ> = <выражение>
<выражение> ::= <терм> {<терм>}
<терм> ::= <фактор> {<фактор>} (1.12)
<фактор> ::= <символ> | [<терм>]

Заметим, что в порождающих правилах входного языка используются иные метасимволы, чем в БНФ. Это делается по двум причинам:
  1. В (1.12) нужно отличать символы языка от метасимволов.
  2. Желательно использовать более привычные символы печатающего устройства, в частности использовать один знак (=) вместо (::= ).

Соответствие между обычной БНФ и нашей входной версией показано в табл. 1
Таблица 1    
БНФРБНФ
::==
|,
{[
}]

Кроме того, каждое наше порождающее правило должно заканчиваться точкой. При использовании этого входного языка для описания синтаксиса примера 1 (1.7) мы получаем

A = х, (В).
В = АС.
C=[+A]


Литература
  1. Ammann U. The Method of Structured Programming Applied to the Development of a Compiler. - International Computing Symposium 1973, A Gunther et a!., eds., Amsterdam: North-Holland Publishing Co., 1974, 93-99.
  2. Cohen D. J., Gotlieb С. С. A List Structure Form of Grammars for Syntactic Analysis.- Сотр. Surveys, 2, No. I, 1970, 65-82.
  3. Floyd R. V. The Syntax of Programming Languages - A Survey. - IEEE Trans., EC-13, 1964, 346-353.
  4. Cries D. Compiler Construction for Digital Computers. - New-York: Wiley, 1971. [Имеется перевод: ГРИС Д. Конструирование компиляторов для цифровых вычислительных машин.-М.: Мир, 1975.]
  5. Knuth D. E. Top-down Syntax Analysis. - Ada fnformatica, 1, No. 2, 1971,79-110.
  6. Lewis P. M., STEARNS R. E. Syntax-directed Transduction, /. ACM. 15, No. 3, 1968, 465-488.
  7. Naur P. Report on the Algorithmic Language ALGOL 60. - ACM, 6, No. I, 1963, 1 - 17.
  8. Schorre D. V. META II, A Syntax-oriented Compiler Writing Language. - Proc. ACM Nat I. Conl, 19, 1964, D 1 3. 1 - 11.
  9. Wirth N. The Design of a PASCAL Compiler. -Software -Practice and Experience, 1. No. 4, 1971, 309-333.