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

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

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

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

<идентификатор переменной>:: =<идентификатор>,

<идентификатор массива>::=<идентификатор>,

<идентификатор процедуры>::=<идентификатор>.

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

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

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

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

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

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

Литература:

Лебедев В.Н. «Введение в системы программирования» - Москва, 1985

Ахо А.,Ульман Дж.  «Компиляторы : Технологии и инструменты» Москва ,2001