Курс Основы построения трансляторов


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


Регулярные грамматики также, как и конечные автоматы, могут быть использованы для описания лексики. Причем они являются эквивалентными друг другу. Так в правиле вида   U ::=aX  нетерминал в левой части можно интерпретировать как состояние перехода, нетерминал в правой части - как текущее состояние, терминал - как распознаваемый символ. На самом же деле регулярные грамматики являются не слишком удобным средством для непосредственного описания лексики. На практике используется более свободная форма описания, называемая регулярными выражениями.  РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ - это язые описания лексики, формально сводимый к регулярным грамматикам. Рассмотрим вкратце его синтаксис.

Простейшие регулярные выражения – [<символ>], где квадратные скобки являются метасимволом. Простейшие регулярные выражения также могут быть заданы в виде [<список символов>]. Пример [ + - * / ]. В данном примере разрешается употребление одного символа из этого списка. Еще один вид описания простейших регулярных выражений – с помощью диапазона – [<символ> – <символ>] возможность использования одного символа из этого диапазона. В этом описании квадратные скобки и знак диапазона ( дефис ) являются метасимволами. Стоит заметить, что программа лексического анализа автоматически распознает диапазон символов и отличает его от знака минус. Диапазон будет интерпретирован правильно, только если начальный и конечный символы являются границами этого диапазона. Т.е. это либо буквы, либо цифры и начальный символ диапазона является меньшим , чем конечный.

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

1.Оператор ?. Порядок использования (регулярное выражение)?. Означает в точности одно или ни одного появления регулярного выражения в тексте. Пример: [ + - ]? – либо плюс, либо минус, либо вообще ничего.

2.Оператор *. Порядок использования (регулярное выражение)*. Означает ни одного, одно или несколько появлений регулярного выражения в тексте.


Начало  Назад  Вперед