 |
Постфиксная польская запись
|
|
|
|
Лекция 16
Синтаксический анализ
Вторым этапом компиляции является синтаксический анализ. На вход блока синтаксического анализа поступает лексическая свертка программы, сформированная лексическим анализатором. Синтаксический анализатор проверяет, удовлетворяет ли структура предложений синтаксису языка программирования, и если да, то формирует синтаксическое дерево программы, которое легко может быть переведено в последовательность машинных команд.
Правила составления предложений языка программирования описывает его грамматика. Грамматика строится на некотором алфавите. В синтаксическом анализе символами алфавита являются лексемы. Предложения являются последовательностью лексем (цепочкой лексем). Если х и у – две цепочки, то цепочка ху называется конкктенацией (или сцеплением). Цепочка х называется префиксом цепочки ху, а у – суффиксом цепочки ху. Цепочка z называется подцепочкой цепочки xzy. Пустую цепочку, не содержащую ни одного символа, обозначают е.
Под (порождающей) грамматикой понимается черверка объектов: (T, N, Z, P). Т– множество терминальных символов (терминальными символами являются лексемы языка); N – множество нетерминальных символов (нетерминальными являются символы, составленные по особым правилам из терминальных); ни один символ не может быть одновременно терминальным и нетерминальным, т.е. TÇN=Æ. Z – выделенный нетерминальный символ, называемый начальным символом или аксиомой грамматики. Р – множество правил составления предложений (эти правила называются продукциями). Продукции языка обычно записываются в форме, предложенной разработчиками АЛГОЛ-60 Бэкусом и Науром:
|
|
|
< символ 1> ::= < символ 2> или < символ 1> ® < символ 2>
Такая форма записи получила название бэкусо-науровской формы, или Бэкусовской нормальной формы, сокращенно БНФ. Слева записывается нетерминальный символ, справа может находиться либо нетерминальный, либо терминальный символ, или их конкатенация. Знак ::= или ® означает возможность замены цепочки < символ 1> на цепочку < символ 2>. Нетерминальные символы записываются в треугольных скобках <>, терминальные – без скобок.
Множество правил U ::= X, U ::= Y, U ::= Z с одинаковыми левыми частями можно записать так: U ::= X | Y | Z. Вертикальная черта означает альтернативный выбор.
Пример:
правила составления арифметических выражений с простейшими арифметическими операциями.
<АРИФ_ВЫР> ::= <ОПЕРАНД><ЗНАК><ОПЕРАНД>
<ЗНАК> ::= <ЗНАК_ПЛЮС_МИНУС> | * | /
<ЗНАК_ПЛЮС_МИНУС> ::= + | –
<ОПЕРАНД> ::= <АРИФ_ВЫР> | <ЧИСЛО_БЕЗ_ЗНАКА> | идентификатор
<ЧИСЛО_БЕЗ_ЗНАКА> ::= <ВЕЩЕСТВЕННОЕ_ЧИСЛО> | целое_число
<ВЕЩЕСТВЕННОЕ_ЧИСЛО> ::=. целое_число | целое_число. целое_число | целое_число.
целое_число Е<ЗНАК_ПЛЮС_МИНУС> целое_число
Здесь терминальными символами являются идентификатор, целое_число, символы. +–*/.
Нетерминальные символы: <АРИФМЕТ_ВЫРАЖ>, <ОПЕРАНД>,<ЗНАК> и т.д.
Практическое применение грамматики связано с решением проблемы распознавания – принадлежит ли цепочка символов (лексем) языку, порожденному этой грамматикой, или нет.
Пример: выяснить, удовлетворяет ли цепочка А*В–1.5 описанной выше грамматике?
Для лексем заданной цепочки последовательно применяем описанные выше правила:
<АРИФ_ВЫР>::= <ОПЕРАНД> <ЗНАК> <ОПЕРАНД>
<АРИФ_ВЫР>::= <АРИФ_ВЫР> – <ЧИСЛО_БЕЗ_ЗНАКА>
<АРИФ_ВЫР>::= <АРИФ_ВЫР> – <ВЕЩЕСТВЕННОЕ_ЧИСЛО>
<АРИФ_ВЫР>::= <АРИФ_ВЫР> – целое_число. целое_число
<АРИФ_ВЫР>::= <ОПЕРАНД><ЗНАК><ОПЕРАНД> – целое_число. целое_число
|
|
|
<АРИФ_ВЫР>::= идентификатор*идентификатор – целое_число. целое_число (*)
Последовательная подстановка продукций называется выводом или разбором.
Продукция (*) содержит только терминальные символы. Продукция, выводимая из начального символа грамматики Z и содержащая только терминальные символы, называется предложением. Язык образуют множество предложений.
Правила составления предложений можно записывать различными способами. Первый – с помощью рассмотренной выше БНФ. Более удобной оказывается скобочная форма записи. Скобочная форма использует обозначения:
= соответствие левой и правой частей (аналогично ::= или ®)
| возможность альтернативного выбора;
{ } указание альтернативных конструкций, варианты разделяются |.
[ ] указание необязательных конструкций;
… многократное повторение предыдущего элемента (количество повторений
не ограничено)
KEYWORD обязательные ключевые слова подчеркиваются, необязательные – нет.
Правило записи вещественного числа в скобочной форме выглядит так:
<ВЕЩЕСТВЕННОЕ_ЧИСЛО> =
= [{+|–}] { целое_число. [ целое_число ] |. целое_число } [E[{+|–}] целое_число ]
Третий способ представления грамматики – с помощью синтаксического графа, при составлении которого приняты обозначения:
терминальный символ;
выбор одного из символов;
 |
