\documentclass{article}
\usepackage{graphics}
\usepackage{fancyheadings}

\newcommand{\coursenumber}{131}
\newcommand{\coursetitle}{Principles of Programming Languages}

\topmargin  18pt        % 27pt
\headheight 12pt        % 12pt
\headsep    35pt        % 45pt
\textheight 8.0in
\textwidth  6.2in

\oddsidemargin   22pt      % Left margin on odd-numbered pages.
\evensidemargin  22pt      % Left margin on even-numbered pages.
\marginparwidth  72pt       % Width of marginal notes.
\marginparsep    11pt      % Horizontal space between outer margin and 
                           % marginal note

\pagestyle{fancy}
\lhead{CSCI \coursenumber}
\chead{}
\rhead{\semester}
\lfoot{}
\cfoot{\thepage}
\rfoot{}
\setlength{\headrulewidth}{0pt}
\setlength{\footrulewidth}{0pt}

\newcommand{\semester}[0]{
     \ifnum\month>7{Fall}\fi
     \ifnum\month<8{Spring}\fi\  \number\year
}

\newcommand{\points}[1]{(#1 points)}
\newcommand{\phead}[2]{\points {#1} \textbf{#2}}

\def\rightarrowfill{\mathsurround=0pt  \mathord- \mkern-6mu
  \cleaders\hbox{$\mkern-2mu \mathord- \mkern-2mu$}\hfill
  \mkern-6mu \mathord-\!\!\!\!\longrightarrow}
\newcommand{\step}[1]{~~\stackrel{\texttt{\scriptsize #1}}{\rightarrowfill}~~}


\begin{document}

\begin{center}
    \Large Homework 6\\ \vspace{1 ex} Due Friday, 10/15/10
\end{center}

\vspace{2 ex} 

Please turn in your homework solutions online at  
\texttt{http://www.dci.pomona.edu/tools-bin/cs131upload.php}
before the beginning of class on the due date. 

\vspace{2 ex}


\begin{enumerate}
    
    \item \phead{30}{Parsing Tuples}
    
    Given the following BNF:
    \begin{verbatim}
        <exp> ::= ( <tuple> ) | a 
        <tuple> ::= <tuple>, <exp> | <exp>
    \end{verbatim}

    \begin{enumerate}
        \item Draw the parse tree for ((a,a),a,(a)).
        
        \item Write a lexer for terms of this form.  The tokens are
        simply ``a'', ``(``, ``)'', and ``,''.  The tokens generated
        by the lexer should be from the following type:
        \begin{verbatim}
        data Tokens = AToken | LParen | RParen | Comma | Error String | 
                      EOF deriving (Eq,Show)
        \end{verbatim}
        where \texttt{EOF} marks the end of the token list.  The main
        lexer function should be of the form:
        \begin{verbatim}
        getTokens :: [Char] -> [Tokens]
        \end{verbatim}
        
        As an example, you should get the following results when
        testing \texttt{getTokens}:
        \begin{verbatim}
        *Main> getTokens "((a,a),a,(a,a))"
        [LParen,LParen,AToken,Comma,AToken,RParen,Comma,AToken,Comma,
        LParen,AToken,Comma,AToken,RParen,RParen,EOF]
        \end{verbatim}       
        
        \item\label{bettergrammar} An alternative grammar for the
        above language in EBNF is
        \begin{verbatim}
        <exp> ::= ( <tuple> ) | a 
        <tuple> ::= <exp> {, <exp> }*
        \end{verbatim}
        where the * means the items in parentheses repeat 0 or more
        times.

        We can rewrite this as BNF as
        \begin{verbatim}
        <exp> ::= ( <tuple> ) | a 
        <tuple> ::= <exp> <expTail> 
        <expTail> ::= e | , <exp> <expTail>
        \end{verbatim}
        where \texttt{e} stands for the empty string.
        
	Recall from class that we can build a table that will direct a
	parser as follows.  The rows of the table will correspond to
	non-terminals, while the columns will correspond to terminals.
	The entries are productions from our grammar.

	Put production \texttt{X} ::= $\alpha$ in entry
	(\texttt{X},\texttt{b}) if either
	\begin{itemize}
	    \item \texttt{b} $\in$ FIRST($\alpha$), or
    
	    \item $\epsilon \in$ FIRST($\alpha$) and \texttt{b} $\in$ 
	    FOLLOW(\texttt{X}).
	\end{itemize}

	For any non-terminal \texttt{X} and terminal \texttt{b}, the
	production \texttt{X} ::= $\alpha$ will occur in the
	corresponding entry if applying this production can eventually
	lead to a string starting with \texttt{b}.

	For this to give us an unambiguous parse, no table entry
	should contain two productions.  (If so, we would have to
	rewrite the grammar!)  Slots with no entries correspond to
	errors in the parse (e.g., that the string is not in the
	language generated by the grammar).

	We can also write this restriction out as the following two
	laws for predictive parsing:
	\begin{enumerate}
	    \item If \texttt{A ::= $\alpha_{1}$ | \ldots |
	    $\alpha_{n}$} then for all i $\ne$ j, First($\alpha_{i}$)
	    $\cap$ First($\alpha_{j}$) = $\emptyset$.
    
	    \item If \texttt{X} $\rightarrow$* $\epsilon$, then
	    First(\texttt{X}) $\cap$ Follow(\texttt{X}) = $\emptyset$.
	\end{enumerate}
	
        Compute First and Follow for each non-terminal of this grammar
        and show that the grammar follows the first and second rules
        of predictive parsing.
        
	\item The following definition can be used to represent
	abstract syntax trees of the expressions generated by the
	grammar above:
        \begin{verbatim}
        data Exp = A | AST_Tuple [Exp] | AST_Error String deriving (Eq,Show)
        \end{verbatim}
        [The last item is simply there to handle the case of errors.]
        Thus the tuple (a,a,a) would be represented as
        \texttt{AST\_Tuple[A,A,A]}, while the term in part (a) would be
        represented as \texttt{AST\_Tuple [AST\_Tuple 
	[A,A],A,AST\_Tuple[A,A]]}.
        
        Write a predictive recursive descent parser for the grammar in
        part \ref{bettergrammar}.  It should generate abstract syntax
        trees of type \texttt{Exp}.
        
        \emph{Hint}: Watch the types of your parsing functions.  You
        should have
        \begin{verbatim}
        parseExp :: [Tokens] -> (Exp, [Tokens]) 
        parseTuple :: [Tokens] -> ([Exp], [Tokens]) 
        parseExpTail :: ([Exp], [Tokens]) -> ([Exp], [Tokens]) 
        parse :: [Char] -> Exp
        \end{verbatim}
        where \texttt{parse} is the function invoked on the input
        string.  E.g.,
        \begin{verbatim}
        *Main> parse "((a,a),a,(a,a))" 
        AST_Tuple [AST_Tuple [A,A],A,AST_Tuple [A,A]]
        \end{verbatim}
    \end{enumerate}
    
    \item \phead{20}{Table-driven parsing}
    
    Early in the semester we discussed the fact that
    \texttt{if-then-else} expressions in C, C++, Java, and Pascal are
    ambiguous.  Suppose we use the following grammar for a very simple
    language with conditional statements:
    \begin{verbatim}
        <stmt> ::= if (bool) <stmt> <possElse> | assn
    <possElse> ::= else <stmt> | e
    \end{verbatim}
    where \texttt{e} stands for the empty string.
    
    In this grammar, ``\texttt{if}'', ``\texttt{bool}'', ``\texttt{assn}'',
    and ``\texttt{else}'' are tokens, and hence terminals of the
    grammar, while \texttt{<stmt>} and \texttt{<possElse>} represent
    non-terminals.  (In a more realistic language, ``\texttt{bool}''
    would be a non-terminal that would generate Boolean valued
    expressions, while ``\texttt{assn}'' would generate assignment
    statement.  However, it makes the problem easier if we just let
    them be terminals.

    \begin{enumerate}
        \item Show that the string ``\texttt{if (bool) if (bool) assn
        else assn}'' has two distinct parse trees.

        \item Compute the \textbf{first} and \textbf{follow} sets for
        the grammar, and build a parse table like that in Lecture 15
        (see online notes).

        \item Explain how the parse table suggests that the grammar
        will be problematic to parse using predictive parsing like
        that explained in class.

        \item How could we manually manipulate the parse table so
        that, if used as the basis for a recursive descent or
        stack-based top down parser, it always chooses a parse
        according to the C/C++/Java/Pascal rules (i.e., always
        associate an ``\texttt{else}'' with the nearest
        ``\texttt{if}'')?
    \end{enumerate}
 

    \item \phead{10}{Static and Dynamic Scope}
    
    Please do problem 7.8 from Mitchell, page 196.
    
    \item \phead{10}{Eval and Scope}
    
    Please do problem 7.10 from Mitchell, page 197.  You only need to 
    do parts b and c, but please read part a so that the rest makes 
    sense.
    
    \item \phead{18}{Lambda Calculus and Scope}
    
    Please do problem 7.11 from Mitchell, page 198.
    
\end{enumerate}

\end{document}