Queχ - Lexical Analyser Generator

The queχ program generates a lexical analyser that scans text and identifies patterns. The result of this lexical analysis is a list of tokens. A token is a piece of atomic information directly relating to a pattern, or an event. It consists of a type-identifier, i.e. the token type, and content which is extracted from the text fragment that matched the pattern.

Figure (here) shows the principle of lexical analysis. The lexical analyser receives a stream of characters "if( x> 3.1 ) { …" and produces a list of tokens that tells what the stream signifies. A first token tells that there was an if statement, the second token tells that there was an opening bracket, the third one tells that there was an identifier with the content x, and so on.

In compilers for serious programming languages the token stream is received by a parser that interprets the given input according to a specific grammar. However, for simple scripting languages this token stream might be treated immediately. Using a lexical analyser generator for handcrafted ad-hoc scripting languages has the advantage that it can be developed faster and it is much easier and safer to provide flexibility and power. This is demonstrated in the following chapters.

The following features distinguish queχ from the traditional lexical analysers such as lex or flex:

This text briefly explains the basic concepts of lexical analysis in queχ. Here, a short review is given on lexical analysis, but then it concentrates on the introduction of the features mentioned above. The subsequent chapter dicusses a simple example of a complete application for lexical analysis. The final chapter elaborates on the formal usage of all features of queχ.