необязательное повторение символа;
 |
многократное повторение символа.
Синтаксический граф легко получается из скобочной формы записи.
Правила записи вещественных чисел в графовой форме выглядят так:
Здесь ЦЧ – целое число.
На базе синтаксического графа строится синтаксический распознаватель (конечный автомат). Для построения КА синтаксический граф размечают – расставляют состояния – и по ним строят таблицу переходов КА. Для нашего примера
 |
| № сост. | + | – | ЦЧ | . | Е | T | |
| – | |||||||
| – | |||||||
| – | |||||||
| – | |||||||
| – | |||||||
| – | |||||||
| – | |||||||
| – | |||||||
| – | |||||||
| + |
|
|
|
Синтаксический разбор программы производится следующим образом. На основе всевозможных предложений языка программирования строится конечный автомат (точно так же, как для лексического анализа, но этот КА дополняется магазином – структурой, работающей по принципу LIFO, в которую можно помещать и выталкивать лексемы)). Затем лексическая свертка программы, рассматриваемая как поток символов, обрабатывается на этом конечном автомате. Если последовательность лексем переводит КА из начального состояния в одно из конечных, то предложение составлено синтаксически верно, в противном случае выдается сообщение об ошибке. В результате синтаксического анализа формируется синтаксическое дерево программы.
Синтаксическое дерево программы представляется в ЭВМ обычно одним из следующих способов:
· постфиксная польская запись;
· тетрады;
· триады и др.
Постфиксная польская запись
Её еще называют польской инверсной записью (ПОЛИЗ). Эта форма записи была предложена польским логиком Я.Лукашевичем. Обычная форма записи арифметических выражений, при которой знак операции стоит между операндами (А+В), называется инфиксной. В постфиксной записи знак операции следует сразу за операндами. Например, выражение А*В+С/D будет выглядеть АВ*СD/+. Польская форма записи не требует скобок, и просто и точно указывает порядок выполнения операций.
Перевод из инфиксной в постфиксную польскую запись несложен, он основан на следующих правилах:
1. Идентификаторы в польской записи следуют в том же порядке, что и в инфиксной записи;
2. Операторы в польской записи следуют в том порядке, в каком они должны выполняться (слева направо);
3. Операторы располагаются непосредственно за своими операндами.
Примеры бинарных операций:
| Инфиксная запись | Постфиксная запись |
| A:=B (присваивание) A+B (арифметические операции + – * /) A or B (бинарные логические операции or, and, xor) | AB:= AB+ AB OR |
Унарный минус и другие унарные операторы можно представлять двумя способами: либо записывать их как бинарные операторы, т.е. вместо –В писать 0–В, либо для унарного минуса можно ввести новый символ, например @. Таким образом, –A*(B+C) можно было бы записать как A@BC+*.
|
|
|
Следуя описанным правилам, можно представлять в польской записи более сложные операторы, такие как условные и безусловные переходы, циклы.
Безусловный переход – это унарная операция, которую будем обозначать BRL (BRanch to Label). Переход GOTO < метка > будет выглядеть: < метка > BRL.
Условный переход IF < выражение > THEN < оператор > в польской записи имеет вид:
< выражение > <метка_указывающая_на_ оператор > BZ. Если операнд < выражение > равен 0, то следующей берется команда, на которую указывает метка; в противном случае работа продолжается как обычно. Здесь BZ (Branch to Zero) – “знак” операции перехода по условию < выражение >=0. Можно ввести такие операторы переходов как BP (Branch to Positive) – переход по положительному результату, BM (Branch to Minus) – переход по минусу, смешанные условия: BMZ (минус или ноль), BPZ (положительное значение или ноль) и т.д.
Условный переход вида IF < выраж-е >=0 THEN < оператор 1> ELSE < оператор 2>
в описанных конструкциях запишется:
< выраж-е > <метка_на_оператор_1> BZ < оператор 2> <метка_обход> BRL < оператор 1>
Цикл FOR i:=1 TO n DO < оператор > в постфиксной записи будет выглядеть так:
i 1:= i n – <метка_конец_цикла> BP < оператор > i i 1:= <метка_начало_цикла> BRL
В ПОЛИЗ имеется еще несколько общепринятых конструкций. Это BLOCK (начало блока) и BLCKEND (конец блока). Они используются для отметки тела подпрограмм (как begin–end). Эти инструкции не имеют операндов, носят информативный характер и предназначены для генератора кода.
Для обращения к элементам массива в польской записи имеется команда вычисления адреса элемента массива SUBS. Для одномерного массива она имеет формат:
< выражение_для_индекса _1> < имя_массива > SUBS
для двумерного массива
< выражение_для_индекса _1> < выражение_для_индекса _2> < имя_массива > SUBS
и т.д. для массива большей размерности (размерность массива запоминается на этапе синтаксического анализа предложения, описывающего массив).
Пример:
Procedure SomeProc;
var i: integer;
A: array[1..10] of real;
s1,s2: real;
begin
s1:=0; s2:=0;
for i:=1 to 10 do
begin
if A[i]>0 then s1:=s1+A[i]
else s2:=s2+A[i]
end
end;
Постфиксная польская запись:
в скобках слева указаны порядковые номера крайних слева символов (!) строки, эти номера позиций используется в качестве меток в операторах перехода.
(1) BLOCK
(2) s1 0:= s2 0:=
(8) i 1:=
(11) i 10 – (46) BP
(16) i A SUBS 0 – (32) BMZ
(23) s1 s1 i A SUBS +:= (39) BRL
(32) s2 s2 i A SUBS +:=
(39) i i 1 -:= (11) BRL
(46) BLCKEND
Представление польской записи в машине похоже на представление лексической свертки программы: для каждого символа польской записи отводится две ячейки памяти, в первой хранится код типа символа (служебное слово польской записи, идентификатор, числовая константа или метка), во второй – индекс в таблице символов соответствующего типа.
|
|
|
Кодирование синтаксического дерева программы с помощью тетрад.
Для бинарной операции удобной формой представления является тетрада
(< оператор >, < операнд 1>, < операнд 2>, < результат >)
где < операнд 1>, < операнд 2>, < результат > определяют аргументы и результат. Таким образом, A*B можно представить как (*,A,B,T). Здесь Т – несуществующая (абстрактная) переменная для хранения промежуточного результата. Она описывается в таблицах символов наряду с переменными-идентификаторами, но снабжается признаком, говорящим о том, что генератору кода не следует резервировать под нее память.
Выражение A*B+C*D представляется в виде последовательности следующих тетрад:
(*, A, B, T1)
(*, C, D, T2)
(+, T1, T2, T3)
Унарные операторы также оформляются в виде тетрад, в которых место под несуществующий операнд остается пустым. Например, унарный минус –А записывается (–, А,, Т). Ниже приведена таблица тетрад с другими, неарифметическими операторами.
| Тетрада | Комментарий |
| (BLOCK,,,) (BLCKEND,,,) (:=, P1,,P3) (Ä, P1, P2, P3) (BRL, i,,) (B x, i, P1, P2) | Начало блока Конец блока Присваивание P1®P3 Бинарная арифметическая операция P1ÄP2®P3. Знак Ä означает любую из операций: + – * / Безусловный переход на i -ю тетраду Условный переход. B x – любое из значений BG, BL, BE. Выполняется переход на i -ю тетраду, если значение, описанное в Р1 больше (BG), меньше (BL) или равно (BE) значению Р2. |
Пример индексирования двумерной матрицы с помощью тетрад:
var A: array [1..N] of integer; (…) C:=A[i,j];
(*,i,N,T1)
(+,T1,j,T2)
(:=,A[T2],,C)
Запись программы в виде тетрад более удобна при проведении оптимизации, чем польская запись.
|
|
|
