############################################################################ # # Name: ibpag2.icn # # Title: Icon-based parser generator (version 2) # # Author: Richard L. Goerwitz # # Version: 1.22 # ############################################################################ # # The Basics # # Ibpag2 is a simple tool for generating parsers from grammar # specifications. This may sound pretty arcane to those who have # never used a parser generator. In fact, though, this kind of tool # forms the basis of most programming language implementations. # Parser generators are also used in preprocessors, transducers, # compilers, interpreters, calculators and in fact for just about any # situation where some form of structured input needs to be read into # an internal data structure and/or converted into some form of # structured output. This might include something as mundane as # reading in recepts or mailing addresses from a file, or turning # dates of one type (e.g. "September 3, 1993") into another # ("9/3/93"). For more information on how to use it, see the README # file included with the Ibpag2 distribution. # ############################################################################ # # Running Ibpag2: # # Invoking Ibpag2 is very, very simple. There are quite a few # command-line switches, but all are optional: # # ibpag2 [-f infile] [-m module] [-o outfile] [-p iiparse.lib dir] # [-a] [-c] [-v] [-y] # # Where infile is the Ibpag2 source file (default &input), outfile is # the output file (default &output), module is an optional string # appended to all global variables and all procedure calls (to allow # multiple running parsers), and where -v instructs Ibpag2 to write a # summary of its operations to ibpag2.output. Normally all of these # arguments can be ignored. Ibpag2 can usually be run using simple # shell redirection symbols (if your OS supports them). See the next # paragraph for an explanation of the -p option. The -c option is # for compressed tables, and -a is for non-LR or ambiguous grammars. # See the advanced sections of README file. -y directs Ibpag2 to # resolve reduce/reduce conflicts by their order of occurrence in the # grammar, and to resolve shift/reduce conflicts in favor of shift - # just like YACC. Invoking Ibpag with -h causes it to abort with a # brief help message. # # Make sure that the iiparse.lib and iiglrpar.lib files are in # some path listed in your LPATH directory, or else in a data # directory adjacent to some IPL "procs" directory in your LPATH. # Basically, LPATH is just a space-separated list of places where # .icn library source files reside. If your system does not support # environment variables, then there are two ways to tell Ibpag2 where # the .lib files are without using LPATH. The first is to move into # the directory that contains these files. The second is to supply # the files' location using Ibpag's -p option (e.g. ibpag2 -p # /usr/local/lib/icon/data). # ############################################################################ # # More Technical Details # # Technically speaking, Ibpag2 is a preprocessor that accepts a # YACC-like source file containing grammar productions and actions, # then 1) converts these into parse tables and associated code, 2) # adds to them an LR parser, and a few debugging tools, and 3) writes # the combination to the standard output, along with the necessary # action and goto table construction code. The user must $include, # or hard-code into the Ibpag2 source file, a lexical analyzer that # returns integers via symbolic $defines generated by %token, %right, # etc. declarations in the Ibpag2 source file. # # Cycles and epsilon moves are handled correctly (to my # knowledge). Shift-reduce conflicts are handled in the normal way # (i.e. pick the rule with the highest priority, and, in cases where # the priority is the same, check the associativities) I decided to # flag reduce/reduce conflicts as errors by default, since these # often conceal deeper precedence problems. They are easily enough # handled, if need be, via dummy precedences. The -y command-line # switch turns off this behavior, causing Ibpag2 to resolve # reduce/reduce conflicts in a YACCish manner (i.e. favoring the rule # that occurs first in the grammar). Ibpag2 normally aborts on # shift/reduce conflicts. The -y switch makes Ibpag resolve these in # favor of shift, and to keep on processing - again, just like YACC. # # For more information, see the README file. # ############################################################################ # # Links: ibreader, ibwriter, slrtbls, ibutil, version, options # ############################################################################ # link ibreader, ibwriter, slrtbls, ibutil, version, options link options global DEBUG procedure main(a) local infile, outfile, verbosefile, atbl, gtbl, grammar, opttbl, module, abort_on_conflict, paths, path, parser_name, iiparse_file # Get command-line options. opttbl := options(a, "f:o:vdm:p:hcay", bad_arg) # Abort with help message if -h is supplied. if \opttbl["h"] then { write(&errout, ib_version()) return ib_help_() } # If an input file was specified, open it. Otherwise use stdin. # if \opttbl["f"] then infile := open(opttbl["f"], "r") | bad_arg("can't open " || opttbl["f"]) else infile := &input # If an output file was specified, use it. Otherwise use stdout. # if \opttbl["o"] then outfile := open(opttbl["o"], "w") | bad_arg("can't open " || opttbl["o"]) else outfile := &output # If a module name was specified (-m), then use it. # module := opttbl["m"] | "" # If the debug option was specified, set all verbose output to go # to errout. # if \opttbl["d"] then { verbosefile := &errout DEBUG := 1 } # If the verbose option was specified, send all verbose output to # "ibpag2.output" (a bit like YACC's yacc.output file). # else if \opttbl["v"] then verbosefile := open("ibpag2.output", "w") | bad_arg("can't open " || opttbl["v"]) # Output defines for YACC-like macros. Output iiisolate and # iiprune if -a option is specified. Sorry for the ugly code. # write_defines(opttbl, outfile, module) # Whew! Now fetch the grammar from the input file. # # Emit line directives keyed to actual line numbers in the # original file. Pass its name as arg4. If obttbl["f"] is # null (and the input file is &input), ibreader will default # to something else. # grammar := ibreader(infile, outfile, module, opttbl["f"]) if \verbosefile then # grammar contains start symbol, rules, and terminal token table print_grammar(grammar, verbosefile) # Fill in parse tables, atbl and gtbl. Abort if there is a # conflict caused by an ambiguity in the grammar or by some # precedence/associativity problem, unless the -a option is # supplied (telling Ibpag2 that ambiguous tables are okay). # if /opttbl["a"] then abort_on_conflict := "yes" atbl := table(); gtbl := table() make_slr_tables(grammar, atbl, gtbl, abort_on_conflict, opttbl["y"]) if \verbosefile then # grammar.tbl maps integer terminal symbols to human-readable strings print_action_goto_tables(atbl, gtbl, grammar.tbl, verbosefile) # If -c was specified on the command line, compress the action and # goto tables. # if \opttbl["c"] then { write(outfile, "\n$define COMPRESSED_TABLES\n") if \verbosefile then write(verbosefile, "\nNote: parse tables are compressed") shrink_tables(grammar, atbl, gtbl) } # Try to find the .lib file using LPATH. # parser_name := { if \opttbl["a"] then "iiglrpar.lib" else "iiparse.lib" } paths := [] put(paths, trim(\opttbl["p"], '/') || "/") put(paths, "") (\getenv)("LPATH") ? { while path := trim(tab(find(" ") | 0), '/') || "/" do { tab(many(' ')) if find("procs", path) then put(paths, ibreplace(path, "procs", "data")) put(paths, path) pos(0) & break } } iiparse_file := open(!paths || parser_name, "r") | iohno(2) # Write .lib file (contains the iiparse() parser routine), along # with the start symbol, action table, goto table, and a list of # productions. # # grammar contains start symbol, rules, and terminal token table # ibwriter(iiparse_file, outfile, grammar, atbl, gtbl, module) return exit(0) end # # write_defines # procedure write_defines(opttbl, outfile, module) # Output defines for YACC-like macros. Output iiisolate and # iiprune if -a option is specified. Sorry for the ugly code. # if \opttbl["a"] then { write(outfile, "$define iiisolate (iidirective", module, " ||:= \"isolate\")") write(outfile, "$define iiprune (iidirective", module, " ||:= \"prune\")") write(outfile, "$define iierrok (iidirective", module, " ||:= \"errok\")") } else { write(outfile, "$define iierrok (recover_shifts", module, " := &null &", " discards", module, " := 0)") } write(outfile, "$define iiclearin (iidirective", module, " ||:= \"clearin\")") write(outfile, "$define IIERROR (iidirective", module, " ||:= \"error\")") write(outfile, "$define IIACCEPT (iidirective", module, " ||:= \"accept\")") end # # bad_arg # # Simple routine called if command-line arguments are bad. # procedure bad_arg(s) write(&errout, "ibpag2: ",s) write(&errout, "usage: ibpag2 [-f inf] [-m str ] [-o outf] _ [-p dir] [-a] [-c] [-v] [-y]") write(&errout, " for help, type \"ibpag2 -h\"") stop() end # # ib_help_ # procedure ib_help_() write(&errout, "") write(&errout, "usage: ibpag2 [-f inf] [-m str] [-o outf] [-p dir] _ [-a] [-c] [-v] [-y]") write(&errout, "") write(&errout, " -f inf........where inf = Ibpag2's input file (default") write(&errout, " &input)") write(&errout, " -m str........where str = a string to be appended to") write(&errout, " global identifiers and procedures") write(&errout, " -o outf.......where outf = Ibpag2's output file (default") write(&errout, " &output)") write(&errout, " -p dir........where dir = directory in which the") write(&errout, " iiparse.lib file resides (mainly for") write(&errout, " systems lacking LPATH support)") write(&errout, " -a............permits ambiguous grammars and multiple") write(&errout, " parses (makes iiparse() a generator).") write(&errout, " -c............compresses action/goto tables (obstructs") write(&errout, " debugging somewhat).") write(&errout, " -v............sends debugging info to ibpag2.output") write(&errout, " -y............tells Ibpag2 to resolve reduce/reduce") write(&errout, " conflicts by order of occurrence in") write(&errout, " the grammar, and to resolve shift/") write(&errout, " reduce conflicts in favor of shift") stop("") end