Re: YACC embedded actions

Re: YACC embedded actions

[Chris F Clark]

While it is not as simple and concise as Anton's solution, a common
solution to your problem is to build an AST (abstract syntax tree) as
you parse the expression, and then walk the tree (in-order is usually
the correct traversal here) to recreate (a paraphrase of) the original
text.  The advantage of the AST approach over the straight-forward
approach is that you can manipulate the tree before printing it (or
storing it as a string), for example to produce a more optimal
expression.

By using the "visitor pattern", you can easily write several tree
traversals: one that evaluates the tree, one that prints it, one that
generates code, etc.

Note, it is easy to build an AST by hand.  Simply collect all the
relevant operands off the parse stack into a data structure at each
reduction.  There are also tools for many of the parser generators
(including yacc I'm certain, try the Gentle toolkit for instance)
either as add-ons or as part of the generator itself.

Warning ranting and kvetching follows:
By the way, one nit I have with many yacc calculator tutorials is that
they do all evaluation as part of the parsing pass.  While that is
sufficient to create a simple calculator, it doesn't scale to more
serious applications.  In my opinion, it leads many yacc users down a
bad path.  (Aside from implementing a simple calculator I can't
imagine wanting to do evaluation during parsing.)  As you might guess,
for the calculator tutorial in Yacc++ we use the tool's AST building
facility and then implement a couple of traversals to "run" the
program and to "list" it ala Basic.  The fact that we build an AST
also makes it easy to have loops and other control structures in our
calculator.  One of my tip-offs to someone having been mislead by a
simple calculator example is when they ask how to reparse text over
and over again real fast (i.e. they are looping by reparsing the
input rather than just rewalking a tree).

Hope this helps,
-Chris

*****************************************************************************
Chris Clark                    Internet   :  compres@world.std.com
Compiler Resources, Inc.       CompuServe :  74252,1375
3 Proctor Street               voice      :  (508) 435-5016
Hopkinton, MA  01748  USA      fax        :  (508) 435-4847  (24 hours)
------------------------------------------------------------------------------
Web Site in Progress:          Web Site   :  http://world.std.com/~compres