BNF Parse Tree Запрос

Question

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

Назначение на 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?

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

Answer 1

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

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

• <expr> + <term>, т.е. <expr> с последующим + с последующим <term> или
• <expr> - <term> (интерпретируется аналогично), или
• <term>

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

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

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

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

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

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

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