[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Building a parse tree...
|
From: |
Steve Fernandez |
|
Subject: |
Re: Building a parse tree... |
|
Date: |
Sun, 19 May 2002 20:56:56 +0530 |
Hans Aberg wrote:
Thank you very much for the quick reply. Well, thought about
what you
said, but I figured out a problem. How will you know which branch to
attach
the resulting new branch, and whether it will be the left/right child of
the
parent? I don't know if the above question is valid or not, but still I
couldn't figure out an answer. Well, I did create a parse tree
successfully,
and I did it using the postfix expression generated by the parser built
by
bison.
I found that if i return the number itself from the rule
specifying
the identifier in expr, as well as all the operations ( +,- etc ) when
two
numbers are reduced using them, this results in the postfix expression
of the
given expression. Now using this, I was able to build a parse tree and
traverse it successfully using in, pre and post orders. I have attached
the
code herewith.
BTW, I don't know if this is the right place to say this, but
I'm in
the process of building a C compiler for myself.....a Herculerian task,
no
doubt, but I'm halfway through the lexical analyser part, and it is
faster
than the lex generated by lex.........and I can make several
optimizations to
it. Anyone interested in working together? Please do reply.
Thanks once more for all the help.
Regards,
Steve Fernandez.
> Reply-to: address@hidden
>
> At 09:10 +0530 2002/05/18, Steve Fernandez wrote:
> > I'm really sorry if this isn't the place to ask my question, but
> >I found no other. I am a novice as far as bison is concerned. I wrote a
> >desktop calculator, a common exercise, to compute the value of an
> >arithmetic expression. The result was correct. But I need to construct a
> >parse tree for the expression. Now I discovered that I could get the
> >postfix form of the input expression from the parser, and is there some
> >way to build a parse tree using this? Or is there an easier way?
>
> You need to build the parse tree by putting into the grammar suitable
> actions that constructs the parse tree during runtime.
>
> I have not needed to do this in practise myself, but here is a suggestion:
>
> If your original calculator grammar has say:
> expr: expr '+' expr { $$.value = $1.value + $3.value }
> | expr '-' expr { $$.value = $1.value - $3.value }
> | expr '*' expr { $$.value = $1.value * $3.value }
> | expr '/' expr { $$.value = $1.value / $3.value }
> | expr '^' expr { $$.value = pow($1.value, $3.value) }
> | '(' expr ')' { $$.value = $2.value }
> | '-' expr %prec UMINUS { $$.value = -$2.value }
> | IDENTIFIER expr { $$.value = sqrt($2.value) }
> | ELEMENTARY_FUNCTION expr { $$.value = (*$1.f)($2.value) }
> | NUMBER
> ;
>
> Then you may for example add (and it is easier to do this under C++ than
> under C) to the YYSTYPE a field "branch" that allows you to add nodes say
> by:
>
> expr: expr '+' expr { $$.branch = node("expr", "expr", "+", "expr"); }
> | expr '-' expr { $$.branch = node("expr", "expr", "-", "expr"); }
> ...
>
> Here the function node() would create a node of the parse tree with first
> argument the grammar rule LHS. This way you need to write it out all for
> every rule, so one may try to make some kind of workaround.
>
> The best way would probably be if one defined a macro like
> #define rule_3(x, x1, x2, x3) x: x1 x2 x3 { $$.branch = node(x, x1, x2,
> x3); }
> and used that to pass the grammar part through the C preprocessor before
> passing the output to Bison. Then your rule would look like:
> rule_3(expr, expr, '+', expr);
> rule_3(expr, expr, '-', expr);
> ...
>
> Unfortunately, Bison is not hooked up like that; the C preprocessor is only
> invoked by the (C/C++) compiler processing the Bison output. Therefore one
> might try a dynamic (but somewhat runtime slower) solution: Make sure
> YYSTYPE is given field "name", with the idea that the code should look like
> expr: expr '+' expr { $$.name = "expr";
> $$.branch = node($$.name, $1.name, $2.name, $3.name); }
> | expr '-' expr { $$.name = "expr";
> $$.branch = node($$.name, $1.name, $2.name, $3.name) }
> ...
>
> As you see, all the rule actions now become the same, except for the rule
> length and the LHS name. But the rule length is dynamically available
> during parsing, in bison.simple, it is called yylen. And the end of the
> stack (probably corresponding to $n) is called yyvsp. So you should be able
> to write a function
> node($$.name, yyvsp)
> that constructs the parser tree node. (Be aware, though that when you
> change skeleton file, names like yyvsp and yylen may change.)
>
> If you the define a macro
> #define NODE(x) $$.name = #x; node($$.name, yyvsp)
> your grammar code might look something like:
> expr: expr '+' expr { NODE(expr); }
> | expr '-' expr { NODE(expr); }
> ...
> | '(' expr ')' { NODE(expr); }
> | '-' expr %prec UMINUS { NODE(expr); }
> | IDENTIFIER expr { NODE(expr); }
> | ELEMENTARY_FUNCTION expr { NODE(expr); }
> | NUMBER { NODE(expr); }
> ;
>
> That is, all actions now look the same, which should be fairly easy, even
> if they must be written in by hand.
>
> Hans Aberg
>
> _______________________________________________
> address@hidden http://mail.gnu.org/mailman/listinfo/help-bison%{
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define YYSTYPE double
#define YYDEBUG 1
#define OPERAND 0
#define OPERATOR 1
double power ( double, double );
void yyerror ( char * );
int yylex ( void );
void add_to_parse_tree ( int, double );
void print_parse_tree ( void );
struct node
{
char value[25];
struct node *left;
struct node *right;
};
void do_preorder_traversal ( struct node * );
void do_inorder_traversal ( struct node * );
void do_postorder_traversal ( struct node * );
struct node *term1 = NULL, *term2 = NULL;
struct node **stack;
int stack_pointer = -1;
%}
%token NUMBER
%left '+' '-'
%left '*' '/'
%left UMINUS
%right '^'
%%
lines: lines expr '\n' {
printf ( "Result : %.7f\n\nParse tree
traversals...\n", $2 );
print_parse_tree ( );
stack_pointer = -1;
printf ( "\nExpression : ");
}
| lines '\n' { printf ( "Expression : " ); }
| { printf ( "Expression : " ); }
;
expr: NUMBER { add_to_parse_tree ( OPERAND, $1); }
| expr '+' expr { $$ = $1 + $3; add_to_parse_tree ( OPERATOR, 1
); }
| expr '-' expr { $$ = $1 - $3; add_to_parse_tree ( OPERATOR, 2
); }
| expr '*' expr { $$ = $1 * $3; add_to_parse_tree ( OPERATOR, 3
); }
| expr '/' expr { $$ = $1 / $3; add_to_parse_tree ( OPERATOR, 4
); }
| '-' expr %prec UMINUS { $$ = -$2; add_to_parse_tree ( OPERATOR,
-1 ); }
| expr '^' expr { $$ = power ( $1, $3); add_to_parse_tree (
OPERATOR, 5 ); }
| '(' expr ')' { $$ = $2; }
;
%%
void yyerror ( char *error )
{
char dummy[1000], temp;
printf ( "\n!!!%s.\n", error );
printf ( "Attempting to recover..." );
scanf ( "%s", dummy );
temp = getchar ( );
fflush ( stdin );
fflush ( stdout );
printf ( "done.\n\n" );
yyparse ( );
}
int yylex ( void )
{
int c;
while ( ( c = getchar ( ) ) == ' ' )
;
if ( ( c == '.' ) || ( isdigit ( c ) ) )
{
ungetc(c,stdin);
scanf("%lf",&yylval);
return NUMBER;
}
if ( c == EOF )
{
printf ( "\n\nBye!\n\n" );
return ( 0 );
}
return ( c );
}
int main ( void )
{
stack = malloc ( sizeof ( struct node ) * 100 );
if ( stack == NULL )
{
printf ( "!!! Unable to allocate memory for stack.\n" );
exit ( 1 );
}
printf ( "\nDesktop calculator.\n\( Press Control-D to exit. )\n\n" );
yyparse ( );
return ( 0 );
}
double power ( double x, double y )
{
double i=y;
y = 1;
for ( ; i>0 ; i-- )
y *= x;
return ( y );
}
void add_to_parse_tree ( int type, double value )
{
struct node *tempnode, *newnode;
double operand1, operand2, result;
switch ( type )
{
case OPERAND:
tempnode = malloc ( sizeof ( struct node ) );
if ( tempnode == NULL )
{
printf ( "\n!!! Out of memory.\n" );
exit ( 1 );
}
stack_pointer++;
if ( stack_pointer == 100 )
{
printf ( "\n!!! Stack overflow.\n" );
exit ( 1 );
}
sprintf ( tempnode->value, "%.2f", value );
stack[stack_pointer] = tempnode;
if ( term1 == NULL )
{
term1 = tempnode;
}
else if ( term2 == NULL )
{
term2 = tempnode;
}
else
{
term1 = term2;
term2 = tempnode;
}
break;
case OPERATOR:
if ( value == -1 )
{
if ( stack_pointer < 0 )
{
stack_pointer = -1;
yyerror ( "Invalid expression" );
}
sscanf ( stack[stack_pointer]->value, "%lf",
&operand1 );
operand1 *= -1;
sprintf ( stack[stack_pointer]->value, "%.2f",
operand1 );
break;
}
if ( stack_pointer < 1 )
{
stack_pointer = -1;
yyerror ( "Invalid expression." );
}
tempnode = malloc ( sizeof ( struct node ) );
newnode = malloc ( sizeof ( struct node ) );
if ( tempnode == NULL || newnode == NULL )
{
printf ( "\n!!!Out of memory.\n" );
exit ( 1 );
}
sscanf ( term1->value, "%lf", &operand1 );
sscanf ( term2->value, "%lf", &operand2 );
if ( term1->left == NULL )
tempnode->left = term1;
else
tempnode->left = term1->left;
if ( term2->left == NULL )
tempnode->right = term2;
else
tempnode->right = term2->left;
stack_pointer -= 2;
switch ( (int)value )
{
case 1:
sprintf ( tempnode->value, "+" );
result = operand1 + operand2;
break;
case 2:
sprintf ( tempnode->value, "-" );
result = operand1 - operand2;
break;
case 3:
sprintf ( tempnode->value, "*" );
result = operand1 * operand2;
break;
case 4:
sprintf ( tempnode->value, "/" );
result = operand1 / operand2;
break;
case 5:
sprintf ( tempnode->value, "^" );
result = power ( operand1, operand2 );
break;
}
sprintf ( newnode->value, "%.2f", result );
newnode->left = tempnode;
stack_pointer++;
if ( stack_pointer == 100 )
{
printf ( "\n!!! Stack overflow.\n" );
exit ( 1 );
}
stack[stack_pointer] = newnode;
term2 = newnode;
if ( ( stack_pointer-1) > -2 )
term1 = stack[stack_pointer-1];
break;
}
}
void print_parse_tree ( void )
{
struct node *traversenode;
traversenode = stack[0];
printf ( "\tPreorder : ");
do_preorder_traversal ( traversenode );
printf ( "\n\tInorder : " );
do_inorder_traversal ( traversenode );
printf ( "\n\tPostorder : " );
do_postorder_traversal ( traversenode );
printf ( "\n" );
}
void do_preorder_traversal ( struct node *start )
{
struct node *traversenode = start;
if ( traversenode == NULL )
{
printf ( "Empty expression.\n" );
return;
}
if ( traversenode->left != NULL )
do_preorder_traversal ( traversenode->left );
if ( traversenode->right != NULL )
do_preorder_traversal ( traversenode->right );
if ( traversenode != stack[0] )
printf ( "%s ", traversenode->value );
}
void do_inorder_traversal ( struct node *start )
{
struct node *traversenode = start;
if ( traversenode == NULL )
{
printf ( "Empty expression.\n" );
return;
}
if ( traversenode->left != NULL )
do_inorder_traversal ( traversenode->left );
if ( traversenode != stack[0] )
printf ( "%s ", traversenode->value );
if ( traversenode->right != NULL )
do_inorder_traversal ( traversenode->right );
}
void do_postorder_traversal ( struct node *start )
{
struct node *traversenode = start;
if ( traversenode == NULL )
{
printf ( "Empty expression.\n" );
return;
}
if ( traversenode != stack[0] )
printf ( "%s ", traversenode->value );
if ( traversenode->left != NULL )
do_postorder_traversal ( traversenode->left );
if ( traversenode->right != NULL )
do_postorder_traversal ( traversenode->right );
}
franline.vcf
Description: Card for Steve Fernandez
smime.p7s
Description: S/MIME Cryptographic Signature