Re: Parsing expressions without outer parentheses

Frank Heckenbach wrote:


> 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.
. . .
> The disadvantage of this solution is that is basically doubles the
> number of nonterminals required. Is there any better way?


Unfortunately, there is not a better way to do it in the grammar.
This is very similar to the nested-if problem, where the same doubling
occurs when one tries to write a strict grammar that captures the
precise nesting rules.


It is a fundamental limitation of conflict-free grammars that this is
so. To capture external state in a tree of productions, you have to
duplicate the productions (once for inside the state, and once for
outside).


Grammar writers run into the same problem when they try to capture
semantic type information in the state. If you want different rules
for integer, real, and boolean productions, but otherwise they share
the same expressions, one ends up with three copies of the expression
rules.


Note, in addition to having more rules in the grammar, one also ends
up with more states in the state machines (if one is using a table
driven approach) or more recursive routines in one is using recursive
descent.


A similar problem occurs in SQL where null lists are special. Many
query language parser authors have driven themselves crazy trying to
work out how to propogate the right null list restrictions
syntactically through the grammar.


Essentially, a grammar is not a good way to capture that information.
An attribute grammar, in contrast, is a good way to capture that
information.


If you really want to capture that information and do it
"efficiently". It is better to have a grammar that allows
paranthesized expressions even in the contexts you don't desire them
and in a separate check (or pass), detect the undesired case where the
top-most expression is simply a parenthesis wrapper.


However, in my opinion, the fact that it is not easy to write
grammatically, should in may cases suggest something. That something
is a sense of warning in that you are making something that mixes
syntax and semantics. It is likely that you want to prohibit
expressions with outer parenthesis because they represent some
specific semantic condition. However, constraining the symtax to
match the semantics means you are actually making something complex,
especially when it makes the grammar more complicated to express the
desired syntax. If that warning rings true for you, and if you have
control to change the decision, please heed it.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)

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