The major component in ToolMaker is the LALR-parser generator ParserMaker. This component generates parsers from grammars, i.e. from a formal textual description of a language it creates programs that checks its input according to that grammar.

The generated parser not only accepts or refuses its input but also contains various error recovery routines. This means that when an incorrect input is encountered it automatically tries to correct it so that the rest of the input also may be analysed. This automatically generated error recovery is possible to further fine-tune by giving ParserMaker additional information.

In addition to the actual grammar it is also possible to specify semantic actions for each production (or rule). A semantic action is target language code provided by the implementor that will be executed each time the parser reduces the input according to the corresponding rule, i.e. when that input is encountered. The code in the semantic actions may refer to data synthesised in other terminals or non-terminals, so called attributes. Using these attributes a representation of the input may be built for example.

The ScannerMaker tool produces lexical analysers from a description of regular expressions to recognise. The emphasis when designing this tool has been speed as a major part of the execution time of a software tool often is to read the input and compose it into tokens.

ScannerMaker supports multiple vocabularies (sets of tokens to recognize) and scanners making it easy to implement context sensitive scanning.

The connection between ParserMaker and ScannerMaker is almost completely seamless as ScannerMaker takes as input not only a file describing the regular expressions but also a file produced by ParserMaker containing the tokens found in the grammar.

A Lister is a subroutine package to handle error messages and to produce listing files. ListerMaker is a tool to create and customize such modules also included in the ToolMaker kit. This makes it very easy to produce and handle listings and error messages.

To be able to efficiently produce the source code to compile from the various generated files a specially optimized text processor is also included in ToolMaker. The Incremental Macro Processor allows text to be conditionally included, sections defined and inserted at other places, variables to be expanded and so on.

ParserMaker, ScannerMaker and ListerMaker all uses the facilities of the Incremental Macro Processor to automatically generate compilable source code in an efficient manner.

The Incremental Macro Processor is delivered as a separate tool with the ToolMaker package and is documented in a separate manual (the IMP Reference Manual).

Toolmake makes it very simple to set up a new subsystem based on ToolMaker. Using a dialogue you specify what parts you want to generate using ToolMaker, toolmake creates the appropriate files in the current directory.

You may also select the level of information already in the various files (description files, main module suggestion etc.), minimal, normal contents or a complete example (see App. A, The PL/0 Example, App. D, The PL/0 Example, App. H, The PL/0 Example and App. L, The PL/0 Example).

A description file is the input to a component. This file contains information for the actual generation process.

The description file for ParserMaker contains the description of the grammar, and for ScannerMaker the regular expressions to be assembled to tokens. The ListerMaker description file contains primarily the message templates.

A description file contains sections containing different information, such as options and the rules. Both ScannerMaker and ParserMaker have rules sections where the grammar and regular expressions respectively are described in a meta-language.

Each actual Maker reads and analyses its description file, producing any error messages on the screen and a listing file if requested.

After having analysed the Makers own description file and the optional ToolMaker Common Description file (containing definitions common for all Makers, refer to Ch. 4, The ToolMaker Description File) the Maker produces output in the form of table files. The table files contain data and code definitions to complement skeleton files which are provided and may be modified. As a last step the table file is processed together with the skeleton files (using the Macro processor IMP) to produce the actual source files.

Also a source file is never generated unless necessary, i.e. unless the contents of the file has changed. This can make enormous differences in compile times for large systems (when using automatic build tools such as make) as files that are dependent on ToolMaker generated source files need not be recompiled unless a real change has been made. For small systems the gain may be small in comparison with times needed to compare the new files so the possibility to force generation (thus avoiding the comparison) is available.

The skeleton files are files in IMP format which when processed by the Incremental Macro Processor together with the table files generated by the Maker will produce the actual data and code which constitutes the compilable source for the parser, scanner or lister.

The skeleton files resides in a special directory delivered with ToolMaker. There is one separate subdirectory for each target language available.

Under particular circumstances it may be necessary to modify the skeleton files. The modified files should be kept separate from the standard skeleton files and pointed to by using the library option of the Makers.

The verbose directive controls the amount of information that is output on the terminal during the generation processes.

If NO VERBOSE is specified, the generation process will be silent, and only error messages will be output to the terminal.

If VERBOSE is specified, the progress of the generation process will be logged to the terminal, and timing figures for the various phases will be supplied.

The default is:

This option specifies for which language the files should be generated. The following values of the target option are supported:

The default setting is:

This option specifies for which operating system the files should be generated. The following options are supported:

The default setting is:

The prefix is used as a prefix for all externally visible functions and types. This prefix set (implicitly or explicitly) in the ToolMaker Common Description file is known as the system prefix and may be overridden locally for each Maker. System wide types and functions will still use the system prefix.

The default value is:

The library directive instructs the ToolMaker tools to look for template files in a directory other than the default, which is $TMHOME/lib/target/, for example:

The escape directive allows the implementor to change the escape character in target language sections. The quoted string used to describe the escape character must contain exactly one character which is directly interpreted as the escape character.

If NO ESCAPE is specified no character will be used as escape character in semantic target language sections.

Default:

This option specifies the maximum number of characters on a line in the list file (if requested) before a line is broken into two. If NO WIDTH is specified, lines will be printed in full length.

The default value is:

This option specifies the number of lines that fit on a page in the list file. If NO HEIGHT is specified, the list file will not be divided into pages.

The default value is:

The generate directive instructs the Makers on which output to generate. The intermediate table files are normally not kept after successfully generating the target language source, but by using this option any combination of tables and/or source files may be generated.

The default for all Makers is to generate only source files. To generate tables this option must be used.

The force directive instructs the Makers to force the generation of source files, even though it might not be necessary, thus overriding the built-in functionality to not overwrite any source files that would contain identical information.

The default value is naturally:

Consider the productions for the well-known IF-statement:

It can easily be seen that the above grammar is ambiguous by the statement:

where c and s stands for condition and statement respectively. The ambiguity occurs because there is no way of determining to which IF the ELSE-clause belongs. It can be bound to the innermost THEN representing the structure:

or to the outermost THEN giving:

The ParserMaker system will recognize the conflict in a state having the LALR(1) items:

The grammar contains one shift-reduce conflict. ParserMaker does not know whether to shift the symbol ELSE, binding the ELSE-clause to the innermost THEN, or to reduce and bind the ELSE to an outer THEN-clause.

