Синтаксис отдельных лексем описывается, главным образом, с использованием регулярных грамматик. Для них продукция имеет следующую форму: А→а|Ва или А→а|аВ а – терминальные символы, А,В – нетерминальные
Функционирование сканера базируется на грамматическом описании лексем, в основе построения сканера лежит конечный автомат, соответствующий используемой грамматике. Конечный автомат – математическая машина, которая определяется множеством возможных состояний, множеством возможных переходов между состояниями и множеством возможных символов, управляющих этими переходами.
Геометрическое функционирование конечного автомата можно задать графовой моделью, которая называется диаграммой состояния.
Пример. Синтаксис целых констант представляется:
<целое>::=цифра|<знак>цифра|<целое>цифра
<знак>::= +|-
Для представления грамматики состояния целых констант диаграмма имеет вид:
Вершины соответствуют состояниям автомата и определяются нетерминальными символами. Дуги описывают возможные переходы между состояниями и соответствуют продукции грамматики. Для заданной грамматики определяются следующие лексемы:
1) каждому нетерминальному символу сопоставляется вершина графа с соответствующим именем
2) добавляется дополнительная вершина, соответствующая начальному состоянию автомата с именем Старт
3) каждому правилу вывода следующего вида А→а сопоставляется дуга, связывающая вершины Старт и А, которая помечается терминальным символом а
4) каждой продукции А→Ва сопоставляется дуга , которая также помечается терминальным символом а Распознавание лексем с использованием диаграмм состояний конечного автомата осуществляется следующим образом:
1) исходным состоянием является состояние Старт
2) последовательно сканируются (считываются) символы входной цепочки и в соответствии с очередным считывающимся символом выполняется переход автомата в следующее состояние. Этот переход происходит из текущей вершины в то состояние ( вершину), в которую направлена дуга, помеченная символом, совпадающим со считанным символом входной цепи.
3) Переходы между состояниями продолжаются до остановки автомата, которая происходит в двух случаях:
• Считаны все символы входной цепочки
• Переход в следующее состояние невозможен, т.к. не найдена дуга, помеченная считанным символом.
В итоге лексемы будут распознаны, если работа автомата заканчивается в состоянии, соответствующем начальному символу грамматики. На диаграмме эта вершина выделена
По мере считывания символов входной цепочки фиксируется символ, на котором автомат начинает работу ( выходит из состояния Старт) и на котором заканчивает работу, т.е. останавливается.
Сама лексема состоит из тех считанных символов, начиная с которых автомат вышел из сосояния старт и до символа, на котором автомат завершил работу.
Построим диаграмму состояний для автомата, который распознает лексемы трех типов: целые константы, десятичные константы, идентификаторы
С точки зрения процесса трансляции в целом, сканер может быть реализован в двух вариантах:
1) сканер выполняет полный лексический анализ всей программы и формирует эквивалентную последовательность лексем, которая потом используется на фазе синтаксического анализа
2) сканер выполняется в виде подпрограмм, к которым обращается синтаксический анализатор, когда требуется очередная лексема для грамматического разбора
Применение второго варианта часто является более предпочтительным, т.к. не требуется хранить всю исходную программу, представленную в виде последовательности лексем.
Главная
Каталог файлов
, которая также помечается терминальным символом а
