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

• VAR: [a-z]([a-z]|[0-9])*
• NUM: [1-9][0-9]*|0
• OPs: + | -
• OPm: * | /
• ASN: =

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)