The normal interpretation of an IF statement is to bind the ELSE to the innermost THEN-clause.

Thus, shifting the symbol ELSE will do the job.

The above grammar contains a number of LALR(1) conflicts. The conflicts in this grammar are associated with operator associativity and precedence.

The expression:

can be interpreted either being left or right associative, yielding the structures:

or

respectively.

The system gets a shift-reduce conflict when recognizing the input I + I, representing <expr> + <expr>, and the next token is +. ParserMaker can then not determine whether to shift, interpreting + to have right associativity, or reduce, getting left associativity.

The most common interpretation of additive expressions is to let + and * be left associative. The conflict is solved by reducing <expr> + <expr> when + is the look-ahead symbol. The second type of conflict arises when:

or

appears as input. If we consider the first one it could be structured into:

or

The first interpretation defines * to have higher precedence than + and vice versa for the second one. This situation is quite analogous to the associativity problem above. If the input is I * I and the next token is +, the action must be to reduce <expr> * <expr>. But, if the input is I + I and the next token is *, the action must be shift.

As already mentioned, ParserMaker contains two different mechanisms to help producing a consistent parser. Again, the safest way to avoid problems is to rewrite the grammar, or, if possible, to modify the language.

If a grammar is not LALR(1), and no modifications resolve the conflict, a default disambiguating mechanism will be used. A conflict is by default resolved by the rules:

The dangling else problem is solved adequately by applying the first rule. That is, the ELSE will always be shifted and bound to the innermost THEN.

The ambiguous expression however, will not be solved correctly since different look-ahead symbols are treated differently, and it is impossible to predict the logic of every such situation.

The modification rules directly affects the parse tables. The mechanism requires great attention and should be used with care.

A conflict is resolved by preventing or forcing a reduce action on specified look-ahead symbols. The modification rules are written:

or

%+ means reduce-for the indicated symbols, while %- means reduce-not-for the indicated symbols.

The modification rules can appear at two different places in a right hand side:

When an input grammar contains LALR(1) conflicts, the affected states are written to a list file. The conflicting look-ahead symbols can then be inspected and appropriate actions can be decided.

As examples of the modification mechanism, consider the solutions to the dangling else and the expression problems. The dangling ELSE problem is solved by avoiding a reduce for the look-ahead symbol ELSE. This is written:

An unambiguous grammar for the expression is specified below. The interpretation is that * has higher precedence than +, and both operators are left associative.

A modification is considered by ParserMaker only when a conflict is resolved.

When a conflict occurs, the following actions should be taken:

The first level is a restricted local corrector. Restricted because it is not able to recover from all types of syntax errors. Local correction means that it will change only the remaining input and not the already parsed text. The first level tries to find a least cost correction of single symbol errors. One symbol of insertion, deletion or replacement will be considered.

In the error configuration of the parse stack and input, each possible single symbol repair is considered, and the correction with the least cost is applied. The cost is based on the costs assigned to each terminal in the terminals section, and how well the correction fits in the context in which the error occurred.

The cost of the best repair is compared with a predefined threshold value. If the computed cost is below this threshold value, the correction is applied. If not, the first level fails. By default the threshold value is equal to the cost of accepting two symbols after the error symbol.

The acceptance cost and the amount of look-ahead are defined using options (see Sec. 8.2.4, “The Options Section”). Together with the facility of defining costs for each terminal symbol (see Sec. 8.2.6, “The Terminals Section”) a parser implementor has an opportunity to tune the first level of recovery to a specific environment.

The acceptance (shift) cost has a default value of 5. This cost should be regarded as an upper bound for the insert and delete costs for the terminal symbols. It is only necessary to change the acceptance cost if you want the terminal costs to have a greater range.

The amount of look-ahead has a default value of 5. This value is a reasonable trade-off between functionality and performance. Since the threshold value is defined as (look-ahead-amount - 3) * shift-cost, you are not allowed to reduce the amount of look-ahead below 4. The threshold value would in that case get a value of less than or equal to zero which means that the single symbol correction will always fail. Due to performance reasons, it is not recommended to increase the look-ahead above 6.

Defining appropriate cost functions is not easy and should be based on some statistical observations on how the language is used. The general idea behind the cost functions is that they should be selected such that the lower the probability of a specific error occurring, the higher the cost should be for the symbol correcting the error. For instance, omission of a semicolon is a very frequent error in Pascal, thus the insertion cost for ; should be low. Similarly long reserved words should be assigned high deletion costs.

It can sometimes be useful to deliberately violate the rule that the acceptance cost should be regarded as an upper limit of the terminal costs. If you want to make sure that a specific terminal symbol is never inserted or deleted during error correction, you should give it an insertion or deletion cost which is larger than the threshold value.

If the first level of recovery fails, the parser will enter the second phase. The string synthesizer will, from the error point, generate a least-cost string which yields a legal continuation of the already parsed text. The least cost string is generated from the grammar and based on the insertion costs (defined in Sec. 8.2.6, “The Terminals Section”).

The generated string is then matched against the remaining input. In this process, a prefix of the generated string will be inserted, and some symbols from the remaining input might be deleted. The idea is to preserve as much as possible of the remaining input and base the recovery on insertion rather than deletion.

The string synthesising technique is a true local corrector as it never gives up. It can return a legal configuration for each possible input string. However, the parser will terminate the second level when it tries to delete a fiducial symbol (however see the modified panic mode algorithm below). A fiducial symbol is a syntactically important symbol, and it is defined as fiducial by the parser implementor (see Sec. 8.2.11.3, “The Fiducial Part”). Symbols that start main phrases of the input language, e.g. some of the reserved words like VAR, BEGIN and PROCEDURE in Pascal, should be defined as fiducial symbols.

Panic mode is a very crude way of recovering from syntax errors. The general idea behind panic mode is to scan ahead into the input string until something solid, like a reserved word, is found. The parse stack is then reconfigured, popped, such that the new token is accepted. The term fiducial will be used for such important symbols. See Sec. 8.2.11.3, “The Fiducial Part” for how to specify these symbols.

In the original panic mode large portions of the remaining input might be deleted, and ParserMaker therefore uses a modified variant.

The technique used by ParserMaker can be summarized by:

Even if panic mode is a crude way of recovery, it might be the only reasonable choice when dealing with gross structural syntax errors.

