49 \end{center} |
51 \end{center} |
50 |
52 |
51 \end{frame} |
53 \end{frame} |
52 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
54 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
53 |
55 |
|
56 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
57 \begin{frame}[c] |
|
58 \frametitle{CW3} |
|
59 |
|
60 Atomic parsers for tokens |
|
61 |
|
62 \begin{center} |
|
63 \bl{$\texttt{T\_Num(123)}::rest \;\Rightarrow\; \{(\texttt{T\_Num(123)}, rest)\}$} |
|
64 \end{center}\bigskip |
|
65 |
|
66 \begin{itemize} |
|
67 \item you consume one or more token from the\\ |
|
68 input (stream) |
|
69 \item \bl{\texttt{T\_NUM(1), T\_OP(+), T\_NUM(2)}} |
|
70 \end{itemize} |
|
71 \end{frame} |
|
72 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
73 |
|
74 |
54 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
75 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
55 \begin{frame}[c] |
76 \begin{frame}[c] |
56 \begin{textblock}{10}(0.5,0.5) |
77 \begin{textblock}{10}(0.5,0.5) |
57 \LARGE |
78 \LARGE |
58 \fontspec{Hoefler Text Black} |
79 \fontspec{Hoefler Text Black} |
194 \end{columns} |
215 \end{columns} |
195 |
216 |
196 \end{frame} |
217 \end{frame} |
197 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
218 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
198 |
219 |
199 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
220 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
200 \begin{frame}[t] |
221 %\begin{frame}[t] |
201 \frametitle{Interpreted Code} |
222 %\frametitle{Interpreted Code} |
202 |
223 % |
203 \begin{center} |
224 %\begin{center} |
204 \begin{tikzpicture} |
225 %\begin{tikzpicture} |
205 \begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small] |
226 %\begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small] |
206 \addplot+[smooth] file {interpreted.data}; |
227 %\addplot+[smooth] file {interpreted.data}; |
207 \end{axis} |
228 %\end{axis} |
208 \end{tikzpicture} |
229 %\end{tikzpicture} |
209 \end{center} |
230 %\end{center} |
210 |
231 % |
211 \end{frame} |
232 %\end{frame} |
212 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
233 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
213 |
234 % |
214 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
235 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
215 \begin{frame}[c] |
236 %\begin{frame}[c] |
216 \frametitle{Java Virtual Machine} |
237 %\frametitle{Java Virtual Machine} |
217 |
238 % |
218 \begin{itemize} |
239 %\begin{itemize} |
219 \item introduced in 1995 |
240 %\item introduced in 1995 |
220 \item is a stack-based VM (like Postscript, CLR of .Net) |
241 %\item is a stack-based VM (like Postscript, CLR of .Net) |
221 \item contains a JIT compiler |
242 %\item contains a JIT compiler |
222 \item many languages take advantage of JVM's infrastructure (JRE) |
243 %\item many languages take advantage of JVM's infrastructure (JRE) |
223 \item is garbage collected $\Rightarrow$ no buffer overflows |
244 %\item is garbage collected $\Rightarrow$ no buffer overflows |
224 \item some languages compiled to the JVM: Scala, Clojure\ldots |
245 %\item some languages compiled to the JVM: Scala, Clojure\ldots |
225 \end{itemize} |
246 %\end{itemize} |
226 |
247 % |
227 \end{frame} |
248 %\end{frame} |
228 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
249 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
229 |
250 |
230 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
251 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
231 \begin{frame}[t,fragile] |
252 \begin{frame}[t,fragile] |
232 \frametitle{Compiling AExps} |
253 \frametitle{Compiling AExps} |
233 |
254 |
234 For example \liningnums{\bl{$1 + ((2 * 3) + (4 - 3))$}}:\medskip |
255 For example \textbf{\bl{1 + ((2 * 3) + (4 - 3))}}:\medskip |
235 |
256 |
236 \begin{columns}[T] |
257 \begin{columns}[T] |
237 \begin{column}{.3\textwidth} |
258 \begin{column}{.3\textwidth} |
238 \begin{center} |
259 \begin{center} |
239 \bl{\begin{tikzpicture} |
260 \bl{\begin{tikzpicture} |
789 \end{lstlisting} |
810 \end{lstlisting} |
790 |
811 |
791 \end{frame} |
812 \end{frame} |
792 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
813 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
793 |
814 |
794 |
815 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
795 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
816 \begin{frame}[c] |
796 \mode<presentation>{ |
817 \frametitle{Next Compiler Phases} |
797 \begin{frame}[c] |
|
798 \frametitle{\begin{tabular}{c}Next Compiler Phases\end{tabular}} |
|
799 |
818 |
800 \begin{itemize} |
819 \begin{itemize} |
801 \item assembly $\Rightarrow$ byte code (class file) |
820 \item assembly $\Rightarrow$ byte code (class file) |
802 \item labels $\Rightarrow$ absolute or relative jumps\bigskip\bigskip |
821 \item labels $\Rightarrow$ absolute or relative jumps\bigskip\bigskip |
803 \item \texttt{javap} is a disassembler for class files |
822 \item \texttt{javap} is a disassembler for class files |
|
823 \item jasmin and krakatau are assemblers for jvm code |
804 \end{itemize} |
824 \end{itemize} |
805 |
825 |
806 \end{frame}} |
826 \end{frame} |
807 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
827 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
808 |
828 |
809 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
829 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
810 \mode<presentation>{ |
830 \begin{frame}[t] |
811 \begin{frame}[t] |
831 \frametitle{Recall: Interpreted Code} |
812 \frametitle{\begin{tabular}{c}Compiled Code\end{tabular}} |
832 |
|
833 \begin{center} |
|
834 \begin{tikzpicture} |
|
835 \begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small] |
|
836 \addplot+[smooth] file {interpreted.data}; |
|
837 \end{axis} |
|
838 \end{tikzpicture} |
|
839 \end{center} |
|
840 |
|
841 Loop program |
|
842 \end{frame} |
|
843 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
844 |
|
845 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
846 \begin{frame}[t] |
|
847 \frametitle{Compiled Code} |
813 |
848 |
814 \begin{center} |
849 \begin{center} |
815 \begin{tikzpicture} |
850 \begin{tikzpicture} |
816 \begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small] |
851 \begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small] |
817 \addplot+[smooth] file {compiled.data}; |
852 \addplot+[smooth] file {compiled.data}; |
818 \end{axis} |
853 \end{axis} |
819 \end{tikzpicture} |
854 \end{tikzpicture} |
820 \end{center} |
855 \end{center} |
821 |
856 |
822 \end{frame}} |
857 \end{frame} |
823 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
858 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
824 |
859 |
825 |
860 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
826 |
861 \begin{frame}[t] |
827 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
862 \frametitle{Compiler vs.~Interpreter} |
828 \mode<presentation>{ |
|
829 \begin{frame}[t] |
|
830 \frametitle{\begin{tabular}{c}Compiler vs.~Interpreter\end{tabular}} |
|
831 |
863 |
832 \begin{center} |
864 \begin{center} |
833 \begin{tikzpicture} |
865 \begin{tikzpicture} |
834 \begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs, |
866 \begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs, |
835 xlabel=n, |
867 xlabel=n, |
840 %\legend{interpreted, compiled} |
872 %\legend{interpreted, compiled} |
841 \end{axis} |
873 \end{axis} |
842 \end{tikzpicture} |
874 \end{tikzpicture} |
843 \end{center} |
875 \end{center} |
844 |
876 |
845 \end{frame}} |
877 \end{frame} |
846 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
878 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
879 |
|
880 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
881 \begin{frame}[c] |
|
882 \frametitle{A ``Compiler'' for BF*** to C} |
|
883 |
|
884 \begin{center} |
|
885 \begin{tabular}{lcl} |
|
886 \bl{\texttt{>}} & $\Rightarrow$ & \texttt{ptr++}\\ |
|
887 \bl{\texttt{<}} & $\Rightarrow$ & \texttt{ptr--}\\ |
|
888 \bl{\texttt{+}} & $\Rightarrow$ & \texttt{(*ptr)++}\\ |
|
889 \bl{\texttt{-}} & $\Rightarrow$ & \texttt{(*ptr)--}\\ |
|
890 \bl{\texttt{.}} & $\Rightarrow$ & \texttt{putchar(*ptr)}\\ |
|
891 \bl{\texttt{,}} & $\Rightarrow$ & \texttt{*ptr = getchar()}\\ |
|
892 \bl{\texttt{[}} & $\Rightarrow$ & \texttt{while(*ptr)\{}\\ |
|
893 \bl{\texttt{]}} & $\Rightarrow$ & \texttt{\}}\medskip\\ |
|
894 & $\Rightarrow$ & ignore everything else\\ |
|
895 \end{tabular} |
|
896 \end{center}\bigskip |
|
897 |
|
898 \texttt{char field[30000]\\ char *ptr = \&field[15000]} |
|
899 |
|
900 \end{frame} |
|
901 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
902 |
|
903 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
904 \begin{frame}[c,fragile] |
|
905 \frametitle{BF***} |
|
906 |
|
907 we need some big array, say \texttt{arr} and 7 (8) instructions:\medskip |
|
908 |
|
909 \begin{itemize} |
|
910 \item \texttt{>} move \texttt{ptr++} |
|
911 \item \texttt{<} move \texttt{ptr-{}-} |
|
912 \item \texttt{+} add \texttt{arr[ptr]++} |
|
913 \item \texttt{-} subtract \texttt{arr[ptr]-{}-} |
|
914 \item \texttt{.} print out \texttt{arr[ptr]} as ASCII |
|
915 \item \texttt{[} if \texttt{arr[ptr] == 0} jump just after the corresponding \texttt{]}; otherwise \texttt{ptr++} |
|
916 \item \texttt{]} if \texttt{arr[ptr] != 0} jump just after the corresponding \texttt{[}; otherwise \texttt{ptr++} |
|
917 |
|
918 \end{itemize} |
|
919 |
|
920 \end{frame} |
|
921 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
922 |
|
923 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
924 \begin{frame}[c,fragile] |
|
925 \frametitle{Arrays in While} |
|
926 |
|
927 \begin{itemize} |
|
928 \item \texttt{new arr[15000]}\medskip |
|
929 \item \texttt{x := 3 + arr[3 + y]}\medskip |
|
930 \item \texttt{arr[42 * n] := ...} |
|
931 \end{itemize} |
|
932 |
|
933 \end{frame} |
|
934 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
935 |
|
936 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
937 \begin{frame}[c,fragile] |
|
938 \frametitle{New Arrays} |
|
939 |
|
940 \begin{lstlisting}[mathescape,numbers=none,language=While] |
|
941 new arr[number] |
|
942 \end{lstlisting}\bigskip\bigskip |
|
943 |
|
944 \begin{lstlisting}[mathescape,numbers=none,language=JVMIS] |
|
945 ldc number |
|
946 newarray int |
|
947 astore loc_var |
|
948 \end{lstlisting} |
|
949 |
|
950 |
|
951 \end{frame} |
|
952 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
953 |
|
954 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
955 \begin{frame}[c,fragile] |
|
956 \frametitle{Array Update} |
|
957 |
|
958 \begin{lstlisting}[mathescape,numbers=none,language=While] |
|
959 arr[...] := |
|
960 \end{lstlisting}\bigskip\bigskip |
|
961 |
|
962 \begin{lstlisting}[mathescape,numbers=none,language=JVMIS] |
|
963 aload loc_var |
|
964 index_aexp |
|
965 value_aexp |
|
966 iastore |
|
967 \end{lstlisting} |
|
968 |
|
969 |
|
970 \end{frame} |
|
971 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
972 |
|
973 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
974 \begin{frame}[c,fragile] |
|
975 \frametitle{Array Lookup in AExp} |
|
976 |
|
977 \begin{lstlisting}[mathescape,numbers=none,language=While] |
|
978 ...arr[...]... |
|
979 \end{lstlisting}\bigskip\bigskip |
|
980 |
|
981 \begin{lstlisting}[mathescape,numbers=none,language=JVMIS] |
|
982 aload loc_var |
|
983 index_aexp |
|
984 iaload |
|
985 \end{lstlisting} |
|
986 |
|
987 |
|
988 \end{frame} |
|
989 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
990 |
847 |
991 |
848 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
992 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
849 \mode<presentation>{ |
993 \mode<presentation>{ |
850 \begin{frame}[c] |
994 \begin{frame}[c] |
851 \frametitle{Backend} |
995 \frametitle{Backend} |