Алексей Молчанов - Системное программное обеспечение. Лабораторный практикум

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

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

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

Примечание.

• Римскими числами считать последовательности заглавных латинских букв X, V и I;

• шестнадцатеричными числами считать последовательность цифр и символов «а», «Ь», «с», «d, „е“ и „f“, начинающуюся с цифры (например: 89, 45ас9, 0abc4);

• задание по лабораторной работе № 2 взаимосвязано с заданием по лабораторной работе № 3, для уточнения состава входного языка можно посмотреть грамматику, заданную в работе № 3 по соответствующему варианту.

В качестве задания для примера возьмем входной язык, который содержит набор условных операторов условия типа if… then… else и if… then, разделенных символом; (точка с запятой). Эти операторы в качестве условия содержат логические выражения, построенные с помощью операций or, xor и and, операндами которых являются идентификаторы и целые десятичные константы без знака. В исполнительной части эти операторы содержат или оператор присваивания переменной логического выражения (:=), или другой условный оператор.

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

Описанный выше входной язык может быть построен с помощью КС-грамматики G({if,then,else,a,=,or,xor,and,(,),},{S,F,E,D,C},P,S) с правилами Р:

S → F;

F → if E then T else F | if E then F | a:= E

T → if E then T else T | a:= E

E → E or D | E xor D | D

D → D and С | С

С → a | (E)

Описание грамматики построено в форме Бэкуса—Наура. Жирным шрифтом в грамматике и в правилах выделены терминальные символы.

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

Задача лексического анализатора для описанного выше языка заключается в том, чтобы распознавать и выделять в исходном тексте программы все лексемы этого языка. Лексемами данного языка являются:

• шесть ключевых слов языка (if, then, else, or, xor и and);

• разделители: открывающая и закрывающая круглые скобки, точка с запятой;

• знак операции присваивания;

• идентификаторы;

• целые десятичные константы без знака.

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

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

• идентификатор – это произвольная последовательность малых и прописных букв латинского алфавита (от А до Z и от а до z), цифр (от 0 до 9) и знака подчеркивания (_), начинающаяся с буквы или со знака подчеркивания;

• целое десятичное число без знака – это произвольная последовательность цифр (от 0 до 9), начинающаяся с любой цифры.

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

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

Рис. 2.1. Фрагмент графа переходов КА для распознавания всех лексем, кроме ключевых слов.

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

На рис. 2.2 изображен фрагмент графа переходов КА, отвечающий за распознавание ключевых слов if и then (этот фрагмент имеет ссылки на состояния, изображенные на рис. 2.1). Аналогичные фрагменты можно построить и для других ключевых слов.

Рис. 2.2. Фрагмент графа переходов КА для ключевых слов if и then.

На фрагментах графа переходов КА, изображенных на рис. 2.1 и 2.2, приняты следующие обозначения:

• А– любой алфавитно-цифровой символ;

• А(*) – любой алфавитно-цифровой символ, кроме перечисленных в скобках;

• П– любой незначащий символ (пробел, знак табуляции, перевод строки, возврат каретки);