Re: request for simple example: parse tree generation

>I'm looking for a *simple* example that shows how to generate
>an explicit parse tree using yacc. Since the tool is used a lot,
>I thought there would be some sort of "standard" way of doing this.


>[Yeah, I wanted to put some examples of that in the book, but ran out of
>time and pages. It's pretty straightforward, generate subtrees each time
>you reduce a rule and splice them together as you go, ending up with one
>big tree when the parse is done. -John]


I'm not sure I should 'jump' at this and put a 'plug' for our 'termp
processor' Kimwitu here, but it is perfect for this kind of thing
(yes, I'm biased, I know :-). Instead of using


|> ParseTree(opcode,...) constructs a tree node


to construct tree nodes, you would use a small grammar to describe
your (abstract syntax) tree, from which Kimwitu would generate data
structure definitions and create-routines (and lots of others). (and
later on you would use pattern matching in your routines that convert
your tree into another one, and use unparse rules to define your
output... :-) For this example you would use Kimwitu input like:


expr
: opMULT( expr expr )
| opDIV( expr expr )
| opREM( expr expr )
| opMOD( expr expr )
| opCONDEXP( expr expr expr )
...
;


Given such input, Kimwitu will generate C routines like:
expr opMULT( expr expr1, expr expr2 );
that (in this case) takes two expr subtrees and combines them with a
opMULT node.


|> Here the stack is used both to pass tree nodes (as in product_expr)
|> and opcodes (as in product_op).


I have adapted Alex' example to use the Kimwitu generated routines:


   product_expr
   : product_expr '*' cast_expr
   { $$ = opMULT($1,$3); }
   | product_expr '/' cast_expr
{ $$ = opDIV($1,$3); }
| product_expr '%' cast_expr
   { $$ = opREM($1,$3); }
| product_expr tkMOD cast_expr
{ $$ = opMOD($1,$3); }
| cast_expr { $$ = $1; }
;


conditional_expr /* AC: could be called simple_expr */
: infix_expr { $$ = $1; }
| infix_expr '?' expr ':' conditional_expr
{ $$ = opCONDEXP($1,$3,$5); }
;


assignment_expr
: conditional_expr { $$ = $1; }
| unary_expr assignment_operator assignment_expr
{ $$ = ParseTree($2,$1,$3); }
/* here we would also use some kind of operator instead of ParseTree */
|> ;
|>
|> single_expr /* no commas */
|> : assignment_expr { $$ = $1; }
|> ;
|>


For more information on Kimwitu follow the kimwitu links at
    <URL:http://wwwtios.cs.utwente.nl/lotos/#tools>
A _very_ small example of using it with yacc and lex from the manual:
  <URL:http://wwwtios.cs.utwente.nl/doc/tp.man/node23.html>
  (NOTE: this last link may change over time)


Hope this is of some use,
Axel.
--
  <Axel.Belinfante@cs.utwente.nl> <URL:http://www.cs.utwente.nl/~belinfan/>
    University of Twente, Dept. of C.S., Tele-Informatics & Open Systems Group
  P.O. Box 217; NL-7500 AE Enschede. Phone: +31 53 4893774; Fax: +31 53 4893247
--

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