Разбор синтаксического и рекурсивного спуска деревьев
Итак, я много месяцев изучал и экспериментировал с языковым дизайном, и у меня гораздо лучшее понимание, чем пару месяцев назад. Я все еще смущен некоторыми вещами, хотя …
Я взломал несколько плохих парсеров без исследований, но мне нужно что-то лучше.
Поэтому я пытаюсь написать синтаксический анализатор рекурсивного спуска, поскольку я прочитал, что наиболее логичным является написать вручную. Насколько я понимаю, каждое правило реализовано в своей собственной функции. Поэтому я думаю, что понимаю, как бы написать об этом, но только о первой половине … Работа синтаксического анализатора заключается в создании синтаксического дерева или чего-то подобного, верно? Я также пытался исследовать эту тему, но мне не удалось найти каких-либо примеров того, как дерево представлено в языке. Я пишу на D, потому что это мой любимый язык, но он очень похож на C / C ++, поэтому я буду понимать любые примеры, написанные на этих языках или псевдокоде.
Из того, что я видел, есть тонна классов, которые наследуются друг от друга, поэтому может быть класс операторов, который, например, расширяет класс IfStatement. Но я не смог найти, как все это представлено на дереве или даже как оно проходило позже.
Было бы замечательно, если бы кто-то мог показать мне пример или рассказать об этих вещах немного глубже. Любая помощь действительно много значит и помогает с моим любопытством и целями, спасибо заранее!
Решение
Дерево, как правило, представляется в виде структуры, содержащей указатели на своих дочерних элементов и node член, который хранит свой тип узла или он принадлежит к определенному классу, так что вы можете получить его фактический тип (то есть, если он содержит арифметическое выражение, оператор if, цикл и т. д.).
Простой пример действительно был бы if Скажите, как вы упомянули. Для этого вы должны сделать что-то вроде этого (псевдо-C следует):
enum AST_Node {
Node_if,
Node_and,
Node_or,
Node_not,
Node_equal,
Node_less,
// etc., other node types follow
};
struct AST {
struct AST *children[MAX_CHILDREN]; // don't do this
enum AST_Node node;
};
struct AST *parse_if_statement()
{
// expect tokens in order
expect("if");
// parse condition
expect("(");
struct AST *condition = parse_expression();
expect(")");
// parse two child statements
struct AST *then_branch = parse_statement();
struct AST *else_branch = NULL;
if (accept("else")) {
else_branch = parse_statement();
}
// create AST, fill in children
struct AST *if_statement = new_AST_node(Node_if);
if_statement->children[0] = condition;
if_statement->children[1] = then_branch;
if_statement->children[2] = else_branch;
return if_statement;
}
Таким образом, в основном вы просто ожидаете / принимаете постоянные лексические элементы («если», круглые скобки вокруг условия и т. Д.), Затем вы передаете разбор поддеревьев (условие и две ветви) соответствующим функциям синтаксического анализатора.
И вот как вы ходите по дереву: вы в основном делаете прогулка вглубь, составление или интерпретация каждого ребенка по порядку. Затем вы добавляете дополнительную семантику, которую подразумевает тип узла поддерева, который в настоящее время интерпретируется / компилируется.
Value *interpret_if_statement(struct AST *ast)
{
assert(ast->node == Node_if);
struct AST *condition = ast->children[0];
struct AST *then_branch = ast->children[1];
struct AST *else_branch = ast->children[2];
// evaluate condition
Value *condval = interpret_expression(condition);
if (condval->bool_value == TRUE) {
// if condition is true, interpret "then" branch
return interpret_statement(then_branch);
} else if (else_branch != NULL) {
// otherwise interpret "else" branch, if any
return interpret_statement(else_branch);
} else {
return NULL;
}
}
Другие решения
Других решений пока нет …