Компиляция арифметических выражений при восходящем разборе

Среди многообразия грамматик для представления выражений имеется «удачный» вариант, в котором синтаксису каждой операции соответствует отдельное правило, включающее в себя терминальный символ операции и нетерминалы операндов. Эта грамматика применима в восходящем анализаторе, основанном на методе «свертка-перенос». Синтаксическое дерево, построенное в такой грамматике, обладает следующими свойствами:

· первичные операнды (константы, идентификаторы) являются терминальными вершинами синтаксического дерева;

· каждой операции соответствует свое правило: левая часть его соответствует нетерминалу – результату, нетерминалы правой части – входным операндам, терминал, обозначающий операцию, находится в правой части правила;

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

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

Наиболее просто спроецировать эти идеи на восходящие методы синтаксического анализа:

· cтек распознавателя в этом случае идентичен стеку операндов;

· свертка правой части правила приводит к генерации соответствующей команды, извлекающей из стека операнды и помещающей результат туда же;

· правила, выполняющие приведение первичных операндов (констант, идентификаторов), помещают их значения (или адреса) в стек;

· генерируемая в процессе сверток последовательность команд стековой машины пишется в последовательный поток (последовательность сверток идентична последовательности выполения).

Пусть некоторый условный процессор имеет следующий набор команд для работы со стеком:

· PUSH(V) – загрузить значение V в стек;

· V=POP() – извлечь значение из вершины стека;

· V=GET(n) – получить значение n-го элемента относительно вершины стека, не удаляя его оттуда.

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

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

Специфика l-value также может быть учтена в коде, ориентированном на стек операндов. Для операнда l-value в стеке может храниться ссылка (адрес), а иначе – само значение операнда.