Parsing expressions without outer parentheses

I have a usual grammar for artihmetic expressions with several
levels of precedence, such as the following (strongly simplified,
bison syntax):


    expression: simple_expression | expression '=' simple_expression;


    simple_expression: term | simple_expression '+' term;


    term: factor | term '*' factor;


    factor: primary | factor '^' primary;


    primary: constant | '(' expression ')';


Now I want to accept only expressions which are not completely
enclosed in a pair of parentheses, e.g. `(1) + (2)' would be
accepted, but `(1 + 2)' would not.


So far I've come up with the following grammar:


    expression: simple_expression | expression_par '=' simple_expression_par;
    expression_par: expression | par;


    simple_expression: term | simple_expression_par '+' term_par;
    simple_expression_par: simple_expression | par;


    term: factor | term_par '*' factor_par;
    term_par: term | par;


    factor: primary | factor_par '^' primary_par;
    factor_par: factor | par;


    primary: constant;
    primary_par: primary | par;


    par: '(' expression_par ')';


The disadvantage of this solution is that is basically doubles the
number of nonterminals required. Is there any better way?


(I know I could perhaps use bison's precendence rules to put all
operators into a single nonterminal, but I'd prefer to write a
conflict-free grammar.)


Frank


--
Frank Heckenbach, http://fjf.gnu.de/
GnuPG and PGP keys: http://fjf.gnu.de/plan (7977168E)

Return to the comp.compilers page.
Search the comp.compilers archives again.