ИСПОЛЬЗОВАНИЕ АВТОМАТНОЙ ГРАММАТИКИ ПРИ ПОСТРОЕНИИ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА

Введение

Мы живем в XXI веке – столетии тотальной информатизации и автоматизации окружающих нас процессов. Информационные технологии и производство компонент ЭВМ за последние десятилетия совершили небывалый прорыв.

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

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

Чтобы код программы, написанной программистом на языке программирования, мог быть выполнен ЭВМ, должны осуществиться компиляция и компоновка.

Первая составляющая часть компилятора – лексический анализатор. Он осуществляет сканирование и лексический анализ входной программы (затем компиляцию продолжает синтаксический анализатор). В основе работы лексического анализатора лежит теория регулярных грамматик.

В этой научной работе авторы ставят задачу ознакомления читателя с этапами лексического анализа и демонстрации примера построения простейшего лексического анализатора для конкретного фрагмента программы на языке программирования Java.

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

Цель

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

Теоретические сведения

Лексический анализатор – часть компилятора, выполняющая разбор входной последовательности символов и выделяющая в ней лексемы исходного языка. В результате работы лексического анализатора создается последовательность токенов – классифицированных по типу лексем [2].

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

Символы языка делятся на терминальные и нетерминальные. Терминальный символ непосредственно присутствует в "словах" языка, соответствующего грамматике, и имеет неизменяемое значение. Нетерминальный символ обозначает какую-либо сущность языка (например выражение) и не имеет конкретного символьного значения.

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

-ключевые слова (begin, while, do, for),

-идентификаторы (i, j,Test),

-константы(123,"name",1E-5),

-знаки операций (=,++,<<),

-разделители(,:.)

В процессе построения лексического анализатора языка составляются таблицы идентификаторов и лексем. Таблица лексем содержит все их возможные виды, любая лексема может повторится несколько раз. Таблица идентификаторов содержит только идентификаторы и константы, каждые из которых встречаются только один раз [3].

Таблица 1.

Пример таблицы лексем

При составлении таблицы каждому элементу языка сопоставляется тип соответствующей лексемы. Некоторые базовые элементы объединены в один тип (осуществляют схожие функции и имеют одинаковый приоритет).

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

В основе лексических анализаторов лежат автоматные грамматики.

Грамматикой G называется четверка (S,V_N,S_T,R), где S – начальный символ грамматики, V_N – множество нетерминальных символов, S_T  – множество терминальных символов, R – множество правил грамматики [4].

Каждое правило грамматики в общем случае записывается в виде α→β, где α, β – произвольные цепочки, составленные из терминальных и нетерминальных символов грамматики.

Автоматной называется грамматика, все правила которой имеют вид: А→αB, A→ α, где A, B – нетерминальные символы, α – терминальный символ [1]. Правила A→ α называют заключительными(терминальными) правилами.

Автоматная грамматика для целочисленных констант имеет вид:

S→0S|1S|...|9S|0|1|...|9

Автоматная грамматика для идентификаторов имеет вид:

S→aA|bA|...|zA

S→ 0A|1A|...|9A|0|1|...|9|aA|bA|...|zA|a|b|...|z

Построение собственного лексического анализатора для цепочки с предуcловием на языке Java

В качестве анализируемого выражения возьмем цепочку следующего вида:

while ((a<n) and (b<k) ){

sum=sum+a;

a=a+1;

b=b+20;

}

В качестве алфавита выступают буквы латинского алфавита, цифры, другие значащие символы (+, <, =,  ;, (, ), {, }) и незначащие символы(пробел, табуляция, перевод строки)

Составим таблицы лексем и идентификаторов, которые будет использоваться лексическим анализатором при трансформации исходной программы в цепочку токенов(см. таблицы 2–6). Сам лексический анализатор будем реализовывать как анализатор автоматного языка.

Составим автоматную грамматику для идентификаторов и констант(символом '^' обозначен символ конца строки). При ее построении будем считать, что символом '*' обозначены все символы, не являющиеся цифрами, символом '~' – пробел, символом 'ϴ' – все кроме букв и цифр, символом 'µ' – все символы, кроме фигурных скобок. После перехода в состояние F_x, автомат сбрасывается и переходит в состояние S.

S→~S                                      

S→aA|bA|...|zA                        S→0B|1B|...|9B

A→aA|bA|...|zA                       B→0B|1B|...|9B

A→0A|1A|...|9A                      B→*F₅

A→ ϴF_1,4

