Subversion Repositories tendra.SVN

<?xml version="1.0" standalone="no"?>

<!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook XML V4.4//EN"

"http://www.oasis-open.org/docbook/xml/4.4/docbookx.dtd">

<!--

  $Id$

-->

<book>

  <bookinfo>

    <title>The sid users' guide</title>

    <corpauthor>The TenDRA Project</corpauthor>

    <author>

      <firstname>Jeroen</firstname>

      <surname>Ruigrok van der Werven</surname>

    </author>

    <authorinitials>JRvdW</authorinitials>

    <pubdate>2006</pubdate>

    <copyright>

      <year>2006</year>

      <holder>The TenDRA Project</holder>

    </copyright>

    <copyright>

      <year>1998</year>

      <holder>DERA</holder>

    </copyright>

  </bookinfo>

  <chapter id="introduction">

    <title>Introduction</title>

    <para>This document describes how to use the <code>sid</code> parser

      generator. It was written for <code>sid</code> version 1.9. The

      main features of each version of <code>sid</code> are listed

      below:</para>

    <itemizedlist>

      <listitem>

        <para><code>sid</code> 1.0 - this was the first version of

          <code>sid</code> to support attribute grammars. The output

          language was C.</para>

      </listitem>

      <listitem>

        <para><code>sid</code> 1.1 - this was a bug fix version of

          <code>sid</code> 1.0.</para>

      </listitem>

      <listitem>

        <para><code>sid</code> 1.2 - this version of <code>sid</code> added

          predicates, exception handling, improved inlining options, and a

          grammar test pseudo-language.</para>

      </listitem>

      <listitem>

        <para><code>sid</code> 1.3 - this version of <code>sid</code> added

          anonymous rules, and a better syntax for the C specific

          information.</para>

      </listitem>

      <listitem>

        <para><code>sid</code> 1.4 - this was a bug fix version of

          <code>sid</code> 1.3.</para>

      </listitem>

      <listitem>

        <para><code>sid</code> 1.5 - this was a bug fix version of

          <code>sid</code> 1.4. The command line option syntax changed in

          this release as well.</para>

      </listitem>

      <listitem>

        <para><code>sid</code> 1.6 - this version of <code>sid</code>

          changed the input syntax, added scoped rules, and removed basics

          (replacing them with terminal symbols). It also added a stricter

          ISO C language.</para>

      </listitem>

      <listitem>

        <para><code>sid</code> 1.7 - The syntax of the actions file changed

          slightly in this version. The error messages and recovery from

          syntax errors were also improved in this version.  This version

          also added explicit call by reference support (rather than the

          inconsistent function call semantics of earlier versions). The

          command line options changed in this version, to support language

          specific options, and the <code>strict-ansi-c</code> language was

          dropped. Non-local variables were also added.</para>

      </listitem>

      <listitem>

        <para><code>sid</code> 1.8 - Initialisers were added for non-local

          variables. Assignment was added.</para>

      </listitem>

      <listitem>

        <para><code>sid</code> 1.9 - this was a bug fix version of

          <code>sid</code> 1.8.</para>

      </listitem>

    </itemizedlist>

    <para><code>sid</code> turns specifications of languages into

      programs that recognise those languages. One of the aims of

      <code>sid</code> was to separate the specification of the

      language to be recognised from the language that the recogniser

      program is written in. For this reason, input to <code>sid</code>

      is split into two components: output language independent

      information, and output language dependent information.</para>

    <para>At present, <code>sid</code> will only output programs in C

      (either ISO or pre-ISO), but it is designed so that adding new

      output languages should be fairly simple. There is one other

      pseudo-language: the test language. This is used for testing

      grammars and the transforms, but will not output a parser.</para>

  </chapter>

  <chapter id="grammar">

    <title>Grammars</title>

    <sect1 id="parsing">

      <title>Parsing</title>

      <para>There are two phases in traditional language recognition that

        are relevant to <code>sid</code>: the first is lexical analysis

        (breaking the input up into terminal symbols); the second is

        syntax analysis or parsing (ensuring that the terminal symbols in

        the input are in the correct order).</para>

      <para><code>sid</code> currently does very little to help with

        lexical analysis. It is possible to use <code>sid</code> to

        produce the lexical analyser, but <code>sid</code> provides no

        real support for it at present. For now, the programmer is

        expected to write the lexical analyser, or use another tool to

        produce it.</para>

      <para>The lexical analyser should break the input up into a series

        of terminals. Each of these terminals is allocated a number. In

        <code>sid</code>, these numbers range from zero to the maximum

        terminal number (specified in the grammar description). The

        terminals may also have data associated with them (e.g. the value

        of a number), known as the attributes of the terminal, or the

        results of the terminal.</para>

      <para><code>sid</code> generates the parser. The parser is a program

        that reads the sequence of terminals from the lexical analyser,

        and ensures that they form a valid input in the language being

        recognised. If the input is not valid, then the parser will fail

        (<code>sid</code> provides mechanisms to allow the parser to

        recover from errors).</para>

    </sect1>

    <sect1 id="context-free">

      <title>Context free grammars</title>

      <para>This section provides a brief introduction to grammars. It is

        not intended to be an in-depth guide to grammars, more an

        introduction which defines some terminology.</para>

      <para><code>sid</code> works with a subset of what are known as

        context free grammars. A context free grammar consists of a set

        of input symbols (known as terminals), a set of rules

        (descriptions of what are legal forms in the language, also known

        as non-terminals), and an entry point (the rule from which the

        grammar starts).</para>

      <para>A rule is defined as a series of alternatives (throughout this

        document the definition of a rule is called a production - this

        may conflict with some other uses of the term). Each alternative

        consists of a sequence of items. An item can be a terminal or a

        rule. As an example (using the <code>sid</code> notation, which

        now looks unlike the conventional syntax for grammars), a comma

        separated list of integers could be specified as:

        <programlisting>

