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

Question

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

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

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

Answer 1

Прежде всего, вам необходимо различать обычные проходы компилятора:

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

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

Answer 2

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

<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

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

Answer 3

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

Если вы пишете свой собственный анализатор, здесь есть превосходный обзор .