Before beginning the installation of queχ, make sure that Python (http://www.python.org) is installed. Most linux distributions provide handy rpm packages—so this should not be an issue. Then, follow these steps:

That is all. Now, you should either copy the directories ./demo/* to a place where you want to work on it, or simply change directory to there. These directories contain sample applications 000, 001, $\ldots$. Change to the directory of the sample applications and type make. If everything is setup properly, you will get your first queχ-made lexical analyser executable in a matter of seconds.

The example applications depict easy ways to specify traditional lexical analysers, they show some special features of queχ such as mode transitions, and more. Each demo-application deals with a particular feature of queχ:

The author of this document suggests that the user look at these sample applications first before continuing with the remainder of this text. With the background of easy-to-use examples to serve as starting point for their own efforts, it should be natural to get a feeling for the ease of queχ.

The Software is distributed under LPGL, provided the following restriction:

Note, that if any part of the LPGL contradicts with the former restrictions, the former restrictions have precedence. The no warranty clause holds in any case. Here is a brief summary of the LPGL:

The name queχ obviously has a lexo-graphical relation to lex and flex—the most well known tools for generating lexical analysers at the time of this writing. The Qu at the beginning of the word stands for quick, so hopefully the new features of queχ and the ability to create directly coded engines will generate much faster lexical analysers. Also, the process of programming shall be much quicker by means of the handy shortcuts and elegant solutions that queχ provides.

The last letter χ is a the greek lowercase letter chi. It is intended to remind the author of this text that he actually wanted to create a better \TeX
[As Donald Knuth explains it\cite{}, the last letter in \TeX is an uppercase chi so the name is to be pronounced like the German word ach (it's actually more a sound Germans utter, rather than a word with a dedicated meaning). Analogously, the χ at the end of queχ should not be pronounced like the x of the German word nix.]
system with optimized source code appearance. When he realized that traditional lexical analysers did not provide the functionality to express solutions easily he started working on queχ—and dove much deeper into the subject than he ever thought he would.

Lexical analysis is all about patterns. The following section recalls some basics of the mechanicss of pattern matching. For a detailed description see \cite{}, \cite{}, and \cite{}. It also explains how tokens are communicated to the caller of the lexical analyzer. Further, it introduces queχ's concept of lexical analyzer modes. Finally, a section explains the control and handling of mode transitions.

Pattern matching can be described as a finite state automaton where incoming characters play the role of triggers. Each incoming character (trigger), determines whether the state machine transits into a new state or if it remains in the same state. Consider figure Example that depicts a state machine to match a floating point number. In its initial state it waits for a digit (the START state). If no digit arrives, the state machine goes into the FAILED state. It can be said for sure, that there was no number. If a digit arrives, though, it transits into DIGITS-A. As long as digits arrive, it remains in this state. If a non-digit comes in it transits into the ACCEPTANCE state, since already enough digits have arrived as to judge that it is a number. However, if a dot arrived, then the state machine enters into the DOT state. If after the dot a new digit arrives, it enters into the state DIGITS-B. Note, that in the states DIGITS-A, DOT, or DIGITS-B a character from the else set (non-expected characters) lets the machine still transit into an ACCEPTANCE state, since enough characters have arrived to judge that it is a number.

In real world lexical analysis a whole bank of state machines are active at the same time. Starting from a position $x_0$ in the character stream, a_ step in lexical analysis_ consists of the following procedures:

In brief, a step in lexical analysis starts at a position $x_0$ in the character stream. After eating some characters, at some position $x_1$, it can be decided what pattern matches the best, and eventually the action related to the winning pattern is executed. Then lexical analysis starts at position $x_1$ all over again until the end of the character stream.

In principle, the functioning of a lexical analyser is determined by a 1) a set of patterns and 2) by their related actions. For most practical applications though one requires additionally a definition of token identifiers because the signals need to be understood by another unit (e.g. the parser).

Traditionally, lexical analysers send a single token for an identified pattern in the character stream. Practically, this means that, after a pattern match has happened the token-getter-function returns the token that was identified. Queχ, though, implements a more flexible approach which is better suited for implicit tokens and mode transitions. The following section shows how tokens are communicated by a lexical analyser created with the queχ program.

Queχ promotes the idea of implicit tokens, i.e. tokens that are produced without any pattern match. This concept raised from the fact that some tokens are, in fact, redundant and can be derived from context. From the perspective of the source code appearance of a programming language, a redundancy free language is much clearer than one that forces the programmer to specify information over and over again. Consider the example of the \verb|\|begin-\verb|\|end-regions in {LaTeX} as shown in the subsequent listing.

Logically, the begin and end tokens could have been derived from the fact that an \verb|\|item token pops up in normal text mode. Implicit tokens means that the lexical analyser can read between the lines. It sees things that are meant to be there from the context. Implementing the concept of implicit token generation inside lexical analysis rather than in a parsers allows the parser to constitute a unit that reasons logically, i.e. it considers distinct signals as input, it has a clear set of grammatical rules, and produces a clear understanding of the information (e.g. a syntax tree of a program). In Queχ's philosophy words that are implicitly thought to be inserted into the context of a sentence, are treated by lexical analysis. Multiple-Meanings (TODO: check this wording), i.e. the interpretation of a signal/token due to its context is expressed by grammar.

Traditionally, the parser calls a function of the form get_token(); the lexical analyser does one single pattern match, and then returns the token that represents the matched pattern---or an error, if no pattern matched. This mechanism is not sufficient when implicit tokens are involved, because implicit tokens can pop up out of nowhere in the character stream. When a pattern matches a whole set of such implicit tokens may be ready to be sent.

image::figures/token-queue.png

Figure style=ref shows the information flow when a lexical analyser generated by queχ parses a character stream. The user begins and requests a new token using member function get_token(). The engine's object start then the lexical analysis. During the analysis, the pattern matching actions may send a whole set of tokens into the _token-queue_. When the pattern matching actions decide to come back, the get_token() function returns the first token that was entered into the queue.

The subsequent call to get_token(), though, does not trigger a lexical analysis since there are still tokens in the queue. Until the queue is empty, the function only returns tokens from the queue. When the queue is empty, the lexical analysis starts again in the same manner as described above. From the caller's side the process appears to be a reading from a continuous token stream. From inside the pattern match action the process appears to be a sending process, where tokens are sent to some recipient.

An important discussion evolves around what type of variables should be supported by the token that is sent. The author of queχ, prefers the idea of separating the interpretation of the lexeme from lexical analysis. This is for the following reasons:

On the other hand, there might be hints that the lexer gives about a token. The author did not come up with the perfect token class, but instead leaves it open to be redefined by the user for his particular needs.

In many cases the behavior of lexical analysers can be described effectively by modes for lexical analysis. A standard example is format strings. In format strings, there is no need for the lexical patterns that are necessary when parsing an algorithm. They are actually better turned off. Thus, a mechanism is needed that is able to control the activation and deactivation of groups of patterns to be matched.

A lexical analyser mode is a state of the lexical analyser where only a particular set of patterns is actively waiting to be matched. A lexical analyser needs to be in exactly one mode at a particular point in time. Thus, a lexical analyser mode corresponds to the way that the input stream is currently transformed into signals, i.e. tokens. To handle the detection and influence of mode transitions, Queχ provides event handling mechanisms as described in the following sections.

A potential disadvantage of modes is confusion. With traditional lexical analyser generators. In flex, for example, the end-user does not see more than a token stream. He has no insight into the current lexical analyser mode. He cannot sense or control the mode transitions that are currently being made. The mode transitions are hidden somewhere in the pattern match actions. GNU Flex's start conditions are similar to modes, but the only way two modes, A and B, can be related in flex is via inclusion, i.e. by letting a pattern be active in A and B. There is no convienient mechanism to say: let B override all patterns of A. This is where the mode inheritance relationships of Queχ provide clear, convenient advantages as described in the section after next.

Object oriented programming introduced the concept of_ inheritance_\cite{}, in the sense that two classes can have an is-a relationship. The class of cars may for example be related to the class of vehicles by an is-a relationship. This means that cars inherit all attributes of the broader class vehicles and may add some specific attributes to it. Such inheritance relationships are directional. In our example this means that every object that belongs to the class of cars also belongs to the class of vehicles (every car is a vehicle). However, not every object that belongs to the class of vehicles (e.g. a submarine) belongs to the the class of cars. Mode inheritance in queχ works similarly and effects the following three mechanisms:

Figure style=ref shows an example where mode A acts as a base for mode B. Internally, queχ creates a new mode B* that contains the patterns that were explicitly givent by the definition of B and the patterns that are inherited from A. The pattern match action of {sf XYZ} from mode B is omitted, since mode B has to behave like mode A for patterns specified in mode A. The on_entry and on_exit functions of mode A are pasted into B's own event handlers, so that they are executed before them. What is not displayed in the figure is access inheritance. When Queχ checks the entry and exits of a mode it consideres automatically also the base classes. If there is no base mode that acts like a door opener to a particular mode, then transits will cause a run-time error.

In conclusion, it can be said that inheritance is a very useful tool to implement some standard behavior in a base mode. Derived modes can then comply to this standard simply by being derived from this mode. Also, for the control of mode transitions the is-a relationships of inheritance provides a lot of flexibility. Mode inheritance promotes thinking about mode relationships naturally and helps to avoid code duplication.

In Queχ, modes can be changed by two basic mechanisms. First, modes can simple be changed. This makes sense if the new mode knows exactly to which mode it has to change, and this does not depend on the previous mode. Another mechanism is that of pushing and popping. This makes sense if the new mode shall return to the previous mode. It is therefore similar to a call-subroutine in procedural programming languages.

Figure style=ref shows a typical mode transition. Mode X has some patterns and one of them matched. Inside the pattern match action a transition to mode Y is requested. This triggers the event handler on_exit() of mode X before any transition is made. Here the user can send tokens, change some internal variables or write some debug output. Then the event handler on_entry() of entered mode Y is called. Again, the user can provide some actions related to the entrance of that mode.

The ability to define event handlers for entering and exiting modes not only supports implicit token production, but also supports transparency. It can now exactly be traced how modes are transitted. In order to restrict the transition from and to lexical modes, queχ provides transition control mechanisms. In the header of a definition of a mode X it can be specified from which modes mode X can be entered and to which modes mode X can exit. If a mode transition happens that does not conform to these restrictions, a run-time error is triggered. This helps to prevent the lexical analyser from sliding from one mode to another due to some thoughtlessly designed patterns.

Figure style=ref shows an example, where mode transition control is very handy. There is a lexical mode for parsing the content of a {sf FUNCTION}, a mode for {sf COMMENT} and one for {sf DOCU}-mentation parsing, a mode for parsing a character {sf STRING} and one for {sf MATH}. The design here says that the comment mode can only be activated from the {sf FUNCTION} mode and can only leave to {sf FUNCTION} mode. Similarly for the {sf STRING} and the {sf MATH} mode, Queχ provides the feature that for {sf COMMENT} mode, for example, one can specify that it can only be entered from {sf FUNCTION} mode, thus preventing the {sf DOCU}, {sf STRING} and the {sf MATH} mode from ever transiting into {sf COMMENT} mode. Also, it can be specified that the {sf COMMENT} mode can only exit to {sf FUNCTION} or {sf DOCU} mode, thus preventing it from dropping into {sf STRING} or {sf MATH} mode.

Extensive mode transitions, without a control mechanism as implemented is queχ, is highly error prone. The advantage is that the restrictions on the mode transitions are explicitly specified in the description of the lexical analyser. The alternative would be to create an external document and review the behavior of the lexical analyser with respect to mode transitions whenever an error is assumed from being caused by straying mode transitions. Practically, solid handling of extensive mode transitions in lexical analysis are not possible except with a control mechanism as provided by queχ.

With the rise of the Python programming language, the use of indentation as the scope delimiter has become popular. Indeed, it may be the most efficient method to delimit scope with the least amount of additional characters provides a convenient mechanism to handle indentations which runs quasi-parallel to the pattern matching: indentation events.

Figure style=ref displays an example of the principle of indentation events. Whenever the lexical analyser reaches the first non-whitespace in a line, an indentation event (indicated as a little star in the figure) is triggered. The lexical analyser engine then calls a user defined indentation handler. The numbers at the indentation events indicate the number of characters that the indentation spans. They are passed to the user's indentation handler as arguments. The indentation handler can then keep track of indentation blocks or whatever its little heart desires.

Note that it is not trivial to express indentation in terms of pattern action pairs based solely on regular expressions. It is not enough to define a pattern such as

That is a newline followed by whitespace. Imagine, one introduces a comment sign such as the traditional # for comment until newline. The comment eating pattern would be at first glance:

That is a # followed by anything but newline and then one newline. The action related to this pattern would have to put pack the last newline. Otherwise the indentation catcher which starts with a newline can never trigger. In this particular case, this problem can be solved by deleting the last newline from the comment eater pattern, knowing that after as many not-newline as possible there must be a newline, i.e.

The last newline is then eaten by the indentation catcher. However, the main problem remains: with such a design patterns need to know about each other to work propperly! In an environment of many different modes which are additionally related by inheritance, it is difficult to guarantee that all patterns respect the quirks of each other. They better work independently. The indentation events of queχ prevent inter-pattern dependencies.

Similarly, catching indentation with pre-condition newline plus whitespace, i.e. \verb|^[ \t]*| is fragile, in the sense that another pattern that contains newline plus whitespace might hinder this pattern from triggering. In a lexical analyzer with dozens or hundreds of patterns this becomes quickly unmanageable. Errors that arise from patterns defined somewhere else are very hard to find and require a lot of insight into the actual process of lexical analysis. Using the on_indentation event handler ends up in a much clearer and safer design. For more information about the pre-condition newline pitfall see section // \ref{sec-formal/patterns/context-dependent-pitfalls}, page // \pageref{formal/patterns/context-dependent-pitfalls}. [formal-patterns-context-dependent-pitfalls].

Caveat:

Note that if a pattern contains more than one newline then only the indentation event concerning the last newline is triggered! Imagine a pattern

then the following pattern would match

If this matches, then the lines of hello and world do not trigger an indentation event. So, when dealing with indentation based scoping such strange things are best avoided\footnote{Probably, it is anyway hard to think of a case where such pattern definitions are not to be avoided.}.

Any compiler or lexical analyzer imposes rules on the text that it has to apply. Most of those texts are written by humans, and humans occasionally make errors and disrespect rules. A gentle compiler tells its user about his errors and also tells it about the place where the error occured. Here line numbering becomes crucial. Additionally, columns can be counted. This provides even more detailed information.

There is a general default algorithm to count lines and columns that is always applied in case that there is no better alternative. Queχ analyzes the patterns and adapts the way of counting lines and columns according to special characteristics\footnote{Actually, even the indentation count algorithm is adapted to profit from knowledge about the patterns internal structure.}. If the pattern contains, for example, a fixed number of newlines, then only a fixed number is added and no newlines are counted at runtime. The mechanisms for line and column counting are optimized for the most reasonable pattern characteristics. There are strange cases\footnote{Example: A pattern that contains a newline which is followed by a fixed number of characters. The determination of this in the context of post-conditions is complicated. On the other hand, such patterns are considered strange and occur rarely,, so the expected gain with an optimized algorithm was considered negligible by the author.} for which a slightly better counting mechanism might be found. For reasonable applications as known from popular programming languages the mechanisms of counting should be optimal.

Note that line and column counting can be turned off individually by pre-processor switches. By these switches the generated analyzer is naked of any counting mechanism and it is likely that it runs a little faster. For serious applications, though, at least line number counting should be in place for error reporting.

This chapter discussed the major features of queχ. To the knowledge of the author of this text, at the time of this writing, there is no lexical analyser generator that matches these features. Moreover, once one gets used to thinking in terms of sending tokens and mode-transitions, and once one gets used to defined modes that implement standard behavior for other modes using inheritance, then it becomes hard to get back to the cumbersome thinking of plain lex or flex. The little overhead required to learn new concepts comes with the great advantage of being able to design the lexical analysis process in a very natural way
[Well, at least natural to the author of this text.]
.

This practical example guides the user through the phases of creating a lexical analyser using queχ. The files used in this example can be found in the directory demo/001/ of the queχ distribution. The file simple.qx contains the description of the lexical analyzer, lexer.cpp contains a lexical analyzer application, and a Makefile allows for the convenient creation of the whole lexical analyzer application. Copying and pasting this example may be a good starting point for working with queχ. A good approach is to divide the development of a lexical analyzer into the two steps of design and implementation. The first step consists of three minor activities:

Once these simple steps are completed, the implementation of the modes in terms of pattern-action pairs can be started. The example discussed in this section develops the following files, which are required for generating a lexical analyser:

To follow the explanations of this chapter the directory demo/001 is best copied into a user domain for further examination and modifications.

In this simple example, only very basic patterns have to be defined. There is a pattern for whitespace, consisting of space, tabulator, and newline. There are two bracket types for opening and closing brackets: an assignment operator =, the two keywords if and struct, identifiers consisting of letters from A-Z in capital and lower-case, floating point numbers and string delimeters. The listing in figure [fig-pattern-code] shows the content of the define section in simple.qx describing all required patterns in terms of regular expressions.

The filename including the extension can, of course, be chosen freely. Note that all pattern names are global. They are not local to a specific mode. That means, that all modes can access the pattern definitions. Note also that inside the define-range only //-comments are allowed. The P_-prefix was chosen to indicate to the reader, that this is a pattern definition. There is no danger of interfering with the program namespace. These shorthand names are only considered for the definition of regular expressions. The later generated engine does not contain them as variables.

Token-ids can be specified as simply as patterns. A token-section containing token-ids only has to contain a newline separated list of token names. Queχ will create a set of constants with unique numerical values. Figure [fig-token-ids-code] shows the definition of token-ids for the example.

Note, that queχ pastes a prefix in front of the numerical constants for the tokens. A token-id of STRUCT will be called TOK_STRUCT, if TOK is specified as token-prefix. This is discussed briefly in the section [sec-formal-command-line-options]. It is also important to reinforce that the token-ids are relevant to the namespace. They name constant variables inside the namespace queχ. It is not advisable to set the token-id prefix to an empty string and name a token-id i or x because those names are likely to interfere with the names of other variables.

The design of modes, their relations, and their transitions is something to be done informally with a drawing program or on a sheet of paper. It is basically an aid to help user develop a clear design of the lexical analysis process. In our simple example, there are only three modes:

The inheritance relationships in this example are displayed in figure style=ref. Both real modes PROGRAM and` STRING_READER` are derived from END_OF_FILE so that they implement the standard behavior for the end-of-file event.

In this example, the lexical analyser can only be in one of two modes. The posible transitions are shown in figure style=ref. PROGRAM mode can transit into STRING_READER mode and vice versa. The mode inheritances and transitions are only pinpointed in non-machine readable form. This information can be used to write the first stubs of the modes in which one will later fill in the pattern-action pairs.

The three code-stubs for the three modes are shown in figure style=ref. Until now, there are no pattern action pairs defined inside the modes. The dots … inside the curly braces will later be replaced by the pattern-action pairs. First of all, mode END_OF_FILE is defined. It does not inherit any mode, but can only be used as a base mode. Thus the option

is specified in edgy brackets. Second, the PROGRAM mode is derived from END_OF_FILE which is indicated by its name following the colon. The options

tell that this mode can be entered from STRING_READER mode, and that it can exit to this mode. Any transition to another mode (that is not derived from STRING_READER) is detected as an error\footnote{Note, that inside queχ assert() commands are used. According to ISO9899 (ANSI-C) the command only takes effect, if NDEBUG is not defined. If it is, the mode transitions are consequently not checked by the queχ engine. The general rule applies here also: only define NDEBUG if it is 100\% safe to say that no use-case will violate the design.}. Analogously, the STRING_READER mode is defined specifying its base class and the allowed transitions to PROGRAM.

Note, that all options given here are indeed optional. They are not necessary to define pattern-action pairs and they do not contribute to the functioning of the generated lexical analyser. However, they allow verification of whether or not mode definitions and mode transitions are according to the design. The detection of usage against design specifications is a great help to avoiding errors or finding their causes.

The previous sections explained the definitions of patterns, token-ids, and mode characteristics. In this section the core of the lexical analysis is discussed: pattern-action pairs. It is a basic concept in lexical analysis that a pattern triggers an action. This action has the following goals:

The most simple pattern-action pair consists of sending a specific token whenever a particular pattern occurs. Consider for example figure style=ref. It shows the definition of a mode that can handle the end of a file. The only pattern of this mode is <<`EOF`>>. The action to be executed if this pattern occurs is embraced by curly brackets. Inside the brackets a special token is sent, a token with the id:

telling that lexical analysis is over. Note, that in queχ the keyword self and not a this-pointer is used to refer to the lexical analyser. Recall that queχ is a code generator, not a compiler. Internally, the code fragments that are specified as pattern-action pairs or event handlers may be pasted by queχ into objects other than the lexical analyser (e.g. the lexical-analyser-mode-information structures). Also the user might derive his own class from the lexical analyser class, so there would be a type-issue. To unify the access to the lexical analyser, all places were code is pasted allow to use self as a variable that represents the lexical analyser. Use self. not this→!

A final RETURN statement in the pattern-action pair says that the flow of control can be turned back to the caller of function` get_token(). Note again, that `return is not used. The RETURN macro ensures that the token queue is in a sound state before returning from the lexical analysis. The rule here is: say RETURN not return.

The pattern-action pairs of the PROGRAM mode displayed in figure style=ref are a little more diverse. Note also, that for simple patterns the operator =$>$ is used to express the sending of a token of a specific id. The whitespace pattern does not cause any token to be sent and one does not return to the user, thus it is followed by an empty pair of curly brackets. The pattern P_IDENTIFIER creates a token that contains the string that was matched. P_NUMBER also stores a number that corresponds to the lexeme that was matched. The pattern` P_STRING_DELIMITER` initiates a mode transition to the mode STRING_READER. Since we are working with a token queue it is necessary to send a dummy token TKN_EVENT_MODE_CHANGE and return. The return is necessary, so that the analyser function pointer can be reset by the analyser.

The STRING_READER mode's pattern-action pairs are shown in figure style=ref. This mode makes use of a special member of the lexical analyser object: _the accumulator_. This object allows accumulation of text from incoming patterns and flushes them when desired. When this mode is entered, the accumulator is emptied (see on_entry). When this mode is left, the accumulator is flushed (see on_exit). This means, that if the accumulated text is not empty, it is sent as a token with a user defined token-id. The STRING_READER mode sends the accumulated text with a token-id TKN_STRING.

The arrival of a string delimiter causes a mode transition back to the mode PROGRAM. A backslashed string delimiter allows a string delimiter inside the string so that it does not cause a return to PROGRAM mode. Instead, it adds a quote to the accumulator. The default action . specifies that any other incoming text is simply accumulated. Even in this simple example it becomes clear that the specification of entry and exit event handlers facilitates the specification of mode transitions. It can be said that wherever in the code a command triggers an exit to another mode, the accumulator is flushed.

This section now finished the specification of file simple.qx as an input file for the queχ lexical analyser generator. The next section tells how to call queχ to generate a full fledged engine that does the lexical analysis as required.

In order to skip portions of the input without considering its content, queχ provides the ability to define so called skippers. Skippers can be used, for example, to skip whitespaces and comments. Of course, most of the skippers can also be defined as patterns that have no action related to it. However, there are great advantages to using skippers rather than their implementation as a skipping pattern.

First of all, skippers offer faster performance since they only compare against the closing delimiter while swallowing the input file. Second, they may reduce the required buffer size. Normally, the buffer size has to be in the range of the size of the largest possible token. This would include skipping patterns, such as patterns eating the / - / type of comments. With skippers the buffer size could be left at 64K, even though, comments may be much larger. Finally, the nested skipper type, allowing nested comments, for example, cannot be implemented as a regular expression.

With the files from directory \$(QUEX_PATH)/DEMO/001/ the creation of the example lexical analyser application is as simple as can be. Type make in the command line and the application is built. The Makefile that comes with the sample application is written in a way that makes it very easy to adapt and extend its contents for other user's needs. The core of this make file explains how to call queχ:

The build rule says that whenever one of the files containing mode descriptions changes the source code for the lexical analyser has to be rebuild. In our example the only mode file is simple.qx. Queχ receives the names of the input file names as no-minus followers of the command line option —mode-files.

The output of queχ is determined by the option —engine. The name that follows it specifies the name of the class that implements the engine. But, it also acts as a filestem for all output files. In our example, the engine's name is tiny_lexer. Therefore, there will be four files created:

Once the engine sources are built by queχ, an example application can be built that uses the lexical analyser. The source code for the example is specified in file lexer.cpp. The content of this file is shown in figure [fig-sample-application].

Initially, the lexical analyser needs to be created as an object of type` queχ::tiny_lexer`. The filename of the file to be analysed is directly passed to the constructor of the class. Then, set the initial lexical analysis mode. In our example, PROGRAM shall be the initial mode. Since it shall not trigger any mode transitions or protection algorithms, it is set using the function set_mode_brutally().

After printing out the version information, the loop over the token stream starts. In the sample application it does not more than getting the a token using get_token() and printing it out. In a more realistic application this token is to be passed to a parser that does its syntactic analysis on it. When a token arrives with an identifier equal to` queχ::TKN_TERMINATION`, then the loop exits and the program terminates.

At this point in time everything is ready for compilation. Using the Makefile that came with the example, typing make shall produce a ready-to-run application called lexer in the current directory. If one types now

on the command line essentially the following output is produced:

This section has shown how to build a lexical analyser with queχ and provided a ready-to-run sample application. It was discussed how to specify patterns in a pattern file, how to announce names for token-identifiers and how to code mode-files that contain information about modes and pattern-action pairs. After an explanation of how to invoke queχ, a sample application was discussed that uses the created lexical analyser engine. The Makefile that comes with the example can be easily adapted to particular applications and reduces the required effort to the typing of make on the command line. In general, the example files simple.qx and lexer.cpp build a good basis for a new project. In the following chapters various features and options of queχ are discussed. Additionally some discussion will be made about the generated lexical analyser. The current chapter provided enough information to start coding a lexical analyzer. Following chapters become interesting once you have tasted the ease of queχ.

The last chapter provided a functioning example for the usage of queχ. At this point the user should have a clear idea about the basic concepts and how they are applied. This chapter discusses the details of usage and minor features that may not have been mentioned in the previous chapters. The first sections discuss the specification of patterns, mode characteristics, pattern-action pairs, and mode transitions. Section [sec-formal-generated-class] discusses the lexical analyser class that queχ creates with all members and member functions that the user might want to use.

In some cases, the provided functionality of the generated lexical analyser class might not be sufficient, so section [sec-formal-derivation] discusses the formalities to implement a derived class and its usage. The generated code contains some macro switches that allow to control the behavior of the analyser at compile time. Section [sec-formal-macros] discusses the usage of those macros. Finally, section [sec-formal-command-line-options] explains all command line arguments that can be passed to queχ.

Section [sec-practical-patterns] already discussed the format of the pattern file. In this section, it is described how to specify patterns by means of regular expressions. The regular expression syntax follows the scheme of what is usually called traditional UNIX syntax \cite{}, includes elements of extended POSIX regular expressions \cite{IEEE POSIX Standard 1003.2} and POSIX bracket expressions \cite{}. This facilitates the migration from and to other lexical analyzer generators and test environments. Additionally, queχ provides support for Unicode Propperties. A compliance to Unicode Regular Expressions \cite{Unicode 5.0 Technical Report Standard #18} is currently not targeted, though, because this expressive power is usually not required for compiler generation.

Nevertheless, queχ provides features that, for example, flex does not. If it is intended to maintain compatibility of regular expressions with flex, then please refer to the flex manual \cite{}, section Patterns and do not use queχ-specific constructs. This section discusses pure queχ syntax. The explanation is divided into the consideration of context-free expressions and context-dependent expressions.

Context free regular expressions match against an input independent on what come before or after it. For example the regular expression for will match against the letters f, o, and r independent if there was a whitespace or whatsoever before it or after it. This is the usual way to define patterns. More sophisticated techniques are explained in the subsequent section. This sections explains how to define simple chains of characters and operations to combine them into powerful patterns.

Chains of Characters

[: expression :] matches a set of characters that result from a character set expression expression. Section [formal/patterns/character-set-expressions] discusses this feature in detail. In particual [:alnum:], [:alpha:] and the like are the character sets as defined as POSIX bracket expressions.

Any character specified as character code, i.e. using \, \x, \X, or \U are considered to be unicode code points. For applications in english spoken cultures this is identical to the ASCII encoding. For details about unicode [sec-formal-ucs-properties] is dedicated to an introduction to Unicode properties.

Two special rules have to appear isolatedly, out of the context of regular expressions. With the following two rules the actions for the event of end of file and the failure event can be specified:

This syntax is more in recognition of the traditional lex syntax. In fact the two event handlers on_failure and on_end_of_stream are a one-to-one correspondance to what is mentioned above. Possibly some later versions will totally dismiss the lex related engine core, and then also these constructs will disappear in favor of the mentioned two event handlers.

Operations

Let R and S be regular expressions, i.e. a chain of characters specified in the way mentioned above, or a regular expression as a result from the operations below. Much of the syntax is directly based on POSIX extended regular expressions \cite{}.

Character set expression are a tool to combine, filter and or select character ranges conviniently. The result of a character set expression is a set of characters. Such a set of characters can then be used to express that any of them can occur at a given position of the input stream. The character set expression [:alpha:], for example matches all characters that are letters, i.e. anything from a to z and A to Z. It belongs to the POSIX bracket expressions which are explained below. Further, this section explains how sets can be generated from other sets via the operations union, intersection, difference, and inverse.

POSIX bracket expressions are basically shortcuts for some more regular expressions that would formally look a bit more clumpsy. Queχ provides those expressions bracketed in [: and :] brackets. They are specified in the table below.

Caution has to be taken if these expressions are used for non-english languages. They are solely concerned with the ASCII character set. For more sophisticated property processing it is advisable to use Unicode property expressions as explained in section [formal/ucs-properties]. In particular,

The use of Unicode character set potentially implies the handling of many different properties and character sets. For convinience, queχ provides operations on character sets to combine and filter different character sets and create new adapted ones. The basic operations that queχ allows are displayed in the following table:

Note, that the difference and intersection operation can be used convienently to filter different sets. For example

results in the set of greek characters except the digits. To allow only the numbers from the arabic code block intersection can be used as follows:

The subsequent section elaborates on the concept of Unicode properties.

Unicode is distinguished from other coding standards not only with respect to its level of completeness including all possibly used character sets. Moreover, much effort has been accomplished in categorizing characters, providing terminology for concepts related to letter systems and defining character properties. Unicode defines a fixed set of properties that a character can have. The most important property for a lexical analyzer is the code point, i.e. the integer value that represents a character. However, there are other interesting properties that simplify the description of regular expressions.

Queχ supports Unicode Standard Properties through the \P{..} expressions, where the P stands for property. For a queχ user properties can be devided into two categories:

Note, that the result of a \P{...} expression is always a set of characters. Therefore, it cannot be used inside a quotes string expression. For convinience, the properties Name and General_Category are provided through the shortcuts \N{…} and \G{…}. Thus, \N{MIDDLE DOT} is a shorthand for \PUppercase_Letter.

Unicode 5.0 provides more than 17000 character names, so please consult the standard literature for settings of the Name property
[Alternatively, consider the file UnicodeData.txt that comes with the queχ application]
. Note also, that names as defined in Unicode 1.0 can be accessed through the Unicode_1_Name property. This property also contains names of control functions according to ISO 6429 \cite{}.

As for the General_Category property, the appendix provides the list of possible settings [sec-appendix-property-general-category]. At this place, more detailed information is specified about provided properties, their meaning, and settings of other likely-to-be-used properties.

When starting to write lexical analyzers using a wider range of unicode characters the reliance on properties becomes almost unavoidable. However, the huge volume of characters requires some sophisticated tool to browse through properties and related character sets. For this purpose queχ provides a query mode. This mode allows the user to specify some queries on the command line and get the response immediately on the console. This subject is handled in section [sec-query-intro].

As an option to facilitate the specification of property values, queχ allows you to use wildcards *, ? and simple character sets such as as [AEIOUX-Z] for the characters A, E, I, O, U, X, Y, and Z. If the first character is an ! then the inverse character set is considered. This is conform with unix file name matching. set specifications such as [a-z] such to facilitate the search. It is advisable, though, to use queχ's query functionality first [sec-query-intro] in order to get an impression to what value such a wild-card expression expands.

The most dangerous pitfall is related to precedence and length. Note, that a pattern that is defined {it before} another pattern has a higher precedence. Also, if a pattern can match a longer chain of characters it wins. Thus, if there are for example two patterns

then the keyword PRINT will never be matched. This is so, because [A-Z] matches also the character chain PRINT and has a higher precedence, because it is defined first. To illustrate the danger of greedy matching, i.e. the fact that length matters, let two patterns be defined as:

Now, the Else statement may be matched, but only if it is not followed by tabulator and Augenstein. On the first glance, this case does not seem to be very probable. Sometimes it may be necessary, though, to define delimiters to avoid such confusion. In the very large majority of cases greedy matching is a convienient blessing. Imagine the problem with identifiers, i.e. any chain of alphabetic characters, and a keyword for. If there was no greedy matching (longest match), then any variable starting with for could not propperly be detected, since the first three letters would result in the for-keyword token.

Another pitfall is related to character codes that the lexical analyser uses to indicate begin-of-file, end-of-file, or buffer-limit. The values for those codes are chosen to be out of the range for sound regular expressions parsing human written text (0x0 for buffer-limit, 0x1A for end-of-file, and 0x19 for begin-of-file). If it is intended to parse binary files, and these values are supposes to occur in patterns, then these codes need to be changed. Section [sec-formal-command-line-options] mentions how to specify their codes on the command line.

Additionally to the specification of the pattern to be matched queχ allows to define conditions on the boundary of the pattern. This happens through pre- and post-conditions. First, the trivial pre- and post-conditions for begin of line and end of line are discussed. Then it is shown how to specify whole regular expressions to express conditions on the surroundings of the pattern to be matched. The traditional characters to condition begin and end of line are:

For more sophisticated case real regular expressions can be defined to handle pre- and post-conditions. Note, that pre- and post-conditions can only appear at the front and rear of the core pattern. Let R be the core regular expression, Q the regular expression of the pre-condition, and S the regular expression for the post-condition.

A somehow subtle pitfall is related to the begin-of-line pre-condition. When using the ^ sign at the beginning of a line it is tempting to sing "don't worry, be happy … this matches at any begin of line"—well, it does not! The important thing to understand is that it matches when the lexical analysis step starts at the beginning of a line. The alarm signal should ring if begin-of-line is triggered and a whitespace pattern is defined that includes newline. Consider the following patterns being defined:

Where the hello greeting is to be matched after newline and some possible whitespace. Now, given the character stream:

will not send a GREETING token. This is because the whitespace pattern eats the newline before the hello-line and even the whitespace before hello. Now, the next analysis step starts right before hello and this is not the beginning of a line. Splitting the whitespace eater into newline and non-newline helps:

Now, the first whitespace eating ends right before newline, then the second whitespace eating ends after newline, and the hello-greeting at the beginning of the line can be matched.

Another pitfall is, again, related to precedence. Make sure that if there are two patterns with the same core pattern R, then the pre- or post-conditioned patterns must be defined before the un-conditioned pattern. Otherwise, the pre- or post-conditioned patterns may never match. Recall section \ref{formal/patterns/context-free-pitfalls} for a detailed discussion on precedence pitfalls.

In most practical applications it is not a good idea to start in a void initial mode, so queχ requires an initial mode explicitly to be specified. This happens using the start keyword, i.e. one has to type somewhere in between the mode definitions (but best at the very beginning):

Let the mode-stubs be stored in a file called simple.qx. The previous sections defined patterns, token-ids, and modes. Together with these definitions one can now start with the specification of pattern-action pairs as discussed in the following section.

Queχ allows to specify characteristics of modes concerning transitions and inheritance. The keyword mode starts the definition of a lexical analyser mode. Then it can be directly followed by a curly bracket that starts the pattern-action pair definitions as shown in figure style=refa. This is the most simple way to define a mode.

a)

b)

c)

In order to define options or base modes the name of the mode has to be followed by a colon as in the examples in figure <<:formal-mode-definition, style=ref>>b and \ref{fig-formal-mode-definition, style=ref>>c. Note, that if a mode specifies base modes and options, the options are specified after the base modes.

Base modes directly follow the : sign. The list of base modes is whitespace separated. When the first $<$ sign arrives, queχ starts reading the options. Options are bracketed by $<$ and $>$ signs and multiple options are also listed whitespace separatedly. The following options can be specified:

Options are optional, i.e. they do not need to be specified. But, they facilitate the debugging and add confidence that the mode transitions are safe and sound. The list of options is then to be followed by an opening curly bracket { that opens the list of pattern-action pairs. These are discussed in the following section.

Queχ only allows to specify pattern-action pairs inside modes. As the name says, a pattern-action pair consists of a pattern that is to be matched and a code fragment that is executed when the pattern matches. Patterns are best specified inside the pattern definition sections, so that inside the mode sections only names of patterns occur. However, one can also use regular expressions inside the mode definitions. The format for pattern-action pairs is as simple as can be:

Examples for pattern-action pairs have been given enough in section [sec-practical-pattern-action-pairs], page There are a few important variables to know for coding the action for a pattern match:

In practical applications for programming languages, the large majority of patterns to be identified are simple and do not require large algorithms to handle them. Keywords, such as if, then, and foreach, operators, such as $+$ and * and delimiters such as ;, ( and )`' simply need to send a token telling that such and such appeared. Their pattern action pairs all look similar to the following:

Queχ allows to write such simple token sendings in a more elegant manner. If a pattern is followed by a ⇒ operator and a name xyz then this is translated into pattern sends token with name xyz. The code as shown above will be internally generated. The above code segment is equivalent to the following:

For simple patterns that consist of a fixed string and that appear only in one place it does not make sense to define a pattern explicitly. They can also be given directly, i.e. one can write

thus avoiding long lists of pattern definitions external to the mode definition. Sometimes, though, things are little more complicated. It might be necessary to extract some of the information in the lexeme and store it into the token as in the following pattern action pairs:

In these cases, one passes arguments to the send function other then the token-id. In order to specify additional arguments to the send functions the token-ids have to be followed by a pair of brackets containing the list of arguments (possibly separated by comma). This way, the above two pattern action pairs can be rewritten elegantly as:

These abbreviations not only speed up the generation of a lexical analyser tremendously, but they make the lexical analyser descriptions also very readable. Long lists of pattern-action pairs can be understood and analysed in a few seconds.

Note, that if an identifier is used that is not declared in a token-section, then queχ implicitly declares this token, but still a warning is reported. In order to get things setup quickly, it is possible to complete renounce on token sections. However, for a good style the output of these warnings might be pasted into one of the token-sections.

For a given character stream it might be possible that more than one pattern matches. Therefore, rules are needed that describe the resolution of those conflicts. This section explains the priorities that queχ assigns to a given set of patterns based on length, position, inheritance relationships, and a possible priority-mark. Imagine, two patterns:

both patterns "print" and "printer" match the first five characters of a character stream print…. The first pattern could match, but what if the stream continuous with …er? It would never be possible to match an incoming printer because the first pattern eats the first five characters and the remaining er is lost in space. Thus, the rule, followed by most lexical analysers: The pattern with the longest match proceeds! Still, there might be more than one pattern that matches the same number of characters, e.g. the two patterns

match in a character stream print exactly five characters. How can be decided wether to vote for a keyword or an identifier? The rule here is: first come, first serve_ — patterns that are mentioned first in the code win!. If a pattern in a base mode and a pattern in a derived mode match with the same number of characters, than the base mode' pattern proceeds!. This follows the philosophie that the base mode imposes behavior on the derived modes. Figure style=ref shows how a pattern is matched in case of multiple patterns matching the current character input stream.

With respect to pre- and post-conditioned patterns, the rules remain the same. However, some things need to be clarified. For a pre-conditioned pattern Q/R/ the string matching the pre-condition Q does not contribute to the length of the pattern match. For a post-conditioned pattern R/S the matching characters of the post-condition S do contribute to the length of the pattern match. Note, that the last rule is, on the first glance, counter-intuitive to the fact that the Lexeme variable in a post-conditioned pattern match action contains only the length of the core pattern and not the length of the post-condition. There is a rational, though, behind this distinction:

For cases of real urgency, a keyword allows to struck the ruleset of pattern-action dispatching: PRIORITY-MARK. A pattern followed by this keyword is lifted into the current mode, thus having the priority according to the position in the current mode not of the base mode. This requires, of course, for the pattern to be defined before. For example:

When the lexical analyser is in the my_derived mode, then print is always recognized as an identifier and never as keyword. However, if the PRIORITY-MARK is set as in the following code fragment,

then the [a-z]+ pattern has a priority of a pattern in the mode my_derived _after_ the pattern "print". The action related to the [a-z]+ pattern, though, remains. An incoming print character stream is now always recognized as keyword. It cannot be overemphasized, that using priority marks allow derived modes to act against the concepts of the base modes. Thus a mode B may be derived from mode A, i.e. is-a mode A, but it behaves different! Priority marks are indecent and a sign of a bad design!

Priority marks can be avoided by splitting the base mode A into two modes A0 and A1, one containing desired patterns and the undesired patterns. Figure style=ref shows this idea. The original mode can be achieved by derivation from A0 and A1. The mode B can derive from the base mode of desired patterns. This is the clean way to avoid that undesired base class patterns have to high priority —use PRIORITY-MARK in case of laziness.

Queχ provides a special event is executed at the moment any match is executed. This allows the user to do some things—for example for debugging purposes—at any pattern match. The event handler name to do this is on_match. The code fragment that follows this name is considered to be the action which is executed before any match action is executed. Every mode has its own on_match event handler. However, these event handlers can be inherited in the same way as on_exit and on_entry are inherited.

The event handler receives the two arguments Lexeme, the pointer to the first character of the lexeme and LexemeL, i.e. the length of the lexeme that was matched. The following shows an example, where the user wants to do some statistics on the number of matches, the number of backslashes and the total length that was matched in the mode CORE.

There are exactly two events that are related to mode transitions: entering and exiting. Accordingly, one can define inside a mode the two handlers` on_entry` and on_exit. In addition to the self reference, the following variables are available:

The on_exit function of the mode that is left is always called before the on_entry function of the mode that is entered. Note, that it does not make sense inside transitions to use the RETURN statement since at this point the token-queue is not to be synchronized with a user's token request. Examples for enter and exit handlers have been given in section [sec-practical-pattern-action-pairs].

Note, that initiating explicitly mode transition inside on_exit {t will cause} an infinite recursion! If this is intended the mode transition mechanism should be circumvented using the member function` set_mode_\-brutally(). Note also, that initiating an explicit mode transition inside `on_entry _can cause_ an infinit recursion, if one initiates a transit into the entered mode. Certainly, such a mode transition does not make sense. In general, mode transitions inside on_entry or on_exit event handlers are best avoided. Consider the code fragment

meaning that one desires to enter MY_MODE_B if pattern` P_SOMETHING` is detected. Imagine, now, because of some twisted mode transitions in the transition event handlers one ends up in a mode` MY_MODE_K`! Not to mention the chain of mode transition event handler calls - such a design makes it hard to conclude from written code to the functionality that it implements. To repeat it: _explicit mode transitions inside on_entry and on_exit are best avoided!_

One might recall how uncomfortable one would feel if one mounts a train in Munich, leading to Cologne, and because of some redirections the trains ends up in Warsaw or in Moscow. In a same way that train companies should better not do this to theirs customers, a programmer should not do to himself mode transitions inside on_entry and on_exit.

Another issue has to do with optimization. Queχ is aware of transition handlers being implemented or not. If no transition handlers are implemented at all then no event handling code is executed. Note, that each entry and exit transition handler requires a dereferecing and a function call—even if the function itself is empty. For fine tuning of speed it is advisable to use only entry handlers or only exit handlers. The gain in computation time can be computed simply as: probability of mode swith times time for dereferencing and empty function call over two. For reasonable languages (probability of mode change < 1 / 25 characters) consider the speed gain in a range of less than 2%. The derefencing, though, can come costy if the mode change is seldom enough that is causes a cache-miss. Thus, for compilers that compile large fragments of code, this optimization should be considered.

Additionally to the on_entry and on_exit event there is an event for the first non-whitespace character that appears in a line: on_indentation. In order to trigger this event a dedicated process keeps track of newlines and whitespace that follows it. This process happens virtually in paralell to pattern matching. It knows to states:

At the beginning of lexical analysis, or at the beginning of a line the lexical analyser is in state 1. When the first non-whitespace character appears in a line it enters state 2. The transition from state 1 to state 2, i.e. the appearance of the first non-whitespace character in a line triggers the indentation event and the correspondent event handler is called. The transition from state 2 to state 1 and state 1 to state 2 can also appear inside one single matched pattern
[Imagine, for example a pattern [ \n]
+$$ that matches newlines and whitespace.].

This event handler is called right before the pattern action is executed that belongs to the matched pattern. Inside the event handler, in addition to the self reference, the following variable is available:

Note, that the indentation event can be disabled, but only for single event. Using the member function

disables the indentation event for the next time. However, after the next prevented indentation handling it is enabled again. This comes handy if one needs to have a line-prolonger, such as a backslash in python and many shell script languages, or the underscore in VisualBasic. The following mode action pair would prevent the subsequent line to be considered for indentation handling:

If the subsequent line, though, does not end with a backslash the event handler is automatically active and indentation handling is in place.

Queχ generates a C++ class that implements a lexical analyser as specified by the user. This section discusses the class members and member functions with which the user may interacts. Section [sec-formal-generated-class-ui] discusses the usage of the lexical analyser from outside, i.e. how the end user of the engine is going to create a lexical analyser and how a character stream is transformed into a token stream. The subsequent sections discuss how modes can be handled using member functions, token handling, the_ accumulator_, and some virtual functions to be possibly overriden by a derived class. Any member function can theoretically be used in any context
[This is, of course, only true as long as acces rights of` private` or public do not forbid it.]
.

Before the lexical analyser can be used, one has to create an instance of it. Assuming that the_lexer is the name of the lexical analyser engine (see command line option —engine) the following two constructors are provided:

The first constructor accepts an input stream of any kind and an optional output stream for unmatched characters. The second constructor directly accepts a filename instead of a stream. The stream or the filename act as the root-file for the lexical analysis. The lexical analyser is now ready to run. Tokens are received by calling the member function

It initiates a lexical analyser process and fills the object at` result_p` with the next token. Internally, tokens may be stacked and not every call to get_token() initiates an analysis. But the user does not care. He simply receives a sequence of tokens through this function until a token arrives with the the token-id

Note, that TKN_ represents the token prefix. If the user decides to modify the token prefix to TOK_, for example, the identifier for termination is TOK_TERMINATION. Note, that the default action on failure also sends this identifier, so that no second check at the end of the analyzing loop is required. This id is by default defined as zero, because also many parsers require that. This id tells that the input has been totally treated and no further token will arrive. In order to keep track of different versions of generated lexers the member function

returns a string telling about the version (see also command line option` —version`), and the date when queχ produced the engine. The current line and column numbers can be accessed using the functions

where the *_number() functions return the information where the last pattern started, and the *_index() functions return the information where the last pattern ended.

From the given set of modes, queχ creates a set of mode-information objects as members of the lexical analyser class. The names of the members are exactly the same names as the names of the modes. In the example of the last section, the following three objects are members of the class tiny_lexer:

The three classes END_OF_FILE_tag, STRING_READER_tag, and PROGRAM_tag are all derived from class queχ_mode. Thus pointers and references to them can do the job, whenever a pointer to a` queχ_mode` can. The lexical analyser class provides the following functions to access information about the current mode.

The first function returns a reference to the mode-information object that represents the current mode. The second returns a string with the name of the current mode. Those member functions shall be accessed using the self member, i.e. for example

The third function mode_id() returns a mode-identifier, i.e. an integer value that is unique for the current mode. This identifier was historically used by the flex generated engine under the hood. Since version 0.10.0 queχ produces its own engine and does not rely on flex anymore. However, these ids might still be useful for administration of modes, or for tagging of tokens. The mode-ids can be mapped to mode objects using the member functions:

A direct transition to another mode is initiated through the $<$$<$-operator or the function enter_mode(), i.e.

The operators return void deliberately because mode transitions are not thought to be done in concatination without pattern matching. If so, one can still write multiple mode transitions in a row. In any case of the three above the following three steps are guaranteed:

Additionally to direct mode transitions modes can be pushed and popped similar to subroutine calls (without arguments). This is provided by the functions:

The member function push_mode(new_mode) pushed the current mode on a last-in-first-out stack and set the new_mode as the current mode. A call to pop_mode() pops the last mode from the stack and sets it as the current mode. Note, that the mode transitions with push and pop follow the same mode transition procedure as for entering a mode directly. This means, that the on_exit and on_entry handler of the source and target mode are called. The function pop_drop_mode() pops a mode from the mode-stack, but does not set it as current mode. It is rather dropped and forgotten.

If one wants to avoid the call of exit and enter event handlers, then modes can also set brutally using the member functions:

Using these functions only the current mode is adapted, but no event handlers are called. This also means that mode transition control is turned off. Inadmissible transitions triggered with these functions cannot be detected during run-time.

Modes themselves are implemented as objects of classes which are derived from the base class queχ_mode. Those mode objects have member functions that provide information about the modes and possible transitions:

The first three member functions allow to get information about the relation to other modes. If the flag PringErrorMsgF is set than the function will print an error message to the standard error output in case that the condition is not matched. This comes very handy when using these functions in assert`s or during debugging. The functions can be applied on a given mode object or inside the `on_entry and on_exit functions with the this pointer. In a pattern action pair, for example, one might write

For the end-user these functions are not really relevant, since queχ itself introduces `assert`s on mode transitions and provides convienient member functions in the lexical analyser class to access information about the current mode.

Section [sec-basics-token-queue] elaborated on the idea that the lexical analyser communicates tokens to the user. In the queχ generated lexical analyser the tokens are stored in a token-queue before they are delivered to the caller of get_token(). Inside the pattern-action the send function group allows to send tokens:

As mentioned before, the author of queχ is in favor for the idea that the lexical analyzer should only find out for what a string in the input stream stands for. It should not interpret it, but leave the interpretation to the user or the parser.

Figure style=ref, displayed a sequence diagram depicting the communication of tokens. Using the send function group the writer of pattern-action pairs does not need to care about the get_token() function call. He sends tokens and leaves the responsibility of delivery to the engine.

The accumulator is a member that allows stock strings to communicate between pattern-actions. In the practical example in section [sec-practical-intro] the string contained in string delimiter marks was accumulated until the on_exit handler was activated, i.e. the` STRING_READER` mode is left. Inside the handler, the string is flushed into a token with a specific id TKN_STRING. The accumulator provides the following functions:

The add-functions add a string or a character to the accumulated string, the flush() function sends a token with the accumulated string and the specified token-id. Finally, the clear() function clears the accumulated string without sending any token.

Instead of deriving a class from the lexical analyser, it is sometimes more convenient to simply paste some more content into the class body. This can be done using the keyword body outside the mode definitions. The following code, for example, pastes the definition of an integer vector into the class' body, so that it can later be used to keep track of indentation columns.

Note, that the namespace prefix std:: is used. This is because the class definition's body appears inside a header file and in header files one better uses absolute namings, rather than abbreviating using namespaces. The newly defined member can then be used inside any pattern action or event handler via access of the self reference, e.g.

The last section discussed how additional contents can be pasted into the defintion of the class' body that represents the lexical analyser. Naturally, those new contents need to be initialized. This happens inside the constructor of the generated lexical analyser. Queχ allows to specify additional content to be executed inside the constructor using the init keyword outside any mode definition. The following code fragment shows a setup as it might occur in a lexical analyser that supports indentation based statement blocks:

The body fragment adds an indentation stack as a member to keep track of line indentations. A second member variable tells if a higher indentation is supposed to appear that opens a statement block. These two variables need to be initialized. Therefore, the init fragment contains an initial block starting at column 0. This indentation block cannot be closed (except by end-of-file) because no column can have a negative indentation. Also, by default open sub-blocks is disallowed, so the correspondent member variable is set to false. This code fragment will then appear in any constructor of the generated lexical analyser class.

Many programming languages provide an include feature. This means that they allow the user to get some input from another file and then returning to the file itself. If in C one specifies stdio.h to be included, then the content of this file will be treated before one continues parsing the current file. Such features are popular and provide a lot of convenience to the user. In a more general sense, what happens is that the input stream changes and needs to return after the alternative input has finished. This sounds like a case for the memento pattern \cite{} where the state of the lexical analyzer needs to be stored and restored---and it is.

The decision of what information about the lexical analyzer is to be stored during a input channel change, i.e. an include is not left to the user. The generated analyzer class provides the user with handy functions that do the whole job. Those are the following:

The functions can be grouped according to two actions: pushing the current state of the lexical analyzer on an include stack and popping the last pushed state of the lexical analyzer from the include stack. The overloaded functions include_stack_push(…) require as a first argument a FILE* or an istream* pointer of the stream which is supposed to be the new input stream. The analyzer then automatically creates a new buffer object and sets everything up for the input from the new stream. Also, the current state is stored in a stack. If the program feels that is has finished parsing an _included file_\footnote{This happens usually on the occasion of end of file.} then it may want to return to the including file. The reset of the old state is now easily possible using the function include_stack_pop(). It _deletes_ the buffer of the included file, but it does not delete the related input stream. If there is something to do with it, it has to be done before calling include_stack_pop(). In particular, it is generally a good idea to close the file stream when reading has finished.

Traditional lexical analyzer generators concentrate on the ASCII \cite{} character set for the encoding of characters. With the rise of UTF-8 \cite{} those generators could even be used to parse unicode character sets, since they were unaware of escape characters. The problem with this approach is a lack of flexibility. UTF-8 is for most languages, i.e. unicode code pages, a highly redundant coding. Second the UTF-8 standard (ISO-10646) is a dynamic length coding where characters are coded with different numbers of bytes. Counting of columns or lexeme lengthes is no longer trivial and is prone to consume significant computation time. For example, for lex the definition of character ranges such as [a-z], for non-latin languages, is not possible because it considers only the two bytes around the - where the characters might actually be represented by more than one byte.

Under Unix, a utility called iconv \cite{} is the quasi standard for character set conversions. It is freely available for any major operating system. Queχ uses the library of this utility and has it webbed into its buffer handling. This way queχ is able to analyze character streams of all the hundreds of character encodings that iconv supports. It is essential to understand that there are three different places where character encodings are involved in the lexical analyzer generation. As shown in figure [fig-character-encodings] these are the following:

There only three things required to get the encoding support for a particular coding. First one needs to make sure that the queχ files, i.e. the files that describe the lexical analyzer are stored in UTF-8 format by your editor. Most editors do this anyway by default. You need to pass the option --iconv to queχ when calling it. Third, the constructor of queχ is to be called with the encoding name of the files you want to parse, i.e. one might type

if one intends to create a purely greek programming language. If you set the command line option for byte per character -b wchar_t, then queχ will use the number of bytes that corresponds to wchar_t on your platform. For anything other than ASCII input encodings do not specify a byte per character less than two. At the time of this writing queχ does not support internal engines that are not based on Unicode. Clearly, in the above example the greek encoding is treated internally as character codes in the range of code points from \$370 to \$3FF and \$1F00 to \$1FFF.

It is sometimes necessary to provide header file information or macro definitions to the pattern-action pairs or event handlers. To do this queχ allows to specify a header. This keyword has to appear outside any mode definition. It is followed by an opening curly bracket, the code to be pasted and a matching closing curly bracket.

The class generated by queχ implements an engine for lexical analysis with some basic functionality as was discussed in the previous sections. Sometimes, though, it is necessary to add features to the lexical analyser. Especially, adding event handlers for file inclusion and pattern matching requires overiding virtual functions of the engine. Adding new features while keeping basic functionality is best done using C++ inheritance, i.e. one derives his own class from the generated lexer class.

The name and definition of this class needs to be known for the creation of the lexical analyser. Thus, one has to specify the command line option` —derived-class` followed by the name of the class and` —derived-class-file` followed by the name of the file that contains the definition of the derived class. The derivation itself happens in the standard C++ way, i.e. one derives publicly from the lexical analyser class:

Note that the derived class has to call a base class' constructor from inside its constructor initialization list in order to properly initialize the lexical analyser object.

If these caveats are taken care of, the user is free to create objects of his derived class and use it the same way as he used the previous plain generated class.

Queχ provides a default token class that allows the storage of a string object, an int value. Note, that any complex structure might be transformed later on by the parser based on the given string. In some cases, though, it may be promising to implement a dedicated token class that is optimal in memory and speed with respect to a specific problem. For these cases, queχ allows the user to specify his own token class. The token queue does not require any adaption, since it is implemented as a template. The context of usages of tokens, however, imposes that it complies to some policies:

As long as these conventions are respected the user created token class will interoperate with the framework smoothly. The inner structure of the token class can be freely implemented according to the programmer's optimization concepts. Note, that the name of the token class is also of free choice. When invoquing queχ, the command line option —token-class needs to be followed by the user defined token class name. The command line option —token-class-file tells queχ the name of the file where this class is defined. As long as this options are not defined queχ will not consider user defined token classes and provide the standard token class.

Previous chapters and sections introduced different code sections where patterns, token identifier, modes, and engine code could be specified. The following table summarizes these section in order to serve as an overview. It associates the code section's keyword with its content and the section and page reference of its explanation.

For convenience, even though it is not a region, let it be mentioned here, that the assignment

defines the starting mode of the lexical analyzer. If no starting mode is explicitly defined queχ assumes the first mode defined in the source code as starting mode and produces a warning if the console.

When queχ creates a lexical analyser it leaves some switches in the code that can be turned on and off in order to control certain charactersistics. First of all, queχ makes heavy use of`assert`s to make sure that the code is executed appropriately. These asserts can be turned off by defining the`NDEBUG` macro. The following macros are queχ specific and can be specified with the -D option of your compiler:

The specification of character sets based on properties and character set operations requires in general some closer inspection in order to avoid the inclusion of unwanted characters or to span a character set that is wider than actually intended. Consider for example that one might want to provide a programming language that allows Latin and Greek letters in identifiers. The direct approach would be as follows:

This specification is totally rational. However, it might include more characters than one actually intended. If one mentions Greek and Latin characters one usually thinks about lower and upper case letters from a to z and α to ω. However, the set of characters that are included in Script=Latin is much larger than that—and so is the set of characters in Script=Greek. Figure [fig-screenshot-character-set-query] displays the set of characters for the character set specified by GREEK_ID_CONT.

As can be seen in the screenshot, the character set that is actually spanned by the expression is rather huge and exceeds the set of characters that can be displayed by the console of the user. At this point in time, one might have to use further intersection and difference operations in order to cut out the set that is actually desired. Also, consider not using the powerful tool of unicode properties, if things are expressed elegantly with traditions character set expressions. In the above case, a solution that likely fulfills the user's purpose might look like this:

Including other scripts, or enabling other features of a used language requires closer investigation of the unicode properties. Queχ provides some powerful services to investigate the effect of a character set expression on the command line. Sophisticated programming language design on a non-latin language, though, requires some review of the literature of UCS based character sets and their characteristics. This chapter shows how queχ can be used to query the unicode database and see the effect of character set expressions immediately, without having to compile a whole lexical analyzer.

The first doubt that arises when properties are to be applied is whether the properties actually exists. The second doubt, then, is what values these properties can actually have. To help out with the first question, simply call queχ with the command line option —property and it prints a list of properties that it is able to extract from the unicode database. This leads to an output as follows:

Each line contains three fields separated by commas. The first field contains the alias for the property name, the second field contains the property name, and the last column contains the type of property. If a field containing <unsuported> is appended, this means that this property is not supported by queχ. In most cases this so because these properties support character operations rather then the definition of character sets.

To help out with the second question call queχ with the command line option —property followed by the name of the property that you want to know more about. The following displays the query about the property Numeric_Type:

This tells, that Numeric_Type is a property of type Enumerated, i.e. its values are taken from a fixed list of values. The alias nt can be used as a placeholder for Numeric_Type, and the possible value settings are Decimal, Digit, and Numeric. The strings mentioned in brackets are the value aliases that can be used as placeholders for the values, in case one does not want to type the whole name of the value. From this output one knows that expressions such as \P{Numeric_Type=Decimal}, \P{nt=Di}, and \P{Numeric_Type=Nu} are valid for this property. The next doubt that arises is about the character set that is actually spanned by such expressions. This is discussed in the subsequent section.

The specification of character sets using unit code properties requires caution and a precise vision of the results of character set operations. In order to allow to user to see results of character set operations, queχ provides a query mode where the character set corresponding to a specific property setting can be investigated. Additionally, whole character set expressions can be specified and queχ displays the set of characters that results from it.

In order to display the character set related to a unicode property setting, call queχ with the option —set-by-property followed by a string that specifies the setting in the same way as this is done in regular expressions with the \P{…} operation. Note, that binary properties have no value in the sense that they are specified in a manner as property-name=value. Instead, it is sufficient to give the name of the binary property and queχ displays all characters that have that property, e.g.

displays all characters that have the property ASCII_Hex_Digit, i.e.

For non-binary properties the value of the property has to be specified. For example, the set of characters where the property Block is equal to Ethiopic can be displayed by calling

and the result is displayed in figure [fig-screenshot-block-ethiopic.png]. Naturally, sets specified with a simple property setting are not precisely what the user desires. To apply complex operations of character set, queχ provides character set operations [sec-formal/patterns/operations]. Again, it is essential to know which character sets these expressions expand. Thus, queχ provides a function to investigate set expressions with the command line option —set-by-expression. The following call

Displays all characters that are numeric digits in the arabic script. Note that the display of characters on the screen is not always meaningful, so you might specify the option —numeric in order to display numeric values of the characters. The option —intervals prints out character intervals instead of each isolated character. This way output may become more brief and understandable.

Property value settings can be specified using wildcards as explained in [sec-formal/patterns/character-set]. Using the command line option —property-match allows the user to see to which values these wildcard expressions actually expand. For example, the call

delivers:

Note, that the final character sets spanned by these settings can be viewed using —set-by-property Name=MATH*FIVE* and —set-by-expression \N{MATH*FIVE*}$$` in the manner previously explained. For example,

delivers:

This section lists the command line options to control the behavior of the generated lexical analyzer. Numbers following these options can be either decimal, without any prefix, hexadecimal with a 0x prefix or octal with a 0o prefix.

For the support of derivation from the generated lexical analyzer class the following command line options can be used.

Additionally, there are options for specialists who want to provide their own token-class:

Even if a non-queχ token class is provided, the token-id generator may still be useful. By default, it remains in place. The user, however, can specify the following option to disable it:

There may be cases where the characters used to indicate buffer limit, end-of-stream and begin-of-stream need to be redefined, because the default code points appear in a pattern
[As for normal ASCII or Unicode based lexical analyzers, this would most probably not be a good design decision. But, when other, alien, non-unicode codings are to be used, this case is conceivable.]
. Also, note that the . regular expression (meaning nothing but newline or end of file) needs check for begin-of-buffer and end-of-buffer in the general case. Giving both the same value may come with some speedup, and does not hurt. None of these values should be equal to the buffer limit delimiter. The following options allow modification of the values discussed above.

If the trivial end-of-line pre-condition (i.e. the \$ at the end of a regular expression) is used, by default queχ produces code that runs on both Unix and DOS-like systems. Practically, this means that it matches against newline 0x0A and carriage return/newline 0x0D 0x0A. For the case that the resulting analyzer only runs on a Unix machine some tiny performance improvements might be achieved by disabling the 0x0D 0x0A sequence and only triggering on 0x0A. In this case, the following flag may be specified:

For unicode support it is essential to allow iconv support \cite{}. For this the iconv library must be installed on your system. On Unix systems this library is usually present. If a coding other than ASCII is required, specify the following options:

For version information pass option —version or -v. The options —help and -h are reserved for requesting a help text. Those are the options for using queχ in the 'normal mode where it creates lexical analyzers. However, queχ provides some services to query and test character sets. If one of those options is called, then queχ does not create a lexical analyzer but responds with some information requested by the user. Those options are the following.

Additionally, queχ provides the ability to display transition diagrams of produced state machines graphically. The following command line options support this feature:

Since version 0.21.11, queχ has had the ability to produce transition graphs for the state machines that result from the regular expressions of its modes. This happens with help of the tool graphviz from AT\&T Labs (http://www.graphviz.org). Please install this package before any attempt to produce transition graphs.

The plot of transition graphs is initiated with the command line argument —plot followed by a string that indicates the graphic format, e.g.

will produce transition graphs of all state machines that would result from descriptions in core.qx. As a result of this operation a set of files is created that carry the extension of the graphic format. The basenames of the files are related to the mode from which its content results. A list of supported graphic formats can be queried by passing the command line argument —plot-format-list.

This chapter focuses on the Unicode Character Properties as they are provied by queχ. The current version of Queχ is based on Unicode 5.0. It uses the databases as provided by the Unicode Consortium and it is likely that Queχ integrates the property system of any later standard as soon as it is in a major state. In particular, Unicode Character Properties are used to define sets of characters to be matched during lexical analysis. This excludes some properties from consideration, namely the properties tagged as string property types and the quick-check properties (see [UCS#15]). The following properties are explicitly supported by queχ. The expressions in brackets are the aliases that can be used as a shorthand for the full name of the property.

Binary properties can simply be applied using the \P{…} expression. Thus, in usual programming languages.

This section elaborates on possible property settings for non-binary properties. In queχ's regular expression syntax they can be used using the \P{..} expressions. For example, \P{Age=3.1} selects the set of character that exists since Unicode Version 3.1. For reasons mentioned in the previous section some Unicode Character Code properties are not supported. Note also, that some settings can be provided using value aliases. Those aliases are specified in brackets.

The queχ program is provided in source code with an LPGL license in order to promote understanding of the processes of lexical analysis in its practical application. The source code may be used for teaching or to enhance the functionality or performance of the software. In order to allow programmers to get into queχ's source code programming, the following sections describe the way that queχ generates lexical analysers step by step. Clearly, this chapter is a hacker's guide to queχ. Users interested only in the application of queχ may skip this chapter without hesitation.

The generation of the core engine is separate from the handling of modes and their relationships. In the following sections, only the generation of the core engine, i.e. a lexical analyser for a single mode, is explained. Each mode consists of such an engine. The aggregation of engines for each mode to one single analyser engine is trivial and not the subject of further explanation\footnote{The switching between modes is not much more than the bending of a function pointer to the mode's analyzer function.}. For further support to get into programming, the unit tests for each sub-module in the source code may be considered. They can be found in the`./TEST/` sub-directory of each module.

The engine produced by queχ is a directly coded engine, rather than a table driven approach followed by the lex/flex family of analyzer generators. It is more suited to handling unicode and provides advantages in terms of system memory usage and calculation speed.

The following sections elaborate on the process of generating code for a directly coded lexical analyser. Each lexical analyzer mode consists of such an independent code fragment embedded into a function. In a first section, the big picture is discussed. This gives an overview about the major issues involved and builds a basis for later sections to refer to. Many books discuss in detail the Thomson-construction and the Hopcroft-Optimization, but few (the author does not know a single one) discuss the construction down to code-generation and its specialities in detail. Queχ was created to handle efficiently Unicode character sets. As a consequence the table-driven approach, such as in lex \cite{} is no longer suitable%% %% \footnote{In table driven analysers the table size is the square of the number of characters. Unicode provides currently \$10.FFFF code points. A table for this character set would blow the memory of todays computers (The century). Compressing the table might slow down the speed of the lexical analyser significantly.}. %% Thus, queχ implements a directly coded lexical analyser where no state variable is needed and no character-trigger table. It is also a much faster approach, since no memory has to be referenced%% %% \footnote{Note, that an expression such as vector$[$i$]$' implies generally a multiplication offset = i * sizeof(type)), an addition adress = vector + offset), and a memory referencing operation object = *adress).}. %%

In this section the overal lexical analyser is discussed. This is done before the detailed construction is dealt with in order to introduce the basic ideas that influence the creation of a lexical analyser. In particular concepts such as pattern privileges, pre- and post-conditions, as well as state origins are discussed at this point. The lexical analyser to be generated by queχ is a state machine. In this text the following notation for different states of a state machine is chosen:

Figure style=ref shows an example of three patterns to be matched against: A keyword WHILE, a label a character sequence terminated by a colon), and an identifier, i.e. a character sequence. An incoming character stream triggers step by step the transition in each of these state machines. Some may bail out. Other may reach the acceptance state. If one state machine reached the acceptance state, one can say that the pattern it represents has matched. For example a character sequence`H`,E`, R`,E, : lets state machine 0 fail at the first character, state machine 1 reaches acceptance at character :' and state machine 2 reaches acceptance one character before. Here an essential concept has to be mentioned:

\definition{ Longest Match: Queχ produces a lexical analyser that eats as many characters as possible. When a pattern can match more incoming characters than another, it dominates. }

This approach is very logical, since it was otherwise impossible to have a keyword End} and EndIf for example. If the shortest match wins, then always End is detected, but never EndIf. Practically in the example above this means that we do not stop when state machine 2 enters acceptance, but we give state machine 1 a chance match a longer pattern.

Now, consider the character sequence`W`,H,I,L`, E`,(. State machine 1 fails without ever entering acceptance at the last character. State machine 0 enters acceptance at the last`E`, and so does state machine 2. Both match the same amount of characters, but a lexical analyser can only report the detection of one pattern at a particular position in the character stream. There is no general logical rule here that can be applied to determine dominance of one pattern over the other. At this point the decision must be made by the user. Usually, this happens by sequence, i.e. the pattern that was defined first, matches in case of equal length\footnote{Note, that we are talking here on the state machine engine level. The rules for pattern precedence in derived modes as mentioned in section style=ref are actually translated into privilege rules on the engine level. The design of queχ is laid out in a way for using a database that maintains pattern-precedents. However, this has no practical advantage since base mode precendents can be expressed by the order that patterns are defined. This means, that pattern that are inherited from based modes simply have to be converted into state machines before the derived mode's patterns. This way it is guaranteed that the base mode's pattern state machines have lower ids and higher precedence.}.

The construction of a lexical analyser includes the construction of a single state machine that is equivalent to the bank of patterns which were shown in state machine which is the result of such a construction. In particular, this involves a construction of a deterministic finite automaton (DFA) from the pattern bank, which is a non-deterministic finite automaton (NFA). The pattern bank allows that the state machine is in multiple states at the same time, a DFA is only in one particular state at a particular time. The state machine that results from this operation is still to be optimized. A so called Hopcroft optimization \cite{} reduces the number of states to a minimum. The result in the aforementioned case is that the state machine of figure style=ref.

Queχ allows the definition of patterns that only trigger in a certain environment of characters. The ability to define borders of a pattern that are not part of the pattern itself is implemented by means of so called pre- and post-conditions. The following two subsections introduce these two

A post-condition is a condition on the character stream after the real pattern has matched. When the real pattern notifies a match at position X, the analyser needs to proceed in the character stream until it determines whether the subsequent characters match the post-condition. If the post-condition is met it reports acceptance---however, the lexical analyser's focus is put back to position X.

An example of a post-condition is shown in figure style=ref. The rule for this pattern is that when a number comes in that is followed by a currency, then it has to be reported as {it amount}, rather than a number. In this example there are two currencies: EUR for Euro and USD for US-Dollars. When a number is matched---with or without a floating point---then we reached the position to which we want to step back, if it was an {it amount}. These acceptance states have a dashed inner circle, to indicate that the input position has to be marked, but we're not finished yet. Only after one of the currencies EUR or USD appeared, finally, an acceptance state is reached. But, the following analysis needs to start at the position, backwards, where the number matched.

Figure style=ref displays the sequence of actions for an incoming character stream. When the 12 has matched as a number the input position 2 is stored but the analysis continues. When USD has matched it is now determined, that the previous number was indeed an amount. A token AMOUNT(12) can be reported. But, but one needs to go back to the position where the amount ended, i.e. to position 2. From there, it detects a currency USD and reports a token CURRENCY("USD"). The same thing happens now with the number 45.10 and the currency EUR in the remainder of the stream.

Post-conditions are implemented by setting a store-input-position mark at the states where the real pattern matches. The end of the post-condition is an acceptance state. Figure style=ref depicts the states of the amount/currency pattern webbed into a state machine that contains other patterns. The process of combining and optimizing the state machine needs to make sure that the information about saving input positions and acceptance states remains---here indicated as notes on a flag.

A Pre-Condition is a condition on the character stream before the pattern is actually being parsed. Starting from the current position X, the analyser needs to go backwards to check whether the pre-condition is met. After determining whether it is met or not, the real pattern is analysed starting from position X.

Intuitively, it does not make sense to try to match against a pattern if it is known from the beginning that the pre-condition is not met. For this reason, it is tempting to consider a single analyzer function for each case of pre-condition met and pre-condition not met. With this approach, though, the total number of analysers to deal with $N$ pre-conditions is $2^N$ since any combination of pre-condition met and pre-condition not met has to be considered. Just a few pre-conditions would then blow the number of analysers beyond what is practical. Queχ could not be a general solution for pre-conditions.

Rather than creating an analyser for each pre-condition combination, one single analyser containing all pre-conditioned and non-pre-conditioned patterns is created. Pre-conditions are simply implemented by a conditional acceptance at the end of the pattern, i.e.

When the analyser reaches the acceptance state of a pre-conditioned pattern it notifies a match only under the condition that the pre-condition flag was raised before. From one point of view, this is inefficient since in some cases the analyser tries to match against a pattern, even though the pre-condition disallows an acceptance. On the other hand, the states of the pre-conditioned patterns are webbed altogether into one single state machine and the overhead for doing so is minimal.

\TODO{It would be an improvement to allow the user to control when a pre-conditioned pattern combination is webbed into the combined state machine and when not.}

In detail, the process of generating a lexical analyser consists of the following steps:

- Code generation for the given combined state machine section [sec-inside-queχ-code-generation-core]. This consists of generation of code for:

The lexical analyser that queχ creates is based on regular expressions. In order to create state machines that represents regular expressions, it is necessary to provide operations that combine elementary regular expressions through concatenation, parallelization, optionality and_ repetition_. This section discusses how this is accomplished by means of the so called Thomson Construction \cite{}.

An essential concept is the so called $\epsilon$-transition. By means of this special transition state machines can be connected in sequence and in parallel. It builds a very basic concept in the Thomson construction for developing a state machine that represents a regular expression.

\definition{{bf An $\epsilon$-transition} is a transition that does not require any input. If a state A is connected with a state B via an $\epsilon$-transition, then entering state A implies that the state machine enters state B.}

In a sense, an $\epsilon$-transition behaves like a free-ride where no input character is necessary to trigger a subsequent state. However, those transitions imply that the state machine become non-deterministic, since it can now be in multiple states at the same time.

A very important principle which facilitated writing algorithms on state machines was that every state-id in every state machine is unique\/. That is, a state machine A cannot have a state-id that also appears in B. Further, state machines are mere collections of states. States are mere mappings that describe what subsequent state is reached by what trigger. Operations on state machines can then be applied by setting transitions, i.e. changing the mappings of states, and finally collecting all mappings (i.e. states) in a single state machine. The uniqueness of state-ids ensures consistency.

The following sections discuss the elementary operations on state machines that are necessary to describe regular expressions.

Mounting two state machines together in sequence is fairly simple. If state machine B is to be mounted after state machine A, then the following is to be done:

These steps imply that the acceptance state of the last state machine remains. In Queχ, an algorithm is implemented that does the sequentialization for any number of state machines---not just two---in one step. In figure style=ref a state machine is created representing a matcher for floating point numbers out of the sequentialized patterns [0-9]+, a dot ., and [0-9]+}.

In order to implement the logical or operation in regular expressions it must be possible to mount in parallel. Therefore, all acceptance states of the original state machines to be mounted in parallel need to remain acceptance states. All initial states need to remain initial states. However, there can be only one initial state. At this point the $\epsilon$-transition comes handy again. The following steps describe the process of mounting state machines in parallel:

Figure [fig-mount-parallel] shows the result of combining three state machines in parallel. By means of this procedure there is only one initial state and one terminal acceptance state for the state machine. Now, regular expression such as "hello"|"bonjour" can be implemented as two parallel state machines for "hello" and "bonjour".

Repetition must govern the following scenarios:

The first case`R$$*$$` is the so called Kleene-closure \cite{}. Again, by means of the $\epsilon$-transition this can be achieved by the following steps:

Figure style=ref shows the example of a Kleene-Closure for the pattern [A-Z]+":"}, which would match a C-style label. The other forms of repetitition are closely related to that. The one or arbitrary repetition R+ can be achieved by mounting the same state machine in front of the Kleene closure, ensuring that the pattern has to match at least once. Similarly minimum repetitions are achieved by mounting the state machines N times in front of the Kleene-Closure, where N is the minimum number of times the pattern has to be matched.

Where a maximum number M of repetitions is involved, one cannot rely on the Kleene Closure anymore. The state machines have to be mounted M-N times in sequence, where the acceptance states in between remain acceptance states. This way one can be sure that any number of matches from N to M corresponds to an acceptance state.

A special case is the case where zero and a maximum number of repetions are involved, i.e. R? and R{x,y} with x=0. In this case, simply the initial state is raised to an acceptance state, and then the usual algorithm for generating a maximum number of repetitions is applied.

The previous sections discussed how to generate a state machine for one isolated regular expression using the Thomson Construction. The final lexical analyzer, though, needs to have all possible patterns present, i.e. combined into an automaton in order to judge which pattern matches from the current input position. The approach that was chosen in queχ was to produce a single deterministic automaton from the set of state machines for each pattern. This process is described in the following sections.

It was already discussed that information about acceptance section [sec-basics-pattern-matching], storing of input position ssection [sec-inside-queχ-intro-post-conditions] and dependence on pre-conditions section [sec-inside-queχ-intro-pre-conditions] need to be stored as hidden state variables\cite{} inside the states of the isolated pattern state machines. This information needs to be maintained when the states dissolve into the super state machine that contains all patterns. This happens by labeling them with origin information.

As for acceptance, no special information carrier is required since the Thomson Construction and the Hopcroft Optimization treat them appropriately. A state in the super state machine has acceptance if one of its original states had acceptance and it does not have acceptance if none of its original states had acceptance. It remains to store information about which pattern has raised the acceptance in a particular acceptance state, i.e. some type of pattern-id.

Without post-conditions, an acceptance state stands for storing the input position. If the pattern that raised acceptance at this point wins, then the analyzer's focus must be set back to this position and the next analysis starts from this point. With post-conditions acceptance and storing the input position are no longer the same. When the core pattern has ended, the input position must be saved. But, at this point the state machine has not yet reached acceptance. It must first reach the end of the post condition. Then the input position can be put back to the end of the core pattern. Thus a flag is required telling wether or not it is required to store the input position.

The input positions for different post-conditions must be stored in different variables, since only at the end of the match can it be decided which pattern actually succeeded. A flag indicating that the original pattern was post-conditioned tells the code generator to use the pattern-id as the indicator for the variable storing the input positions.

The existence of pre-conditions imply the check at an acceptance state if a particular pre-condition has been met. Thus, a variable is required containing the pre-condition which has to be met in order to trigger acceptance. A special pre-condition is the begin-of-line pre-condition. It is a trivial pre-condition, since it does not involve an inverse state machine. Thus it is treated as a separate flag.

Inside Queχ, there is a data structure dedicated to store this information, called class`StateOriginInfo`. It contains the following fields:

\item [\tt state_machine_id] carries the id of the original state machine. This identifies the pattern to which the state belongs.

\item [\tt state_index] contains the index of the original state.

\item [\tt store_input_position_f()] gives information about the input position to be stored or not. In the table below referenced as {bf S}.

\item [\tt post_conditioned_acceptance_f()] indicates whether the origin of the state relates to a post condition. In the table below referenced as {bf post}.

\item [\tt pre_condition_id] indicates the id of the pre-condition that has to be fulfilled so that the acceptance of the state is valid. In the table below referenced as {bf pre}.

\item [\tt trivial_precondition_begin_of_line_f] indicates whether the pattern is supposed to start at the beginning of a line, i.e. after newline or the start of the buffer. In the table below referenced as {bf bol}.

Note, that there is nothing like a flag to indicate trivial post-condition end of line. This is for the simple reason that this trivial post condition is internally translated into a post-condition end of line or end of file. There is no mechanism that could gain some speed here. For the begin of line pre-condition though, one can rely on the last character that was considered.

A state in the super state machine contains a list of origins, each origin corresponds to an original state of the isolated patterns. The following table shows the possible combinations of these parameters together with the acceptance flag {bf AccF} of the state that may be labeled with these origins:

& {bf AccF} & {bf S} & {bf post} & {bf pre} & {bf bof} \\ \hline \hline %% normal acceptance state & must & yes & --- & --- & --- \\ \hline normal non-acceptance state & ? & --- & --- & --- & --- \\ \hline end of post-conditioned core & ? & yes & yes & --- & --- \pattern & & & & & \\ \hline end of post-condition & must & --- & yes & --- & --- \\ \hline acceptance of pre-conditioned & must & yes & --- & yes & no! \pattern & & & & & \\ \hline acceptance of begin-of-line & must & yes & --- & no! & --- \pre-conditioned pattern & & & & & \\ \hline

Note, that must for the acceptance flag means that the state in the final state machine that contains this origin has to be an acceptance state. The ? means that in the original state machine the state was not an acceptance state, thus the state that contains it together with others may or may not be an acceptance state. Note also, that pre-conditioned patterns and trivially pre-conditioned patterns are mutually exclusive.

In order to help get easy access to the origin's state type the member function type' returns direct information about the type of the original state, i.e. if it was a normal acceptance, a non-acceptance, a post-conditioned state (end of core pattern), an end of a post condition or a pre-conditioned acceptance state. In case the constitution does not lead to any valid interpretation, the function replies with an error. This would indicate that some functions do not work propperly. This allows for a double-check that all origins have passed the state machine construction properly.

The conversion of a non-deterministic finite automaton (NFA) to a deterministic finite automaton (DFA) brings the advantage that at a particular point in time the state machine is in one particular state---not in multiple states as with the NFA. This not only reduces complexity, but also decreases memory requirements (to store state indices and pattern match-management) and computation time of the resulting lexical analyser. The key to doing so is to combine states that the NFA takes simultaneously into a single state. Whenever a state in the NFA triggers on the same character to more than one state, the states that are reached by this trigger are combined into one single state. The process relies on two sub-processes described in this section: 1) construction of a so called epsilon closure, and 2) determining unique state combinations for the range of all triggers.

The core idea of this process is to find all possible super states of the NFA, i.e. the state combinations that can exist at a particular point in time. Then trigger sets have to be found that trigger the transition from one state combination to the other. The state combinations can then be renamed as a single state and it is sure that the resulting state machine is deterministic. By requesting that the acceptance state of a combined state is acceptance as soon as one of its member states is acceptance the entire mechanism of the NFA is preserved.

The notion of $\epsilon$-triggers enabled a very efficient method to sequentialize, parallelize and repeat state machines. As soon as a state machine contains an $\epsilon$-trigger it becomes a NFA. If a state A transits on an $\epsilon$ trigger to a state B, then the state machine is in state A {it and} B simultaneously as soon as A is reached, because an $\epsilon$-trigger does not require any input. This is one reason why the result of those operations is an NFA. In order to help with the $\epsilon$-transitions the $\epsilon$-closure is defined:

\definition{An {bf Epsilon Closure} of a state $n$ is the aggregation of all states that can be reached from $n$ via an epsilon transition.}

Consequently, when treating a state, one first collects all states that can immediately be reached via $\epsilon$-transition into a new state. This is shown in figure style=ref. This new state $n0$ contains all transitions of all states of the $\epsilon$-closure. It is supposed to be equivalent to the super state of the NFA which is in all of the states of the epsilon closure simultaneously. Note, however, even though state 23 in the figure is part of the $\epsilon$-closure, as a target state it is kept isolated referred to its maiden name rather then as part of $n0$ %% \footnote{From a super state point of view, state 23 which is reached through the recursion of itself, is not the same as the state 23 being entered from state 0. Also, $n0$ as being a super state does not belong to the same world as the original states.}.

The next step consists of finding state combinations and the trigger sets by which they are reached from the new state $n0$. Figure style=ref shows an example of a state $n0$ where some characters trigger to multiple states at the same time. This means that the state machine would be in more than one state at the same time, and can, therefore, not be a DFA. On the other hand, one can definitely say that {it one particular character} triggers {it one state combination}. Combining the states of each character trigger to a state combination, again allows the one-to-one (injective) mapping from a trigger to a state---and the conditions for a DFA are met. The search of a distinct trigger map consist of the following:

\definition{A {bf distinct trigger map} from a state $n$ is based on target state combinations that are reached by exactly the same trigger. A set of target states can be combined, if there is at least one common trigger (character code point) by which they are reached from state $n$. When all target state combinations are found, they can be renamed as single states, and the trigger map describes a one-to-one mapping from incoming characters to target states.}

Traditionally \cite{}, \cite{} the detection of suitable state combinations considers each single character of the trigger map isolated. This works fine as long as the code set does not exceed the oldtimer 8-bit ASCII character set. Each state in the NFA then requires 255 checks. For a Unicode-based lexical analyser this behaves significantly different. Unicode 5.0 currently has $10FFFF, i.e. decimal 1.114.111, code points — not to speak about code points for private usage. Consequently about 140.000 times checks would have to be performed for each state in the state machine. In order to avoid such a waste in calculation time, the author of queχ developed a different algorithm based on character ranges as shown in figure style=ref. The algorithm identifies state combinations which are related to certain overlapping ranges of characters.

As mentioned in [sec-character-range-representation], the queχ engine relies on a description of triggers in terms of number ranges. Instead of checking each character, the algorithm considers the numeric ranges R_{A,B} in which a state A triggers to state B. If a range R_{A,B} and R_{A,B} intersect, then B and C are states which are entered simultaneously in the NFA. Thus, they have to be combined in the DFA. For each set of target state combinations the intersection of all trigger ranges gives the range on what the combination is triggered. It can now be renamed, i.e. a new state can be created that is triggered based on any character that falls into the intersection.

The computation of intersections between all possible target states can also be simplified. Again, the line-up of the ranges on the time line comes handy (figure style=ref). This time line is implemented by begin-trigger-target-state and and-trigger-target-state commands that appear at certain code points. Finding intersecting ranges then consists only in walking down the timeline, adding and removing target states on any such command, and storing the intersecting domains together with the target state combinations. With this approach it is possible to compute most suitable lexical analyzers in the frame of few seconds on present day computing machines.

Now, that multiple states are combined into one state, the question remains about the acceptance type of the combined state? The answer becomes simple, though, considering that we try to match patterns and that a pattern match relates to an acceptance state:

The transformation from NFA to DFA is a process that is not only applied during the construction of state machines for isolated patterns, but also on the state machine that combines all patterns to be matched. In this case, the information about the origins all have to be kept. This includes the information about the original state. If a non-acceptance state from pattern X is combined with an acceptance state from pattern Y, we want to be sure, that the lexical analyser does not notify that X matched. A correct way to determine the winning pattern is to consider the origins that were acceptance states, determine the most privileged winner.

The following very important assumption has to hold for the process of converting a set of state machines, i.e. a NFA, into a single state machine, i.e. a DFA:

\definition{ Let $P_{a, b}$ be the set of paths from a state $A$ to a state $B$ in a state machine (constituting a parallel branch of the NFA). resulting DFA. For the DFA to uniquely represent the NFA, one must the original one, i.e. %% }

A direct consequence of this is that if a state X in a pattern can only be reached over a state Y, then in the resulting state machine this holds equally. The following algorithm demonstrates in pseudo-code the process of constructing a DFA that corresponds to an NFA. It can be applied for single patterns, as well as for the combined state machine that represents the lexical analyser.

In some cases, such as in the example shown in figure style=refa, the structure of a state machine can obviously be optimized. Note, that the sole task of the state machine is to determine if the sequence of characters appeared that matches a pattern. In this sense, there is no difference between all acceptance states. As a direct consequence, if there is a set of acceptance states, such as state 1, 2, and 3 in figure style=refa, where all characters trigger to another acceptance state, then those acceptance states can obviously be combined into a single one. This section concretizes this idea and develops the process known as the Hopcroft optimization.

{Combining equivalent states of a state machine.} image:figures/hopcroft-before.pdf]

An essential concept of the Hopcroft Optimization is the concept of_ equivalent states_. State machines are equivalent if all possible following sequences of triggers lead to the same result. Broken down to states, one requires for any two states A and B to be equivalent that all character streams that cause failure starting A will cause failure starting from B. Further, all character streams that cause acceptance starting from A cause {it equivalent acceptance} starting from B. Concretely, this means that for all possible triggers $t$, one requires that the follow-up state from A on $t$ is in the same state set than from B on $t$.

In the case of a single pattern, the set of states can be split up into two state sets that build the original worklist: the set of states that are acceptance states and those that are not. These two state sets are the initial worklist. For each state set X in the worklist one has to check wether it behaves abnormal, wether it triggers on a character $\alpha$ to a different set of states then the rest. Now, this state set is split into normal states $X_0$ and abornal states $X_1$. The state set X from the worklist is then replaced by the two state sets $X_0$ and $X_1$. This process can then be repeated until the worklist does not change anymore, i.e. no state sets have to be split up, because the represent equivalent states.

As long as one deals with a single isolated pattern things end up here. For isolated patterns, it only matters if a match occured or not. For the combined state machine, that represents the whole bank of patterns more information is to be considered. Such a case is depicted in figure style=ref. Two acceptance state that report different patterns as winner are not equivalent. Thus, the state set of initial equivalent acceptance states needs to be redefined. Note, that the remaining procedure remains the same — one only has to discuss the change of the initial set of equivalent acceptance states for the case that multiple origins are involved. Here, the term {it equivalent acceptance} has to be revisited.

\definition{As long as there are no origins involved, then two acceptance states are equivalent, if and only if — well — they are acceptance states.}

For the combined state machine, though, it is important to know what pattern, i.e. original state machine, actually reached acceptance, i.e. matched. It is possible that multiple patterns match at the same time. Thus, one has to concentrate on the dominating original pattern (see section

\definition{If a state machine contains origins, then two acceptance states are equivalent, if and only if their dominating original patterns are the same.}

Post conditions do not change anything at this setup, because the acceptance state of the post-condition is only reached through the state that represents acceptance of the core pattern. Pre-conditions, though, add some restrictions. At this point, it makes sense to imagine the code produced to deal with pre- conditions:

Let us assume that the pattern priviledges are ordered the same way as they appear in the code fragment, i.e. 5 has the highest priority, if not than comes 2, if not then comes 6, and if the precondition of 6 does not hold then comes the unconditional acceptance of pattern 7. Lesser priviledged patterns (conditioned or unconditioned) do not matter, since the pattern 7 takes it all. Lets call the set of origins from the most priviledged one to the first unconditional state (if it exists) the {it list of possible acceptance origins}. Now, the following can be set about equivalent acceptance states:

\definition{If a state machine contains preconditioned origins, then two acceptance states are equivalent, if and only if their list of possible origins are the same.}

The only modification one has to do to the Hopcroft algorithm is to adapt the construction of the initial set of acceptance states. It has to be split according to the above criterion. The splitting procedure considering the triggering to equivalent states remains the same. Here is the algorithm in pseudo-code:

TODO

Traditionally, the decision wether a set is to be split is made traditionally \cite{} based on single characters. This method works fine for ASCII character streams but becomes uneffective with Unicode (see also page \pageref{}). Again, the author developed a method that determines equivalence based on character ranges that cuts down the computation time to a tiny fraction.

The previous sections discused the construction of an annotated state machine representing the lexical analyser. The final step of code generation remains. Code generation means to write a program that behaves like the state machine. This means, that if a character α appears at the input one has to transit to the same state as the state machine would. Further, if the state machine fails, the program needs to fail. And, if it succeeds, i.e. a pattern matches, then the program need to notify a match. Additionally, some framework needs to be created for the lexical analyser to iterate over an incoming character stream.

One particular problem has not been discussed before. Real lexical analyser search for the longest match, i.e. they try to eat as many characters as possible to achieve a match. It is now conceivable that a pattern A has matched but pattern B is still in the race and has still hope to be matched — it might only need some more characters. Thus the state machine leaves the acceptance state, but it needs to store information about the match of A, just in case that pattern B is finally not matched. Consider the two patterns return and [a-z_]+":". When a character stream "return" came in, the first pattern matched, but the second is still an option. So, if a string "return_label:" appears one can report that the second pattern matched. But, if the trailing colon is missing, we need to be able to go back and report that there was a return statement. For this reason, we need two variables:

Since one incoming character is potentially compared multiple times until it is determined to what follow-up state it triggers, one needs a variable to store the character that just arrived:input.

For the case, that post-conditions appear, variables have to be added that store the place where a particular post-condition starts, i.e. the place one has to jump back if the post-condition is successful:

where`N` is the numeric identifier of the pre-condition. If pre-conditions are involved one needs to store information wether the pre-conditions are fulfilled or not. Thus variables need to be provided to store the pre-condition results:

where`M` is the index of the pre-condition. The lexical analyser core, generated by \queχ produces a single function, let it be called`analyse_this()` that is called in order to initiate the lexical analysis:

The way the function is defined leaves opportunities to adapt it to different types of environments, depending on the definitions of th`e QUEX_…-macros. The following to sections discuss the construction of state transition code and code for the terminal states. Then it has to be discussed how inverse state machines for pre-conditions are translated into code and fit into the picture. A final section explains how to modify the analyser function by the definition of the`QUEX_…-macros.

Each character that is read from a character stream triggers a state transition inside the lexical analyser. This continues until the currently incoming character does not trigger any further transition. Following cases need to be distingushed:

\item[\bf Mismatch] The lexical analyser never reached an acceptance state. No explicitly defined pattern has matched. If a default action is defined than it is executed at this point.

\item[\bf Match] The lexical analyser reached an acceptance state, some time earlier---or is currently in it. The the action of the dominating pattern has to be executed.

If the current state is an acceptance state, then the id of the winning pattern and the position where it was reached has to be stored. If the current state represents the beginning of a post-condition, then one needs to store the current input position. If later on the post-condition finishes, then one can go back to it.

What pattern actually wins in an acceptance state depends on two issues. First, something that can be compiled into the code: the patterns priviledge. Seconds, something that has to be determined at run-time: dependence on a pre-condition flag. Note, that information about a post-conditioned pattern needs not to be stored, since the path to the acceptance state can only be reached through the state where the core pattern would have raised acceptance. The header of the state transition code of a particular acceptance state looks like the following:

If the state is not an acceptance state, then this header is simply empty. However, both types of states, acceptance and non-acceptance states share the following code fragment:

It simply reads the next character from the input stream. It is canned into a macro, so the user may adapt its underlying procedure to his way of representing the character stream (e.g. as a buffer, an object of`istream`, etc.). The code fragment for the state transition has to determine what trigger triggered, and therefore what the subsequent state will be.

The dynamic behavior of a state machine is uniquely determined by the transitions of its states. For a DFA, it can be assumed that it is in one distinct state when an incoming character arrives. The incoming character determines, according to the triggers of the state, what the subsequent state will be. The next to sections discuss the code generation for a state of the lexical analyser state machine. The operations to be coded for a state can be subdivided into writing a state header (section \ref{}) which does some bookkeeping and writing code for the trigger transitions (section \ref{}).

As mentioned earlier, \queχ's engine is based on character ranges. This enables a fast algorithm to bracket the incoming character. Similar to binary search\cite{}, it determines if the incoming character lies above a border of the middle interval, then higher and lower intervals are checked. Of course, one first checks if the character fits any interval. Imagine an acceptance state for pattern 21 that has the following trigger map:

mismatch & $\longrightarrow$ & terminal 21 \ $[$A-H$]$, $[$J-Z$]$ & $\longrightarrow$ & state 94 \ : & $\longrightarrow$ & state 95 \ I & $\longrightarrow$ & state 99

The current implementation produces the following code to implement these transition rules:

The first if-statement checks wether the`input` lies in the borders of the trigger map. If not, one can directly jump to the terminal state 21. Then one checks wether the input is less than 65, i.e. an A, and then brackets the input down for each interval. This way of generating code seems to leave room for improvement, though. To check wether the input is : (character code 58) we test against $>=\,58$, $<\,91$, $<\,65$, and $<\,59$, instead of a simple check $==\,58$. A hand written transition code may look like the following:

However, if one does too many single checks one would loose the advantage of binary bracketting and the result would be much less efficient. The following table shows an estimated cost in terms of comparisons with respect to the two approaches:

mismatch (before) & 1 & 3 \ mismatch (after) & 2 & 4 \ mismatch (inside) & 4 & 4 \ $[$A-H$]$ & 5 & 4 \ $[$J-Z$]$ & 4 & 4 \ : & 4 & 1 \ I & 5 & 2 \\ \hline \hline

A meaningful comparison of the efficiency of the two approaches, one would have to multiply the results with the probabilities that these characters sets occur. In the above example, the code size of the handwritten transition is much less than the solution created automatically. Determining the optimal algorithm that takes a parameters memory-size-speed-tradeoff and computes the optimal state transition would be an interesting contribution to the \queχ project. The author of this text welcomes any propositions to improve the generation of transition code.

\framebox{vbox{NOTE: The information here is not complete, since the buffer handling was re-designed. Add to this chapter inconv support and input strategies.}} \vskip 0.2cm

Instead of relying on direct read and write operations from storage devices and transmission lines, it is generally advantegous to profit from the fact that data is usually transported faster when it is transported in some larger blocks. When doing lexical analysis one treats the data stream character by character. To send a request for each character and wait for the reply each time a new character is read is obviously not a very promissing approach. Independent on what device or line there is in the background the solution that comes handy is: a buffer in the system memory. A buffer loads a larger blocks of data and keeps them ready-to-read until its content is read completely. Then it loads the next larger block of data.

The structure of queχs buffer is shown in figure style=ref. The buffer itself is not more than a continous chunk of memory. It has two places to store border characters. One is located at the front to store begin of buffer or begin of file. The other is located at the end to store end of buffer or end of file. However, the end of file character may come anywhere from the start of the buffer to the end. Details about these limit characters are explained below. Thus the actual buffer size is two elements greater than the actual number of content elements. A current pointer iterates from left to right\footnote{In this figure it is left-to-right. This basically means from low memory addresses to higher memory addresses. It had absolutely nothing to to with the directionality of the character encoding.} to go forward. The element to which it points designates the current input to the lexical analyser state machine. If it reaches a border new content has to be loaded. The fallback area allows to prevent immediate loads in the opposite directions if one requests to go back immediately after loading.

The following sections explain the mechanisms of queχs buffer, some basic API functions for lexical analysis, the loading procedures, and the buffer creation procedure.

The extreme efficiency mentioned in the last section is payed off, though, by some deveilement of the buffer internals to its API. This is not beautiful, from a design prespective, but---well, very efficient. The following operations need to be implemented for the buffer:

-get_forward(): increments the pointer to the current character and returns the content. If a limit is reached, then a limiting character code is returned. Again, this has not to be checked before the transition check, because if it is a limit character it drops out anyway. -get_backward(): decrements the pointer to the current character and returns the content. If a limit is reached, then a limiting character code is returned the same way as above.

-tell_adr(): returns the position of the current pointer _in memory_. -seek_adr(position): sets the current pointer to the position given as first argument. The first argument, therefore, designates _a memory address_---not a stream position. -seek_offset(const int): adds the given offset to the current pointer.

This interface requires some care to be taken\footnote{Note, that this API is only used by code that is autogenerated. The human end-user is not confronted with such a fragile interface.}. It is not possible to call get_forward() blindly and get the whole stream of data. If a limiting character is returned, it is mandatory to call {tt load_forward()} and {tt get_forward()} again. This spares the comparison against end of buffer and end of file at each get\footnote{Instead, a get is not more than a pointer increment and a dereferencation}. The function {tt get_backward()} works in exactly the same manner.

The positioning functions {tt tell_adr()} and {tt seek_adr()} are implemented with the same spirit of stingyness. The return and receive memory addresses. Thus, any address taken with tell needs to be adapted at after any call to {tt load_forward} or {tt load_backward()}footnote{Again, such a requirement on the usage is nearly insane to be demanded from a human user. Queχs code generator, though, has no problem with that.}. The {tt seek_offset()} function currently only adds a value to the current pointer\footnote{When the {tt NDEBUG} flag is not set, it is checked wether the result is inside the boundaries of the buffer}. This function, actually, only used for unit tests. During analysis the absolut addressing functions are applied.

The buffer implementation in queχ takes advantage of the mechanism of lexical analysis, and manages to keep the overhead of buffering extremely low. This works as shown in figure style=ref. First of all, some content of the information stream in stored in a fixed chunk of memory, the buffer. During the lexical analysis one basically iterates through this chunk. Whenever a new input character is required to determine a state transition, the pointer to the current character, short the current pointer, is increased and the input is assigned the content to what this pointer points. The buffer limits, begin of file, and end of file is determined through special characters. Thus, if the input that is received equals those, then one touched either a buffer limit, the begin of the file, or the end of the file. The trick here is that the transition checks of any state will drop if those characters occur. In any other case the business can continue as usual.

The mechanism described above is highly efficient, since there is a zero overhead as long as no limit is reached. Only when the buffer limit is reached some overhead occurs for identifying that the drop out occured either due to buffer limit or end of file (begin of file, if one iterates backwards during pre-conditions). Already with a buffer size of 64KB, the buffer limit is only reached every 65536 characters. With an average of 4 operations per character the time overhead should not exceed 0.02\% for buffer loading. The speed is basically equivalent to iterating directly through system memory.

Figure style=ref shows the process of loading the buffer with fresh content in forward direction. Loading data from a device into a buffer is very costy. So, it is a good idea to introduce some fallback area where the end of the current buffer content is stored at the beginning. This prevents an immediate load backwards as soon as a character is required from before the current position. Also, since the current lexeme may be post-treated by some pattern action, the pointer to the lexeme start also has to lie inside the buffer. The maximum of both values defines the fallback border.

The new content from the file is then stored behind this border. If an end of file occurs, internally an end of file pointer is set to the position in the buffer where this occurs (most probably before the end of the buffer, but not necessarily). It is stored in a pointer, because it needs to be moved during backward loading. Running through the whole buffer searching for EOF would imply a tremendous slow-down. Also, the end of file character is stored at the position where end of file occured. This way, the`get_forward()` function will return it and the state transition can react on it.

The setting and unsetting of the buffer limit characters and end of file characters at the borders is handled by the load function. Basically, when a border of the buffer does not represent a begin or end of file, it is set to the buffer limit code character. Else, it contains either the begin of file or the end of file character. Note, that the begin of file character, if it occurs, occurs only at the begin of the buffer. The end of file character may occur at any position.

Figure style=ref shows the process of backward loading. Unlike loading forward not such a large amount of memory is newly loaded. Note, that backward loading is only necessary if the fallback buffer was not enough. Thus, it implies some abuse of design that is caught and treated seeminglessly. However, a basic assumption about lexical analysis is that the main direction is`forward\/`. Instead of loading a large bunch of memory before the current position, loading backwards only loads about the first third of the buffer with backwards content from the file. The two thirds of buffer remain intact. Thus, when lexical analysis finally goes forward again, there is still much room before a forward loading is necessary.

Queχs buffer is implemented as a template. By this means a maximum of flexibility is achieved. The following parameters can be passed to the template:

Those are the parameters to the class`basic_buffer`. The header, though, defines a default setting for the class`buffer`. If these default do not interfere with some abnormal goals (such as using EOF inside, not at the border, of a regular expression), then these values can be adapted. The easiest way to to so is to adapt the typedef' statement in the header file:

Then, again`queχ::buffer` can be used to name the buffer class at any given place. Constructing a buffer is possible with two basic approaches. The first approach is suitable for systems where dynamic memory allocation is not an issue. It leaves the buffer allocation to the constructor of`buffer`. The second approach can be used for systems where dynamic memory allocation is an issue, such as for embedded systems. In these systems memory is a costy resource and there is no room for slow memory management routines. In this case a pointer to a location in memory can be passed together with the number of bytes that can be taken from it.

Martin Miller <martin.miller7@gmail.com>

Malathi Voodi <test@tst.com>