er;

efine :parser <laration-part>ame>rguments-part>
        <ions-part>
        <initions-part>
        <ens-part>
        <es-part>
    enddefine;

-11 syntax interface to the LALR(1) parser generator.

Contents

ect headings to return to index

• Introduction
• Loading the Library
• An Example
• Structure of the Define Form
• . . The Declaration and Arguments Parts
• . . The Options Part
• . . The Definitions Part
• . . The Tokens Part
• . . The Rules Part
• Input to the Parser
• Structure of the Parser
• Additional Features
• . . Intermediate Actions in Rules
• . . Meta Symbols and Rules
• . . Operator Precedences
• . . Generating a Program File
• Error Handling
• . . Error Reporting
• . . Error Recovery
• Hints on Parser Development
• Further Examples

Introduction

define_parser is a *define_form which simplifies the construction of parsing procedures for LALR(1) languages. Its design is influenced heavily by other similar systems, most notably the Unix yacc utility, but integrated into the Poplog environment.

define-form allows the parser to be built around a grammar for the language: this is used to generate automatically the basic parsing engine, leaving the programmer free to concentrate on writing the action code which determines what the parser does once it has identified the particular language constructs. Parsers built in this way are quicker and simpler to write than those done by hand, especially if an appropriate grammar is already available from elsewhere (perhaps as part of a language specification); they are also easier to read, understand and modify at a later date. The technique has been proven over many years by the success of yacc and its derivatives.

define-form is built directly on the parser-generator utilities defined by LIB * LR_PARSER. Users who have not encountered similar systems before might like to consult the file HELP * LR_PARSER to get some background information about the LALR(1) system and how the basic parsing engine works. It should be noted that LALR(1) grammars are of most use in describing formal languages (including programming languages, command interpreters and the like) rather than natural languages.

e all define-forms, the define_parser syntax generates a procedure at the point at which it is compiled. You can, however, arrange for a Pop-11 program to be generated simultaneously which can be loaded at a later time to recreate the parsing procedure without using this library. This gives the maximum flexibility between development and delivery. Other features of the system include a choice of parsing engines (one for tracing and one for fast execution) and independence of the parser from the lexical representation of grammar tokens.

Loading the Library

order to use the define_parser syntax, your program must include the line:

er;

define-form will then be autoloaded on first use. You should mark and load this line now if you want to compile the examples in this file.

An Example

following example defines a parser for terms in the lambda calculus and illustrates the main features of the define-form. The definition is based around a grammar for lambda terms, the same as that used in the Lambda1 example from HELP * LR_PARSER.

er Lambda();

)' VAR:isword

   exp ::=
                \ VAR:x . exp:e      { [ABS ^x ^e] }
            |   appexp
            ;

   appexp ::=
                appexp:e1 aexp:e2    { [APP ^e1 ^e2] }
            |   aexp
            ;

   aexp ::=
                VAR:x                { [VAR ^x] }
            |   '(' exp:e ')'        { e }
            ;

tokens part of the definition declares the terminal symbols of the grammar, and defines recognisers which allow the parser to identify instances of the tokens in its input: the first four tokens are taken literally, but the VAR token is declared to be any other item satisfying the test isword. The quotes around the tokens '(' and ')' are necessary because unquoted these have a special meaning as part of the define-form syntax.

rules part simultaneously declares the non-terminal symbols, the start symbol and all the productions of the grammar. Each production can have a Pop-11 action (written inside the {} brackets) associated with it, which is run automatically when the rule is reduced. Symbols in a rule can have names attached which are bound to the symbol values during execution of the action code. The actions shown here build a parse tree reflecting the abstract syntax of lambda terms.

should try marking and loading this definition now. If it seems to take a long time, that could be because the define_parser library has to be autoloaded on first use. Compiling the definition a second time should be considerably quicker.

result of the definition is a procedure:

** <cedure Lambda>

run the parser, we need to provide it with a source of input. To keep the parser independent of any particular input format, input is obtained from a procedure which generates a sequence of items; these items are mapped to grammar tokens by means of the recognisers declared in the tokens part of the definition. By default, the parser will look for an input procedure called Lambda_input (which is, of course, the grammar name with _input added to the end) which is declared automatically by the define-form, and initialised to readitem:

