Синтаксический анализ. Программное моделирование конечных преобразователей

Программное моделирование конечных преобразователей

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

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

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

Пример:

Решение:

Для объединенного автомата из предыдущего примера дадим программную реализацию

Добавить программную реализацию в псевдокоде для конечных преобразователей в двух вариантах: 1) кодирование функций переходов; 2) завести кусок кода для каждого состояния

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

Дата добавления: 2014-01-07