Notes:Possible error 2016 compiler design q2b
Contents
Question
File:Cs3250-2016-with-solutions.pdf - question 2 part b - which can be found on the front page
Examiner's answer
The same as mine, but with a transition via [ilmath]y[/ilmath] from my [ilmath]A_5[/ilmath] to [ilmath]G_2[/ilmath], see bottom of page 5 in File:Cs3250-2016-with-solutions.pdf
Alec's answer
| # | Production | DFA | Comment |
|---|---|---|---|
| 0 | [ilmath]S::\eq\ A\#[/ilmath] | [ilmath]\begin{xy}\xymatrix{& & & *++[o][F=]{C_0} \\ \text{start} \ar[r] & *++[o][F=]{A_5} \ar[dr]^B \ar[ddr]_x \ar[r]^A \ar & *++[o][F-]{B} \ar[ur]^{\#} \ar[r]^z \ar[dr]^x & *++[o][F=]{D_1} \\ & & *++[o][F-]{F} \ar[dr]_y & *++[o][F=]{E_3} \\ & & *++[o][F-]{H} \ar[dr]_y & *++[o][F=]{G_2} \\ & & & *++[o][F=]{I_4} }\end{xy} [/ilmath] | Notice that if we just have the input "[ilmath]y[/ilmath]" we are stuck on [ilmath]A_5[/ilmath], this is accepting so we "construct" (reduce [ilmath]\epsilon[/ilmath] - nothing - to [ilmath]B[/ilmath]) [ilmath]B[/ilmath] from an [ilmath]\epsilon[/ilmath] and go back to the start.
We now have a [ilmath]B[/ilmath] on the top of the stack, we shift this and end up at state [ilmath]F[/ilmath], we shift the next top-of-the-stack (the [ilmath]y[/ilmath] from before) ending up at [ilmath]G_2[/ilmath], this is an accepting state, so:
We then shift the [ilmath]A[/ilmath] and shit the [ilmath]\#[/ilmath] (assuming this means "end of input") then reduce both to the start symbol, which is the accept-the-parse of accepting states, we're done. There is some abuse of terminology here, but you see what I mean, and we'd usually use numbers for the states. Regardless we reduce to "logically" get a [ilmath]B[/ilmath] from [ilmath]\epsilon[/ilmath], shift the [ilmath]y[/ilmath] over that, reduce them both to get an [ilmath]A[/ilmath], shift the [ilmath]\#[/ilmath] over that, reduce them both to get an [ilmath]S[/ilmath], we're done. |
| 1 | [ilmath]A::\eq\ Az[/ilmath] | ||
| 2 | [ilmath]A::\eq\ By[/ilmath] | ||
| 3 | [ilmath]B::\eq\ Ax[/ilmath] | ||
| 4 | [ilmath]B::\eq\ xy[/ilmath] | ||
| 5 | [ilmath]B::\eq\ \epsilon[/ilmath] |
