Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Problem 1

Given the grammar below, draw a parse tree for the string cacbcac.
S → SaS | SbS | c
 

Problem 2

Prove that the following grammar is ambiguous!
S → SS | S
S → a|b|c
 

Problem 3

Consider the following regular expressions Given a string, we can try to break it up into tokens, i.e. pieces that match the regular expressions above. The token for a piece of the string is simply the name for the regular expression mathing it - VAR, NUM, etc in this case. We sometimes need to disambiguate by the convention that the longest possible match is the one we use. For example, tokenizing val10+3 gives VAR OPs NUM:
val10  +   3
-----  -   -
 VAR  OPs NUM
	    
rather than VAR NUM OPs NUM:
val  10   +   3
---- --   -   -
 VAR NUM OPs NUM
	    
because val10 is a longer match than val.

Tokenize the string e2=10-m3*2.

 

Problem 4

Using the grammar below, draw a parse tree for your answer to (2).
S → VAR ASN E
E → E
OPs T  | T
T → T
OPm N | N
N → NUM | VAR | (E)