Unambiguous grammar for arithmetic expressions with no redundant parenthesis

Question

I am looking for an unambiguous grammar for arithmetic expressions with no redundant parentheses. For example, parentheses are redundant in id+(id*id), but not in (id+id)*id.

Answer 1

It depends on exactly what you mean by 'for arithmetic expressions with no redundant parentheses'. This will accept expressions with no redundant parentheses, but will also accept arbitrarily nested parentheses:

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

mul_div ::= '*' | '/'

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

add_sub ::= '+' | '-'

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

I'm assuming that NUMBER manages to recognize signed numbers, so there is no unary plus or minus in there. You can work out how to handle them if you need them. You can also add variables etc if you need them.

If you mean a grammar that rejects expressions that have unnecessary parentheses, then I think you are on a search for the something that is not a context-free grammar.

Answer 2

You can easily do this. The only time when parentheses become necessary is a sum to the right of a subtraction, a sum to the right of a multiplication, or a sum or multiplication to the right of a division.

You want to parse the expression as such:

An expression is either a single value, or a sum or product.

A sum is the sum or difference of one or more multiplicative terms or individual values, which we add left to right, so we parse right to left; the right side of a subtraction can be a parenthetical sum (but not a parenthetical multiplication).

A product has either a value or a parenthetical sum to the right of it; parenthetical multiplications can be to the right of a division, too, but values cannot. Values can never be in parentheses.

expr      ::= sum
expr      ::= product
expr      ::= value


sum       ::= sum addsub prodvalue
sum       ::= prodvalue addsub prodvalue
sum       ::= sum '-' parensum
sum       ::= prodvalue '-' parensum

addsub    ::= '+' | '-'

parensum  ::= '(' sum ')'

prodvalue ::= value
prodvalue ::= product

product   ::= prodterm muldiv value
product   ::= prodterm muldiv parensum
product   ::= prodterm '/' parenprod

prodterm  ::= prodvalue
prodterm  ::= parensum

parenprod ::= '(' product ')'

value     ::= [0-9]+.?
value     ::= [0-9]*.[0-9]+

I'm pretty sure this I hope this helps!

Editing some time later: I had made some mistakes, namely that I didn't handle addition correctly. I realized that subtraction is a problem. I've simplified the system and fixed the problems.

The only time parentheses can show up is around a nontrivial product that is to the right of a division, or around a nontrivial sum that is to the right of a division, a multiplication, or a subtraction, or around a sum that is at the left of a product.