list-of-integers = {

integer ;

||

integer ;

comma ;

list-of-integers ;

} ;

        </programlisting></para>

      <para>This production contains two alternatives: the first matches the

        terminal <code>integer</code>; the second matches the sequence of

        terminals <code>integer</code> followed by <code>comma</code>,

        followed by another list of integers.</para>

      <para>There is much documentation available on context free grammars

        (and other types of formal grammar). The reader is advised to

        find an alternative source for more information.</para>

    </sect1>

    <sect1 id="sid-grammar">

      <title>sid grammars</title>

      <para><code>sid</code> grammars are based upon a subset of context

        free grammars, known as LL(1) grammars. The main property of such

        grammars is that the parser can always tell which alternative it

        is going to parse next by looking at the current terminal symbol.

        <code>sid</code> does a number of transforms to turn grammars

        that are not in this form into it (although it cannot turn all

        possible grammars into this form). It also provides facilities

        that allow the user to alter the control flow of the parser.</para>

      <para><code>sid</code> makes the following changes to the context

        free grammars described above:</para>

      <orderedlist>

        <listitem><para>There may be more than one entry point to the

          grammar.</para></listitem>

        <listitem><para>As well as being a rule or a terminal, an item may be

          an action, a predicate or an identity. An action is just a user

          supplied function. A predicate is a cross between a basic and an

          action (it is a user defined function but it may alter the control

          flow). An identity is like an assignment in a conventional

          programming language.</para></listitem>

        <listitem><para>Rules may take parameters and return results (as may

          actions; terminals may only return results). These may be

          passed between items using names.</para></listitem>

        <listitem><para>Each rule can have an exception handler associated

          with it.  Exception handlers are used for error recovery when the

          input being parsed does not match the grammar.</para></listitem>

        <listitem><para>Rules may be anonymous.</para></listitem>

        <listitem><para>Rules may have non-local names associated with them.

          These names are in scope for that rule and any rules that are

          defined inside it. The value of each non-local name is saved on

          entry to the rule, and restored when the rule is

          exited.</para></listitem>

      </orderedlist>

    </sect1>

  </chapter>

  <chapter id="overview">

    <title>Overview</title>

    <para><code>sid</code> takes the input grammar and applies several

      transformations to it, before it produces the parser. These

      transformations allow the language descriptions to be written in

      a slightly more natural form than would otherwise be

      necessary.</para>

    <sect1 id="left-recursion">

      <title>Left recursion elimination</title>

      <para>The first transformation is to eliminate any left recursive

        productions, replacing them with right recursive ones. This

        transforms a set of rules of the form:

        <programlisting>

