Грамматика для выполнения арифметических операций.

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

V_т ={I , X , + , ( , )}

V_n ={ E }

E

R = {Ei+E;EI;Ei*E;E{E}}

E=>i+E=>i+E=>i+(E)=>i+(i*E)=>i+(i*i)

Набор данных правил не обеспечивает скобки для первых операндов.

V_т ={I , X , + , ( , )}

V_n ={ E }

E

R= {EE+E;EE*E;E(E);Ei}

E=>E+E=>E+E*E=>i+i*I (1244)

E=>E*E=>E*i=>E+E*i=>i+i*i(24144)

Для одной и той же цепочки получили два синтаксического разбора, следовательно грамматика не однозначна.

Грамматика не обеспечивает приоритет операций сложение и умножение. Чтобы обеспечить приоритеты операций мы можем операции суммирования сделать в скобках, тогда:

R = (E9E+E);EE*E,Ei)

E => (E+E) => (E+(E*E)) => (i+(i*i))

E => (E*E) => ((E+E)*E) => ((i+i)*i)

Грамматика получилась неоднозначной, однако каждая операция оказалась в своей скобке.

Приоритетность операции умножить по отношению к операции сложить обеспечивается благодаря скобкам.

V_т = {I, * , + , ( , )}

V_n={E,T,P}

E– арифметическое выражение

Т – слагаемое (или терм)

Р – произведение или сам множитель

R={ET,EPPP*P,P(T)*P,PP*(T)*P,PP*P,PI,TT+P,TP+T,TP+T,TT+T,Ti}

Нужно получить : i + i * i

8,8 i+P*P

5 i+P

12 T+P

9 T

3 E

E=>T=>T + P => либоT+(T)*P=>T+(T)*I либо i+P=>i+(I)*P=>i+(T+T)*P либо i+(T+T)*i=>i+(i+i)*I либо T+(T+T)*i=>i+(i+i)*i

Данная грамматика полностью удовлетворяет требованиям арифметической операции для умножения и суммирования, однако она не однозначна. Если в правилах в правой части существует два разных нетерминальных символа, то грамматика будет неоднозначна.