1 CFSM Drawing

The following grammar represents the language of all “even” records, where there are an equal number of wins and losses:

S → even
even → even WIN even LOSS
even → LOSS even WIN even
even → \(\epsilon\);

I want you to draw out the CFSM for this grammar. Remember that this process really has 3 steps:

1. Write out all the LR items (the things with bullets)
2. Generate the Nondeterministic CFSM using the two kinds of transitions
3. Generate the actual (deterministic) CFSM by combining states

But I’ll only require you to show the result at the last step, that is, the final CFSM. As a hint, this CFSM has exactly 9 states.

2 CFSM Conflicts

Answer the following regarding the CFSM that you came up with from the previous question:

1. Give an example of a conflict in the CFSM. Identify the state and say whether it is a shift-reduce or reduce-reduce conflict.

2. Is this grammar SLR(1)? Why or why not?

3. (OPTIONAL enrichment) Give an SLR(1) grammar for this language, or prove that none exists.

3 Draw an AST

Here is a program written in Python. Draw its AST.

x = 10
while x > 0:
    print(x)
    x = x - 3
print("done")

4 Undraw an AST

Write a program in the language of your choosing that would generate the following AST:

(Be sure to specify which language you have chosen!)