Как распечатать дерево парсеров в Yacc (BISON) - PullRequest
Новая
       31

Как распечатать дерево парсеров в Yacc (BISON)

3 голосов
/ 13 марта 2012

Я сделал парсер для языка Си, используя BISON и FlEX. Он работает и печатает «синтаксическую ошибку» в терминале, если данный c-входной код синтаксически неверен, в противном случае ничего не печатается.

Но я хочу распечатать дерево синтаксического анализатора , относящееся к данному c-входному коду в качестве вывода моего синтаксического анализатора. Как я могу это сделать? Есть ли в BISON функция, которую можно использовать для печати дерева парсера?

1 Ответ

1 голос
/ 14 марта 2012

Язык TXR (http://www.nongnu.org/txr) использует Flex и Yacc для анализа входных данных. Вы можете увидеть дерево разбора, если вы укажете ему -v.

Например: 

$ ./txr -v -c "@/[a-z]*|foo/"
spec:
(((text (#<sys:regex: 9d99268> or (0+ (set (#\a . #\z))) (compound #\f #\o #\o)))))

Вы создаете дерево в действиях синтаксического анализатора и распечатываете его самостоятельно с помощью процедуры печати дерева. Я использовал представление объекта, похожее на Лисп, чтобы упростить жизнь. Записывание этого выполняется рекурсивной функцией печати, которая распознает все возможные объекты.вводит и отображает их в нотации. Например, выше вы видите объекты символьного типа, напечатанные с нотацией хэш-обратной косой черты, а непечатаемое, непрозрачное, скомпилированное регулярное выражение напечатано с использованием нотации #< ... >.

Вотчасть грамматики: 

regexpr : regbranch                     { $$ = if3(cdr($1), 
                                                   cons(compound_s, $1),
                                                   car($1)); }
        | regexpr '|' regexpr           { $$ = list(or_s, $1, $3, nao); }
        | regexpr '&' regexpr           { $$ = list(and_s, $1, $3, nao); }
        | '~' regexpr                   { $$ = list(compl_s, $2, nao); }
        | /* empty */ %prec LOW         { $$ = nil; }
        ;

Как видите, построение AST - это в основном простая конструкция вложенных списков. Эта форма очень удобна для компиляции. Функция верхнего уровня регулярного выражения на основе NFAКомпилятор очень читабелен: 

/*
 * Input is the items from a regex form,
 * not including the regex symbol.
 * I.e.  (rest '(regex ...)) not '(regex ...).
 */
static nfa_t nfa_compile_regex(val exp)
{
  if (nullp(exp)) {
    nfa_state_t *acc = nfa_state_accept();
    nfa_state_t *s = nfa_state_empty(acc, 0);
    return nfa_make(s, acc);
  } else if (typeof(exp) == chr_s) {
    nfa_state_t *acc = nfa_state_accept();
    nfa_state_t *s = nfa_state_single(acc, c_chr(exp));
    return nfa_make(s, acc);
  } else if (exp == wild_s) {
    nfa_state_t *acc = nfa_state_accept();
    nfa_state_t *s = nfa_state_wild(acc);
    return nfa_make(s, acc);
  } else {
    val sym = first(exp), args = rest(exp);

    if (sym == set_s) {
      return nfa_compile_set(args, nil);
    } else if (sym == cset_s) {
      return nfa_compile_set(args, t);
    } else if (sym == compound_s) {
      return nfa_compile_list(args);
    } else if (sym == zeroplus_s) {
      nfa_t nfa_arg = nfa_compile_regex(first(args));
      nfa_state_t *acc = nfa_state_accept();
      /* New start state has empty transitions going through
         the inner NFA, or skipping it right to the new acceptance state. */
      nfa_state_t *s = nfa_state_empty(nfa_arg.start, acc);
      /* Convert acceptance state of inner NFA to one which has
         an empty transition back to the start state, and
         an empty transition to the new acceptance state. */
      nfa_state_empty_convert(nfa_arg.accept, nfa_arg.start, acc);
      return nfa_make(s, acc);
    } else if (sym == oneplus_s) {
      /* One-plus case differs from zero-plus in that the new start state
         does not have an empty transition to the acceptance state.
         So the inner NFA must be traversed once. */
      nfa_t nfa_arg = nfa_compile_regex(first(args));
      nfa_state_t *acc = nfa_state_accept();
      nfa_state_t *s = nfa_state_empty(nfa_arg.start, 0); /* <-- diff */
      nfa_state_empty_convert(nfa_arg.accept, nfa_arg.start, acc);
      return nfa_make(s, acc);
    } else if (sym == optional_s) {
      /* In this case, we can keep the acceptance state of the inner
         NFA as the acceptance state of the new NFA. We simply add
         a new start state which can short-circuit to it via an empty
         transition.  */
      nfa_t nfa_arg = nfa_compile_regex(first(args));
      nfa_state_t *s = nfa_state_empty(nfa_arg.start, nfa_arg.accept);
      return nfa_make(s, nfa_arg.accept);
    } else if (sym == or_s) {
      /* Simple: make a new start and acceptance state, which form
         the ends of a spindle that goes through two branches. */
      nfa_t nfa_first = nfa_compile_regex(first(args));
      nfa_t nfa_second = nfa_compile_regex(second(args));
      nfa_state_t *acc = nfa_state_accept();
      /* New state s has empty transitions into each inner NFA. */
      nfa_state_t *s = nfa_state_empty(nfa_first.start, nfa_second.start);
      /* Acceptance state of each inner NFA converted to empty
         transition to new combined acceptance state. */
      nfa_state_empty_convert(nfa_first.accept, acc, 0);
      nfa_state_empty_convert(nfa_second.accept, acc, 0);
      return nfa_make(s, acc);
    } else {
      internal_error("bad operator in regex");
    }
  }
}
...