Диаграммы переходов

Пример 6

Распознавание лексем и регулярные выражения

Рассмотрим пример языка, порождаемого следующей грамматикой.

Рассмотрим следующий фрагмент грамматики:

stmt	→	if expr then stmt
	│	if expr then stmt else stmt
	│	λ
expr	→	term relop term
	│	term
term	→	id

где терминалы if, then, else, relop, id и num порождают множество строк, задаваемых следующими регулярными определениями:

if→	if
then→	then
else→	else
relop→	< │ <= │ = │ <> │ > │ >=
id→	letter (letter │ digit) *

где letter и digit определены так же, как и ранее.

Для этого фрагмента языка лексический анализатор будет распознавать ключевые слова if,then,else,а также лексемы, обозначенные relop, id. Для простоты считаем, что ключевые слова зарезервированы и, таким образом, не могут использоваться в качестве идентификаторов.

Цель – построение лексического анализатора, который сможет выделять из входного очередную лексему и, используя таблицу трансляции на рис. 8, выдавать пары, состоящие из значения лексемы и атрибута-значения. Атрибут-значение для операторов отношения определяется символическими константами LT,LE,EQ,NE,GT,GE.

Регулярное выражение	Лексема	Атрибут-значение
ws	–	–
if	if	–
then	then	–
else	else	–
Id	id	указатель на запись в таблице
num	num	указатель на запись в таблице
<	relop	LT
<=	relop	LE
=	relop	EQ
<>	relop	NE
>	relop	GT
>=	relop	GE

Рис. 8. Шаблоны регулярных выражений для лексем

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

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

На рис. 9 показана диаграмма переходов для шаблонов >= и >. Диаграмма работает следующим образом. Работа начинается в состоянии 0, в котором считывается следующий символ из входного потока. Дуга, помеченная >, ведет в состояние 6, если этот символ – “>”. В противном случае мы не можем распознать > или >=.

Рис. 9. Диаграмма перехода для >=

По достижении состояния 6 считываем следующий входной символ. Дуга, помеченная как =, приводит из состояния 6 в состояние 7, если считанный символ – “=”. В противном случае по дуге other попадаем в состояние 8. Двойной кружок, который изображает состояние 7, показывает, что это – заключительное состояние, в котором найдена лексема >=.

Символ > с другим дополнительным символом приводит в другое допускаемое состояние 8. Поскольку этот другой символ не является частью лексемы, он должен быть возвращен во входной поток, что и указано звёздочкой около этого состояния.

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

Дата добавления: 2014-12-27