1179 in an injection-based lexer, one could still end up in |
1179 in an injection-based lexer, one could still end up in |
1180 trouble, when cases that require more involved and aggressive |
1180 trouble, when cases that require more involved and aggressive |
1181 simplifications arise. |
1181 simplifications arise. |
1182 \section{A Case Requring More Aggressive Simplifications} |
1182 \section{A Case Requring More Aggressive Simplifications} |
1183 For example, when starting with the regular |
1183 For example, when starting with the regular |
1184 expression $(a^* \cdot a^*)^*$ and building a few successive derivatives (around 10) |
1184 expression $(a^* \cdot a^*)^*$ and building just over |
|
1185 a dozen successive derivatives |
1185 w.r.t.~the character $a$, one obtains a derivative regular expression |
1186 w.r.t.~the character $a$, one obtains a derivative regular expression |
1186 with more than 9000 nodes (when viewed as a tree) |
1187 with millions of nodes (when viewed as a tree) |
1187 even with simplification. |
1188 even with simplification, which is not much better compared |
1188 \begin{figure} |
1189 with the naive version without any simplifications: |
|
1190 \begin{figure}[H] |
|
1191 \centering |
1189 \begin{tikzpicture} |
1192 \begin{tikzpicture} |
1190 \begin{axis}[ |
1193 \begin{axis}[ |
1191 xlabel={$n$}, |
1194 xlabel={$n$}, |
1192 ylabel={size}, |
1195 ylabel={size}, |
1193 legend entries={Naive Matcher}, |
1196 legend entries={Simple-Minded Simp, Naive Matcher}, |
1194 legend pos=north west, |
1197 legend pos=north west, |
1195 legend cell align=left] |
1198 legend cell align=left] |
1196 \addplot[red,mark=*, mark options={fill=white}] table {BetterWaterloo.data}; |
1199 \addplot[red,mark=*, mark options={fill=white}] table {BetterWaterloo.data}; |
|
1200 \addplot[blue,mark=*, mark options={fill=white}] table {BetterWaterloo1.data}; |
1197 \end{axis} |
1201 \end{axis} |
1198 \end{tikzpicture} |
1202 \end{tikzpicture} |
1199 \caption{Size of $(a^*\cdot a^*)^*$ against $\protect\underbrace{aa\ldots a}_\text{n \textit{a}s}$} |
1203 \caption{Size of $(a^*\cdot a^*)^*$ against $\protect\underbrace{aa\ldots a}_\text{n \textit{a}s}$} |
1200 \end{figure}\label{fig:BetterWaterloo} |
1204 \end{figure}\label{fig:BetterWaterloo} |
1201 |
1205 |