Если U Ï Dstates

то Dstates: =Dstates+U;

Dtrans[T, a]: =U;

end;

end;

Рассмотрим преобразование недетерминированного автомата с рисунка 11 к детерминированному.

Определим eclosure(S₀). Через e-переходы из нулевого стартового состояния можно попасть в состояния 1, 2, 5, 9. Таким образом, в Dstates заносим множество {0, 1, 2, 5, 9}.

На первой итерации цикла помечаем множество T={0, 1, 2, 5, 9}.

Для входного символа " точка" U={3}, так как по этому символу из состояний множества {0, 1, 2, 5, 9} можно перейти только в третье состояние, а из него e-переходов нет. Dstates={{0, 1, 2, 5, 9}^', {3}}. Помещаем множество {3} в таблицу переходов в качестве нового состояния при текущем состоянии {0, 1, 2, 5, 9} и входном символе “точка”, то есть Dtrans[{0, 1, 2, 5, 9}, точка]: ={3}. Для входного сигнала " тире" U={6}. Для символа " пробел" U={10}. После первой итерации внешнего цикла конечный автомат имеет вид Dstates={{0, 1, 2, 5, 9}^', {3}, {6}, {10}}, Dtrans =

На второй итерации рассматриваем Т={3}, так как это первое непомеченное состояние в Dstate. Из этого множества возможен переход только по символу " пробел" в состояние 4. Из состояния 4 существуют e-переходы в состояния 8, 9, 1, 2, 5. После выполнения второй итерации автомат имеет вид. Dstate={{0, 1, 2, 5, 9}^', {3}^', {6}, {10}, {4, 8, 9, 1, 2, 5}}, Dtrans=

Рассмотрение множества {6} добавит в автомат множество {7, 8, 9, 1, 2, 5} и соответствующий переход. Из множества {10} нет никаких переходов, так как оно конечное, поэтому четвертая итерация цикла ничего к графу не добавит. После этого конечный автомат будет иметь вид

Dstates={{0, 1, 2, 5, 9}^', {3}^', {6}^', {10}^', {4, 8, 9, 1, 2, 5}, {7, 8, 9, 1, 2, 5}}

Dtrans=

Из множества {4, 8, 9, 1, 2, 5} по символу " пробел" можно перейти в множество {10}, по символу " тире" – в множество {6}, а по символу " точка" – в состояние {3}. Таким образом, рассмотрение множества {4, 8, 9, 1, 2, 5} не приведет к добавлению к автомату новых состояний, но добавит соответствующие переходы. Аналогичные рассуждения можно провести для множества {7, 8, 9, 1, 2, 5}. После рассмотрения этих двух состояний в Dstates не останется непомеченных множеств, следовательно, алгоритм завершит работу. При этом Dtrans имеет вид

Таким образом, конечный автомат будет иметь вид, представленный на рисунке 12.

Рисунок 12. – Детерминированный конечный автомат

3.2.4 Минимизация конечного автомата

При минимизации конечного автомата все состояния делятся на две группы: финальные и нефинальные. Затем выполняется следующая процедура. Рассматриваем группу {S1, S2, …, Sk} и некоторый входной символ а. Если по этому входному символу есть переходы в разные группы, то исходную группу разбивают на части. Принадлежность Si к той или иной части зависит от того, в какую группу существует переход из состояния Si по входному символу а. Эта процедура продолжается до тех пор, пока не останется ни одной группы, которую можно было бы разбить по какому-либо входному сигналу.

Минимизируем конечный автомат, приведенный на рисунке 12. Разбиваем все состояния на две группы. В первую войдет конечное состояние S5, а во вторую все неконечные состояния, то есть группа имеет вид {S0, S1, S2, S3, S4}.

Первую группу разделить не возможно, так как она состоит из единственного состояния. Рассмотрим входной сигнал “точка” и вторую группу. По этому входному символу есть переходы только из состояний S0, S3, S4 в состояние S1, то есть для всех состояний группы по входному символу “точка” осуществляется переход в одну и ту же группу. Следовательно, входной сигнал “точка” не разбивает группу. Аналогичные рассуждения можно провести и для входного сигнала “тире”. Теперь рассмотрим входной символ “пробел”. По этому сигналу из состояний S1 и S2 осуществляется переход в состояния той же группы, а из состояний S0, S3, S4 – в состояние S5, то есть в другую группу. Таким образом, группу {S0, S1, S2, S3, S4} делим на две {S0, S3, S4} и {S1, S2}. Разбить получившиеся группы нельзя ни по какому входному сигналу. Таким образом, минимизированный конечный автомат будет иметь три состояния. Рассмотрим переходы между состояниями. Как видно по рисунку 12 из множества состояний {S0, S3, S4} существует переход в множество состояний {S1, S2} по символам “точка” и “тире”, а по символу “пробел” - переход в множество {S5}. Из множества {S1, S2} можно выполнить переход в множество состояний {S0, S3, S4} по символу “пробел”. Из состояния S5 переходов нет. Минимизированный конечный автомат для распознавания буквы азбуки Морзе представлен на рисунке 13.

Рисунок 13. – Минимизированный конечный автомат

3.2.5 Конечный автомат для распознавания нескольких лексем

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

Пусть язык включает два класса лесем.

Первый описывается регулярным выражением (цифра)+пробел. Для распознавания этой лексемы построен конечный автомат, приведенный на рисунке14.

Рисунок 14. – Автомат для распознавания лексемы (цифра)⁺пробел

