Name: ____________________________________________________ Alpha: _____________________

## 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)