The error recovery system is generated almost entirely from the grammar, and very little extra information must be supplied by the parser implementor. There are however, several ways of enhancing the generated error recovery system. Parser implementor supplied information can be added in the terminals section (see Sec. 8.2.6, “The Terminals Section”), by the cost functions and print symbol, and in the recovery section (see Sec. 8.2.11, “The Recovery Section”). The recovery section contains facilities for defining the set of fiducial symbols and some other tuning information. Also, the shifting cost and the amount of look-ahead applied can be defined using options to ParserMaker (see Sec. 8.2.4, “The Options Section”).

This chapter defines the lexical symbols of the ParserMaker description language.

The ParserMaker description file may contain thirteen different sections: the options section, the import section, the srcp section, the token section, the declarations section, the terminal section, the attribute section, the recovery section, the export section, the scanner section, the insertsymbol section, the deletesvmbol section and the rules section.

All sections except the rules section are optional. The rules section must be the last section, the option section must be first if it exists and the import, token and srcp sections must, if they exist, immediately follow the option section. Otherwise the order between the sections is free.

The options section controls the ParserMaker generation process. For instance, the degree of table packing, included error recovery facilities and the kind of logging information produced.

The import, token and srcp sections are further described in Ch. 4, The ToolMaker Description File in Part I, “ToolMaker System Description”. These three sections are normally located in the ToolMaker description file and should be put in the ParserMaker description file only when developing a stand-alone parser.

The declarations, export, insertsymbol, deletesymbol and scanner sections defines target dependent code that should be included in the produced parser.

The terminals, attributes and recovery sections together with the rules section specifies the input language. It contain facilities for tuning the automatically generated error recovery system, defining the scanner interface, handling ambiguous grammars and defining semantic actions.

To give a short overview of what the description file may look like, a small example will be presented.

The problem: Assume that a file contains a sequence of telegrams.

Each telegram consists of one or more sentences terminated by the symbol STOP. A telegram ends with the symbol ZZZZ. The problem is to analyse a telegram file and for each telegram write a summary containing the total number of words in the telegram (excluding STOP and ZZZZ) and all words exceeding 12 characters.

Preconditions: The target language is C. A scanner exists which recognizes the tokens:

When a WORD is recognized the scanner returns the length of the WORD. The lexical attribute LENGTH is used to hold this value. The scanner call interface is defined in the scanner section (see Sec. 8.2.8, “The Scanner Section”). The token section is shown here for completeness but is normally defined in the ToolMaker description file.

Example: A file containing the text:

will result in the output:

The solution:

The options section of the ParserMaker description file controls the parser generation process. Corresponding options can be given as command line parameters to ParserMaker at its invocation. Options given as command line parameters override those within the description file. Command line options are described in Sec. 9.2, “Options”. For a detailed discussion on options see Sec. 4.1, “The Options Section” in Part I, “ToolMaker System Description”.

The directives can be given in any order. If a directive is repeated, only the last one given is used.

Note that if a directive is explicitly stated in the options section, all its default options are turned off. This means that all desired options must be included when a directive is used explicitly, not just the desired extra ones, which is especially important for set valued directives. The default setting of the options are

The semantic actions in the rules section are written in the target language extended with an attribute propagation technique. Variables and subroutines referenced within the semantic routines are defined in the import and declaration sections. Using the export section variables and functions declared in the declaration section may be exported. These particular sections should contain declarations and routines in the target language. The character sequences, representing the code, are copied unformatted to the output file.

Example: A C interface might be written:

Target dependent errors in the import, export and declaration_ sections_ will not be detected until the generated code is run through the target compiler.

The terminals section defines the scanner interface and is optional. If omitted, ParserMaker will supply pertinent defaults. If present, it should define the terminal symbols used in the grammar and the token codes returned by the scanner. Information for error recovery improvement can be supplied with each terminal.

The left hand side of the definition is a terminal symbol. The terminal is written exactly as it is used in the subsequent grammar. The <token code> is a positive integer value that the scanner must return in order for the generated parser to recognize the token. If the terminals section is omitted ParserMaker will generate an internal number for each token.

Example:

The optional error recovery information makes it possible for a parser implementor to tune the error recovery handler. The insert cost and delete cost values define the cost of inserting and deleting the terminal symbol respectively. The higher the cost, the more seldom the symbol will be inserted or deleted in the error recovery process. Both the insert cost and the delete cost default to one (1).

The print symbol defines the string to be used in error messages and in the error repair process instead of the terminal symbol itself. This facility applies normally only to pseudo terminals, i.e. terminals like identifiers and numbers, which are identified both with a type and a value. The default print symbol is the terminal string itself.

Example: An identifier might be defined as:

An identifier has the token code 10, and it is expensive to insert an identifier compared to deleting it (5 versus 1), and if an identifier is inserted, GENID00 will be issued in its place in the error message.

Example: The definition:

is equivalent to:

How these weights and the print name are used is described in Sec. 7.7, “Error Recovery Principles”, in Sec. 8.2.9, “The Insertsymbol Section”, Sec. 8.2.10, “The Deletesymbol Section” and in Sec. 10.1.3, “Error Recovery”.

The attributes section defines the semantic attributes used in the grammar. Language dependent declarations, i.e. a description of the implementation, are defined in the optional declaration part of each attribute.

Example:

Instead of repeating the name of the identifier in the target language declaration, it is possible to use a %1 as a placeholder for the name. It will automatically be substituted with the name in the produced code.

Example:

How to use attributes is described in Sec. 7.5, “Grammar Attributes”.

The code specified in the scanner section is executed when a new token should be read from the input stream. The target language code is copied into the generated parser. The purpose of this code is to fill the token structure as supplied by the pre-defined pointer variable token which is defined when the scanner section is entered. See Sec. 4.4, “The Token Section” in Part I, “ToolMaker System Description” for a description of the fields in the token structure and how to define them.

The scanner section can be viewed as a procedure with the following formal interface:

Example:

If this section is omitted, default code will be generated:

where %%(tmkPrefix) stands for (and will be expanded to) the system prefix, i.e. the code generated will assume that the scanner is a scanner generated by ScannerMaker using the common prefix (see Sec. 4.1.4, “The Prefix Directive” in Part I, “ToolMaker System Description” for a description of how to define a system prefix).

This block should contain the necessary target language code to construct a semantically valid token when the parser error recovery process has decided to insert a token in the input stream. The code is inserted into the pmISym() function. See Sec. 10.2, “Run-Time Interface” for further details.

