Table of Contents

The ideal (and quickest) method is to decide as each character is retrieved whether a) it's part of the same token, and b) what valid token can be recognized at that point. This method requires that a token table be built which contains all possible permissible sequences of characters. The lexical analyzer has the job of building the table; the tokenizer uses the table at runtime to break down the input into tokens.

A problem that tokenizers have to deal with is the question of when a token should be recognized. For instance, in one version of BASIC, the tokens PRINT and PRINTER are both valid tokens. Usually a tokenizer will use a 'greedy algorithm' to recognize the longest possible token.

Using our BASIC example, and given an input of 'PRINTERS:' (note the colon), the tokenizer would make the following decisions as it read the input:

P - var
PR - var
PRI - var
PRIN - var
PRINT - var or PRINT
PRINTE - var
PRINTER - var or PRINTER
PRINTERS - var
PRINTERS: - no valid transition. Last valid transition gave PRINTERS as var. Return that. Save ':' for next token.

Note that in order to operate properly, the tokenizer had to remember the last transition that resulted in a valid token. Once it runs into an input character that doesn't produce a valid transition, it must go back to the memorized point and return that. It must also push back the subsequent characters for use in the next token.

A token table is usually generated beforehand, then compiled into the program - the idea being that you presumably know the nature of the input stream when you are writing your program. The generator will produce a table which identifies all possible transitions in the language, and the tokens that are valid for each transition.

The lexical table generator takes as its input a file containing a set of token definitions and builds a data table which will allow the lexical analyzer routine in the program to identify tokens. The analyzer will always identify the longest token possible. This form of program is significantly faster than a series of literal compares; and the token set can be modified easily and swiftly just by editing the definition file and rebuilding the token table.

The purpose of Luthor is to allow the programmer to create a token definition file, which Luthor then uses to produce a tokenizer which can be included in a program to allow the program to break down an input stream into tokens.

LEX has several shortcomings. First, the generator actually generates program code, with the table embedded in the source. The code is cryptic and hard to follow; using it in your programs is not straightforward; and it makes heavy use of global variables. And most importantly, the code would have to be heavily modified if you wanted to have access to more than one lex table in a program. Even if you don’t want to modify the LEX code, or use multiple tables, the generated program code and global variables force you into a specific program style in order to incorporate the functionality.

LUTHOR has several new and useful features

1. The lex engine is designed as a linkable library. This means that the interface to LUTHOR is well-defined and limited to the library function calls, improving code isolation and making side-effects less likely.

2. LUTHOR provides several interface methods for feeding the input stream: Your program can simply supply a filename and have LUTHOR return tokens from it; your program can supply the address of a function which will supply characters to LUTHOR; your program can directly supply characters one at a time and check for tokens on each call; or your program can submit strings to use as the source for tokens.

3. LUTHOR allows you to query the token value and text string for the current and next token in the stream.

4. LUTHOR allows your program to switch lex tables at any time for a given input stream.

5. LUTHOR supports run-time-loadable (and discardable) lex tables.

6. LUTHOR allows you to have multiple input streams active at the same time, each with its own assigned lexical table - or you can have multiple input streams sharing the same lex table.

7. LUTHOR allows you to define multiple lex tables in one lex definition file. This has the advantages of allowing you to keep related lex table definitions in a single file, and automatically prevents token value collisions since the token values are assigned sequentially in one pass.

8. LUTHOR allows you to optionally assign a structure and/or text value to each token in the definition file. These items produce additional ‘.h’ files which can be compiled into your code.

LEXGEN inputfile [outputprefix] [options]

LUTHOR generates lex tables from token definitions contained in a definition file (file extension .def).The definition file may also contain metacommands which control lexical table generation.

Certain commands can be embedded in the lex definition file, which will have an affect on the files and tables produced. These metacommands are identified by starting with a ‘%’.

Some examples of valid lex definitions are:

Possible components of the lexical definition string are:

Lexical elements can be modified using closure operators. These are:

Lexical definitions can be anchored to either the left or right, using the ‘$’ character. A left-anchored token must be the first token on a line in order to be recognized as that token. A right-anchored token must be the last token on the line in order to be recognized.

For instance, using this definition:

$\.NAME

will recognized the five-character sequence of ‘.NAME’ only if it is the first token on a line. Otherwise, some other rule will be used.

A lexical definition can include OR functionality using ‘|’. For instance,

‘~’*’|"~"*"

