Построение отдельных фаз компиляции

     Лексемами данного языка являются:

• ключевые слова (prog, end., begin, end, while ,do, if, then, else);
• скобки ( «(», «)» );
• оператор присваивания ( := );
• операторы сравнения ( >, <, = );
• разделитель ( ; );
• арифметические операции ( +, –, ++ );
• шестнадцатеричные константы (тип данных word);
• идентификаторы;
• логические операции (or, not, and).

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

     2.2. Принцип работы лексического анализатора

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

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

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

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

     Любой КА может быть задан с помощью  пяти параметров:

М(Q, V,δ,q₀,F),          (2.1)

где: Q – конечное множество состояний автомата;

     V – конечное множество допустимых входных символов (алфавит автомата);

     δ – функция переходов, отображающая декартовое произведение множеств V´Q во множество подмножеств Q: R(Q);

     q₀ Q – начальное состояние автомата;

     F Q – непустое множество конечных состояний автомата.

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

      Графически  автомат отображается нагруженным  однонаправленным графом, в котором  вершины представляют состояния, дуги отображают переходы  из одного состояния в другое, а пометки дуг соответствуют функции перехода. Если функция перехода предусматривает переход из состояния q_i в q_i+1 по нескольким символам, то между ними строится одна дуга, которая помечается всеми символами, по которым происходит переход из q_i в q_i+1. 

     2.3. Схема распознавателя

     Распознавателем лексем входного языка является конечный детерминированный автомат без внешней памяти (приложение Б).

     Начальное состояние автомата обозначено H, конечное S. В случае ошибочной входной цепочки автомат попадает в состояние ошибки ERR. При этом работа автомата останавливается. Остальные состояния автомата определяются допустимыми для компилятора исходного языка лексемами.

     В графе также используются следующие  обозначения:

• ┴ – пробел, табуляция, перевод строки, +, –, =, <, >, (, ), ;, :, {
• ┴c – перевод строки
• x0 – любой символ
• x1 – любой символ, кроме символа *
• x2 – любой символ, кроме символа }
• x3 – любой символ, кроме символа ┴
• x4 – любой символ, кроме символа h
• x5 – любой символ, кроме символов 0..9, A..F
• x6 – любой символ, кроме символа =
• x7 – любой символ, кроме символа +
• x8 – символы A..Z, c, f..h, j..m, q..s, u, v, x..z, _
• x9 –символы A..Z, a..d, f..z, _
• x10 – любой символ, кроме символов A..Z, a..z, _
• x11 – символы A..Z, a..f, h..z, _
• x12 – символы A..Z, a..h, j..z, _
• x13 – символы A..Z, a..g, i..z, _
• x14 – символы A..Z, a..z, _
• x15 – символы A..Z, a..k, m..z, _
• x16 – символы A..Z, a..m, o..z, _
• x17 – символы A..Z, a..e, g..z, _
• x18 –символы A..Z, a..q, s..z, _
• x19 – символы A..Z, a..n, p..z, _
• x20 – символы A..Z, a..s, u..z, _
• x21 – символы A..Z, a..c, e..z, _
• x22 – символы A..Z, a..k, m, o..z, _
• x23 – символы A..Z, a..r, t..z, _
• x24 – любой символ, кроме символов A..Z, a..z, _, ┴
• x25 – символы A..F, 0..9
• x26 – любой символ, кроме символов A..Z, a..z, _, ┴, '.'

     Регулярная  грамматика входного языка в форме Бэкуса-Наура имеет вид:

     G ( {0..9, A..Z, a..z, +, – , <, >, =, (, ), ;, :, {, }, *, '.'}, {S, H, BEGIN1, BEGIN2, BEGIN3, BEGIN4, BEGIN5, WHILE1, WHILE2, WHILE3, WHILE4, WHILE5, THEN1, THEN2, THEN3, THEN4, IF1, IF2, PROG1, PROG2, PROG3, PROG4, VAR, NOT1, NOT2, NOT3, AND1, AND2, AND3, OR1, OR2, DO1, DO2, E1, END2, END3, END4, ELSE2, ELSE3, ELSE4}, P, S )

     P:

     PROG1 ® p     PROG2 ® PROG1 r

     PROG3 ® PROG2 o    PROG4 ® PROG3 g

     BEGIN1 ® b     BEGIN2 ® BEGIN1 e

     BEGIN3 ® BEGIN2 g    BEGIN4 ® BEGIN3 i

     BEGIN5 ® BEGIN4 n    WHILE1 ® w

     WHILE2 ® WHILE1 h    WHILE3 ® WHILE2 i

     WHILE4 ® WHILE3 l    WHILE5 ® WHILE4 e

     DO1 ® d      DO2 ®DO1 o

     IF1 ® i      IF2 ®IF1 f

     THEN1 ® t      THEN2 ® THEN1 h

     THEN3 ® THEN2 e    THEN4 ® THEN3 n

     E1 ® e      ELSE2 ® E1 l

     ELSE3 ® ELSE2 s    ELSE4 ® ELSE3 e

     END2 ® E1 n     END3 ® END2 d

     END4 ® END3 .     AND1 ® a

     AND2 ® AND1 n     AND3 ® AND2 d

     OR1 ® o      OR2 ® OR1 r

     CONST1 ® 0     CONST2 ® CONST1 x25

     CONST3 ® CONST2 x25   CONST4 ® CONST3 x25

     CONST5 ® CONST4 x25   CONST6 ® CONST5 h

     ASSI1 ® :      ASSI2 ® ASSI1 =

     SEMI ® ;      SUB ® –

     ADD ® +      INC ® ADD +

     OPEN ® (      CLOSE ® )

     RAVN ® =      MEN ® <

     BOL ® >      

     COMM1 ® {

     COMM2 ® COMM1 * | COMM2 x1 

     COMM3 ® COMM2 *

     COMM4 ® COMM3 }

