REF LR_PARSER                               Robert Duncan, November 1992

        COPYRIGHT University of Sussex 1992. All Rights Reserved.

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
<<<<<<<<<<<<<<<<<<<<<                             >>>>>>>>>>>>>>>>>>>>>>
<<<<<<<<<<<<<<<<<<<<<         AN LALR(1)          >>>>>>>>>>>>>>>>>>>>>>
<<<<<<<<<<<<<<<<<<<<<      PARSER GENERATOR       >>>>>>>>>>>>>>>>>>>>>>
<<<<<<<<<<<<<<<<<<<<<                             >>>>>>>>>>>>>>>>>>>>>>
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

This file describes an LALR(1)  parser generator library for Pop-11.  It
assumes a working knowledge of what  such a parser generator can do  and
what it's good for:  useful background information can  be found in  the
file HELP * LR_PARSER.

         CONTENTS - (Use <ENTER> g to access required sections)

  1   Introductory Note

  2   The Basic Library

  3   Generating a Parser

  4   Running the Parser

  5   Running the Parser in Trace Mode

  6   Saving the Parser to a File

  7   The Parser Report File

  8   Investigating the Parser States



--------------------
1  Introductory Note
--------------------

Most Pop-11 programmers will find the syntactic interface to the library
described in HELP * DEFINE_PARSER  of more immediate  use. The  features
described here are more likely to  be useful to programmers using  other
languages or who need to generate parsers dynamically.




--------------------
2  The Basic Library
--------------------

None of  the identifiers  described in  this file  are autoloadable.  In
order to use the library at all, you must first include in your  program
the line:

    uses lr_parser;

This adds the  LR_PARSER library  directory to  popuseslist and  defines
some basic utility procedures. Libraries defining specific features  can
then be  loaded individually  as required.  Each of  the sections  which
follow is introduced with the  name of the library  you need to load  to
access the identifiers described in that section.

In the context of this library,  a PARSER is a recordclass object  which
encodes the LALR(1)  parsing tables for  the grammar from  which it  was
constructed. A parser is created initially by the procedure lr_build and
then interpreted (i.e. made to parse) by the procedure lr_parse.

The procedure lr_parser  maintains a  global property  table which  maps
grammar  names  to  their  associated  parsers.  Whenever  a  parser  is
constructed  using  lr_build  it  can  optionally  be  added  into  this
property, after which the grammar name can be used interchangeably  with
the parser structure  itself. Throughout  this file,  the argument  name
PARSER is used  to stand  for any item  which lr_parser  would map  to a
parser structure, i.e. it can be either the parser structure itself,  or
a grammar name recorded in the lr_parser property.


lr_parser(item) -> parser                                    [procedure]
false -> lr_parser(item)
        A recogniser for  parsers built by  the library. If  item is  an
        LALR(1)  parser  structure  generated  by  a  previous  call  to
        lr_build or if item is the name of such a parser which was built
        with the  KEEP argument  <true>, then  the parser  is  returned;
        otherwise <false> is returned. Uses a property table to maintain
        the mapping from names to parsers. You can assign <false> to the
        updater to clear the property entry for a particular name.


LR_PARSER_DIR -> string                                       [constant]
        The root  of the  LR_PARSER directory  tree containing  standard
        sub-directories such as:

            auto
            lib

        The lib directory is added by the library to popuseslist and the
        auto directory to popautolist.




----------------------
3  Generating a Parser
----------------------

LIB * LR_BUILD defines the LALR(1)  parser generator which  constructs a
set of parsing tables from the symbolic description of  a  grammar.  The
library should be loaded using:

    uses lr_build;