This block should contain the necessary target language code to handle the deletion of an already constructed token when the parser error recovery process has decided to delete a token from the input stream. The code is inserted into the pmDSym() function. See Sec. 10.2, “Run-Time Interface” for further details.

The recovery section is optional. It defines language dependent information that will improve the error recovery system.

The rules section defines the syntax of the input language. The input specification is written in an EBNF-like notation, extended with semantic actions and a mechanism for resolving ambiguities in the grammar.

The concepts behind the various constructs in the rules section are discussed at length in Ch. 7, Concepts and Assumptions.

The pretty printed grammar is written to the list file if option List Grammar; is activated. It is divided in two parts, the vocabulary and the productions.

The vocabulary contains:

The productions list contains all productions pretty printed together with their production number.

The internal codes of the vocabulary and the production numbers are later used when the item set and the tables are printed.

The LALR(1) item set is written to the list file if the option List Items; is activated. A subset of the item set is also written if the grammar contains errors. This may provide useful information in conjunction with the trace output printed if the trace directive is set in the options section (see Sec. 8.2.4.4, “The Trace Directive”). The concept of items is further discussed in reference [Aho].

For each state, a table containing all items in that state is written. The table is labelled by the state number and the continuation symbol chosen by the second level error correction (see Sec. 7.7.2, “Level 2: String Synthesizing Technique”). If separators have been defined (see Sec. 8.2.11.2, “The Separator Part”), a separator continuation symbol will be printed within parentheses if applicable for the state.

Each item in the state is represented by an entry in the table. Each entry is labelled by the parsing action for the item in the state. The action has one of the following formats:

The item itself follows the parsing action. If the parsing action is reduce, the item is followed by the follow set of terminals within curly braces.

Consider the following example:

The state number is 14, the continuation symbol is ., and the separator continuation symbol is ;. The parsing action for the first item is reduce by production 39, and the follow set which causes that reduction is enclosed in curly braces. The parsing action for the second item is shift, and the next state is number 15 if a <mulop> is recognized. The parsing action for the third item is shift-reduce by production 50 if a * is the next token.

When the grammar is ambiguous, indicated by error message 303, the list file will contain information about the ambiguity. If this is the case, the item sets for all offending states will be logged, and each state will be preceded by a line explaining the nature of the ambiguity (shift-reduce or reduce-reduce), followed by the offending symbol and the involved production or productions. With this information it is normally possible to rewrite the grammar or use modification rules to resolve the ambiguity (see Sec. 7.6, “Grammar Ambiguity and LALR-Conflicts”).

The parser tables are printed as matrices. Each row is labelled with a state number, and the state is also identified by the symbol before the dot in the first item of the state. The columns of the action table are labelled with the internal codes of the terminals, and the columns of the goto table are labelled with the internal codes of the non-terminals. An entry in the table has one of the following formats:

If table packing is activated, the packed parser tables and the various access structures will also be printed. In order to understand the purpose of the various access structures it is necessary to understand the theory behind the various packing methods, see reference [Dencker]. The entries in the packed parser tables have the same format as described above.

When the parser implementor wants to parse the input stream, all that need be done is to call the pmParse() function. The only requirement the parser has is that the input stream must be initialized so that the first call of the scanning function defined in the scanner section of the description file will return the first symbol of the input stream to be parsed. If ScannerMaker is used to generate the scanner, this involves initialising it and setting up a context. Of course it is appropriate to perform other initialization like initializing the listing system, setting data structures for the semantic actions etcetera before calling pmParse().

The generated parser expects the code defined in the scanner section (or default) to supply it with tokens from the input stream. This functionality must be implemented by the parser implementor. If ScannerMaker is used this is no problem since this is exactly the task of ScannerMaker.

The parser expects the scanner section to return exactly one token from the input stream each time it is called. The tokens it expects the scanner to recognize are defined together with their token codes in the vocabulary file (see Sec. 8.5, “The Vocabulary File” for the format of the vocabulary file).

The error recovery system of the generated parser is very good at recovering from syntax errors. What is lacking is a means for reporting to the user what has occurred during error recovery. The error recovery interface routines of the generated parser provide the necessary hooks for reporting the error recovery activities to the user. The error recovery interface routines are pmISym(), pmDSym(), pmMess() and pmRPoi(). These routines can be automatically generated if the errorhandler option is used. The default interface assumes a ListerMaker generated lister module. The error recovery interface may also be completely provided by the implementor.

When an error is detected by the parser, the generated error recovery system in the parser is activated to try to repair the error. If this is successful, and if recovery has been made by inserting or deleting one or more symbols, pmISym() and/or pmDSym() are called one or more times (once for each inserted or deleted symbol).

Regardless whether the recovery process was successful or not, the next step is that pmMess() is called to report that the error recovery process is finished, and the result of the process. At this time it is appropriate to output an error message to the poor parser user.

If the error recovery process was successful, i.e. the parser was able to recover from the error, pmRPoi() is called to indicate from what point the parser will continue to process the input (the recovery point). For small errors, this is often the same point that caused the error, and in these cases it is probably not necessary to do any special reporting to the user.

In summary, this is the calling sequence of the error recovery interface routines:

After these corrections of the input has been made the parsing is continued as if the input had actually been the corrected stream of tokens. No semantic actions are executed during error recovery until the final decision on which corrections to apply has been made, and then it is executed exactly as if the corrected input had been found. This means if the routines above (particularly pmISym() as defined by the insertsymbol section) have been designed properly the semantic actions will be executed exactly as if the user had input the corrected input, thus making it possible to perform even semantic analysis on the input. The design of the semantic actions is thus greatly simplified as no special care have to be taken for the erroneous input.

The parser entry point. To be called from the application when a source language text should be parsed. The scanner must be initialized when this function is called so that the scanner section can be called to fetch the first input symbol.

Called from the error recovery routines when the parser has decided upon inserting a symbol in the input stream in order to recover from a syntax error. It is intended for error reporting, and for constructing a semantically feasible token. The parser error recovery process has no notion at all about semantics, it just decides upon a syntactically reasonable token to insert. Thus the parser implementor must supply code to construct a token that has semantic meaning to the application.

Consider the following example: when the scanner reads an INTEGER, a normal action for the scanner is to compute the value of the integer read and return it as a terminal attribute. When the parser error recovery process decides to insert an INTEGER token in the input string, it has no knowledge about how the scanner handles an INTEGER, so in order to construct a semantically feasible token we must set the value attribute to some value for an INTEGER in pmISym().

