Unambiguous grammar for arithmetic expressions with no redundant parenthesis

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 (开发者_如何学JAVAid+id)*id.

You can easily do this. The only time when parentheses become necessary is when there's a sum expression as one of the pieces of a multiplication expression, or some expression as the second piece of one of the division expressions. In either of these cases, you can ensure that the parentheses aren't redundant by forcing the material inside the parentheses to have at least one bare operator (not surrounded by further parentheses).

I guess I might be helping you answer a question for an entrance exam or homework, which I don't much like, but everyone calling this impossible or suggesting that it might be impossible is wrong and I wanted to set them straight.

You want to parse the expression as such:

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'*

A lone value can never have parentheses around it. Units are the subexpressions of multiplication expressions; produnits allow for parenthetical tails to your division expressions. (5) would be ( value ), which is impossible, because only produnits and units have parentheses, and they require some arithmetic operator to occur inside the parentheses if they are present. ( value ) can not be derived from any expression, and ( ( anything ) ) is not possible, because only produnit and unit derive parentheses. Looking closely, produnit requires a * or a / to occur if a parenthesis is derived, or for it to parse as a unit, or a value without parentheses. unit requires a + or a - to occur, or no parentheses.

( ( 5 + 6 ) ) fails because ( 5 + 6 ) can only parse as a unit, which could make it a produnit, but there's no way to put parentheses around a lone produnit - there is no chain which turns a unit or a produnit into parentheses around a lone produnit.

I'll break down my choices for you: 5*(6*7) does not parse - it's a term times a unit, you would think, but then (6*7) is not a unit, because units have to be values or parentheses around expressions with at least one sum. Once at least one sum occurs, the parentheses aren't trivial. On the other hand, 5/(6*7) is not the same as 5/6*7 at all - the first is like 5/6/7, and the second is like 5*7/6. However, 5/(6) is the same thing as 5/6 - single values can not occur inside parentheses. Likewise, 5/(6/7) is not the same as 5/6/7 because the first is the same as 5*7/6 and the second is the same as 5/(6*7). In other words, parentheses around the denominator are never extraneous if there's a bare operator inside.

(5+6)+7 is also impossible, because the left hand side (and the right hand side) of a sum are either strict values, sums without parentheses around the sum, or products without parentheses around the product. There's no way to turn

You can convince yourself that these hold, and check for yourself that it's unambiguous. You could demonstrate to yourself that it holds by extending it to include the exponentiation operator, or even better generalize it to higher precedence operators, or lower precedence operators, like == or <.

I hope this helps!

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.