VAR ® x8|BEGIN1 x9|BEGIN2 x11|BEGIN3 x12|BEGIN4 x16|BEGIN5 x14| VAR x14| WHILE1 x13|WHILE2 x12|WHILE3 x15|WHILE4 x9| IF1x17|     WHILE5 x14|E1 x22| THEN1 x13|THEN2 x9|THEN3 x16|THEN4 x14|  IF2 x14|PROG1 x18| PROG2 x19|PROG3 x11|PROG4 x14|OR1 x18|   OR2 x14| NOT1 x19|DO2 x14| NOT2 x20|NOT3 x14|AND1 x16|AND2 x21| AND3 x14|END2 x21| END3 x14|END4 x3|ELSE2 x23|ELSE3 x9|        DO1 x19|ELSE4 x14|

ERR ® BEGIN1 x10|BEGIN2 x10|BEGIN3 x10|BEGIN4 x24|BEGIN5 x10|   DO1 x10| WHILE1 x10|WHILE2 x10|WHILE3 x10|WHILE4 x10|  WHILE5 x24| DO2 x24| THEN1 x10| THEN2 x0|THEN3 x10|THEN4 x24| IF2 x24| VAR x24| PROG1 x10|PROG2 x10|PROG3 x10|PROG4 x24|   IF1 x10|OR1 x10|OR2 x24|E1 x10| NOT1 x10| NOT2 x10|NOT3 x24| AND1 x10|AND2 x10|AND3 x24|END2 x10| END3 x26|END4 x3| x3| ELSE2 x10|ELSE3 x10|ELSE4 x24|CONST1 x5|INC x3| CONST2 x5| CONST3 x5|CONST4 x5|CONST5 x4|CONST6 x3|ASSI1 x6| ASSI2 x3| SEMI x3|SUB x3|ADD x7|OPEN x3|CLOSE x3|RAVN x3|MEN x3|BOL x3| COMM1 x1|COMM2 ┴c|COMM3 x2|COMM4 x3