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

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

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

Заметим, что отмеченные выше обобщения нетривиальны, поскольку, например, метод стека с приоритетами в чистом виде применим лишь в том случае, когда существуют функции операторного предшествования  и , в то время как метод операторного предшествования применим в более общем случае, когда существует лишь матрица операторного предшествования, что не гарантирует, вообще говоря, существования функции операторного предшествования.

Необходимо  также заметить,   что  в   чистом   виде   метод   стека с приоритетами неприменим к языкам типа Алгол-60. Чтобы «подогнать»  этот  метод для  трансляции  условных  операторов  и  операторов цикла, приходится вводить дополнительные переменные состояния и другие уточнения общего алгоритма. Аналогичные  замечания   можно  сделать  и  в  отношении   всех   методов предшествования: некоторые особенности реального входного языка   почти  всегда   приходится  учитывать  в  семантических  подпрограммах.

Сравнительная оценка методов основанных на предшествовании

Основное достоинство  методов,  основанных  на   предшествовании, простота алгоритмов распознавателя. Другое важное преимущество—наличие общих алгоритмов, позволяющих:

проверить, является ли грамматика грамматикой предшествования (или расширенного предшествования, или операторного предшествования);

отыскать   отношения   предшествования   (операторного   предшествования);

вычислить  значения   функций   предшествования   (операторного предшествования), если они существуют;

построить таблицы правых и левых троек для метода расширенного предшествования.

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

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

В языках типа Алгол-60, Фортран, Кобол, ПЛ/1 число порождающих правил колеблется от 200 до 1000. Например, в эталонном Алголе-60 насчитывается 369 правил. Даже после исключения правил, которые не используются в реальных входных языках, в Алголе-60 остается 200—300 правил. Следовательно, таблица порождающих правил реального языка высокого уровня может быть достаточно велика. Таблица большого объема, с одной стороны, занимает много места в памяти, а с другой стороны, замедляет трансляцию за счет дополнительных операций поиска правила для редукции. Например, даже при двоичном поиске правила в таблице для Алгола-60 требуется не менее 9 сравнений (20—30 машинных операций). Относительно большой объем таблиц — недостаток всех методов, основанных на предшествовании.