# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1573982327 0
# Node ID 991849dfbcb11ea1c93213c718fb6932031b9957
# Parent  8d57433c7b5ee61ce8596f427d938964e13a27a3
updated

diff -r 8d57433c7b5e -r 991849dfbcb1 handouts/ho05.tex
--- a/handouts/ho05.tex	Fri Nov 15 14:58:16 2019 +0000
+++ b/handouts/ho05.tex	Sun Nov 17 09:18:47 2019 +0000
@@ -8,7 +8,10 @@
 % http://www.mollypages.org/page/grammar/index.mp
 
 %% parsing scala files
-%%https://scalameta.org/
+%% https://scalameta.org/
+
+% chomsky normal form transformation
+% https://youtu.be/FNPSlnj3Vt0
 
 \begin{document}
 
diff -r 8d57433c7b5e -r 991849dfbcb1 handouts/ho07.pdf
Binary file handouts/ho07.pdf has changed
diff -r 8d57433c7b5e -r 991849dfbcb1 handouts/ho07.tex
--- a/handouts/ho07.tex	Fri Nov 15 14:58:16 2019 +0000
+++ b/handouts/ho07.tex	Sun Nov 17 09:18:47 2019 +0000
@@ -684,10 +684,10 @@
 
 \subsection*{Arrays}
 
-Maybe a useful addition to the While-language are arrays. This 
-lets us generate more interesting While-programs by translating
-BF*** programs into equivalent While-programs. This means we 
-want to support the following three constructions
+Maybe a useful addition to the While-language would be arrays. This
+would let us generate more interesting While-programs by translating
+BF*** programs into equivalent While-code. So in this section lets have
+a look at how we can support the following three constructions
 
 \begin{lstlisting}[mathescape,language=While]
 new arr[15000]
@@ -696,14 +696,16 @@
 \end{lstlisting}
 
 \noindent
-The first one creates a new array with name \pcode{arr} that can 
-hold a given number of integers. The second is referencing an array
-inside a arithmetic expression. Essentially we have to be able to 
-look up the contents of an array at an index. Similarly we need to be
-able to update the content of an array (3rd line). The latter two
-constructions state that the index to an array can be given by 
-an arithmetic expression. For creating a new array we need to generate
-the following JVM instructions:
+The first construct is for creating new arrays, in this instance the
+name of the array is \pcode{arr} and it can hold 15000 integers. The
+second is for referencing an array cell inside an arithmetic
+expression---we need to be able to look up the contents of an array at
+an index determined by an arithmetic expression. Similarly, we need to
+be able to update the content of an array at an calculated index---the
+3rd feature.  
+
+For creating a new array we can generate the following three JVM
+instructions:
 
 \begin{lstlisting}[mathescape,language=JVMIS]
 ldc number 
@@ -712,10 +714,12 @@
 \end{lstlisting}
 
 \noindent
-First we need to put the dimension of the array onto the
-stack, then next instruction creates the array and last we
-need to store the array in a local variable (like ``simple'' variables).
-For looking up an element in an array we can use the following code
+First we need to put the dimension of the array onto the stack. The next
+instruction creates the array. With the last we can store the array as a
+local variable (like the ``simple'' variables from the previous
+section). The use of a local variable allows us to have multiple arrays
+in a While-program. For looking up an element in an array we can use the
+following JVM code
 
 \begin{lstlisting}[mathescape,language=JVMIS]
 aload loc_var 
@@ -724,10 +728,55 @@
 \end{lstlisting}
 
 \noindent
-This first loads the ``pointer'' to the array onto the stack. Then we have the
-instructions corresponding to the index where we want to look up the array. The
-idea is that these instructions will leave a concrete number on the stack, which is
-the index. Finally we just need to load the corresponding element onto the stack.
+The first instruction loads the ``pointer'' to the array onto the stack.
+Then we have some instructions corresponding to the index where we want
+to look up the array. The idea is that these instructions will leave a
+concrete number on the stack, which will be the index into the array we
+need. Finally we need to tell the JVM to load the corresponding element
+onto the stack. Updating an array at an index with a value is as
+follows.
+
+\begin{lstlisting}[mathescape,language=JVMIS]
+aload loc_var 
+index_aexp 
+value_aexp 
+iastore
+\end{lstlisting}
+
+\noindent
+Again the first instruction loads the ``pointer'' to the array onto the
+stack. Then we have some instructions corresponding to the index where
+we want to update the array. After that come the instructions for with what
+value we want to update the array. Finally the instruction for 
+updating the array.
+
+Next we need to update our grammar rules: it seems best to extend the 
+rule for factors in arithmetic expressions with a rule for looking up
+an array.
+
+\begin{plstx}[rhs style=, margin=3cm]
+: \meta{E} ::= \meta{T} $+$ \meta{E}
+         | \meta{T} $-$ \meta{E}
+         | \meta{T}\\
+: \meta{T} ::= \meta{F} $*$ \meta{T}
+          | \meta{F} $\backslash$ \meta{T}
+          | \meta{F}\\
+: \meta{F} ::= ( \meta{E} )
+          | $\underbrace{\meta{Id}\,[\,\meta{E}\,]}_{new}$
+          | \meta{Id}
+          | \meta{Num}\\
+\end{plstx}
+
+\noindent
+There is no problem with left-recursion as the \meta{E} is ``protected''
+by an identifier and brackets. There are two new rules in statements,
+namely creation of an array and array assignment:
+
+\begin{plstx}[rhs style=, margin=2cm, one per line]
+: \meta{Stmt} ::=  \ldots
+              | \texttt{new}\; \meta{Id}\,[\,\meta{Num}\,] 
+              | \meta{Id}\,[\,\meta{E}\,]\,:=\,\meta{E}\\
+\end{plstx}
 
 \end{document}