Второй класс лексем описывается выражением букава (цифра)* пробел и распознается автоматом, представленным на рисунке 15.

Рисунок 15. – Автомат для распознавания лексемы буква(цифра)^*пробел

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

Рисунок 16

3.2.6 Распознавание ключевых слов

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

Рассмотрим, как распознать язык, состоящий либо из идентификатора, заканчивающегося пробелом, либо из служебного слова if, за которым также следует пробел. Для этого в качестве входных символов необходимо отдельно выделить символ “i”, символ “f”, все символы без “i” и “f”, а также символ “пробел”. Детерминированный автомат для такого языка представлен на рисунке 17.

Рисунок 17

В приведенном автомате финальное состояние 3 соответствует распознанной лексеме класса “служебное слово”, а финальное состояние 5 – лексеме класса “идентификатор”.

Этот же язык может распознаваться с использованием недетерминированного автомата. Тогда из состояния 0 в состояние 4 можно попасть еще и по входному символу “i”. Кроме того, будет отсутствовать переход из состояния 2 в состояние 4. Работать этот автомат будет так. Если пришел сигнал “i”, то автомат перейдет в состояние 1. Если в состоянии 1 или 2 на входе автомата появиться неожидаемый сигнал, то произойдет откат до состояния 0 и работа автомата продолжится переходом в состояние 4.

Второй вариант распознавания ключевых слов не подразумевает построения специальных автоматов для ключевых слов. В этом случае анализатор должен иметь таблицу, содержащую ключевые слова языка. После распознавания идентификатора лексический анализатор сравнивает значение лексемы с элементами таблицы ключевых слов. Если было найдено совпадение, то лексема относится к классу “ключевое слово”, иначе – к классу “идентификатор”.

3.3 Реализация лексического анализатора в виде конечного автомата

Рассмотрим реализацию в виде конечного автомата лексического анализатора построенного ранее.

Определим тип “входной сигнал”. Этот тип должен включать нижеприведенные элементы.

- “Точка” (dot), “тире” (dash) и “пробел” (space) для отражения входных сигналов конечного автомата.

- “Другой символ” (other). Этот элемент необходим для отражения всех символов, не входящих в алфавит азбуки Морзе, но появляющихся на входе конечного автомата.

- “Конец последовательности” (endf). Этот элемент необходим, так как автомат должен знать, когда заканчивается последовательность, которую нужно распознать как букву или как ошибочную последовательность.

type input_signal = (dot, dash, space, other, endf)

Определяем возможные состояния конечного автомата. Согласно графу это будут состояния S0, S1, S2, а также специальное состояние S_error, которое будет соответствовать ошибке, возникшей при разборе.

type state = (S0, S1, S2, S_error)

Исходя из рисунка 13, определим функцию переходов конечного автомата. В ошибочное состояние автомат переводит любой, неожидаемый сигнал. Сигнал “Другой символ” переводит автомат в ошибочное состояние из любого состояния автомата.

const next_state: array [dot..other, S0..S1] of state =

((S1, S_error), (S1, S_error), (S2, S0), (S_error, S_error));

В рассматриваемом примере только один класс лексем, но обычно автомат распознает лексемы нескольких классов, поэтому введем тип “класс лексемы”. В данной реализации этот тип будет включать только одно значение - “буква”.

type lexeme_class=(letter)

Реализуем работу конечного автомата, считая что глобальная переменная Entry: string содержит входную последовательность. Переменные cur_state и cur_input необходимы для хранения текущего состояния автомата и входного символа. Глобальная переменная lex_val будет содержать значение распознаваемой лексемы. В начале работы автомата эта переменная инициализируется пустой строкой, а формирование значение лексемы будет производиться при распознавании символа входной последовательности. Приведенная ниже функция возвращает класс распознанной лексемы. Работа функции заключается в переходе по состояниям конечного автомата до тех пор, пока не будет достигнуто конечное состояние или входная последовательность не разобрана полностью. Если автомат перешел в ошибочное состояние, то в системе возникает исключительная ситуация и пользователь получает сообщение об ошибке. Такое же сообщение пользователь получит, если просмотрена вся входная последовательность, а автомат не находится в конечном состоянии.

function state_machine: lexeme_class;

var cur_state: state; cur_input: input_signal;

begin

lex_val: =''; cur_state: =s0; cur_input: =recognize;

while (cur_state< > S2) and (cur_input< > endf) do

begin

cur_state: =next_state[cur_input, cur_state];

if cur_state=S_error