Ai = Aj Bji, Ci

        </programlisting>

        into:

        <programlisting>

Ai = Cj Xji

Xji = Bjk Xki, Yji

        </programlisting>

        where <code>Yji</code> is the identity function if <code>i</code>

        equals <code>j</code>, and an error otherwise. In order for this

        transformation to work, the following conditions must hold:

        <orderedlist>

          <listitem>

            <para>The parameter type for all <code>Ai</code> must be the

              same.</para>

          </listitem>

          <listitem>

            <para>The result type for all <code>Ai</code> must be the

              same.</para>

          </listitem>

          <listitem>

            <para>The exception handlers for all <code>Ai</code> must be the

              same.</para>

          </listitem>

          <listitem>

            <para>The parameters to each left recursive call to some

              <code>Aj</code> must be exactly the formal parameters to the

              calling rule <code>Ai</code>.</para>

          </listitem>

          <listitem>

            <para>Any non-local name referenced by any rule must be in scope

              for all rules.</para>

          </listitem>

          <listitem>

            <para>A rule may not define non-local variables unless it is the

              only entry point into the cycle (i.e. there is only one named

              rule in the cycle).</para>

          </listitem>

        </orderedlist>

        <code>sid</code> will report an error if these conditions are not

        met.</para>

    </sect1>

    <sect1 id="factoring">

      <title>Factoring</title>

      <para>The second major transformation is to factor the grammar. It is

        possible that this phase could go on for ever, so there is a limit to

        the number of rules that can be generated. This limit may be changed

        (see the <link linkend="invoke">invocation section</link>). In

        practice it is rare for this to happen.</para>

      <para>The factoring phase tries to increase the number of language

        specifications that <code>sid</code> can produce a parser for, by

        factoring out common initial items in alternatives, e.g.:

        <programlisting>

X = {

a ; b ;

||  a ; c ;

} ;

        </programlisting>

        would be transformed into something like:

        <programlisting>

X = {

a ; X1 ;

} ;

X1 = {

b ;

||  c ;

} ;

        </programlisting></para>

      <para>It will also expand calls to rules at the beginning of

        alternatives if this is necessary to allow the parser to be produced

        (this is the phase that the limit is needed for). The expansions are

        done in the following cases:

        <orderedlist>

          <listitem>

            <para>If the rule is see-through (i.e. there is an expansion of

              the rule that does not contain any terminals or predicates) and

              its first set contains terminals in the first set of the rest of

              the alternative.</para>

          </listitem>

          <listitem>

            <para>If the rule has a predicate in its first set.</para>

          </listitem>

          <listitem>

            <para>If the rule has terminals in its first set that are also in

              the first set of another alternative that does not begin with

              the same rule.</para>

          </listitem>

        </orderedlist></para>

      <para>If the rule being expanded contains an exception handler, and it

        is not identical to the exception handler in the enclosing rule, then

        an error will occur. Similarly if the rule being expanded defines any

        non-local variables then an error will occur.</para>

    </sect1>

    <sect1 id="optimise">

      <title>Optimisations</title>

      <para>After these two transformations, <code>sid</code> performs some

        optimisations on the grammar, such as reducing multiple copies of

        identical rules, removing tail recursion, inlining all basic rules,

        inlining single alternative rules, inling rules used only once, and

        inlining everything that can be inlined. All of the inlining is

        optional.</para>

      <para>After these optimisations, <code>sid</code> checks the language

        description to ensure that it is possible to produce a parser for it,

        and if so it outputs the parser.</para>

    </sect1>

  </chapter>

  <chapter id="invoke">

    <title>Invocation</title>

    <para><code>sid</code> should be invoked in the following manner:

      <programlisting>

