# Changeset 4453 for docs/Working/icGrep

Ignore:
Timestamp:
Feb 3, 2015, 4:29:58 PM (4 years ago)
Message:

First draft

File:
1 edited

### Legend:

Unmodified
 r4446 \section{Unicode Regular Expression Methods}\label{sec:Unicode} \textsc{}\section{Unicode Regular Expression Methods}\label{sec:Unicode} \subsection{toUTF8 Transformation}\label{sec:Unicode:toUTF8} The icGrep parser generates an abstract syntax tree (AST) that represents an input regular expression over code points.  This AST is passed as input to the toUTF-8 transformation that generates a new AST that represents the equivalent regular expression over UTF-8 byte sequences. The transformation accomplishes this by first determining the number of UTF-8 bytes that are required to represent each code point contained within each character class.  The code points are then split into sequences of bytes, where each byte is encoded with the necessary UTF-8 prefix after which they are each assigned to a new character class in the new AST.  For an example, consider the following regular expression that consists entirely of multibyte Unicode characters: \verb:\u{244}[\u{2030}-\u{2137}]:.  The AST from the parser would represent this as a sequence starting with a character class containing the code point \verb:0x244: followed by a second character class containing the range from \verb:0x2030: to \verb:0x2137:.  After being passed through the toUTF-8 transformation this AST would become considerably more complex.  The first code point in the sequence would be encoded as the two byte sequence \verb:\u{C9}\u{84}:. The character class containing the range, which is a range of three byte sequences would be expanded into the series of sequences and alternations that are necessary to specify all of the possible byte encodings that would be contained within the range.  The UTF-8 encoded regular expression for the range \verb:[\u{2030}-\u{2137}]: would be encoded as follows: \newline { \small \verb:\xE2((\x84[\x80-\xB7])|(([\x81-\x83][\x80-\xBF])|(\x80[\xB0-\xBF]))): \newline } Transforming the regular expression immediately after parsing from being a regular expression over code points into a regular expression over bytes simplifies the rest of the compiler, as the compiler only needs to be concerned with single bytes as opposed to code points, which vary in size. \subsection{UTF-8 Advance using ScanThru} Each bit position in the character class bitstream of a single byte ASCII character marks either the location of, or the absence of the search character. To match the location of a character the current position of the cursor is checked to see if the bit is set and then the cursor is advanced by one position. To match the position of a multibyte search character the procedure is different. For multibyte UTF-8 characters of length \verb:k:, it is the last \verb:(k-1):th byte of the multibyte sequence in the bitstream that marks the location of the  multibyte character. Figure~\ref{fig:multibytesequence} illustrates the process of matching a character class of a three byte character.  The locations of the first two bytes of each character in the character class CC have been marked with zeros. To match multibyte characters, first a \emph{nonfinal} helper bitstream must be formed.  The \emph{Nonfinal} bitstream is formed by marking the locations of the first bytes of two byte sequences, the first two bytes of three byte sequences, and the first three bytes of any four byte sequences. The \verb:ScanThru(current, nonfinal): operation is then applied, in order to advance all of the current cursor positions to the locations of the \verb:(k-1):th final character positions.  To find any matches the result is then compared with the bits that are set in the UTF-8 character class bitstream. After this, the cursor is advanced by one position to be ready for the next matching operation. \begin{figure}[tbh] \begin{center} %\begin{tabular}{cr}\\ \begin{tabular}{rclr} \\ $CC$ & \verb001...001.........\\ $M_1$ & \verb1.....1....1......\\ $nonfinal$ & \verb11....11..........\\ $T_1 = ScanThru(M_1, nonfinal)$ & \verb..1.....1.........\\ $T_2 = CC \land T_1$ & \verb..1.....1.........\\ $M_2 = Advance(M_1)$ & \verb...1.....1........ \end{tabular} \end{center} \caption{Processing of a Multibyte Sequence} \label{fig:multibytesequence} \end{figure} \subsection{MatchStar for Unicode character classes} Figure~\ref{fig:multibytesequence_matchstar} shows how the MatchStar operation can be used to find all matches of a multibyte UTF-8 sequence.   The problem is to find all matches to the character class CC that can be reached from the current cursor positions in $M_1$. First we form two helper bitstreams \emph{initial} and \emph{nonfinal}.  The initial bitstream marks the locations of all single byte characters and the first bytes of all multibyte characters.  Any full match to a multibyte sequence must reach the initial position of the next character.  The nonfinal bitstream consists of all positions except those that are final positions of UTF-8 sequences.   It is used to "fill in the gaps" in the CC bitstream so that the MatchStar addition can move through a contiguous sequence of one bits.  In the figure, the gaps in CC are filled in by a bitwise-or with the nonfinal bitstream to produce $T_1$.   This is then used as the basis of the MatchStar operation to yield $T_2$.  We then filter these results using the initial bitstream to produce the final set of complete matches $M_2$. \begin{figure}[tbh] \begin{center} %\begin{tabular}{cr}\\ \begin{tabular}{rclr} \\ $CC$ & \verb001001001.........\\ $M_1$ & \verb1...........1..1..\\ $initial$ & \verb1..1..1..1..1..1..\\ $nonfinal$ & \verb11.11.11.11.11.11.\\ $T_1 = nonfinal \lor CC$ & \verb11111111111.11.11.\\ $T_2 = MatchStar(M_1, T_1)$ & \verb111111111111......\\ $M_2 = T_2 \land initial$ & \verb1..1..1..1........\\ \end{tabular} \end{center} \caption{Processing of MatchStar for a Multibyte Sequence} \label{fig:multibytesequence_matchstar} \end{figure} \subsection{Predefined Unicode classes} With each of the Unicode general categories containing such a large number of code points, an \emph{If Hierarchy} optimization has been included in the statically compiled implementation of each category.  The optimization works under the assumption that most input documents will only contain the code points of the characters from a small number of writing systems. Processing the blocks of code points for characters that exist outside of this range is unnecessary and will only add to the total running time of the application.  The optimization tests the input text to determine the ranges of the code points that are contained in the input text and it only processes the character class equations and the regular expression matching equations for the code point ranges that the input text contains. The optimization tests the input text with a series of nested \emph{if else} statements, using a process similar to that of a binary search.  As the nesting of the statements increases, the range of the code points in the conditions of the \emph{if} statements narrow until the exact ranges of the code points in the text has been found. \subsection{Character Class Intersection and Difference} \subsection{Unicode Case-Insensitive Matching}