=> ** <cedure readitem>

ng readitem means that the parser fits comfortably with standard Pop-11 input conventions, but the input procedure can be redefined as appropriate and for demonstration purposes we shall define it to work on single characters, stopping at the end of a line:

efine Lambda_input();
        lvars c = cucharin();
        while c == `\s` or c == `\t` do
            ;;; skip leading spaces
            cucharin() ->
        endwhile;
        if c == `\n` or c == termin then
            ;;; end of input
            termin;
        elseif strmember(c, '\\.()') or islowercode(c) then
            ;;; legal item
            consword(c, 1);
        else
            ;;; illegal item
            consstring(c, 1);
        endif;
    enddefine;

can then try some examples: to run these, you must mark and load both the line containing the procedure call, and the subsequent line of input.

t; x ** [VAR x]

t; \x.\y.x ** [ABS x [ABS y [VAR x]]]

t; (\x.xx)(\x.xx) ** [APP [ABS x [APP [VAR x] [VAR x]]] [ABS x [APP [VAR x] [VAR x]]]]

the input is syntactically incorrect and can't be parsed, the parser gives up with an error:

t; f(xy))

PARSE ERROR ;;; INVOLVING: )

same happens if the input contains something the parser doesn't recognise as a token -- in this case, a string:

t; f(f0)

PARSE ERROR ;;; INVOLVING: '0'

Structure of the Define Form

parser define-form has the syntax:

efine :parser <laration-part>ame>rguments-part>
        <ions-part>
        <initions-part>
        <ens-part>
        <es-part>
    enddefine

s defines a parsing procedure called <e>t may also, depending on any options specified, define a second, input procedure called:

<laration-part>ntrols the declaration of both identifiers.

<uments-part>ecifies any arguments to the parse procedure.

<ions-part>n be omitted. If present, it contains various options for controlling the behaviour of the parser generator.

<initions-part>n also be omitted. If present, it contains ordinary Pop-11 code which is compiled inside the procedure body. This is meant for the definition of local variables and procedures used within any subsequent action code.

<ens-part> compulsory. It declares the terminal symbols of the grammar and defines recognisers for them so that the parser can identify instances of tokens in its input.

<es-part> also compulsory. It declares the non-terminal symbols, start symbol and productions of the grammar and defines actions to be invoked whenever a rule is reduced during parsing.

define-form is read using the standard Pop-11 itemiser, so the usual itemisation rules apply. In particular, comments can appear anywhere. Macro-expansion is not done, except of course in those sections which are compiled as ordinary Pop-11 code.

The Declaration and Arguments Parts

<larations-part> the define-form controls the declaration of both the parser itself and the subsidiary input procedure (where necessary). It consists of any meaningful combination of the usual declarators:

ant lconstant vars lvars procedure

HELP * DEFINE if the meaning of any of these is unclear. The actual declaration is done with pop11_define_declare so any attributes not specified explicitly in the <laration-part>herit the defaults pertaining to a standard definition.

<uments-part>clares any arguments expected by the parser and can be omitted if there are none. It has the general form:

list>

re the <ument-list> a comma-separated sequence of arguments. Each argument is normally just a word, which is implicitly declared as lvars within the procedure body, but this default declaration can be overridden by prefixing the argument with an explicit declaration made up of declarators from the set:

dlocal vars procedure

<uments-part> superficially similar to the argument list of a standard procedure definition, but with two significant differences:

standard definition, declarations for the arguments follow the definition header, interspersed with declarations of local variables; any arguments not explicitly declared default to vars
• parser definition, the syntax does not allow for any following declarations, so declarations for the arguments are given as part of the argument list; arguments not explicitly declared default to lvars

The Options Part

<ions-part> the define-form has the general structure:

ptions
        <ion-sequence>
    endoptions

<ion-sequence> a possibly empty list of options, where each option has one of the forms:

;ue>

option <e> always a word; the <ue>f present) is typically a single item (word, string or number) but depends on the particular option. Adjacent options can be separated by commas.