Грамматики для операций и отношений:

S→=F₂|+F₂|>F₂                     

Грамматики для специальных символов:

S→;F₃|(F₃|)F₃                     

Грамматика для последовательностей незначащих символов:

S→#32S|...|#10S|#13S|^

Грамматика для выражений, находящихся в фигурных скобках (включая их):

S→{S'

S'→µS'

S'→}S

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

Автомат завершает работу при считывании символа '^':

S→^fin, здесь fin – состояние, в котором считывается последняя лексема.

Таблица 2.

Тип 1– служебные слова

Таблица 3.

Тип 2 – операции и отношения

Таблица 4.

Тип 3 – специальные символы

Таблица 5.

Тип 4 – идентификаторы

Таблица 6.

Тип 5 – числовые константы

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

<1,1>,<3,2>,<3,2>,<4,1>,<2,1>,<4,2>,<3,3>,<1,2>,<3,2>,<4,3>,<2,1>,<4,4>,<3,3>,<3,3>,<3,4>,<4,5>,<2,2>,<4,5>,<2,3>,<4,1>,<3,1>,<4,1>,<2,2>,<4,1>,<2,3>,<5,1>,<3,1>,<4,3>,<2,2>,<4,3>,<2,3>,<5,2>,<3,1>,<3,5> – здесь у пары <i,j> число i  означает номер типа, число j – номер лексемы в типе.

Создадим конечный детерминированный автомат, распознающий цепочки, являющиеся лексемами вышеприведенных типов. Конечными состояниями автомата будут являться F_1,4, F₂, F₃, F₅(здесь индекс конечного состояния означает нахождение считанной лексеме в соответствующей таблице лексем), т.е. попадание в состояние F₃ означает,  что считан специальный символ из таблицы 3 и т.д. Лексемы из таблиц 1 и 4(служебные слова и идентификаторы) объединены в одно финальное состояние с целью уменьшения размера автомата и упрощения программистской задачи. Заметим, что конец считывания происходит только при считывании одного лишнего символа.

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

Рисунок 1. Конечный автомат в виде графа

На представленном рисунке Err – состояние ошибки, в которое автомат попадает при неописанном символе, в Err ведут стрелки со всех состояний.

Код программы лексического анализатора

char GetNextChar();

void ReturnLiter(char c);

void AddToBuf(char c);

bool IsNumber(char c);

void IsLetter(char c);

int BufIntendKey(int &Type);

int BufOper(int &Type);

int BufSpec(int &Type);

int BufNum(int &Type);

enume State {S,S1,A,B,fin} T;

int StepNextChar (int &Type) {

 char c;

 State T=S;

 do{

   c=GetNextChar();

   switch(T){

     case S: if((c==’ ’)||(c==’\t’)||(c==’\r’)||(c==’\n’)) break;

            if(c==’{’) {T=S1;break;}

            if(c==’^’) return 0;

            AddToBuf (c);

            if(IsLetter(c)) {T=A; break;}

            if((c==’=’)||(c==’+’) ||(c==’<’)) return BufOper (Type);

            if((c==’;’) ||(c==’(’)||(c==’)’)) return BufSpec (Type);

            if(IsNumber(c)) {T=A; break;}

            return -1;

    case A:if(IsNumber(c)|| IsLetter(c)) { AddToBuf (c);break;}

            else {ReturnLiter(c);return BufIntendKey (Type);}

    case B:if(IsNumber(c)){

             AddToBuf (c);

             break;

            }

            ReturnLiter(c);

            return BufNum (Type);

   }

 } while true;

}

 int LexicalAnalyzer (int &Type) {

 int Type;

 int N;

  do{

  N=StepNextChar(Type);

  if(N=<0) return N;

  AddToOutSeq(N,T);

 } while true;

}

Список литературы:

1. Иванова Г.С., Ничушкина Т. Н. Основы конструирования компиляторов. Учебное пособие. Москва, 2010. –47c.
2. Конечные автоматы в лексическом анализе [Электронный ресурс] –Режим доступа. – URL: http://ermak.cs.nstu.ru/trans/Trans23.htm (дата обращения 17.04.2017).
3. Лексический анализ [Электронный ресурс] – Режим доступа. – URL: http://www.intuit.ru/studies/courses/26/26/lecture/803?page=1(дата обращения 13.04.2017).
4. Молчанов А. Ю. Системное программное обеспечение: Учебник для вузов. 3-е изд. –Спб.: Питер,2010. –400c.