ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/icon/historic/v941.tgz/icon.v941src.tar/icon.v941src/ipl/packs/ibpag2/README

Text File | 2000-07-29 | 53KB | 1,094 lines

               A User's Manual for Ibpag2
           (Icon-Based Parser Generation System 2)
                 Version 1.2

                - or -

           How to Use an LR-based Parser Generator


               Richard L. Goerwitz, III
            University of Chicago






1.__What_is_Ibpag2?

    Ibpag2 is a so-called "parser generator," i.e. a tool for
automating the process of generating a recognizer and/or parser from
abstract structural descriptions of an input language.  Put in more
practical terms, Ibpag2 is a piece of software that a) reads a source
file containing a grammar that defines an input language, and then b)
outputs an automaton that recognizes that language.  The user may, at
his or her option, specify actions this automaton should take when it
sees various substructures within its input language.  By default,
however, the parser simply recognizes a given sequence as belonging,
or not, to that language.

    Ibpag2 utilizes so-called "LR" table generation and parsing
algorithms.  These algorithms facilitate construction of reasonably
fast deterministic pushdown automata that are powerful enough to
handle most commonly used programming language constructs.  LR-based
systems come in three main flavors: SLR(1), LALR(1), and LR(1).  The
LR(1) flavor is fairly easy to implement, but uses too many resources
to be practical.  LALR(1) algorithms are harder to implement, but much
faster, and the parse tables they construct use considerably less
memory than do those of their LR(1) counterparts.  SLR(1) algorithms
are the easiest to implement, compile the fastest, and use about as
much memory as LALR(1)s.  SLR(1) is the least powerful of the three,
though, so there is a tradeoff.  Ibpag2 is an "enhanced" SLR(1) parser
generator.  It is enhanced in the sense that it can operate both in
its native SLR(1) mode, and in a more powerful "quasi-GLR" mode (on
which, see section 5 below).

    As its full title ("Icon-Based Parser Generator 2") implies,
Ibpag2 is written in Icon [2,3], as are the automata it creates.
Ibpag2 has been tested with Icon version 8.10.  So far I have only run
it on an i386 box running Xenix 2.3.3, and on a Sun 4 running some
version of SunOS.  I have many reports, though, of it running under
other UNIX variants.  It will probably also run under other operating
systems, though modifications will in some instances be required.
Using Ibpag2 under MS-DOS may not be possible, on account of the way
it manages memory.

    The Ibpag2 distribution adheres to de facto UNIX installation
standards: Just set the appropriate variables in the makefile, and
then "make install."  For those who are using a non-UNIX system, or
who have not installed such a package before, there is a section at
the end entitled "Installing Ibpag2" that details the installation
procedure (section 6).

    Aside from the above-mentioned installation section (6), the
remainder of this document aims to provide the reader a) with a
simple, practical explanation of what LR-family parser generators are
and how they work (section 2), and b) with a set of directions
specifically on how to use Ibpag2 (section 3).  There is also an
advanced section on debugging (4), and one on using Ibpag2 with non-LR
and/or ambiguous languages (5).  The discussion is geared for those
that have little or no experience in parsing or automaton theory.  For
very advanced reading, consult the bibliography.  For a brief summary
of Ibpag's command-line options, see the main Ibpag2 source file,
ibpag2.icn, or invoke ibpag2 with the -h (help) option.

    In general, be warned that Ibpag2 works best with small or
medium-sized grammars.  Its parse tables have to be reconstructed at
run-time, and the code for doing this can become a bit cumbersome for
grammars with more than 100 rules and fifty or so terminal symbols.  I
myself have processed grammars with as many as 300 terminals and 400
rules.  Although the resulting automata run well enough, the output
files are over 300k, and Ibpag2 takes a long time to create them.  If
you must use Ibpag2 with a very large grammar symbols, try the -c
command-line option (which produces compressed parse tables).  This
option is discussed below, in section 4.  Compiling (rather than
interpreting) Ibpag2 may result in much faster processing, as will
resetting your BLOCKSIZE and STRSIZE environment variables.  See the
installation section (6) below on using the Icon compiler to create
the Ibpag2 executable.  Good starting values for BLOCKSIZE and STRSIZE
are triple their default values (i.e. 3 x 65000).  These variables are
discussed in the Icon manual page.

    My ultimate aim in writing this document has been to make
accessible to the non-CS portion of the Icon community what for them
might seem an inaccessible branch of applied parsing and automaton
theory.  I am a philologist myself, and feel that there is a great
deal that can and ought to be done to make advanced tools accessible
to people with other interests than twiddling bits or pondering the
true meaning of epsilon closures :-).

    Any comments on the Ibpag2 system itself or its documentation
will be gratefully received.  Write to me at the address appended to
the final section (6).


2.__What_is_an_LR_Parser_Generator?

    Back in the late 50s and 60s, linguists, mathematicians, and
software engineers all became intensely interested in the formal
properties of languages: Can they be described as a series of logical
structures and relations?  Can computers recognize and manipulate
these structures efficiently?  Linguists, in particular, quickly
realized that the amount of structural complexity, ambiguity, and pure
noise in natural language would render it computationally intractable,
especially given the limited memory/throughput of then available CPUs.
Mathematicians and engineers, however, found that many of the
formalized notations they dealt with could, in fact, be (re)designed
in such a way that efficient computer processing could - at least in
principle - be achieved.

    Principle, in this case, did not squarely meet reality until
viable parser generation tools came into being.  Parser generation
tools map an abstract structural description of a formal notation or
"language" to working computer code.  Ideally, the designer simply
makes assertions like:

    an expression is composed of either
        1) a term (e.g. 10), or
        2) an expression, a "+" or "-", and another expression

Parser generator systems translate these assertions (the "grammar")
into a machine, i.e. automaton, that can recognize and/or manipulate
input streams that conform to the "language" so described.

    Let me dwell, for a moment, on the toy expression grammar
