\documentstyle[11pt,simplemargins]{article}
\setallmargins{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{3}

% DEFINE THE DUE DATE
\def\due{October 7, 1991}

% title command
\newcommand{\mytitle}{{\large\noindent 6.035 Computer Language
Engineering \hfill{} Juliet Bourne \\ 
Homework \#\psnum \hfill{} \due \\}
\vspace{-.43in}
\begin{center} \rule{6.5in}{.25mm} \end{center}}
% newpage setup command 
\newcommand{\mypage}[1]{\newpage{\large\noindent 6.035 Computer Language
Engineering \hfill{} Juliet Bourne \\
Homework \#\psnum \hfill{} \due \\}
\vspace{-.43in}
\begin{center} \rule{6.5in}{.25mm} \end{center}}
%\newcommand{\mynewpage}{\newpage\noindent
%{\large 6.035 \hfill{} Juliet Bourne \\
%Problem Set \psnum \hfill{} {\bf Page \thepg} \\}
%\vspace{-.6in}
%\begin{center}
%\rule{6in}{.25mm}
%\end{center}
%\addtocounter{pg}{1}}
% problem command
\newcommand{\prob}[1]{\noindent{\fbox{\large\bf Problem #1}}\vspace{.25in}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}

\newcommand{\PSbox}[3]{\mbox{\rule{0in}{#3}\special{psfile=#1}\hspace{#2}}}

\begin{document}

\mytitle

\prob{1}

\subprob{a} The CFSM:

\PSbox{/mit/jcbourne/Psets/6035/cfsm.ps hoffset=-48}{8in}{6.25in}

\mypage

\subprob{b} 

\noindent Productions:

\begin{enumerate}
\item S $\rightarrow$ S {\bf ;} $\langle$stmt$\rangle$
\item S $\rightarrow$ $\langle$stmt$\rangle$
\item $\langle$stmt$\rangle$ $\rightarrow$ {\bf if} $\langle$expr$\rangle$ {\bf then} $\langle$stmt$\rangle$
\item $\langle$stmt$\rangle$ $\rightarrow$ $\langle$expr$\rangle$
\item $\langle$expr$\rangle$ $\rightarrow$ {\bf id}
\end{enumerate}

\noindent Goto table:

\vspace*{.1in}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}\hline
State & \verb+id+ & \verb+if+ & \verb+then+ & \verb+;+ & $\langle$expr$\rangle$ & $\langle$stmt$\rangle$
& S & \$ \\ \hline
0 & 7 & 5 & \mbox{} & \mbox{} & 6 & 8 & 1 & \mbox{} \\ \hline
1 & \mbox{} & \mbox{} & \mbox{} & 3 & \mbox{} & \mbox{} & \mbox{} & 2 \\ \hline
2 & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} \\ \hline
3 & 7 & 5 & \mbox{} & \mbox{} & 6 & 4 & \mbox{} & \mbox{} \\ \hline
4 & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} \\ \hline
5 & 7 & \mbox{} & \mbox{} & \mbox{} & 9 & \mbox{} & \mbox{} & \mbox{} \\ \hline
6 & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} \\ \hline
7 & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} \\ \hline
8 & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} \\ \hline
9 & \mbox{} & \mbox{} & 10 & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} \\ \hline
10 & 7 & 5 & \mbox{} & \mbox{} & 6 & 11 & \mbox{} & \mbox{} \\ \hline
11 & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} & \mbox{} \\ \hline
\end{tabular}

\vspace*{.1in}
\noindent Action table:

\vspace*{.1in}
\begin{tabular}{|c|c|}\hline
State & Action \\ \hline 
0 & shift \\ \hline
1 & shift \\ \hline
2 & accept \\ \hline
3 & shift \\ \hline
4 & reduce-1 \\ \hline
5 & shift \\ \hline
6 & reduce-4 \\ \hline
7 & reduce-5 \\ \hline
8 & reduce-2 \\ \hline
9 & shift \\ \hline
10 & shift \\ \hline
11 & reduce-3 \\ \hline
\end{tabular}

\mypage 

\noindent Parse of the sentence: \verb+id ; if id then if id then id+ 

\vspace*{.1in}
\begin{tabular}{|r|r|l|}\hline
States & Input & Action \\ \hline\hline
0 & \verb+id ; if id then if id then id $+ & shift 7 \\ \hline
0 7 & \verb+; if id then if id then id $+ & reduce-5, goto(0,$\langle$expr$\rangle$)=6\\ \hline
0 6 & \verb+; if id then if id then id $+ & reduce-4, goto(0,$\langle$stmt$\rangle$)=8\\ \hline
0 8 & \verb+; if id then if id then id $+ & reduce-2, goto(0,S)=1 \\ \hline
0 1 & \verb+; if id then if id then id $+ & shift 3 \\ \hline
0 1 3 & \verb+if id then if id then id $+ & shift 5 \\ \hline
0 1 3 5 & \verb+id then if id then id $+ & shift 7 \\ \hline
0 1 3 5 7 & \verb+then if id then id $+ & reduce-5, goto(5,$\langle$expr$\rangle$)=9 \\ \hline
0 1 3 5 9 & \verb+then if id then id $+ & shift 10 \\ \hline
0 1 3 5 9 10 & \verb+if id then id $+ & shift 5 \\ \hline
0 1 3 5 9 10 5 & \verb+id then id $+ & shift 7 \\ \hline
0 1 3 5 9 10 5 7 & \verb+then id $+ & reduce-5, goto(5,$\langle$expr$\rangle$)=9  \\ \hline
0 1 3 5 9 10 5 9 & \verb+then id $+ & shift 10  \\ \hline
0 1 3 5 9 10 5 9 10 & \verb+id $+ & shift 7 \\ \hline
0 1 3 5 9 10 5 9 10 7 & \verb+$+ & reduce-5, goto(10,$\langle$expr$\rangle$)=6 \\ \hline
0 1 3 5 9 10 5 9 10 6 & \verb+$+ & reduce-4, goto(10,$\langle$stmt$\rangle$)=11 \\ \hline
0 1 3 5 9 10 5 9 10 11 & \verb+$+ & reduce-3, goto(10,$\langle$stmt$\rangle$)=11 \\ \hline
0 1 3 5 9 10 11 & \verb+$+ & reduce-3, goto(3,$\langle$stmt$\rangle$)=4 \\ \hline
0 1 3 4 & \verb+$+ & reduce-1, goto(0,S)=1 \\ \hline
0 1 & \verb+$+ & shift 2 \\ \hline
0 1 2 & \mbox{} & accept \\ \hline
\end{tabular}

\vspace*{.1in}
\subprob{c} Since this grammar is so simple, removing the semi-colon
from the first production does not result in any shift/reduce or
reduce/reduce conflicts. Thus, it is still an LR(0) grammar. This is
easily seen by modifying the CFSM to eliminate this semi-colon; there
are no conflicts. Here is how the effected states are modified to be
placed in the same CFSM shown in {\bf a}.

\PSbox{/mit/jcbourne/Psets/6035/cfsm-mod.ps voffset=-32}{5.5in}{2in}

\mypage

\prob{2} 

Comparing the relevant portions of the CFSMs for SLR(1) and LALR(1), it
can be seen that in the SLR(1) CFSM there is a shift/reduce conflict
which the LALR(1) does not have.

Part of the SLR(1) CFSM:

\PSbox{/mit/jcbourne/Psets/6035/slr.ps hoffset=-32}{7in}{1.75in}

\noindent There is a shift/reduce conflict in state 3 which arises even
with a lookahead since a is expected by S $\rightarrow$ bd.a and a $\in$
Follow(A)=\{a,c\}. The Action(3,a) rule gives both shift and reduce.

Part of the LALR(1) CFSM:

\PSbox{/mit/jcbourne/Psets/6035/lalr.ps hoffset=-48}{7.5in}{1.5in}

\noindent There is no conflict in state 3 since the LALR(1) preserves
where each state came from. For example, knowing the context in which a
closure of A is calculated allows the lookahead symbol to be determined
precisely (as in state 2).

\mypage

\prob{3}

\beq
<expr> \rightarrow <list> &\Rightarrow& \{ expr.depth = list.depth \} \\
<expr> \rightarrow integer &\Rightarrow& \{ expr.depth = 0 \} \\
<list> \rightarrow [ <contents> ] &\Rightarrow& \{ list.depth =
contents.depth + 1 \} \\
<contents> \rightarrow \lambda  &\Rightarrow& \{ contents.depth = 0 \} \\
<contents> \rightarrow <expr> &\Rightarrow& \{ contents.depth = expr.depth \}\\
<contents> \rightarrow <contents> , <expr> &\Rightarrow& \{
contents_1.depth = Max(contents_2.depth, expr.depth) \} 
\eeq

\noindent Example: calculating depth of \verb+[1,[2,3],4]+

\end{document}

