Создание самых левых производных входной строки. Как предсказать, какую продукцию использовать?

Question

Допустим, у меня есть следующая грамматика:

Expr -> Expr plus Expr  (1)
     |  Expr minus Expr (2)
     |  num             (3)

Когда вы производите самый левый вывод, после "расширения" Expr как узнать, какую продукцию использовать?

Например, если я захочу разобрать 1 + 2 - 3 я бы начал с:

Expr => Expr minus Expr

, но это произошло бы только потому, что это небольшой пример, и легко увидеть, что (3) быстро приведет в никуда и (2) не поместится в следующем шаге.Будет ли пример немного сложнее, и мне придется сделать все в основном методом проб и ошибок.Это «правильный» подход или я что-то упустил?

Answer 1

Поскольку синтаксический анализ CFG по существу недетерминирован, нет общего способа заранее узнать, какое из возможных правил является правильным.В основном на самом простом уровне это действительно проб и ошибок.Как и логическое выражение дизъюнкции if(a OR b OR c), отдельные термины будут оцениваться один за другим, пока не будет достигнут успех, в противном случае правило в целом не будет выполнено.Таким образом, ваш парсер должен просто начать с правила (1), попытаться проанализировать входные данные, а в случае сбоя перезапустить с этого момента с правилом (2) и т. Д.