582
|
1 |
|
664
|
2 |
% !TEX program = xelatex
|
743
|
3 |
\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
|
270
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
4 |
\usepackage{../slides}
|
871
|
5 |
\usepackage{../graphicss}
|
215
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
6 |
\usepackage{../langs}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
7 |
\usepackage{../data}
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
8 |
\usepackage{../grammar}
|
44
|
9 |
|
270
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
10 |
\hfuzz=220pt
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
11 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
\pgfplotsset{compat=1.11}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
14 |
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
|
44
|
15 |
|
|
16 |
% beamer stuff
|
445
|
17 |
\renewcommand{\slidecaption}{CFL 05, King's College London}
|
270
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
18 |
|
796
|
19 |
\usepackage{tcolorbox}
|
|
20 |
\newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black}
|
|
21 |
\newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1}
|
|
22 |
\newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1}
|
|
23 |
|
|
24 |
|
44
|
25 |
|
|
26 |
\begin{document}
|
|
27 |
|
|
28 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
270
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
29 |
\begin{frame}[t]
|
44
|
30 |
\frametitle{%
|
|
31 |
\begin{tabular}{@ {}c@ {}}
|
|
32 |
\\[-3mm]
|
893
|
33 |
\LARGE Compilers and \\[-1mm]
|
|
34 |
\LARGE Formal Languages\\[-5mm]
|
44
|
35 |
\end{tabular}}
|
|
36 |
|
|
37 |
\normalsize
|
|
38 |
\begin{center}
|
|
39 |
\begin{tabular}{ll}
|
893
|
40 |
Email: & christian.urban at kcl.ac.uk\\
|
|
41 |
Office Hour: & Fridays 11 -- 12\\
|
|
42 |
Location: & N7.07 (North Wing, Bush House)\\
|
|
43 |
Slides \& Progs: & KEATS\\
|
|
44 |
Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\
|
44
|
45 |
\end{tabular}
|
893
|
46 |
\end{center}
|
743
|
47 |
|
|
48 |
\begin{center}
|
|
49 |
\begin{tikzpicture}
|
|
50 |
\node[drop shadow,fill=white,inner sep=0pt]
|
|
51 |
{\footnotesize\rowcolors{1}{capri!10}{white}
|
|
52 |
\begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline
|
|
53 |
1 Introduction, Languages & 6 While-Language \\
|
|
54 |
2 Regular Expressions, Derivatives & 7 Compilation, JVM \\
|
|
55 |
3 Automata, Regular Languages & 8 Compiling Functional Languages \\
|
|
56 |
4 Lexing, Tokenising & 9 Optimisations \\
|
|
57 |
\cellcolor{blue!50}
|
|
58 |
5 Grammars, Parsing & 10 LLVM \\ \hline
|
|
59 |
\end{tabular}%
|
|
60 |
};
|
|
61 |
\end{tikzpicture}
|
44
|
62 |
\end{center}
|
270
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
63 |
\end{frame}
|
289
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
64 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
44
|
65 |
|
667
|
66 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
743
|
67 |
%\begin{frame}[c]
|
|
68 |
% \frametitle{Coursework 1: Submissions}
|
|
69 |
%
|
|
70 |
% \begin{itemize}
|
|
71 |
% \item Scala (29)
|
|
72 |
% \item Haskell (1)
|
|
73 |
% \item Kotlin (1)
|
|
74 |
% \item Rust (1)
|
|
75 |
% \end{itemize}\bigskip\bigskip
|
|
76 |
%
|
|
77 |
% \small
|
|
78 |
% Please get in contact if you intend to do CW Strand 2. No zips please.
|
|
79 |
% Give definitions also on paper if asked. BTW, simp
|
|
80 |
% can stay unchanged. Use \texttt{ders} for CW2, not \texttt{ders2}!
|
|
81 |
% \end{frame}
|
289
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
82 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
743
|
83 |
|
528
|
84 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
85 |
\begin{frame}[t]
|
795
|
86 |
\frametitle{Parser}
|
528
|
87 |
\mbox{}\\[-16mm]\mbox{}
|
|
88 |
|
|
89 |
\begin{center}
|
|
90 |
\begin{tikzpicture}[scale=1,
|
|
91 |
node/.style={
|
|
92 |
rectangle,rounded corners=3mm,
|
|
93 |
very thick,draw=black!50,
|
|
94 |
minimum height=18mm, minimum width=20mm,
|
743
|
95 |
top color=white,bottom color=black!20,drop shadow}]
|
528
|
96 |
\node (0) at (-2.3,0) {};
|
|
97 |
|
|
98 |
\node (A) at (0,0) [node] {};
|
|
99 |
\node [below right] at (A.north west) {lexer};
|
|
100 |
|
|
101 |
\node (B) at (3,0) [node] {};
|
|
102 |
\node [below right=1mm] at (B.north west)
|
|
103 |
{\mbox{}\hspace{-1mm}parser};
|
|
104 |
|
|
105 |
\node (C) at (6,0) [node] {};
|
|
106 |
\node [below right] at (C.north west)
|
|
107 |
{\mbox{}\hspace{-1mm}code gen};
|
|
108 |
|
|
109 |
\node (1) at (8.4,0) {};
|
|
110 |
|
|
111 |
\draw [->,line width=4mm] (0) -- (A);
|
|
112 |
\draw [->,line width=4mm] (A) -- (B);
|
|
113 |
\draw [->,line width=4mm] (B) -- (C);
|
|
114 |
\draw [->,line width=4mm] (C) -- (1);
|
|
115 |
\end{tikzpicture}
|
|
116 |
\end{center}
|
|
117 |
|
795
|
118 |
|
|
119 |
\only<2>{
|
|
120 |
\begin{textblock}{1}(3,6)
|
|
121 |
\begin{bubble}[8.5cm]
|
|
122 |
\normalsize
|
|
123 |
parser input: a sequence of tokens\smallskip\\
|
|
124 |
|
|
125 |
{\small\hspace{5mm}\code{key(read) lpar id(n) rpar semi}}\smallskip\\
|
|
126 |
|
|
127 |
parser output: an abstract syntax tree\smallskip\\
|
|
128 |
\footnotesize
|
|
129 |
\hspace{2cm}\begin{tikzpicture}
|
|
130 |
\node {\code{read}}
|
|
131 |
child {node {\code{lpar}}}
|
|
132 |
child {node {\code{n}}}
|
|
133 |
child {node {\code{rpar}}};
|
|
134 |
\end{tikzpicture}
|
|
135 |
\end{bubble}
|
|
136 |
\end{textblock}}
|
528
|
137 |
\end{frame}
|
|
138 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
139 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
140 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
141 |
\begin{frame}[c]
|
550
|
142 |
\frametitle{What Parsing is Not}
|
|
143 |
|
|
144 |
Usually parsing does not check semantic correctness, e.g.
|
|
145 |
|
|
146 |
\begin{itemize}
|
|
147 |
\item whether a function is not used before it
|
|
148 |
is defined
|
|
149 |
\item whether a function has the correct number of arguments
|
|
150 |
or are of correct type
|
|
151 |
\item whether a variable can be declared twice in a scope
|
|
152 |
\end{itemize}
|
|
153 |
|
|
154 |
\end{frame}
|
|
155 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
156 |
|
|
157 |
|
|
158 |
|
|
159 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
160 |
\begin{frame}[c]
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
161 |
\frametitle{Regular Languages}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
162 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
163 |
While regular expressions are very useful for lexing, there is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
164 |
no regular expression that can recognise the language
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
165 |
\bl{$a^nb^n$}.\bigskip
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
166 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
167 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
168 |
\bl{$(((()()))())$} \;\;vs.\;\; \bl{$(((()()))()))$}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
169 |
\end{center}\bigskip\bigskip
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
170 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
171 |
\small
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
172 |
\noindent So we cannot find out with regular expressions
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
173 |
whether parentheses are matched or unmatched. Also regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
174 |
expressions are not recursive, e.g.~\bl{$(1 + 2) + 3$}.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
175 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
176 |
\end{frame}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
177 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
178 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
179 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
180 |
\begin{frame}[c]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
181 |
\frametitle{Hierarchy of Languages}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
182 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
183 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
184 |
\begin{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
185 |
[rect/.style={draw=black!50,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
186 |
top color=white,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
187 |
bottom color=black!20,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
188 |
rectangle,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
189 |
very thick,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
190 |
rounded corners}, scale=1.2]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
191 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
192 |
\draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
193 |
\draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
194 |
\draw (0,-0.85) node [rect, text depth=17mm] {context sensitive languages};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
195 |
\draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
196 |
\draw (0,-1.4) node [rect] {regular languages};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
197 |
\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
198 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
199 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
200 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
201 |
\end{frame}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
202 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
203 |
|
795
|
204 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
205 |
\begin{frame}[c]
|
|
206 |
\LARGE
|
|
207 |
\begin{center}
|
|
208 |
Time flies like an arrow.\\
|
|
209 |
Fruit flies like bananas.
|
|
210 |
\end{center}
|
|
211 |
\end{frame}
|
|
212 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
213 |
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
214 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
215 |
\begin{frame}[c]
|
792
|
216 |
\frametitle{CFGs}
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
217 |
|
360
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
218 |
A \alert{\bf context-free grammar} \bl{$G$} consists of
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
219 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
220 |
\begin{itemize}
|
664
|
221 |
\item a finite set of nonterminal symbols (e.g.~$\meta{A}$ upper case)
|
|
222 |
\item a finite set terminal symbols or tokens (lower case)
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
223 |
\item a start symbol (which must be a nonterminal)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
224 |
\item a set of rules
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
225 |
\begin{center}
|
451
|
226 |
\bl{$\meta{A} ::= \textit{rhs}$}
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
227 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
228 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
229 |
where \bl{\textit{rhs}} are sequences involving terminals and nonterminals,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
230 |
including the empty sequence \bl{$\epsilon$}.\medskip\pause
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
231 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
232 |
We also allow rules
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
233 |
\begin{center}
|
451
|
234 |
\bl{$\meta{A} ::= \textit{rhs}_1 | \textit{rhs}_2 | \ldots$}
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
235 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
236 |
\end{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
237 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
238 |
\end{frame}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
239 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
240 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
241 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
582
|
242 |
\begin{frame}[t]
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
243 |
\frametitle{Palindromes}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
244 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
245 |
A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
246 |
|
795
|
247 |
\only<1>{%
|
|
248 |
\bl{\begin{plstx}[margin=1cm]
|
451
|
249 |
: \meta{S} ::= a\cdot\meta{S}\cdot a\\
|
|
250 |
: \meta{S} ::= b\cdot\meta{S}\cdot b\\
|
588
|
251 |
: \meta{S} ::= a\\
|
|
252 |
: \meta{S} ::= b\\
|
|
253 |
: \meta{S} ::= \epsilon\\
|
795
|
254 |
\end{plstx}}}
|
|
255 |
%
|
|
256 |
\only<2>{%
|
|
257 |
\bl{\begin{plstx}[margin=1cm]
|
|
258 |
: \meta{S} ::= a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b | a | b | \epsilon\\
|
|
259 |
\end{plstx}}}
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
260 |
|
795
|
261 |
%\small
|
|
262 |
%Can you find the grammar rules for matched parentheses?
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
263 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
264 |
\end{frame}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
265 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
266 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
267 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
268 |
\begin{frame}[c]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
269 |
\frametitle{Arithmetic Expressions}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
270 |
|
451
|
271 |
\bl{\begin{plstx}[margin=3cm,one per line]
|
795
|
272 |
: \meta{E} ::= 0 \mid 1 \mid 2 \mid ... \mid 9
|
451
|
273 |
| \meta{E} \cdot + \cdot \meta{E}
|
|
274 |
| \meta{E} \cdot - \cdot \meta{E}
|
|
275 |
| \meta{E} \cdot * \cdot \meta{E}
|
|
276 |
| ( \cdot \meta{E} \cdot ) \\
|
|
277 |
\end{plstx}}\pause
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
278 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
279 |
\bl{\texttt{1 + 2 * 3 + 4}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
280 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
281 |
\end{frame}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
282 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
283 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
284 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
285 |
\begin{frame}[c]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
286 |
\frametitle{A CFG Derivation}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
287 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
288 |
\begin{enumerate}
|
451
|
289 |
\item Begin with a string containing only the start symbol, say \bl{\meta{S}}\bigskip
|
|
290 |
\item Replace any nonterminal \bl{\meta{X}} in the string by the
|
|
291 |
right-hand side of some production \bl{$\meta{X} ::= \textit{rhs}$}\bigskip
|
582
|
292 |
\item Repeat 2 until there are no nonterminals left
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
293 |
\end{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
294 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
295 |
\begin{center}
|
451
|
296 |
\bl{$\meta{S} \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots $}
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
297 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
298 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
299 |
\end{frame}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
300 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
301 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
302 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
451
|
303 |
\begin{frame}[t]
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
304 |
\frametitle{Example Derivation}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
305 |
|
451
|
306 |
\bl{\begin{plstx}[margin=2cm]
|
|
307 |
: \meta{S} ::= \epsilon | a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b \\
|
|
308 |
\end{plstx}}\bigskip
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
309 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
310 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
311 |
\begin{tabular}{lcl}
|
451
|
312 |
\bl{\meta{S}} & \bl{$\rightarrow$} & \bl{$a\meta{S}a$}\\
|
|
313 |
& \bl{$\rightarrow$} & \bl{$ab\meta{S}ba$}\\
|
|
314 |
& \bl{$\rightarrow$} & \bl{$aba\meta{S}aba$}\\
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
315 |
& \bl{$\rightarrow$} & \bl{$abaaba$}\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
316 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
317 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
318 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
319 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
320 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
321 |
\end{frame}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
322 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
323 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
324 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
451
|
325 |
\begin{frame}[t]
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
326 |
\frametitle{Example Derivation}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
327 |
|
451
|
328 |
\bl{\begin{plstx}[margin=3cm,one per line]
|
795
|
329 |
: \meta{E} ::= 0 \mid 1 \mid 2 \mid ... \mid 9
|
451
|
330 |
| \meta{E} \cdot + \cdot \meta{E}
|
|
331 |
| \meta{E} \cdot - \cdot \meta{E}
|
|
332 |
| \meta{E} \cdot * \cdot \meta{E}
|
|
333 |
| ( \cdot \meta{E} \cdot ) \\
|
|
334 |
\end{plstx}}
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
335 |
|
451
|
336 |
\small
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
337 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
338 |
\begin{tabular}{@{}c@{}c@{}}
|
451
|
339 |
\begin{tabular}{@{\hspace{-2mm}}l@{\hspace{1mm}}l@{\hspace{1mm}}l@{\hspace{4mm}}}
|
|
340 |
\bl{\meta{E}} & \bl{$\rightarrow$} & \bl{$\meta{E}*\meta{E}$}\\
|
|
341 |
& \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}$}\\
|
|
342 |
& \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}+\meta{E}$}\\
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
343 |
& \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
344 |
\end{tabular} &\pause
|
451
|
345 |
\begin{tabular}{@{}l@{\hspace{0mm}}l@{\hspace{1mm}}l}
|
|
346 |
\bl{$\meta{E}$} & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}$}\\
|
|
347 |
& \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}+\meta{E}$}\\
|
|
348 |
& \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}+\meta{E}$}\\
|
|
349 |
& \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
350 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
351 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
352 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
353 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
354 |
\end{frame}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
355 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
356 |
|
796
|
357 |
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
358 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
359 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
360 |
\begin{frame}[c]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
361 |
\frametitle{Language of a CFG}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
362 |
|
451
|
363 |
Let \bl{$G$} be a context-free grammar with start symbol \bl{\meta{S}}.
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
364 |
Then the language \bl{$L(G)$} is:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
365 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
366 |
\begin{center}
|
451
|
367 |
\bl{$\{c_1\ldots c_n \;|\; \forall i.\; c_i \in T \wedge \meta{S} \rightarrow^* c_1\ldots c_n \}$}
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
368 |
\end{center}\pause
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
369 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
370 |
\begin{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
371 |
\item Terminals, because there are no rules for replacing them.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
372 |
\item Once generated, terminals are ``permanent''.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
373 |
\item Terminals ought to be tokens of the language\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
374 |
(but can also be strings).
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
375 |
\end{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
376 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
377 |
\end{frame}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
378 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
379 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
380 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
451
|
381 |
\begin{frame}[t]
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
382 |
\frametitle{Parse Trees}
|
582
|
383 |
\mbox{}\\[-12mm]
|
451
|
384 |
|
593
|
385 |
\bl{\begin{plstx}: \meta{E} ::= \meta{T} | \meta{T} \cdot + \cdot \meta{E} | \meta{T} \cdot - \cdot \meta{E}\\
|
529
|
386 |
: \meta{T} ::= \meta{F} | \meta{F} \cdot * \cdot \meta{T}\\
|
795
|
387 |
: \meta{F} ::= 0 ... 9 | ( \cdot \meta{E} \cdot )\\
|
451
|
388 |
\end{plstx}}
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
389 |
|
795
|
390 |
\begin{textblock}{5}(6, 5)
|
|
391 |
\small
|
|
392 |
\begin{tikzpicture}[level distance=10mm, blue]
|
|
393 |
\node {$\meta{E}$}
|
|
394 |
child {node {$\meta{T}$}
|
|
395 |
child {node {$\meta{F}$} child {node {1}}}
|
|
396 |
}
|
|
397 |
child {node {+}}
|
|
398 |
child {node {$\meta{E}$}
|
|
399 |
child[sibling distance=10mm] {node {$\meta{T}$}
|
|
400 |
child {node {$\meta{F}$} child {node {2}}}
|
798
|
401 |
child {node {*}}
|
795
|
402 |
child {node {$\meta{T}$} child {node {$\meta{F}$} child {node {3}}}}
|
|
403 |
}
|
|
404 |
child {node {+}}
|
|
405 |
child {node {$\meta{E}$} child {node {$\meta{T}$}
|
|
406 |
child {node {$\meta{F}$} child {node {4}}}}}
|
|
407 |
}
|
|
408 |
;
|
|
409 |
\end{tikzpicture}
|
|
410 |
\end{textblock}
|
|
411 |
|
|
412 |
\begin{textblock}{5}(1, 10)
|
|
413 |
\bl{\texttt{1 + 2 * 3 + 4}}
|
|
414 |
\end{textblock}
|
|
415 |
|
|
416 |
\end{frame}
|
|
417 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
418 |
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
419 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
420 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
451
|
421 |
\begin{frame}[t]
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
422 |
\frametitle{Arithmetic Expressions}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
423 |
|
451
|
424 |
\bl{\begin{plstx}[margin=3cm,one per line]
|
795
|
425 |
: \meta{E} ::= 0..9
|
451
|
426 |
| \meta{E} \cdot + \cdot \meta{E}
|
|
427 |
| \meta{E} \cdot - \cdot \meta{E}
|
|
428 |
| \meta{E} \cdot * \cdot \meta{E}
|
|
429 |
| ( \cdot \meta{E} \cdot ) \\
|
|
430 |
\end{plstx}}\pause\bigskip
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
431 |
|
451
|
432 |
A CFG is \alert{\bf left-recursive} if it has a nonterminal \bl{$\meta{E}$} such
|
|
433 |
that \bl{$\meta{E} \rightarrow^+ \meta{E}\cdot \ldots$}
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
434 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
435 |
\end{frame}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
436 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
437 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
438 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
451
|
439 |
\begin{frame}[t]
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
440 |
\frametitle{Ambiguous Grammars}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
441 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
442 |
A grammar is \alert{\bf ambiguous} if there is a string that
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
443 |
has at least two different parse trees.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
444 |
|
796
|
445 |
\bl{\begin{plstx}[margin=3cm,one per line]: \meta{E} ::= 0 ... 9
|
451
|
446 |
| \meta{E} \cdot + \cdot \meta{E}
|
|
447 |
| \meta{E} \cdot - \cdot \meta{E}
|
|
448 |
| \meta{E} \cdot * \cdot \meta{E}
|
|
449 |
| ( \cdot \meta{E} \cdot ) \\
|
|
450 |
\end{plstx}}
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
451 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
452 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
453 |
\bl{\texttt{1 + 2 * 3 + 4}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
454 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
455 |
\end{frame}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
456 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
457 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
458 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
459 |
\begin{frame}[c]
|
582
|
460 |
\frametitle{`Dangling' Else}
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
461 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
462 |
Another ambiguous grammar:\bigskip
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
463 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
464 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
465 |
\bl{\begin{tabular}{lcl}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
466 |
$E$ & $\rightarrow$ & if $E$ then $E$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
467 |
& $|$ & if $E$ then $E$ else $E$ \\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
468 |
& $|$ & \ldots
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
469 |
\end{tabular}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
470 |
\end{center}\bigskip
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
471 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
472 |
\bl{\texttt{if a then if x then y else c}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
473 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
474 |
\end{frame}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
475 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
476 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
477 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
478 |
\begin{frame}[c]
|
798
|
479 |
\frametitle{CYK Algorithm}
|
|
480 |
|
|
481 |
Suppose the grammar:
|
|
482 |
|
|
483 |
\begin{center}
|
|
484 |
\bl{\begin{tabular}{@ {}lcl@ {}}
|
|
485 |
$\meta{S}$ & $::=$ & $\meta{N}\cdot \meta{P}$ \\
|
|
486 |
$\meta{P}$ & $::=$ & $\meta{V}\cdot \meta{N}$ \\
|
|
487 |
$\meta{N}$ & $::=$ & $\meta{N}\cdot \meta{N}$ \\
|
|
488 |
$\meta{N}$ & $::=$ & $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\
|
|
489 |
$\meta{V}$ & $::=$ & $\texttt{trains}$
|
|
490 |
\end{tabular}}
|
|
491 |
\end{center}
|
|
492 |
|
|
493 |
\bl{\texttt{Jeff trains geometry students}}
|
|
494 |
|
|
495 |
\end{frame}
|
|
496 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
497 |
|
|
498 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
499 |
\begin{frame}[c]
|
|
500 |
\frametitle{CYK Algorithm}
|
|
501 |
|
|
502 |
\begin{center}
|
|
503 |
\begin{tikzpicture}[scale=1,line width=0.8mm]
|
|
504 |
\draw (-2,0) -- (2,0);
|
|
505 |
\draw (-2,1) -- (2,1);
|
|
506 |
\draw (-2,2) -- (1,2);
|
|
507 |
\draw (-2,3) -- (0,3);
|
|
508 |
\draw (-2,4) -- (-1,4);
|
|
509 |
|
|
510 |
\draw (0,0) -- (0, 3);
|
|
511 |
\draw (1,0) -- (1, 2);
|
|
512 |
\draw (2,0) -- (2, 1);
|
|
513 |
\draw (-1,0) -- (-1, 4);
|
|
514 |
\draw (-2,0) -- (-2, 4);
|
|
515 |
|
|
516 |
\draw (-1.5,-0.5) node {\footnotesize{}\texttt{Jeff}};
|
|
517 |
\draw (-0.5,-1.0) node {\footnotesize{}\texttt{trains}};
|
|
518 |
\draw ( 0.5,-0.5) node {\footnotesize{}\texttt{geometry}};
|
|
519 |
\draw ( 1.5,-1.0) node {\footnotesize{}\texttt{students}};
|
|
520 |
|
|
521 |
\draw (-1.5,0.5) node {$N$};
|
|
522 |
\draw (-0.5,0.5) node {$N,V$};
|
|
523 |
\draw ( 0.5,0.5) node {$N$};
|
|
524 |
\draw ( 1.5,0.5) node {$N$};
|
|
525 |
|
|
526 |
\draw (-2.4, 3.5) node {$1$};
|
|
527 |
\draw (-2.4, 2.5) node {$2$};
|
|
528 |
\draw (-2.4, 1.5) node {$3$};
|
|
529 |
\draw (-2.4, 0.5) node {$4$};
|
|
530 |
\end{tikzpicture}
|
|
531 |
\end{center}
|
|
532 |
|
|
533 |
\begin{textblock}{5}(10,10)
|
|
534 |
\small\bl{\begin{tabular}{@ {}lcl@ {}}
|
|
535 |
$\meta{S}$ & $::=$ & $\meta{N}\cdot \meta{P}$ \\
|
|
536 |
$\meta{P}$ & $::=$ & $\meta{V}\cdot \meta{N}$ \\
|
|
537 |
$\meta{N}$ & $::=$ & $\meta{N}\cdot \meta{N}$ \\
|
|
538 |
$\meta{N}$ & $::=$ & $\texttt{students} \;|\; \texttt{Jeff}$\\
|
|
539 |
& & $\;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\
|
|
540 |
$\meta{V}$ & $::=$ & $\texttt{trains}$
|
|
541 |
\end{tabular}}
|
|
542 |
\end{textblock}
|
|
543 |
|
|
544 |
\end{frame}
|
|
545 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
546 |
|
|
547 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
548 |
\begin{frame}[t]
|
|
549 |
\frametitle{Chomsky Normal Form}
|
|
550 |
|
|
551 |
A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}:
|
|
552 |
|
|
553 |
\bl{\begin{plstx}[margin=0cm]
|
|
554 |
: \meta{S} ::= a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b | a\cdot a | b\cdot b | a | b \\
|
|
555 |
\end{plstx}}
|
|
556 |
|
|
557 |
\end{frame}
|
|
558 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
559 |
|
|
560 |
|
|
561 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
562 |
\begin{frame}[c]
|
|
563 |
\frametitle{CYK Algorithm}
|
|
564 |
|
|
565 |
|
|
566 |
\begin{itemize}
|
|
567 |
\item fastest possible algorithm for recognition problem
|
|
568 |
\item runtime is \bl{$O(n^3)$}\bigskip
|
|
569 |
\item grammars need to be transformed into CNF
|
|
570 |
\end{itemize}
|
|
571 |
|
|
572 |
\end{frame}
|
|
573 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
574 |
|
|
575 |
|
799
|
576 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
577 |
\begin{frame}[c,fragile]
|
|
578 |
\begin{mybox3}{}\it
|
|
579 |
"The C++ grammar is ambiguous, context-dependent and potentially
|
|
580 |
requires infinite lookahead to resolve some ambiguities."
|
|
581 |
\end{mybox3}\bigskip
|
|
582 |
|
|
583 |
|
|
584 |
\hfill from the \href{http://www.computing.surrey.ac.uk/research/dsrg/fog/FogThesis.pdf}{PhD thesis} by Willink (2001)
|
|
585 |
|
|
586 |
\small
|
|
587 |
\begin{center}
|
|
588 |
\begin{lstlisting}[language={},numbers=none]
|
|
589 |
int(x), y, *const z;
|
|
590 |
int(x), y, new int;
|
|
591 |
\end{lstlisting}
|
|
592 |
\end{center}
|
|
593 |
\end{frame}
|
|
594 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
798
|
595 |
|
|
596 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
597 |
\begin{frame}[c]
|
796
|
598 |
\frametitle{Context Sensitive Grammars}
|
|
599 |
|
|
600 |
It is much harder to find out whether a string is parsed
|
|
601 |
by a context sensitive grammar:
|
|
602 |
|
|
603 |
\bl{\begin{plstx}[margin=2cm]
|
|
604 |
: \meta{S} ::= b\meta{S}\meta{A}\meta{A} | \epsilon\\
|
|
605 |
: \meta{A} ::= a\\
|
|
606 |
: b\meta{A} ::= \meta{A}b\\
|
|
607 |
\end{plstx}}\pause
|
|
608 |
|
|
609 |
\begin{center}
|
|
610 |
\bl{$\meta{S} \rightarrow\ldots\rightarrow^? ababaa$}
|
799
|
611 |
\end{center}
|
796
|
612 |
|
|
613 |
\end{frame}
|
|
614 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
615 |
|
465
|
616 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
617 |
|
798
|
618 |
\begin{frame}[t,fragile]
|
|
619 |
\begin{mybox3}{}
|
|
620 |
For CW2, please include '$\backslash$' as a symbol in strings, because
|
|
621 |
the collatz program contains
|
|
622 |
\begin{lstlisting}[language=Scala, numbers=none]
|
|
623 |
write "\n";\end{lstlisting}
|
|
624 |
\end{mybox3}
|
|
625 |
\end{frame}
|
|
626 |
|
796
|
627 |
\begin{frame}[t]
|
|
628 |
\begin{mybox3}{}
|
|
629 |
val (r1s, f1s) = simp(r1)\\
|
|
630 |
val (r2s, f2s) = simp(r2)\\
|
|
631 |
how are the
|
|
632 |
first rectification functions f1s and f2s made? could you maybe
|
|
633 |
show an example?
|
|
634 |
\end{mybox3}
|
|
635 |
\end{frame}
|
|
636 |
|
849
|
637 |
\begin{frame}<1-24>[c]
|
796
|
638 |
\end{frame}
|
|
639 |
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
640 |
|
44
|
641 |
\end{document}
|
|
642 |
|
|
643 |
%%% Local Variables:
|
|
644 |
%%% mode: latex
|
|
645 |
%%% TeX-master: t
|
|
646 |
%%% End:
|
|
647 |
|