Re: parsing with user defined operators (Michael Lee Finney)
15 Aug 1999 10:43:35 -0400

          From comp.compilers

Related articles
parsing with user defined operators (1999-08-12)
Re: parsing with user defined operators (Torben Mogensen) (1999-08-13)
Re: parsing with user defined operators (1999-08-15)
Re: parsing with user defined operators (Dr A. N. Walker) (1999-08-27)
Re: parsing with user defined operators (rspartan) (1999-08-27)
Re: parsing with user defined operators darcy@moa.CS.Berkeley.EDU (1999-08-28)
| List of all articles for this month |

From: (Michael Lee Finney)
Newsgroups: comp.compilers
Date: 15 Aug 1999 10:43:35 -0400
Organization: (
References: 99-08-053 99-08-057
Keywords: parse, syntax

Roy Germon wrote:
> > I'm looking for parsing techniques to handle expressions that include
> > user defined operators and overloaded operators. The precedence
> > levels of operators are user definable over a range of several hundred
> > values. The associativity is user definable as well. Any pointers to
> > books or articles are more than welcome. says...
> There are several ways of doing this.
> 1) Parse all operators with the same associativity and
> precedence. The use a second pass over the syntax tree to change
> the structure to reflect the precedences. This means that
> parentheses must be visible in the syntax tree.
> 2) Define a lexical token for each possible precedence/associativity
> combination. Give the lexer access to a table that contains the
> precedences of all user-defined operators and use this to assign
> the correct lexical token to the operator (the operator name is
> now an attribute to the token).
> 3) Make a modified LR-parser that can resolve conflicts at
> parse-time. The parser will look up the precedences in a table
> when it has to resolve a conflict.
> The first is the conceptually simplest method and has a small
> parse-table, but requires an extra pass. The second requires a simple
> fix in the lexer, something that can usually be done in the lexer
> specification without having to fix the generated lexer. The
> parse-table will be fairly large as it has to handle a (potentially)
> large number of precedence/associativity combinations. The third
> alternative requires use of a non-standard parser-generator or else a
> modification of the generated parser, which may be complex. But it
> uses a small parse-table and no extra pass.

Another possibility is to use a dynamic grammar that is altered by the
operator definitions as they are encountered. If the dynamic grammar
is implemented using generic routines then that might be a more direct
approach. I must add that I do like solution (2) very much -- it
might also be viewed as a method of creating a dynamic grammar because
each of those those special tokens would have to handled in a grammar
that essentially would only parse a subset of the possible rules.
Each time an operator is defined that uses one of those tokens, you
"activate" a new grammar rule which essentially make the grammar
dynamic over a predefined range.

Michael Lee Finney

Post a followup to this message

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