Запрос дерева синтаксического анализа BNF

В настоящее время я учусь в классе компьютерной архитектуры и пытаюсь выполнить одно из домашних заданий.

Задание находится на BNF, и даже после лекции, чтения слайдов и поиска в Интернете я все еще в тупике.

Вот моя грамматика:

<expr>-><expr> + <term> |
          <expr> - <term> |
          <term>
<term>-><term> * <factor> |
          <term> / <factor> |
          <factor>
<factor>->(<expr>)|<id>
<id>->A|B|C|D

Как будет выглядеть дерево синтаксического анализа для A + (C - D) / B?

Мне просто нужно небольшое руководство, и я смогу решить эту проблему для себя. Мой учитель не очень хорошо объясняет, поэтому я надеялся на объяснение с точки зрения непрофессионала, как это сделать?


bnf
person nward17    schedule 29.10.2014    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Хотя это не указано, я предполагаю, что мы пытаемся интерпретировать строку A + (C - D) / B как <expr> (поскольку никакой другой анализ не работает).

<expr> — нетерминальный символ, т. е. он не встречается буквально в конечной строке. Скорее первое правило (<expr> -> <expr> + <term> | <expr> - <term> | <term>) говорит нам, какие символы ожидать в строке, которая является <expr>. В нем говорится, что <expr> можно сделать одним из следующих вариантов:

  • <expr> + <term>, то есть <expr>, за которым следует +, за которым следует <term>, или
  • <expr> - <term> (интерпретируется аналогично) или
  • <term>

Не вдаваясь в детали того, как синтаксический анализатор механически принимает решение, мы должны выбрать один из этих вариантов, чтобы продолжить построение дерева синтаксического анализа. Я выберу первый вариант (<expr> + <term>), который предполагает, что первый <expr> будет представлять A в сообщении, + буквально означает +, а <term> — это осталось (C – D) / B. Таким образом, начало нашего дерева разбора выглядит так:

     <expr>
     / | \
    /  |  \
<expr> + <term>

Это еще не полный анализ, так как из правил не сразу ясно, что <expr> может дать результат A. Точно так же (C - D) / B не является непосредственным вариантом для <term>. Мы можем ответить на первое возражение, увидев, что:

  1. <expr> может быть <term> (по третьему варианту правила для <expr>)
  2. <term> в свою очередь может быть <factor> (по третьему варианту правила для <term>)
  3. <factor> может быть <id> (по второму варианту правила для <factor>), и наконец
  4. <id> может быть A (по первому варианту правила для <id>)

Эта линия рассуждений заполняет дерево синтаксического анализа следующим образом:

      <expr>
      / | \
     /  |  \
 <expr> | <term>
   |    |
 <term> |
   |    |
<factor>|
   |    |
  <id>  |
   |    |
   A    +

Я надеюсь, что это дало вам представление о процессе и значении правил, чтобы вы могли дальше показать, как <term> может дать (C - D) / B и, таким образом, заполнить остальную часть дерево.

person hcs    schedule 29.10.2014
comment
Да, вы правы, думая, что ввод идет для <expr>. Думаю, мне удалось разобраться. Вот изображение моего дерева анализа: i.imgur.com/GVArYJw.png - person nward17; 29.10.2014
comment
Кроме того, разве это не должно быть <term>, затем <factor>, а затем <id>? Я думаю, вы забываете один шаг. - person nward17; 29.10.2014
comment
Я думаю, что несколько уровней вашего дерева расположены в обратном порядке (нетерминалы должны появляться в том же порядке слева направо, что и в правилах), но ваша структура выглядит правильной. - person hcs; 29.10.2014