Получив арифметическое выражение?

Question

как бы вы получили это выражение? Мне нужно нарисовать дерево разбора для этого, но у меня есть реальная проблема с выводом этого. Поиск в Google также не дал никаких полезных ссылок, любая помощь будет высоко ценится, но, пожалуйста, дайте краткое объяснение того, как вы это сделали, так как у меня есть несколько других, чтобы сделать сам. Есть ли "|" означает оператор "или", как в программировании ??

< exp> ---> < exp> * < factor> | < factor>
< factor> ---> < factor> - < term> | < term>
< term> ---> x | y | z

Это лучшее, что я мог придумать, и я полностью потерян ..

< exp> ---> < exp> * < factor>
---> x * < factor>
---> x * < factor> * < factor>

Answer 1

Да, |или, как в обычном программировании.Строка типа:

< exp> ---> < exp> * < factor> | < factor>

означает, что что-то может быть < exp>, если оно имеет вид < exp> * < factor> или если это < factor>.

.полная грамматика:

< exp>    ---> < exp> * < factor> | < factor>
< factor> ---> < factor> - < term> | < term>
< term>   ---> x | y | z

выражение типа x - y * x - y - y * z может быть построено в проходах следующим образом:

x        y        x          y        y        z
<term> - <term> * <term>   - <term> - <term> * <term>
<factor>        * <factor> - <term> - <term> * <factor>
<factor>        * <factor>          - <term> * <factor>
<expr>          * <factor>                   * <factor>
<expr>                                       * <factor>
<expr>

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

          e
         /|\
        / | \
       e  *  f
      /|\     \
     / | \     t
    /  |  \     \
   /   |   \     z
  e    *    f
  |        /|\
  f       / | \
 /|\     f  -  t
f - t   /|\    |
|   |  f - t   y
t   y  |   |
|      t   y
x      |
       x

(На этой диаграмме потребовалось больше работы, чем я ожидал ...)

Answer 2

Это контекстно-свободная грамматика .Раздел «Алгебраические выражения» содержит пример дерева разбора, аналогичного тому, что вы хотите.

Answer 3

Чтобы ответить на ваш вопрос | используется для обозначения или как в программировании. Грамматика, которую вы разместили, хотя и выглядит так, что ее приоритет отключен. Обычно умножение имеет более высокий приоритет, чем сложение, но размещенная вами грамматика имеет обратную сторону, что может быть частью вашей проблемы.

Обычный способ исправить грамматику выражения (для ограниченного набора операций в вашем примере) -

expression = expression+ term 
           | term
term       = term * factor
           | factor
factor     = x 
           | y 
           | z

Таким образом, вы делаете умножения перед сложениями. Для x + y * z у вас будет следующее. Я не занимаюсь искусством ASCII, поэтому вам придется согласиться на S-выражения с операторами вместо запятых в качестве разделителей.

(Выражение (Выражение (термин (фактор х))) '+' (Термин (фактор у) '*' (фактор z)))