sid options input-files output-files

      </programlisting></para>

      <para>The options are described later. The input files should be a

        number of input file names dependent upon the output language. The

        first input file is the <code>sid</code> grammar file. In the case of

        either C dialects there should be one other input file that provides C

        specific information to <code>sid</code>. The number of output files

        is also language specific. At present, two output files should be

        specified for the C languages. The first should be a <code>.c</code>

        file into which the parser is written; the second should be a

        <code>.h</code> file into which the terminal definitions and external

        function declarations are written.</para>

    <para>The options list should consist of zero or more of the following

      options. There are short forms for each of these options as well; see

      the <code>sid</code> manual page for more information on

      invocation.</para>

    <itemizedlist>

      <listitem>

        <para>--dump-file <filename>FILE</filename></para>

        <para>This option causes intermediate dumps of the grammar to be

          written to the named file. The format of the dump files is similar

          to the format of the grammar specification, with the following

          exceptions:</para>

        <orderedlist>

          <listitem>

            <para>Predicates are written with the predicate result replaced

              by the predicate identifier (this will always be zero), and

              the result is followed by a <code>?</code> to indicate that it

              was a predicate. As an example, the predicate:

            <programlisting>

( b, ? ) = <pred> ( a )

            </programlisting>

            would be printed out as:

            <programlisting>

( b : Type1T, 0 : Type2T ) ? = <pred> ( a : Type3T )

            </programlisting></para>

          </listitem>

          <listitem>

            <para>Items that are considered to be inlinable are prefixed by

              a <code>+</code>. Items that are tail calls which will be

              eliminated are prefixed by a <code>*</code>.</para>

          </listitem>

          <listitem>

            <para>Nested rules are written at the outer level, with names of

              the form

              <code>outer-rule::....::inner-rule</code>.</para>

          </listitem>

          <listitem>

            <para>Types are provided on call parameter and result

              tuples.</para>

          </listitem>

          <listitem>

            <para>Inline rules are given a generated name, and are written

              out as a call to the generated rule (and a definition

              elsewhere).</para>

          </listitem>

        </orderedlist>

      </listitem>

      <listitem>

        <para>--factor-limit <token>LIMIT</token></para>

        <para>This option limits the number of rules that can be created

          during the factorisation process. It is probably best not to change

          this.</para>

      </listitem>

      <listitem>

        <para>--help</para>

        <para>This option writes a summary of the command line options to the

          standard error stream.</para>

      </listitem>

      <listitem>

        <para>--inline <token>INLINES</token></para>

        <para>This option controls what inlining will be done in the output

          parser. The inlines argument should be a comma separated list of the

          following words:

          <itemizedlist>

            <listitem>

              <para><code>SINGLES</code></para>

              <para>This causes single alternative rules to be inlined. This

                inlining is no longer performed as a modification to the

                grammar (it was in version 1.0).</para>

            </listitem>

            <listitem>

              <para><code>BASICS</code></para>

              <para>This causes rules that contain only basics (and no

                exception handlers or empty alternatives) to be inlined. The

                restriction on exception handlers and empty alternatives is

                rather arbitrary, and may be changed later.</para>

            </listitem>

            <listitem>

              <para><code>TAIL</code></para>

              <para>This causes tail recursive calls to be inlined. Without

                this, tail recursion elimination will not be

                performed.</para>

            </listitem>

            <listitem>

              <para><code>OTHER</code></para>

              <para>This causes other calls to be inlined wherever possible.

                Unless the <code>MULTI</code> inlining is also specified, this

                will be done only for productions that are called

                once.</para>

            </listitem>

            <listitem>

              <para><code>MULTI</code></para>

              <para>This causes calls to be inlined, even if the rule being

                called is called more than once. Turning this inlining on

                implies <code>OTHER</code>. Similarly turning off

                <code>OTHER</code> inlining will turn off <code>MULTI</code>

                inlining. For grammars of any size, this is probably best

                avoided; if used the generated parser may be huge (e.g. a C

                grammar has produced a file that was several hundred MB in

                size).</para>

            </listitem>

            <listitem>

              <para><code>ALL</code></para>

              <para>This turns on all inlining.</para>

            </listitem>

          </itemizedlist>

          In addition, prefixing a word with <code>NO</code> turns off that

          inlining phase. The words may be given in any case.  They are

          evaluated in the order given, so:

          <programlisting>