then raise exception.create(‘Лексическая ошибка');

if cur_state< > s2 then cur_input: =recognize;

end;

if (cur_state < > S2) and (cur_input=endf)

then raise exception.create('Лексическая ошибка')

else result: =letter;

end;

При реализации конечного автомата была использована функция recognize, которая возвращает следующий символ входной последовательности. Эта функция необходима, так как последовательность имеет строковый тип, а для входных символов автомата задан свой тип input_signal. Кроме того, функция формирует значение лексемы.

function recognize: input_signal;

begin

if entry=''

then result: =endf

else

begin

case entry[1] of

'.': result: =dot;

'-': result: =dash;

' ': result: =space;

else result: =other

end;

lex_val: =lex_val+entry[1];

entry: =copy(entry, 2, length(entry));

end;

end;

Теперь рассмотрим текст основной программы. Она будет состоять в вызове подпрограммы лексического анализатора до тех пор, пока не будет разобрана вся входная последовательность. В зависимости от класса распознанной лексемы основная программа выдает пользователю сообщение, включающее класс и значение лексемы. Будем считать, что входная последовательность вводится пользователем через объект класса TEdit.

begin

entry: =edit1.text;

while (entry< > '') do

begin

case state_machine of

letter: showmessage('Буква'+lex_val);

end;

end;

end;

3.4 Контрольные вопросы

1 В чем состоит основная задача лексического анализа?

2 Какую информацию должен выдавать лексический анализатор?

3 Что такое ключевые слова и как они выделяются из входной последовательности?

4 Что такое регулярное выражение?

5 Каким образом описывается конечный автомат?

6 Чем определяется и в чем состоит шаг работы конечного автомата?

7 Каким образом можно преобразовать к недетерминированному конечному автомату регулярные выражения r+ и r?.

3.5 Задание

Создать лексический анализатор, выделяющий из входной последовательности следующие лексемы:

- " идентификатор" - последовательность букв и цифр, начинающаяся с буквы;

- " число" - последовательность цифр, целая часть от дробной отделяется точкой или запятой, причем дробная часть может отсутствовать;

- " присвоение" - строка ": =";

- " знак операции" - символы + или –;

- ключевые слова begin и end.

Лексемы отделяются друг от друга пробелом или начинаются с новой строки.

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

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

Пример

входная последовательность

3434334 eree wew3

3434.4 +: =

Результат

число 3434334

идентификатор eree

идентификатор wew3

число 3434.4

знак +

присвоение: =

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

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

3.6 Содержание отчета

Отчет должен содержать:

- Регулярные выражения, описывающие распознаваемые лексемы.

- Недетерминированный, детерминированный и минимизированный автоматы для распознавания лексемы “число”.

- Конечный автомат для распознавания всех лексем, перечисленных в задании.

3.7 Защита лабораторной работы

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

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

4. Лабораторная работа №2 “Построение лексического анализатора с использованием генератора лексических анализаторов Lex”

4.1 Цель работы

Целью выполнения лабораторной работы является:

- закрепление навыков описания лексем с использованием регулярных выражений;

- знакомство с генератором лексических анализаторов Lex.

4.2 Общие сведения о генераторе лексических анализаторов Lex

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

Исходный текст для Lex создается в текстовом редакторе, например в блокноте, и сохраняется в файле с расширением l. Программа lex.exe, в –качестве параметра которой выступает исходный файл с расширением l, строит лексический анализатор на Pascal(то есть файла с расширением pas). Lex создает анализатор на основе кода, содержащегося в файле Yylex.cod, поэтому этот файл должен находиться в том же каталоге, что и файл lex.exe. Если исходный текст содержит ошибки, то при попытке построить лексический анализатор создаться файл ошибок с расширением lst.

Полученный в результате работы Lex модуль присоединяется к проекту Delphi, который будет содержать основной текст программы. Для корректной работы с проектом, он должен подключать библиотеку lexlib.pas.

4.3 Lex-программа

Текст Lex-программы может включать регулярные выражения, операторы и функции Pascal, а также переменные и функции, объявленные и реализованные в библиотеке lexlib.pas.

4.3.1 Регулярные выражения

Lex позволяет использовать регулярные выражения, приведенные в таблице 2.

Таблица 2. – Регулярные выражения, используемые в Lex

4.3.2 Разделы Lex-программы

Исходный текст программы Lex может состоять из трех разделов, разделенных %%.

раздел определений

%%

раздел правил

%%

Пользовательский раздел

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

Радел правил Lex-программы имеет вид

p1 {действие 1}

p2 {действие 2}

…

pn {действие n}

Каждое pi – регулярное выражение, а каждое i-ое действие – фрагмент программы, описывающий, какое действие должен сделать лексический анализатор, когда образец pi сопоставляется лексеме. Действие включает код на Pascal, включая функции, определенные в Lexlib.pas.

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

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

4.3.3 Функции и переменные, используемые при работе с

Lex-анализатором.

Lex преобразует текст исходного файла в функцию yylex: integer. Вызов этой функции приводит к запуску лексического анализатора, обрабатывающего остаток входной последовательности. Значение, возвращаемое функцией, соответствует классу распознанной лексемы. Функция yylex возвращает значение в том случае, если действие, соответствующее регулярному выражению, включает передачу управления основной программе. Передать управление можно, используя функции returni(< значение: integer>) и returnc(< значение: char>). Эти функции реализованы в lexlib.pas. Обе они прекращают лексический разбор и передают управление основной программе, но первая возвращает значение, указанное в качестве параметра, а вторая код символа, указанного в качестве параметра. Значения, возвращаемые функциями returni и returnc, должны быть расценены главной программой как класс распознанной лексемы. В качестве параметра функции return(i) может выступать константа. Использование констант в качестве возвращаемого параметра позволяет сделать код основной программы удобочитаемым. Обычно константы начинают задавать с 257, так как все предыдущие значения могут быть использованы при передачи кодов символов. Если входная последовательность пуста, то функция yylex всегда выдает значение 0.

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

Перед вызовом функции yylex для новой входной последовательности необходимо вызвать функцию yyclear, которая приводит конечный автомат лексического анализатора в начальное состояние. Кроме того, нужно вызвать функцию yyMemoInit. В качестве параметров эта функция должна получить четыре объекта класс TMemo. Первый объект предназначен для ввода пользователем входной последовательности. Второй – выводит фрагменты входной последовательности, которые не были распознаны в качестве лексемы какого-либо класса. Третий – для вывода сообщений об ошибках. Четвертый – для формирования отчета о работе анализатора. Последний объект будет использоваться в синтаксическом анализаторе, выполненном в генераторе Yacc. Для указания строки во входном Memo с которой должен начаться разбор используется переменная yylineno: integer.

Кроме класса лексемы лексический анализатор должен возвратить значение лексемы. Для этой цели используется переменная yytext: string[255]. Заметим, что при работе со строковыми типами в Lex необходимо четко задавать их длину. Например, нельзя объявить константу типа string, но можно типа string[20].

4.4 Работа анализатора, построенного с помощью генератора Lex

Лексический анализатор, сгенерированный Lex, взаимодействует с основной программой следующим образом. При вызове его основной программой лексический анализатор посимвольно читает остаток входной последовательности, пока не находит самый длинный префикс, который может быть сопоставлен одному из регулярных выражений pi. Если несколько регулярных выражений соответствуют входной последовательности, то выбирается первый найденный в Lex-программе. Затем выполняется действие i. Как правило, действие i возвращает управление основной программе. Если это не так, то продолжается разбор до тех пор, пока очередное действие не вернет управление основной программе.

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

4.5 Пример построения лексического анализатора с использованием Lex.

Рассмотрим Lex-программу, распознающую целые числа и идентификаторы. Целое число представляет собой последовательность символов, состоящую из одной и более цифр. Идентификатор – это последовательность букв и цифр, начинающаяся с буквы. Кроме того, лексический анализатор должен распознавать символ “+”.

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

Лексический анализатор будет возвращать лексемы трех классов. Для классов “идентификатор” и “число” зададим константы. При получении на входе символа “+” Lex будет возвращать код этого символа. Определим еще одну константу, которую лексический анализатор будет возвращать, если на входе получен какой-либо символ, не соответствующий ни одной лексеме. Анализатор, построенный Lex, использует функции и переменные, реализованные в Lexlib.pas, поэтому необходимо подключить соответствующий модуль. Кроме того, в разделе определений опишем две подстановки “цифра” и буква. Цифра это любой символ от “0” до “9”. Цифра – это любой строчный или прописной символ от “a” до “z”. Заметим, что все строки, которые должны быть перенесены в лексический анализатор без изменений, начинаются не с начала строки.

unit Simple;

interface

const num=257; id=258; lex_error=313;

function yylex: Integer;

implementation

uses lexlib;

D [0-9]

L [a-zA-Z]

%%

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

{D}+ returni(num);

{L}({L}|{D})* returni(id);

\+ returnc(‘+’);

" ";

. returni(lex_error);

%%

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

end.

Текст основной программы приведен ниже. Объект Memo3 класса TMemo выступает в качестве служебного, а Memo2 предназначен для отражения результатов лексического разбора.

var i: integer;

begin

yyclear;

yymemoinit(memo1, memo2, memo3, memo4);

yylineno: =0;

repeat

i: =yylex;

case i of

num: memo2.lines.add('число '+yytext);

id: memo2.lines.add('идентификатор '+yytext);

ord('+'): memo2.lines.add('знак '+yytext);

lex_error: raise exception.Create('Лексическая ошибка')

end;

until i=0;

end;

4.6 Контрольные вопросы

1 Какие разделы выделяются в Lex-программе и каково их назначение?

2 При помощи чего лексический анализатор передает управление основной программе?

3 Каково назначение переменной yytext?

4 Каким образом лексический анализатор, сгенерированный Lex, взаимодействует с основной программой?

5 Каковы особенности конечного автомата, построенного генератором лексических анализаторов Lex?

4.7 Задание

Написать лексический анализатор, распознающий лексемы:

- “Идентификатор” – последовательность букв и цифр, начинающаяся с буквы, в последовательности могут встречаться как строчные, так и заглавные буквы.

- “Целое число” – последовательность цифр.

- “Десятичное” – последовательность цифр, в которой целая часть отделяется от дробной запятой или точкой.

- “Присваивание” –: =

- “Знак операции” – +, -, *, /

- “Служебное слово var”

- “Служебное слово if”

- “Служебное слово then”

- “Служебное слово else”

- “Служебное слово begin”

- “Служебное слово end”

- “Логическая операция” - or или and

- “Знак сравнения” - < > =

- “Разделитель команд” -;

- “Операция округления” - round

- “Двоеточие” -:

- “Открытая скобка” - (

- “Закрытая скобка” -)

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

4.8 Защита лабораторной работы

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

5 Лабораторная работа № 3. “Использование метода рекурсивного спуска для построения синтаксического анализатора”

5.1 Цель работы

Целью выполнения лабораторной работы является

- получение навыков описания языка с использованием контекстно-свободных грамматик;

- изучение метода рекурсивного спуска.

5.2 Общие сведения

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

В самом общем виде контекстно-свободная грамматика описывает язык как множество строк, полученных применением конечного множества продукций. Формально контекстно-свободная грамматика это четверка < V, å, P, S>. Рассмотрим составляющие контекстно-свободной грамматики. V – это конечное множество всех грамматических символов. å - множество терминальных символов, причем å является подмножеством V. Терминальные символы в грамматике будем обозначать строчными буквами. Множество нетерминальных символов N=V-å. Нетерминальные символы в грамматике будем обозначать заглавными буквами. S – стартовый нетерминал. P – множество правил вывода. PÍ NxV*, то есть продукция – это последовательность, начинающаяся с нетерминального символа (левая часть правила), за которым следует замыкание Клини терминальных и нетерминальных символов (правая часть правила).

Рассмотрим пример грамматики, описывающей арифметические действия.

1. GOALà EXPR

2. EXPRà EXPR+TERM

3. EXPRà EXPR-TERM

4. EXPRà TERM

5. TERMà TERM*FACTOR

6. TERMà TERM/FACTOR

7. TERMà FACTOR

8. FACTORà num

9. FACTORà id

Рисунок 18. – Грамматика языка арифметических действий

В данном примере стартовым является нетерминал GOAL, так как он не встречается в правой части ни одной продукции. å ={+, -, *, /, num, id}; N={GOAL, EXPR, TERM, FACTOR}. Любая из продукций состоит из нетерминала в левой части и последовательности терминалов и нетерминалов в правой. Например, правило 2 утверждает, что EXPR есть последовательность из нетерминала EXPR, терминала + и нетеминала TERM.

Будем говорить, что agb выводимо за один шаг из aАb (agb=> aАb), если в грамматике существует правило вывода Aà g, а a и b - произвольные строки из V. Если u1=> u2=> …=> un, то можно утверждать, что u1 выводится из un за 0 или более шагов (u1=> *un). Если un нельзя вывести из u1 за 0 шагов, то говорят, что un выводимо из u1 за 1 или более шагов(u1=> +un).

Различают два вида вывода: левый и правый. Если на каждом шаге заменяют самый левый нетерминальный символ, то вывод называется левым, если самый правый, то вывод – правый.

Если дана грамматика G со стартовым символом S, то используя отношение => +, можно определить язык L(G), порожденный грамматикой G. Строки такого языка могут содержать только терминальные символы из G. Строка терминалов w принадлежит L(G) тогда и только тогда, когда w выводимо из S за 1 или более шагов S=> +w.

Таким образом, приведенная ранее грамматика описывает язык арифметических операций. При этом строки этого языка могут содержать только терминалы +, -, *, /, num, id. Пусть есть строка “id*id+num”. Рассмотрим, принадлежит ли эта строка языку арифметических операций. Для этого проверим, можно ли вывести входную строку из стартового символа. В скобках после знака => будем указывать номер продукции, по которой осуществляется вывод.

GOAL=> (1) EXPR=> (2) EXPR+TERM=> (4) TERM+TERM=> (5)

TERM*FACTOR+TERM=> (7) FACTOR*FACTOR+TERM=> (9)

id*FACTOR+TERM=> (9) id*id+TERM=> (7) id*id+FACTOR=> (8)

id*id+num

Получили входную строку, следовательно, строка “id*id+num” принадлежит языку. Заметим, что был использован левый вывод.

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

- корень дерева помечен стартовым символом

- каждый лист помечен терминалом или e

- каждая внутренняя вершина помечена нетерминалом

- если N – нетерминал, которым помечена внутренняя вершина и X1, X2, …, Xn – метки ее прямых потомков в указанном порядке, то правило Nà X1 X2 … Xn существует в грамматике.

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

Для рассмотренного ранее примера дерево вывода представлено на рисунке 19.

Рисунок 19- Дерево разбора для последовательности “x*y+5”.

5.3 Рекурсивный спуск

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

Процедура рекурсивного разбора сверху вниз состоит из следующих шагов:

- Для узла дерева, помеченного, как нетерминал А, выбирают одну из продукций вида Aà a. После этого строим от А ветви, соответствующие a.

- Если в процессе применения продукций получено обрамление, несоответствующее входной последовательности, то производится откат.

- Находим следующий узел, помеченный нетерминалом, для подстановки правила.

При таком подходе может возникнуть проблема бесконечного цикла. В грамматике для арифметических операций применение второго правила приведет к зацикливанию процедуры разбора. Подобные грамматики называются леворекурсивными. Грамматика называется леворекурсивной, если в ней существует нетерминал А, для которого существует вывод А=> +Аa. В простых случаях левая рекурсия вызвана правилами вида

Aà Aa|b

В этом случае вводят новый нетерминал и исходные правила заменяют следующими.

Aà bB

Bà aB|e

Рассмотрим правила 2 и 4 грамматики с рисунка 18. Правило 2 делает грамматику леворекурсивной. Воспользуемся вышеизложенным приемом исключения левой рекурсии. a=+Т, b=Т. Введем новый нетеримнал EXPR1 и получим новые продукции. ЕXPRà TERM EXPR1; EXPR1à +TERM EXPR1; EXPR1à e.

На рисунке 16 изображена грамматика, к которой была преобразована грамматика с рисунка 14 путем исключения левой рекурсии.

1. GOALà EXPR

2. EXPRà TERM EXPR1

3. EXPR1à +TERM EXPR1

4. EXPR1à -TERM EXPR1

5. EXPR1à e

6. TERMà FACTOR TERM1

7. TERM1à *FACTOR TERM1

8. TERM1à /FACTOR TERM1

9. TERM1à e

10. FACTORà num

11. FACTORà id

Рисунок 20 Грамматика языка арифметических выражений, из которой исключена левая рекурсия.

Применение рекурсивного спуска в вышеизложенном виде может работать очень длительное время за счет откатов. Поэтому важно найти такой алгоритм, который мог бы однозначно выбирать продукцию на каждом шаге. Есть разновидность грамматик, которые при разборе сверху вниз позволяют выбирать продукцию на основе первых k символов входной последовательности. Будем использовать LL(1)-грамматики, которые позволяют выбирать продукцию на основе первого символа входной последовательности. Первое L означает, что сканирование осуществляется слева на право, второе L, что строиться левый вывод.

Грамматика, приведенная на рисунке 16, является LL(1), так как при выборе правила для любого нетерминала достаточно проанализировать первый символ входной последовательности.

5.4 Пример реализации метода рекурсивного спуска

Реализуем грамматику, приведенную на рисунке 16. Будем считать, что уже написан лексический анализатор, который возвращает константы num и id при появлении на входе соответствующих терминалов. Для остальных терминалов, лексический анализатор возвращает код соответствующих символов.

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

Для реализации синтаксического анализатора потребуется глобальная переменная token: integer, которая будет содержать распознанную лексему.

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

yymemoinit(memo1, memo3, memo3, memo3);

yyclear;

yylineno: =0;

token: =yylex;

if goal

then showmessage(‘Успех’)

else showmessage(‘Неудача’)

В соответствии с первым правилом грамматики, функция goal должна вызвать функцию expr и в зависимости от ее результата сформировать свой результат.

function goal: boolean;

begin

result: =expr;

end;

Аналогично согласно второму правилу входная последовательность соответствует нетерминалу expr в том случае, если первая ее часть соответствует нетерминалу TERM, а вторая нетерминалу EXPR1

function expr: boolean;

begin

result: =(term and expr1);

end;

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

function expr1: boolean;

begin

case token of

ord('+'):

begin

token: =yylex;

result: =term and expr1;

end;

ord('-'):

begin

token: =yylex;

result: =term and expr1;

end

else result: =true;

end; {case}

end; {function}

Функции для реализации продукций 6-9 аналогичны предыдущим и приведены ниже.

function term: boolean;

begin

result: = factor and term1

end;

function term1: boolean;

begin

case token of

ord('*'):

begin

token: =yylex;

result: =factor and term1;

end;

ord('/'):

begin

token: =yylex;

result: =factor and term1;

end

else result: =true;

end; {case}

end; {function}

Для нетерминала FACTOR в грамматике присутствует два правила, если последовательность не соответствует ни одному из них, то она не соответствует нетерминалу FACTOR.

function factor: boolean;

begin

case token of

id:

begin

token: =yylex;

result: =true;

end;

num:

begin

token: =yylex;

result: =true;

end;

else result: =false

end {case}

end; {function}

Расширим язык, который должен распознаваться синтаксическим анализатором. Прежде всего, значение арифметического выражения должно присваиваться какой-либо переменной. Ведем еще одну команду: запросить значение переменной у пользователя. Эта команда состоит из служебного слова read, за которым следует идентификатор, взятый в круглые скобки. Теперь наш язык представляет собой список команд, разделенных символом “; ”. Команда – это либо операция присвоения переменной значения, либо запрос значения переменной у пользователя. Список команд может быть пустым.

Грамматика для нового языка представлена на рисунке 21.

1. GOALà LIST_INSTRUCTION

2. LIST_ INSTRUCTION à READ_INSTR; LIST_INSTRUCTION

3. | ASSIGN_INSTR; LIST_INSTRUCTION

4. | e

5. READ_INSTRà read_term (id)

6. ASSIGN_INSTRà id = EXPR

2. EXPRà TERM EXPR1

3. EXPR1à +TERM EXPR1

4. EXPR1à -TERM EXPR1

5. EXPR1à e

6. TERMà FACTOR TERM1

7. TERM1à *FACTOR TERM1

8. TERM1à /FACTOR TERM1

9. TERM1à e

10. FACTORà num

11. FACTORà id

Рисунок 21.

Будем считать, что при распознавании строки “read” лексический анализатор возвращает основной программе константу read_term. Если во входной последовательности встречаются символы “(” или “)”, то LEX возвращает коды этих символов. Для строки “: =” лексический анализатор возвращает код символа “=”.

Ниже приведен текст функция для новых и изменившихся продукций.

function goal: boolean;

begin

result: =list_instruction;

end;

function list_instruction: boolean;

begin

case token of

read_term:

begin

if read_instr and (token=ord(’; ’))

then result: =list_instruction

else result: =false;

end;

id:

begin

if assign_instr and (token=ord(’; ’))

then result: =list_instruction

else result: =false

end;

else result: = true {case}

end; {case}

end; {function}

function read_instr: boolean;

begin

if (token=read_term) and (yylex=ord(’(’))

and (yylex=id) and (yylex=ord(’)’))

then

begin

result: =true;

token: =yylex;

end

else result: =false;

end;

function assign_instr: boolean;

begin

if (token=id) and (yylex=ord(’=’))

then

begin

token: =yylex;

result: =expr;

end

else result: =false

end;

5.5 Контрольные вопросы

- Что такое контекстно-свободная грамматика?

- Какой нетерминал является стартовым в грамматике?

- Когда можно утверждать, что одна последовательность выводим из другой за один шаг?

- В чем различие левого и правого вывода?

- Как вывод можно представить в виде дерева?

- В чем состоит метод разбора сверху вниз?

- Какова процедура рекурсивного разбора сверху вниз?

- Какие грамматики являются леворекурсивными?

- В чем состоит метод исключения левой рекурсии?

- Какие грамматики являются LL(1)-грамматиками?

5.6 Задание

1. Написать грамматику для распознавания программы. Программа состоит из раздела определения переменных и раздела команд. Раздел определения переменных начинается со служебного слова “var”, за которым следует список переменных вида < имя переменной>: < тип переменной>. Раздел команд начинается со служебного слова “begin”, за которым следует список команд. Завершается раздел команд служебным словом “end”.

Команды могут быть следующего вида:

а) Команда присвоения, состоит из идентификатора, знака присвоения (: =) и арифметического выражения. Арифметическое выражение включает в себя сложение, умножение, вычитание, деление, скобки, округление.

