Как построить дерево разбора?

Нашли C++ BNF и там следующие строки

selection-statement:
    if ( condition ) statement
    if ( condition ) statement else statement

Сейчас пытаюсь написать парсер. Нужно построить дерево разбора. На входе у меня есть BNF и исходный файл. Но я застрял в том, как я могу указать своему синтаксическому анализатору, что, если условие оценено как истинное, тогда ему нужно выполнить первый оператор, иначе блокируется? Спасибо.


c++ parsing bnf context-free-grammar
person Yola    schedule 29.09.2011    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Условные операторы имеют простую рекурсивную структуру. Соответствующий синтаксический анализатор рекурсивного спуска имеет такую ​​же простую рекурсивную структуру. Абстрактно внутренние условные операторы анализируются следующим образом:

<cond> -> if <expression> then <statement> [else <statement>]

cond :
  a = parse expression
  b = parse statement
  if is_else(token)
    then c = parse statement
         return conditional(a,b,c)
    else return conditional(a,b)

В вашем примере условные операторы содержат блоки условных операторов, последний из которых содержит предложение else. Предполагая, что токенизированная входная последовательность имеет такую ​​форму и при лексическом анализе были обнаружены синтаксические ошибки, внешний условный оператор анализируется следующим образом:

<conditional> -> selection_statement: {<cond>} <cond>

conditional :
  b = new block
  while (iscond(next))
    s = parse cond
    b = insert(s,b)
  return b

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

Я только что понял, что вы говорили об оценке абстрактного синтаксического дерева. Структура функции, которая оценивает условный оператор, аналогична функции, которая анализирует условный оператор. Абстрактно,

cond(input) :
  a = evaluate(if_part(input))
  if is_true(a)
    then evaluate(then_part(input))
    else if(is_else(input))
           then evaluate(else_part(input))
           else return

Чтобы определить, какую часть условного выражения следует оценивать, вы должны сначала оценить часть условного выражения "if" как логическое значение. Если логическое значение равно "true", оценивается часть условного выражения "then". Если логическое значение равно false, то оценивается часть else условного выражения. Если нет «другой» части, то и оценивать нечего. Разумеется, реализация будет более детальной, чем описанная выше.

person danportin    schedule 03.10.2011
comment
Спасибо чувак. теперь я знаю, что мне нужен модуль для реализации семантики, bnf дает мне только грамматику. - person Yola; 05.10.2011
comment
Да, как указал Титон, вам нужно сделать три вещи. Во-первых, вам нужно токенизировать входной поток. Во-вторых, вам нужно проанализировать токенизированный входной поток. В-третьих, вам нужно оценить проанализированное абстрактное синтаксическое дерево. - person danportin; 05.10.2011

arrow_upward
1
arrow_downward

В первую очередь нужно различать обычные проходы компилятора:

  1. Лексирование, то есть распознавание слов и удаление комментариев,
  2. синтаксический анализ, то есть структурирование линейного входного потока в абстрактное синтаксическое дерево, и
  3. оценка или генерация кода.

Сначала делайте первые вещи, тогда вы поймете остальное. Посмотрите на boost::spirit для первых двух шагов.

person thiton    schedule 29.09.2011
comment
its — AST с условием if. Похоже, что компилятор теперь должен что-то делать с if-else, кроме информации из BNF. - person Yola; 29.09.2011
comment
И я могу построить AST, думаю, это не сложно, но я не понимаю, как в части генерации кода он выяснит, что если условие истинно, то jmp к первому оператору, а иначе блокировать. - person Yola; 29.09.2011
comment
@Yola: Это полностью зависит от того, что вы пытаетесь сделать с AST, что выходит за рамки синтаксического анализа, CFG и BNF. Вам придется переформулировать свой вопрос, указав, что вы пытаетесь сделать (интерпретация? компиляция? упрощение выражений?) и в чем заключается ваша конкретная проблема. - person thiton; 29.09.2011
comment
мне нужно интерпретировать и оценить выражение. Знаете ли вы калькулятор, который может вычислять выражение типа следующего: c=1;c*2; в результате получается 2 или еще один if (1 › 2) then 1; else 2; тоже 2. - person Yola; 29.09.2011
comment
Это шаг, который вы делаете после синтаксического анализа. Обычно компилятор преобразует AST в код. Для оператора if вы можете получить следующий псевдокод. CMP 1,2; JLE #ELSE; MOV R1, 1; JMP #END; #ELSE: MOV R1, 2 #END: (JLE будет прыжком, если меньше) - person MSalters; 29.09.2011

arrow_upward
0
arrow_downward

Существует множество программ, которые принимают грамматику BNF и выводят правильный парсер: http://en.wikipedia.org/wiki/Backus-Naur_form#Software_using_BNF

Если вы пишете свой собственный синтаксический анализатор, отличный онлайн-обзор .

person Will    schedule 29.09.2011