lex (813547), страница 7
Текст из файла (страница 7)
Детерминированный конечный автомат (далее по текстуДКА) по любому входному символу допускает не более одного перехода из каждого состояния.Поэтому для любого входного символа может существовать только одно допускающеесостояние,вкотороеонможетпереходитьизтекущегосостояния.Напротив,недетерминированный конечный автомат (далее по тексту НКА) допускает не более одногоперехода из каждого состояния. Поэтому он одновременно может находиться в несколькихсостояниях. Формально ДКА и НКА различаются значением функции переходов.
В ДКАзначением функции переходов может быть только одно состояние, а в НКА – множествосостояний. В общем случае НКА более компактны и легче строятся, но ДКА имеетпреимущество по быстродействию. По этой причине для распознавания лексем входногопотока по регулярному выражению обычно реализуется ДКА.В следующем примере рассматривается ДКА для распознавания лексем, обозначаемыхрегулярным выражением:(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*Этому регулярному выражению удовлетворяют бинарные векторы с четным числом нулевых ичетным числом единичных разрядов. Например, ему соответствует бинарный вектор01001000, который содержит две единицы и шесть нулей.Очевидно, входной алфавит ДКА, реализующего это регулярное выражение, должнысоставлять символы 0 и 1.
Также вполне естественно использовать состояния данного ДКА дляподсчета числа нулей и единиц входной последовательности по модулю 2, чтобы фиксироватьчетное или нечетное число символов 0 или 1 было получено в каждый момент из входногопотока. Поэтому актуальными могут быть только четыре состояния, которые можноохарактеризовать и обозначить следующим образом:Q1 – получено четное число символов 0 и четное число символов 1;Q2 - получено четное число символов 0 и нечетное число символов 1;Q3 - получено нечетное число символов 0 и нечетное число символов 1;Q4 - получено нечетное число символов 0 и четное число символов 1.Состояние Q1 одновременно является начальным и единственным допускающим.
Начальнымоно является потому, что до того как будут прочитаны какие-либо входные данные, количествополученных символов 0 и 1 равно нулю, а нуль есть четное число. Это же состояние являетсяединственным допускающим, поскольку только оно в точности удовлетворяет условиямсоответствия регулярному выражению, которое должен реализовывать данный ДКА. Чтобызавершить определение ДКА нужно задать функцию переходов между его состояниями.
Приэтом, полезно учесть, что возможно всего 8 переходов по символам 0 и 1 между состояниями,которые различаются либо числом нулей, либо числом единиц. Таким образом, взаимообратныепереходы при получении символа 1 имеют место в парах состояний Q1<=>Q2 и Q3<=>Q4.Также взаимообратные переходы имеют место при получении символа 0 в парах состоянийQ1<=>Q4 и Q2<=>Q3. Эти наблюдения можно представить в виде следующей двумернойтаблицы, обычно называемой таблицей переходов:||0||1===================================Q1||Q4||Q2Q2||Q3||Q1Q3||Q2||Q4Q4||Q1||Q3Столбцы таблицы переходов обозначают символы входного алфавита, а строки соответствуюттекущим состояниям ДКА. Элементы каждой строки указывают состояния ДКА, в которые ондолжен переходить из текущего состояния при получении соответствующих символов входногоалфавита. В частности, из первой строки данной таблицы переходов следует, что получениесимволов 0 и 1 в начальном состоянии Q1 переводит ДКА в состояния Q4 и Q2,соответственно.При распознавании входной последовательности по таблице переходов легко проследитьизменения состояния ДКА с целью определить достигается или нет одно из допускающихсостояний.
В частности, для бинарного вектора 01001000 с четным числом нулей и единицрассмотренный ДКА порождает следующую последовательность переходов, где каждыйпереход помечен вызывающим его символом входного алфавита:01001100Q1 -> Q4 -> Q3 -> Q2 -> Q3 -> Q4 -> Q1 -> Q4 -> Q1Эта последовательность переходов завершается допускающим состоянием Q1, следовательно,бинарный вектор 01001000 принадлежит регулярному множеству, распознаваемомурассмотренным ДКА и удовлетворяет приведенному выше регулярному выражению.В заключение следует отметить, что рассмотренный неформальный способ конструированияДКА для регулярного выражения основан на частном логическом исследовании проблемы и неявляется универсальным. Однако существуют формальные алгоритмы построения конечныхавтоматов по регулярному выражению. В частности, для получения НКА из регулярноговыражения используется построение Томпсона, а последующее преобразование НКА в ДКАобеспечивает метод построения подмножеств состояний.
Для непосредственного полученияДКА по регулярному выражению применяется алгоритм, основанный на построениисинтаксического дерева регулярного выражения.Перечисленные формальные методы реализованы во всех программах генераторов лексическиханализаторов, где для спецификации лексем входного потока используются регулярныевыражения. В частности, генератор LEX автоматически конструирует ДКА для лексическогоанализатора на основе построения синтаксических деревьев регулярных выражений, которыезаданы во входном файле спецификации лексем разработчиком лексического анализатора.СПЕЦИФИКАЦИЯ ЛЕКСЕМСТРУКТУРА ФАЙЛА СПЕЦИФИКАЦИИ ЛЕКСЕМВся исходная информация для построения лексического анализатора средствами генератораLEX должна быть сосредоточена в файле спецификации лексем, который имеет определеннуювнутреннюю структуру.
В общем случае он может состоять из трех последовательных секций:секции описаний,секции правил,секции подпрограмм.Для разграничения этих секций в файле спецификации лексем используется специальныйразделитель, который образует пара знаков процента %% в начале отдельной строки. Общийформат файла спецификации лексем имеет следующий вид:/* Секция описаний */%%/* Секция правил */%%/* Секция подпрограмм */В частном случае секции описаний и подпрограмм могут отсутствовать. Секция правилобязательна, но может быть пустой. Поэтому минимальный корректный для генератора LEXфайл спецификации лексем имеет следующий вид:%%В этом файле спецификации лексем нет описаний, нет правил и нет подпрограмм. По такомуфайлу спецификации лексем генератор LEX построит лексический анализатор, который толькокопирует без изменений содержимое входного потока стандартного ввода в выходной потокстандартного вывода.
Очевидно, что в практическом смысле такой лексический анализ малополезен, поэтому в общем случае, по крайней мере, секция правил не должна быть пустой.Принципы формирования перечисленных секций файла спецификации лексем рассмотреныниже.СЕКЦИЯ ОПИСАНИЙВсе, что находится в файле спецификации лексем до первой разделительной пары знаковпроцента %%, генератор LEX считает относящимся к секции описаний. Эта секция содержитдекларативную информацию для секций правил и подпрограмм. В общем случае в секцииописаний могут быть декларированы:блок описаний,метки предусловий,макросы регулярных определений,размеры внутренних массивов программы лексического анализатора.Перечисленные декларации должны начинаться с начальной позиции строк секции описаний.Только в этом случае они могут быть соответствующим образом интерпретированыгенератором LEX.
Любые строки секции описаний, которые содержат лидирующие символыпробела и табуляции, без обработки копируются в исходный код программы лексическогоанализатора. Это обычно используется, чтобы включать в секцию описаний необходимыекомментарии, которые должны задаваться в формате языка программирования C. Аналогичнымобразом в секцию описаний можно включать объявления внешних переменных программылексического анализатора или иные законченные конструкции языка программирования C,которые не обязаны начинаться с первой позиции строки.В некоторых случаях важно иметь возможность включать в секцию описаний глобальныеспецификации, которые не являются конструкциями генератора LEX, но должны начинаться спервой позиции строки, например, директивы препроцессора системы программирования C, вчастности, директивы #if, #else, #ifdef, #ifndef, #endif, #line, #define и #include.
Такиеглобальные спецификации должны быть размещены между служебными ограничителями %{ и%}, которые располагаются в отдельных строках секции описаний, начиная с первой позиции.Все, что находится между ними, образует блок описаний, любые инструкции которого имеютглобальный характер для остальных секций файла спецификации лексем и без измененийкопируются генератором LEX в исходный код проектируемой программы лексическогоанализатора. Следует отметить, что некоторые реализации генератора LEX также допускаютвключать блок описаний в секцию правил файла спецификации лексем.Пример оформления блока описаний демонстрирует следующий фрагмент программного кода,макросы и переменные которого могут быть полезны для обработки скобочных конструкций:/* Блок глобальных описаний для скобочных конструкций */%{#include "y.tab.h"#define LEFTBRACKET'('/* код открывающей скобки */#define RIGHTBRACKET')'/* код закрывающей скобки */extern int bracketcount;/* декларация счетчика скобок */int bracketcount = 0;/* инициализация счетчика скобок */%}Этот блок описаний содержит директивы препроцессора системы программирования C#include и #define, которые применяются для подключения заголовочного файла y.tab.h имакроопределенийскобочныхсимволовLEFTBRACKETиRIGHTBRACETсцельюпоследующего использования в секциях правил и подпрограмм файла спецификации лексем.
Всоответствии с правилами языка программирования C эти декларации должны начинаться спервой позиции строки и поэтому не могут быть специфицированы за пределами блокаописаний. Следующее за ними инструкции объявления, определения и инициализации внешнейцелочисленной переменной bracketcount не обязательно должны начинаться с первой позициистроки. Поэтому эти инструкции могут быть расположены в любой строке за пределами блокаописаний, после символов пробела или табуляции аналогично комментарию перед блоком.
Вданном случае они включены в блок описаний исходя из косметических соображений.Если содержимое блока описаний и комментарии просто копируются в файл спецификациилексем, то конструкции остальных служебных директив секции описаний ориентированы наобработку генератором LEX. На практике наиболее часто используются директивы, которыедекларируют метки предусловий и макросы регулярных определений для секции правил.Метки предусловий используются для идентификации состояний лексического анализатора приобработке регулярных выражений с левым контекстом в секции правил. В секции описаний всенеобходимые метки предусловий должны быть объявлены служебной директивой %START,которая указывается с первой позиции строки.Например, следующая декларация секции описаний объявляет метку предусловия STATE дляпоследующего использования в секции правил:%START STATEЕсли необходимо задать несколько меток предусловий, то они должны быть перечислены последирективы %START через пробел. В частности, следующая декларация объявляет меткипредусловий STATE1 и STATE2 для секции правил:%START STATE1 STATE2Следует отметить, что название этой служебной директивы допустимо задавать строчнымибуквами, например, %start или %Start, а также сокращать до одного символа, то есть, %s или%S.
Обязательно только то, чтобы строка, содержащая данную директиву в любой допустимойформе, была первой строкой секции описаний.Регулярные определения обычно применяются для упрощения и унификации записи регулярныхвыражений. Все необходимые регулярные определения специфицируются в секции описанийстроками следующего вида:MACROREGULARВ этой строке MACRO обозначает произвольное алфавитно-цифровое имя, которое начинаетсяс буквы и используется в дальнейшем как макрос для подстановки регулярного выраженияREGULAR в другие регулярные выражения или определения секций описаний и правил.Генератор LEX гарантирует автоматическую подстановку значения регулярного определения влюбое регулярное выражение файла спецификации лексем, где его имя указано в фигурныхскобках.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