The parameters: code is the terminal code for the inserted token, symString is the terminal string as used in the grammar, printString is the terminal print string as defined in the grammar, and token is the token that should be created.

This function is defined in the generated error recovery interface module, pmErr, if selected by use of the errorhandler option. The actual code to construct a semantically valid token should be defined in the ParserMaker description file (see Sec. 8.2.9, “The Insertsymbol Section”). The code from the insertsymbol section is inserted into the body of the pmISym() function if the option Errorhandler; is set, otherwise this functionality must be supplied by the implementor.

Called from the error recovery routines when the parser has decided upon deleting a symbol from the input stream in order to recover from a syntax error. It is intended for error reporting and clean up. The first parameter is the deleted token. The symString and printString has the same interpretation s for pmISym(). The function is defined in the default error recovery interface module that is automatically generated if the Errorhandler option is set.

The actual code to necessary to clean up may be defined in the ParserMaker description file (see Sec. 8.2.10, “The Deletesymbol Section”). The code may for example return dynamically allocated areas referenced by the semantic attributes of the token. The code from the deletesymbol section is inserted into the body of the pmDSym() function if the option Errorhandler; is set, otherwise this functionality must be supplied by the implementor.

Called from the error recovery routines when an error has been recovered from. It is intended for error reporting. The parameter is the token from which the parsing process will continue. The default module pmErr implementing the function is generated if the Errorhandler option is set, otherwise the function must be supplied by the implementor.

Called from the error recovery routines when the syntax error has been repaired, and an error message should be output. The function is generated in the error recovery interface module if the Errorhandler option is set. Otherwise the function must be supplied by the implementor.

The parameters: token is the token which activated the error recovery process, method is the recovery method applied, code is an error classification, and severity is the error severity code.

The values of the integer arguments have the following meaning:

Symbols in the ScannerMaker description language are constructed from using upper case letters from the ISO-8859-1 character set, lower case letters (ISO-8859-1) and digits.

The overall structure of the Scanner Description file is as follows:

The toolmaker sections are further described in Ch. 4, The ToolMaker Description File in Part I, “ToolMaker System Description”.

The option section follows the general guidelines as described in Sec. 4.1, “The Options Section” in Part I, “ToolMaker System Description”. The options which can be specified in the options section are described in Sec. 13.2, “Options”. The import, srcp and token sections are described in Ch. 4, The ToolMaker Description File in Part I, “ToolMaker System Description”.

The target code sections are one of the following subsections:

The general definition sections are one of the following subsections:

The vocabulary sections have the following structure:

The scanner sections have the following structure:

The rule section includes the following subsections:

Each section maybe optionally ended by the %%END keyword. The case of the letters in keywords are not significant and all keywords starting with %% may be specified in plural as well as in singular. For example the following keywords are equivalent

Between sections, that is, after an %%END token up to the next %% characters, is treated as comments. The special %%COMMENT keyword also starts a comment up to %%. The %% may be quoted by the escape character to be part of the comment. Inside a section comments may appear anywhere as long as they do not break a lexical unit such as an identifier or a string. Comments begin with two hyphens and end with a new line.

In this section options can be specified to control some actions taken by the scanner generator. These options can be overridden by options given on the command line when the scanner generator is invoked (see Ch. 13, The ScannerMaker Command). If an option is not specified its default value is used. The default options are:

Note however that the settings of common options in the ToolMaker Common Description file influences the default values (see Sec. 4.1, “The Options Section” in Part I, “ToolMaker System Description”).

In this section types, variables and functions used within the scanner should be defined. This target language dependent source code is copied into the generated scanner and is accessible (valid) in all other target language sections.

In this section variables used within a scanner context should be defined, see Sec. 12.2.21, “Semantic Actions” and Sec. 14.1.1, “Type: smScContext and smScContextItem” for a complete description of how to use the scanner context.

User defined functions and variables that should be visible outside the generated scanner should be defined in this section, this section is included in the interface description of the generated scanner (in C the smScan.h file).

The code specified in the reader section is executed when reading characters into the input stream, see Sec. 12.2.21, “Semantic Actions” for more information on the contents of this section. The reader section may be viewed as the body of a function with the following definition.

The function must return the number of characters read. If no more characters can be read, zero should be returned. In case of an error, a negative value should be returned. This will cause the scanner to abort and return the value as an error code instead of an external token code. For example

This reader reads from the file fd into the buffer smBuf fer a maximal of smLength characters. It returns the number of characters read or -1 if an error occurs (which will abort the scanner as described above). The default reader is

That is, characters are read from standard input.

The code specified in the action section is executed just before entering any token specific action and is therefore common to all token specific actions, see Sec. 12.2.21, “Semantic Actions” for a complete definition of semantic actions. This code is copied in-line into the body of the smScAction function and then followed by the semantic actions for the tokens.

In the prehook section code which should be performed before scanning a token is defined. For more information on the contents of this section, see Sec. 12.2.21, “Semantic Actions”. The prehook section may be viewed as the body of a function with the following definition

If a positive number, zero included, is returned the scanning is terminated immediately. The number is used as the external token code returned by the scanner.

The code specified in the posthook section is executed after a complete token is found, see Sec. 12.2.21, “Semantic Actions” for more information on the contents of this section. The posthook section may be viewed as the body of a function with the following definition:

The found token’s external code is determined by the value of the field smCode in the token structure (smToken→smCode in C) when the posthook function is terminated. This field is initially set to the value as specified in the vocabulary file or the vocabulary section depending on the token recognised.

The external token code for the token found can be changed in two ways, either by setting smToken→smCode to the new external code or by returning the new external code by executing a return statement. The external token code should be one of the enumeration values defined for tokens in the vocabulary to which the current token belongs, or the predefined enumeration smSkipToken.

When smSkipToken is returned the current token is skipped, as if it was given in the skip section.

This section defines a character set. The use of a character set is primarily to generate a scanner that should execute on a machine with a different character representation than the machine on which is was generated. A character set may be viewed as the mapping from the native set (the set on the machine which the scanner is running) to the internal for which the tables are generated. This makes it very easy to generate scanners that can be compiled and run on various machines even with different character sets.