defines a string as being either a single quote (‘), followed by zero or more of any characters except a single quote, followed by a single quote; or a double quote (") followed by zero or more of any characters except a double quote, followed by a double quote.

A lexical definition can include parenthesized segments. For instance,

EQU(ATE)?

will match E Q U followed by zero or one occurrences of A T E, so this definition matches EQU or EQUATE.

The combination of the definition options can produce a quite complicated structure. For instance,

-?([0-9]+|([0-9]*\.[0-9]+)|([0-9]+\.[0-9]*))[Ee]-?[0-9]+

will recognize a number in scientific notation. It allows for zero or one negative signs; then a number which may be one or more digits, or zero or more digits plus a decimal plus one or more digits, or one or more digits plus a decimal plus zero or more digits; then the letter E in upper or lower case (if you have case sensitivity turned off, this extra definition is simply redundant); then zero or one negative signs; then one or more digits.

This complex definition is required because the first part of the number is valid with no decimal point, with numbers before the decimal but not after, with numbers after the decimal but not before; but it is not valid with a decimal point by itself.

Let's look at some of the examples used above, on a character-by-character basis.

For those who are wondering, the British spelling of some words is different than the American spelling. So this particular trick would recognize either variant.

The first item is always the token name, and the last item is always the lexical definition string. The FLAGS section needs to exist if the -F option was specified, and the TEXT option needs to exist if the -T option was specified.

The FLAGS definition is assumed to be in a format suitable for a struct initialization. The TEXT definition is assumed to be suitable for a string. You must put quotes around the TEXT definition if it contains whitespace. There can be no whitespace in the FLAGS definition unless it is within a quoted string.

A Simple definition line might look like this:

A version of the same with all four fields would look like this:

The struct table produced by LUTHOR is always named XXXXXFlagTab[] where XXXXX is the output prefix specified on the command line or by %OutputPrefix. The text table is always named XXXXXTextTab[].

This version of LUTHOR does not include support for loadable XTXT.H or XFLG.H files as part of the loadable lex table functionality. If you really need this suport, one worakaround is to generate the lex table twice - once with the -L option and once without. The .H files can be compiled into the EXE.

SAMPLES/15 Using a LexStream set up with LexInputString

This int variable contains the last error, for functions that have an error return. The possible errors are defined in luthor.h

A lex table is submitted to the LUTHOR engine by one of the LEX SETUP functions. Once this is done, the LEXTABLE value can be used to associate the table with any number of LEXSTREAMS. The LEXTABLE handle is valid until program termination or until the table is dropped using LexDropTable().

A LEXTABLE, in association with an input stream of some kind, forms a LEXSTREAM. This handle specifies which input stream is being referred to when performing any of the TOKEN operations.

This structure is defined in LUTHOR.H . It is the structure of the object in XTAB.H that defines the lex table.

This structure is defined in LUTHOR.H. It contains the fields required to return the info specified by LexLineInfo.

Function initializes the lexical engine. It may be called explicitly, or will be called automatically the first time one of the other lexical routines is called, with options set to zero.

Options are defined by OR-ing the following constants:

LO_SUPPRESS - Suppresses the LUTHOR banner at initialization time.

Returns LXE_ERROR on error.

Function sets up a lexical analyzer table by passing a pointer to a LEXOBJECT. Returns an int handle which may be used to associate an input stream with this lex table.

Returns LXE_ERROR on error.

Function loads a Lexical analyzer table specified by filename. Returns a handle which may be used to associate an input stream with this lex table.

Returns LXE_ERROR on error.

Function assigns an input file to a given lex table, and returns a handle to a lexical analyzer stream.

Returns a LEXSTREAM handle.

Returns LXE_ERROR on error.

Function assigns a function to be the source of input for a particular LEXSTREAM. The called function must not require arguments and must return an int value for the next character on each call. At EOF, the function must return EOF’s every time it is called.

Returns LXE_ERROR on error.

This function sets up a LEXSTREAM that can then be used with the BuildToken() function.

Returns LXE_ERROR on error.

Function sets up a LEXSTREAM using the supplied string as input. Further input can subsequently be submitted using LexSubmitString().

This function pushes a new file into the input stream, so that all further input comes from the new file until EOF. ThisToken() is not affected but NextToken() is reevaluated. When the input stream reaches EOF for the new file, further input continues from the former file, where it left off. The depth of stacking of files is limited only by the ability of the library to reallocate tables.

Note: When a file reaches EOF, one EOF token is returned. An AdvanceToken() will then retrieve the next token from the next pushed-down file. To determine if you are at true EOF, use LexLineInfo() to retrieve the current file pushed depth.

The function releases memory if the specified lex table was an LLT; otherwise it just makes the lextable handle available for new lextables.

Returns buffer character count on success or LXE_ERROR on error.

This function submits a new string to a lexstream. Opt can be one of:

which will either insert the new string at the current input location (forcing reevaluation of ThisToken()), at the end of input, or completely replacing the existing input and forcing reevaluation.

The function returns the number of characters in the input buffer, including the current token, after submission. You can pass a NULL string to the function to get the current character count without affecting the buffer (value of opt is ignored). Clearing the input buffer using SSO_REPLACE requires a non-NULL, zero-length string.

Function allows the program to submit characters one at a time to the lex table. The function will return zero until it has built a valid token, then it will return the token value. Input can be flushed by calling the routine with EOF (-1) as the value for c until the function returns EOF. If the function cannot resolve the received input into a valid token, it will return -2 and flush its buffers of all pending input.

Notes:

• ThisTokenText(LEXSTREAM) will return NULL until a token is recognized, then will return the token text value until another character is submitted.

• Most of the other functions in the library are invalid for LEXSTREAMs that use BuildToken().

Returns a pointer to a LEXINFO object that contains the following:

• char pointer to the name of the current input file (where applicable)

• Line number of the text line that the current token is on

• char pointer to the text of the current line.

• position in the current line of the start of the current token.

• Number of files ‘pushed’.

• Minimum and maximum token values for the lex table.

• Pointers to the Flags and Text Tables for LLT's.

Compiler Design in C
by Alan Holub

Published by Prentice Hall --- ISBN 0-13-155045-4

This book gives a clear plain-english description of the theory and practice of lexical analysis and the design of lexical generators and tables.

• Fixed a bug in the table generator that wasn't handling multiple OR'd token definitions properly.
• Added width setting option for the Flags table.
• Added the capability to embed the text table and character-type flags table in an LLT.
• Added fields to LexLineInfo struct.