Help on parse trees...

[iopusstarr1]

I was given a question of the follwing:

Consider the Baby Programming Language (BPL). It is a very simple programming language,
whose syntax is given by the following grammar:

S → WHILE B DO S ENDWHILE; | SS | A | P
A → I := E;
I → char(char)٭
E → digit | E + E | I
P → PRINT I;
B → TRUE | FALSE | E == E


Give the parse tree for :
WHILE 4==3 DO PRINT x; x:=4; ENDWHILE;
ex := 4;

I'm really stuck. Somebody help!

[OneOffDriveByPoster]

Well, you have to start with S by convention. It looks like you have a WhileStatement (a production of S) and an AssignmentStatement (can also be produced in one or more steps from S). So it looks like you want two S's. (Naming what you want, e.g. WhileStatement, can help, but is not necessary.)

Let's try the first step:

code:

S  |  v  SS

[ali_dada]

(Starting with S) - LEFTMOST DERIVATION (just convert this into a tree now).

=>SS
=>WHILE B DO S ENDWHILE;
S
=>WHILE E == E DO S ENDWHILE;
S
=>WHILE digit == E DO S ENDWHILE;
S
=>WHILE 4 == E DO S ENDWHILE;
S
=>WHILE 4 == digit DO S ENDWHILE;
S
=>WHILE 4 == 3 DO S ENDWHILE;
S
=>WHILE 4 == 3 DO SS ENDWHILE;
S
=>WHILE 4 == 3 DO PS ENDWHILE;
S
=>WHILE 4 == 3 DO PRINT I;S ENDWHILE;
S
=>WHILE 4 == 3 DO PRINT char(char)* ;S ENDWHILE;
S
=>WHILE 4 == 3 DO PRINT x; A ENDWHILE;
S
=>WHILE 4 == 3 DO PRINT x; I := E; ENDWHILE;
S
=>WHILE 4 == 3 DO PRINT x; char(char)* := E; ENDWHILE;
S
=>WHILE 4 == 3 DO PRINT x; x := E; ENDWHILE;
S
=>WHILE 4 == 3 DO PRINT x; x := digit; ENDWHILE;
S
=>WHILE 4 == 3 DO PRINT x; x := 4; ENDWHILE;
S
=>WHILE 4 == 3 DO PRINT x; x := 4; ENDWHILE;
S
=>WHILE 4 == 3 DO PRINT x; x := 4; ENDWHILE;
A
=>WHILE 4 == 3 DO PRINT x; x := 4; ENDWHILE;
I := E;
=>WHILE 4 == 3 DO PRINT x; x := 4; ENDWHILE;
char(char)* := E;
=>WHILE 4 == 3 DO PRINT x; x := 4; ENDWHILE;
ex := E;
=>WHILE 4 == 3 DO PRINT x; x := 4; ENDWHILE;
ex := digit;
=>WHILE 4 == 3 DO PRINT x; x := 4; ENDWHILE;
ex := 4;


HINT: on the step you get stuck, just start doing it from bottom up (ie. bottom-up parse).