The name of the set is specified followed by 256 character specifications. Allowed representation of characters are all non-white printable ISO-8859-1 characters, two digit hexadecimal numbers and the special character combination two dots. The two dots specifies an undefined character. Comments are the same as for the rest of the scanner, double hyphens.

The mapping determines which character is used in the rules description for the n-th character in the character set. For example,

specifies that the first four characters in the set are a, b, undefined and 0F. That is, if the character a is used in the description of the scanner, the generated scanner uses a as the first character in the set (value 97). For example:

defines a set of a possible IBM character set.

Undefined characters always result in error states in the generated DFA. That is, if such a character is encountered in the input string when the generated scanner is used, the scanning is aborted and eventually the character is returned as an undefined token.

Any number of character sets can be defined in addition to the built-in allowing easy generation of the same scanner for different character sets.

This section defines the mapping of a character read in the scanner. This can for example be used to map lower case characters on the upper case, creating a case-insensitive scanner (as opposed to character sets which handle the complete representation of characters and should be changed by changing the setting of the set option).

To define a character map character classes are used. Characters are given on the left-hand side and the equivalent characters on the right-hand side. For example:

maps the digits to the characters with hexadecimal values F0 and F9.

The characters in the character class are ordered from the lowest to the highest character value. The mapping is then performed by assigning the lowest character on the left-hand side to the value of the character on the right-hand side, and so on until the highest value is reached.

If the set of characters on the right-hand side contains fewer characters than that on the left-hand side the highest value of the set with the least number of characters is assigned to the remaining characters of the left-hand side. For example:

maps all digits to the hexadecimal value 0 (zero).

If the left-hand side has fewer characters than the right-hand side the remaining characters are discarded. For example:

maps all digits to the ASCII values A to J respectively.

If the character class begins with a character that is greater than the last character in the specified set of characters, the characters are processed in reversed order. For example:

maps the character a to z to the ASCII values Z down to A and the digits 0 to 9 to the values 9 (11 octal) down to 0.

The mapping of the empty character set defines undefined values in the character set. It is recommended that the first mapping is to make all characters undefined.

This will disallow the use of any non mapped character. By default all characters are mapped to themselves. That is, the character A is mapped to the character A, etc.

The mapping of characters are given in the same manner as for the mapping of a character set. The only difference is that if characters are mapped to the empty set, those characters are skipped by the scanner. However the characters remain in the token string. This is especially significant when defining a scanner for languages such as FORTRAN where all blank characters are discarded in the input stream.

This section defines identifiers which can be used within regular expressions and/or a semantic action. These definitions can have the same name as a token defined in the rule definition sections. The name of a definition can not be given as a string (i.e. surrounded by quotes).

The definition is defined by using a regular expression in the same way as in the rule definition sections, except that no lookahead definition is allowed. A definition can also be specified without a regular expression. For example:

In the example above digit defines a rule as being a number 0 to 9. Integer is defined to be both a rule, a number of digits, and a semantic action. Copy on the other hand only defines a semantic action.

Semantic actions defined in this way can be used later in the rule and skip sections in place of an ordinary semantic action by using the %%DO keyword. For example:

This is further described in the description of semantic actions below.

The vocabulary section is used to specify the vocabulary used by the scanners defined for a specific vocabulary. A vocabulary also defines a set of tokens. The tokens can either be specified in a vocabulary file or directly after the name of the vocabulary in the vocabulary section. Each vocabulary may specify a number of scanners to recognise its set of tokens.

A token must always have an external token code which must be unique in the vocabulary. Tokens may be string tokens, in which case the name of the token is given as a quoted string. All string tokens are automatically defined in the first scanner in the vocabulary that defines them if they are not explicitly defined in a scanner.

ScannerMaker will complain if a token have not been defined, or explicitly undefined, in any of the scanners defined for the vocabulary.

where the rule definition section is

The scanner section defines a scanner. It consist of a scanner name, an optional screening section, an optional undefine token section, and rule definition sections. The name of the scanner is local for each vocabulary. That is, the same scanner name can be used in several vocabularies. However, a vocabulary may only define one scanner with a specific name.

The definition

defines a scanner which inherits definitions from another scanner. The new scanner copies all rules and semantic actions from the other scanner. For example:

defines newScanner to be a copy of oldScanner. The new scanner can then be expanded with new definitions but also restricted by removing a definition or altered by first removing a definition and then redefining them. For example:

if the old scanner has a definition of integer it is replaced by the new definition.

ScannerMaker will complain about tokens which have been defined in another scanner than the first and is only predefined in the first scanner. However, if the token is explicitly undefined in the first scanner, ScannerMaker will not complain since the token has been explicitly said to be undefined until it is later defined in a rule or skip section.

This section specifies which tokens in the scanner can be screened. By default all tokens can be screened.

This section undefines a predefined or inherited token. All rules associated to the token are marked as undefined.

In the rules section the tokens which the scanner should recognize are defined. The token could be both a token name and a string and the definition is a regular expression which can be followed by a lookahead regular expression. For example

defines that the externally visible token integer is to be an integer, as defined in the definition section above, and it is also an integer followed by a lookahead string ... This is a rather perplexing definition because of the use of the token integer defined in the definition section in the regular expression and the definition of an external visible token which may be defined in the vocabulary file. However this example shows that it is possible to use the same name for a token defined in the definition section and a token defined in the rules section without name clash. The example also shows the possibility to give multiple internal definitions for the same externally visible token. That is, both definitions return the same external token code.

An alternative definition of integer could be

which is an integer followed by an optional lookahead string ... Both definitions define exactly the same token but the first set of definitions creates a more efficient scanner because the lookahead is fixed to two characters while the other definition uses a variable length lookahead of either none or two characters.

The scanner always tries to find the longest possible token, even when using lookahead. For example

locates a string which has one or more digits followed by at least one digit. However, such a definition is absurd because there is no definite way to determine when the lookahead starts but with the convention to always locate the longest token, even this type of definitions has a well defined meaning. The rule

will find the same token as above but is more efficient because the lookahead has a fixed length of one character.

This section defines the tokens that should be skipped by the scanner, that is, not be passed to the caller of the scanner function. For example

skips all blank spaces (“space”, tabs and newline) in the input stream between tokens. Skip tokens are defined exactly in the same manner as for ordinary tokens defined in the rules section including lookahead. The rules for semantic actions are the same as for semantic rules in the rules section.

