То, какой узел в дерене является операцией, а какой — операндом, никак невозможно определить из грамматики, описывающей синтаксис входного языка. Также ниоткуда не следует, каким операциям должен соответствовать объектный код в результирующей программе, а каким — нет. Все это определяется только исходя из семантики — «смысла» — языка входной программы. Поэтому только разработчик компилятора может четко определить, как при построении дерева операции должны различаться операнды и сами операции, а также то, какие операции являются семантически незначащими для порождения объектного кода. Алгоритм преобразования дерева семантического разбора и дерево операции можно представить следующим образом. Шаг 1.
Если в дереве больше не содержится узлов, помеченных нетерминальными символами, то выполнение алгоритма завершено; иначе — перейти к шагу 2Шаг. 2. Выбрать крайний левый узел дерена, помеченный нетерминальным символом грамматики и сделать его текущим. Перейти к шагу 3. Шаг 3. Если текущий узел имеет только один нижележащий узел, то текущий узел необходимо удалить из дерена, а связанный с ним узел присоединить к узлу вышележащего уровня (исключить из дерена цепочку) и вернуться к шагу 1; иначе — перейти к шагу 4. Шаг 4. Если текущий узел имеет нижележащий узел (лист дерева), помеченный терминальным символом, который не несет семантической нагрузки, тогда этот лист нужно удалить из дерева и вернуться к шагу 3; иначе — перейти к шагу 5. Шаг 5.
Если текущий узел имеет один нижележащий узел (лист дерева), помеченный терминальным символом, обозначающим знак операции, а остальные узлы помечены как операнды, то лист, помеченный знаком операции, надо удалить из дерева, текущий узел пометить этим знаком операции и перейти к шагу 1; иначе — перейти к шагу 6. Шаг 6. Если среди нижележащих узлов для текущего узла есть узлы, помеченные нетерминальными символами грамматики, то необходимо выбрать крайний левый среди этих узлов, сделать его текущим умом и перейти к шагу 3: иначе — выполнение алгоритма завершено. Тестовые примеры/* prog — файл с транслируемой программой, lex — выходной файл лексем */ while (!feof (prog)) { ch = readsym (); /* чтение очередного символа ch с пропуском пробелов */ if (isAlpha (ch)) fprintf (lex, «%c %d», ch, 1); else if (isDigit (ch)) digit (); /* Процедура чтения числа и вывода его в файл */ else if (ch == '=') fprintf (lex, «%c %d», ch, 3); else if (ch == '*' — ch == '/') fprintf (lex, «%c %d», ch, 4); else if (ch == '+' — ch == '
-') fprintf (lex, «%c %d», ch, 5); elseprintf («Недопустимый символ языка — %c n», ch); }2. Алгоритм перевода в обратную польскую запись функции, имеющей не менее одного параметра, такой же, что для переменной с индексами, но различие состоит в том, что в момент прихода закрывающей круглой скобки в выходную строку записывается символ Ф. Чтобы отличить открывающую круглую скобку в начале списка фактических параметров от открывающей круглой скобки в начале выражения, используют специальную переменную состояния f (признак функции), которая обычно имеет значение 0. В момент появления идентификатора функции f принимает значение 1, а после занесения в стек круглой скобки и начального значения счетчика операндов, равного 2, вновь принимает значение 0. Закрывающая скобка, встретив в стеке открывающую круглую скобку, записанную вместе со значением счетчика операндов, заносит это значение в выходную строку, записывает туда знак Ф и уничтожает в стеке круглую скобку и значение счетчика операндов. Обратная польская нотация (RPN) заданного выражения — корень (4*a — 8/a2) будет иметь вид 0 4 а-8*а корень2^/3. Обычно задача решается следующим образом:
Каждому состоянию ставим в соответствие нетерминал. Если есть переход из состояния X в состояние Y по а, добавляем правило X → aY. Для конечных состояний добавляем правила X → ε. Для ε-переходов — X → Y.Пример.Продукция грамматики имеет вид: A → aB — cCB → bD — cEC → εD → aB — cCE → aB — cCСписок использованных источников
Серебряков — Языки программирования:
http://infonet.cherepovets.ru/citforum/programming/theory/serebryakovСвободная энциклопедия — Википедия
http://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B0%D0%BD%D1%81%D0%BB%D1%8F%D1%82%D0%BE%D1%80
