-----------------------------------

WeedzGeek

Wed Feb 20, 2013 5:22 pm


Urgent Help!: Parse Trees

-----------------------------------

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

Wed Feb 20, 2013 7:26 pm


RE:Urgent Help!: Parse Trees

-----------------------------------

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

Thu Feb 21, 2013 5:12 am


RE:Urgent Help!: Parse Trees

-----------------------------------

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

Thu Feb 21, 2013 7:24 pm


Re: Urgent Help!: Parse Trees

-----------------------------------

HELLOOOOOOO ???????


-----------------------------------

Sur_real

Thu Feb 21, 2013 7:25 pm


RE:Urgent Help!: Parse Trees

-----------------------------------

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.