155 \begin{frame}[t]

   155 \begin{frame}[c]

   156 \frametitle{\begin{tabular}{c}Numbers\end{tabular}}

   156 \frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}}

   157 

   157 

   158 A grammar for numbers:

   158 A grammar for arithmetic expressions and numbers:

   159 

   159 

   160 \begin{center}

   160 \begin{center}

   161 \bl{\begin{tabular}{lcl}

   161 \bl{\begin{tabular}{lcl}

   162 $N$ & $\rightarrow$ &  $N \cdot N \;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\

   162 $E$ & $\rightarrow$ &  $E \cdot + \cdot E \;|\;E \cdot * \cdot E \;|\;( \cdot E \cdot ) \;|\;N$ \\

   163 $N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1 \;|\: \ldots \;|\; 9$ 

   170 A non-left-recursive grammar for numbers

   171 \end{frame}}

   171 

   172 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   172 \begin{center}

   173 

   173 \bl{\begin{tabular}{lcl}

   174 

   174 $N$ & $\rightarrow$ &  $0 \cdot N \;|\;1 \cdot N \;|\ldots\;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\

   175 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   176 \mode<presentation>{

   177 \begin{frame}[t]

   178 \frametitle{\begin{tabular}{c}Numbers\end{tabular}}

   179 

   180 

   181 

   182 \begin{center}

   183 \bl{\begin{tabular}{lcl}

   184 $N$ & $\rightarrow$ &  $N \cdot N \;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\

   185 \end{tabular}}

   186 \end{center}

   187 

   188 A non-left-recursive, non-ambiguous grammar for numbers

   189 

   190 \begin{center}

   191 \bl{\begin{tabular}{lcl}

   192 $N$ & $\rightarrow$ &  $0 \cdot N \;|\;1 \cdot N \;|\;\ldots\;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\

   193 \end{tabular}}

   194 \end{center}

   195 

   196 

   197 \end{frame}}

   198 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   199 

   200 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   201 \mode<presentation>{

   202 \begin{frame}[c]

   203 \frametitle{\begin{tabular}{c}Operator Precedences\end{tabular}}

   204 

   205 

   206 To disambiguate

   207 

   208 \begin{center}

   209 \bl{\begin{tabular}{lcl}

   210 $E$ & $\rightarrow$ &  $E \cdot + \cdot E \;|\;E \cdot * \cdot E \;|\;( \cdot E \cdot ) \;|\;N$ \\

   211 \end{tabular}}

   212 \end{center}

   213 

   214 Decide how many precedence levels, say\medskip\\

   215 \hspace{5mm}highest for \bl{$()$}, medium for \bl{*}, lowest for \bl{+}

   216 

   217 \begin{center}

   218 \bl{\begin{tabular}{lcl}

   219 $E_{low}$ & $\rightarrow$ & $E_{med} \cdot + \cdot E_{low} \;|\; E_{med}$ \\

   220 $E_{med}$ & $\rightarrow$ & $E_{hi} \cdot * \cdot E_{med} \;|\; E_{hi}$\\

   221 $E_{hi}$ & $\rightarrow$ &  $( \cdot E_{low} \cdot ) \;|\;N$ \\

   222 \end{tabular}}

   223 \end{center}\pause

   224 

   225 \small What happens with \bl{$1 + 3  + 4$}?

   226 \end{frame}}

   227 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   228 

   229 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   230 \mode<presentation>{

   231 \begin{frame}[c]

   232 \frametitle{\begin{tabular}{c}Removing Left-Recursion\end{tabular}}

   233 

   234 The rule for numbers is directly left-recursive:

   235 

   236 \begin{center}

   237 \bl{\begin{tabular}{lcl}

   238 $N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1\;\;\;\;(\ldots)$ 

   239 \end{tabular}}

   240 \end{center}

   241 

   242 Translate

   243 

   244 \begin{center}

   245 \begin{tabular}{ccc}

   246 \bl{\begin{tabular}{lcl}

   247 $N$ & $\rightarrow$ & $N \cdot \alpha$\\

   248  &  $\;|\;$ & $\beta$\\

   249  \\ 

   250 \end{tabular}} 

   251 & {\Large$\Rightarrow$} &

   252 \bl{\begin{tabular}{lcl}

   253 $N$ & $\rightarrow$ & $\beta \cdot N'$\\

   254 $N'$ & $\rightarrow$ & $\alpha \cdot N'$\\

   255  &  $\;|\;$ & $\epsilon$ 

   256 \end{tabular}}

   257 \end{tabular}

   258 \end{center}\pause

   259 

   260 Which means

   261 

   262 \begin{center}

   263 \bl{\begin{tabular}{lcl}

   264 $N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1 \cdot N'$\\

   265 $N'$ & $\rightarrow$ & $N \cdot N' \;|\; \epsilon$\\

   199 

   290 No rule can contain \bl{$\epsilon$}.

   200 

   291 

   201 \end{frame}}

   292 \end{frame}}

   202 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   293 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   294 

   295 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   296 \mode<presentation>{

   297 \begin{frame}[c]

   298 \frametitle{\begin{tabular}{c}$\epsilon$-Removal\end{tabular}}

   299 

   300 \begin{enumerate}

   301 \item If \bl{$A\rightarrow \alpha \cdot B \cdot \beta$} and \bl{$B \rightarrow \epsilon$} are in the grammar,

   302 then add \bl{$A\rightarrow \alpha \cdot \beta$} (iterate if necessary).

   303 \item Throw out all \bl{$B \rightarrow \epsilon$}.

   304 \end{enumerate}

   305 

   306 \small

   307 \begin{center}

   308 \begin{tabular}{ccc}

   309 \bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}

   310 $N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'$\\

   311 $N'$ & $\rightarrow$ & $N \cdot N'\;|\;\epsilon$ 

   312 \end{tabular}} &

   313 \bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}

   314 $N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\

   315 $N'$ & $\rightarrow$ & $N \cdot N'\;|\;N\;|\;\epsilon$ 

   316 \end{tabular}}

   317 \end{tabular}

   318 \end{center}

   319 

   320 

   321 \end{frame}}

   322 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   323 

   324 

   325