Computer Science Canada Help on parse trees... |
| Author: | iopusstarr1 [ Tue Mar 11, 2008 9:01 pm ] |
| Post subject: | Help on parse trees... |
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! |
|
| Author: | OneOffDriveByPoster [ Wed Mar 12, 2008 8:04 am ] | ||
| Post subject: | Re: Help on parse trees... | ||
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:
|
|||
| Author: | ali_dada [ Wed Apr 23, 2008 7:54 pm ] |
| Post subject: | Re: Help on parse trees... |
(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). |
|