Лабораторная работа № 2
Построение распознавателя для регулярной грамматики

Цель работы: изучение основных понятий теории регулярных языков и грамматик, ознакомление с назначением и принципами работы конечных автоматов (КА), получение практических навыков построения КА на основе заданной регулярной грамматики.

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

Функции лексического анализатора

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

Лексема (лексическая единица языка) – это структурная единица языка, которая состоит из элементарных символов языка и не содержит в своем составе других структурных единиц.

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

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

·      упрощается работа с текстом исходной программы на этапе синтаксического разбора и сокращается объем обрабатываемой информации, так как лексический анализатор структурирует поступающий на вход исходный текст программы и выкидывает всю незначащую информацию;

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

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

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

Лексический анализатор имеет дело с таким объектами, как различного рода константы и идентификаторы (к последним относятся и ключевые слова). Язык констант и идентификаторов в большинстве случаев является регулярным – то есть, может быть описан с помощью регулярных (праволинейных или леволинейных) грамматик [1, 2, 7]. Распознавателями для регулярных языков являются конечные автоматы (КА). Существуют правила, с помощью которых для любой регулярной грамматики может быть построен недетерминированный КА, распознающий цепочки языка, заданного этой грамматикой.

Конечные автоматы

Определение конечного автомата

Как уже было сказано выше, лексемы могут быть описаны с помощью регулярных языков. Распознавателями для регулярных языков являются конечные автоматы (КА) [1, 6, 9, 20]. Поэтому КА лежат в основе лексического анализа.

КА задается пятеркой:

M=(Q, S, d, q0, F),

где:

Q - конечное множество состояний автомата;

S - конечное множество допустимых входных символов;

d - заданное отображение множества Q*S во множество подмножеств P(Q) d: Q*S®P(Q) (иногда d называют функцией переходов автомата, которая может быть определена как: d(q,a)=D, где qÎQ – текущее состояние КА, aÎS – текущий входной символ, а DÍQ – множество возможных следующих состояний КА);

q0ÎQ - начальное состояние автомата;

FÍQ - множество заключительных состояний автомата.

Работа КА выполняется по тактам. На каждом очередном такте i автомат, находясь в некотором состоянии qiÎQ, считывает очередной  символ wÎS из входной цепочки символов и изменяет свое состояние на qi+1Îd(qi,w), после чего указатель в цепочке входных символов передвигается на следующий символ и начинается такт i+1. Так продолжается до тех пор, пока цепочка входных символов не закончится, либо КА попадёт в состояние, из которого нет переходов. Конец цепочки символов часто помечают особым символом ^. Считается также, что перед тактом 1 автомат находится в начальном состоянии q0.

Говорят, что КА допускает цепочку aÎS*, если в результате выполнения всех тактов работы над этой цепочкой он может оказаться в состоянии qÎF. Язык, определяемый автоматом, является множеством всех цепочек, допускаемых данным автоматом.

Графически КА отображается нагруженным однонаправленным графом, в котором вершины представляют состояния КА, дуги отображают переходы из одного состояния в другое, а символы нагрузки (пометки) дуг соответствуют входным символам функции перехода. Если функция перехода предусматривает переход из состояния q в q' по нескольким символам, то между ними строится одна дуга, которая помечается всеми символами, по которым происходит переход из q в q'. Такой граф называют графом переходов КА.

Детерминированные и недетерминированные КА

