Создание деревьев разбора с разбором сдвига

Question

Я экспериментирую с разбором в свободное время, и я хотел реализовать анализатор Shift-Unize для очень простой грамматики. Я прочитал много онлайн-статей, но я все еще путаю в том, как создавать паршиные деревья. Вот пример того, что я хочу сделать:

---

Грамматика:

Expr -> Expr TKN_Op Expr 
Expr -> TKN_Num

.

Вот пример ввода:

1 + 1 + 1 + 1

.

что после токенизации становится:

TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num

.

---

Я понимаю, что:

1. смещение означает нажатие первого входного токена в стеке и удаление его с входа
2. Уменьшение означает подстановку одного или нескольких элементов на стек с элементом грамматики

Так, в основном это должно произойти:

Step 1:
    Stack:
    Input: TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Stack is empty. Shift.

Step 2:
    Stack: TKN_Num
    Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: TKN_Num can be reduced to Expr. Reduce.

Step 3:
    Stack: Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Cannot reduce. Shift.

Step 4:
    Stack: Expr TKN_Op 
    Input: TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Cannot reduce. Shift.

Step 5:
    Stack: Expr TKN_Op TKN_Num
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: TKN_Num can be reduced to Expr. Reduce.
    // What should I check for reduction? 
    // Should I try to reduce incrementally using 
    // only the top of the stack first, 
    // then adding more stack elements if I couldn't
    // reduce the top alone?

Step 6:
    Stack: Expr TKN_Op Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: Expr TKN_Op Expr can be reduced to Expr. Reduce.

Step 7:
    Stack: Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: ...
    // And so on...

.

Помимо от "Что сократить?" Сомнений, у меня нет никакой подсказки, как правильно создать дерево разбора. Дерево, вероятно, должно выглядеть так:

1    +    o
          |
     1    +    o
               |
          1    +    1

.

Должен ли я создать новый узел по уменьшению?

И когда я должен добавить детей к новому узеру / когда я должен создать новый корневой узел?

Answer 1

Простая и очевидная вещь, которую нужно сделать, это создать узел дерева в каждом уменьшении и добавить узлы деревьев из элементов грамматики, которые были уменьшены до этого узла дерева.

Это легко управляется с помощью узла стека, который работает параллельно стекам «Token Shift», который использует необработанный парсер. Для каждого снижения для правила длины N стек сдвигаемого токена сокращается по N, а нетерминальный токен нажимается на стек сдвига. В то же время сокращают стек узла, удалив верхние n узлов, создайте узел для нетерминальных, прикрепленных удаленные N узлы в качестве детей, и нажимайте этот узел на стек узла.

Эта политика даже работает с правилами, имеющими правую руку с нулевой длиной: создайте узел дерева и прикрепите пустой набор детей к нему (например, создайте узел листья).

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

Если вы сделаете это, вы получаете «бетонный синтаксис / разборку дерева», который соответствует изоморфическому грамматике. (Мы делаем это для коммерческого инструмента, которое я предлагаю). Есть много людей, которые не любят такие бетонные деревья, потому что они содержат узлы для ключевых слов и т. Д., Что на самом деле не добавляет много ценности. Правда, но такие деревья в высшей степени легко построить, а в высшей степени легко понять, потому что грамматика является структурой дерева. Когда у вас есть 2500 правил (как мы делаем для полного парсера Cobol), это имеет значение. Это также удобно, потому что весь механизм может быть полностью построен в инфраструктуру разборки. Инженер грамматики просто пишет правила, пробеги парсера, вуаля, дерево. Также легко изменить грамматику: просто измените его, вуаля, вы все еще получаете табло деревьев.

Однако, если вы не хотите бетонное дерево, например, вы хотите, чтобы «абстрактное синтаксическое дерево», то то, что вам нужно сделать, это позволить управляющему инженеру грамматики, какое снижение генерирует узлы; Обычно добавляют некоторую процедурную прикрепление (код) к каждому правиле грамматики для выполнения на этапе снижения. Затем, если какое-либо такое процессуальное приложение дает узел, он сохраняется на стеке узла. Любое процессуальное приложение, которое создает узел, должен прикреплять узлы, созданные правыми элементами рук. Если кто-то, это то, что YACC / BISOCON / ... большая часть механизмов Shift-Unize Paser делает. Иди читайте о YACC или бизона и осмотрите грамматику. Эта схема дает вам много контроля, по цене настаивания на том, что вы принимаете этот контроль. (Для того, что мы делаем, мы не хотим, чтобы это много инженерных усилий по созданию грамматики).

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

Answer 2

Причина вашей неприятностей в том, что у вас есть сдвиг / уменьшение конфликта в вашей грамматике:

expr: expr OP expr
    | number

.

Вы можете решить это 2 способа:

expr: expr OP number
    | number

.

для левых ассоциативных операторов или

expr: number OP expr
    | number

.

для правильных ассоциативных. Это также должно определить форму вашего дерева.

Сокращение обычно делается, когда одно предложение обнаружено полным. В правильном ассоциативном случае вы начнете в состоянии 1, который ожидает, что ряд толкает его на стек значений и сдвигается к состоянию 2. В штате 2, если токен не является OP, вы можете уменьшить число для EXPR Отказ В противном случае нажмите оператора и перейти к состоянию 1. После завершения состояния 1 вы можете уменьшить количество, оператор и выражение в другое выражение. Примечание, вам нужен механизм «возврата» после сокращения. Затем общий анализатор начнутся в штате 0, скажем, что сразу идет до состояния 1 и принимает после восстановления.

Обратите внимание, что инструменты, такие как YACC или Bison, делают этот вид вещей намного легче, потому что они приносят все машины низкого уровня и стеки.