Команда чтения значения переменной. Она состоит из служебного слова “read” и идентификатора, взятого в скобки.

б) Команда вывода. Состоит из служебного слова “write” и идентификатора, взятого в скобки или строки, заключенной в кавычки и скобки.

в) Команда ветвления, которая состоит из трех разделов: условие, список операторов при выполнении условия, список операторов при не выполнении условия. Раздел условия начинается со служебного слова If. После него следует само условие. Условие состоит из конструкций вида идентификатор|число =|< |> идентификатор|число. Конструкции такого вида заключаются в скобки. Такие конструкции могут быть соединены в условии или операцией and, или операцией or. Если в условии присутствуют такие операции, то связываемые ими конструкции должны быть взяты в круглые скобки. Скобки могут встречаться в условии и для обозначения приоритета действий. Два остальных раздела команды ветвления имеют идентичную структуру. Первый из них начинается со служебного слова “Then”, а второй с “Else”. После служебного слова должна следовать или команда или список команд, заключенные в программные скобки “begin” “end”. Раздел “Else” в операции ветвления может отсутствовать.

2 Реализовать полученную грамматику методом рекурсивного спуска.

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

5.7 Содержание отчета

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

6 Лабораторная работа № 4 “Таблично управляемый синтаксический разбор сверху вниз”

