| 1 |
|
| 2 |
|
| 3 |
|
| 4 |
|
| 5 |
|
| 6 |
|
| 7 |
A User's Manual for Ibpag2 |
| 8 |
(Icon-Based Parser Generation System 2) |
| 9 |
Version 1.2 |
| 10 |
|
| 11 |
- or - |
| 12 |
|
| 13 |
How to Use an LR-based Parser Generator |
| 14 |
|
| 15 |
|
| 16 |
Richard L. Goerwitz, III |
| 17 |
University of Chicago |
| 18 |
|
| 19 |
|
| 20 |
|
| 21 |
|
| 22 |
|
| 23 |
|
| 24 |
1.__What_is_Ibpag2? |
| 25 |
|
| 26 |
Ibpag2 is a so-called "parser generator," i.e. a tool for |
| 27 |
automating the process of generating a recognizer and/or parser from |
| 28 |
abstract structural descriptions of an input language. Put in more |
| 29 |
practical terms, Ibpag2 is a piece of software that a) reads a source |
| 30 |
file containing a grammar that defines an input language, and then b) |
| 31 |
outputs an automaton that recognizes that language. The user may, at |
| 32 |
his or her option, specify actions this automaton should take when it |
| 33 |
sees various substructures within its input language. By default, |
| 34 |
however, the parser simply recognizes a given sequence as belonging, |
| 35 |
or not, to that language. |
| 36 |
|
| 37 |
Ibpag2 utilizes so-called "LR" table generation and parsing |
| 38 |
algorithms. These algorithms facilitate construction of reasonably |
| 39 |
fast deterministic pushdown automata that are powerful enough to |
| 40 |
handle most commonly used programming language constructs. LR-based |
| 41 |
systems come in three main flavors: SLR(1), LALR(1), and LR(1). The |
| 42 |
LR(1) flavor is fairly easy to implement, but uses too many resources |
| 43 |
to be practical. LALR(1) algorithms are harder to implement, but much |
| 44 |
faster, and the parse tables they construct use considerably less |
| 45 |
memory than do those of their LR(1) counterparts. SLR(1) algorithms |
| 46 |
are the easiest to implement, compile the fastest, and use about as |
| 47 |
much memory as LALR(1)s. SLR(1) is the least powerful of the three, |
| 48 |
though, so there is a tradeoff. Ibpag2 is an "enhanced" SLR(1) parser |
| 49 |
generator. It is enhanced in the sense that it can operate both in |
| 50 |
its native SLR(1) mode, and in a more powerful "quasi-GLR" mode (on |
| 51 |
which, see section 5 below). |
| 52 |
|
| 53 |
As its full title ("Icon-Based Parser Generator 2") implies, |
| 54 |
Ibpag2 is written in Icon [2,3], as are the automata it creates. |
| 55 |
Ibpag2 has been tested with Icon version 8.10. So far I have only run |
| 56 |
it on an i386 box running Xenix 2.3.3, and on a Sun 4 running some |
| 57 |
version of SunOS. I have many reports, though, of it running under |
| 58 |
other UNIX variants. It will probably also run under other operating |
| 59 |
systems, though modifications will in some instances be required. |
| 60 |
Using Ibpag2 under MS-DOS may not be possible, on account of the way |
| 61 |
it manages memory. |
| 62 |
|
| 63 |
The Ibpag2 distribution adheres to de facto UNIX installation |
| 64 |
standards: Just set the appropriate variables in the makefile, and |
| 65 |
then "make install." For those who are using a non-UNIX system, or |
| 66 |
who have not installed such a package before, there is a section at |
| 67 |
the end entitled "Installing Ibpag2" that details the installation |
| 68 |
procedure (section 6). |
| 69 |
|
| 70 |
Aside from the above-mentioned installation section (6), the |
| 71 |
remainder of this document aims to provide the reader a) with a |
| 72 |
simple, practical explanation of what LR-family parser generators are |
| 73 |
and how they work (section 2), and b) with a set of directions |
| 74 |
specifically on how to use Ibpag2 (section 3). There is also an |
| 75 |
advanced section on debugging (4), and one on using Ibpag2 with non-LR |
| 76 |
and/or ambiguous languages (5). The discussion is geared for those |
| 77 |
that have little or no experience in parsing or automaton theory. For |
| 78 |
very advanced reading, consult the bibliography. For a brief summary |
| 79 |
of Ibpag's command-line options, see the main Ibpag2 source file, |
| 80 |
ibpag2.icn, or invoke ibpag2 with the -h (help) option. |
| 81 |
|
| 82 |
In general, be warned that Ibpag2 works best with small or |
| 83 |
medium-sized grammars. Its parse tables have to be reconstructed at |
| 84 |
run-time, and the code for doing this can become a bit cumbersome for |
| 85 |
grammars with more than 100 rules and fifty or so terminal symbols. I |
| 86 |
myself have processed grammars with as many as 300 terminals and 400 |
| 87 |
rules. Although the resulting automata run well enough, the output |
| 88 |
files are over 300k, and Ibpag2 takes a long time to create them. If |
| 89 |
you must use Ibpag2 with a very large grammar symbols, try the -c |
| 90 |
command-line option (which produces compressed parse tables). This |
| 91 |
option is discussed below, in section 4. Compiling (rather than |
| 92 |
interpreting) Ibpag2 may result in much faster processing, as will |
| 93 |
resetting your BLOCKSIZE and STRSIZE environment variables. See the |
| 94 |
installation section (6) below on using the Icon compiler to create |
| 95 |
the Ibpag2 executable. Good starting values for BLOCKSIZE and STRSIZE |
| 96 |
are triple their default values (i.e. 3 x 65000). These variables are |
| 97 |
discussed in the Icon manual page. |
| 98 |
|
| 99 |
My ultimate aim in writing this document has been to make |
| 100 |
accessible to the non-CS portion of the Icon community what for them |
| 101 |
might seem an inaccessible branch of applied parsing and automaton |
| 102 |
theory. I am a philologist myself, and feel that there is a great |
| 103 |
deal that can and ought to be done to make advanced tools accessible |
| 104 |
to people with other interests than twiddling bits or pondering the |
| 105 |
true meaning of epsilon closures :-). |
| 106 |
|
| 107 |
Any comments on the Ibpag2 system itself or its documentation |
| 108 |
will be gratefully received. Write to me at the address appended to |
| 109 |
the final section (6). |
| 110 |
|
| 111 |
|
| 112 |
2.__What_is_an_LR_Parser_Generator? |
| 113 |
|
| 114 |
Back in the late 50s and 60s, linguists, mathematicians, and |
| 115 |
software engineers all became intensely interested in the formal |
| 116 |
properties of languages: Can they be described as a series of logical |
| 117 |
structures and relations? Can computers recognize and manipulate |
| 118 |
these structures efficiently? Linguists, in particular, quickly |
| 119 |
realized that the amount of structural complexity, ambiguity, and pure |
| 120 |
noise in natural language would render it computationally intractable, |
| 121 |
especially given the limited memory/throughput of then available CPUs. |
| 122 |
Mathematicians and engineers, however, found that many of the |
| 123 |
formalized notations they dealt with could, in fact, be (re)designed |
| 124 |
in such a way that efficient computer processing could - at least in |
| 125 |
principle - be achieved. |
| 126 |
|
| 127 |
Principle, in this case, did not squarely meet reality until |
| 128 |
viable parser generation tools came into being. Parser generation |
| 129 |
tools map an abstract structural description of a formal notation or |
| 130 |
"language" to working computer code. Ideally, the designer simply |
| 131 |
makes assertions like: |
| 132 |
|
| 133 |
an expression is composed of either |
| 134 |
1) a term (e.g. 10), or |
| 135 |
2) an expression, a "+" or "-", and another expression |
| 136 |
|
| 137 |
Parser generator systems translate these assertions (the "grammar") |
| 138 |
into a machine, i.e. automaton, that can recognize and/or manipulate |
| 139 |
input streams that conform to the "language" so described. |
| 140 |
|
| 141 |
Let me dwell, for a moment, on the toy expression grammar |
| 142 |
offered above. Note that it describes a set of simple mathematical |
| 143 |
constructs like: |
| 144 |
|
| 145 |
9 |
| 146 |
9 + 3 |
| 147 |
9 + 3 - 8 |
| 148 |
|
| 149 |
According to the specifications given above, the nine, three, and |
| 150 |
eight alone constitute terms - which are also expressions (via rule |
| 151 |
1). Because these terms are also expressions, "9 + 3" can be reduced |
| 152 |
to a larger expression by rule 2. The same is true for "9 + 3 - 8," |
| 153 |
except that there rule 2 must apply twice - once for "9 + 3," and then |
| 154 |
again for that and the remainder of the line - in effect grouping the |
| 155 |
expressions as ( ( (9) + (3) ) - (8) ). It is also possible to group |
| 156 |
the expression ( (9) + ( (3) - (8) ) ), although for the discussion |
| 157 |
that immediately follows this second grouping will be ignored (see |
| 158 |
below on the terms "precedence" and "associativity"). |
| 159 |
|
| 160 |
If we add actions to the above grammar specification, we can |
| 161 |
create a calculator-like automaton. Traditionally, LR-family automata |
| 162 |
(like the ones Ibpag2 creates) contain a parser, one or more stacks, |
| 163 |
and a set of action tables. The parser reads from an input stream |
| 164 |
segmented into "tokens" (e.g. TERM, '+', '-'), and then manipulates |
| 165 |
its stacks according to directives contained in so-called "action" and |
| 166 |
"goto" tables. As it reads the input stream, the parser matches rules |
| 167 |
with action code specified by the programmer, e.g. rule 2 above might |
| 168 |
be matched with code that added/subtracted the expressions on either |
| 169 |
side of the '+'/'-' operator, and produced (in calculator style) the |
| 170 |
result. Alternatively, it might be matched with code that generated |
| 171 |
an equivalent construct in another language. |
| 172 |
|
| 173 |
In the case of our toy expression grammar above, the |
| 174 |
corresponding LR automaton operates as follows. Omitting and/or |
| 175 |
simplifying some of the inner details, it first looks at the input |
| 176 |
stream to see what the next token is. If the next token is an |
| 177 |
operator or end-of-input, it checks the top of its stack. If the top |
| 178 |
of the stack has a term on it, that term is popped off, and pushed |
| 179 |
back on, this time renamed as an expression (rule 1 above). The input |
| 180 |
token is then shifted from the input stream onto the stack, unless it |
| 181 |
is the end-of-input token, in which case the parser returns with a |
| 182 |
result. If the top of the stack has an expression on it (rather than |
| 183 |
a term), the parser pops the top three elements off of the stack, and |
| 184 |
then either subtracts the third element from the first or adds the two |
| 185 |
together, depending on whether the second element down was the |
| 186 |
addition or subtraction operator, and the result is pushed onto the |
| 187 |
stack as yet another expression. |
| 188 |
|
| 189 |
Even in this much-simplified form, the automaton's structure |
| 190 |
is complex. Let us look briefly, therefore, at a practical example of |
| 191 |
its actual workings. If we were to feed it "9 + 3 + 8," our |
| 192 |
calculator would take the following actions: |
| 193 |
|
| 194 |
1) read the 9, and push it onto the stack as a term |
| 195 |
2) see a plus sign on the input stream |
| 196 |
3) pop the term (9) off of the stack and push it back on again |
| 197 |
(this time calling it an expression) |
| 198 |
4) push the plus sign onto the stack |
| 199 |
5) read the 3, and push it onto the stack as a term |
| 200 |
6) see a minus sign on the input stream |
| 201 |
7) pop the 3 off of the stack and push it back on again (this |
| 202 |
time calling it an expression) |
| 203 |
8) see a minus sign still waiting on the input stream |
| 204 |
9) pop 9, +, and 3 off of the stack, apply the plus operator |
| 205 |
to 9 and 3, then push the result onto the stack again a |
| 206 |
single expression (the stack now has 12 on top) |
| 207 |
10) read the minus sign, and push it onto the stack |
| 208 |
11) read the 8, and push it onto the stack as a term |
| 209 |
12) see the end of input coming up on the input stream |
| 210 |
13) pop the 8 off of the stack and push it back on again as an |
| 211 |
expression |
| 212 |
14) see the end-of-input token still sitting on the input |
| 213 |
stream |
| 214 |
15) pop 12, -, and 8 off of the stack, apply the minus operator |
| 215 |
to 12 and 8, then push the result onto the stack again (the |
| 216 |
stack now has 4 on top) |
| 217 |
16) return the "answer" (i.e. 4) |
| 218 |
|
| 219 |
This series of actions is hard to describe, and even more so |
| 220 |
to model as part of a hand-written computer program. And, even if |
| 221 |
such a program were written by hand, this program would have to be |
| 222 |
modified, at times radically, every time the grammar it assumes was |
| 223 |
augmented or changed. What I am leading up to is that, with a parser |
| 224 |
generator, the hand compilation stage can be eliminated by allowing |
| 225 |
the programmer simply to declare his/her tokens and language specs, |
| 226 |
then have the appropriate automaton constructed with little, or no, |
| 227 |
human intervention. This is why parser generation tools were critical |
| 228 |
to the development of not just theoretically feasible, but truly |
| 229 |
*practical*, LR-based computer language design systems. |
| 230 |
|
| 231 |
|
| 232 |
3.__Using_Ibpag2 |
| 233 |
|
| 234 |
To recode the above toy expression grammar in |
| 235 |
Ibpag2-compatible format is relatively simple, especially if we omit |
| 236 |
the actions initially, and concentrate on simple recognition. We need |
| 237 |
only a set of token declarations and three rules. Certain |
| 238 |
modifications will have to be made to the token declarations later on. |
| 239 |
For general illustration's sake, however, the following will suffice: |
| 240 |
|
| 241 |
%token TERM, '+', '-' |
| 242 |
%% |
| 243 |
expression : TERM |
| 244 |
expression : expression, '+', expression |
| 245 |
expression : expression, '-', expression |
| 246 |
|
| 247 |
TERM, and the addition and subtraction operators, are the tokens (i.e. |
| 248 |
the terminals symbols out of which the grammar is constructed - the |
| 249 |
things that the input stream is segmented into). Note the %token |
| 250 |
keyword used to declare them. The colon means "is composed of." The |
| 251 |
double percent sign separates token declarations from the grammar |
| 252 |
proper. |
| 253 |
|
| 254 |
Adding in our actions - which above were keyed to a complex |
| 255 |
set of decisions based on input tokens and stack conditions - requires |
| 256 |
just a few extra lines of Ibpag2 action code, set off in curly braces: |
| 257 |
|
| 258 |
%token TERM, '+', '-' |
| 259 |
%% |
| 260 |
expression : TERM { return arg1 } |
| 261 |
expression : expression, '+', expression { return arg1 + arg3 } |
| 262 |
expression : expression, '-', expression { return arg1 - arg3 } |
| 263 |
|
| 264 |
Using a "|" shorthand for repeated left-hand sides of rules, we may |
| 265 |
reformat this as: |
| 266 |
|
| 267 |
%token TERM, '+', '-' |
| 268 |
%% |
| 269 |
expression : TERM { return arg1 } |
| 270 |
| expression, '+', expression { return arg1 + arg3 } |
| 271 |
| expression, '-', expression { return arg1 - arg3 } |
| 272 |
|
| 273 |
ArgX above refers to the Xth element of the right-hand side of |
| 274 |
the preceding rule. So, for example, arg1 in "{ return arg1 }" above |
| 275 |
refers to TERM - the only right-hand side element of the first rule. |
| 276 |
The action "{ return arg1 }" means, "once you find a TERM and have |
| 277 |
renamed it as an expression, use the value of TERM as the value for |
| 278 |
that expression." By way of contrast, the action "{ return arg1 + |
| 279 |
arg3 }" means, in conjunction with the rule it follows: "When you find |
| 280 |
an expression consisting of a sub-expression, a plus operator, and |
| 281 |
another sub-expression, use the value of sub-expression 1 + the value |
| 282 |
of sub-expression 2 as the value for the expression as a whole." |
| 283 |
Technically, the action "{ return arg1 }" for expression : TERM is not |
| 284 |
necessary, since the Ibpag2 parser, by default, pushes the value of |
| 285 |
the last RHS arg onto the stack. For epsilon productions (to be |
| 286 |
discussed below), it pushes &null. |
| 287 |
|
| 288 |
One serious problem with this set of specifications is that |
| 289 |
the operators '-' and '+' are left associative. We humans take this |
| 290 |
for granted, because correct algebraic grouping is something our |
| 291 |
high-school math teachers burned into us. The computer, though, has |
| 292 |
to be told, pedantically, how to group addition and subtraction |
| 293 |
expressions. It has to be explicitly instructed, in other words, to |
| 294 |
group expressions like "9 + 32 - 4" as (9 + 32) - 4. Without |
| 295 |
instructions of this kind, the parser does not know, after it has read |
| 296 |
"9 + 32" and is looking at a minus sign, whether to shift the minus |
| 297 |
sign onto the stack, and eventually try to group as 9 + (32 - 4), or |
| 298 |
to reduce "9 + 32" to an expression and group as (9 + 32) - 4. |
| 299 |
Although in this case the grouping may not seem to matter, it |
| 300 |
sometimes does. Some operators group right to left. The unary minus |
| 301 |
sign, for example, is one such operator (--4 groups as (- (- 4))). To |
| 302 |
include the unary minus sign in our grammar, we might append yet |
| 303 |
another rule: |
| 304 |
|
| 305 |
%token TERM |
| 306 |
%left '+', '-' |
| 307 |
%right '-' |
| 308 |
%% |
| 309 |
expression : TERM { return arg1 } |
| 310 |
| expression, '+', expression { return arg1 + arg3 } |
| 311 |
| expression, '-', expression { return arg1 - arg3 } |
| 312 |
| '-', expression { return - arg2 } |
| 313 |
|
| 314 |
The trouble with this arrangement is that the minus sign was already |
| 315 |
declared as left associative. To get around the conflict we use a |
| 316 |
"dummy" token declaration, and a %prec declaration in the applicable |
| 317 |
rule: |
| 318 |
|
| 319 |
%token TERM |
| 320 |
%left '+', '-' |
| 321 |
%right UMINUS |
| 322 |
%% |
| 323 |
expression : TERM { return arg1 } |
| 324 |
| expression, '+', expression { return arg1 + arg3 } |
| 325 |
| expression, '-', expression { return arg1 - arg3 } |
| 326 |
| '-', expression %prec UMINUS { return - arg2 } |
| 327 |
|
| 328 |
The %prec declaration simply tells the parser that, even though the |
| 329 |
rule contains a '-' operator, the rule should be handled as if the |
| 330 |
operator were UMINUS. UMINUS is not actually used as a symbol in the |
| 331 |
right-hand side of any rule (hence the designation "dummy"). It is |
| 332 |
there simply to make the last rule behave as if the minus sign in the |
| 333 |
last rule were different than in the second-to-last rule. |
| 334 |
|
| 335 |
Let us now add in multiplication and division operators to our |
| 336 |
calculator specifications, and see what happens. Let me reiterate |
| 337 |
here that the action "{ return arg1 }" for rule 1 (expression : TERM) |
| 338 |
is not strictly necessary, since the default is to push the last RHS |
| 339 |
arg onto the value stack: |
| 340 |
|
| 341 |
%token TERM |
| 342 |
%left '+', '-' |
| 343 |
%left '*', '/' |
| 344 |
%right UMINUS |
| 345 |
%% |
| 346 |
expression : TERM { return arg1 } |
| 347 |
| expression, '+', expression { return arg1 + arg3 } |
| 348 |
| expression, '-', expression { return arg1 - arg3 } |
| 349 |
| expression, '*', expression { return arg1 * arg3 } |
| 350 |
| expression, '/', expression { return arg1 / arg3 } |
| 351 |
| '-', expression %prec UMINUS { return - arg2 } |
| 352 |
|
| 353 |
Note that the multiplication and division operators were defined |
| 354 |
*after* the addition and subtraction operators. The reason for this |
| 355 |
is that, technically speaking, the grammar itself is ambiguous. If we |
| 356 |
treat all operators identically, the parser will not be able to tell |
| 357 |
whether "9 + 1 * 3" should be parsed as (9 + 1) * 3 or as 9 + (1 * 3). |
| 358 |
As we all know from our high-school algebra, multiplication has a |
| 359 |
higher precedence than addition. You do the multiplications before |
| 360 |
the additions, in other words, no matter where they occur. To tell |
| 361 |
the parser to behave in this same manner, we declare '*' after '+'. |
| 362 |
Note that, despite their higher priority, the '*' and '/' operators |
| 363 |
are still left associative. Hence, given "3 / 4 * 7," the parser will |
| 364 |
group its input as (3 / 4) * 7. As a brain teaser, try to figure out |
| 365 |
how the parser might group the input "9 + 3 / 4 * 7." Remember that |
| 366 |
higher-precedence rules get done first, but that same-precedence rules |
| 367 |
get done according to associativity. |
| 368 |
|
| 369 |
The only fundamental problem remaining with the above grammar |
| 370 |
is that it assumes that the end of the input coincides with the end of |
| 371 |
the line. Is it possible to redefine the language described as |
| 372 |
consisting of arbitrary many lines? The answer to this question is |
| 373 |
"yes." One can simply add another set of productions to the grammar |
| 374 |
that state, essentially, that the input language consists of lines |
| 375 |
made up of an expression and a carriage return or of nothing. Nothing |
| 376 |
is indicated by the keyword epsilon. Note that only the first rule |
| 377 |
has an action field: |
| 378 |
|
| 379 |
lines : lines, expression, '\n' { write(arg2) } |
| 380 |
| lines, '\n' |
| 381 |
| epsilon |
| 382 |
|
| 383 |
This rule-series may seem rather abstruse, but it becomes a bit |
| 384 |
clearer when you think about what happens on actual input. If there |
| 385 |
is no input (epsilon), nothing gets printed, because lines : epsilon |
| 386 |
has no action field. If the parser sees an expression and a newline, |
| 387 |
the parser takes this as an instance of epsilon, plus an expression, |
| 388 |
plus a newline. This, then, becomes the first component of rule 1 if |
| 389 |
another expression + newline follows, or of rule two if just a newline |
| 390 |
occurs. Every time an instance of rule 1 occurs, the action "{ |
| 391 |
write(arg2) }" is executed, i.e. the value of the expression gets |
| 392 |
printed. If this still seems hard to fathom, try walking through |
| 393 |
step-by-step. Even experienced hands may find these sorts of rules |
| 394 |
difficult to construct and debug. |
| 395 |
|
| 396 |
Note that "lines" is now the so-called "start symbol" of our |
| 397 |
grammar. It is, in other words, the goal of every parse. By default |
| 398 |
the left-hand side symbol of the first rule is the start symbol. This |
| 399 |
may be overridden with a %start declaration in the tokens section (on |
| 400 |
which, see the sample Ibpag2 input file below). |
| 401 |
|
| 402 |
With our new, multi-line start symbol in place, the only piece |
| 403 |
that needs to be added, in order to make our calculator specification |
| 404 |
a full working input to Ibpag2, is a tokenizer. A tokenizer is a |
| 405 |
routine that reads input from a file or from some other stream (e.g. |
| 406 |
the user's console), and then segments this input into tokens that its |
| 407 |
parser can understand. In some cases, the tokens must be accompanied |
| 408 |
by a literal value. For example, if we encounter a TERM, we return |
| 409 |
TERM, just as it is listed in the %token declaration. But what is the |
| 410 |
literal value of a TERM token? It could be, for example, 9, or 5, or |
| 411 |
700. The tokenizer returns the symbol TERM, in this case, but then |
| 412 |
records that TERM's actual value by setting some global variable. In |
| 413 |
Ibpag2's parser, this variable is assumed to be "iilval." In the |
| 414 |
tokenizer, therefore, one might write |
| 415 |
|
| 416 |
iilval := (literal value) |
| 417 |
suspend TERM |
| 418 |
|
| 419 |
For literal operators like '+' and '*', there is no need to set |
| 420 |
iilval, since their literal value is irrelevant. One simply returns |
| 421 |
these as integers (usually via "suspend ord(c)"). |
| 422 |
|
| 423 |
The tokenizer routine is normally appended to the grammar |
| 424 |
after another double percent sign. Everything after this second |
| 425 |
double percent sign is copied literally to the output file. |
| 426 |
Alternatively, the tokenizer can be $included via Icon's preprocessor. |
| 427 |
Ibpag2 demands that the tokenizer be called iilex, and that it take a |
| 428 |
single file argument, that it be a generator, and that it fail when it |
| 429 |
reaches end-of-input. Combined with our "lines" productions, the |
| 430 |
addition of an iilex routine to our calculator grammar yields the |
| 431 |
following Ibpag2 input file: |
| 432 |
|
| 433 |
%token TERM |
| 434 |
%left '+', '-' |
| 435 |
%left '*', '/' |
| 436 |
%right UMINUS |
| 437 |
|
| 438 |
%start lines |
| 439 |
|
| 440 |
%% |
| 441 |
|
| 442 |
expression : TERM { return arg1 } |
| 443 |
| expression, '+', expression { return arg1 + arg3 } |
| 444 |
| expression, '-', expression { return arg1 - arg3 } |
| 445 |
| expression, '*', expression { return arg1 * arg3 } |
| 446 |
| expression, '/', expression { return arg1 / arg3 } |
| 447 |
| '-', expression %prec UMINUS { return - arg2 } |
| 448 |
|
| 449 |
lines : lines, expression, '\n' { write(arg2) } |
| 450 |
| lines, '\n' |
| 451 |
| epsilon |
| 452 |
|
| 453 |
%% |
| 454 |
|
| 455 |
procedure iilex(infile) |
| 456 |
|
| 457 |
local nextchar, c, num |
| 458 |
|
| 459 |
nextchar := create !(!infile || "\n" || "\n") |
| 460 |
c := @nextchar | fail |
| 461 |
|
| 462 |
repeat { |
| 463 |
if any(&digits, c) then { |
| 464 |
if not (\num ||:= c) then |
| 465 |
num := c |
| 466 |
} else { |
| 467 |
if iilval := \num then { |
| 468 |
suspend TERM |
| 469 |
num := &null |
| 470 |
} |
| 471 |
if any('+-*/()\n', c) then { |
| 472 |
iilval := c |
| 473 |
suspend ord(c) |
| 474 |
} else { |
| 475 |
if not any(' \t', c) then { |
| 476 |
# deliberate error - will be handled later |
| 477 |
suspend &null |
| 478 |
} |
| 479 |
} |
| 480 |
} |
| 481 |
c := @nextchar | break |
| 482 |
} |
| 483 |
if iilval := \num then { |
| 484 |
return TERM |
| 485 |
num := &null |
| 486 |
} |
| 487 |
|
| 488 |
end |
| 489 |
|
| 490 |
procedure main() |
| 491 |
return iiparse(&input, 1) |
| 492 |
end |
| 493 |
|
| 494 |
As noted above, the tokenizer (iilex) must be a generator. It must |
| 495 |
suspend integers either directly (e.g. ord(c)), or else via symbolic |
| 496 |
defines like TERM, created by Ibpag2 on the basis of %token, %right, |
| 497 |
%left, and %nonassoc declarations. The tokenizer must fail on end of |
| 498 |
input. |
| 499 |
|
| 500 |
If you like, cut the above code out, place it in a temporary |
| 501 |
file, tmp.ibp, and then feed this file to Ibpag2 by typing "ibpag2 -f |
| 502 |
tmp.ibp -o tmp.icn." If your system supports input and output |
| 503 |
redirection, type: "ibpag2 < tmp.ibp > tmp.icn." Ibpag2 will turn |
| 504 |
your grammar specifications and actions into a routine called iiparse. |
| 505 |
If you look above, you will see that I appended a main procedure that, |
| 506 |
in fact, calls iiparse(). Iiparse() takes two arguments: 1) an input |
| 507 |
stream, and 2) a switch that, if nonnull, tells the parser to fail |
| 508 |
rather than abort on unrecoverable errors. When Ibpag2 is finished |
| 509 |
creating its output file (tmp.icn above), compile that file the way |
| 510 |
you would compile any other Icon program (e.g. "icont tmp"). Finally, |
| 511 |
run the executable. You should be able to type in various simple |
| 512 |
arithmetic expressions and have the program spit back answers each |
| 513 |
time you hit a return. The only problem you might encounter is that |
| 514 |
the parser aborts on erroneous input. |
| 515 |
|
| 516 |
The issue of erroneous input brings up yet another point of |
| 517 |
general Ibpag2 usage. Normally, if one is processing input, one does |
| 518 |
not want to abort on errors, but rather just emit an error message, |
| 519 |
and to continue processing - if this is at all possible. To do this, |
| 520 |
Ibpag2 provides a simple but fairly effective mechanism: A reserved |
| 521 |
"error" token. |
| 522 |
|
| 523 |
When Ibpag2 encounters an error, it will remove symbols from |
| 524 |
its stack until it has backtracked to a point where the error token is |
| 525 |
legal. It then shifts the error token onto the stack, and tries to |
| 526 |
re-start the token stream at the point where it left off, discarding |
| 527 |
tokens if necessary in order to get itself resynchronized. The parser |
| 528 |
considers itself resynchronized when it has successfully read and |
| 529 |
shifted three tokens after shifting the error token. Until then it |
| 530 |
remains in an error state, and will not output additional error |
| 531 |
messages as it discards tokens. |
| 532 |
|
| 533 |
This explanation may sound a bit abstruse, but in practice it |
| 534 |
is turns out to be quite simple. To implement error handling for our |
| 535 |
calculator, we really have to add only one production to the end of |
| 536 |
the "lines" section: |
| 537 |
|
| 538 |
lines : lines, expression, '\n' { write(arg2) } |
| 539 |
| lines, '\n' |
| 540 |
| epsilon |
| 541 |
| error, '\n' { |
| 542 |
write("syntax error; try again:") |
| 543 |
iierrok |
| 544 |
} |
| 545 |
|
| 546 |
Given the above grammar, the parser will handle errors as follows: If |
| 547 |
an error occurs (say it has an expression then an operator on its |
| 548 |
stack and sees a newline on the input stream) the parser will throw |
| 549 |
out the operator, then check if the error token would be OK in this |
| 550 |
state (which it would not). Then it would throw out the expression. |
| 551 |
At this point, the stack is in the ready-to-read-a-lines state - the |
| 552 |
state it was in before it read the last expression. Since "lines" may |
| 553 |
consist of error and '\n,' the error token is legal here, and so the |
| 554 |
parser pushes error onto the stack, then looks back at the input |
| 555 |
stream (where a newline is still waiting). Since the newline now |
| 556 |
completes the rule lines : error, '\n', the parser pushes the newline |
| 557 |
onto its stack, then executes the action associated with this |
| 558 |
production, i.e. it writes "syntax error; try again:" to the console, |
| 559 |
prompting the user for additional input. |
| 560 |
|
| 561 |
The keyword "iierrok" in the above error production's action |
| 562 |
field is there for a subtle, but important, reason: It tells the |
| 563 |
parser to consider itself resynchronized, even if three tokens have |
| 564 |
not yet been shifted. If iierrok were not in the action code for this |
| 565 |
rule, and the user were to supply more bad input after the prompt, |
| 566 |
then the parser would simply discard those tokens, without emitting |
| 567 |
another error message. Why? Because, as you will recall, the parser |
| 568 |
discards tokens after an error, in efforts to resynchronize itself. |
| 569 |
Until it reads and shifts three tokens successfully, it considers |
| 570 |
itself in an error state, and will not emit additional error messages. |
| 571 |
The three-token resync rule is there to prevent a cascade of |
| 572 |
irrelevant error messages touched off by a single error. In our |
| 573 |
calculator's case above, though, we are smarter than the parser. We |
| 574 |
know that it is resynchronized as soon as it reduces error, '\n' to |
| 575 |
lines. So if a syntax error occurs on the next token, it should be |
| 576 |
reported. Adding "iierrok" to the action insures that the parser will |
| 577 |
do just this. |
| 578 |
|
| 579 |
In addition to iierrok, there are several other directives |
| 580 |
Ibpag2 accepts as part of the action code segments. These are as |
| 581 |
follows: |
| 582 |
|
| 583 |
iiclearin clear the current input token |
| 584 |
IIERROR perform error recovery |
| 585 |
IIACCEPT simulate an accept action |
| 586 |
|
| 587 |
There are several other directives (all implemented as macros) that |
| 588 |
Ibpag2 accepts in GLR mode. For a discussion of GLR mode, see below, |
| 589 |
section 5. IIERROR in particular, and error recovery in general, work |
| 590 |
a bit differently in that mode than they do in Ibpag2's normal (i.e. |
| 591 |
LR) mode. |
| 592 |
|
| 593 |
There are admittedly many other topics that might be covered |
| 594 |
here. This treatment, however, is intended as a general nontechnical |
| 595 |
introduction, and not as a complete textbook on parser generation use. |
| 596 |
If you want to learn more about this topic, consult the bibliography. |
| 597 |
Also, check the UNIX manual pages on the YACC utility (Yet Another |
| 598 |
Compiler Compiler). Ibpag's input format is fairly close (too close, |
| 599 |
perhaps) to YACC's. In fact, most of what is said about YACC in UNIX |
| 600 |
documentation can be carried directly over to Ibpag2. Several salient |
| 601 |
differences, though, should be kept in mind: |
| 602 |
|
| 603 |
1) YACC's "$$ = x" constructs are replaced by "return x" (e.g. |
| 604 |
"$$ = $1 + $3" -> "return $1 + $3" [$1 is a synonym for |
| 605 |
"arg1", $3 for "arg3", etc.]) |
| 606 |
|
| 607 |
2) all variables within a given action are, by default, local |
| 608 |
to that action; i.e. they cannot be accessed by other |
| 609 |
actions unless you declare them global elsewhere (e.g. in |
| 610 |
the pass-through part of the declarations section %{ ... |
| 611 |
%}) |
| 612 |
|
| 613 |
3) the %union and %type declarations/tags are not needed by |
| 614 |
Ibpag2 (both for better and for worse) |
| 615 |
|
| 616 |
4) tokens and symbols are separated from each other by a comma |
| 617 |
in Ibpag2 files (e.g. %token '+', '-' and S : NP, VP) |
| 618 |
|
| 619 |
5) epsilon is indicated by the keyword "epsilon" (e.g. REL : |
| 620 |
epsilon), and not by an empty RHS |
| 621 |
|
| 622 |
6) both epsilon and error *may* be declared as %tokens for |
| 623 |
reasons of precedence, although they retain hard-coded |
| 624 |
internal values (-2 and -1, respectively) |
| 625 |
|
| 626 |
7) all actions must follow the last RHS symbol of the rule |
| 627 |
they apply to (preceded by an optional %prec directive); to |
| 628 |
achieve S : NP { action1 }, VP { action2 }, insert a dummy |
| 629 |
rule: S : NP, dummy, VP { action2 }; dummy : epsilon { |
| 630 |
action1 } ; |
| 631 |
|
| 632 |
8) YYERROR, YYACCEPT, yyclearin, and yyerrok are the same, |
| 633 |
except they are written IIERROR, IIACCEPT, iiclearin, and |
| 634 |
iierrok (i.e. "ii" replaces "yy") |
| 635 |
|
| 636 |
9) Ibpag2's input files are tokenized as modified Icon files, |
| 637 |
and, as a consequence, Icon's reserved words must not be |
| 638 |
used as symbols (e.g. "if : if, then" is no go) |
| 639 |
|
| 640 |
I myself find YACC to be ugly. As a result, Ibpag2 is not an exact |
| 641 |
YACC clone. I would like to underscore the fact that I have no |
| 642 |
intention to move in this direction, either. It's as YACC-like as |
| 643 |
it's going to get! |
| 644 |
|
| 645 |
Both YACC and non-YACC users should note number 9 in the above |
| 646 |
list. Don't use things like "while," "every," "do," etc. as symbols |
| 647 |
in your grammar! Just use the same rules for Ibpag2 nonterminals as |
| 648 |
for Icon variables, and you'll be OK. |
| 649 |
|
| 650 |
For those that just can't bear using anything but a strictly |
| 651 |
YACC-conformant system, I've included a preprocessor with the Ibpag2 |
| 652 |
distribution called (at one user's recommendation) "iacc." Iacc reads |
| 653 |
&input - assumed to be a YACCish grammar - and sends to &output an |
| 654 |
Ibpag2-conformant file. I have not tested this file extensively, and |
| 655 |
there are likely to be bugs in the way I've handled the necessary 2 |
| 656 |
token lookaheads and value stack references. Give it a whirl, though, |
| 657 |
if you are feeling adventurous. The only reason I personally use Iacc |
| 658 |
is that some YACCs (e.g. BSD YACC) have particularly nice debugging |
| 659 |
messages and help. If my grammar is particularly complex, I just run |
| 660 |
it through YACC without action code first, then use Iacc to convert it |
| 661 |
to Ibpag2 format. Iacc's output, as I noted, is not meant to be |
| 662 |
pretty, so I invariably end up doing a little editing - usually just |
| 663 |
respacing a few rules, and re-inserting any comments that I might have |
| 664 |
put in the original YACC file. |
| 665 |
|
| 666 |
In general, Ibpag2 (like YACC) handles epsilon moves and |
| 667 |
indirect cycles. LR-mode shift-reduce conflicts are also handled in |
| 668 |
the normal way (i.e. pick the rule with the highest priority, and, in |
| 669 |
cases where the priority is the same, check the associativities). In |
| 670 |
contrast to YACC, Ibpag2 flags reduce/reduce conflicts as errors |
| 671 |
(since these often conceal deeper precedence problems and just plain |
| 672 |
kludges). Reduce/reduce conflict errors are easily enough remedied, |
| 673 |
if need be, via (dummy) precedences. One can convert these errors to |
| 674 |
warnings by specifying -y on the command line. With the -y option, |
| 675 |
reduce/reduce conflicts are resolved in favor of the rule that occurs |
| 676 |
first in the grammar. The -y switch also prevents Ibpag2 from |
| 677 |
aborting on shift/reduce conflicts, telling it instead to resolve in |
| 678 |
favor of shift. Basically, -y is a partial YACC compatibility switch. |
| 679 |
Normally (i.e. in SLR mode) Ibpag2 is much more finicky than YACC |
| 680 |
about conflicts in its grammars. |
| 681 |
|
| 682 |
Also in contrast to YACC, Ibpag2 supports multiple |
| 683 |
simultaneous parsers. Ibpag2 normally names its main parser routine |
| 684 |
iiparse(). By using the -m command-line option, however, you can |
| 685 |
override this default behavior, and force Ibpag2 to augment this name |
| 686 |
in some uniquely identifiable fashion. For example, "ibpag2 -m _1 < |
| 687 |
tmp.ibp > tmp.icn" will force Ibpag2 to write a parser called |
| 688 |
"iiparse_1" to tmp.icn. Note that, instead of calling iilex, this |
| 689 |
iiparse_1() routine will now call iilex_1, and all necessary global |
| 690 |
variables will have _1 appended to them (e.g. errors will become |
| 691 |
errors_1). I don't expect that many people will have occasion to use |
| 692 |
this feature. It is there, though, for those that want it. |
| 693 |
|
| 694 |
|
| 695 |
4.__Debugging |
| 696 |
|
| 697 |
Constructing and debugging LR(1) family parsers can sometimes |
| 698 |
be hair raising, even with a parser generator. Several precautions |
| 699 |
can be taken, however, to minimize the agony. The first is to declare |
| 700 |
all tokens initially as part of a single %token declaration, i.e. with |
| 701 |
no precedences, and with the same associativities. Also, leave out |
| 702 |
action code until the grammar seems to be working. In this stage, you |
| 703 |
can even run the grammar through (BSD)YACC or GNU Bison. All you |
| 704 |
would need to do is remove the commas between tokens and symbols, and |
| 705 |
place a semicolon at the end of every rule. During this and all |
| 706 |
debugging stages, supply Ibpag2 with a -v command-line switch. This |
| 707 |
will cause Ibpag2 to write a summary of rules, tokens, and its two |
| 708 |
state tables to "ibpag2.output" (a bit like GNU Bison, but with a |
| 709 |
hard-coded name). If you get messages about conflicts in your parse |
| 710 |
tables (e.g. "unresolvable reduce/reduce conflict, state 5, token |
| 711 |
257, rules 4,5"). This file will tell you what rules these are, and |
| 712 |
what token number 257 is. Use precedences and associativities to |
| 713 |
clear these problems up as they arise. If you are comfortable having |
| 714 |
reduce/reduce errors resolved by the order in which the conflicting |
| 715 |
rules occur, then use the -y command-line switch. With -y on the |
| 716 |
command line, Ibpag2 will always resolve in favor of the earlier rule. |
| 717 |
This option will also cause it to resolve all shift/reduce conflicts |
| 718 |
in favor of shift. |
| 719 |
|
| 720 |
There are certain languages that are not ambiguous that SLR(1) |
| 721 |
parsers like Ibpag2 will fail to produce an unambiguous parse table |
| 722 |
for. The classic example is |
| 723 |
|
| 724 |
expr : lval, '=', rval | rval |
| 725 |
lval : '*', rval | ID |
| 726 |
rval : lval |
| 727 |
|
| 728 |
C programmers will recognize this as a toy expression grammar with |
| 729 |
code for identifiers, assignments, and pointers. The problem is that |
| 730 |
if we feed this grammar to Ibpag2, it will claim that there is a |
| 731 |
conflict on lookahead '='. In truth, there is no ambiguity. The SLR |
| 732 |
parser simply doesn't remember the pathway the parser used to get to |
| 733 |
the state it is in when it sees '=' on the input stream. Whether the |
| 734 |
parser gets into this state by seeing '*' plus and ID, or by seeing |
| 735 |
just an ID, it knows to turn the ID into an lval. Then it knows to |
| 736 |
turn lval into rval. At this point, though, it doesn't know whether |
| 737 |
to shift the = sign via rule 1, or to turn rval and the preceding '*' |
| 738 |
into an lval. The parser has "forgotten" that the '*' is there |
| 739 |
waiting on level down on the stack! |
| 740 |
|
| 741 |
The solution to this problem is actually quite simple (at |
| 742 |
least in concept). Just provide a unique pathway in the grammar for |
| 743 |
the conflicting rules. In this case, they are rules 1 and 5 (the |
| 744 |
first and last): |
| 745 |
|
| 746 |
expr : lval, '=', rval | rval |
| 747 |
lval : '*', pval | ID |
| 748 |
pval : lval |
| 749 |
rval : lval |
| 750 |
|
| 751 |
Now when the parser sees '*,' it can only have a pval after it. Never |
| 752 |
mind that pval is composed of precisely the same things as rval. The |
| 753 |
point is that the parser generator follows a different route after |
| 754 |
seeing '*' than if it starts with ID and no preceding '*'. Hence it |
| 755 |
"remembers" that that the '*' is back on the stack, waiting for the |
| 756 |
"lval : '*', pval" rule to apply. There is no more conflict. |
| 757 |
|
| 758 |
Go ahead and run these grammars through Ibpag2 if you aren't |
| 759 |
sure what is going on. Remember to declare ID as a token, and to |
| 760 |
place "%%" in the appropriate spot! |
| 761 |
|
| 762 |
If you get your parser up and running, but find that it is not |
| 763 |
functioning quite the way you expect, add the following line somewhere |
| 764 |
near the start of Ibpag2's output file: |
| 765 |
|
| 766 |
$define IIDEBUG |
| 767 |
|
| 768 |
If you like, you can add it to the beginning of your Ibpag2 input |
| 769 |
file. Place it in the declarations section (before the first double |
| 770 |
percent sign), and surround it by %{ and %}, e.g.: |
| 771 |
|
| 772 |
%{ |
| 773 |
$define IIDEBUG |
| 774 |
%} |
| 775 |
|
| 776 |
This tells Ibpag2 to send $define IIDEBUG straight through to the |
| 777 |
output file. |
| 778 |
|
| 779 |
What defining IIDEBUG does is tell iiparse, once compiled, to |
| 780 |
emit profuse debugging messages about the parser's actions, and about |
| 781 |
the state of its stacks. This display will not make a whole lot of |
| 782 |
sense to anyone who doesn't understand LR-family parsers, so those who |
| 783 |
want to access this feature should perhaps go through a standard |
| 784 |
reference like Aho, Sethi, and Ullman [1]. |
| 785 |
|
| 786 |
If, after you are finished debugging your grammar, you find |
| 787 |
that Ibpag2's output files are rather large, you may try saving space |
| 788 |
by compressing the action and goto tables. This is accomplished by |
| 789 |
invoking Ibpag2 with the -c (compress) option. Using this option |
| 790 |
makes debugging difficult, and makes the parser run a bit more slowly. |
| 791 |
It also only works for rather large grammars with long nonterminal |
| 792 |
symbol names. Don't even consider it until the grammar is thoroughly |
| 793 |
debugged and you have determined that the output file's size is just |
| 794 |
too great for practical use. Even then, compression may or may not |
| 795 |
help, depending on how long your nonterminal names are. In general, |
| 796 |
Ibpag2 is best as a teaching tool, or as a production system for |
| 797 |
medium or small grammars. |
| 798 |
|
| 799 |
|
| 800 |
5.__Using_Ibpag2_with_Non-LR_Grammars |
| 801 |
|
| 802 |
There may be times when you *want* to parse languages that no |
| 803 |
LR-based algorithm can handle. There may be times, that is, when the |
| 804 |
grammar you want to use contains conflicts or ambiguities that are |
| 805 |
there by design, and not by oversight. For example, you may want to |
| 806 |
parse a natural language. Full-blown natural languages involve many |
| 807 |
highly ambiguous constructs, and are not LR-parsable. By invoking it |
| 808 |
with the -a option, Ibpag2 can parse or recognize certain natural |
| 809 |
languages, or, more practically speaking, certain NL subsets. The |
| 810 |
letter "a" in -a is supposed to stand for "ambiguous," although what |
| 811 |
this option really does is put Ibpag2 into a quasi-GLR mode - i.e. |
| 812 |
into a kind of "generalized" LR mode in which it can accept non-LR |
| 813 |
grammars [4,5]. |
| 814 |
|
| 815 |
User-visible changes to Ibpag2's operation in quasi-GLR mode |
| 816 |
(i.e. with the -a option) are as follows: |
| 817 |
|
| 818 |
1) iiparse() is now a generator |
| 819 |
2) action code can use suspend as well as return |
| 820 |
3) IIERROR places the current thread in an error state (i.e. |
| 821 |
it doesn't *necessarily* trigger error recovery; see below) |
| 822 |
4) there are two new action-code directives (iiprune and |
| 823 |
iiisolate) and a general define (AUTO_PRUNE) |
| 824 |
5) conflicts due to ambiguities in the grammar no longer |
| 825 |
result in aborted processing (so, e.g., if you do not |
| 826 |
specify the -y option on a grammar with reduce/reduce |
| 827 |
conflicts, Ibpag2 will simply generate a parser capable of |
| 828 |
producing multiple parses for the same input) |
| 829 |
|
| 830 |
In quasi-GLR mode, iiparse() should be invoked in a way that |
| 831 |
will render multiple results usable, if they are available (e.g. |
| 832 |
"every result := iiparse(&input) do...". Action code is also allowed |
| 833 |
to produce more than one value (i.e. to use suspend). When it does |
| 834 |
so, iiparse() creates separate parse threads for each value. So, for |
| 835 |
instance, if your action code for some production suspends both of the |
| 836 |
following lists, |
| 837 |
|
| 838 |
["noun", "will", "gloss: desire"] |
| 839 |
["noun", "will", "gloss: legal document mandating how _ |
| 840 |
one's possessions are to be disposed _ |
| 841 |
of after one's death"], |
| 842 |
|
| 843 |
iiparse() would create two separate parse threads - one for each |
| 844 |
result. Note that in this case, the syntactic structure of each |
| 845 |
thread is the same. It is their semantics (i.e. the stuff on the |
| 846 |
value stack) that differs. |
| 847 |
|
| 848 |
If you use the iierrok and iiclearin macros in your action |
| 849 |
code before suspending any result, their affect persists through all |
| 850 |
subseqent suspensions and resulting parse threads. If you use these |
| 851 |
macros after suspending one or more times, however, they are valid |
| 852 |
only for the parse thread generated by the next suspension. By way of |
| 853 |
contrast, the IIERROR macro *always* flags only the next parse thread |
| 854 |
as erroneous. Likewise, IIACCEPT always simulates an accept action on |
| 855 |
the next suspension only. IIERROR and IIACCEPT, in other words, never |
| 856 |
have any effect on subsequent suspensions and parse threads other than |
| 857 |
the one that immediately follows them. This is true of iierrok and |
| 858 |
iiclearin only when used after the first suspension. |
| 859 |
|
| 860 |
In quasi-GLR mode, IIERROR (number three in the difference |
| 861 |
list above) becomes a mechanism for placing the current parse thread |
| 862 |
in error mode. This is similar to, but not quite identical to, how |
| 863 |
IIERROR functions in straight LR mode. In quasi-GLR mode, if other |
| 864 |
threads can carry on the parse without error the erroneous parse |
| 865 |
thread is quietly clobbered. Full-blown error recovery only occurs if |
| 866 |
all of the other parsers halt as well. This makes sense if you think |
| 867 |
about it. Why keep erroneous threads around when there are threads |
| 868 |
still continuing a valid parse? For some large interactive systems, |
| 869 |
it might be necessary to keep bogus threads around longer, and weed |
| 870 |
them out only after a lengthy grading process. If you are |
| 871 |
constructing a system such as this, you'll have to modify Ibpag2's |
| 872 |
iiglrpar.lib file. In particular, you'll need to change the segment |
| 873 |
in iiparse() that takes out the trash, so to speak, in such a way that |
| 874 |
it does so only if the error count in a given parser either rises |
| 875 |
above a specific threshhold or else exceeds the number of errors in |
| 876 |
the "most correct" parser by a certain amount. This is not that hard |
| 877 |
to do. I just don't expect that most parsers people generate with |
| 878 |
Ibpag2 will use IIERROR or error recovery in general in so involved a |
| 879 |
fashion. |
| 880 |
|
| 881 |
Iiprune and iiisolate (number 4 above) are used to control the |
| 882 |
growth of the parallel parser array. In order to give straightforward |
| 883 |
(read "implementationally trivial") support for action code, Ibpag2 |
| 884 |
cannot create a parse "forest" in the sense that a standard GLR parser |
| 885 |
does. Instead, it simply duplicates the current parser environment |
| 886 |
whenever it encounters a conflict in its action table. Even if the |
| 887 |
conflict turns out to reflect only a local ambiguity, the parsers, by |
| 888 |
default, remain separate. Put differently, Ibpag2's quasi-GLR parser, |
| 889 |
by default, makes no direct effort to reduce the size of its parser |
| 890 |
arrays or to alter the essentially linear structure of their value and |
| 891 |
state stacks. Size reduction, where necessary and/or desirable, is up |
| 892 |
to the programmer. What the iiprune macro is there to do is to give |
| 893 |
the programmer a way of pruning a given thread out of the active |
| 894 |
parser list. Iiisolate allows him or her to prune out every thread |
| 895 |
*but* the current one. AUTO_PRUNE makes the parser behave more like a |
| 896 |
standard GLR parser, instructing it to prune parse threads that are |
| 897 |
essentially duplicating another parse thread's efforts. The parser, |
| 898 |
though, does not build a parse tree per se, the way most GLR parsers |
| 899 |
typically do, but rather manipulates its value stack like a |
| 900 |
traditional LR-family parser. |
| 901 |
|
| 902 |
Iiprune is useful when, for example, the semantics (i.e. your |
| 903 |
"action" code segments) determine that a given parse thread is no |
| 904 |
longer viable, and you want to signal the syntactic analyzer not to |
| 905 |
continue pursuing it. The difference between iiprune and IIERROR is |
| 906 |
that iiprune clobbers the current parser immediately. IIERROR only |
| 907 |
puts it into an error state. If all active parsers end up in an error |
| 908 |
state, and none can shift additional input symbols, then the IIERROR |
| 909 |
macro induces error recovery. Iiprune does not. NB: iiprune, if used |
| 910 |
in action code that suspends multiple results, cancels the current and |
| 911 |
remaining results (i.e. it does not clobber parsers already spun off |
| 912 |
by previous suspensions by invocation of that same code; it merely |
| 913 |
cuts the result sequence). Iiprune essentially stands in for "fail" |
| 914 |
in this situation. Fail itself can be used in the code, but be warned |
| 915 |
that iiparse() will still push *at least one* value onto its value |
| 916 |
stack, even if a given action code segment fails. This keeps the |
| 917 |
value stack in sync with the syntax. To avoid confusion, I recommend |
| 918 |
not using "fail" in any action code. |
| 919 |
|
| 920 |
Iiisolate is useful if, during error recovery, you prompt the |
| 921 |
user interactively, or do something else that cannot be elegantly done |
| 922 |
in parallel for two or more distinct parse threads. Iiisolate allows |
| 923 |
you to preserve only the the current parse thread, and to clobber the |
| 924 |
rest. Iiisolate can also be useful as a way of making sure that only |
| 925 |
one thread carries on the parse in non-error situations. Suppose that |
| 926 |
we have a series of productions: |
| 927 |
|
| 928 |
sentences : sentences sentence '\n' |
| 929 |
{ print_parse(arg2) } |
| 930 |
| sentences '\n' |
| 931 |
| error '\n' |
| 932 |
| epsilon |
| 933 |
|
| 934 |
If we get a sentence with more than one parse, all of the underlying |
| 935 |
threads that produced these parses will be active for the next |
| 936 |
sentence as well. In many situations this will not be what we want. |
| 937 |
If our desire it to have only one active parse thread at the start of |
| 938 |
each sentence, we simply tell our lexical analyzer to suspend two |
| 939 |
newlines every time it sees a newline on the input stream. This |
| 940 |
insures that the second rule will always apply right after the first. |
| 941 |
We then insert iiisolate directives for both it and the one error |
| 942 |
production: |
| 943 |
|
| 944 |
sentences : sentences sentence '\n' |
| 945 |
{ print_parse(arg2) } |
| 946 |
| sentences '\n' |
| 947 |
{ iiisolate } |
| 948 |
| error '\n' |
| 949 |
{ iiisolate; iierrok } |
| 950 |
| epsilon |
| 951 |
|
| 952 |
The effect here is to allow multiple parsers to be generated only |
| 953 |
while parsing "sentence". The iiisolate directive, in other words, |
| 954 |
sees to it that no sentence parse will ever begin with multiple active |
| 955 |
parsers. As with LR mode, iierrok clears the error flag for the |
| 956 |
(current) parser. |
| 957 |
|
| 958 |
Note that if you use iiisolate in action code that suspends |
| 959 |
multiple results, iiisolate will clobber all parsers but the one |
| 960 |
generated by the next suspension. |
| 961 |
|
| 962 |
If there is no need for close control over the details of the |
| 963 |
parser array, and you wish only to clobber parsers that end up doing |
| 964 |
the same thing as some other parser (and hence returning identical |
| 965 |
values), then just make sure you add "$define AUTO_PRUNE" to the |
| 966 |
pass-through code section at the top of the file. Put differently, |
| 967 |
defining AUTO_PRUNE instructs the quasi-GLR parser to weed out parsers |
| 968 |
that are in the same state, and which have identical value stacks. |
| 969 |
AUTO_PRUNE can often be used in place of iiisolate in situations like |
| 970 |
the one discussed just above. Its only drawback is that it slows |
| 971 |
the parser a bit. |
| 972 |
|
| 973 |
Other than these deviations (action code and iiparse becoming |
| 974 |
generators, IIERROR's altered behavior, and the addition of iiprune, |
| 975 |
iiisolate, and AUTO_PRUNE), Ibpag2's quasi-GLR mode - at least on the |
| 976 |
surface - works pretty much like its straight LR mode. In fact, if |
| 977 |
you take one of your SLR(1) grammars, and run it through Ibpag2 using |
| 978 |
the -a option, you probably won't notice any difference in the |
| 979 |
resulting automaton unless you do some debugging or perform some |
| 980 |
timing tests (the GLR parser is slower, though for straight SLR(1) |
| 981 |
grammars not by much). Even with non-SLR(1) grammars, the quasi-GLR |
| 982 |
parser will clip along merrily, using all the same sorts of rules, |
| 983 |
action code, and macros that you would typically use in LR mode! |
| 984 |
|
| 985 |
|
| 986 |
6.__Installing_Ibpag |
| 987 |
|
| 988 |
If you are a UNIX user, or have a generic "make" utility, you |
| 989 |
are in luck. Just edit Makefile.dist according to the directions |
| 990 |
given in that file, rename it as "makefile," then execute "make." |
| 991 |
Ibpag2 should be created automatically. If everything goes smoothly, |
| 992 |
then "make install" (su-ing root, if both possible and necessary for |
| 993 |
correct installation of the iiparse.icn file). Check with your system |
| 994 |
administrator if you are on a public system, and aren't sure what to |
| 995 |
do. |
| 996 |
|
| 997 |
Please be sure to read the directions in the makefile |
| 998 |
carefully, and set DESTDIR and LIBDIR to the directory where you want |
| 999 |
the executable and parser file to reside. Also, make sure the paths |
| 1000 |
you specify are correct for your Icon executables. |
| 1001 |
|
| 1002 |
If you are using some other system - one that lacks "make" - |
| 1003 |
then shame on your manufacturer :-). You'll be a bit inconvenienced. |
| 1004 |
Try typing: |
| 1005 |
|
| 1006 |
icont -o ibpag2 follow.icn ibpag2.icn ibreader.icn \ |
| 1007 |
ibtokens.icn ibutil.icn ibwriter.icn iohno.icn \ |
| 1008 |
outbits.icn slritems.icn slrtbls.icn shrnktbl.icn \ |
| 1009 |
version.icn slshupto.icn |
| 1010 |
|
| 1011 |
The backslashes merely indicate that the next line is a continuation. |
| 1012 |
The whole thing should, in other words, be on a single line. |
| 1013 |
|
| 1014 |
If your operating system support environment variables, and |
| 1015 |
you have set up your LPATH according to the specifications in the Icon |
| 1016 |
distribution (see below), then you may copy iiparse.lib and |
| 1017 |
iiglrpar.lib to some file in your LPATH. If you do not do this, or if |
| 1018 |
your OS does not support environment variables, then you must be in |
| 1019 |
the directory where you keep your Ibpag2 files when you use it, or |
| 1020 |
else invoke Ibpag2 with the -p dirname option (where dirname is the |
| 1021 |
directory that holds the iiparse.lib and iiglrpar.lib files that come |
| 1022 |
with the Ibpag2 distribution). The .lib files contain template |
| 1023 |
parsers that are critical to Ibpag2's operation. Ibpag2 will abort if |
| 1024 |
it cannot find them. |
| 1025 |
|
| 1026 |
If your operating system permits the creation of macros or |
| 1027 |
batch files, it might be useful to create one that changes |
| 1028 |
automatically to the Ibpag2 source directory, and runs the executable. |
| 1029 |
This has the side-benefit of making it easier for Ibapg2 to find the |
| 1030 |
parser library files, iiparse.lib and iiglrpar.lib. Under DOS, for |
| 1031 |
instance, one might create a batch file that says: |
| 1032 |
|
| 1033 |
c: |
| 1034 |
cd c:\ibpag2 |
| 1035 |
iconx ibpag2 %1 %2 %3 %4 %5 %6 %7 %8 %9 |
| 1036 |
|
| 1037 |
DOS, it turns out, has to execute Icon files indirectly through iconx, |
| 1038 |
so this technique has yet another advantage in that it hides the |
| 1039 |
second level of indirection - although it prevents you from using |
| 1040 |
input and output redirection. Naturally, the above example assumes |
| 1041 |
that Ibpag2 is in c:\ibpag2. |
| 1042 |
|
| 1043 |
Ibpag2 assumes the existence on your system, not only of an |
| 1044 |
Icon interpreter, but also of an up-to-date Icon Program |
| 1045 |
Library. There are several routines included in the IPL that Bibleref |
| 1046 |
uses. Make sure you (or the local system administrators) have put the |
| 1047 |
IPL online, and have translated the appropriate object modules. Set |
| 1048 |
your IPATH environment variable to point to the place where the object |
| 1049 |
modules reside. Set LPATH to point to the modules' source files. |
| 1050 |
Both IPATH and LPATH are documented in doc directory of the Icon |
| 1051 |
source tree (ipd224.doc). If your system does not support environment |
| 1052 |
variables, copy ximage.icn, options.icn, ebcdic.icn, and escape.icn |
| 1053 |
from the IPL into the Ibpag2 source directory, and compile them in |
| 1054 |
with the rest of the Ibpag2 source files, either by adding them to the |
| 1055 |
SRC variable in the makefile, or by adding them manually to the "icont |
| 1056 |
-o ..." command line given above. |
| 1057 |
|
| 1058 |
If you have any problems installing or using Ibpag2, please |
| 1059 |
feel free to drop me, Richard Goerwitz, an e-mail message at |
| 1060 |
[email protected], or (via the post) at: |
| 1061 |
|
| 1062 |
5410 S. Ridgewood Ct., 2E |
| 1063 |
Chicago, IL 60615 |
| 1064 |
|
| 1065 |
|
| 1066 |
6.__Bibliography |
| 1067 |
|
| 1068 |
1. Aho, Alfred V., Sethi, Ravi, and Ullman, Jeffrey D. Compilers. |
| 1069 |
Addison-Wesley: Reading, Massachusetts, second printing, 1988. |
| 1070 |
|
| 1071 |
2. Griswold, Ralph E. and Griswold, Madge T. The Icon Programming |
| 1072 |
Language. Prentice-Hall, Inc.: Englewood Cliffs, New Jersey, USA, |
| 1073 |
second edition, 1990. |
| 1074 |
|
| 1075 |
3. Griswold, Ralph E., Jeffery, Clinton L., and Townsend, Gregg M. |
| 1076 |
Version 8.10 of the Icon Programming Language. Univ. of Arizona |
| 1077 |
Icon Project Document 212, 1993. (obtain via anonymous FTP from |
| 1078 |
cs.arizona.edu ~ftp/icon/docs/ipd212.doc) |
| 1079 |
|
| 1080 |
4. Tomita, Masaru. Efficient Parsing for Natural Language. Boston: |
| 1081 |
Kluwer Academic Publishers, c. 1985. |
| 1082 |
|
| 1083 |
5. Tomita, Masaru editor. Generalized LR Parsing. Boston: Kluwer |
| 1084 |
Academic Publishers, 1991. |