Недвусмысленная грамматика для арифметических выражений без избыточной скобки

Question

Я ищу однозначную грамматику для арифметических выражений без лишних круглых скобок. Например, круглые скобки являются избыточными в id+(id*id), но не в (id+id)*id.

Answer 1

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

expr ::= factor 
expr ::= factor mul_div factor 

mul_div ::= '*' | '/' 

factor ::= term 
factor ::= term add_sub term 

add_sub ::= '+' | '-' 

term ::= NUMBER 
term ::= '(' expr ')' 

Я предполагаю, что ЧИСЛО удается распознать подписанные номера, так что нет унарных плюс или минус там. Вы можете решить, как обращаться с ними, если они вам понадобятся. Вы также можете добавить переменные и т. Д., Если они вам понадобятся.

Если вы имеете в виду грамматику, которая отвергает выражения, которые имеют ненужные круглые скобки, тогда я думаю, что вы ищете что-то, что не является контекстно-свободной грамматикой.

Answer 2

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

Я думаю, что я могу помочь вам ответить на вопрос о вступительном экзамене или домашнем задании, что мне не очень нравится, но все, кто говорит об этом невозможным или предлагая, что это может быть невозможно, ошибочны, и я хотел их прямо установить ,

Вы хотите разобрать выражение, например:

expr  ::= expr addsub term 
expr  ::= prodterm 
expr  ::= value 

sum  ::= expr addsub term 

addsub ::= '+' | '-' 

term  ::= prodterm 
term  ::= unit 

prodterm ::= term '*' unit 
prodterm ::= term '/' produnit 

unit  ::= '(' sum ')' 
unit  ::= value 

produnit ::= unit 
produnit ::= '(' prodterm ')' 

value  ::= '0-9'* 

Одинокая значение никогда не может иметь круглые скобки вокруг него. Единицы - это подвыражения выражений умножения; produnits позволяют вставлять скобки в ваши выражения разделения. (5) будет (значение), что невозможно, потому что только у единиц и единиц есть круглые скобки, и они требуют, чтобы в круглых скобках находился некоторый арифметический оператор, если они присутствуют. (значение) не может быть выведено из какого-либо выражения, и ((ничего)) невозможно, потому что только производные и единицы выводятся в круглые скобки. Если вы внимательно изучаете, produnit требует, чтобы * или a/возникали, если была выведена скобка или для ее анализа в качестве единицы или значение без круглых скобок. единицам требуется a + или a - или нет скобок.

((5 + 6)) терпит неудачу, потому что (5 + 6) может анализировать только как единицу, что может сделать ее продуницей, но нет способа поставить круглые скобки вокруг одиночного изделия - нет цепи, которая поворачивается блок или изделие в круглые скобки вокруг одиночного продукта.

Я сломаю свой выбор для вас: 5 * (6 * 7) не анализируется - это термин, когда вы единицу, вы думаете, но тогда (6 * 7) не является единицей, потому что единицы должны быть значениями или круглыми скобками вокруг выражений с хотя бы одной суммой. Когда происходит хотя бы одна сумма, скобки не являются тривиальными. С другой стороны, 5/(6 * 7) совсем не совпадает с 5/6 * 7 - первое похоже на 5/6/7, а второе похоже на 5 * 7/6. Однако 5/(6) - это то же самое, что и 5/6 - одиночные значения не могут встречаться в круглых скобках. Аналогично, 5/(6/7) не совпадает с 5/6/7, потому что первый такой же, как 5 * 7/6, а второй такой же, как 5/(6 * 7). Другими словами, круглые скобки вокруг знаменателя никогда не являются посторонними, если внутри есть голый оператор.

(5 + 6) +7 также невозможно, так как левая часть (и правая сторона) суммы - это либо строгие значения, либо суммы без круглых скобок вокруг суммы, либо продукты без круглых скобок вокруг продукта.Невозможно повернуть

Вы можете убедить себя, что они держат и проверяют, что это однозначно. Вы могли бы продемонстрировать себе, что это выполняется, расширяя его, чтобы включить оператор экспоненции, или даже лучше обобщить его на более высокоприоритетные операторы или операторы с более низким приоритетом, например == или <.

Надеюсь, это поможет!