lr_build(name, tokens, symbols, start_symbol, rules,         [procedure]
                                resolve_p, keep) -> parser
        Constructs the LALR(1) parsing tables for the grammar  described
        by the arguments:

            name
                The grammar name: this can be any item and plays no role
                other than to identify the resulting parser.

            tokens
                The set of terminal symbols (tokens). This may be a list
                or vector. Any item can be used as a token, but tokens
                are always compared for equality using the "=="
                operator, so wherever a particular token occurs (e.g. in
                a grammar rule) it must always be represented by the
                identical item. In principle the tokens set should be a
                true set, containing no duplicates, but this is not
                checked: subsequent occurrences of the same item are
                ignored.

            symbols
                The set of nonterminal symbols. This may be a list or
                vector. The comments above relating to terminal symbols
                apply equally to nonterminal symbols, with one extra
                condition: no item from the tokens set can appear in the
                symbols set (i.e. no item can be both a terminal and a
                nonterminal symbol of the same grammar).

            start_symbol
                The start symbol of the grammar: this must be an item
                from the symbols set.

            rules
                The set of productions (grammar rules). This may be a
                list or vector. A grammar rule is a non-empty list or
                vector of symbols. The first item in a rule must be a
                nonterminal symbol and stands for the left-hand-side of
                the rule; the remaining items make up the
                right-hand-side of the rule. A rule containing just a
                single item (the left-hand-side) stands for a null
                production. A rule cannot contain any item which does
                not occur in either the tokens or symbols sets.

        The resulting parser is a record structure encoding the  LALR(1)
        parsing tables  for the  input grammar.  If the  grammar is  not
        LALR(1) then the  tables will contain  conflicts: the number  of
        conflicts   can    be    determined    with    the    procedures
        lr_parser_sr_conflicts and  lr_parser_rr_conflicts.  The  parser
        also retains  the symbolic  information about  the grammar  from
        which it was  constructed: the name,  tokens symbols and  rules.
        These can be recovered using the procedures described below.

        The remaining arguments to lr_build are optional:

            resolve_p
                A procedure used for resolving conflicts arising from
                grammars which are not properly LALR(1). It has the call
                form:

                     resolve_p(ITEM_1, ITEM_2) -> ITEM

                The two arguments represent a single conflict in the
                parser. For a shift/reduce conflict, ITEM_1 is a
                terminal symbol standing for the possible shift action
                and ITEM_2 is a rule standing for the possible
                reduction; for a reduce/reduce conflict, both items are
                rules standing for the alternative reductions, ordered
                such that ITEM_1 always precedes ITEM_2 in the rules
                set. The result ITEM can be either ITEM_1 or ITEM_2 to
                indicate a successful resolution of the conflict or else
                <false> to indicate no resolution. Conflicts
                successfully resolved are not counted in the parser. For
                each conflict not resolved, and for every conflict if
                the resolve_p argument is omitted, a default strategy is
                applied: in a shift/reduce conflict the shift is chosen,
                and in a reduce/reduce conflict the rule which occurs
                first in the rules set is chosen (this is the only case
                where the order of items in the input is significant).
                This is functionally equivalent to providing a value of
                erase for resolve_p, except that conflicts resolved
                using resolve_p are not counted.

            keep
                A boolean: if <true> the result parser is added to the
                lr_parser property keyed under the grammar name. The
                name can then be used everywhere in place of the parser
                structure. The default value is <false>.

        The following example constructs the parsing tables for a simple
        grammar describing expressions in the Lambda calculus.

            uses lr_parser;
            uses lr_build;

            lr_build(
                "Lambda",                  ;;; name
                { VAR \ . ( ) },           ;;; tokens
                { exp },                   ;;; symbols
                "exp",                     ;;; start_symbol
                {{ exp VAR }               ;;; rules
                 { exp exp exp }
                 { exp \ VAR . exp }
                 { exp ( exp ) }},
                true,                       ;;; keep
            ) =>
            ** <parser Lambda>

        This  grammar  is  ambiguous  and  hence  not  LALR(1),  so  the
        resulting parser  has  conflicts. See  HELP * LR_PARSER  for  an
        alternative formulation of the grammar.


lr_parser_name(parser) -> item                               [procedure]
lr_parser_terminal_symbols(parser) -> vec                    [procedure]
lr_parser_nonterminal_symbols(parser) -> vec                 [procedure]
lr_parser_start_symbol(parser) -> item                       [procedure]
lr_parser_rules(parser) -> vec                               [procedure]
        Return the components of the  grammar from which the parser  was
        built. Note that  the tokens, symbols  and rules components  are
        always returned as  vectors for faster  indexing, regardless  of
        the format of the original arguments to lr_build, but the  order
        of items  within  the vectors  is  identical with  the  original
        input. For example:

            lr_parser_name("Lambda") =>
            ** Lambda

            lr_parser_nonterminal_symbols("Lambda") =>
            ** {exp}


