I thought the sometimes-required-parentheses rule was interesting. Here's what I came up with in 30 minutes using ANTLR. Highly recommend it! The ANTLRWorks grammar IDE is incredibly useful -- it shows rules and trees visually, and can single-step the generated code so you can see your parse tree being built one token at a time.

The following grammar accepts input like 3 + (5 * 7) but rejects 3 + 5 * 7.

The key is that, if your expression doesn't start with a parenthesis, you know that all the operators at that level have to be the same. (I assume that sums or products of several things like 1 + 5 + (2 * 3) are permitted without parenthesizing further.)

Also, tool choice matters. ANTLR is an LL parser and Yacc/Bison are LR parsers; IMHO with LL it's much easier to understand what's going on. This grammar would need substantial rewriting for Yacc to deal with the fundamental differences between LL and LR parsing.

(edited to deal with HN markup issues related to asterisks and fix implementation bugs)

grammar parencheck;

prgm : expr EOF ;

expr : atom ( (PLUS poratom)*

             | (TIMES poratom)* )

      | '(' expr ')' ;

poratom : atom | '(' expr ')' ;

atom : INT | VAR ;

PLUS : '+' ;

TIMES : '*' ;

INT : ('0'..'9')+ ;

VAR : ('A'..'Z' | 'a'..'z' | '_')+ ;