6.1 Цель работы

Целью выполнения лабораторной работы является:

- получение навыков построения таблицы для разбора сверху вниз;

- изучение алгоритма работы таблично управляемого синтаксического анализатора.

6.2 Структура анализатора

Структура таблично управляемого синтаксического анализатора представлен на рисунке 22.

Рисунок 22 - Структура таблично управляемого синтаксического анализатора.

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

6.3 Построение множества first

Для последовательности a определим множество first как множество терминалов, с которых может начинаться последовательность, выводимая из a. Если из a можно вывести пустую строку, то в множество first последовательности a должно присутствовать e. Определим множество first для некоторого грамматического символа х.

1. Если х - терминал, то first(x)={x}. Так как первым символом последовательности из одного терминала может являться только сам терминал.

2. Если в грамматике присутствует правило Хà e, то множество first(х) включает e. Это означает, что Х может начинаться с пустой последовательности, то есть отсутствовать вообще.

3. Для всех продукций вида Xà Y₁ Y₂ … Y_k выполняем следующее. Добавляем в множество first(Х) множество first(Y_i) до тех пор, пока first(Y_i-1) содержит e, а first(Y_i) не содержит e. При этом i изменяется от 0 до k. Это необходимо, так как если Y_i-1 может отсутствовать, то необходимо выяснить, с чего будет начинаться вся последовательность в этом случае.