lr_parser_sr_conflicts(parser) -> n                          [procedure]
lr_parser_rr_conflicts(parser) -> n                          [procedure]
        Return the number of shift/reduce and reduce/reduce conflicts in
        the parser. A properly  LALR(1) parser will  return 0 for  both.
        However, conflicts resolved by an explicit RESOLVE_P argument to
        lr_build are not  counted, so  a parser  may appear  to have  no
        conflicts even though the grammar was not strictly LALR(1).  For
        example:

            lr_parser_sr_conflicts("Lambda") =>
            ** 6

            lr_parser_rr_conflicts("Lambda") =>
            ** 0


lr_strip(parser)                                             [procedure]
lr_strip(parser, bool)
        Removes symbolic information from the parser structure. This can
        considerably reduce  the size  of  the parser,  but  necessarily
        means that certain features of the library will no longer work.

        By default, the parser is only partially stripped to remove  the
        rules,  states  and  conflict  information.  This  recovers  the
        majority of  the  available  space,  but  also  means  that  the
        following procedures will mishap if applied to the parser:

            # lr_trace
            # lr_report
            # lr_state_items

        In addition, the procedures

            # lr_parser_rules
            # lr_parser_sr_conflicts
            # lr_parser_rr_conflicts

        will no longer return sensible values.

        If the optional bool argument is given <true> then the parser is
        fully stripped, which  removes (in  addition to  the above)  the
        vectors of  terminal and  non-terminal symbols.  This makes  the
        parser as small as it possibly can be, but also means that  none
        of the  LR_STATE procedures  can be  expected to  work, and  the
        procedures

            # lr_parser_terminal_symbols
            # lr_parser_nonterminal_symbols
            # lr_parser_start_symbol

        will all return <false>.




---------------------
4  Running the Parser
---------------------

LIB * LR_PARSE defines an implementation of the LR(1) parsing  algorithm
which  interprets  the  PARSER  tables  generated  by lr_build. Load the
library using:

    uses lr_parse;


lr_parse(input_p, reduce_p, parser)                          [procedure]
        Interprets  the  parser  tables  to  parse  a  stream  of  items
        generated by  input_p, using  reduce_p to  perform the  semantic
        actions appropriate to each reduction.

        The input procedure is called each time the parser needs to read
        an item. It has the call form:

            input_p() -> (ITEM, TOKEN_N)

        where ITEM is  some arbitrary  item, and TOKEN_N  is an  integer
        number  identifying   to   which  terminal   symbol   the   ITEM
        corresponds. Terminal symbols are  numbered from 1 according  to
        their order in the vector

            lr_parser_terminal_symbols(parser)

        A value of  0 is a  special case used  to stand for  the end  of
        input; any other value is taken to indicate some input error. If
        the token read leads to a shift action, then ITEM is pushed onto
        the user stack.

        The reduction  procedure is  called immediately  prior to  every
        reduce action. It has the call form:

            reduce_p(RULE_N)

        where RULE_N is the  integer number of  the rule being  reduced:
        rules are numbered from 1 according to their order in the vector

            lr_parser_rules(parser)

        The reduction procedure would typically do a go_on to select  an
        action appropriate to the rule. There are no restrictions on the
        actions which can be performed, except that the procedure should
        be prepared to  take account  of any terminal  symbols from  the
        right-hand-side of  the rule  which  will have  been  previously
        shifted  onto   the  user   stack.  If   the  parse   terminates
        successfully, then  any results  computed by  reduce_p are  left
        untouched on the stack.

        If the parse fails, either because of an input error or  because
        the  input  is  not   well-formed,  the  redefinable   procedure
        lr_parse_error is called.

        The procedure lr_parse is the default class_apply of the  parser
        structure, allowing a parser to be applied directly:

            parser(input_p, reduce_p)


lr_parse_error(item, token_n, state_n)              [procedure variable]
        Called by lr_parse on a parsing  error. item and token_n are  as
        returned by the last call to  INPUT_P and state_n is an  integer
        identifying the current  parsing state. For  an error to  arise,
        either token_n must be an invalid token number, or else there is
        no action  for that  token  in the  current state.  The  default
        behaviour of lr_parse_error is to call

            mishap(item, 1, 'PARSE ERROR')

        but the procedure can  be redefined to  give a more  informative
        error report.




-----------------------------------
5  Running the Parser in Trace Mode
-----------------------------------

LIB * LR_TRACE  defines  an  alternative  implementation  of  the  LR(1)
parsing algorithm which provides a trace of its actions in a VED buffer,
useful for debugging. This  library cannot be used  with a parser  which
has been stripped. Load it using:

    uses lr_trace;