--inline noall,singles

          </programlisting>

          would turn on single alternative rule inlining only, whilst:

          <programlisting>

--inline singles,noall

          </programlisting>

          would turn off all inlining. The default is as if <code>sid</code>

          were invoked with the option:

          <programlisting>

--inline noall,basics,tail

          </programlisting></para>

      </listitem>

      <listitem>

        <para id="lang">--language <token>LANGUAGE</token></para>

        <para>This option specifies the output language. Currently this should

          be one of <code>ansi-c</code>, <code>pre-ansi-c</code> and

          <code>test</code>. The default is <code>ansi-c</code>.</para>

        <para>The <code>ansi-c</code> and <code>pre-ansi-c</code> languages

          are basically the same. The only difference is that

          <code>ansi-c</code> initially uses function prototypes, and

          <code>pre-ansi-c</code> doesn't. The C language specific options

          are:

          <itemizedlist>

            <listitem>

              <para><code>prototypes, proto, no-prototypes,

                no-proto</code></para>

              <para>These enable or disable the use of function prototypes.

                By default this is enabled for <code>ansi-c</code> and

                disabled for <code>pre-ansi-c</code>.</para>

            </listitem>

            <listitem>

              <para><code>numeric-ids, numeric, no-numeric-ids,

                no-numeric</code></para>

              <para>These enable or disable the use of numeric identifiers.

                Numeric identifiers replace the identifier name with a number,

                which is mainly of use in stopping identifier names getting

                too long. The disadvantage is that the code becomes less

                readable, and more difficult to debug. Numeric identifiers are

                not used by default.</para>

            </listitem>

            <listitem>

              <para id="casts"><code>casts, cast, no-casts,

                no-cast</code></para>

              <para>These enable or disable casting of action and assignment

                operator immutable parameters. If enabled, a parameter is cast

                to its own type when it is substituted into the action. This

                will cause some compilers to complain about attempts to modify

                the parameter (which can help pick out attempts at mutating

                parameters that should not be mutated). The disadvantage is

                that not all compilers will reject attempts at mutation, and

                that ISO C doesn't allow casting to structure and union types,

                which means that some code may be illegal. Parameter casting

                is disabled by default.</para>

            </listitem>

            <listitem>

              <para><code>unreachable-macros, unreachable-macro,

                unreachable-comments, unreachable-comment</code></para>

              <para>These choose whether unreachable code is marked by a macro

                or a comment. The default is to mark unreachable code with a

                comment <code>/*UNREACHED*/</code>, however a macro

                <code>UNREACHED ;</code> may be used instead, if

                desired.</para>

            </listitem>

          </itemizedlist>

          The <code>test</code> language only takes one input file, and

          produces no output file. It may be used to check that a grammar is

          valid. In conjunction with the dump file, it may be used to check

          the transformations that would be applied to the grammar. There are

          no language specific options for the <code>test</code>

          language.</para>

      </listitem>

      <listitem>

        <para>--show-errors</para>

        <para>This option writes a copy of the current error messages to the

          standard output. See the manual entry for more details about

          changing the error message content.</para>

      </listitem>

      <listitem>

        <para>--switch <token>OPTION</token></para>

        <para>This passes through <token>OPTION</token> as a language specific

          option. The valid options are described

          <link linkend="lang">above</link>.</para>

      </listitem>

      <listitem>

        <para>--tab-width <token>NUMBER</token></para>

        <para>This option specifies the number of spaces that a tab occupies.

          It defaults to 8. It is only used when indenting output.</para>

      </listitem>

      <listitem>

        <para>--version</para>

        <para>This option causes the version number and supported languages to

          be written to the standard error stream.</para>

      </listitem>

    </itemizedlist>

  </chapter>

  <chapter id="grammar-file">

    <title>The sid grammar file</title>

    <para>The <code>sid</code> grammar file should always be the first input

      file specified on the command line. It provides an output language

      independent description of the language to be recognised. The file is

      split up into a number of different sections, each of which begins with

      a section header. All sections must be included, although it is possible

      to leave most of them empty. The following sections exist at present:

      type declaration, terminal declaration, rule definition, and grammar

      entry points. They must appear in that order. The sections are detailed

      below, after the lexical conventions.</para>

    <sect1 id="grammar-lex">

      <title>Lexical conventions</title>

      <para>Almost all non-printable characters (but definitely space, tab,

        newline and form-feed) are considered to be white space, and are

        ignored other than to separate other tokens. In addition, two comment

        forms are recognised: the C comment syntax, where comments begin with

        <code>/*</code>, and end with <code>*/</code>, although unlike C these

        comments nest properly; and the C++ line comment syntax, where

        comments begin with <code>//</code>, and are terminated at the end of

        the line. Comments are treated in the same way as white space

        characters.</para>

      <para>Section headers are enclosed in percent characters, and are case

        insensitive. The following section headers are currently

        recognised:

        <programlisting>

