Russ Atkinson converted PGS to NPGS in March 1988 to produce Cedar/Mesa programs rather than binary tables stuffed into bcd files. A preliminary revision of the documentation has taken place, but there may still be errors in the more obscure sections.

Also, the TableCompiler is not included under NPGS.df. The TableCompiler is considered obsolete, since the tables produced are neither safe nor portable.

[James Eve wrote the bulk of this document in 1979. Doug Wyatt converted it to Tioga form and revised section 6 to describe the operaton of PGS and TableCompiler in Cedar. Much of Section 6.2 was derived from a brief memo by Ed Satterthwaite.]

The parser generator system (PGS) is a Mesa program which takes a context free grammar specified in Backus-Naur form as input and tests whether it is LALR(1); if the LALR(1) condition is satisfied, compacted binary tables are output which can be used in conjunction wth the Mesa parser. Ancillary tables are also output which simplify the writing of lexical routines to recognise the terminal symbols of the grammar. As a primary task of NPGS is to aid development the Mesa system itself a preprocessor is included which aids this.

The LALR(1) parsing algorithm is fairly widely held to be the best practical algorithm currently available; it has good space and time performance properties, it handles a larger subset of the context free grammars than other methods in common use and it allows a good syntax error repair capability to be added. The one snag is that the LALR(1) condition is far from intuitively obvious; checking that the condition holds requires substantial computation and in the event that it does not, a fair knowledge of the underlying theory may be needed to modify a grammar to make it meet the condition. A really good account of the theory has yet to be written, notational problems tend to obscure the underlying ideas. Probably the easiest starting point is the tutorial article "LR Parsing" by Aho and Johnson in Computing Surveys, 6(1974)74, the most comprehensive account readily available is in "The Theory of Parsing, Translating and Compiling" Volume 1, Prentice-Hall (1972), by Aho and Ullman; the algorithms used in NPGS are from Anderson, Eve and Horning, "Efficient LR(1) Parsers", Acta Informatica 2(1973)12 so the terminology here follows the latter paper, which is referenced subsequently as AEH.

In Cedar, NPGS.df is a CedarChest package, and can be retrieved and run using the normal Cedar methodology. Usually, NPGS takes a command line with the following form:

Such a command produces several files:

The files Defs.mesa and DefsImpl.mesa restrict themselves to portable Cedar/Mesa in the safe subset. These files define and produce the parse tables that are to be used by a parser (NPGSParser.mesa is an example of such a parser).

If the defs: Defs part is not given, the default name is the name of the type given in the TYPE: option in the Input.pgs file.

For use by non-Cedar programs, NPGS will produce Defs.mesa and DefsImpl.mesa without using any Cedar langauge features if the -M switch is given, as in the command:

In an effort to reduce the number of PGS tools the CuspPGS features have been incorporated into NPGS. To use the CuspPGS features use the -c switch, as in:

RRA: Most of this section discusses the format of the file when it is NOT in the form of a Cedar/Mesa program with comments supplying the productions. This section is retained for historical purposes, but the features described may not be fully retained by NPGS. Only the usage supported by the preprocessor (see Section 5 - The Preprocessor) is likely to be supported in the future.