offered above.  Note that it describes a set of simple mathematical
constructs like:

    9
    9 + 3
    9 + 3 - 8

According to the specifications given above, the nine, three, and
eight alone constitute terms - which are also expressions (via rule
1).  Because these terms are also expressions, "9 + 3" can be reduced
to a larger expression by rule 2.  The same is true for "9 + 3 - 8,"
except that there rule 2 must apply twice - once for "9 + 3," and then
again for that and the remainder of the line - in effect grouping the
expressions as ( ( (9) + (3) ) - (8) ).  It is also possible to group
the expression ( (9) + ( (3) - (8) ) ), although for the discussion
that immediately follows this second grouping will be ignored (see
below on the terms "precedence" and "associativity").

    If we add actions to the above grammar specification, we can
create a calculator-like automaton.  Traditionally, LR-family automata
(like the ones Ibpag2 creates) contain a parser, one or more stacks,
and a set of action tables.  The parser reads from an input stream
segmented into "tokens" (e.g. TERM, '+', '-'), and then manipulates
its stacks according to directives contained in so-called "action" and
"goto" tables.  As it reads the input stream, the parser matches rules
with action code specified by the programmer, e.g. rule 2 above might
be matched with code that added/subtracted the expressions on either
side of the '+'/'-' operator, and produced (in calculator style) the
result.  Alternatively, it might be matched with code that generated
an equivalent construct in another language.

    In the case of our toy expression grammar above, the
corresponding LR automaton operates as follows.  Omitting and/or
simplifying some of the inner details, it first looks at the input
stream to see what the next token is.  If the next token is an
operator or end-of-input, it checks the top of its stack.  If the top
of the stack has a term on it, that term is popped off, and pushed
back on, this time renamed as an expression (rule 1 above).  The input
token is then shifted from the input stream onto the stack, unless it
is the end-of-input token, in which case the parser returns with a
result.  If the top of the stack has an expression on it (rather than
a term), the parser pops the top three elements off of the stack, and
then either subtracts the third element from the first or adds the two
together, depending on whether the second element down was the
addition or subtraction operator, and the result is pushed onto the
stack as yet another expression.

    Even in this much-simplified form, the automaton's structure
is complex.  Let us look briefly, therefore, at a practical example of
its actual workings.  If we were to feed it "9 + 3 + 8," our
calculator would take the following actions:

    1) read the 9, and push it onto the stack as a term
    2) see a plus sign on the input stream
    3) pop the term (9) off of the stack and push it back on again
       (this time calling it an expression)
    4) push the plus sign onto the stack
    5) read the 3, and push it onto the stack as a term
    6) see a minus sign on the input stream
    7) pop the 3 off of the stack and push it back on again (this
       time calling it an expression)
    8) see a minus sign still waiting on the input stream
    9) pop 9, +, and 3 off of the stack, apply the plus operator
       to 9 and 3, then push the result onto the stack again a
       single expression (the stack now has 12 on top)
    10) read the minus sign, and push it onto the stack
    11) read the 8, and push it onto the stack as a term
    12) see the end of input coming up on the input stream
    13) pop the 8 off of the stack and push it back on again as an
       expression
    14) see the end-of-input token still sitting on the input
       stream
    15) pop 12, -, and 8 off of the stack, apply the minus operator
       to 12 and 8, then push the result onto the stack again (the
       stack now has 4 on top)
    16) return the "answer" (i.e. 4)

    This series of actions is hard to describe, and even more so
to model as part of a hand-written computer program.  And, even if
such a program were written by hand, this program would have to be
modified, at times radically, every time the grammar it assumes was
augmented or changed.  What I am leading up to is that, with a parser
generator, the hand compilation stage can be eliminated by allowing
the programmer simply to declare his/her tokens and language specs,
then have the appropriate automaton constructed with little, or no,
human intervention.  This is why parser generation tools were critical
to the development of not just theoretically feasible, but truly
*practical*, LR-based computer language design systems.


3.__Using_Ibpag2

    To recode the above toy expression grammar in
Ibpag2-compatible format is relatively simple, especially if we omit
the actions initially, and concentrate on simple recognition.  We need
only a set of token declarations and three rules.  Certain
modifications will have to be made to the token declarations later on.
For general illustration's sake, however, the following will suffice:

    %token TERM, '+', '-'
    %%
    expression : TERM
    expression : expression, '+', expression
    expression : expression, '-', expression

TERM, and the addition and subtraction operators, are the tokens (i.e.
the terminals symbols out of which the grammar is constructed - the
things that the input stream is segmented into).  Note the %token
keyword used to declare them.  The colon means "is composed of."  The
double percent sign separates token declarations from the grammar
proper.

    Adding in our actions - which above were keyed to a complex
set of decisions based on input tokens and stack conditions - requires
just a few extra lines of Ibpag2 action code, set off in curly braces:

    %token TERM, '+', '-'
    %%
    expression : TERM { return arg1 }
    expression : expression, '+', expression { return arg1 + arg3 }
    expression : expression, '-', expression { return arg1 - arg3 }

Using a "|" shorthand for repeated left-hand sides of rules, we may
reformat this as:

    %token TERM, '+', '-'
    %%
    expression : TERM { return arg1 }
           | expression, '+', expression { return arg1 + arg3 }
           | expression, '-', expression { return arg1 - arg3 }

    ArgX above refers to the Xth element of the right-hand side of
the preceding rule.  So, for example, arg1 in "{ return arg1 }" above
refers to TERM - the only right-hand side element of the first rule.
The action "{ return arg1 }" means, "once you find a TERM and have
renamed it as an expression, use the value of TERM as the value for
that expression."  By way of contrast, the action "{ return arg1 +
arg3 }" means, in conjunction with the rule it follows: "When you find
an expression consisting of a sub-expression, a plus operator, and
another sub-expression, use the value of sub-expression 1 + the value
of sub-expression 2 as the value for the expression as a whole."
Technically, the action "{ return arg1 }" for expression : TERM is not
necessary, since the Ibpag2 parser, by default, pushes the value of
the last RHS arg onto the stack.  For epsilon productions (to be
discussed below), it pushes &null.

    One serious problem with this set of specifications is that