ions specified in the <ions-part>ply only to the definition in which they occur. You can select options which apply globally to all parser definitions by assigning to the variable define_parser_options. If set, this must be a list of options, where a simple option is denoted by its name, and an option taking a value is denoted as a sub-list:

e]

ions from this global list are processed after those specified in the <ions-part> take precedence.

available options are summarised here, but many are discussed in more detail at relevant points throughout the text:

icts = <gt;<gt;
    Declares the number of conflicts expected in the parser: <gt; the
    number of SHIFT/REDUCE conflicts and <gt; the number of
    REDUCE/REDUCE conflicts. <gt;d <gt;st both be non-negative
    integers.

 = <e>
    Declares an alternative name for the parser's input procedure. The
    <e>gument must be a word; if omitted, it defaults to ""
    See the section headed Input to the Parser below.

    Passed on to the call to lr_build causing the generated parser to be
    added into the lr_parser property table keyed under the procedure
    name.

r = <e>
    Declares a name for the parser tables generated by lr_build. The
    <e>gument must be a word and is declared lconstant within
    the parser procedure, making it accessible from user code in the
    <initions-part>d the <es-part> the definition. If the
    <e>gument is omitted, it defaults to the word "r"

am = <ename>
    Writes a program to <ename>ich will recreate the parser
    without using the define-form, requiring less time and space to
    compile. The <ename>gument can be a word or string; a word
    will have the extension '.p' added automatically. If omitted, the
    <ename>faults to the procedure name. See the section headed
    Generating a Program File below.

nput
    Declares that the parser's input procedure has the call form

() ->tem, token_n)

generation of the input map. See the section headed Input to the Parser below.

t = <ename>
    Calls the procedure lr_report to write a report on the parser to
    <ename>he <ename>gument can be a word or string; on VMS
    systems, a word will have the extension '.lis' added automatically.
    If omitted, the <ename>faults to the procedure name.

ts = <t;
    Declares the default multiplicity of non-terminal symbols, i.e. the
    number of values expected from all symbols not explicitly qualified.
    The value <t;st be a non-negative integer.

ode
    Used in combination with LIB * SHOWCODE. If set, then the variable
    pop_show_code is set <e>ile the parser definition is compiled.

_checks
    Adds code to each user action to check that the number of results
    returned by the action matches that which the parser expects from
    the corresponding non-terminal symbol.

 = <bol>
    Declares <bol> the start symbol of the grammar: <bol>st
    be subsequently declared as a non-terminal symbol. The default start
    symbol is the first non-terminal declared.

n = <e>
    Declares an alternative name for the end-of-input marker. The <e>
    argument must be a word; if omitted, it defaults to "n"
    the section headed Input to the Parser below.

    Uses the lr_trace implementation of the LR(1) parsing algorithm in
    place of standard lr_parse. This produces the same results (albeit
    more slowly) but also generates a trace of the parse in an output
    file.

The Definitions Part

<initions-part> the define-form has the general structure:

efinitions
        <11-statement-sequence>
    enddefinitions

Pop-11 code is compiled in the usual way within the context of the parse procedure. This provides a place for defining local variables and procedures which are to be used in subsequent recogniser or action code, or for declaring dynamic local variables and actions.

The Tokens Part

<ens-part> the define-form has the general structure:

okens
        <en-definitions>
    endtokens

<en-definitions>nsists of a sequence of token definitions. This may be empty: it is possible to have a grammar with no terminal symbols, although its behaviour would be predictable.

imple token definition has one of three forms:

t;11-expression>

t;11-expression>

e complex definitions involving precedences are possible: these are described later. Adjacent token definitions are normally separated by a comma but this can be omitted for definitions consisting of the <en> alone.

h form of definition declares the item <en> a terminal symbol of the grammar. A token is always a word. You can write tokens inside string quotes, in which case they are read as strings but converted immediately to words using consword. There are three possible reasons for using quoted tokens:

   certain words are special to the parser syntax form and simply
        can't be used as tokens unquoted; the full list of these special
        words is:

ptions definitions enddefinitions tokens endtokens rules endrules , ; : = ::= | ( ) { }

   quoted tokens are read as strings, and so can contain characters
        which aren't normally allowed in words, e.g:

