Рекурсивный достойный синтаксический анализ

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

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

program -> VAR = exp
exp -> NUM term
exp -> LEFTPAR exp RIGHTPAR
term -> MUL NUM term
term -> DIV NUM term
term -> . (empty)

Примером функции для правила может быть:

public Pair<bool, Token> exp(Token tok)
{
    if (tok.type == NUM)
    {
         return term(tok.next);
    }
    if (tok.type = LEFTPAR)
    {
         Pair<bool, Token> temp = exp(tok.next);
         if (temp.left && temp.right.type == RIGHTPAR)
             return new Pair<bool, Token>(true,temp.right.next);
         return new Pair<bool, Token>(false,null);
    }
}

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


parsing c# abstract-syntax-tree recursive-descent
person McAngus    schedule 22.02.2016    source источник
comment
См. мой ответ о том, как создать парсер рекурсивного спуска, в котором обсуждается, как построить AST. stackoverflow.com/questions/2245962/ (вам не нужно начинать каждое правило с терминала; итерация может обрабатывать многие случаи левой рекурсии.)   -  person Ira Baxter    schedule 22.02.2016
comment
Спасибо! Это очень помогает! Что вы делаете, когда у вас есть правило, допускающее значение NULL, такое как term в моем примере или несколько (как в моей полной грамматике)? Кажется, что единственное решение состоит в том, чтобы иметь кучу операторов if, чтобы проверить, какие из них являются нулевыми, а затем не возвращать их.   -  person McAngus    schedule 22.02.2016
comment
Поскольку вы контролируете, какой узел возвращает каждое правило, вы можете передать все, что захотите, вверх по дереву. Да, вам может понадобиться сложная логика, чтобы решить, что на самом деле создавать для каждого правила. Это цена наличия AST, который не имеет точно такой же формы, как грамматика (например, CST). Для небольших грамматик вы можете захотеть сделать это дополнительное кодирование. Для большой или быстро развивающейся грамматики построение дерева той же формы, что и грамматика, не требует мозгов и является простым делом. Вы не получите настоящего AST, но если вы последуете моим советам по удалению некоторых узлов по мере продвижения, то то, что вы получите, достаточно близко.   -  person Ira Baxter    schedule 22.02.2016
comment
Как я выяснил, синтаксический анализ рекурсивного спуска подходит для реализации с помощью процедурно-ориентированных языков, но не совсем подходит для объектно-ориентированного программирования.   -  person Anil Kumar    schedule 23.02.2016

Ответы (1)


arrow_upward
1
arrow_downward

Вот пример разбора аргумента функции. Это на C, но идея передается, т. е. вы создаете AST, когда анализируете поток токенов.

Эта функция анализирует такие строки, как foo : double

static void parse_arg(parser_obj *obj, AstFunc *func) {
  Token   * tok;
  TokenId   tid = peek(obj);

  if(tid == T_PAREN_R) {
    return;
  }
  EXPECT(T_ID);
  tok = t(obj);
  char *arg_name = tok_value(tok);
  EXPECT_EAT(T_COLON);

  tok = t(obj);
  ctype arg_type = tokid_to_type(tok_id(tok));
  func->ops->new_arg(func, arg_name, arg_type);
}

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

В следующей строке мы добавляем аргумент к объекту func.

func->ops->new_arg(func, arg_name, arg_type);

Фактическое внутреннее устройство func, т.е. форма строящегося дерева или то, как оно реализовано, парсеру не видны.

person Harry    schedule 29.03.2016