Почему эта грамматика EBNF неоднозначна?

Question

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

Ниже грамматика в EBNF, который описывает простые арифметические выражения, как 1 + 2 * 3 - 4:

Expression = Operand, {Operator, Operand}; 
Operand = "1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"; 
Operator = "+"|"-"|"*"|"/"; 

(IV) Используя эту грамматику, существует несколько способов вычисления выражения например, 1 + 2 * 3 - 4. Опишите два из них и объясните, что такое , это означает о предоставляемой грамматике. [2 балла]

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

Рекомендации?

Answer 1

У вас есть часть ответа в вашем вопросе.

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

Да; Вы почти правы, когда думаете, что это подразумевает проблему с порядком приоритета грамматик, и да, эта грамматика не имеет. В этом и заключается проблема: всем операторам присваивается одинаковый приоритет, и, следовательно, разные выводы приводят к различным ответам на оценку примера.

Мы могли бы сократить 1 + 2 * 3 - 4 ни в одну:

(1+2) * (3-4) 
1 + (2 * 3) - 4 
1 + (2 * (3 - 4)) 

в зависимости от того, как обрабатываются старшинство операторов.

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