ninems/ninems.tex
changeset 45 60cb82639691
parent 44 4d674a971852
child 46 9b48724ec609
--- a/ninems/ninems.tex	Wed Jul 03 23:02:48 2019 +0100
+++ b/ninems/ninems.tex	Thu Jul 04 10:19:35 2019 +0100
@@ -1,4 +1,4 @@
- \documentclass[a4paper,UKenglish]{lipics}
+\documentclass[a4paper,UKenglish]{lipics}
 \usepackage{graphic}
 \usepackage{data}
 \usepackage{tikz-cd}
@@ -466,7 +466,7 @@
     \item[2)] string $ab$ or 
     \item[3)] string $abc$.
 \end{enumerate}
-In order to differentiate between these choices, we just need to remember their positions--$a$ is on the left, $ab$ is in the middle , and $abc$ is on the right. Which one of these alternatives is chosen later does not affect their relative position because our algorithm does not change this order. There is no need to traverse this information twice. This leads to a new approach of lexing-- if we store the information for parse trees  in the corresponding regular expression pieces, update this information when we do derivative operation on them, and collect the information when fininshed with derivatives and calling $mkeps$ for deiciding which branch is POSIX, we can generate the parse tree in one pass, instead of doing an n-step backward transformation.This leads to Sulzmann and Lu's novel idea of using bit-codes on derivatives.
+In order to differentiate between these choices, we just need to remember their positions--$a$ is on the left, $ab$ is in the middle , and $abc$ is on the right. Which one of these alternatives is chosen later does not affect their relative position because our algorithm does not change this order. There is no need to traverse this information twice. This leads to a new approach of lexing-- if we store the information for parse trees  in the corresponding regular expression pieces, update this information when we do derivative operation on them, and collect the information when finished with derivatives and calling $mkeps$ for deciding which branch is POSIX, we can generate the parse tree in one pass, instead of doing an n-step backward transformation.This leads to Sulzmann and Lu's novel idea of using bit-codes on derivatives.
 
 In the next section, we shall focus on the bit-coded algorithm and the natural
 process of simplification of regular expressions using bit-codes, which is needed in
@@ -477,7 +477,7 @@
 
 \section{Simplification of Regular Expressions}
 Using bit-codes to guide  parsing is not a new idea.
-It was applied to context free grammars and then adapted by Henglein and Nielson for efficient regular expression parsing \cite{nielson11bcre}. Sulzmann and Lu took a step further by intergrating bitcodes into derivatives.
+It was applied to context free grammars and then adapted by Henglein and Nielson for efficient regular expression parsing \cite{nielson11bcre}. Sulzmann and Lu took a step further by integrating bitcodes into derivatives.
 
 The argument for complicating the data structures from basic regular expressions to those with bitcodes
 is that we can introduce simplification without making the algorithm crash or impossible to reason about.
@@ -571,7 +571,7 @@
 %\end{definition}
 
 
-Sulzmann and Lu's integrated the bitcodes into annotated regular expressions by attaching them to the head of every substructure of a regularexpression\emph{annotated regular expressions}~\cite{Sulzmann2014}. They are
+Sulzmann and Lu's integrated the bitcodes into annotated regular expressions by attaching them to the head of every substructure of a regular expression\emph{annotated regular expressions}~\cite{Sulzmann2014}. They are
 defined by the following grammar:
 
 \begin{center}
@@ -674,7 +674,7 @@
 \end{center}    
 %\end{definition}
 This function completes the parse tree information by 
-travelling along the path on the regular epxression that corresponds to a POSIX value snd collect all the bits, and
+travelling along the path on the regular expression that corresponds to a POSIX value snd collect all the bits, and
 using S to indicate the end of star iterations. If we take the bitsproduced by $bmkeps$ and decode it, 
 we get the parse tree we need, the working flow looks like this:\\
 \begin{center}