lr_trace(input, parser) -> parse_tree                        [procedure]
lr_trace(input_p, reduce_p, parser)
        Parses the input according to  the tables encoded in the  parser
        structure, displaying a trace of its actions.

        The tracer has  two call forms.  In the first  form, input  is a
        list (possibly dynamic) of items drawn from the parser's  TOKENS
        set. If the input makes up a sentence of the language which  the
        parser recognises, then lr_trace returns a parse tree describing
        its derivation, otherwise it returns <false>. The parse_tree for
        a successful parse has  the input tokens at  its leaves and  one
        interior node  for each  reduction which  the parser  performed.
        These  interior  nodes  are   constructed  by  the   redefinable
        procedure lr_trace_constree. Its default action is to  construct
        a list  representing the  rule being  reduced: the  head is  the
        nonterminal symbol from the left-hand-side of the rule, and  the
        tail is  a  list  of  sub-trees, one  for  each  symbol  on  the
        right-hand-side. For example:

            uses lr_trace;
            lr_trace([ \ VAR . VAR VAR ], "Lambda") =>
            ** [exp \ VAR . [exp [exp VAR] [exp VAR]]]

        Such a tree can  be displayed graphically  within VED using  the
        procedure showtree:

            uses showtree;
            showtree(lr_trace([ \ VAR . VAR VAR ], "Lambda"));

        See HELP * SHOWTREE.

        In its second call form, lr_trace takes two procedure  arguments
        input_p  and  reduce_p  which  provide  an  input  source  and a
        reduction procedure  for  the  parser. In  this  mode,  lr_trace
        simulates the behaviour of lr_parse. This means that the results
        (if any) returned  by the  parse are  determined exclusively  by
        reduce_p, and  a parsing  error would  normally cause  a  mishap
        rather than returning <false>. Refer to the previous section for
        more details.

        In either case, lr_trace  displays a trace  of its actions  in a
        VED buffer. The trace output takes the form of a table headed as
        follows:

             State|          Stack | Input    | Action
             -----+----------------+----------+-------

        One row is added to  the table for each  step in the parse.  The
        columns of the table have the following interpretations:

           Column   Meaning
           ------   -------

            State   the current state

            Stack   the top of the parser's symbol stack: the topmost
                    item is always at the right-hand end of the field

            Input   the current input item: a blank entry here means
                    that the parser's choice of action is independent of
                    the input

            Action  the action chosen for the current state/input
                    combination

        The  trace  generated  from  the  previous  example  would  look
        something like the following:

            State|           Stack | Input | Action
            -----+-----------------+-------+-------
                1|                 | \     | SHIFT  3
                3|               \ | VAR   | SHIFT  10
               10|           \ VAR | .     | SHIFT  11
               11|         \ VAR . | VAR   | SHIFT  2
                2|     \ VAR . VAR |       | REDUCE exp --> VAR
               12|     \ VAR . exp | VAR   | CONFLICT [SHIFT  2]
                2| \ VAR . exp VAR |       | REDUCE exp --> VAR
                7| \ VAR . exp exp | $end$ | REDUCE exp --> exp exp
               12|     \ VAR . exp | $end$ | REDUCE exp --> \ VAR . exp
                5|             exp | $end$ | SHIFT  6
                6|       exp $end$ |       | ACCEPT

        The parser always begins in state  1 with nothing on the  stack.
        The first input item  is the token "\"  which causes a shift  to
        state 3. The second  row of t he table  thus shows the parser  in
        state 3, with "\" on the stack. The next three items ("VAR", "."
        and "VAR") are also shifted: note how items cross from the Input
        to the Stack field as they are consumed. At row 5 (state 2)  the
        parser performs a reduction by the rule

            exp --> VAR

        which replaces the  topmost "VAR"  token on the  stack with  the
        symbol "exp". This is the  default action for state 2  activated
        for any input item,  hence the empty  Input column. Each  REDUCE
        action in  the trace  corresponds to  one interior  node in  the
        resulting parse tree:

            [exp \ VAR .             ;;; REDUCE exp --> \ VAR . exp
                [exp                 ;;; REDUCE exp --> exp exp
                    [exp VAR]        ;;; REDUCE exp --> VAR
                    [exp VAR]]]      ;;; REDUCE exp --> VAR

        Once a parse has run to completion, the last action in the table
        will either  be  ACCEPT  for  a  successful  outcome,  or  ERROR
        otherwise.

        Loading the LR_TRACE library also generalises the class_apply of
        the parser structure to call  lr_trace where possible, but  with
        the trace output disabled. This allows calls such as:

            lr_parser("Lambda")([ \ VAR . VAR VAR ]) =>
            ** [exp \ VAR . [exp [exp VAR] [exp VAR]]]

            lr_parser("Lambda")([ \ VAR VAR VAR ]) =>
            ** <false>


