Answers to January 2002 CS2121 Exam Q1

(Parts in italics are just my working out loud, that I wouldn't expect to see in real exam answers.)

a)

i)

brackets around highest precedence operations -> a-b-(c/d/e)
bracket left-to-right -> (a-b)-((c/d)/e)

        -
     /     \
   -     divide
 /  \     /   \
a    b divide  e
      /     \
     c       d

ii)

brackets around highest precedence operations -> (a-b-c)/d/e
bracket right-to-left -> (a-(b-c))/(d/e)

   divide
   /    \
  -    divide
 / \    / \
a   -  d   e
   / \
  b   c

b)

lex:

[A-Za-z][A-Za-z0-9]*	{yylval.i=strdup(yytext); return id;}
[0-9]+			{yylval.n=atoi(yytext); return number;}
[()-/]			{return yytext[0];}
[ \t\n]			;
.			{ECHO; yyerror("unexpected\n");}

yacc:

%token <n> number
%token <i> id
%union {int n; char *i;}
%start exp
%%
exp: term | exp '-' term ;
term: factor | term '/' factor ;
factor: id | number | '(' exp ')' ;

or:

%token <n> number
%token <i> id
%union {int n; char *i;}
%start exp
%left '-'
%left '/'
%%
exp: exp '-' exp | exp '/' exp | id | number | '(' exp ')' ;

c)

each precedence level is in a separate rule, and the %start rule (exp) has lowest priority (is recognised last) and left associativity corresponds to left recursion
change to right-recursion, and put lowest priority operator into %start rule (exp):

exp: term | term '/' exp ;
term: factor | factor '-' term ;
factor: id | number | '(' exp ')' ;

or:
%left gives left associativity, and the last such rule has highest priority
use %right, and put lowest priority operator in first such:

%right '/'
%right '-'