\begin{frame}{Lexical Analysis} \begin{goal}{} How to get from characters to tokens? \end{goal} \begin{itemize} \pause \item Regular expressions $r_1,\ldots,r_n$ express the pattern. \smallskip \emph{Every regular expression corresponds to a token.} \pause \item Lexical analysis repeatedly searches the \emph{longest prefix} of the input that is matched by one of the regular expressions. This prefix is transformed into a token. % \pause\smallskip % % When no prefix matches, the result is an error message. % \pause\smallskip % % When there are multiple longest prefixes, one is chosen. \end{itemize} \pause \begin{goal}{} For \emph{improved performance}: \begin{itemize} \item Regular expressions are translated \emph{minimal DFAs}. \end{itemize} \end{goal} \pause \begin{exampleblock}{} Parser/lexer generators like \begin{itemize} \item JavaCC \item LEX \end{itemize} generate the lexer automatically. Thereby regular expressions or grammars are converted to minimal DFAs. \end{exampleblock} \end{frame}