Introducing new operators (Kjell Post)
Tue, 22 Sep 1992 02:38:35 GMT

          From comp.compilers

Related articles
Introducing new operators (1992-09-22)
Re: Introducing new operators (1992-09-23)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Kjell Post)
Organization: University of California, Santa Cruz (CE/CIS Boards)
Date: Tue, 22 Sep 1992 02:38:35 GMT
Keywords: parse, LR(1), design

There was a discussion about introducing new operators recently. We have
developed a parser generator that works like Yacc, with the added
extension of supporting dynamic operators. A dynamic operator can be any
legal identifier or symbol (even built-ins like "+" and "*"); the
syntactic properties of an operator can be changed by the user during
parsing of input; operators can act as arguments to other operators, and
operators can be overloaded, in that a single identifier can be used as
the name of two or more syntactically different operators.

We are about to submit a paper to a journal. The abstract follows below.
Send me mail if you are interested in the full paper.

Kjell Post (
            Deterministic Parsing of Languages with Dynamic Operators

Allowing the programmer to define operators in a language makes for more
readable code but also complicates the job of parsing; standard parsing
techniques cannot accommodate dynamic grammars. We present an LR parsing
methodology, called Deferred Decision Parsing, that handles dynamic
operator declarations, that is, operators that are declared at run time,
are applicable only within a program or context, and are not in the
underlying language or grammar. It uses a parser generator that takes
production rules as input, and generates a table-driven LR parser, much
like Yacc. Shift/reduce conflicts that involve dynamic operators are
resolved at parse time rather than at table construction time.

For an operator-rich language, this technique reduces the size of the
grammar needed and parse table produced. The added cost to the parser is
minimal. Ambiguous operator constructs can either be detected by the
parser as input is being read or avoided altogether by enforcing
reasonable restrictions on operator declarations. We have been able to
describe the syntax of Prolog, a language known for its liberal use of
operators, and Standard ML, which supports local declarations of

Post a followup to this message

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