%types%

%terminals%

%productions%

%entry%

        </programlisting></para>

      <para>Identifiers must begin with a letter, an underscore or a hyphen.

        This may be followed by zero or more letters, digits, underscores and

        hyphens. Identifiers are case sensitive. The following are all legal

        identifiers:

        <programlisting>

expression      mult-expr       plus_expr       expr-1

        </programlisting></para>

      <para>Identifiers are split into two namespaces: local names have one

        space; types, actions, rules, non-local names and terminals share the

        other namespace, so it is not possible to have an identifier that is a

        type as well as being a rule for example.</para>

      <para>The following symbols are also used:

        <programlisting>

&   ;       =       [       :       ]       !       ,

||      $       ?       {       }       (       )       <

>    ->   ::      ##

        </programlisting></para>

        <para>All other characters are illegal.</para>

    </sect1>

    <sect1 id="type-decl">

      <title>The type declaration section</title>

      <para>The first section is the type declaration section. This begins

        with the types section header, followed by the names of all of the

        types used by the grammar. Each type name should be terminated by a

        semicolon. An example of the type declaration section follows:

        <programlisting>

%types%

NumberT ;

StringT ;

        </programlisting>

        This declares two types: <code>NumberT</code> and

        <code>StringT</code>. There is no requirement for the type names to

        resemble names in the target language (in fact this should be avoided,

        as it is possible to use many different target languages).  All types

        used in the grammar must be declared here. Similarly, all types

        declared here must be used in the grammar.</para>

    </sect1>

    <sect1 id="term-decl">

      <title>The terminal declaration section</title>

      <para>After the type declaration section comes the terminal declaration

        section. This section declares the terminals that will be used by the

        grammar. A terminal is a recogniser for a symbol in the input alphabet

        of the language to be recognised. It is possible to declare terminals

        that are not used by the grammar.</para>

      <para>The section begins with its section header, followed by the

        declarations of the terminals. Each terminal declaration begins with

        the name of the terminal being defined, followed by its type, and

        terminated by a semicolon. If the terminal is not used in the grammar,

        the declaration should be preceded by a <code>!</code> symbol.</para>

      <para>A type (for terminals, rules and actions) is written as a colon,

        followed by the parameter tuple, followed by the <code>-&gt;</code>

        symbol, followed by the result tuple. If the type is zero-tuple to

        zero-tuple, then the type may be omitted. A tuple consists of a comma

        separated sequence of name-type pairs (with the name and type being

        separated by a colon), surrounded by parentheses. For parameter

        tuples, the type may be suffixed by a <code>&amp;</code> symbol,

        indicating that call by reference should be used (the default is call

        by copy). For declarations, the names should be omitted. For

        terminals, the parameter type must be the zero-tuple.</para>

      <para>The simplest type of terminal declaration is as follows:

        <programlisting>