Проиллюстрируем третье правило на примере продукции X à A B C. Пусть first(A)={+, e}, first(B)={-}, first (C)={id}. При i=1 можно увидеть, что first(Y₁)={+, e}, то есть добавляем {+} в множество first(X) и продолжаем рассматривать грамматические символы правой части продукции. First(Y₂)={-} и уже не содержит e, поэтому добавляем {-} в first(X) и прекращаем рассмотрение продукции. Таким образом, first(X) = {+, -}. Заметим, что e отсутствует в first(X), хотя e принадлежит first(A). Из рассматриваемой продукции не следует, что пустая строка выводима из Х, следовательно e не может принадлежать first(X).

Построим множества first для всех грамматических символов языка, описанного на рисунке 16. Согласно первому правилу множество first всех терминалов языка состоит только из самого этого терминала (таблица 1 столбец 2). Так как в грамматике присутствует правило EXPR1à e, то в множество first(EXPR1) добавляем e. Аналогично для множества first(TERM1). Результат шага 2 построения множества first представлен в столбце 3 таблицы 1.

Множество first(FACTOR) строится на основе продукций 10 и 11 согласно правила 3 алгоритма. Исходя из продукций 7 и 8, в множество first(TERM1) должны быть добавлены множества {*} и {/}. В обоих случаях достаточно просмотреть только первый грамматический символ правой части правила. Так как множество first этого символа не содержит e, то дальнейший анализ правила не производим. Согласно продукции 6 first(TERM)=first(FACTOR). Остальные продукции рассматриваются аналогичным образом. Результат выполнения третьего шага алгоритма построения множества first представлен в столбце 4 таблицы 2. В столбце 5 этой таблицы представлено множество first грамматического символа, полученное в результате выполнения всех шагов алгоритма.

