разница между LL-парсером и AST

Question

В настоящее время я пытаюсь создать парсер LL. Однако у меня уже есть моя BNF-грамматика, но мне нужно создать АСТ, и у меня есть несколько вопросов.

• В чем разница между АСТ и парсером LL? (Потому что оба они являются двоичным деревом)
• Как я могу создать AST из грамматики BNF? ( http://mariusbancila.ro/blog/2009/02/05/evaluating-expressions-part-3-building-the-ast/

я нашел на Google этот учебник, который объясняет многое о строить AST иначе, они не объясняют, как знать, если я должен взять правую ветвь или левую ветвь.)

Thank's

Answer 1

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

Как правило, часть компилятора, которая фактически генерирует AST, называется парсером . Существует много разных классов парсера, из которых парсеры LL являются одним из популярных семейств. Анализаторы LL часто могут быть написаны вручную, но они часто генерируются автоматически с использованием средств генерации компилятора.

Другими словами, ответ на ваш основной вопрос о том, какая разница между АСТ и парсером LL, является «парсер LL - это тип парсера, а синтаксический анализатор - это то, что генерирует AST».

Ваш следующий вопрос: как вы строите AST из грамматики BNF. Как правило, вы не строите AST для самой грамматики BNF. Вместо этого грамматика будет направлять конструкцию синтаксического анализатора, и тогда синтаксический анализатор будет строить АСТ. Фактически создание парсера обычно является темой, охватываемой стандартным курсом компиляторов. Если вам интересно, I have a set of lecture slides available from the last time I taught a compilers class, а также лекции 02, 03 и 04, рассмотрим синтаксический анализ и как спроектировать и построить парные анализаторы LL. Надеюсь, они дадут вам толчок в правильном направлении!