terminal1 ;

        </programlisting></para>

      <para>This means the same as:

        <programlisting>

terminal1 : () -> () ;

        </programlisting></para>

      <para>An example of a more complex terminal declaration is:

        <programlisting>

terminal2 : () -> ( :StringT ) ;

        </programlisting></para>

      <para>If these terminals were not to be used in the grammar, they should

        be declared as:

      <programlisting>

!terminal1 ;

!terminal2 : () -> ( :StringT ) ;

      </programlisting></para>

    </sect1>

    <sect1 id="rule-defn">

      <title>The rule definition section</title>

      <para>The rule definition section follows the terminal declaration

        section. It begins with the section header, followed by the

        definitions and declarations of all of the rules used in the grammar,

        and the declarations of all of the actions used in the grammar.</para>

      <para>Rule declarations look identical to terminal declarations, e.g.:

        <programlisting>

rule1 : ( :NumberT ) -> ( :NumberListT ) ;

rule2 ;

        </programlisting></para>

      <para>Action declarations are similar, although the names are surrounded

        by angle brackets, e.g.:

        <programlisting>

<action1> : ( :StringT & ) -> () ;

<action2> ;

        </programlisting></para>

      <para>A declaration (or a definition) may be prefixed with the

        <code>::</code> symbol. This symbol forces the definition into the

        outermost scope. Scopes are described later on.</para>

      <para>A rule definition (called a production) looks something like the

        following:

        <programlisting>

add-expr : () -> ( v : NumberT ) = {

v1 = mul-expr ;

plus ;

v2 = expr ;

v  = <add> ( v1, v2 ) ;

||

v1 = mul-expr ;

minus ;

v2 = expr ;

v  = <subtract> ( v1, v2 ) ;

##

v = <ex> ;

} ;

        </programlisting></para>

      <para>The production begins with the rule name, followed by the

        parameter and result names and types (in this case, the rule name is

        <code>add-expr</code>, there are no parameters, and there is one

        result name <code>v</code> of type <code>NumberT</code>). This may

        optionally be followed by local declarations (there are none here -

        they are described later).</para>

      <para>The left hand side of the rule is followed by the <code>=</code>

        symbol, a list of alternatives surrounded by curly braces, and is

        terminated by a semicolon. The alternatives are separated by the

        <code>||</code> symbol, and the last alternative may be separated from

        its predecessor (there must be one) using the <code>##</code> symbol;

        if this is the case, then this alternative is the exception handler

        for the production (otherwise it has no exception handler).</para>

      <para>An alternative may match the empty string, using the symbol

        <code>$</code> and the terminator symbol <code>;</code>, i.e.:

        <programlisting>

$ ;

        </programlisting>

        unless it is an exception handler alternative (in which case it must

        do something), or a sequence of items. The empty string is only valid

        if the production has no results. If you want to match an empty string

        in a production that has a result, it is necessary to use an action

        (or identity) to provide a result.</para>

      <para>An item is an identity, or a call to a (possibly anonymous) rule,

        a terminal, an action or a predicate. An identity looks like an

        assignment in conventional programming languages:

        <programlisting>

( a, b, c ) = ( d, e, f ) ;

        </programlisting></para>

      <para>Each tuple must contain the same number of names. In the case of a

        one-tuple, the parentheses may be dropped, e.g.:

        <programlisting>