Таблица 3.

6.4 Построение множества follow

Для каждого нетерминала грамматики можно построить множество follow, то есть множество терминалов, которые можно встретить непосредственно после нетерминала в какой-либо последовательности, соответствующей грамматике.

Алгоритм построения множества follow заключается в следующем. Вначале символ конца входной последовательности помещается в множество follow стартового нетерминала (шаг 1). Затем выполнятся шаги 2-4 до тех пор, пока можно еще что-либо добавить в множество follow(X).

2. Если есть правило Аà aBb, то в множество follow(В) добавляем множество first(b) без e. То есть, если есть правило, утверждающее, что за В следует b, то за нетеримналом будут следовать терминалы, с которых начинается последовательность b.

3. Если есть правило Аà aB, то в множество follow(B) добавляется множество follow(A). То есть, если есть правило, утверждающее, что нетерминалом В заканчивается последовательность А, то за нетрминалом В будут следовать те же терминалы, что и за всей последовательностью А.

4. Если есть продукция Аà aBb и пустая последовательность принадлежит first(b), то в множество follow(B) добавляется множество follow(A). Если последовательность b не пуста, то терминалы, которые могут следовать за В уже найдены на шаге 1. Если же последовательность b пуста, то шаг 3 фактически сводится к шагу 2.