In the rule and skip_ sections_ an action can be placed after each token definition, before its trailing semicolon, ;. The action begins and ends with two percent characters, %%, or a reference to a semantic action defined in the definition section using the %%DO keyword.

All characters inside an action are considered to be code written in the same language as the scanner skeleton. This language is the same as the language specified in the TARGET option. The code in a semantic action is executed when the corresponding token is found. For example:

Definitions from the definition section can be referenced. For example:

Using the definitions above in the description of the definition section the integer found is copied to aBuffer.

Similarly, target language code can be specified in the declaration, context, reader, action, prehook and posthook_ sections_. Each of these target language code sections begins with its keyword and ends with anything starting with two percent characters. For example:

By default the character ` has special meaning in the target language code sections. This character is called the escape character (see Sec. 4.1.6, “The Escape Directive” in Part I, “ToolMaker System Description”). By giving an escape character the following character is unconditionally processed. For example, if double percent characters should be used in the code they should be preceded by the escape character. For example

is translated to

instead of terminating at the first pair of percent characters. The escape character is escaped by itself. Thus, `` means `.

The code in a semantic action is executed when a token that matches the corresponding definition is found. Each semantic action may be viewed as a function with the following definition:

In addition the code given in the action section is executed first. The token’s external code is determined by the value of the field smCode in the token structure (smToken→smCode in C) when the function is terminated. This variable is initially set to the value as specified in the vocabulary file or the vocabulary section or as set in a possible action section (see Sec. 12.2.8, “The Action Section”).

The external token code for the token found can be changed (simulating finding of another token) in two ways by either setting smToken→smCode to the new external code or by returning the new external code by executing a return statement. The external token codes should be one of the enumeration values defined for tokens in the vocabulary to which the current token belongs, or the predefined enumerators smSkipToken or smContinueToken.

When smSkipToken is returned the current token is skipped, as if it had been specified in the skip section.

When smContinueToken is returned continued scanning will be performed, Sec. 14.3.2, “Continued Scanning”.

A context is the main object in the generated scanner. Almost all functions operate on that object. A context consist of a buffer, source position, scanner, and user defined variables.

In object-oriented languages this type is declared as a class named smScContext with the structure components above as public members.

The context buffer is divided into two parts, the token and the input stream, where the input stream always follows the token. Initially the token length is zero and when end of text is found the input stream has a length of zero. The size of the context buffer can be found in the smSize field. Initially the length of the context buffer is zero.

The variable smText holds the last scanned token and smLength is the length of the token. The characters in smText may be altered freely but if any altered characters are skipped back into the input stream the source position calculation will be wrong if any newline characters was altered or inserted.

Great care should be taken not to alter any characters after the last character in the token permanently. It is alright to alter the character while in a semantic action and then restoring the old character before leaving the semantic action or calling the scanner recursively. For example, to convert a token representing an integer into an integer, the Unix standard function atoi could be used. However, this function requires that the string representation is null terminated but ScannerMaker does not null terminate a token string so this must be done explicitly.

It is very important to restore the character over-written by the null character as in the example above or else the next token would start with a null character.

If the scanning of a token exceeds the maximum token length or the reallocation to a larger buffer fails, characters in the buffer will be skipped. The number of characters saved equals to the minimum length of the token and the only characters saved are the last ones in the buffer. The variable smBufferOverflow holds the number of characters which are skipped. The source position will still however reference the true beginning of the character but the smLength will not include any skipped characters. Thus the true length of the token is the sum of smBufferOverflow and smLength.

If no overflow occurs smBufferOverflow will be zero.

Changing the context can be necessary when changing from one source of input to another. This can be achieved by simply replacing the current context variable with a new (created using the smNew function). To be able to restore the previous context the context buffers should be linked or stacked, which is the responsibility of the user

The change of a context should preferably be performed outside the actual generated scanner, e.g. in a function enclosing the smScan function, which recognises and handles situations when this is necessary.

The source position is only calculated if the appropriate source position directive is given in the source position section. The line number and column number start from one and the position from zero. The position is the number of characters read in this context before the token. The source position will always be correct with one exception. If altered characters are returned to the input stream by using smScSkip instead of smScModify and any newline is altered to a character other than the newline character or if a character is altered to a newline, then the source position will be computed incorrectly. However, if the number of newlines are the same the source position will be correct after the next newline following the altered characters. The suggestion is not to return any altered character with the smScSkip function.

When smScModify is used to return altered characters to the input stream any token found containing altered characters will have the source position of the token following the token which altered the input stream. For example

when the token hello is found, the token is altered to theis. If the source position of hello was line one and column five, then the next token should be found at line one and column ten. This is the line number which is reported by the, is, and the token following is.

The next positions gives the next token’s position. That is, the token following the current one.

Which scanner a context should use is determined by the value of the smScanner variable. Available scanners are determined by the description file defining the scanners. An enumeration type is defined containing an enumeration literal for each scanner. The name of the enumeration literal is the scanner prefix concatenated by the vocabulary name and scanner name surrounded by underscores and finally the characters Scanner as a suffix. For example, if the scanners main and comment are defined the following enumeration type is defined (if C is the target language):

By simply changing the value of the smScanner field in the context variable a new scanner is entered. The variable can be changed any time and the effect is immediate. For example, it is possible to change scanner in a semantic action and then continue scanning using the newly selected scanner.

For each vocabulary there is also an enumeration type defined containing enumeration literals for all tokens defined in that vocabulary. The name of the enumeration type is sm followed by the vocabulary name enclosed by underscores and followed by the characters ScToken. Each enumeration literal is named sm followed by underscore, vocabulary name, underscore, token name or external token code for a string token, underscore, and Token. For example, if C is the target language:

This function scans a new token. If successful, the token code is returned and the token structure or record is assigned the token code and source position, if used. If the reader, as defined in the reader section, returns a negative value this is immediately propagated as the return value of the smScan and the scanning is aborted.

This function is a so called constructor. It constructs a new context with the specified smScanner.

This function is a so called destructor. It destroys a context and its buffer.

This function changes the token by either replacing characters from the end of the token to the input stream, or by extending it by reading characters from the input stream. The number of characters replaced or read are given by the value of smLength. A negative value replaces characters and a positive value reads characters. The actual number of characters replaced or read are returned. For example,

returns the three last characters of the token to the beginning of the input stream. The length of the token will be three characters shorter. However, if it has a length of less than three characters, for example one character, only that many characters will be returned. If the reader, as defined in the reader section, needs to be called to fetch further characters from the input stream and it returns a negative value, this is immediately propagated as the return value of smScSkip and the skipping is terminated.