the operators '-' and '+' are left associative.  We humans take this
for granted, because correct algebraic grouping is something our
high-school math teachers burned into us.  The computer, though, has
to be told, pedantically, how to group addition and subtraction
expressions.  It has to be explicitly instructed, in other words, to
group expressions like "9 + 32 - 4" as (9 + 32) - 4.  Without
instructions of this kind, the parser does not know, after it has read
"9 + 32" and is looking at a minus sign, whether to shift the minus
sign onto the stack, and eventually try to group as 9 + (32 - 4), or
to reduce "9 + 32" to an expression and group as (9 + 32) - 4.
Although in this case the grouping may not seem to matter, it
sometimes does.  Some operators group right to left.  The unary minus
sign, for example, is one such operator (--4 groups as (- (- 4))).  To
include the unary minus sign in our grammar, we might append yet
another rule:

    %token TERM
    %left '+', '-'
    %right '-'
    %%
    expression : TERM { return arg1 }
           | expression, '+', expression { return arg1 + arg3 }
           | expression, '-', expression { return arg1 - arg3 }
           | '-', expression { return - arg2 }

The trouble with this arrangement is that the minus sign was already
declared as left associative.  To get around the conflict we use a
"dummy" token declaration, and a %prec declaration in the applicable
rule:

    %token TERM
    %left '+', '-'
    %right UMINUS
    %%
    expression : TERM { return arg1 }
           | expression, '+', expression { return arg1 + arg3 }
           | expression, '-', expression { return arg1 - arg3 }
           | '-', expression %prec UMINUS { return - arg2 }

The %prec declaration simply tells the parser that, even though the
rule contains a '-' operator, the rule should be handled as if the
operator were UMINUS.  UMINUS is not actually used as a symbol in the
right-hand side of any rule (hence the designation "dummy").  It is
there simply to make the last rule behave as if the minus sign in the
last rule were different than in the second-to-last rule.

    Let us now add in multiplication and division operators to our
calculator specifications, and see what happens.  Let me reiterate
here that the action "{ return arg1 }" for rule 1 (expression : TERM)
is not strictly necessary, since the default is to push the last RHS
arg onto the value stack:

    %token TERM
    %left '+', '-'
    %left '*', '/'
    %right UMINUS
    %%
    expression : TERM { return arg1 }
           | expression, '+', expression { return arg1 + arg3 }
           | expression, '-', expression { return arg1 - arg3 }
           | expression, '*', expression { return arg1 * arg3 }
           | expression, '/', expression { return arg1 / arg3 }
           | '-', expression %prec UMINUS { return - arg2 }

Note that the multiplication and division operators were defined
*after* the addition and subtraction operators.  The reason for this
is that, technically speaking, the grammar itself is ambiguous.  If we
treat all operators identically, the parser will not be able to tell
whether "9 + 1 * 3" should be parsed as (9 + 1) * 3 or as 9 + (1 * 3).
As we all know from our high-school algebra, multiplication has a
higher precedence than addition.  You do the multiplications before
the additions, in other words, no matter where they occur.  To tell
the parser to behave in this same manner, we declare '*' after '+'.
Note that, despite their higher priority, the '*' and '/' operators
are still left associative.  Hence, given "3 / 4 * 7," the parser will
group its input as (3 / 4) * 7.  As a brain teaser, try to figure out
how the parser might group the input "9 + 3 / 4 * 7."  Remember that
higher-precedence rules get done first, but that same-precedence rules
get done according to associativity.

    The only fundamental problem remaining with the above grammar
is that it assumes that the end of the input coincides with the end of
the line.  Is it possible to redefine the language described as
consisting of arbitrary many lines?  The answer to this question is
"yes."  One can simply add another set of productions to the grammar
that state, essentially, that the input language consists of lines
made up of an expression and a carriage return or of nothing.  Nothing
is indicated by the keyword epsilon.  Note that only the first rule
has an action field:

    lines    : lines, expression, '\n'    { write(arg2) }
        | lines, '\n'
        | epsilon

This rule-series may seem rather abstruse, but it becomes a bit
clearer when you think about what happens on actual input.  If there
is no input (epsilon), nothing gets printed, because lines : epsilon
has no action field.  If the parser sees an expression and a newline,
the parser takes this as an instance of epsilon, plus an expression,
plus a newline.  This, then, becomes the first component of rule 1 if
another expression + newline follows, or of rule two if just a newline
occurs.  Every time an instance of rule 1 occurs, the action "{
write(arg2) }" is executed, i.e. the value of the expression gets
printed.  If this still seems hard to fathom, try walking through
step-by-step.  Even experienced hands may find these sorts of rules
difficult to construct and debug.

    Note that "lines" is now the so-called "start symbol" of our
grammar.  It is, in other words, the goal of every parse.  By default
the left-hand side symbol of the first rule is the start symbol.  This
may be overridden with a %start declaration in the tokens section (on
which, see the sample Ibpag2 input file below).

    With our new, multi-line start symbol in place, the only piece