КА называется детерминированным, если функция переходов этого автомата из любого состояния по любому входному символу содержит не более одного следующего состояния. В противном случае КА называется недетерминированным. Условие детерминированности КА можно сформулировать следующим образом: "qÎQ, "aÎS: либо d(q,a)={q'}, либо d(q,a)=Æ.

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

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

Доказано, что любой недетерминированный КА может быть преобразован в детерминированный так, чтобы их языки совпадали (говорят, что такие КА эквивалентны) [1, 6, 7, 20]. В отличие от обычного КА функция переходов детерминированного КА может быть определена как d': Q*S®Q или d(q,a)=q', где qÎQ – текущее состояние КА, aÎS – текущий входной символ, а q'ÎQ – следующее состояние КА.

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

Построение КА на основе регулярной грамматики

Исходные данные для построения КА определяет регулярная грамматика, задающая язык, описывающий лексемы, которые должен уметь распознавать лексический анализатор. Таким образом, для построения лексического анализатора необходимо уметь строить КА на основе заданной регулярной грамматики. Такое построение выполняется с помощью несложного алгоритма в два этапа [1, 7, 20]:

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

·      на основе автоматной грамматики строится КА.

В качестве примера рассмотрим лексический анализатор, выполняющий анализ лексем, представляющих собой целочисленные константы без знака в формате языка Си. В соответствии с требованиями языка, такие константы могут быть десятичными, восьмеричными, либо шестнадцатеричными. Восьмеричной константой считается  число, начинающееся с 0 и содержащее цифры от 0 до 7; шестнадцатеричная константа должна начинаться с последовательности символов 0x и может содержать цифры, а также буквы от A до F (будем рассматривать только прописные буквы). Остальные числа считаются десятичными (правила их записи напоминать, наверное, не стоит). Будем считать, что всякое число завершается символом конца строки ^.

Рассмотренные выше правила могут быть записаны в форме Бэкуса-Наура в грамматике целочисленных констант без знака языка Си (для избежания путаницы терминальные символы грамматики в правилах выделены жирным шрифтом).

G({S, G, X, H, Q, Z}, {0...9, A...F, x, ^}, P, S)

P:    S® G^|Z^|H^|Q^

       G® 1|2|3|4|5|6|7|8|9|G0|G1|G2|G3|G4|G5|G6|G7|G8|G9|Z8|Z9|Q8|Q9

       H® X0|X1|X2|X3|X4|X5|X6|X7|X8|X9|XA|XB|XC|XD|XE|XF|

              H0|H1|H2|H3|H4|H5|H6|H7|H8|H9|HA|HB|HC|HD|HE|HF

       X® Zx

       Q®     Z0|Z1|Z2|Z3|Z4|Z5|Z6|Z7|Q0|Q1|Q2|Q3|Q4|Q5|Q6|Q7

       Z® 0

Данная грамматика является регулярной грамматикой (леволинейной). Она также является автоматной грамматикой, поэтому преобразование исходной грамматики к автоматному виду в данном случае не требуется. Следовательно, можно сразу построить КА.

Получим следующий КА:

M({N, Z, X, H, Q, G, S}, {0...9, A...F, x, ^}, d, N, {S})

d:    d(G,^)={S}, d(Z,^)={S}, d(H,^)={S}, d(Q,^)={S},

       d(N,1)={G}, d(N,2)={G}, d(N,3)={G}, d(N,4)={G}, d(N,5)={G}, d(N,6)={G}, d(N,7)={G},

       d(N,8)={G}, d(N,9)={G}, d(G,0)={G}, d(G,1)={G}, d(G,2)={G}, d(G,3)={G}, d(G,4)={G},

       d(G,5)={G}, d(G,6)={G}, d(G,7)={G}, d(G,8)={G}, d(G,9)={G}, d(Z,8)={G}, d(Z,9)={G},

       d(Q,8)={G}, d(Q,9)={G},

       d(X,0)={H}, d(X,1)={H}, d(X,2)={H}, d(X,3)={H}, d(X,4)={H}, d(X,5)={H}, d(X,6)={H},

       d(X,7)={H}, d(X,8)={H}, d(X,9)={H}, d(X,A)={H}, d(X,B)={H}, d(X,C)={H}, d(X,D)={H},

       d(X,E)={H}, d(X,F)={H}, d(H,0)={H}, d(H,1)={H}, d(H,2)={H}, d(H,3)={H}, d(H,4)={H},

       d(H,5)={H}, d(H,6)={H}, d(H,7)={H}, d(H,8)={H}, d(H,9)={H}, d(H,A)={H}, d(H,B)={H},

       d(H,C)={H}, d(H,D)={H}, d(H,E)={H}, d(H,F)={H},

       d(Z,x)={X},

       d(Z,0)={Q}, d(Z,1)={Q}, d(Z,2)={Q}, d(Z,3)={Q}, d(Z,4)={Q}, d(Z,5)={Q}, d(Z,6)={Q},

       d(Z,7)={Q}, d(Q,0)={Q}, d(Q,1)={Q}, d(Q,2)={Q}, d(Q,3)={Q}, d(Q,4)={Q}, d(Q,5)={Q},

       d(Q,6)={Q}, d(Q,7)={Q},

       d(N,0)={Z}

Построенный КА M({N,Z,X,H,Q,G,S}, {0...9,A...F,x,^}, d, N, {S}) изображен на рис. 2 (без учёта дуг, показанных пунктирными линиями). Начальным состоянием данного КА является состояние N, множество конечных состояний содержит одно состояние S.

Рис. 2. Граф переходов детерминированного КА, распознающего целые числа языка Си

Очевидно, что построенный КА является детерминированным КА, но не является полностью определённым – в нём есть состояния, из которых нет переходов по одному или нескольким допустимым входным символам. Например, из состояния G нет перехода по допустимому входному символу x. Это может быть неудобным при программировании работы данного КА.

Чтобы данный КА стал полностью определённым, в него дополнительно введено особое состояние E, обозначающее ошибку в распознавании цепочки символов (на рис. 2 это состояние и идущие в него дуги обозначены пунктирными линиями). На графе автомата дуги, идущие в это состояние, не нагружены символами. По принятому соглашению они обозначают функцию перехода по любому символу, кроме тех символов, которыми уже помечены другие дуги, выходящие из той же вершины графа. Такое соглашение принято, чтобы не загромождать обозначениями граф автомата.

Порядок выполнения работы

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

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

3.        Построить КА на основе регулярной грамматики входного языка.

4.        Преобразовать КА к детерминированному виду (если необходимо).

5.        Минимизировать КА (если необходимо).

6.        Подготовить и защитить отчет.

Рекомендации:

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

2.   Идентификатором считается любая последовательность букв и цифр, начинающаяся с буквы (часто в идентификаторах допускается также знак подчёркивания – «_», иногда и другие символы). Для определения идентификаторов рекомендуется использовать правило грамматики: I ® б | Iб | Iц, где «б» обозначает любую букву, а «ц» - любую цифру.

3.   Для упрощения структуры КА ключевые слова предлагается считать идентификаторами, а уже после их выделения выполнять проверку на совпадение найденного идентификатора с заданным перечнем ключевых слов. Более подробно об этом см. в [1, 5].

Требования к оформлению отчета

Отчет должен содержать следующие разделы:

·      Краткое изложение цели работы.

·      Задание по лабораторной работе с описанием своего варианта задания и выбранного вида комментария.

·      Описание регулярной грамматики лексем входного языка в форме Бэкуса-Наура или в форме регулярных выражений (в соответствии с вариантом задания).

·      Описание КА или граф переходов КА для распознавания лексем (в соответствии с вариантом задания).

·      Выводы по проделанной работе.

Допускается оформлять единый (совместный) отчёт для лабораторных работ №2 и №3.

Основные контрольные вопросы

1.       Дайте определение цепочки символов, алфавита, языка. Что такое синтаксис и семантика языка?

2.       Какие существуют методы задания языков?

3.       Что такое транслятор, компилятор, интерпретатор? В чём их различие между собой?

4.       Расскажите об общей структуре компилятора.

5.       Что такое лексема? Расскажите, какие типы лексем существуют в языках программирования.

6.       Какие функции выполняет лексический анализ в процессе компиляции?

7.       Что такое грамматика? Дайте определения грамматики.

8.       Как выглядит описание грамматики в форме Бэкуса-Наура.

9.       Какие классы грамматик существуют?

10.   Что такое регулярные грамматики? В чём их особенности?

11.   Расскажите о распознавателях языка.

12.   Что такое конечный автомат (КА)? Как можно задать КА?

13.   Расскажите о том, как функционирует КА.

14.   Дайте определение детерминированного и недетерминированного КА. Расскажите о возможности преобразования недетерминированного КА в детерминированный.

15.   Объясните, как можно построить КА на основе регулярной грамматики.

16.   Что такое автоматная грамматика? Как связаны между собой регулярные и автоматные грамматики.

Варианты заданий

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

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

1.  Входной язык содержит арифметические выражения, разделенные символом ; (точка с запятой). Арифметические выражения состоят из идентификаторов, десятичных чисел с плавающей точкой, знака присваивания (:=), знаков операций +, -, *, / и круглых скобок.

2.  Входной язык содержит логические выражения, разделенные символом ; (точка с запятой). Логические выражения состоят из идентификаторов, констант true («истина») и false («ложь»), знака присваивания (:=), знаков операций or, xor, and, not и круглых скобок.

3.  Входной язык содержит операторы условия типа if … then … else и if … then, разделенные символом ; (точка с запятой). Операторы условия содержат идентификаторы, знаки сравнения <, >, =, десятичные числа с плавающей точкой, знак присваивания (:=).

4.  Входной язык содержит операторы цикла типа for (…; …; …) do, разделенные символом ; (точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, десятичные числа с плавающей точкой, знак присваивания (:=).

5.  Входной язык содержит операторы выбора типа case … of … end, разделенные символом ; (точка с запятой). Операторы выбора содержат идентификаторы, знак двоеточия (:), знаки операций +,  -, десятичные числа с плавающей точкой, знак присваивания (:=).

6.  Входной язык содержит операторы цикла типа while … do …, разделенные символом ; (точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, знаки операций +,  -, десятичные числа с плавающей точкой, знак присваивания (:=).

7.  Входной язык содержит арифметические выражения, разделенные символом ; (точка с запятой). Арифметические выражения состоят из идентификаторов, римских чисел, знака присваивания (:=), знаков операций +, -, *, / и круглых скобок.

8.  Входной язык содержит логические выражения, разделенные символом ; (точка с запятой). Логические выражения состоят из идентификаторов, констант 0 и 1, знака присваивания (:=), знаков операций or, xor, and, not и круглых скобок.

9.  Входной язык содержит операторы условия типа if … then … else и if … then, разделенные символом ; (точка с запятой). Операторы условия содержат идентификаторы, знаки сравнения <, >, =, римские числа, знак присваивания (:=).

10.  Входной язык содержит операторы цикла типа for (…; …; …) do, разделенные символом ; (точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, римские числа, знак присваивания (:=).

11.  Входной язык содержит операторы выбора типа case … of … end, разделенные символом ; (точка с запятой). Операторы выбора содержат идентификаторы, знак двоеточия (:), знаки операций +,  -, римские числа, знак присваивания (:=).

12.  Входной язык содержит операторы цикла типа while … do …, разделенные символом ; (точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, знаки операций +,  -, римские числа, знак присваивания (:=).

13.  Входной язык содержит арифметические выражения, разделенные символом ; (точка с запятой). Арифметические выражения состоят из идентификаторов, шестнадцатеричных чисел, знака присваивания (:=), знаков операций +, -, *, / и круглых скобок.

14.  Входной язык содержит логические выражения, разделенные символом ; (точка с запятой). Логические выражения состоят из идентификаторов, шестнадцатеричных чисел, знака присваивания (:=), знаков операций or, xor, and, not и круглых скобок.

15.  Входной язык содержит операторы условия типа if … then … else и if … then, разделенные символом ; (точка с запятой). Операторы условия содержат идентификаторы, знаки сравнения <, >, =, шестнадцатеричные числа, знак присваивания (:=).

16.  Входной язык содержит операторы цикла типа for (…; …; …) do, разделенные символом ; (точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, шестнадцатеричные числа, знак присваивания (:=).

17.  Входной язык содержит операторы выбора типа case … of … end, разделенные символом ; (точка с запятой). Операторы выбора содержат идентификаторы, знак двоеточия (:), знаки операций +,  -, шестнадцатеричные числа, знак присваивания (:=).

18.  Входной язык содержит операторы цикла типа while … do …, разделенные символом ; (точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, знаки операций +,  -, шестнадцатеричные числа, знак присваивания (:=).

19.  Входной язык содержит арифметические выражения, разделенные символом ; (точка с запятой). Арифметические выражения состоят из идентификаторов, символьных констант (один символ в одинарных кавычках), знака присваивания (:=), знаков операций +, -, *, / и круглых скобок.

20.  Входной язык содержит логические выражения, разделенные символом ; (точка с запятой). Логические выражения состоят из идентификаторов, символьных констант ‘T’ («истина») и ‘F’ («ложь), знака присваивания (:=), знаков операций or, xor, and, not и круглых скобок.

21.  Входной язык содержит операторы условия типа if … then … else и if … then, разделенные символом ;(точка с запятой). Операторы условия содержат идентификаторы, знаки сравнения <, >, =, строковые константы (последовательность символов в двойных кавычках), знак присваивания (:=).

22.  Входной язык содержит операторы цикла типа for (…; …; …) do, разделенные символом ;(точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, строковые константы (последовательность символов в двойных кавычках), знак присваивания (:=).

23.  Входной язык содержит операторы выбора типа case … of … end, разделенные символом ; (точка с запятой). Операторы выбора содержат идентификаторы, знак двоеточия (:), знаки операций +,  -, символьные константы (один символ в одинарных кавычках), знак присваивания (:=).

24.  Входной язык содержит операторы цикла типа while … do …, разделенные символом ; (точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, знаки операций +,  -, символьные константы (один символ в одинарных кавычках), знак присваивания (:=).

Примечание:

  1. Римскими числами считать последовательности больших латинских букв X, V и I. Если в задании требуется использование римских чисел, то обычные (арабские) числа должны восприниматься как недопустимые лексемы.
  2. Шестнадцатеричными числами считать последовательность цифр и символов ‘a’, ‘b’, ‘c’,’d’, ’e’ и ‘f’, начинающуюся с цифры (например: 89, 45ac9, 0abc4). Допускается использовать специальные символы для выделения шестнадцатеричных чисел (например: $0abc4 или 0x0abc4).
  3. Задание по лабораторной работе №2 взаимосвязано с заданиями по лабораторным работам №3-8. Результаты, полученные при выполнении лабораторной работы №2, будут использованы в последующих работах.
  4. Для уточнения состава входного языка можно посмотреть грамматику, заданную в работе №4 для соответствующего варианта.

Лабораторная работа № 3
Построение лексического анализатора

Цель работы: ознакомление с назначением и принципами работы лексических анализаторов (сканеров), получение практических навыков построения сканера на примере заданного простейшего входного языка.

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

Проблемы при построении лексических анализаторов

Лексический анализатор (или сканер) – это часть компилятора, которая читает литеры программы на исходном языке и строит из них слова (лексемы). Функции лексического анализатора были рассмотрены в предыдущей лабораторной работе №2.

Лексический анализатор имеет дело с таким объектами, как различного рода константы и идентификаторы (к последним относятся и ключевые слова). Язык констант и идентификаторов в большинстве случаев является регулярным – то есть, может быть описан с помощью регулярных (праволинейных или леволинейных) грамматик [1, 7, 8]. Распознавателями для регулярных языков являются конечные автоматы (КА). Существуют правила, с помощью которых для любой регулярной грамматики может быть построен КА, распознающий цепочки языка, заданного этой грамматикой.

Таким образом, построение распознавателя входного языка, лежащего в основе лексического анализатора, является достаточно простой задачей, которая гарантированно имеет решение для всех регулярных языков. Решение этой задачи было подробно рассмотрено в предыдущей лабораторной работе №2.

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

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

·      выполнить действия для сохранения информации об обнаруженной лексеме (или выдать сообщение об ошибке, если лексема неверна).

Проблема определения границ лексем

Выделение границ лексем является нетривиальной задачей. Ведь в тексте исходной программы лексемы никак не ограничены. В лабораторной работе №2 при построении КА был использован специальный символ (^), определяющий границы входной лексемы. Но в реальных программах такой символ в исходном тексте отсутствует – лексический анализатор должен сам определить, где необходимо поставить границы лексем. При этом следует учесть, что граница одной лексемы может быть в то же время началом другой лексемы. Если говорить в терминах лексического анализатора, то определение границ лексем – это выделение тех строк в общем потоке входных символов, для которых надо выполнять распознавание.

Иллюстрацией случая, когда определение границ лексемы вызывает определенные сложности, может служить пример оператора программы на языке FORTRAN: по фрагменту исходного кода DO 10 I=1 невозможно определить тип оператора языка (а соответственно, и границы лексем). В случае DO 10 I=1.15 это присвоение вещественной переменной DO10I значения константы 1.15 (пробелы в языке FORNTAN игнорируются), а в случае DO 10 I=1,15 – это цикл с перечислением от 1 до 15 по целочисленной переменной I до метки 10.

Другой иллюстрацией может служить оператор языка C, имеющий вид: k=i+++++j;. Существует только одна единственно верная трактовка этого оператора: k = i++ + ++j; (если явно пояснить ее с помощью скобок, то данная конструкция имеет вид: k = (i++) + (++j);). Однако найти ее лексический анализатор может, лишь просмотрев весь оператор до конца и перебрав все варианты, причем неверные варианты могут быть обнаружены только на этапе семантического анализа (например, вариант вида k = (i++)++ + j; является синтаксически правильным, но семантикой языка C не допускается). Конечно, чтобы эта конструкция была в принципе допустима, входящие в нее операнды k, i и j должны быть описаны и должны допускать выполнение операций языка ++ и +.

Как видно из приведённых примеров, для определения границ лексем недостаточно только распознавателя входного языка на основе КА. Поэтому во многих компиляторах лексический и синтаксический анализаторы – это  взаимосвязанные части [1, 7, 9, 13].

Взаимодействие лексического и синтаксического анализаторов

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


Рис. 3. Последовательное взаимодействие лексического и синтаксического анализаторов

Для некоторых языков программирования информации, имеющейся на этапе лексического анализа, может быть недостаточно для однозначного определения типа и границ очередной лексемы. Иллюстрацией такого случая может служить рассмотренный выше пример оператора программы на языке Фортран, когда по части текста программы DO 10 I=1... невозможно определить тип оператора (а соответственно, и границы лексем).

В этом случае в процессе анализа текста исходной программы лексический и синтаксический анализаторы обмениваются данными между собой. Лексический анализ исходного текста в таком варианте выполняется поэтапно так, что синтаксический анализатор, выполнив разбор очередной конструкции языка, обращается к сканеру за следующей лексемой. При этом он может сообщить информацию о том, какую лексему следует ожидать. В процессе разбора может даже происходить «откат назад», чтобы выполнить анализ текста на другой основе, используя другие типы лексем. Такое взаимодействие лексического и синтаксического анализаторов называют параллельным. Схема, изображающая параллельный метод взаимодействия, представлена на рис. 4.

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

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

Такой принцип не всегда позволяет правильно определить границы лексем в том случае, когда они не разделены пустыми символами. Например, приведенная выше строка языка C k = i+++++j; будет разбита на лексемы следующим образом: k = i++ ++ + j; – и  это разбиение неверное. Лексический анализатор, разбирая строку из 5 знаков + дважды выбрал лексему наибольшей возможной длины – знак операции инкремента (увеличения значения переменной на 1) ++, хотя это неправильно. Компилятор должен будет выдать пользователю сообщение об ошибке при том, что правильный вариант распознавания этой строки всё же существует.

 


Рис. 4. Параллельное взаимодействие лексического и синтаксического анализаторов

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

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

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

Результаты лексического анализа

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

Таблица идентификаторов содержит информацию обо всех лексемах исходной программы, заданных её разработчиком. В неё попадают все идентификаторы – имена переменных, функций, констант и других элементов входного языка. Методы работы с таблицей идентификаторов были подробно рассмотрены в предыдущей лабораторной работе.

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

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

Вот пример фрагмента текста программы на языке Паскаль и соответствующей ему таблицы лексем (таблица 2):

...

begin

  for i:=1 to N do

    fg := fg * 0.5

...

Таблица 2

Таблица лексем программы

Лексема

Тип лексемы

Значение

begin

Ключевое слово

X1

for

Ключевое слово

X2

i

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

i : 1

:=

Знак присваивания

 

1

Целочисленная константа

1

to

Ключевое слово

X3

N

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

N : 2

do

Ключевое слово

X4

fg

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

fg : 3

:=

Знак присваивания

 

fg

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

fg : 3

*

Знак арифметической операции

 

0.5

Вещественная константа

0.5

Информация, представленная в столбце «Значение» в таблице 2, условно изображает некоторые данные, связанные с каждой лексемой. Конкретный состав информации, хранимой в таблице лексем, и форма её представления определяются разработчиками компилятора.

Построение лексического анализатора

 Рис. 5. Граф переходов детерминированного КА, распознающего целые числа языка Си

Для построения лексического анализатора необходимо построить КА, являющийся распознавателем входного языка лексического анализатора. Построение КА описано в лабораторной работе №2. В качестве примера возьмем КА, полученный в лабораторной работе №2 – он представлен на рис. 5.

Для удобства программирования построенный КА желательно привести к детерминированному виду и минимизировать. КА, представленный на рис. 5, является детерминированным (а потому не требует преобразования) и не нуждается в минимизации.

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

Таким способом можно написать программу, моделирующую работу КА, показанного на рис. 5. Ниже приводится текст функции на языке Паскаль, его реализующей. Результат функции истинный (True), если входная цепочка символов принадлежит входному языку автомата. Границей цепочки считается символ с кодом 0 (#0), в функции он искусственно добавляется в конец цепочки.

В этой программе переменная iState отображает текущее состояние автомата, переменная i является счетчиком символов входной строки. Конечно, рассмотренная программа может быть оптимизирована (например, можно сразу же прекращать разбор по обнаружению ошибки), но в данном примере оптимизация не выполнялась, чтобы можно было четко отследить соответствие между программой и построенным автоматом.

 

type

  TAutoState = ( AUTO_N, AUTO_Z, AUTO_X,
            AUTO_Q, AUTO_H, AUTO_G,
            AUTO_ER, AUTO_S );

 

function RunAuto (sInput: string): Boolean;

var

  iState : TAutoState;

  i : integer;

begin

  sInput := sInput + #0;

  iState := AUTO_N;

  i := 0;

  repeat

           i := i + 1;

     case iState of

     AUTO_N:

       case sInput[i] of

          ‘0’:   iState := AUTO_Z;

          ‘1’..’9’: iState := AUTO_G;

          else   iState := AUTO_ER;

       end;

     AUTO_Z:

       case sInput[i] of

          ‘0’..’7’: iState := AUTO_Q;

          ‘8’,’9’:  iState := AUTO_G;

          ‘x’:   iState := AUTO_X;

          #0:    iState := AUTO_S;

          else   iState := AUTO_ER;

       end;

     AUTO_X:

       case sInput[i] of

          ‘0’..’9’: iState := AUTO_H;

          ‘A’..’F’: iState := AUTO_H;

          else   iState := AUTO_ER;

       end;

     AUTO_Q:

       case sInput[i] of

          ‘0’..’7’: iState := AUTO_Q;

          ‘8’,’9’:  iState := AUTO_G;

          #0:    iState := AUTO_S;

          else   iState := AUTO_ER;

       end;

     AUTO_H:

       case sInput[i] of

          ‘0’..’9’: iState := AUTO_H;

          ‘A’..’F’: iState := AUTO_H;

          #0:    iState := AUTO_S;

          else   iState := AUTO_ER;

       end;

     AUTO_G:

       case sInput[i] of

          ‘0’..’9’: iState := AUTO_G;

          #0:    iState := AUTO_S;

          else   iState := AUTO_ER;

       end;

     AUTO_ER:    iState := AUTO_ER;

     end {case};

  until (sInput[i] = #0);

  RunAuto := (iState = AUTO_S);

end; { RunAuto }

 

Построение КА вручную на основе грамматик, содержащих небольшое количество правил (до нескольких десятков), не вызывает затруднений. Однако для грамматик реальных языков построение распознавателя вручную может представлять проблему из-за значительного количества состояний КА. Поэтому существуют средства, позволяющие автоматизировать построение лексического анализатора (например, программа LEX [1, 9, 18]).

В общем случае задача сканера несколько шире, чем просто проверка цепочки символов лексемы на соответствие ее входному языку. Сканер должен выполнить те или иные действия по запоминанию распознанной лексемы (занесение ее в таблицу лексем). Набор действий определяется реализацией компилятора. Обычно эти действия выполняются сразу же по обнаружению конца распознаваемой лексемы, поэтому их несложно вставить в соответствующие места рассмотренной выше программы-сканера (в те операторы, где обнаруживается символ #0).

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

·      проанализировать возможные входные лексемы и выбрать способ определения границ лексем;

·      исходя из выбранного способа определения границ лексем, выбрать метод взаимодействия лексического и синтаксического анализаторов;

·      построить КА, составляющий основу лексического анализатора;

·      привести построенный КА к детерминированному виду;

·      минимизировать полученный детерминированный КА;

·      создать программную функцию, реализующую работу КА;

·      дополнить реализованную функцию структурами данных, используемыми для хранения информации о лексемах (таблицы лексем и таблицы идентификаторов), обеспечить заполнение этих структур в процессе функционирования КА.

Алгоритм работы простейшего сканера можно описать так:

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

·      для выбранной части входного потока выполняется функция распознавания лексемы;

·      при успешном распознавании информация о выделенной лексеме заносится в таблицу лексем, и алгоритм возвращается к первому этапу;

·      при неуспешном распознавании выдается сообщение об ошибке, а дальнейшие действия зависят от реализации сканера - либо его выполнение прекращается, либо делается попытка распознать следующую лексему (идет возврат к первому этапу алгоритма).

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

Порядок выполнения работы

1.        Получить вариант задания у преподавателя.

2.        Построить КА на основе регулярной грамматики (по результатам лабораторной работы №2).

3.        Подготовить и защитить отчет.

4.        Написать и отладить программу на ЭВМ.

5.        Сдать работающую программу преподавателю.

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

Требования к оформлению отчета

Отчет должен содержать следующие разделы:

·      Краткое изложение цели работы.

·      Задание по лабораторной работе с описанием своего варианта и используемого вида комментариев.

·      Описание КА или граф КА для распознавания лексем (в соответствии с вариантом задания на основе результатов лабораторной работы №2).

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

·      Текст программы (оформляется только при необходимости по согласованию с преподавателем).

·      Выводы по проделанной работе.

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

Допускается оформлять единый (совместный) отчёт для лабораторных работ №2 и №3.

Основные контрольные вопросы

1.       Дайте определение цепочки символов, алфавита, языка. Что такое синтаксис и семантика языка?

2.       Какие существуют методы задания языков?

3.       Что такое транслятор, компилятор, интерпретатор? В чём их различие между собой?

4.       Расскажите об общей структуре компилятора.

5.       Что такое лексема? Расскажите, какие типы лексем существуют в языках программирования.

6.       Какие функции выполняет лексический анализ в процессе компиляции?

7.       Какие преимущества дает компилятору наличие лексического анализатора?

8.       Расскажите о проблемах, возникающих при построении лексического анализатора.

9.       Как могут быть связаны лексический и синтаксический анализаторы?

10.   Что такое грамматика? Дайте определения грамматики.

11.   Как выглядит описание грамматики в форме Бэкуса-Наура.

12.   Какие классы грамматик существуют?

13.   Что такое регулярные грамматики? В чём их особенности?

14.   Что такое конечный автомат?

15.   Дайте определение детерминированного и недетерминированного КА. Расскажите о возможности преобразования недетерминированного КА в детерминированный.

16.   Какие проблемы необходимо решить при построении сканера на основе конечного автомата?

Варианты заданий

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

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

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

Варианты заданий полностью соответствуют вариантам заданий по лабораторной работе №2.