Разбор рекурсивного спуска и деревья абстрактного синтаксиса - PullRequest
Новая
       31

Разбор рекурсивного спуска и деревья абстрактного синтаксиса

0 голосов
/ 29 марта 2011

Я жестко программирую рекурсивный приличный парсер, в основном для целей обучения, и у меня возникли некоторые проблемы.

Я буду использовать этот короткий отрывок из грамматики 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.

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

Я использую структуру данных связанного списка для поддержки произвольного просмотра и могу легко нарезать этот список, чтобы попытаться произвести, а затем вернуться кмоя отправная точка, если производство не удается.Однако, пробуя производство, я передаю изменяемое состояние, пытаясь построить объектную модель документа.Это на самом деле не работает, потому что я не знаю, будет ли производство успешным или нет.И если производство не увенчалось успехом, мне нужно как-то отменить любые сделанные изменения.

У меня такой вопрос.Должен ли я использовать абстрактное синтаксическое дерево в качестве промежуточного представления, а затем перейти оттуда?Это то, что вы обычно делаете, чтобы обойти эту проблему?Поскольку проблема, по-видимому, в первую очередь связана с тем, что объектная модель документа не является подходящей древовидной структурой данных для рекурсии.

1 Ответ

1 голос
/ 29 марта 2011

Я не очень хорошо знаком с CSS, но, в общем, вы должны реорганизовать грамматику, чтобы устранить двусмысленности, насколько это возможно.В вашем случае здесь, производство namespace_prefix, которое может быть в начале как type_selector, так и универсального, может быть извлечено спереди как отдельное дополнительное производство: 

simple_selector = [ namespace_prefix ]? (type_selector | universal);
type_selector = element_name;
namespace_prefix = [ IDENT | '*' ]? '|';
element_name = IDENT;
universal =  '*';

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

...