Рассмотрим построение множеств follow для нетерминалов грамматики, приведенной на рисунке 16.

Стартовым является нетерминал GOAL, поэтому на первом шаге follow(GOAL): =eof. Затем рассмотрим продукции грамматики, при этом будем считать, что a может являться пустой последовательностью.

Условию второго шага построения множества follow соответствуют следующие продукции.

EXPRà TERM EXPR1, поэтому в follow(TERM) добавляем first(EXPR1) - e

TERMà FACTOR TERM1, следовательно, в follow(FACTOR) заносим first(TERM1) - e

Условию третьего правила удовлетворяют следующие продукции.

GOALà EXPR, на основании этого заносим в follow(EXPR) follow(GOAL).

EXPRà TERM EXPR1, поэтому в follow(EXPR1) добавляем follow(EXPR).

EXPR1à + EXPR, эта продукция позволяет занести в follow(EXPR) follow(EXPR1). Однако выполнять это не нужно, так как follow(EXPR1)=eof, а follow(EXPR) уже содержит этот элемент.

TERMà FACTOR TERM1, поэтому в follow(TERM1) добавляем follow(TERM).

TERM1à * TERM, следовательно в follow (TERM) можно занести follow(TERM1), но все элементы, которые можно было бы добавить уже содержаться в этом множестве.

Теперь рассмотрим продукции, соответствующие четвертому шагу алгоритма построения множества follow. Пустая последовательность e принадлежит множеству first только двух нетерминалов: EXPR1 и TERM1, поэтому на четвертом шаге будет рассмотрено только две продукции.

EXPRà TERM EXPR1, на основе этого в follow(TERM) добавим follow(EXPR).

TERMà FACTOR TERM1, следовательно в follow(FACTOR) занесем follow(TERM).

Результаты вышеизложенных рассуждений сведены в таблице 3. Заметим, что продукции 4 и 9 не рассматривались, так как они с точки зрения построения множества follow эквиваленты продукциям 3 и 8 соответственно. Так же не рассматривались продукции 5, 9, 10, 11, так как они не подходят ни под одно условие.

Таблица 4 – Множество FOLLOW, после первой итерации.

Теперь необходимо еще раз повторить шаги 2 – 4. Новые элементы в множество follow можно добавить на шаге 3. Рассматривая продукцию TERMà FACTOR TERM1, в follow(TERM1) нужно добавить follow(TERM). Теперь follow(TERM)={+, -, eof}. Таким образом, в follow(TERM1) добавляем элемент eof. Аналогично на четвертом шаге, рассматривая продукцию TERMà FACTOR TERM1, в follow(FACTOR) занесем элементы + и -, которые отсутствуют в этом множестве, но на данном этапе принадлежат follow(TERM). Еще одно выполнение шагов 2-4 ничего нового к множеству follow не добавит, поэтому алгоритм закончил работу. Результат работы алгоритма представлен в таблице 5.

Таблица 5 Множество FOLLOW, после второй итерации.

6.5 Построение таблицы разбора

После построения множеств first и follow можно построить саму таблицу разбора.

Таблица разбора строится следующим образом.

Для всех продукций Аà a грамматики выполняем:

1 Для всех терминалов а, принадлежащих first(a) в клетку [А, а] таблицы разбора записываем продукцию Аà a.

2 Если e принадлежит first(a), то для всех b, принадлежащих follow(А), в клетку [A, b] записываем продукцию Аà a.

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

Если при построении таблицы возникает попытка в одну клетку записать две или более продукции, то разбираемая грамматика не является LL(1)-грамматикой, следовательно, не может разбираться таким способом.

Продолжим построение таблицы разбора для грамматики с рисунка 16.

Рассмотрим первую продукцию. first(EXPR)={num, id}, то есть, записываем продукцию GOALà EXPR в клетки таблицы [GOAL, num] и [GOAL, id]. e не принадлежит first(EXPR), поэтому правило 2 построения таблицы разбора не применимо к первой продукции грамматики.

Для второй продукции first(a)=first(TERM EXPR1)=first(TERM)={num, id}. Переход first(TERM EXPR1)=first(TERM) возможен, так как first(TERM) не содержит e. Если бы это было не так, то необходимо было бы рассмотреть и first(EXPR1). На основании первого правила построения таблицы разбора в клетки [EXPR, num] и [EXPR, id] записываем продукцию EXPRà TERM EXPR1.

Далее построение таблицы производится аналогичным образом. Интерес представляют продукции 5 и 9. Эти продукции в отличие от остальных соответствуют второму правилу построения таблицы разбора. Follow(EXPR1)={eof}, поэтому заносим продукцию EXPR1à e в клетку [EXPR1, eof]. Follow(TERM1)={eof, +, -}, поэтому в клетки таблицы [TERM1, eof], [TERM1, +] и [TERM1, -] заносим продукцию TERM1à e.

Таблица разбора представлена ниже.

Таблица 6 - Таблица разбора.