Re: dynamic yacc-tables?

In article 91-08-043 canver@cyborg.informatik.uni-ulm.de (Ercument Canver) writes:
>I got the following problem: I need to extend the parse tables generated
>by yacc dynamically during parsing a text. I could think of a function like
>
[...]
>Background: I'm posting this request because I have to write a parser suitable
>for declaring mixfix operators and overloading.
>
>I'd also appreciate pointers to parser generaters dealing with this kinda
>problem (not necessarily yacc-like).
>


We have an LR parser-generator available that might do what you need.
The abstract from the paper follows. Source code and documentation can
be obtained by sending a mail to kjell@cs.ucsc.edu.


Regards,
--Kjell
-----------------------------------------------------------------------------
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 parse 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. The
table-driven style of dynamic operator parsing presented in this
paper is easier to use, less ad hoc, and more powerful than the
methods currently in use. For instance, the input grammar for
Standard ML can be taken right out of its formal language definition.
We have also been able to describe several versions of Prolog, a
language known for its liberal use of operators. Definite clause
grammars (DCGs), a novel parsing feature of Prolog, can be translated
into efficient code by our parser generator. The implementation has
the advantage that the token stream need not be completely acquired
beforehand, and the parsing, being deterministic, is approximately
linear time. Conventional implementations based on backtracking
parsers can require exponential time. However, some work remains on
the handling of ``inherited attributes'', which correspond roughly to
``input'' arguments to the goal of the DCG. Aside from the
applications of the parser generator, its implementation in Prolog
demonstrates the power of logic programming techniques for
sophisticated software development.


--
Kjell Post, CS Grad student
Univ of California, Santa Cruz
email: kjell@cs.ucsc.edu
phone: 408 423 8760
--

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