Программное обеспечение ЭВМ. Методы трансляции

Ведение

Вниманию читателей предлагается вторая часть конспекта лекций по курсу "Программное обеспечение ЭВМ. Методы трансляции."

В пособии излагаются классические табличные методы восходящего анализа (методы, основанные на предшествовании, LR- методы), а также приводится краткая характеристика  систем построения трансляторов.

1. ВОСХОДЯЩИЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ.

Рассмотрение восходящих методов синтаксического анализа начнем с наиболее простых – методов, основанных на пред-шествовании. Изложение материала базируется на книгах [4, 5].

1.1. Методы, основанные на предшествовании.

В пособии рассмотрим три табличных метода синтаксического анализа, основанные на предшествовании: метод (простого) предшествования, метод расширенного предшествования и метод операторного предшествования.

1.1.1. Отношения предшествования.

Рассмотрим схемы разбора, в которых применяется восходящий метод.

Пусть  – грамматика,  – сентенциальная форма. Тогда  называется фразой сентенциальной формы  для нетерминального символа , если  и ; и называется простой фразой, если  и .

При использовании восходящего метода в текущей сентенциальной форме повторяется поиск основы (самой левой простой фразы u), которая в соответствии с правилом  приводится к нетерминалу . При применении любого из методов разбора возникает вопрос, как найти основу и к какому нетерминалу ее приводить? Этот вопрос будем решать для определенного класса грамматик, называемых грамматиками, основанными на предшествовании [3,5].

Обобщая ранние работы по синтаксическому анализу, Вирт и Вебер предложили метод предшествования, основанный на том факте, что между любыми двумя соседними символами  и  приводимой строки может существовать лишь три отношения:

1) , если символ  самый левый символ некоторой основы:

2)  , если  – самый правый символ основы:

3) , если символы  и  принадлежат одной основе:

Отношения  ,  ,  называют отношениями предшествования.

Отношения предшествования зависят от порядка, в котором стоят символы и из  отнюдь не следует , а из  вовсе не вытекает .

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

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

                                        (1)

Тогда символы  образуют основу. Следовательно, по определению (основа – самая левая непосредственно приводимая фраза) должно существовать правило вида .

Пусть прямая редукция строки (1), выполненная в соответствии с этим правилом, приводит к строке с отношениями предшествования

                                                         (2)

Следовательно, существует правило вида .

Пусть применение этого правила дает строку с отношениями предшествования

                                                                 (3)

Из (3) следует правило  , поэтому (3) приводится к строке .

Если существует правило <начальный символ>®, то прямая редукция  к <начальный символ> завершает анализ. Разбор получен.

1.1.2. Грамматика простого предшествования.

Пусть , ,  – нетерминальные символы,  ,  , , , – любые строки, возможно пустые. Грамматикой простого предшествования называют такую грамматику типа 2 по Хомскому, в которой:

1) для каждой упорядоченной пары терминальных и нетерминальных символов выполняется не более чем одно из трех отношений предшествования, определяемых следующим образом:

А. , если и только если существует правило .

Б. , если и только если существует правило  и вывод .

В. , если и только если существует правило  и вывод  или правило  и выводы , .

2) разные порождающие правила имеют различные правые части.

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

Второе условие обеспечивает однозначность редукции.

1.1.3. Распознаватель, основанный на простом предшествовании.

Основную идею алгоритма разбора, основанного на отношениях предшествования, можно описать так. Символы входной строки поочередно переписываются в стек до тех пор, пока между символом в вершине стека (обозначим его ) и очередным символом входной строки (обозначим его ) не появится отношение , т. е. окажется, что . Тогда стек просматривается в направлении от вершины к началу до тех пор, пока между двумя очередными символами  и  не появится отношение  , т.е. .

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