Urgent Help!: Parse Trees

[WeedzGeek]

Please, could anybody help me with my assignment? I know I know I should be doing it by myself but for now anyways, so please I need this to be done also by tomorrow evening, so the challenge is there. Thats the grammar of a simple baby programming language:

S → AS|CS|ε

A → I:=E;

C → WHILE B DO S ENDWHILE;

I → char(char)∗

E → I|digit|E+E|E−E

B → (E==E)



Here char = a-z, and digit = 0-9.

And I need to give parse tree for the following
WHILE (x == z+1) DO y:=5; x := x+1; ENDWHILE;


Thank you guys ! [/b]

[Sur_real]

Alright, I can give you some tips but you're gonna have to do it yourself obviously

Ok first of all, I'm gonna assume a left canonical parse tree

How parse tree works is really simple, it's like a tree
So, first you have some production rules
(in your case, one such rule is: S → AS|CS|ε)
So the left hand side is what you have in the beginning and the right hand side is what it can become (so in your ex, S can become either AS or CS or empty/epsilon).
Then you take what you get from the right side and use that as the new left side, checking for any matches in the left hand side.
If you understand tree traversal, the alogrithm is basically like a DFS (that's starting from the left always in this case)

See a somewhat crude example here: https://www.student.cs.uwaterloo.ca/~cs241/cfg/cfg.html

[WeedzGeek]

First of all, take you for your effort!

I understood the whole process/meaning of parse trees, however my language(as given above) is non=deterministic, and in orther for this:WHILE (x == z+1) DO y:=5; x := x+1; ENDWHILE; - to work you first need to rearrange the grammar into a dterministic grammar, so then it can follow its procedures.

For instance: S ---> AS (= is completely wrong and has to be re=written, because A is non-deterministic, and you can not have them like this in this order)

What I have got so far is:

S ---> char A | char S | char C | ε

A ---> := E; (by the way, what is that meaing ':=' ??)

C ---> I dunno know any further... unfortunately, cause I never had to work with while statement in there too. Could you just help me a little bit more please: would be awesome!

[WeedzGeek]

HELLOOOOOOO ???????

[Sur_real]

Hmm I think the ':=', 'while', 'do' and 'endwhile' are all non-terminals (like there's no way to simplify them down any farther) so they're just there and when you see them, you can skip to the next symbol.