Debian Codegraph @

ipl/packs/ibpag2/README

raw
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.