This function modifies the token or input stream in the same way as smScSkip but all affected characters (replaced to the input stream or appended to the token) are modified by characters from the specified buffer. For example

appends the token with three characters from the input stream and modifies them to be “123”. That is, the token now ends with “123”.

returns the three last characters of the token to the beginning of the input stream and replaces them with “123”. If the reader, as defined in the reader section, returns a negative value this is immediately propagated as the return value of smScModify and the modification is terminated.

Copy the token into the buffer specified. The token’s characters are not mapped. The copy starts to copy characters from the smFrom position up to but not including the smTo position from the current token. The number of characters copied is returned. For example, to copy all characters use:

Copy the token into the buffer specified in the function call. The characters of the token are mapped using the specified character map as specified in the map section. The copy starts to copy characters from the smFrom position up to but not including the smTo position from the current token. The number of characters copied is returned.

This function turns on or off checking of screened tokens for the specified scanner. If the scanner has screened tokens these are not recognized if screening is turned off.

This function turns on or off checking of screened tokens for the specified token. If the token has screened tokens these are not recognized if screening is turned off.

This function turns on or off checking of the specified token. If the token is a screened token it is not recognized if screening is turned off.

Inside any action or target language code section it is possible to call the scanner recursively. However smToken should never be passed to any called scanner because it will over-write the current token code. Also note that the variable smToken is not defined in the code section.

The current token is reset by a recursive call. That is, after a recursive call the smText and smLength will refer to the last scanner token. For example

After calling smScan() the string #include which could be found in smText is replaced by the next token, in this case hopefully a string.

It is also possible to continue scanning after a token is found by setting the external code to smContinueToken or returning smContinueToken in the action section or the semantic actions. The current token will be appended with the new token found after a continued scanning is made. The new token will be returned. That is, in the example below the complete string will be found in the last semantic action.

For example

or

Continued scanning can only be used in the action section and inside semantic actions.

Symbols in the ListerMaker description language are constructed from using upper case letters from the ISO-8859-1 character set, lower case letters (ISO-8859-1) and digits.

In the options section various options can be set. The available options for ListerMaker are described below. The term default describes the initial setting unless otherwise stated in the ToolMaker Common Description file when appropriate (see Sec. 3.1, “The ToolMaker Description File” in Part I, “ToolMaker System Description”).

These options can be overridden by options given on the command line when ListerMaker is invoked (see Ch. 17, The ListerMaker Command). If an option is not specified its default value is used. The default options are:

Note however that the settings of common options in the ToolMaker Common Description file influences the default values (see Sec. 4.1, “The Options Section” in Part I, “ToolMaker System Description”, and Sec. 6.4, “Prefix Management” in Part I, “ToolMaker System Description”).

Multiple message sections may be specified. Using the generated initialisation call (lmLiInit()) the section used may be selected during run-time. Example:

Lister works in three different phases, UNINITIALISED, COLLECTING and RETRIEVING. During the UNINITIALISED phase no calls except to initiate the Lister is legal. Calls to procedures logging messages is allowed in the COLLECTING phase, and calls for producing lists, retrieving messages and printing text is only allowed in the RETRIEVING phase. Transition between the COLLECTING and RETRIEVING phases is performed by the first call to lmList(), lmListm(), lmListsi() or lmMsg().

To sum up, the following functions are available in each phase:

In some cases a method of handling nested files is needed. This is for example the case with so called include-files in some programming languages. ListerMaker supplies functions to handle this feature.

Suppose that we want to create a C-preprocessor. The preprocessor has a directive, #include, which allows inclusion of secondary files containing C source.

To solve the problem of creating lists of such input using ListerMaker the function lmLiEnter() is used. When encountering the #include directive this function should be called with the name of the new (included) file and a source position where the file should be inserted (normally at the first position on the line following the #include directive.

During the RETRIEVING phase any messages logged using source positions indicating this included file will be shown (or returned using lmMsg()) before messages occurring after the #include directive in the top level file. So all messages are sorted correctly.

Note that the file component of the source position structure should differentiate between every instance of an included file since even if the same file is included more than once the context is different each time and different messages may be generated for every instance depending on the context.

The following extra functions are available if the include option is used:

Another major feature of Lister is the ability to handle listing of multiple top-level input files. These files have no hierarchical relations as is the case with included files, as described above.

As opposed to the include file handling this is used when multiple files are worked upon at the same time, for example a file compare program or a module interface verifier. This kind of applications require that a small number of related input files are analysed (the files having no hierarchical relation to each other). When creating a listing the files should appear in the same listing file, but separated, not nested.

This requires an array of file names, each index corresponding to the file number used in the source position structure, to be passed to Lister, as is the case in the parameter list for the lmListm() function, which is designed for this purpose. In this case the file numbers for the top level files must be from zero and up. Any further files may have any number.

The following extra functions are available if the Listings multiple; option is used:

The listing of multiple input files can also be handled separately as opposed to the multiple handling described above. This means that a call to a function (lmLists()) must be performed for each of the files. This makes it possible to handle output (using lmLiPrint()) between listings of each file.

The following extra functions are available if the Listings separate; option is used:

This character constant contains the value to be used as separator between concatenated insertion strings. Thus the operation to send two insertion strings to a message in one lmLog() call is to concatenate the two strings separated with the value lmSEPARATOR, and then to send the resulting string as the insertion string in the lmLog() call.

This type contains the enumerated values of the names of the sections given in the Message sections in the description file. There is one value for each named Message section constructed by prepending the lister prefix and an underscore, and appending an underscore and the text ‘Messages’ to the name given to the section, e.g. if the section was called ‘english’ the corresponding constant is called

One of these values must be transferred in the call to the lmLiInit() function to indicate which set of message templates to use.

This enumerated type has all severities exported from Lister as its value set. Values from this type may be combined to form sets used in lmList().

An lmSev constant containing the set of all severities (sevOK, sevINF, sevWAR, sevERR, sevFAT, sevSYS).

This enumerated type is used to indicate selected information to include in the listing file (or on the screen).

A set of lmTyp values appropriate for a tiny list, for example on the screen. Contains liSUM, liERR, liINCL and liHEAD.

A set of lmTyp values appropriate for listing to a list file. Also contains liOK, so as to also show source lines for which there are no messages.