![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Компиляция арифметических выражений при восходящем разборе
Среди многообразия грамматик для представления выражений имеется «удачный» вариант, в котором синтаксису каждой операции соответствует отдельное правило, включающее в себя терминальный символ операции и нетерминалы операндов. Эта грамматика применима в восходящем анализаторе, основанном на методе «свертка-перенос». Синтаксическое дерево, построенное в такой грамматике, обладает следующими свойствами: · первичные операнды (константы, идентификаторы) являются терминальными вершинами синтаксического дерева; · каждой операции соответствует свое правило: левая часть его соответствует нетерминалу – результату, нетерминалы правой части – входным операндам, терминал, обозначающий операцию, находится в правой части правила; · таким образом, нетерминалы синтаксического дерева соответствуют промежуточным результатам, а само синтаксическое дерево можно рассматривать как потоковую модель вычислений от концевых вершин в корню. Следовательно, последовательность выполнения действий при вычислении выражений может быть связана с обходом синтаксического дерева от потомков к предкам, а в качестве памяти для хранения промежуточных операндов может быть использован стек, работающий синхронно со стеком алгоритма обхода синтаксического дерева. Наиболее просто спроецировать эти идеи на восходящие методы синтаксического анализа: · cтек распознавателя в этом случае идентичен стеку операндов; · свертка правой части правила приводит к генерации соответствующей команды, извлекающей из стека операнды и помещающей результат туда же; · правила, выполняющие приведение первичных операндов (констант, идентификаторов), помещают их значения (или адреса) в стек; · генерируемая в процессе сверток последовательность команд стековой машины пишется в последовательный поток (последовательность сверток идентична последовательности выполения). Пусть некоторый условный процессор имеет следующий набор команд для работы со стеком: · PUSH(V) – загрузить значение V в стек; · V=POP() – извлечь значение из вершины стека; · V=GET(n) – получить значение n-го элемента относительно вершины стека, не удаляя его оттуда. Тогда каждому правилу, в котором встречается бинарная или унарная операция, будет соответствовать неизменный код, извлекающий операнды из стека и возвращающий туда же результат выполнения операции.
Выполняемая последовательность «сверток» правых частей правил приведет к появлению необходимой последовательности групп операций над стеком. В принципе, можно «сэкономить» операции над стеком, если последний операнд держать не в вершине стека, а в некотором регистре, например ax, который следует интерпретировать как вершину стека. В приведенном примере показаны только операции свертки, «серая» часть строки находится в стеке.
Специфика l-value также может быть учтена в коде, ориентированном на стек операндов. Для операнда l-value в стеке может храниться ссылка (адрес), а иначе – само значение операнда.
|