a = d ;

        </programlisting></para>

      <para>Note that this is a binding operation, not an assignment.  Each

        name on the left hand side must be a new name. It is illegal to

        redeclare a name that is already in scope. It is possible to assign to

        a name which is already in scope by prefixing that name with the

        <code>&amp;</code> symbol, e.g.:

        <programlisting>

( a, &b, c ) = ( d, e, f ) ;

        </programlisting>

        would assign to the name <code>b</code>, which must have been

        previously defined (it may be a parameter; if it is a call by

        reference parameter, then the change will propagate outside to the

        calling rule).</para>

      <para>It is also possible to use the <code>!</code> symbol in the result

        tuple to ignore results, e.g.:

        <programlisting>

( a, !, b, ! ) = ( c, d, e, f ) ;

        </programlisting></para>

      <para>This is not particularly useful in an identity, but may be more

        useful in a call to a rule, terminal or action. A call to a terminal

        or rule looks like a call to a function in a conventional programming

        language, e.g.:

        <programlisting>

( a, b ) = rule1 ( c, d ) ;

( e, f ) = terminal1 () ;

        </programlisting></para>

      <para>Calls to actions have the same form, except that action names are

        surrounded by angle brackets, e.g.:

        <programlisting>

( g, h, i ) = <action1> ( a, e ) ;

        </programlisting></para>

      <para>In addition, one of the names in the result tuple of the call to

        the action may be the predicate result symbol <code>?</code>, in which

        case the action is used as a predicate (more details on predicates are

        given later).</para>

      <para>When calling a rule, terminal or action, it is necessary to have

        declared it (or in the case of a rule declared or defined it) before

        the call.</para>

      <para>If a rule or action is being invoked, and it takes one or more

        call by reference parameters, then the corresponding arguments should

        be prefixed by the <code>&amp;</code> symbol, e.g.:

        <programlisting>

length = <string-length> ( &string ) ;

        </programlisting></para>

      <para>If the rule, terminal or action has the zero-tuple as a result,

        then only the right hand side of the definition is required, e.g.:

        <programlisting>

rule2 ( a, b ) ;

terminal2 () ;

<action2> ( c, d ) ;

        </programlisting></para>

      <para>If the rule, terminal or action has the zero-tuple as a parameter,

        then the parameter tuple may be omitted, e.g.:

        <programlisting>

( a, b ) = rule3 ;

terminal3 ;

c = <action3> ;

        </programlisting></para>

      <para>In older versions of <code>sid</code>, it used to be possible to

        have ambiguous items, e.g.:

        <programlisting>

a = b ;

        </programlisting>

        where <code>b</code> was both a rule and a name. As local names may

        not shadow non-local and global names, then this is no longer a

        problem.</para>

      <para>In each case, the data flow through the rule is indicated using

        names. In the previous example of a production, both alternatives have

        the same data flow: the call to <code>mul-expr</code> returns one

        value, which is stored in the name <code>v1</code>, and the call to

        <code>expr</code> returns one value, which is stored in the name

        <code>v2</code>. Both of these names are passed to the action

        (<code>add</code> in the first alternative, <code>subtract</code> in

        the second), which returns a value into the name <code>v</code>

        (presumably the sum or difference of the previous two values). The

        name <code>v</code> is the name of the result, so this will be

        returned as the result of the rule. The exception handler (which is

        invoked if something fails) calls the action <code>ex</code> to

        produce the result <code>v</code>.</para>

      <para>It is necessary that the types of the data flow through the

        production are correct. It is also necessary to define all of the

        result names for the production in each of the alternatives in that

        production.</para>

      <para>An anonymous rule is written in the same way as the body of a

        normal rule, e.g.:

        <programlisting>

list : () -> ( l : ListT ) = {

n = number ;

/* START ANONYMOUS RULE */ {

? = <at-eof> ;

l = <make-list> ( n ) ;

||