Построение отдельных фаз компиляции (стр. 3 из 4)
S®BEGIN5 ┴|WHILE5 ┴|DO2 ┴|THEN4 ┴|IF2 ┴|VAR ┴|PROG4 ┴|OR2 ┴| NOT3 ┴|AND3┴|END3 ┴|END4 ┴|ELSE4 ┴|CONST6 ┴|ASSI2 ┴| ADD ┴| SEMI ┴| SUB┴| UMN ┴|OPEN ┴|CLOSE ┴|RAVN ┴|MEN ┴| BOL ┴|COMM2 ┴
Результатом работы лексического анализатора является перечень всех найденных в тексте исходной программы лексем с учетом их характеристик. Этот перечень лексем предоставляется в виде таблицы лексем. Информация об идентификаторах и константах помещается в таблицу идентификаторов.
С теоретической точки зрения лексический анализатор не является обязательной частью компилятора. Все его функции могут выполняться на этапе синтаксического разбора. Но так как он упрощает работу с текстом исходной программы на этапе разбора и сокращает объем обрабатываемой информации, отбрасывая всю незначащую информацию (комментарии, пробел, табуляцию, перевод строки), в данной курсовой работе он используется.
2.4. Результаты работы лексического анализатора
Программа выполняет лексический анализ входного текста в соответствие с заданной грамматикой. Результатом выполнения лексического анализа является таблица лексем с указанием их типов, а также таблица идентификаторов, сформированная методом цепочек. В таблице лексем имеется поле «Адрес», в котором указывается ссылка на место расположения идентификатора в таблице идентификаторов.
Экранная форма работы лексического анализатора представлена на рис.2.1.
Рис. 2.1. Экранная форма работы лексического анализатора
Таблица лексем служит базой для проведения синтаксического анализа и построения дерева вывода в третьей части курсовой работы.
Лексическая ошибка возникает при обнаружении незакрытого комментария, неверного символа в лексеме или если лексема незавершенна (не обнаружен признак окончания лексемы).
Экранная форма при обнаружении лексической ошибки представлена на рис. 2.2.
Рис. 2.2. Экранная форма при обнаружении лексической ошибки
В случае обнаружения лексической ошибки программа выдает сообщение об ошибке с указанием ее места в исходном тексте, работа лексического анализатора останавливается.
3. Проектирование синтаксического анализатора
3.1. Исходные данные
На данном этапе разработанная программа должна выделять и проверять синтаксические конструкции входного языка, то есть выполнить синтаксический анализ входного текста, результатом которого является цепочка вывода, на основе которой строится дерево вывода. На вход синтаксического анализатора поступает таблица лексем, сформированная на этапе лексического анализа. Также программа должна выдавать сообщения о наличии во входном тексте ошибок, которые могут быть обнаружены на этапе синтаксического анализа, с указанием их позиций во входном тексте. При обнаружении ошибки выполнение синтаксического анализа должно прекратиться.
Исходная КС-грамматика имеет вид:
G ({ prog, end., begin, end, while, do, if, then, else, and, or, not, =, <, >, (, ), -, +, ++, a, c, ;, :=}, {S, L, O, B, C, D, E, F}, P, S)
P:
S → prog L end.
L → O | L;O | L;
O → if (B) then O else O| if O then O| begin L end | while (B) do 0 | a:=E | a++
B → B or C | C
C → C and D | D
D → E<E | E>E | E=E | (B) | not(B)
E→E–F | E+F | F
3.2. Построение синтаксического анализатора
Перед синтаксическим анализатором стоят две основные задачи: проверить правильность конструкций входной цепочки, которая представляется в виде уже выделенных слов входного языка, и преобразовать ее в дерево вывода – вид, удобный для дальнейшей семантической обработки и генерации кода.
Основой для построения синтаксического анализатора являются автоматы с магазинной памятью, или МП-автоматы. В общем виде МП-автомат можно определить следующим образом:
(Q, V, Z, δ, q0, z0, F), (3.1)
где: Q – множество состояний автомата;
V – алфавит входных символов автомата;
Z – специальный конечный алфавит магазинных символов автомата;
δ – функция переходов автомата;
F – множество конечных состояний;
q0 – начальное состояние автомата;
z0 – начальный символ магазина (стека).
Конфигурация МП-автомата определяется тремя параметрами: состоянием автомата, текущим символом входной цепочки (положение указателя в цепочке) и содержимым стека.
При выполнении перехода МП-автомата из одной конфигурации в другую из стека удаляются верхние символы, соответствующие условию перехода, и добавляется цепочка, соответствующая правилу перехода. Первый символ цепочки становится верхушкой стека. Если при окончании цепочки автомат находится в одном из заданных конечных состояний, а стек пуст, цепочка считается принятой, иначе цепочка символов не принимается.
Для построения распознавателя для языка, заданного КС-грамматикой, воспользуемся алгоритмом «сдвиг-свертка»:
- если на верхушке стека МП-автомата находится цепочка символов g, то ее можно заменить на нетерминальный символ A при условии, что в грамматике языка существует правило вида A → g, не сдвигая при этом считывающую головку автомата («свертка»);
- если считывающая головка автомата обозревает некоторый символ входной цепочки α, то его можно поместить в стек, сдвинув при этом головку на одну позицию вправо («сдвиг»).
Распознаватель на основе алгоритма «сдвиг-свертка» является восходящим распознавателем: он читает входную цепочку символов слева направо, строит правосторонний вывод, а дерево вывода строит снизу вверх (от корневых вершин к корню).
Для более легкого построения распознавателя, преобразуем исходную КС-грамматику в грамматику операторного предшествования (это такая приведенная КС-грамматика, в которой правые части всех правил не содержат смежных нетерминальных символов и для которой отношения предшествования можно задать на множестве терминальных символов). При этом для каждой упорядоченной пары терминальных символов определено не более чем одно из трех следующих отношений (=., <., .>).
На основе множества правил грамматики P определим множества крайних левых и крайних правых символов L(U), R(U) относительно всех нетерминальных символов грамматики (табл. 3.1).
Таблица 3.1.
Множества крайних левых и крайних правых нетерминальных
символов L(U), R(U) относительно всех нетерминальных символов грамматики
| Символ (U) | Шаг 1 | Шаг 2 | ||
| L(U) | R(U) | L(U) | R(U) | |
| F | (, a, c | ), a, c | (, a, c | ), a, c |
| E | E, F | F | E, F, (, a, c | F, ), a, c |
| D | E, (, not | E, ) | E, (,a, c, not | E, F, ),a, c |
| C | C, D | D | C, D, E, F, (, a, c, not | D, E, F, ), a, c |
| B | B, C | C | B, C, D, E, F, (, a, c, not | C, D, E, F, ), a, c |
| O | if, begin, while, a | O, E, end, ++ | if, begin, while, a | O, E, F, ), a, c, end, ++ |
| L | O, L | O, ; | O, L, if, begin, while, a | O, E, F ,), a, c, end, ++, ; |
| S | prog | end. | prog | end. |
На основе множества правил грамматики P и полученных множеств крайних левых и крайних правых символов L(U), R(U) построим множества крайних левых и крайних правых терминальных символов Lt(U), Rt(U) относительно всех нетерминальных символов грамматики (табл. 3.2).
Таблица 3.2.
Множества крайних левых и крайних правых
терминальных символов Lt(U), Rt(U)
| Символ (U) | Шаг 1 | Шаг 2 | ||
| Lt(U) | Rt(U) | Lt(U) | Rt(U) | |
| F | (, a, c | ), a, c | (, a, c | ), a, c |
| E | -, + | -, + | (, a, c, -, + | ), a, c, -, + |
| D | <, >, =, (, not | <, >, =, ) | (, a, c, -, +, <, >, =, not | ), a, c, -, +, <, >, = |
| C | and | and | (, a, c, -, +, <, >, =, not, and | ), a, c, -, +, <, >, =, and |
| B | or | or | (, a, c, -, +, <, >, =, not, and, or | ), a, c, -, +, <, >, =, and, or |
| O | if, begin, while, a | else, then, end, do, :=, ++ | if, begin, while, a | ), a, c, -, +, else, then, end, do, :=, ++ |
| L | ; | ; | if, begin, while, a, ; | ), a, c, -, +, else, then, end, do, :=, ++, ; |
| S | prog | end. | prog | end. |
На основе полученных множеств и правил грамматики G построим матрицу операторного предшествования (приложение В).