однозначную грамматику для работы возведения в степень

Question

E -> E+T | E-T | T 
T -> T*F | T/F | F 
F -> i | (E) 

Как я могу изменить эту грамматику, чтобы разрешить операцию возведения в степень ^ так что я могу написать i+i^i*i? Поскольку мы знаем, что порядок операций выше для ^, тогда все, что я знаю, это то, что я должен сделать его правильным ассоциативным.

Answer 1

В EBNF (Extended Backus-Naur Form), это может выглядеть следующим образом:

expr -> term [ ('+' | '-') term ]* 
term -> factor [ ('*' | '/') factor ]* 
factor -> base [ '^' exponent ]* 
base -> '(' expr ')' | identifier | number 
exponent -> '(' expr ')' | identifier | number 

(взято из here)

Перевод на вашей нотации (без различия между числами и идентификаторы):

E -> E+T | E-T | T 
T -> T*F | T/F | F 
F -> F^X | B 
B -> i | (E) 
X -> i | (E) 

Для ясности можно объединить «B» и «X».

Answer 2

Симметрично, как показано ниже.

E -> E + T | E - T | T 
T -> T * F | T/F | X 
X -> X^Y | Y 
Y -> i | (E) 

Объяснение:
==========
Заметим, что это грамматика однозначна. Для того, чтобы сгенерировать выражение состоит из операторов ^, *, /, +, -, во-первых, мы должны начать писать шаги, в которых низший приоритет операторов, так что +, - могут быть добавлены прежде, чем выше один, т.е. */. А затем ^ можно добавить в целевое выражение в конце. Следовательно, в дереве абстрактного синтаксиса (синтаксического дерева) оператор ^ будет отображаться внизу (в сторону листьев). Таким образом, если мы оценим это выражение в соответствии с деревом, то сначала выполним ^.

Примечание: В соответствии с правилами грамматики, в сентиментальной форме X -> O^Y мы не можем вернуться назад, чтобы добавить +, - .., Но если у вас есть какие-либо сентиментальное форму из E+T | E-T | T тогда мы можем еще добавить другие операторы снова. Итак, в этой форме грамматики мы контролируем поток генерации любого допустимого выражения (строки), принадлежащего языку грамматики. (Это то, как управлять приоритетом оператора в однозначном).

Например, чтобы произвести выражение i + i^i * i, мы не можем, как E --> T --> X ---> X^Y, потому что, как только вы X^Y вы не можете добавить +, - (без скобок (E)).

Возможный выбор, чтобы сгенерировать выражение i + i^i * i выглядит следующим образом:

E --> E - T --> E + T - T --> E + X - T --> E + X^Y - T --*--> i+i^i*i 

`--*-->` means more than one step 

оператор ^ добавляется в последнем шаге

Примечание (так может появиться в нижней части в дереве, как показано ниже на схеме):

дерево будет что-то вроде:

     E 
       /| \ 
       /| \ 
       E - T <-- - evaluates 3rd 
      /| \  ' 
      /| \ ' 
      E + T i <-- + evaluates 2nd 
      '  |  
      '  | 
      i  X 
       /| \ 
       /| \ 
       X ^ Y  <--^evaluates first 
       '  ' 
       '  ' 
       i  i 
    NOTE: 

    in tree ' means more than one steps 
      ' 
    ^has higher precedence 

    because of Left to right associativity + evaluated before then -  

Когда вы начинаете оценивать это дерево, то ^ будет б e оценивается первым.

Помните, что операторы с высоким приоритетом всегда добавляются снизу, поэтому грамматика должна быть такой, чтобы операторы могли быть добавлены позже (в синтезе предложения).

_{(вы должны понять, почему в вашей грамматике + и - может быть непосредственно генерируются через E и через T вы можете добавить *, /. Почему другие однозначную версии E -> E*T | E/T | T, T -> T+F | T-F | X не правильно! Где, как язык, порожденное этим грамматика и ваша грамматика эквивалентны. Причина в том, что ваша грамматика генерирует правильное дерево из оценочной точки уважения)}

Кроме того, если вы пишете парсер с использованием инструмента YACC. Вы можете использовать двусмысленную версию этой грамматики с меньшим количеством производственных правил и задавать приоритеты операторов вне правил грамматики (что даст приблизительное представление о том, какой оператор должен сначала оценить, а следовательно, как построить дерево). И это будет предпочтительным способом, чем эта однозначная форма, потому что меньшее количество правил производства строит меньшее дерево в высоком (следовательно, эффективный компилятор - занимает меньше времени для синтаксического анализа).

Answer 3

Оба предоставленных здесь ответа неверны. В этих ответах^ассоциируется слева, когда на самом деле он должен ассоциироваться с правом. Правильная модифицированная грамматика должна быть:

E -> E+T | E-T | T 
    T -> T*X | T/X | X 
    X -> F^X | F //Note: it's F^X not X^F 
    F -> i | (E) 

Таким образом, ваша грамматика работает, как ожидалось, с выражением, как:

a+b^c^d^e*f 

Спасибо!