that needs to be added, in order to make our calculator specification
a full working input to Ibpag2, is a tokenizer.  A tokenizer is a
routine that reads input from a file or from some other stream (e.g.
the user's console), and then segments this input into tokens that its
parser can understand.  In some cases, the tokens must be accompanied
by a literal value.  For example, if we encounter a TERM, we return
TERM, just as it is listed in the %token declaration.  But what is the
literal value of a TERM token?  It could be, for example, 9, or 5, or
700.  The tokenizer returns the symbol TERM, in this case, but then
records that TERM's actual value by setting some global variable.  In
Ibpag2's parser, this variable is assumed to be "iilval."  In the
tokenizer, therefore, one might write

    iilval := (literal value)
    suspend TERM

For literal operators like '+' and '*', there is no need to set
iilval, since their literal value is irrelevant.  One simply returns
these as integers (usually via "suspend ord(c)").

    The tokenizer routine is normally appended to the grammar
after another double percent sign.  Everything after this second
double percent sign is copied literally to the output file.
Alternatively, the tokenizer can be $included via Icon's preprocessor.
Ibpag2 demands that the tokenizer be called iilex, and that it take a
single file argument, that it be a generator, and that it fail when it
reaches end-of-input.  Combined with our "lines" productions, the
addition of an iilex routine to our calculator grammar yields the
following Ibpag2 input file:

    %token TERM
    %left '+', '-'
    %left '*', '/'
    %right UMINUS

    %start lines

    %%

    expression : TERM { return arg1 }
           | expression, '+', expression { return arg1 + arg3 }
           | expression, '-', expression { return arg1 - arg3 }
           | expression, '*', expression { return arg1 * arg3 }
           | expression, '/', expression { return arg1 / arg3 }
           | '-', expression %prec UMINUS { return - arg2 }

    lines       : lines, expression, '\n'    { write(arg2) }
           | lines, '\n'
           | epsilon

    %%

    procedure iilex(infile)

        local nextchar, c, num

        nextchar := create !(!infile || "\n" || "\n")
        c := @nextchar | fail

        repeat {
        if any(&digits, c) then {
            if not (\num ||:= c) then
            num := c
        } else {
            if iilval := \num then {
            suspend TERM
            num := &null
            }
            if any('+-*/()\n', c) then {
            iilval := c
            suspend ord(c)
            } else {
            if not any(' \t', c) then {
                # deliberate error - will be handled later
                suspend &null
            }
            }
        }
        c := @nextchar | break
        }
        if iilval := \num then {
        return TERM
        num := &null
        }

    end

    procedure main()
        return iiparse(&input, 1)
    end

As noted above, the tokenizer (iilex) must be a generator.  It must
suspend integers either directly (e.g. ord(c)), or else via symbolic
defines like TERM, created by Ibpag2 on the basis of %token, %right,
%left, and %nonassoc declarations.  The tokenizer must fail on end of
input.

    If you like, cut the above code out, place it in a temporary
file, tmp.ibp, and then feed this file to Ibpag2 by typing "ibpag2 -f
tmp.ibp -o tmp.icn."  If your system supports input and output
redirection, type: "ibpag2 < tmp.ibp > tmp.icn."  Ibpag2 will turn
your grammar specifications and actions into a routine called iiparse.
If you look above, you will see that I appended a main procedure that,
in fact, calls iiparse().  Iiparse() takes two arguments: 1) an input
stream, and 2) a switch that, if nonnull, tells the parser to fail
rather than abort on unrecoverable errors.  When Ibpag2 is finished
creating its output file (tmp.icn above), compile that file the way
you would compile any other Icon program (e.g. "icont tmp").  Finally,
run the executable.  You should be able to type in various simple
arithmetic expressions and have the program spit back answers each
time you hit a return.  The only problem you might encounter is that
the parser aborts on erroneous input.

    The issue of erroneous input brings up yet another point of
general Ibpag2 usage.  Normally, if one is processing input, one does
not want to abort on errors, but rather just emit an error message,
and to continue processing - if this is at all possible.  To do this,
Ibpag2 provides a simple but fairly effective mechanism: A reserved
"error" token.

    When Ibpag2 encounters an error, it will remove symbols from
its stack until it has backtracked to a point where the error token is
legal.  It then shifts the error token onto the stack, and tries to
re-start the token stream at the point where it left off, discarding
tokens if necessary in order to get itself resynchronized.  The parser
considers itself resynchronized when it has successfully read and
shifted three tokens after shifting the error token.  Until then it
remains in an error state, and will not output additional error
messages as it discards tokens.

    This explanation may sound a bit abstruse, but in practice it
is turns out to be quite simple.  To implement error handling for our
calculator, we really have to add only one production to the end of
the "lines" section:

    lines       : lines, expression, '\n'    { write(arg2) }
           | lines, '\n'
           | epsilon
           | error, '\n'    {
                      write("syntax error; try again:")
                      iierrok
                    }

Given the above grammar, the parser will handle errors as follows: If
an error occurs (say it has an expression then an operator on its
stack and sees a newline on the input stream) the parser will throw
out the operator, then check if the error token would be OK in this
state (which it would not).  Then it would throw out the expression.
At this point, the stack is in the ready-to-read-a-lines state - the
state it was in before it read the last expression.  Since "lines" may
consist of error and '\n,' the error token is legal here, and so the
parser pushes error onto the stack, then looks back at the input
stream (where a newline is still waiting).  Since the newline now
completes the rule lines : error, '\n', the parser pushes the newline
onto its stack, then executes the action associated with this
production, i.e. it writes "syntax error; try again:" to the console,
prompting the user for additional input.

    The keyword "iierrok" in the above error production's action
field is there for a subtle, but important, reason: It tells the
parser to consider itself resynchronized, even if three tokens have
not yet been shifted.  If iierrok were not in the action code for this
rule, and the user were to supply more bad input after the prompt,
then the parser would simply discard those tokens, without emitting
another error message.  Why?  Because, as you will recall, the parser
discards tokens after an error, in efforts to resynchronize itself.
Until it reads and shifts three tokens successfully, it considers
itself in an error state, and will not emit additional error messages.
The three-token resync rule is there to prevent a cascade of
irrelevant error messages touched off by a single error.  In our
calculator's case above, though, we are smarter than the parser.  We
know that it is resynchronized as soon as it reduces error, '\n' to
lines.  So if a syntax error occurs on the next token, it should be
reported.  Adding "iierrok" to the action insures that the parser will
do just this.

    In addition to iierrok, there are several other directives
