# 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 '-'
```