Parsing expressions without outer parentheses

Frank Heckenbach <frank@g-n-u.de>
27 Apr 2003 02:23:12 -0400

          From comp.compilers

Related articles
Parsing expressions without outer parentheses frank@g-n-u.de (Frank Heckenbach) (2003-04-27)
Re: Parsing expressions without outer parentheses cfc@world.std.com (Chris F Clark) (2003-05-05)
Re: Parsing expressions without outer parentheses slk15@earthlink.net (SLK Parsers) (2003-05-06)
Re: Parsing expressions without outer parentheses pjj@cs.man.ac.uk (Pete Jinks) (2003-05-06)
Re: Parsing expressions without outer parentheses hannah@schlund.de (Hannah Schroeter) (2003-05-12)
Re: Parsing expressions without outer parentheses frank@g-n-u.de (Frank Heckenbach) (2003-05-24)
Re: Parsing expressions without outer parentheses frank@g-n-u.de (Frank Heckenbach) (2003-05-24)
| List of all articles for this month |

From: Frank Heckenbach <frank@g-n-u.de>
Newsgroups: comp.compilers
Date: 27 Apr 2003 02:23:12 -0400
Organization: Compilers Central
Keywords: parse
Posted-Date: 27 Apr 2003 02:23:12 EDT

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)


Post a followup to this message

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