Ibpag2 accepts as part of the action code segments.  These are as
follows:

    iiclearin        clear the current input token
    IIERROR            perform error recovery
    IIACCEPT        simulate an accept action

There are several other directives (all implemented as macros) that
Ibpag2 accepts in GLR mode.  For a discussion of GLR mode, see below,
section 5.  IIERROR in particular, and error recovery in general, work
a bit differently in that mode than they do in Ibpag2's normal (i.e.
LR) mode.

    There are admittedly many other topics that might be covered
here.  This treatment, however, is intended as a general nontechnical
introduction, and not as a complete textbook on parser generation use.
If you want to learn more about this topic, consult the bibliography.
Also, check the UNIX manual pages on the YACC utility (Yet Another
Compiler Compiler).  Ibpag's input format is fairly close (too close,
perhaps) to YACC's.  In fact, most of what is said about YACC in UNIX
documentation can be carried directly over to Ibpag2.  Several salient
differences, though, should be kept in mind:

        1) YACC's "$$ = x" constructs are replaced by "return x" (e.g.
           "$$ = $1 + $3" -> "return $1 + $3" [$1 is a synonym for
       "arg1", $3 for "arg3", etc.])

        2) all variables within a given action are, by default, local
           to that action; i.e. they cannot be accessed by other
           actions unless you declare them global elsewhere (e.g. in
           the pass-through part of the declarations section %{ ...
           %})

        3) the %union and %type declarations/tags are not needed by
       Ibpag2 (both for better and for worse)

        4) tokens and symbols are separated from each other by a comma
           in Ibpag2 files (e.g. %token '+', '-' and S : NP, VP)

        5) epsilon is indicated by the keyword "epsilon" (e.g. REL :
           epsilon), and not by an empty RHS

        6) both epsilon and error *may* be declared as %tokens for
           reasons of precedence, although they retain hard-coded
           internal values (-2 and -1, respectively)

        7) all actions must follow the last RHS symbol of the rule
           they apply to (preceded by an optional %prec directive); to
           achieve S : NP { action1 }, VP { action2 }, insert a dummy
           rule: S : NP, dummy, VP { action2 }; dummy : epsilon {
           action1 } ;

        8) YYERROR, YYACCEPT, yyclearin, and yyerrok are the same,
           except they are written IIERROR, IIACCEPT, iiclearin, and
           iierrok (i.e. "ii" replaces "yy")

        9) Ibpag2's input files are tokenized as modified Icon files,
           and, as a consequence, Icon's reserved words must not be
           used as symbols (e.g. "if : if, then" is no go)

I myself find YACC to be ugly.  As a result, Ibpag2 is not an exact
YACC clone.  I would like to underscore the fact that I have no
intention to move in this direction, either.  It's as YACC-like as
it's going to get!

    Both YACC and non-YACC users should note number 9 in the above
list.  Don't use things like "while," "every," "do," etc. as symbols
in your grammar!  Just use the same rules for Ibpag2 nonterminals as
for Icon variables, and you'll be OK.

    For those that just can't bear using anything but a strictly
