| 1 |
############################################################################ |
| 2 |
# |
| 3 |
# Name: ibpag2.icn |
| 4 |
# |
| 5 |
# Title: Icon-based parser generator (version 2) |
| 6 |
# |
| 7 |
# Author: Richard L. Goerwitz |
| 8 |
# |
| 9 |
# Version: 1.22 |
| 10 |
# |
| 11 |
############################################################################ |
| 12 |
# |
| 13 |
# The Basics |
| 14 |
# |
| 15 |
# Ibpag2 is a simple tool for generating parsers from grammar |
| 16 |
# specifications. This may sound pretty arcane to those who have |
| 17 |
# never used a parser generator. In fact, though, this kind of tool |
| 18 |
# forms the basis of most programming language implementations. |
| 19 |
# Parser generators are also used in preprocessors, transducers, |
| 20 |
# compilers, interpreters, calculators and in fact for just about any |
| 21 |
# situation where some form of structured input needs to be read into |
| 22 |
# an internal data structure and/or converted into some form of |
| 23 |
# structured output. This might include something as mundane as |
| 24 |
# reading in recepts or mailing addresses from a file, or turning |
| 25 |
# dates of one type (e.g. "September 3, 1993") into another |
| 26 |
# ("9/3/93"). For more information on how to use it, see the README |
| 27 |
# file included with the Ibpag2 distribution. |
| 28 |
# |
| 29 |
############################################################################ |
| 30 |
# |
| 31 |
# Running Ibpag2: |
| 32 |
# |
| 33 |
# Invoking Ibpag2 is very, very simple. There are quite a few |
| 34 |
# command-line switches, but all are optional: |
| 35 |
# |
| 36 |
# ibpag2 [-f infile] [-m module] [-o outfile] [-p iiparse.lib dir] |
| 37 |
# [-a] [-c] [-v] [-y] |
| 38 |
# |
| 39 |
# Where infile is the Ibpag2 source file (default &input), outfile is |
| 40 |
# the output file (default &output), module is an optional string |
| 41 |
# appended to all global variables and all procedure calls (to allow |
| 42 |
# multiple running parsers), and where -v instructs Ibpag2 to write a |
| 43 |
# summary of its operations to ibpag2.output. Normally all of these |
| 44 |
# arguments can be ignored. Ibpag2 can usually be run using simple |
| 45 |
# shell redirection symbols (if your OS supports them). See the next |
| 46 |
# paragraph for an explanation of the -p option. The -c option is |
| 47 |
# for compressed tables, and -a is for non-LR or ambiguous grammars. |
| 48 |
# See the advanced sections of README file. -y directs Ibpag2 to |
| 49 |
# resolve reduce/reduce conflicts by their order of occurrence in the |
| 50 |
# grammar, and to resolve shift/reduce conflicts in favor of shift - |
| 51 |
# just like YACC. Invoking Ibpag with -h causes it to abort with a |
| 52 |
# brief help message. |
| 53 |
# |
| 54 |
# Make sure that the iiparse.lib and iiglrpar.lib files are in |
| 55 |
# some path listed in your LPATH directory, or else in a data |
| 56 |
# directory adjacent to some IPL "procs" directory in your LPATH. |
| 57 |
# Basically, LPATH is just a space-separated list of places where |
| 58 |
# .icn library source files reside. If your system does not support |
| 59 |
# environment variables, then there are two ways to tell Ibpag2 where |
| 60 |
# the .lib files are without using LPATH. The first is to move into |
| 61 |
# the directory that contains these files. The second is to supply |
| 62 |
# the files' location using Ibpag's -p option (e.g. ibpag2 -p |
| 63 |
# /usr/local/lib/icon/data). |
| 64 |
# |
| 65 |
############################################################################ |
| 66 |
# |
| 67 |
# More Technical Details |
| 68 |
# |
| 69 |
# Technically speaking, Ibpag2 is a preprocessor that accepts a |
| 70 |
# YACC-like source file containing grammar productions and actions, |
| 71 |
# then 1) converts these into parse tables and associated code, 2) |
| 72 |
# adds to them an LR parser, and a few debugging tools, and 3) writes |
| 73 |
# the combination to the standard output, along with the necessary |
| 74 |
# action and goto table construction code. The user must $include, |
| 75 |
# or hard-code into the Ibpag2 source file, a lexical analyzer that |
| 76 |
# returns integers via symbolic $defines generated by %token, %right, |
| 77 |
# etc. declarations in the Ibpag2 source file. |
| 78 |
# |
| 79 |
# Cycles and epsilon moves are handled correctly (to my |
| 80 |
# knowledge). Shift-reduce conflicts are handled in the normal way |
| 81 |
# (i.e. pick the rule with the highest priority, and, in cases where |
| 82 |
# the priority is the same, check the associativities) I decided to |
| 83 |
# flag reduce/reduce conflicts as errors by default, since these |
| 84 |
# often conceal deeper precedence problems. They are easily enough |
| 85 |
# handled, if need be, via dummy precedences. The -y command-line |
| 86 |
# switch turns off this behavior, causing Ibpag2 to resolve |
| 87 |
# reduce/reduce conflicts in a YACCish manner (i.e. favoring the rule |
| 88 |
# that occurs first in the grammar). Ibpag2 normally aborts on |
| 89 |
# shift/reduce conflicts. The -y switch makes Ibpag resolve these in |
| 90 |
# favor of shift, and to keep on processing - again, just like YACC. |
| 91 |
# |
| 92 |
# For more information, see the README file. |
| 93 |
# |
| 94 |
############################################################################ |
| 95 |
# |
| 96 |
# Links: ibreader, ibwriter, slrtbls, ibutil, version, options |
| 97 |
# |
| 98 |
############################################################################ |
| 99 |
|
| 100 |
# link ibreader, ibwriter, slrtbls, ibutil, version, options |
| 101 |
link options |
| 102 |
|
| 103 |
global DEBUG |
| 104 |
|
| 105 |
procedure main(a) |
| 106 |
|
| 107 |
local infile, outfile, verbosefile, atbl, gtbl, grammar, opttbl, |
| 108 |
module, abort_on_conflict, paths, path, parser_name, |
| 109 |
iiparse_file |
| 110 |
|
| 111 |
# Get command-line options. |
| 112 |
opttbl := options(a, "f:o:vdm:p:hcay", bad_arg) |
| 113 |
|
| 114 |
# Abort with help message if -h is supplied. |
| 115 |
if \opttbl["h"] then { |
| 116 |
write(&errout, ib_version()) |
| 117 |
return ib_help_() |
| 118 |
} |
| 119 |
|
| 120 |
# If an input file was specified, open it. Otherwise use stdin. |
| 121 |
# |
| 122 |
if \opttbl["f"] then |
| 123 |
infile := open(opttbl["f"], "r") | |
| 124 |
bad_arg("can't open " || opttbl["f"]) |
| 125 |
else infile := &input |
| 126 |
|
| 127 |
# If an output file was specified, use it. Otherwise use stdout. |
| 128 |
# |
| 129 |
if \opttbl["o"] then |
| 130 |
outfile := open(opttbl["o"], "w") | |
| 131 |
bad_arg("can't open " || opttbl["o"]) |
| 132 |
else outfile := &output |
| 133 |
|
| 134 |
# If a module name was specified (-m), then use it. |
| 135 |
# |
| 136 |
module := opttbl["m"] | "" |
| 137 |
|
| 138 |
# If the debug option was specified, set all verbose output to go |
| 139 |
# to errout. |
| 140 |
# |
| 141 |
if \opttbl["d"] then { |
| 142 |
verbosefile := &errout |
| 143 |
DEBUG := 1 |
| 144 |
} |
| 145 |
|
| 146 |
# If the verbose option was specified, send all verbose output to |
| 147 |
# "ibpag2.output" (a bit like YACC's yacc.output file). |
| 148 |
# |
| 149 |
else if \opttbl["v"] then |
| 150 |
verbosefile := open("ibpag2.output", "w") | |
| 151 |
bad_arg("can't open " || opttbl["v"]) |
| 152 |
|
| 153 |
# Output defines for YACC-like macros. Output iiisolate and |
| 154 |
# iiprune if -a option is specified. Sorry for the ugly code. |
| 155 |
# |
| 156 |
write_defines(opttbl, outfile, module) |
| 157 |
|
| 158 |
# Whew! Now fetch the grammar from the input file. |
| 159 |
# |
| 160 |
# Emit line directives keyed to actual line numbers in the |
| 161 |
# original file. Pass its name as arg4. If obttbl["f"] is |
| 162 |
# null (and the input file is &input), ibreader will default |
| 163 |
# to something else. |
| 164 |
# |
| 165 |
grammar := ibreader(infile, outfile, module, opttbl["f"]) |
| 166 |
if \verbosefile then |
| 167 |
# grammar contains start symbol, rules, and terminal token table |
| 168 |
print_grammar(grammar, verbosefile) |
| 169 |
|
| 170 |
# Fill in parse tables, atbl and gtbl. Abort if there is a |
| 171 |
# conflict caused by an ambiguity in the grammar or by some |
| 172 |
# precedence/associativity problem, unless the -a option is |
| 173 |
# supplied (telling Ibpag2 that ambiguous tables are okay). |
| 174 |
# |
| 175 |
if /opttbl["a"] then |
| 176 |
abort_on_conflict := "yes" |
| 177 |
atbl := table(); gtbl := table() |
| 178 |
make_slr_tables(grammar, atbl, gtbl, abort_on_conflict, opttbl["y"]) |
| 179 |
if \verbosefile then |
| 180 |
# grammar.tbl maps integer terminal symbols to human-readable strings |
| 181 |
print_action_goto_tables(atbl, gtbl, grammar.tbl, verbosefile) |
| 182 |
|
| 183 |
# If -c was specified on the command line, compress the action and |
| 184 |
# goto tables. |
| 185 |
# |
| 186 |
if \opttbl["c"] then { |
| 187 |
write(outfile, "\n$define COMPRESSED_TABLES\n") |
| 188 |
if \verbosefile then |
| 189 |
write(verbosefile, "\nNote: parse tables are compressed") |
| 190 |
shrink_tables(grammar, atbl, gtbl) |
| 191 |
} |
| 192 |
|
| 193 |
# Try to find the .lib file using LPATH. |
| 194 |
# |
| 195 |
parser_name := { |
| 196 |
if \opttbl["a"] then "iiglrpar.lib" |
| 197 |
else "iiparse.lib" |
| 198 |
} |
| 199 |
|
| 200 |
paths := [] |
| 201 |
put(paths, trim(\opttbl["p"], '/') || "/") |
| 202 |
put(paths, "") |
| 203 |
(\getenv)("LPATH") ? { |
| 204 |
while path := trim(tab(find(" ") | 0), '/') || "/" do { |
| 205 |
tab(many(' ')) |
| 206 |
if find("procs", path) then |
| 207 |
put(paths, ibreplace(path, "procs", "data")) |
| 208 |
put(paths, path) |
| 209 |
pos(0) & break |
| 210 |
} |
| 211 |
} |
| 212 |
iiparse_file := open(!paths || parser_name, "r") | iohno(2) |
| 213 |
|
| 214 |
# Write .lib file (contains the iiparse() parser routine), along |
| 215 |
# with the start symbol, action table, goto table, and a list of |
| 216 |
# productions. |
| 217 |
# |
| 218 |
# grammar contains start symbol, rules, and terminal token table |
| 219 |
# |
| 220 |
ibwriter(iiparse_file, outfile, grammar, atbl, gtbl, module) |
| 221 |
|
| 222 |
return exit(0) |
| 223 |
|
| 224 |
end |
| 225 |
|
| 226 |
|
| 227 |
# |
| 228 |
# write_defines |
| 229 |
# |
| 230 |
procedure write_defines(opttbl, outfile, module) |
| 231 |
|
| 232 |
# Output defines for YACC-like macros. Output iiisolate and |
| 233 |
# iiprune if -a option is specified. Sorry for the ugly code. |
| 234 |
# |
| 235 |
if \opttbl["a"] then { |
| 236 |
write(outfile, |
| 237 |
"$define iiisolate (iidirective", module, " ||:= \"isolate\")") |
| 238 |
write(outfile, |
| 239 |
"$define iiprune (iidirective", module, " ||:= \"prune\")") |
| 240 |
write(outfile, |
| 241 |
"$define iierrok (iidirective", module, " ||:= \"errok\")") |
| 242 |
} else { |
| 243 |
write(outfile, |
| 244 |
"$define iierrok (recover_shifts", module, " := &null &", |
| 245 |
" discards", module, " := 0)") |
| 246 |
} |
| 247 |
write(outfile, |
| 248 |
"$define iiclearin (iidirective", module, " ||:= \"clearin\")") |
| 249 |
write(outfile, |
| 250 |
"$define IIERROR (iidirective", module, " ||:= \"error\")") |
| 251 |
write(outfile, |
| 252 |
"$define IIACCEPT (iidirective", module, " ||:= \"accept\")") |
| 253 |
end |
| 254 |
|
| 255 |
|
| 256 |
# |
| 257 |
# bad_arg |
| 258 |
# |
| 259 |
# Simple routine called if command-line arguments are bad. |
| 260 |
# |
| 261 |
procedure bad_arg(s) |
| 262 |
|
| 263 |
write(&errout, "ibpag2: ",s) |
| 264 |
write(&errout, |
| 265 |
"usage: ibpag2 [-f inf] [-m str ] [-o outf] _ |
| 266 |
[-p dir] [-a] [-c] [-v] [-y]") |
| 267 |
write(&errout, " for help, type \"ibpag2 -h\"") |
| 268 |
stop() |
| 269 |
|
| 270 |
end |
| 271 |
|
| 272 |
|
| 273 |
# |
| 274 |
# ib_help_ |
| 275 |
# |
| 276 |
procedure ib_help_() |
| 277 |
|
| 278 |
write(&errout, "") |
| 279 |
write(&errout, |
| 280 |
"usage: ibpag2 [-f inf] [-m str] [-o outf] [-p dir] _ |
| 281 |
[-a] [-c] [-v] [-y]") |
| 282 |
write(&errout, "") |
| 283 |
write(&errout, " -f inf........where inf = Ibpag2's input file (default") |
| 284 |
write(&errout, " &input)") |
| 285 |
write(&errout, " -m str........where str = a string to be appended to") |
| 286 |
write(&errout, " global identifiers and procedures") |
| 287 |
write(&errout, " -o outf.......where outf = Ibpag2's output file (default") |
| 288 |
write(&errout, " &output)") |
| 289 |
write(&errout, " -p dir........where dir = directory in which the") |
| 290 |
write(&errout, " iiparse.lib file resides (mainly for") |
| 291 |
write(&errout, " systems lacking LPATH support)") |
| 292 |
write(&errout, " -a............permits ambiguous grammars and multiple") |
| 293 |
write(&errout, " parses (makes iiparse() a generator).") |
| 294 |
write(&errout, " -c............compresses action/goto tables (obstructs") |
| 295 |
write(&errout, " debugging somewhat).") |
| 296 |
write(&errout, " -v............sends debugging info to ibpag2.output") |
| 297 |
write(&errout, " -y............tells Ibpag2 to resolve reduce/reduce") |
| 298 |
write(&errout, " conflicts by order of occurrence in") |
| 299 |
write(&errout, " the grammar, and to resolve shift/") |
| 300 |
write(&errout, " reduce conflicts in favor of shift") |
| 301 |
stop("") |
| 302 |
|
| 303 |
end |