LR(1) разбирает прямо на абстрактное синтаксическое дерево

Question

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

Каждое сокращение в процессе синтаксического анализа LR соответствует внутреннему узлу в дереве разбора. Сокращаемое правило - это внутренний узел AST, а элементы, извлеченные из стека, соответствуют дочерним элементам этого внутреннего узла. Элемент, выдвигаемый для перехода, соответствует внутреннему узлу, тогда как элемент, выдвигаемый действиями сдвига, соответствует листьям (токенам) AST.

Собрав все это вместе, вы можете легко построить AST, создавая новый внутренний узел каждый раз, когда вы делаете сокращение, и соединяйте все вместе соответствующим образом. ~ Крис Додд

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

Answer 1

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

Во многих случаях AST является упрощением полного дерева синтаксического анализа, соответствующего вышеописанному.

Простой пример для грамматики выражения, использующий генератор синтаксического анализатора, похожий на yacc:

expr: term            { $$ = $1; /* see below */ }
    | expr '+' term   { $$ = new_sum_node($1, $3); }
term: factor          { $$ = $1; /* see below */ }
    | term '*' factor { $$ = new_product_node($1, $3); }
factor: '(' expr ')'  { $$ = $2; /* See below */ }
      | ID            { $$ = new_variable_node($1); }
      | NUMBER        { $$ = new_literal_node($1); }

AST строится как семантическая ценность нетерминалов. Функции new_*_node ожидается, что вернет вновь выделенный узел указанного типа. (Здесь мы предполагаем, что существует некоторый механизм, чтобы определить из указателя, какой это тип узла. Например, можно использовать подтипы и виртуальные функции.)

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

Некоторые из вышеуказанных сокращений вообще не отображаются в AST. В частности, единица сокращения (expr:term а также term:factor) просто пройдите через AST для правой стороны. Точно так же сокращение скобок term:'(' expr ')' просто проходит через AST для expr, в результате чего скобки эффективно исчезают из AST. (Это не правильно во всех языках; в некоторых языках явно избыточные круглые скобки фактически влияют на семантику, и вам нужно создать узел AST для записи факта.)

В Yacc, $$ = $1 является действием сокращения по умолчанию, если не указано никакого действия, и поскольку большинство сокращений единиц исключено из AST, они обычно отображаются без действий сокращения. Я сделал их явными для дидактических целей; на практике вы не должны этого делать.