The input file is treated as a sequence of tokens, where a token is defined to be a sequence of characters none of which are in the range [0C..' ]. Tokens are delimited by sequences of characters in this range. In addition to the tokens ::=, |,?,C and the integers which have special roles there are a number of tokens starting with the character pair || which control NPGS.

The input consists of five subsequences, directives, terminals, nonterminals, aliases and productions which must appear in this order.

Immediately preceeding the |'s or to the left of a token followed by ::= there will usually be an integer, the rule number, which may itself be preceded by the token C (upper case only). The rule number associates the production with a semantic routine (an arm of a SELECT statement) which is to be invoked by the parsing algorithm whenever a string derived from the associated production is recognised. Some productions, of the form nonterminal ::= nonterminal, have no semantic significance and serve merely to assert that members of one syntactic class are also members of some larger class. Chains of such productions appear in expression grammars (expr ::= term, term ::= factor, factor ::= primary, etc.) and can significantly reduce the speed of parsing. The appearance of the token C is an assertion that the following production is of the specified form and has no semantic processing associated thereby permitting NPGS to eliminate all references to it with an increase in speed of parsing.

The input phase of NPGS uses the Mesa parsing routine and parsing tables of its own construction so there is clearly a grammar specifying the form of the input. The description given above was preferred as an introduction to the input format since it covers only the essentials. NPGS will, on request, echo its input interspersed with other information in a formatted form. As there was a requirement that this output should also be acceptable as input, the grammar allows a rather wider class of input forms but information other than that described is simply discarded during re-input. The grammar appears in the appendix.

It should be clear that the terminal symbols of NPGS grammar cannot be used as tokens in a client grammar, a syntax error would result. This is not likely to be a problem to most clients insofar as the symbols starting with || are concerned (which is why this curious system was adopted) but there are also ::=, |, ?, C and GOAL some of which may well appear in a client grammar. Finally of course NPGS grammar contains all of them. The standard solution is used; if |, ?, or C are required as tokens in a client grammar they must be specified as '|, '? and 'C. Multi-character symbols such as ::= must be specified as "::=". The only special treatment that these quoted symbols receive at the hands of NPGS is in building the tables for use by the scanner; any two character token beginning with a single quote has the quote removed; similarly any token of three or more symbols where the first and last are double quotes has these bracketing quotes stripped.

Four output files are normally constructed, a record of the input, a log, a definitions file which contains definitions of aliased terminal symbols and some ranges defining the sizes of the various tables, and the implementations file, which contains procedures to quickly build the tables on demand. The definitions and implementations files are written in Cedar/Mesa. These files must be compiled and bound with the Mesa parser and a suitably modified version of the Mesa scanner.

The preprocessor is invoked if the input file name has the extension .pgs. Its function arises from the following considerations. For maintenance purposes it is more or less essential that each arm of the SELECT statement implementing the semantic processing routines in the Mesa compiler has comments displaying those productions associated with this arm. The test preceding the => symbol in the arm is the rule number for these productions. As Mesa evolves, changes are made to the grammar, productions associated with one arm must be moved to another, new productions and new arms are introduced and periodically it is necessary to renumber the rules in a systematic fashion in order to find things (there being being over 200 arms). The bookkeeping necessary to ensure that the story told by the SELECT statement is consistent with that told to NPGS in the input file is tiresome and error prone. Most of the data needed by NPGS is present in the SELECT statement and by adding the rest only one copy of the grammar need be maintained and the reassignment of rule numbers can be mechanised.

The preprocessor expects a Mesa program module as input and it scans for the sequence

after which it expects to find data relevent to it. On encountering CR, or Bravo's ControlZ ... CR sequence, it checks whether the next printing characters open a Mesa comment or not; if they do then more data is expected otherwise the end of the data associated with a particular select arm is presumed and a search is instituted for the next.

Supposing the input file name given was George.pgs, then during the scan the preprocessor copies a modified copy of the file to George.mesa. The modification is a trivial one; as the sequences,

are encountered, the next integer in the sequence 0,1,2,... is substituted before the => symbol.

The rather crude procedure used to locate the grammatical information in the program text places constraints on the program module containing it. In particular it precludes comments in a fairly natural place in any other SELECT statements that may appear in the module which also use integer tests. On the other hand anything approaching parsing the text is out since it merely replaces one updating problem with another.

Since NPGS constructs tables using the new rule numbers just assigned, arms of the SELECT statement can be reordered to group logically related arms together without making the search for an arm with a given rule number tedious.

In the comments associated with SELECT arms (other than the first encountered) the preprocessor expects to find only productions. Here each production is specified in full, its left part token followed by either ::= or (to designate a chain production) ::=C followed by the right part tokens.

Comments preceding the first production contain the additional information needed. This information in order of occurrence is,

Nonterminal symbols are deduced from the tokens to the left of ::= tokens. If the TERMINALS: sequence appears only these symbols are taken to be terminals. In its absence any token in a production which is not a nonterminal according to the previous definition is a terminal. Omitting this sequence means that typing errors define terminal symbols!

From a file of this form (see the example at the end of the appendix), the preprocessor constructs a scratch file in the format specified in section 3, with the directives ||INPUT, ||CHAIN and ||LISTS, which it passes to the input phase of NPGS.

The preprocessor only generates one error message, "Directives incorrect or out of sequence". No further processing occurs in this situation so the message is displayed, followed by the request to type a character to terminate execution.

When inserting new arms in the SELECT statement there is no need (so far as the preprocessor is concerned) to use an integer distinct from those on other arms but it is probably not a good idea. The preprocessor will recognise ? as an alternative to a digit sequence.