Как я могу поместить текущее состояние выполнения в стек, чтобы я мог продолжить с него позже?

Question

Представьте себе простую грамматику:

(a|ab)c

Который читает (a или ab), за которым следует c. Дерево разбора будет выглядеть так:

   and
   / \
  or  c
 /  \
a   ab

Теперь с учетом этого ввода:

abc

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

Но был альтернативный путь, по которому он мог пойти; если бы мы перешли к «ab», мы нашли бы совпадение.

Итак, что я хочу сделать для узлов "or", так это:

1. Оценить левую ветвь
2. Если левая ветвь не совпадает, попробуйте правую ветвь
3. Если совпадение слева совпадает, поместите текущее состояние в стек, чтобы мы могли продолжить с этой точки позже, если необходимо

Затем, когда парсер попадает в тупик, я хочу вытолкнуть элемент из стека и продолжить оттуда снова.

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

---

Я думаю, Крис был чем-то занят. Мы должны найти способ перевести дерево так, чтобы не было необходимости перепрыгивать через такие ветви. Например, у этого эквивалентного дерева разбора такой проблемы нет:

     or
    /  \
 and   and
 / \    / \
a   c  ab  c

На этот раз мы разбираем левую сторону, нажимаем «a», она проходит, поэтому мы пытаемся найти рядом с ним узел «c», который терпит неудачу »и« fails », или« должен попробовать правую ветвь, .. » "ab" проходит, другой "c" проходит, а затем проходит все выражение.

Answer 1

У вас есть ответ на ваш вопрос в том виде, в котором вы его задали.

Вам необходимо сохранить состояние . Сложная часть - идентификация государства. Сохранение это просто.

Ваша проблема в том, что синтаксический анализатор "имеет состояние", когда он начинает синтаксический анализ некоторого правила грамматики. (Это усложняется, если вы используете парсер LALR, который объединяет разбор многих правил в одно состояние). Это состояние состоит из:

• состояние входа (например, где находится поток ввода?).
• состояние стека разбора (какой левый контекст виден до сих пор?)
• где анализатор должен продолжить работу в случае успеха, а где продолжить работу в случае ошибки

Когда вы анализируете и сталкиваетесь с альтернативой выбора, как вы описали, вам нужно «сохранить состояние», запустить пробный анализ первого термина. В случае успеха вы можете выбросить сохраненное состояние и продолжить. В случае неудачи восстановите состояние и попробуйте второй (и n-й варианты). (Легче быть безмозглым и просто сохранять состояние независимо от того, сталкиваешься ли ты с альтернативой, но решать тебе).

Как вы можете сохранить состояние? Вставьте его в стопку. (Обычно у вас есть стек разбора, это довольно удобное место! Если вам это не нравится, добавьте еще один стек, но вы обнаружите его, и стек разбора в целом перемещается синхронно; я просто заставляю стек разбора содержать запись с все, что мне нужно, включая пространство для ввода. И вы найдете «стек вызовов», удобный для частей состояния (см. ниже).

Первым делом нужно сохранить местоположение input ; это, вероятно, позиция источника файла и по причинам оптимизации, вероятно, индекс буфера. Это просто скаляр, поэтому его довольно легко сохранить. Восстановление Входной поток может быть сложнее; нет никакой гарантии, что сканер входного синтаксического анализатора находится где-то рядом, где он был. Таким образом, вам нужно переместить файл, перечитать любой буфер и переместить любой указатель входного буфера. Некоторые простые проверки могут сделать это статистически дешевым: сохранить позицию файла первого символа любого буфера; затем определение необходимости повторного чтения буфера - это вопрос сравнения позиции сохраненного файла с позицией начального файла буфера. Остальное должно быть очевидным.

Вы вернетесь назад через меньшее количество буферов (например, ваш парсер будет работать быстрее), если вы измените свою грамматику, чтобы минимизировать это. В вашей конкретной грамматике у вас есть «(a | ab) c», который можно переписать вручную в «a b? C». Последний, по крайней мере, не будет возвращаться к тому, что представляет собой.

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

"где анализатор выходит из строя при сбое" и "где он проходит в случае успеха" - это всего лишь два скаляра. Вы можете представить их в виде индексов блоков кода синтаксического анализа и счетчиков программ (например, продолжений) или в качестве адреса возврата в стеке вызовов (см. «Другой параллельный стек!»), За которым следует условный тест на успех / сбой.

Если вам нужны подробности о последнем, посмотрите мой SO ответ о парсерах рекурсивного спуска с ручным кодированием.

Если вы начнете строить деревья или делать что-то еще в качестве побочного эффекта при разборе, вам придется выяснить, как захватить / сохранить состояние побочной сущности и восстановить ее. Но что бы это ни было, вы положите его в стек.

Answer 2

Просто верните свое состояние в дополнение к вашему результату.Давайте рассмотрим простой пример, где вы можете иметь индекс для каждого элемента:

Grammer: (a|ab)c
Translated: AND(OR(a,ab),c)
Input: abc

Call AND
Call OR
a matches, return true,1
c does not match, start over
Call OR giving 1
ab matches, return true,2
c matches, return true

Вам понадобится более сложная структура для обработки более сложных случаев (будь то очередь или стек, зависит от того, как вы строите иуничтожить в воссоздании вашего государства)

Answer 3

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

Вы можете указать, успешно ли вы проанализировали ветвь, возвращая значение изметод разбора.Например, вы можете вернуть true для успеха и false для ошибки.В этом случае, если синтаксический анализ возвращает false, попробуйте следующий параметр.

Answer 4

вам нужно использовать рекурсию.

Что-то вроде:

в или оператора для каждого оператора bool ret = eval (оператор) if (ret) bool recVal = вызвать рекурсию if (recVal) чем вы найдете путь, остановите рекурсию.иначе мы продолжим в другом цикле и попробуем следующее утверждение.