YACC-conformant system, I've included a preprocessor with the Ibpag2
distribution called (at one user's recommendation) "iacc."  Iacc reads
&input - assumed to be a YACCish grammar - and sends to &output an
Ibpag2-conformant file.  I have not tested this file extensively, and
there are likely to be bugs in the way I've handled the necessary 2
token lookaheads and value stack references.  Give it a whirl, though,
if you are feeling adventurous.  The only reason I personally use Iacc
is that some YACCs (e.g. BSD YACC) have particularly nice debugging
messages and help.  If my grammar is particularly complex, I just run
it through YACC without action code first, then use Iacc to convert it
to Ibpag2 format.  Iacc's output, as I noted, is not meant to be
pretty, so I invariably end up doing a little editing - usually just
respacing a few rules, and re-inserting any comments that I might have
put in the original YACC file.

    In general, Ibpag2 (like YACC) handles epsilon moves and
indirect cycles.  LR-mode shift-reduce conflicts are also handled in
the normal way (i.e. pick the rule with the highest priority, and, in
cases where the priority is the same, check the associativities).  In
contrast to YACC, Ibpag2 flags reduce/reduce conflicts as errors
(since these often conceal deeper precedence problems and just plain
kludges).  Reduce/reduce conflict errors are easily enough remedied,
if need be, via (dummy) precedences.  One can convert these errors to
warnings by specifying -y on the command line.  With the -y option,
reduce/reduce conflicts are resolved in favor of the rule that occurs
first in the grammar.  The -y switch also prevents Ibpag2 from
aborting on shift/reduce conflicts, telling it instead to resolve in
favor of shift.  Basically, -y is a partial YACC compatibility switch.
Normally (i.e. in SLR mode) Ibpag2 is much more finicky than YACC
about conflicts in its grammars.

    Also in contrast to YACC, Ibpag2 supports multiple
simultaneous parsers.  Ibpag2 normally names its main parser routine
iiparse().  By using the -m command-line option, however, you can
override this default behavior, and force Ibpag2 to augment this name
in some uniquely identifiable fashion.  For example, "ibpag2 -m _1 <
tmp.ibp > tmp.icn" will force Ibpag2 to write a parser called
"iiparse_1" to tmp.icn.  Note that, instead of calling iilex, this
iiparse_1() routine will now call iilex_1, and all necessary global
variables will have _1 appended to them (e.g. errors will become
errors_1).  I don't expect that many people will have occasion to use
this feature.  It is there, though, for those that want it.


4.__Debugging

    Constructing and debugging LR(1) family parsers can sometimes
be hair raising, even with a parser generator.  Several precautions
can be taken, however, to minimize the agony.  The first is to declare
all tokens initially as part of a single %token declaration, i.e. with
no precedences, and with the same associativities.  Also, leave out
action code until the grammar seems to be working.  In this stage, you
can even run the grammar through (BSD)YACC or GNU Bison.  All you
would need to do is remove the commas between tokens and symbols, and
place a semicolon at the end of every rule.  During this and all
debugging stages, supply Ibpag2 with a -v command-line switch.  This
will cause Ibpag2 to write a summary of rules, tokens, and its two
state tables to "ibpag2.output" (a bit like GNU Bison, but with a
hard-coded name).  If you get messages about conflicts in your parse
tables (e.g.  "unresolvable reduce/reduce conflict, state 5, token
257, rules 4,5").  This file will tell you what rules these are, and
what token number 257 is.  Use precedences and associativities to
clear these problems up as they arise.  If you are comfortable having
reduce/reduce errors resolved by the order in which the conflicting
rules occur, then use the -y command-line switch.  With -y on the
command line, Ibpag2 will always resolve in favor of the earlier rule.
This option will also cause it to resolve all shift/reduce conflicts
in favor of shift.

    There are certain languages that are not ambiguous that SLR(1)
parsers like Ibpag2 will fail to produce an unambiguous parse table
for.  The classic example is

    expr : lval, '=', rval | rval
    lval : '*', rval       | ID
    rval : lval

C programmers will recognize this as a toy expression grammar with
code for identifiers, assignments, and pointers.  The problem is that
if we feed this grammar to Ibpag2, it will claim that there is a
conflict on lookahead '='.  In truth, there is no ambiguity.  The SLR
parser simply doesn't remember the pathway the parser used to get to
the state it is in when it sees '=' on the input stream.  Whether the
parser gets into this state by seeing '*' plus and ID, or by seeing
just an ID, it knows to turn the ID into an lval.  Then it knows to
turn lval into rval.  At this point, though, it doesn't know whether
to shift the = sign via rule 1, or to turn rval and the preceding '*'
into an lval.  The parser has "forgotten" that the '*' is there
waiting on level down on the stack!

    The solution to this problem is actually quite simple (at
least in concept).  Just provide a unique pathway in the grammar for
the conflicting rules.  In this case, they are rules 1 and 5 (the
first and last):

    expr : lval, '=', rval | rval
    lval : '*', pval | ID
    pval : lval
    rval : lval

Now when the parser sees '*,' it can only have a pval after it.  Never
mind that pval is composed of precisely the same things as rval.  The
point is that the parser generator follows a different route after
seeing '*' than if it starts with ID and no preceding '*'.  Hence it
"remembers" that that the '*' is back on the stack, waiting for the
"lval : '*', pval" rule to apply.  There is no more conflict.

    Go ahead and run these grammars through Ibpag2 if you aren't
sure what is going on.  Remember to declare ID as a token, and to
place "%%" in the appropriate spot!

    If you get your parser up and running, but find that it is not
functioning quite the way you expect, add the following line somewhere
near the start of Ibpag2's output file:

    $define IIDEBUG

If you like, you can add it to the beginning of your Ibpag2 input
file.  Place it in the declarations section (before the first double
percent sign), and surround it by %{ and %}, e.g.:

    %{
    $define IIDEBUG
    %}

This tells Ibpag2 to send $define IIDEBUG straight through to the
output file.

    What defining IIDEBUG does is tell iiparse, once compiled, to
emit profuse debugging messages about the parser's actions, and about
the state of its stacks.  This display will not make a whole lot of
sense to anyone who doesn't understand LR-family parsers, so those who
want to access this feature should perhaps go through a standard
reference like Aho, Sethi, and Ullman [1].

    If, after you are finished debugging your grammar, you find
that Ibpag2's output files are rather large, you may try saving space
by compressing the action and goto tables.  This is accomplished by
invoking Ibpag2 with the -c (compress) option.  Using this option
makes debugging difficult, and makes the parser run a bit more slowly.
It also only works for rather large grammars with long nonterminal
symbol names.  Don't even consider it until the grammar is thoroughly
debugged and you have determined that the output file's size is just
too great for practical use.  Even then, compression may or may not
help, depending on how long your nonterminal names are.  In general,
Ibpag2 is best as a teaching tool, or as a production system for
medium or small grammars.


5.__Using_Ibpag2_with_Non-LR_Grammars

    There may be times when you *want* to parse languages that no
LR-based algorithm can handle.  There may be times, that is, when the
grammar you want to use contains conflicts or ambiguities that are
there by design, and not by oversight.  For example, you may want to
parse a natural language.  Full-blown natural languages involve many
highly ambiguous constructs, and are not LR-parsable.  By invoking it
with the -a option, Ibpag2 can parse or recognize certain natural
languages, or, more practically speaking, certain NL subsets.  The
letter "a" in -a is supposed to stand for "ambiguous," although what
this option really does is put Ibpag2 into a quasi-GLR mode - i.e.
into a kind of "generalized" LR mode in which it can accept non-LR
grammars [4,5].

    User-visible changes to Ibpag2's operation in quasi-GLR mode
(i.e. with the -a option) are as follows:

    1) iiparse() is now a generator
    2) action code can use suspend as well as return
    3) IIERROR places the current thread in an error state (i.e.
       it doesn't *necessarily* trigger error recovery; see below)
    4) there are two new action-code directives (iiprune and
           iiisolate) and a general define (AUTO_PRUNE)
    5) conflicts due to ambiguities in the grammar no longer
       result in aborted processing (so, e.g., if you do not
       specify the -y option on a grammar with reduce/reduce
       conflicts, Ibpag2 will simply generate a parser capable of
       producing multiple parses for the same input)

    In quasi-GLR mode, iiparse() should be invoked in a way that
