Абстрактное дерево против дерева парсеров

Question

Мне нужно ваше мнение, чтобы выбрать наилучшую альтернативу для выбора дерева синтаксического анализатора (ST) или для генерации абстрактного синтаксического дерева (AST). Это контекст:

Я хочу проанализировать язык, подобный C (только подмножество C с некоторыми изменениями, чтобы сделать его более псевдокодированным), но не для того, чтобы перевести его на другой язык/файл вывода, но для выполнения своих предложений для анимации его выполнения (я использую Qt для рисования). Особенностью этого подмножества C является включение вложенных областей. Мое сомнение, связанное с моим избранием между ST и AST, возникает из таблицы символов. Общая идея (с использованием Boost.spirit):

1. Анализ исходного кода с помощью пользовательского парсера Boost.spirit.
2. Семантические действия создают дерево синтаксиса, только копию дерева синтаксиса исходного кода (а также копию внутреннего дерева синтаксиса Boost.spirit, но с моими собственными классами и структурами). Таким образом, нет АСТ.
3. С помощью этой ST в руке программа считывает это синтаксическое дерево в направлении сверху вниз:
   1. Выполните первое предложение.
   2. Загрузите таблицу символов с новыми значениями (результатом предложения).
   3. Сохранение фактического состояния таблицы символов в стеке состояния программы.
   4. До 3.1 до полной обработки ST.
   5. Анимировать алгоритм чтения и рисования стека состояний программы.

Два рассуждения:

1. Если я работаю с АСТ, я проиграл, после разбора, информацию о объявлении переменных, его типы и так далее. Таким образом, я должен работать с таблицей символов с помощью семантических действий синтаксического анализатора, усложняя запись и понимание парсера. Более того, я должен работать все время с таблицей символов со всеми переменными независимо от фактической области действия (если я нахожусь в области i, нужны только области i, i-1, ...., 1; not все области по всему алгоритму). Это тратит память.
2. Мне нужно, только в стеке состояния программы, переменные фактической и предыдущей областей, чтобы не усложнять понятность алгоритма через анимацию. Если я работаю с ST, я должен удалить все символы, которые мне не нужны, прежде чем сохранять их в стеке. Это тратит время.

3. Статическую таблицу символов с областями управления сложнее разрабатывать и использовать, чем таблицу динамических символов. Таблица статических символов должна иметь идентификатор (например) для каждой области действия и связывать каждый узел дерева с каждым идентификатором. Динамическая таблица символов работает легче, потому что, если я нахожусь в сфере я, нужна только две «векторы» (возможно, двойную очередь и стека):

   • Контейнер (двойная очередь?) С символами и его связанная информация: последняя переменная в контейнере является ближайшей объявленной переменной.
   • Контейнер (стек) целых чисел, показывающий начало (индекс двойной очереди) каждой области.

   Например, для области I:

   • Контейнер 1: [xyzxabzfaz]
   • Контейнер 2: [0 3 6 8]

   Если я оставить объем я , только мне нужно удалить последнее целое число и символы из позиции 8 до конца. Дерево не изменено.

4. Должно к выполнению каждого предложения во время выполнения, ST облегчает мое выполнение.

Два вопроса:

1. Что лучше тогда?
2. Существуют ли какие-либо формы для извлечения внутреннего дерева Духа или его настройки, чтобы не копировать его?

Answer 1

Я думаю, что вы ищете является абстрактным семантический граф (ASG), который представляет семантику (в отличие от синтаксиса) программы. Что вы можете сделать, это:

1. Разбирает источник к AST, затем
2. преобразовать AST в ASG, и, наконец,
3. ходить ASG для выполнения фактического кода.

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