Я жестко кодирую рекурсивный приличный синтаксический анализатор, в основном для целей обучения, и у меня возникли некоторые проблемы.
Я буду использовать этот короткий отрывок из грамматики CSS3 в качестве примера:
simple_selector = type_selector | universal;
type_selector = [ namespace_prefix ]? element_name;
namespace_prefix = [ IDENT | '*' ]? '|';
element_name = IDENT;
universal = [ namespace_prefix ]? '*';
Во-первых, я не понимал, что namespace_prefix
является необязательным элементом как в type_selector
, так и в universal
. Это приводило к тому, что type_selector
всегда терпел неудачу при подаче ввода, такого как *|*
, потому что он слепо рассматривался для любого ввода, который соответствовал продукции namespace_prefix
.
Рекурсивный приличный достаточно прост, но я понимаю, что мне нужно сделать много (из-за отсутствия лучшего слова) исследовательской рекурсии, прежде чем остановиться на производстве. Поэтому я изменил подпись своих продуктов, чтобы они возвращали логические значения. Таким образом, я мог легко сказать, увенчалась ли конкретная постановка успехом или нет.
Я использую структуру данных связанного списка для поддержки произвольного опережающего просмотра и могу легко разрезать этот список, чтобы попытаться произвести производство, а затем вернуться к исходной точке, если производство не удастся. Однако, пробуя производство, я передаю изменяемое состояние, пытаясь построить объектную модель документа. На самом деле это не срабатывает, потому что я не знаю, будет ли производство успешным или нет. И если производство не будет успешным, мне нужно как-то отменить все сделанные изменения.
Мой вопрос заключается в следующем. Должен ли я использовать абстрактное синтаксическое дерево в качестве промежуточного представления, а затем идти оттуда? Это то, что вы обычно делаете, чтобы обойти эту проблему? Потому что проблема, по-видимому, в первую очередь связана с объектной моделью документа, которая не является подходящей древовидной структурой данных для рекурсии.