 |
Синтаксически управляемый перевод
|
|
|
|
На практике синтаксический, семантический анализ и генерация внутреннего представления программы часто осуществляются одновременно.
Существует несколько способов построения промежуточной программы.
Один из них, называемый синтаксически управляемым переводом, особенно прост и эффективен.
В основе синтаксически управляемого перевода лежит грамматика с действиями. Теперь, параллельно с анализом исходной цепочки лексем, будем выполнять действия по генерации внутреннего представления программы. Для этого дополним грамматику вызовами соответствующих процедур генерации.
Пример генерации внутреннего представления программы для М-языка.
Пусть есть грамматика, описывающая простейшее арифметическое выражение:
E → T {+T}
T → F {*F}
F → a | b | (E)
Тогда грамматика с действиями по переводу этого выражения в ПОЛИЗ будет такой:
E → T {+T <putchar('+')>}
T → F {*F <putchar('*')>}
F → a <putchar('a')> | b<putchar('b')> | (E)
Этот метод можно использовать для перевода цепочек одного языка в цепочки другого языка (что, собственно, мы и делали, занимаясь переводами в ПОЛИЗ цепочек лексем).
Например, с помощью грамматики с действиями выполним перевод цепочек языка
L1 = {0n1m | n>=0, m>0}
в соответствующие цепочки языка
L2 = {ambn | n>=0, m>0}:
Язык L1 можно описать грамматикой
S → 0S | 1A
A → 1A |ε
Вставим действия по переводу цепочек вида 0n1m в соответствующие цепочки вида ambn:
S → 0S <putchar('b')> | 1 <putchar('a')> A
A → 1 <putchar('a')> A |ε
Теперь при анализе цепочек языка L1 с помощью действий будут порождаться соответствующие цепочки языка L2.
Генератор внутреннего представления программы на М-языке
Каждый элемент в ПОЛИЗе - это лексема, т.е. пара вида (номер_класса, номер_в_классе). Нам придется расширить набор лексем:
|
|
|
1) будем считать, что новые операции (!,!F, R, W) относятся к классу ограничителей, как и все другие операции модельного языка;
2) для ссылок на номера элементов ПОЛИЗа введем лексемы класса 0, т.е. (0,p) - лексема, обозначающая p-ый элемент в ПОЛИЗе;
3) для того, чтобы различать операнды-значения-переменных и операнды-адреса-переменных (например, в ПОЛИЗе оператора присваивания), операнды-значения будем обозначать лексемами класса 4, а для операндов-адресов введем лексемы класса 5.
Будем считать, что генерируемая программа размещается в массиве P, переменная free - номер первого свободного элемента в этом массиве.
Для записи очередного элемента в массив P будем использовать функцию put_lex.
Кроме того, введем модификацию этой функции - функцию put_lex5, которая записывает лексему в ПОЛИЗ, изменяя ее класс с 4-го на 5-й (с сохранениемзначения поля value):
Пусть есть функция, которая по символьному изображению операции находит в таблицеограничителей соответствующую строку и формирует лексему вида (2, i), где i -номер найденной строки.
Генерация внутреннего представления программы будет проходить во время синтаксического анализа параллельно с контролем контекстных условий, поэтому для генерации можно использовать информацию, "собранную" синтаксическим и семантическим анализаторами; например, при генерации ПОЛИЗа выражений можно воспользоваться содержимым стека, с которым работает семантический анализатор.
Кроме того, можно дополнить функции семантического анализа действиями по генерации:
Действия, которыми нужно дополнить правило вывода оператора присваивания, также достаточно очевидны:
При генерации ПОЛИЗа выражений и оператора присваивания элементы массива P заполнялись последовательно. Семантика условного оператора if E then S1 else S2 такова, что значения операндов для операций безусловного перехода и перехода "по лжи" в момент генерации операций еще неизвестны.
|
|
|
Поэтому придется запоминать номера элементов в массиве P, соответствующих этим операндам, а затем, когда станут известны их значения, заполнять пропущенное.
ПОЛИЗ
ПОЛИЗ - Обратная польская нотация (ОПН) — форма записи математических выражений, в которой операнды расположены перед знаками операций.
Отличительной особенностью обратной польской нотации является то, что все аргументы расположены перед знаком операции. Запись набора операций состоит из последовательности операндов и знаков операций. Выражение читается слева направо. Когда в выражении встречается знак операции, выполняется соответствующая операция над двумя последними встретившимися перед ним операндами в порядке их записи. Результат операции заменяет в выражении последовательность её операндов и её знак, после чего выражение вычисляется дальше по тому же правилу.
Результатом вычисления выражения становится результат последней вычисленной операции.
Например, рассмотрим вычисление выражения 7 2 3 * - (эквивалентное выражение в инфиксной нотации: 7-2*3).
Первый по порядку знак операции — «*», поэтому первой выполняется операция умножения над операндами 2 и 3 (они стоят последними перед знаком). Выражение при этом преобразуется к виду 7 6 - (результат умножения — 6, — заменяет тройку «2 3 *»).
Второй знак операции — «-». Выполняется операция вычитания над операндами 7 и 6.
Вычисление закончено. Результат последней операции равен 1, это и есть результат вычисления выражения.
Особенности обратной польской записи следующие:
Порядок выполнения операций однозначно задаётся порядком следования знаков операций в выражении, поэтому отпадает необходимость использования скобок и введения приоритетов и ассоциативности операций.
В отличие от инфиксной записи, невозможно использовать одни и те же знаки для записи унарных и бинарных операций. Так, в инфиксной записи выражение 5 * (-3 + 8) использует знак «минус» как символ унарной операции (изменение знака числа), а выражение (10 - 15) * 3 применяет этот же знак для обозначения бинарной операции (вычитание). Конкретная операция определяется тем, в какой позиции находится знак. Обратная польская запись не позволяет этого: запись 5 3 - 8 + * (условный аналог первого выражения) будет интерпретирована как ошибочная, поскольку невозможно определить, что «минус» после 5 и 3 обозначает не вычитание; в результате будет сделана попытка вычислить сначала 5 - 3, затем 2 + 8, после чего выяснится, что для операции умножения не хватает операндов. Чтобы всё же записать это выражение, придётся либо переформулировать его, либо ввести для операции изменения знака отдельное обозначение.
|
|
|
Так же, как и в инфиксной нотации, в ОПН одно и то же вычисление может быть записано в нескольких разных вариантах. Например, выражение (10 - 15) * 3 в ОПН можно записать как 10 15 - 3 *, а можно — как 3 10 15 - *
Из-за отсутствия скобок обратная польская запись короче инфиксной. За этот счёт при вычислениях на калькуляторах повышается скорость работы оператора (уменьшается количество нажимаемых клавиш), а в программируемых устройствах сокращается объём тех частей программы, которые описывают вычисления. Последнее может быть немаловажно для портативных и встроенных вычислительных устройств, имеющих жёсткие ограничения на объём памяти.
Соотношения между типами языков:
(1) каждый регулярный язык является КС-языком, но существуют КС-языки,
которые не являются регулярными (например, L = {anbn | n>0}).
(2) каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые
не являются КС-языками (например, L = {anbncn | n>0}).
(3) каждый КЗ-язык является языком типа 0.
Замечание: УКС-язык, содержащий пустую цепочку, не является КЗ-языком.
Замечание: следует подчеркнуть, что если язык задан грамматикой типа k, то это не значит, что не существует грамматики типа k’ (k’>k), описывающей тот же язык. Поэтому, когда говорят о языке типа k, обычно имеют в виду максимально возможный номер k.
Например, грамматика типа 0G1 = ({0,1}, {A,S}, P1, S) и КС-грамматик* G2 = ({0,1}, {S}, P2, S), где
P1:S → 0A1 P2: S → 0S1 | 01
0A → 00A1
A → ε
описывают один и тот же язык L = L(G1) = L(G2) = { 0n1n | n>0}. Язык L называют КС-языком, т.к. существует КС-грамматика, его описывающая. Но он не является регулярным языком, т.к. не существует регулярной грамматики, описывающей этот язык.
|
|
|
Соотношения между типами грамматик:
(1) любая регулярная грамматика является КС-грамматикой;
(2) любая регулярная грамматика является УКС-грамматикой;
(3) любая КС- грамматика является УКС-грамматикой;
(4) любая КС-грамматика является КЗ-грамматикой;
(5) любая КС-грамматика является неукорачивающей грамматикой;
(6) любая КЗ-грамматика является грамматикой типа 0.
(7) любая неукорачивающая грамматика является грамматикой типа 0.
(8) любая УКС-грамматика является грамматикой типа 0.
Замечание: УКС-грамматика, содержащая правила вид* A → ε, не является КЗ-грамматикой и не является неукорачивающей грамматикой.
|
|
|