lr_trace_tracing -> bool                                      [variable]
bool -> lr_trace_tracing
        Determines whether lr_trace should produce any trace output. The
        default value is <true>; setting it <false> means that  lr_trace
        will still parse but without tracing.


lr_trace_file -> string                                       [variable]
string -> lr_trace_file
        Name of  the file  to which  trace output  should be  sent:  the
        default is 'lr_trace'.


lr_trace_file_writeable -> bool                               [variable]
bool -> lr_trace_file_writeable
        Controls whether the trace output file should be writeable:  the
        default value is <false>.


lr_trace_state_width -> n                                     [variable]
n -> lr_trace_state_width
lr_trace_stack_width -> n                                     [variable]
n -> lr_trace_stack_width
lr_trace_input_width -> n                                     [variable]
n -> lr_trace_input_width
        Determine the sizes of the  fields in the trace output  diagram:
        lr_trace_state_width is the number of columns used for the State
        field, lr_trace_stack_width is  the number of  columns used  for
        the Stack  field  and  lr_trace_input_width  is  the  number  of
        columns used for the Input  field. The default value is  <false>
        for each,  meaning that  the  sizes are  determined  dynamically
        depending on the width of the  trace output file: the wider  the
        window, the more  informative the output.  Setting any of  these
        variables to 0 or less means that the corresponding field is not
        shown in the trace  output. The Action  field always extends  as
        far to the right as necessary and cannot be suppressed.


lr_trace_constree(symbol, n) -> tree                [procedure variable]
        Used for constructing interior nodes in the parse tree built  by
        lr_trace.  Called  once  for  each  reduction,  symbol  is   the
        left-hand-side symbol of  the rule  being reduced and  n is  the
        number of symbols on the right-hand-side. The default definition
        is:

            define vars lr_trace_constree(symbol, n) -> tree;
                lvars symbol, n, tree = conslist(n);
                symbol :: tree -> tree;
            enddefine;

        If redefined,  the procedure  should consume  n items  from  the
        stack and return  some object representing  the parse tree.  For
        example, the  procedure  prolog_maketerm  would  be  a  suitable
        alternative value, using Prolog terms to represent trees.




------------------------------
6  Saving the Parser to a File
------------------------------

LIB * LR_OUTPUT writes  a  program  to  regenerate  a  parser  structure
without using the LR_BUILD library. Load using:

    uses lr_output;


lr_output(decl_list, word, parser, output)                   [procedure]
        Writes to the given output  a Pop-11 program to reconstruct  the
        parser structure  and bind  it to  word. decl_list  provides  an
        appropriate declaration for word. The resulting program can only
        be  loaded  after  the  LR_PARSER  library,  but  is   otherwise
        self-contained; in  particular, it  does not  need the  LR_BUILD
        library.

        output can  be  any valid  output  destination: a  file  name, a
        character consumer or  an output  device. A named  file will  be
        opened afresh using discout; if the name is a word, it will have
        the extension '.p' appended automatically.

        The resulting program has the form:

            <declaration> word = <parser> ;

        where <declaration> is generated from the argument decl_list  by
        the call:

            applist(decl_list, spr);

        It is expected that decl_list should be some meaningful list  of
        declaration  syntax   words  (such   as  "global",   "constant",
        "lconstant" etc.) but this is not checked. If decl_list is  nil,
        then a default declaration of "vars" is assumed.

        For example, the sequence:

            uses lr_output;
            lr_output([global vars], "lambdaParser", "Lambda", "Lambda")

        creates a  file  called  'Lambda.p' in  the  current  directory,
        containing a program of the form:

            global vars lambdaParser = <expression> ;

        where <expression> recreates the  Lambda parser without the  use
        of the LR_BUILD library.

        The full symbolic information in the parser is too complex to be
        written out reliably, so  is ignored. This  means that a  parser
        recreated from a program generated  by lr_output will always  be
        at least partially stripped (regardless of whether the  original
        was stripped or  not) and  so cannot  be used  for tracing  (see
        lr_strip above).

        The program does preserve the parser's terminal and non-terminal
        symbols if these  are present  in the original.  This in  itself
        poses a problem, in that  symbols can in principal be  arbitrary
        items which may not have a suitable printing representation. For
        this reason, the symbols are  written out using the  redefinable
        procedure lr_output_pr which must be defined in such a way  that
        its output can be read back in successfully by the compiler.


