Восходящие методы анализа. Свертка-перенос
Восходящие методы синтаксического анализа состоят в том, что в цепочке (промежуточной или терминальной) ищется правая часть очередного правила, которое должно быть заменено своим нетерминалом. Очевидно, что не любая правая часть правила может быть свернута в любое время. Если посмотреть на дерево синтаксического разбора, то нетрудно заметить, что свертку необходимо производить регулярно, путем обхода дерева слева направо.
.
Z
|
E
|
T
-------------
T * F
| --------
F ( E )
-----
E + T
| |
T F
|
F
В данном дереве необходимо выполнить свертку по самому левому правилу T::=F в цепочке. Правая часть такого правила называется ОСНОВОЙ. Таким образом, основа - это полная правая часть первого правила при просмотре цепочки слева направо. Найденная в цепочке основа должна быть заменена на нетерминал из левой части соответствующего правила. Для более полного понимания принципа приведем последовательность основ цепочек при выполнении такого процесса свертки.
.
F * (F + F)
---
T * (F + F)
---
T * (T + F)
---
T * (E + F)
---
T * (E + T)
-----
T * (E)
---
T * F
-----
T
---
E
---
Z
---
Способ нахождения основы цепочки реализован в методе восходящего разбора "свертка-перенос":
В процессе анализа используется магазинный автомат (КА со стеком);
На каждом шаге работы автомата сравнивается пара символов - текущий символ входной цепочки (I) и текущий символ в стеке (М). По результату сравнения возможны два действия:
Перенос терминального символа из строки в стек: PUSH((I), NEXT(I) - в соответствии с принятыми для МА обозначениями.
Свертка правой части правила, которое в данный момент находится в стеке.