Compilers: Principles and Practice by Pearson

92 Compilers – Principles and Practice

Algorithm 4.3.1: Operator precedence parsing

/* Initially the stack contains $, string w$ input*/

1 ip ← pointer to first symbol of w$;

2 while True do

3 if TOS = $ and (ip) = $ then

4 return;

5 else

6 a topmost Terminal and (ip) = b;

7 if a  b or a  b then

8 push(b);

9 ip++;

10 else

11 if a  b then

/* Reduce */

12 repeat

13 pop;

14 until TOS  most recently popped;

15 else

16 ERROR;

17 end

18 end

19 end

20 end

It should be noted here that Algorithm 4.3.1 is very similar to the one used in the first compiler for one

of the earliest High Level languages – FORTRAN.

Unary operators are handled by keeping ...