'...' '\n'

   using quotes consistently can be useful in distinguishing
        terminal and non-terminal symbols in grammar rules, e.g:

ession 'do' block 'endwhile'

, the tokens are the same written with or without quotes.

oken definition also defines a recogniser for the token it declares: the recogniser is simply a test which the parser can apply to an input item to determine whether it corresponds to that token.

the simplest definition form:

token is its own recogniser: the input item is compared against the token itself using "

the other definition forms:

t;11-expression> <en><11-expression>

<11-expression>rt is evaluated in the usual way. In the " case, the result of the expression is compared against the input item using the standard equality procedure; in the "se, the result itself is expected to be a procedure which is applied to the item.

ogniser expressions are evaluated at run-time, each time the recogniser is applied, so be wary of using tests such as:

r(% [a b c d] %)

re the closure will be repeatedly constructed. For efficiency, use the compile-time evaluation brackets:

define a local procedure in the <initions-part>

ognisers are applied to an input item in the order in which they were declared, and the first one returning a non-false result determines the token to which the item corresponds. More details about how input items are classified are given in the section headed Input to the Parser below.

The Rules Part

<es-part> the define-form has the general structure:

ules
        <e-definitions>
    endrules

<e-definitions>nsists of a sequence of rule definitions. This may not be empty: the grammar must have at least one non-terminal symbol with at least one rule.

basic form of a rule definition is:

ide>= <ht-hand-side>ction>

left-hand-side of a rule has two possible forms:

lt;tiplicity>

each case, the item <bol> declared as a non-terminal symbol of the grammar. The first non-terminal symbol declared is taken to be the start symbol of the grammar. The rules for non-terminal symbols are the same as those for tokens: symbols are always words, but may be written in string quotes where necessary. It is an error for a symbol previously declared as a token to be redeclared as a non-terminal symbol.

<tiplicity>rt of the left-hand-side is a non-negative integer which specifies the multiplicity of the symbol, i.e, how many results an instance of the symbol is expected to return. The default multiplicity is normally 1, but can be changed with the option results.

same symbol can appear on the left-hand-side of more than one rule but the multiplicity must be the same in each case. Where two or more adjacent rules share the same left-hand-side they can be abbreviated using the syntax:

ide>= <ht-hand-side-1>ction-1>

ht-hand-side-2>ction-2>
• ht-hand-side-n>ction-n>

Input to the Parser

Structure of the Parser

procedure <e> as originally given; its <laration>d the <uments>d their declarations are synthesised in an obvious way from the <larations-part>d <uments-part> the define-form.
1. <ens-part>d <es-part> the define-form declare the symbols and productions of a grammar. These are passed at compile- time to the procedure lr_build -- with the procedure <e>so used as the grammar name -- and the resulting parser structure which encodes the parsing tables for the grammar is bound to an lconstant identifier within the procedure body. The default name for the parser is a private one, but you can specify an alternative name with the option:

local definitions are simply copied from the <initions-part> of the define-form. This code is the first to be executed when the procedure is applied, so can be used to initialise the parse.
1. main action of the procedure lies in the final call to lr_parse which interprets the parsing tables constructed at (2). The interpreter requires two additional procedure arguments defined locally at (5) &. No code is executed after this call returns -- except, of course, for any dlocal exit actions included in the local definitions -- so this determines the result of the parse.

input procedure provides the input source for the parse: this is simply the input map discussed above. If the option raw_input is specified, this local definition is omitted and the base input procedure is passed directly to lr_parse.
1. reduce procedure is called once for each reduction in the parse. This is generated from the action code in the <es-part> the define-form and consists of a single go_on which switches on the rule number to select the appropriate action-code block. Code is added to the start of each action to declare the identifiers named on the right-hand-side of the rule and initialise them with items popped from the stack.

Additional Features

Intermediate Actions in Rules

Meta Symbols and Rules

Operator Precedences

'-' exp
• '*' exp
• '/' exp
• exp
• ER

'-' exp
• '*' exp
• '/' exp
• ' exp /****/
• ER

Generating a Program File

Error Handling

Error Reporting

Error Recovery

Hints on Parser Development

Further Examples