Регулярные грамматики и выражения в лексическом анализе
Регулярные грамматики также, как и конечные автоматы, могут быть использованы для описания лексики. Причем они являются эквивалентными друг другу. Так в правиле вида U ::=aX нетерминал в левой части можно интерпретировать как состояние перехода, нетерминал в правой части - как текущее состояние, терминал - как распознаваемый символ. На самом же деле регулярные грамматики являются не слишком удобным средством для непосредственного описания лексики. На практике используется более свободная форма описания, называемая регулярными выражениями. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ - это язые описания лексики, формально сводимый к регулярным грамматикам. Рассмотрим вкратце его синтаксис.
Простейшие регулярные выражения – [<символ>], где квадратные скобки являются метасимволом. Простейшие регулярные выражения также могут быть заданы в виде [<список символов>]. Пример [ + - * / ]. В данном примере разрешается употребление одного символа из этого списка. Еще один вид описания простейших регулярных выражений – с помощью диапазона – [<символ> – <символ>] возможность использования одного символа из этого диапазона. В этом описании квадратные скобки и знак диапазона ( дефис ) являются метасимволами. Стоит заметить, что программа лексического анализа автоматически распознает диапазон символов и отличает его от знака минус. Диапазон будет интерпретирован правильно, только если начальный и конечный символы являются границами этого диапазона. Т.е. это либо буквы, либо цифры и начальный символ диапазона является меньшим , чем конечный.
Далее приведен список операторов, которые можно использовать при конструировании языка описания.
1.Оператор ?. Порядок использования (регулярное выражение)?. Означает в точности одно или ни одного появления регулярного выражения в тексте. Пример: [ + - ]? – либо плюс, либо минус, либо вообще ничего.
2.Оператор *. Порядок использования (регулярное выражение)*. Означает ни одного, одно или несколько появлений регулярного выражения в тексте.
Пример: [+ -]? [ 0-9 ]*.
3.Оператор +. Порядок использования (регулярное выражение)+. Означает одно или более появлений регулярного выражения в тексте. Пример: [ A - Z a - z ]+.
4.Оператор ; . Завершение описания класса.
5.Оператор ^. Порядок использования (регулярное выражение)^. Означает в точности любой символ, кроме регулярного выражения. Пример [A]+[Z]^[C]*.
6.Оператор |. Порядок использования (регулярное выражение) | (регулярное выражение). Операция “ИЛИ” над регулярными выражениями.
Оператор “ ”. Порядок использования “<слово>”. <Слово> может состоять из простейших регулярных выражений без использования диапазона. Обычно этот оператор служит для описания ключевых слов языка. В принципе, такую конструкцию можно описать и по-другому с помощью метасимвола квадратных скобок. Для этого необходимо каждый элемент слово описать с помощью простейшего регулярного выражения с использованием метасимвола. Например: “begin”. Равносильная конструкция [b][e][g][i][n]. Использование этого оператора позволяет сделать описание более простым.
С помощью регулярных выражений и вспомогательных операторов, описанных выше можно сконструировать описание любого языка, с использованием букв английского алфавита. Ограничением конструируемых языков является использование квадратных скобок и букв русского алфавита. В заключение приведем пример описания лексики, включающей в себя идентификаторы, десятичные и шестнадцатеричные константы, ключевые слова, знаки операций и операторов.
.
Ident = [A-Z a-z _] [A-Z a-z 0-9 _]*;
Const_Dec = [0-9]+;
Const_Hex = [0] [x] [0-9 A-F a-f]+;
Operation = [+-*/];
Operator = [=] ;
Const=Const_Dec|Const_Hex;
Un_oper = "++" | "--";
Word = "switch" | "case" | "otherwise" | "main";
ENDOFOPER=[;];
Не вдаваясь в подробности работы системы автоматизированного построения лексических анализаторов, отметим, что она производит формальное преобразование лексики в следующей последовательности представлений:
регулярные выражения;
регулярная грамматика;
недетерминированный КА (то есть автомат, имеющий несколько переходов из одного состояния по одному и тому же входному символу, либо имеющий переход по пустому символу);
детерминированный (обычный) КА.
