Методы трансляции.Грамматика.Распознаватель, страница 3

2.3. По правилу (8) с использованием табл. 2 определяются отношения ·>.

Полученная матрица отношений операторного предшествования приведена в табл. 3.

Таблица 3:

Матрица операторного предшествования для грамматики G₁

Особенности транслятора

Общая структура транслятора для языка, порожденного грамматикой с операторным предшествованием, не отличается от структуры транслятора для грамматики предшествования. Лексический анализатор тот же. Распознаватель также использует таблицу порождающих правил, а вместо матрицы предшествования - матрицу операторного предшествования или функции операторного предшествования. Генератор содержит набор семантических подпрограмм.

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

Фактически распознаватель для грамматики с операторным предшествованием без помощи семантических подпрограмм не может найти полный разбор входной строки. Он отыскивает лишь «сокращенный» разбор, в котором отсутствуют элементы, отличающиеся только нетерминальными символами. Следовательно, этот распознаватель без привлечения семантических подпрограмм не способен выполнить полный синтаксический контроль. Это делает метод операторного предшествования менее надежным, чем метод предшествования. Однако неполнота разбора имеет определенное преимущество: сокращаются объем таблицы порождающих правил и число шагов трансляции, поскольку из разбора исключены шаги, редуцирующие части строки, состоящие только из нетерминальных символов.

В качестве примера в табл. 4 представлена таблица порождающих правил распознавателя применительно к грамматике G₁. В таблицу не включены правила грамматики G₁, содержащие в правых частях только нетерминальные символы (правила BT и TM), а в правых частях всех остальных правил нетерминальные символы заменены символами N. Кроме того, таблица дополнена семантическими подпрограммами для перевода арифметических выражений в обратную польскую запись.

Таблица 4:

Таблица порождающих правил грамматики G₁