I am working on a little parsing problem, trying to use Zebu 3.5.5
with CMUCL ("release x86-linux 2.4.20 1 June 2000 build 710"). I am
working with some proprietary software that, thankfully, saves a data
file in ASCII. The data file represents a graph of nodes. Each node
contains a definition in terms of other nodes. The node definitions
are infix with operators at eight precedence levels, plus a few extra
wrinkles. Basically, I want to transform the infix definitions into
Lisp expressions. I am a novice at this kind of parsing problem. I
have tried reading parts of the Aho, Sethi, Ullman's _Compilers:
Principles, Techniques, and Tools_, but mostly I have succeeded in
making my head hurt. I have also read the Zebu documentation as well
as Flex/Bison documentation.
I am most confused about how to express the operator precedence in an
appropriate grammar for Zebu. I notice bison/yacc has special
directives to specify operator precedence, which do not seem to appear
in Zebu grammars. I have seen an example using different nonterminals
to represent the precedence, but it is for a fairly simple example and
it isn't clear to me how it generalizes.
Can anyone help point me in the right direction?
Thanks!
--
Russell Senior ``The two chiefs turned to each other.
·······@aracnet.com Bellison uncorked a flood of horrible
profanity, which, translated meant, `This is
extremely unusual.' ''
Russell Senior <·······@aracnet.com> writes:
> I am most confused about how to express the operator precedence in an
> appropriate grammar for Zebu. I notice bison/yacc has special
> directives to specify operator precedence, which do not seem to appear
> in Zebu grammars. I have seen an example using different nonterminals
> to represent the precedence, but it is for a fairly simple example and
> it isn't clear to me how it generalizes.
>
If you have that many precedence levels consider a specialized parser
for the expressions. Many C/C++ compiler do the same, starting with
the original pcc.
You basically push components onto a stack until you're sure about the
precedence of their surrounding operators. The subject tends to come
up fairly often here and in comp.lang.scheme as converting infix to
prefix or postfix is a popular homework exercise.
--
Lieven Marchand <···@wyrd.be>
Gla�r ok reifr skyli gumna hverr, unz sinn b��r bana.
+ Lieven Marchand <···@wyrd.be>:
| If you have that many precedence levels consider a specialized parser
| for the expressions. Many C/C++ compiler do the same, starting with
| the original pcc.
|
| You basically push components onto a stack until you're sure about the
| precedence of their surrounding operators.
Or you might write a Pratt parser. The basic idea is really simple,
and well suited for languages defined by unary (prefix or postfix) and
binary operators and precedence levels. Save this modern grammar
stuff for when it's *really* needed... 8-)
Reference:
Vaughan R. Pratt, Top down operator precedence
ACM symposium on principles of programming languages, 1973.
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- Yes it works in practice - but does it work in theory?