dynamic yacc-tables?
Ercument Canver
by yacc dynamically during parsing a text. I could think of a function like
yynewrule( _grammarRule_ );
which takes a grammar rule as input and extends the table appropriately. This
funtion may be called during parsing and returns an error code if there are
any problems (like shift/reduce, reduce/reduce, ...). Do extensions of that
type already exist for yacc? I am of course aware of the fact, that such a
parser would have to contain the entire functionality of yacc in addition.
This and the the necessity to keep the tables dynamic, rather than static as
in current yacc versions, would require rewriting of an completely new yacc.
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).
Thanx,
Ercument Canver
e-mail: can...@informatik.uni-ulm.de
[There have certainly been parsers that handle extensible and ambiguous
grammars, such as Irons' IMP72 at Yale and Wegbreit's EL/1 at Harvard. I
suspect that it's a losing battle to try and force yacc to do this. It'd be
easier to use some method driven more directly from the grammar. -John]
--
Send compilers articles to comp...@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
David Keppel
>[Modify the grammar for defining infix operators, overloading dynamically.]
Maybe:
%A Boris Burshteyn
%T On The Modification of the Formal Grammar At Parse Time
%J SIGPLAN Notices
%V 25
%N 5
%D May 1990
%P 117-123
%W pardo
%X * Parsers normally perform reductions and then call semantic action
routines.
* Many of the semantic actions are easily represented as specialized
parse rules e.g., ``ident = expr'' has a semantic action that checks
the type.
* Can also be represented as parsing ``int-ident = int-expr'',
``char-ident = char-expr'' and so on.
* However (a) large # of rules and (b) some types aren't known until
runtime.
* Add and delete grammar productions in a controlled way during
parsing e.g., ``int foo'' creates rules for ``ident-foo =
int-expr''.
;-D on ( Did you write your grammer a thank-you note? ) Pardo
Dan Salomon
>I got the following problem: I need to extend the parse tables generated
>by yacc dynamically during parsing a text.
Take a look at the paper:
"Incremental Generation of Parsers"
by J. Heering, P. Klint, & J. Rekers
in Proceedings of the SIGPLAN '89 Conference on Programming Language
Design and Implementation.
SIGPLAN Notices Vol. 24 Num 7 July 1989, pages 170-178.
They treat specifically this problem: updating an existing parser
according to new grammar rules. You may even be able to get source
for their experimental parser generator from the authors.
--
Dan Salomon -- sal...@ccu.UManitoba.CA
Dept. of Computer Science / University of Manitoba
Winnipeg, Manitoba, Canada R3T 2N2 / (204) 275-6682
Joshua Levy
>
>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).
You may want to attack the problem with lex instead of yacc. Read:
PARSING DISTFIX OPERATORS by Edgar H. Sibley in Commmunications of the ACM
February 1986, Vol 29, num 2, page 118.
Abstract:
The advantages of user-defined distfix operators -- a syntactic
convenience that enhances the readability of programs -- can be
obtained as an extension of almost any programming language without
requiring dynamic changes to the parser.
Conclusions:
We have described a simple technique whereby a fixed BNF grammar can
describe languages including user-defined infix, postfix, and distfix
operators. The technique requires only that the parts of disfix
operators be lexically distinguishable. ...
The idea has been successfully implemented [with YACC] with minimal
effort.
Note that "lexically distinguishable" means that lex can look up the
answer in a table, which can grow dynamically. I'm not sure how Sibley's
ideas interact with overloading.
Joshua Levy (jos...@veritas.com)
Jan Rekers
can...@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
This problem has partly been addressed in at least two articles:
J. Heering, P. Klint, and J. Rekers
Incremental generation of parsers
IEEE Transactions on Software Engeneering, 16(12):1344-1351, 1990
R.N. Horspool
Incremental generation of LR parsers
Computer Languages, 15(4):205-233, 1990
How to update an LR parse table _during_ parsing without disturbing the current
parse is an open problem.
Jan Rekers (rek...@cwi.nl) Centrum voor Wiskunde en Informatica (CWI)
P.O. Box 4079, 1009 AB Amsterdam, The Netherlands
Kjell Post
>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 kj...@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: kj...@cs.ucsc.edu
phone: 408 423 8760
Mark William Hopkins
>
>Background: I'm posting this request because I have to write a parser
>suitable for declaring mixfix operators and overloading.
Your real problem is not a need for a dynamic parser: your syntax remains the
same throughout the parse, it's the conflict resolution (precedences) and
symbol table interpretation that differ.
You'd like to write an expression syntax as simple as this:
%token unary_operator binary_operator
...
expression:
expression binary_operator expression |
unary_operator expression |
...
and use symbol table lookup's to distinguish what symbol/identifier is what
kind of operator during the parse. The scanner does all the work.
The real problem is that you'd also like to wrest direct control of YACC's
precedence declarations, so that you can alter them at run-time, and determine
them on the fly *from the lexical scanner* during the above-mentioned symbol
table lookup.
I don't know if YACC allows you to declare precedences dynamically. There may
be a some easy way of hacking the YACC source to get that feature.
All the above is standard fare for Prolog, whose expression syntax is
completely dynamic in just the way you describe above.
Avoiding YACC in the first place (which is regressive technology anyhow), you
could probably have an easier time doing the parser by hand, especially
considering you now have direct control over the operator precedence conflict
resolution.
Another way to resolve the problem (if the expression sub-syntax is
self-contained), is to declare an expression to YACC as a LEXICAL item, and
write up your own predecence parser, putting it in with rest of the lexical
scanner. Then you can exercise direct run-time control over precedence
conflicts and operator "fixity"-s.
[If you only want to change precedences and you have a moderate number of
possible precedences, it's not very hard in yacc. You declare a lexical token
per precedence, and write the grammar using those tokens as the operators.
The lexer passes the actual operator name as the semantic value that goes with
the token, so the lexer in effect assigns the precedence of each operator,
most likely by looking it up in a runtime table. -John]