will render multiple results usable, if they are available (e.g.
"every result := iiparse(&input) do...".  Action code is also allowed
to produce more than one value (i.e. to use suspend).  When it does
so, iiparse() creates separate parse threads for each value.  So, for
instance, if your action code for some production suspends both of the
following lists,

    ["noun", "will", "gloss: desire"]
    ["noun", "will", "gloss: legal document mandating how _
                      one's possessions are to be disposed _
              of after one's death"],

iiparse() would create two separate parse threads - one for each
result.  Note that in this case, the syntactic structure of each
thread is the same.  It is their semantics (i.e. the stuff on the
value stack) that differs.

    If you use the iierrok and iiclearin macros in your action
code before suspending any result, their affect persists through all
subseqent suspensions and resulting parse threads.  If you use these
macros after suspending one or more times, however, they are valid
only for the parse thread generated by the next suspension.  By way of
contrast, the IIERROR macro *always* flags only the next parse thread
as erroneous.  Likewise, IIACCEPT always simulates an accept action on
the next suspension only.  IIERROR and IIACCEPT, in other words, never
have any effect on subsequent suspensions and parse threads other than
the one that immediately follows them.  This is true of iierrok and
iiclearin only when used after the first suspension.

    In quasi-GLR mode, IIERROR (number three in the difference
list above) becomes a mechanism for placing the current parse thread
in error mode.  This is similar to, but not quite identical to, how
IIERROR functions in straight LR mode.  In quasi-GLR mode, if other
threads can carry on the parse without error the erroneous parse
thread is quietly clobbered.  Full-blown error recovery only occurs if
all of the other parsers halt as well.  This makes sense if you think
about it.  Why keep erroneous threads around when there are threads
still continuing a valid parse?  For some large interactive systems,
it might be necessary to keep bogus threads around longer, and weed
them out only after a lengthy grading process.  If you are
constructing a system such as this, you'll have to modify Ibpag2's
iiglrpar.lib file.  In particular, you'll need to change the segment
in iiparse() that takes out the trash, so to speak, in such a way that
it does so only if the error count in a given parser either rises
above a specific threshhold or else exceeds the number of errors in
the "most correct" parser by a certain amount.  This is not that hard
to do.  I just don't expect that most parsers people generate with
Ibpag2 will use IIERROR or error recovery in general in so involved a
fashion.

    Iiprune and iiisolate (number 4 above) are used to control the
growth of the parallel parser array.  In order to give straightforward
(read "implementationally trivial") support for action code, Ibpag2
cannot create a parse "forest" in the sense that a standard GLR parser
does.  Instead, it simply duplicates the current parser environment
whenever it encounters a conflict in its action table.  Even if the
conflict turns out to reflect only a local ambiguity, the parsers, by
default, remain separate.  Put differently, Ibpag2's quasi-GLR parser,
by default, makes no direct effort to reduce the size of its parser
arrays or to alter the essentially linear structure of their value and
state stacks.  Size reduction, where necessary and/or desirable, is up
to the programmer.  What the iiprune macro is there to do is to give
the programmer a way of pruning a given thread out of the active
parser list.  Iiisolate allows him or her to prune out every thread
*but* the current one.  AUTO_PRUNE makes the parser behave more like a
standard GLR parser, instructing it to prune parse threads that are
essentially duplicating another parse thread's efforts.  The parser,
though, does not build a parse tree per se, the way most GLR parsers
typically do, but rather manipulates its value stack like a
traditional LR-family parser.

    Iiprune is useful when, for example, the semantics (i.e. your
"action" code segments) determine that a given parse thread is no
longer viable, and you want to signal the syntactic analyzer not to
continue pursuing it.  The difference between iiprune and IIERROR is
that iiprune clobbers the current parser immediately.  IIERROR only
puts it into an error state.  If all active parsers end up in an error
state, and none can shift additional input symbols, then the IIERROR
macro induces error recovery.  Iiprune does not.  NB: iiprune, if used
in action code that suspends multiple results, cancels the current and
remaining results (i.e. it does not clobber parsers already spun off
by previous suspensions by invocation of that same code; it merely
cuts the result sequence).  Iiprune essentially stands in for "fail"
in this situation.  Fail itself can be used in the code, but be warned
that iiparse() will still push *at least one* value onto its value
stack, even if a given action code segment fails.  This keeps the
value stack in sync with the syntax.  To avoid confusion, I recommend
not using "fail" in any action code.

    Iiisolate is useful if, during error recovery, you prompt the
user interactively, or do something else that cannot be elegantly done
in parallel for two or more distinct parse threads.  Iiisolate allows
you to preserve only the the current parse thread, and to clobber the
rest.  Iiisolate can also be useful as a way of making sure that only
one thread carries on the parse in non-error situations.  Suppose that
we have a series of productions:

    sentences  :  sentences sentence '\n'
            { print_parse(arg2) }
           |  sentences '\n'
           |  error '\n'
           |  epsilon

If we get a sentence with more than one parse, all of the underlying
threads that produced these parses will be active for the next
sentence as well.  In many situations this will not be what we want.
If our desire it to have only one active parse thread at the start of
each sentence, we simply tell our lexical analyzer to suspend two
newlines every time it sees a newline on the input stream.  This
insures that the second rule will always apply right after the first.
We then insert iiisolate directives for both it and the one error
production:

    sentences  :  sentences sentence '\n'
            { print_parse(arg2) }
           |  sentences '\n'
            { iiisolate }
           |  error '\n'
            { iiisolate; iierrok }
           |  epsilon

The effect here is to allow multiple parsers to be generated only
while parsing "sentence".  The iiisolate directive, in other words,
sees to it that no sentence parse will ever begin with multiple active
parsers.  As with LR mode, iierrok clears the error flag for the
(current) parser.

    Note that if you use iiisolate in action code that suspends
multiple results, iiisolate will clobber all parsers but the one
generated by the next suspension.

    If there is no need for close control over the details of the
parser array, and you wish only to clobber parsers that end up doing
the same thing as some other parser (and hence returning identical
values), then just make sure you add "$define AUTO_PRUNE" to the
pass-through code section at the top of the file.  Put differently,
defining AUTO_PRUNE instructs the quasi-GLR parser to weed out parsers
that are in the same state, and which have identical value stacks.
AUTO_PRUNE can often be used in place of iiisolate in situations like
the one discussed just above.  Its only drawback is that it slows
the parser a bit.

    Other than these deviations (action code and iiparse becoming
generators, IIERROR's altered behavior, and the addition of iiprune,
iiisolate, and AUTO_PRUNE), Ibpag2's quasi-GLR mode - at least on the
surface - works pretty much like its straight LR mode.  In fact, if
you take one of your SLR(1) grammars, and run it through Ibpag2 using
the -a option, you probably won't notice any difference in the
resulting automaton unless you do some debugging or perform some
timing tests (the GLR parser is slower, though for straight SLR(1)
grammars not by much).  Even with non-SLR(1) grammars, the quasi-GLR
parser will clip along merrily, using all the same sorts of rules,
action code, and macros that you would typically use in LR mode!


6.__Installing_Ibpag

    If you are a UNIX user, or have a generic "make" utility, you
are in luck.  Just edit Makefile.dist according to the directions
given in that file, rename it as "makefile," then execute "make."
Ibpag2 should be created automatically.  If everything goes smoothly,
then "make install" (su-ing root, if both possible and necessary for
correct installation of the iiparse.icn file).  Check with your system
administrator if you are on a public system, and aren't sure what to
do.

    Please be sure to read the directions in the makefile
carefully, and set DESTDIR and LIBDIR to the directory where you want
the executable and parser file to reside.  Also, make sure the paths
you specify are correct for your Icon executables.  Although Ibpag2
will apparently compile using iconc, I would recommend using the
interpreter, icont, first, unless you are planning on working with a
large grammar.

    If you are using some other system - one that lacks "make" -
then shame on your manufacturer :-).  You'll be a bit inconvenienced.
Try typing:

    icont -o ibpag2 follow.icn ibpag2.icn ibreader.icn \
         ibtokens.icn ibutil.icn ibwriter.icn iohno.icn \
         outbits.icn slritems.icn slrtbls.icn shrnktbl.icn \
         version.icn slshupto.icn

The backslashes merely indicate that the next line is a continuation.
The whole thing should, in other words, be on a single line.  As noted
above, you may compile rather than interpret - if your OS supports the
Icon compiler.  Just replace "icont" above with "iconc."  The
resulting executable will run considerably faster than with "icont,"
although the time required to compile it may be large, and the (still
somewhat experimental) compiler may not work smoothly in all
environments.

    If your operating system support environment variables, and
you have set up your LPATH according to the specifications in the Icon
distribution (see below), then you may copy iiparse.lib and
iiglrpar.lib to some file in your LPATH.  If you do not do this, or if
your OS does not support environment variables, then you must be in
the directory where you keep your Ibpag2 files when you use it, or
else invoke Ibpag2 with the -p dirname option (where dirname is the
directory that holds the iiparse.lib and iiglrpar.lib files that come
with the Ibpag2 distribution).  The .lib files contain template
parsers that are critical to Ibpag2's operation.  Ibpag2 will abort if
it cannot find them.

    If your operating system permits the creation of macros or
batch files, it might be useful to create one that changes
automatically to the Ibpag2 source directory, and runs the executable.
This has the side-benefit of making it easier for Ibapg2 to find the
parser library files, iiparse.lib and iiglrpar.lib.  Under DOS, for
instance, one might create a batch file that says:

    c:
    cd c:\ibpag2
    iconx ibpag2 %1 %2 %3 %4 %5 %6 %7 %8 %9

DOS, it turns out, has to execute Icon files indirectly through iconx,
so this technique has yet another advantage in that it hides the
second level of indirection - although it prevents you from using
input and output redirection.  Naturally, the above example assumes
that Ibpag2 is in c:\ibpag2.

    Ibpag2 assumes the existence on your system, not only of an
Icon interpreter or compiler, but also of an up-to-date Icon Program
Library.  There are several routines included in the IPL that Bibleref
uses.  Make sure you (or the local system administrators) have put the
IPL online, and have translated the appropriate object modules.  Set
your IPATH environment variable to point to the place where the object
modules reside.  Set LPATH to point to the modules' source files.
Both IPATH and LPATH are documented in doc directory of the Icon
source tree (ipd224.doc).  If your system does not support environment
variables, copy ximage.icn, options.icn, ebcdic.icn, and escape.icn
from the IPL into the Ibpag2 source directory, and compile them in
with the rest of the Ibpag2 source files, either by adding them to the
SRC variable in the makefile, or by adding them manually to the "icont
-o ..." command line given above.

    If you have any problems installing or using Ibpag2, please
feel free to drop me, Richard Goerwitz, an e-mail message at
[e-mail], or (via the post) at:

    5410 S. Ridgewood Ct., 2E
    Chicago, IL   60615


6.__Bibliography

1.  Aho, Alfred V., Sethi, Ravi, and Ullman, Jeffrey D.  Compilers.
    Addison-Wesley: Reading, Massachusetts, second printing, 1988.

2.  Griswold, Ralph E. and Griswold, Madge T.  The Icon Programming
    Language. Prentice-Hall, Inc.: Englewood Cliffs, New Jersey, USA,
    second edition, 1990.

3.  Griswold, Ralph E., Jeffery, Clinton L., and Townsend, Gregg M.
    Version 8.10 of the Icon Programming Language.  Univ. of Arizona
    Icon Project Document 212, 1993.  (obtain via anonymous FTP from
    cs.arizona.edu ~ftp/icon/docs/ipd212.doc)

4.  Tomita, Masaru.  Efficient Parsing for Natural Language.  Boston:
    Kluwer Academic Publishers, c. 1985.

5.  Tomita, Masaru editor.  Generalized LR Parsing.  Boston:  Kluwer
    Academic Publishers, 1991.