lr_output_pr(item)                                  [procedure variable]
        Writes an expression to the current output which would  recreate
        item if compiled by  the Pop-11 compiler.  Used by lr_output  to
        write out a parser's terminal and nonterminal symbols which  can
        be arbitrary items.  The generated expressions  are enclosed  in
        evaluating vector brackets:

            {% ... %}

        separated by commas, and must be evaluable in that context.

        The default version of this procedure handles words, strings and
        integral numbers.  It should  be redefined  for symbols  of  any
        other type. The procedure  is always called  in a context  where
        pop_pr_quotes has  the  value  <false>  and  pr  has  the  value
        sys_syspr.




-------------------------
7  The Parser Report File
-------------------------

LIB * LR_REPORT generates a written  description of the parsing  tables.
This is essential for understanding conflicts in a parser, and can  also
be useful when planning error reporting. Information from the report can
also be determined dynamically using the procedures from  LIB * LR_STATE
(see below). This library  cannot be used with  a parser which has  been
stripped.  Load the library with:

    uses lr_report;


lr_report(parser, output)                                    [procedure]
        Writes a summary report on  the parser to the specified  output.
        The output can be any  valid output destination: a file  name, a
        character consumer or an output device. A file name can be given
        as a word  or a string;  on VMS  systems, a word  will have  the
        extension  '.lis'  appended  automatically.  For  all  but   the
        smallest of grammars,  the report can  get very large  -- up  to
        thousands of lines -- so it's generally best to send the  report
        to a file rather than to the screen.

        The layout of the report is best described with reference to  an
        example. If you  have compiled the  "Lambda" example above,  you
        can generate the report for the parser by doing:

            uses lr_report;
            lr_report("Lambda", 'report');

        The report starts with a brief header which includes the  parser
        name, the number of states and the number of conflicts. For  the
        Lambda parser, this looks like:

            Parser Lambda
            12 states
            6 shift/reduce conflicts
            0 reduce/reduce conflicts

        The remainder of the file is taken up with a description of each
        of the  parser states.  State  number 12  of the  Lambda  parser
        demonstrates most of the relevant features: you can view this by
        doing

            <ENTER> pved report
            <ENTER> /@aState 12/

        The state description is in three parts:

            1)  the set of LR(0) items from which the state was
                constructed

            2)  the action table

            3)  the goto table

        For Lambda state 12, these appear as follows:

            1)  The LR(0) items

                    [2] exp --> exp <.> exp
                    [3] exp --> \ VAR . exp <.>

                There are two items, generated from production numbers 2
                and 3.  These numbers  cross-reference with  the  reduce
                actions in  the action  table.  The special  symbol  <.>
                indicates the "dot" position within each item.

            2) The action table

                    ! VAR shift 2
                    ! VAR reduce 3
                    ! \ shift 3
                    ! \ reduce 3
                    ! ( shift 4
                    ! ( reduce 3
                        $default$ reduce 3

                This lists the tokens which  are valid in the state  and
                shows the action associated with each: an action

                    shift <N>

                means a shift to state <N> and

                    reduce <N>

                means a reduction by rule  <N>. For each reduction,  the
                associated rule must appear in the item set with the dot
                at the right-hand end. The special token "$default$"  is
                a default action to  be taken for  any token not  listed
                explicitly: this  will always  be a  reduction. Not  all
                states have a default action in which case any token not
                listed will cause a parsing error. The `!` character  in
                the first column of the table indicates a conflict, i.e,
                where the associated  token has more  than one  possible
                action in the state (in  this particular state, all  the
                valid tokens have conflicts).  You can locate  conflicts
                within VED by doing

                    <ENTER> /@a!

                The table  is  organised  such  that  the  first  action
                associated with any  token is  the one  the parser  will
                choose.

            3) The goto table

                    exp goto 7

                This lists the  nonterminal symbols which  are valid  in
                the state and  their associated  goto transitions.  Some
                states may have  no goto  transitions, and  there is  no
                concept of a default transition.

        A final point to  note from the report  is that lr_build  always
        adds an additional rule to the grammar RULES set of the form:

            $begin$ --> START_SYMBOL $end$

        where "$begin$" and  "$end$" are  special tokens.  This rule  is
        assigned number [0]; the state constructed from the item

            [0] $begin$ --> START_SYMBOL $end$ <.>

        is the terminal state of the parser.




----------------------------------
8  Investigating the Parser States
----------------------------------

LIB * LR_STATE makes available from procedure calls all the  information
in the parser report file. This  is useful for presenting the report  in
an  alternative  way  (e.g.  with  a  graphical  display)  or  else  for
dynamically generating error reports. This library cannot be used with a
parser which has been stripped. Load with:

    uses lr_state;


lr_state_max(parser) -> n                                    [procedure]
        Returns the largest  valid state number  for the parser.  States
        are numbered sequentially from 1, so this is also the number  of
        states within the parser.


lr_state_tokens(n, parser) -> (token_list, default)          [procedure]
        Returns a list of  tokens for which  there are explicit  actions
        defined in state n of the parser. The boolean default is  <true>
        if there is also a default  action in this state, implying  that
        any token  is  valid in  the  state,  but that  all  tokens  not
        occurring  explicitly  in  the  token_list  share  some  common,
        default action: this will always  be a reduction. If default  is
        <false> then  there is  no default  action: only  the tokens  in
        token_list are valid in  this state, and  any other token  would
        cause an error.  It follows that  in an error  state (e.g.  in a
        call to lr_parse_error) default will always be <false>.

        The special value lr_state_end_token  is included in  token_list
        if the end-of-input marker ("$end$") is valid in state n.


lr_state_actions(token, n, parser) -> (shift, reductions)    [procedure]
        Returns the ACTION table entry (or entries) for a token in state
        n of the parser: in a  properly LALR(1) parser there will  never
        be more than one action for any token, but there may be multiple
        actions in the presence  of conflicts. The  result shift is  the
        next state  number  if token  has  a shift  action,  or  <false>
        otherwise. reductions is a  list of the  rule numbers for  which
        token has reduce  actions. A  rule number  of 0  stands for  the
        ACCEPT action,  indicating that  state n  must be  the  terminal
        state of the parser.

        In a  parser which  has been  partially stripped,  all  conflict
        information will have been removed, so this procedure will never
        return more than one action.


lr_state_shift(token, n, parser) -> shift                    [procedure]
        Returns the shift result returned by lr_state_actions.


lr_state_reduce(token, n, parser) -> reduction               [procedure]
        Returns the  first  rule  number from  the  list  of  REDUCTIONS
        returned by lr_state_actions, or <false> if the list is empty.


lr_state_end_token -> item                                    [variable]
item -> lr_state_end_token
        Special value used  to stand for  the end-of-input marker  (i.e.
        the "$end$"  symbol  from  the  report  file).  The  default  is
        <termin>.


lr_state_symbols(n, parser) -> symbol_list                   [procedure]
        Returns a list of  the nonterminal symbols  for which there  are
        GOTO table entries  in state n  of the parser.  The list may  be
        empty.


lr_state_goto(symbol, n, parser) -> m                        [procedure]
        Returns the GOTO table entry for a nonterminal symbol in state n
        of the parser: this will be the next state number or <false> for
        a blank entry.


lr_state_items(n, parser) -> list                            [procedure]
        Returns a list of the LR(0) items from which the parser  state n
        was constructed. An item is  represented by a pair of  integers:
        the front of the pair  is the item rule  number and the back  of
        the pair is the "dot" position within the rule. The dot position
        is an index into the rule  with the interpretation that the  dot
        occurs after the indexed symbol. Because the first symbol of the
        rule is always  the left-hand-side symbol,  a dot position  of 1
        implies that the  dot is  at the start  of the  right-hand-side,
        while a dot  position equal to  the length of  the rule  implies
        that the dot is at the end.

        For example:

            uses lr_state;
            lr_state_items(12, "Lambda") =>
            ** [[2|2] [3|5]]

        This result  corresponds to  the extract  from the  report  file
        shown above:

            [2] exp --> exp <.> exp
            [3] exp --> \ VAR . exp <.>

        This procedure will mishap if the parser has been even partially
        stripped.



--- C.all/ref/lr_parser
--- Copyright University of Sussex 1992. All rights reserved.
