home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / historic / v941.tgz / icon.v941src.tar / icon.v941src / ipl / packs / ibpag2 / ibreader.icn < prev    next >
Text File  |  2000-07-29  |  17KB  |  516 lines
  1. ############################################################################
  2. #
  3. #    Name:     ibreader.icn
  4. #
  5. #    Title:     reader for Ibpag2 source files
  6. #
  7. #    Author:     Richard L. Goerwitz
  8. #
  9. #    Version: 1.29
  10. #
  11. ############################################################################
  12. #
  13. #  This file contains a collection of procedures that 1) read in an
  14. #  Ibpag2 source file, 2) output token defines, 3) emit action code,
  15. #  and finally 4) pass a start symbol, list of productions, and token
  16. #  table back to the calling procedure.  Described formally:
  17. #
  18. #      ibreader:  file x file x string  -> ib_grammar record
  19. #                 (in,   out,   module) -> grammar
  20. #
  21. #  In is the input stream; out is the output stream; module is an
  22. #  optional string that distinguishes this grammar from others that
  23. #  might also be running simultaneously.  Grammar is an ib_grammar
  24. #  record containing the start symbol in its first field and the
  25. #  production list in its second.  Its third field contains a table
  26. #  used to map integers to actual token names or character literals,
  27. #  i.e. its keys are things like -1, 0, etc. and its values are things
  28. #  like "error," "EOF," etc.
  29. #
  30. #  Note that if a module argument is supplied to ibreader(), one must
  31. #  also be supplied to ibwriter().  See ibwriter.icn.
  32. #
  33. #  The format of the input file is highly reminiscent of YACC.  It
  34. #  consists of three basic sections, the first two of which are
  35. #  followed by %%.  See the main documentation to Ibpag2 for
  36. #  specifics.  Major differences between Ibpag2 and YACC input format
  37. #  include:
  38. #
  39. #      1) "$$ = x" constructs are replaced by "return x" (e.g. "$$ =
  40. #         $1 + $3" -> "return $1 + $3")
  41. #
  42. #      2) all variables within a given action are, by default, local
  43. #         to that action; i.e. they cannot be accessed by other
  44. #         actions unless you declare them global elsewhere (e.g. in
  45. #         the pass-through part of the declarations section %{ ... %})
  46. #
  47. #      3) the %union declaration is not needed by Ibpag
  48. #
  49. #      4) tokens and symbols are separated from each other by a comma
  50. #         (e.g. %token '+', '-' and S : NP, VP)
  51. #
  52. #      5) epsilon is indicated by the keyword "epsilon" (e.g. REL :
  53. #         epsilon)
  54. #
  55. #      6) both epsilon and error *may* be declared as %tokens for
  56. #         reasons of precedence, although they retain hard-coded
  57. #         internal values (-2 and -1, respectively)
  58. #
  59. #      7) all actions must follow the last RHS symbol of the rule they
  60. #         apply to (preceded by an optional %prec directive); to
  61. #         achieve S : NP { action1 }, VP { action2 }, insert a dummy
  62. #         rule: S : NP, dummy, VP { action2 }; dummy : epsilon {
  63. #         action1 } ;
  64. #
  65. #      8) YYERROR, YYACCEPT, yyclearin, and yyerrok are the same,
  66. #         except they are written IIERROR, IIACCEPT, iiclearin, and
  67. #         iierrok (i.e. "ii" replaces "yy")
  68. #
  69. #      9) Ibpag2's input files are tokenized like modified Icon files,
  70. #         and, as a consequence, Icon's reserved words must not be
  71. #         used as symbols (e.g. "if : if, then" is no go)
  72. #
  73. ############################################################################
  74. #
  75. #  Links: itokens, escape
  76. #
  77. #  See also: ibwriter
  78. #
  79. ############################################################################
  80.  
  81. #link itokens, escape
  82. link escape
  83.  
  84. record ib_grammar(start, rules, tbl)
  85. record tokstats(str, no, prec, assoc)
  86.  
  87. # Declared in itokens.icn:
  88. # global line_number
  89.  
  90. #
  91. # ibreader:  file x file x string x string        -> ib_grammar record
  92. #            (in,   out,   module,  source_fname) -> grammar
  93. #
  94. #     Where in is an input stream, out is an output stream, module is
  95. #     some string uniquely identifying this module (optional), and
  96. #     where grammar is an ib_grammar record containing the start
  97. #     symbol in its first field and a list of production records in
  98. #     its second.  Source_fname is the string name of Ibpag2's input
  99. #     grammar file.  Defaults to "source file."
  100. #
  101. procedure ibreader(in, out, module, source_fname)
  102.  
  103.     local tmp, grammar, toktbl, next_token, next_token_no_nl,
  104.     token, LHS, t
  105.  
  106.     /source_fname    := "source file"
  107.     grammar          := ib_grammar(&null, list(), table())
  108.     toktbl           := table()
  109.     next_token       := create itokens(in, 1)
  110.     next_token_no_nl := create 1(tmp := |@next_token, \tmp.sym)
  111.     token            := @next_token_no_nl | iohno(4)
  112.  
  113.     # Do the %{ $} and %token stuff, i.e. everything up to %%
  114.     # (NEWSECT).
  115.     #
  116.     until token.sym == "NEWSECT" do {
  117.     case token.sym of {
  118.         default     : {
  119.         iohno(48, "token "||image(token.str) ||"; line "|| line_number)
  120.         }
  121.         "SEMICOL"   :  {
  122.         # Skip semicolon.  Get another token while we're at it.
  123.         token := @next_token_no_nl | iohno(47, "line "||line_number)
  124.         }
  125.         "BEGGLOB" : {
  126.         write(out, "\n$line ", line_number, " ", image(source_fname))
  127.         # Copy token values to out until we reach "%}" (ENDGLOB).
  128.         (token := copy_icon_stuff(next_token, out)).sym == "ENDGLOB"
  129.         token := @next_token_no_nl
  130.         }
  131.         "MOD"     : {
  132.         (token := @next_token_no_nl).sym == "IDENT" |
  133.             iohno(30, "line " || line_number)
  134.         #
  135.         # Read in token declarations, set associativity and
  136.         # precedences, and enter the tokens into toktbl.
  137.         #
  138.         token := {
  139.             case token.str of {
  140.              default  : iohno(30, "line " || line_number)
  141.             "token"   : read_decl(next_token_no_nl, toktbl, &null)
  142.             "right"   : read_decl(next_token_no_nl, toktbl, "r")
  143.             "left"    : read_decl(next_token_no_nl, toktbl, "l")
  144.             "nonassoc": read_decl(next_token_no_nl, toktbl, "n")
  145.             "union"   : iohno(45, "line "|| line_number)
  146.             "start"   : {
  147.                 (token := @next_token_no_nl).sym == "IDENT" |
  148.                 iohno(31, "line " || line_number)
  149.                 /grammar.start := token.str |
  150.                 iohno(32, "line " || line_number)
  151.                 @next_token_no_nl | iohno(4)
  152.             }
  153.             }
  154.         }
  155.         }
  156.     }
  157.     }
  158.     # Skip past %% (NEWSECT) and semicolon (if present).
  159.     token := @next_token_no_nl | iohno(47, "line "|| line_number)
  160.     (token := token | @next_token_no_nl | iohno(4)).sym ~== "SEMICOL"
  161.     token.sym == "NEWSECT" & iohno(47, "line "|| line_number)
  162.  
  163.     #
  164.     # Fetch start symbol if it wasn't defined above via %start; by
  165.     # default the start symbol is the LHS of rule 1.
  166.     #
  167.     /grammar.start := token.str
  168.  
  169.     # Having reached the end of the declarations section, we can now
  170.     # copy out a define for each token number, not counting character
  171.     # literals (which are stored as integers).  While we're at it,
  172.     # create a table that maps token numbers back to character
  173.     # literals and strings (for use in later verbose and debugging
  174.     # displays).
  175.     #
  176.     write(out, "\n")
  177.     every t := !toktbl do {
  178.     if type(t.str) == "integer" then
  179.         insert(grammar.tbl, t.no, image(char(t.str)))
  180.     else {
  181.         insert(grammar.tbl, t.no, t.str)
  182.         write(out, "$define ", t.str, "\t", t.no)
  183.     }
  184.     }
  185.  
  186.     # Now, finally, read in rules up until we reach EOF or %% (i.e.
  187.     # NEWSECT).  EOF is signaled below by failure of read_RHS().
  188.     #
  189.     until token.sym == "NEWSECT" do {
  190.     token.sym == "IDENT" | iohno(33, token.str ||" line "|| line_number)
  191.     LHS := token.str
  192.     token := @next_token_no_nl | iohno(4)
  193.     token.sym == "COLON" | iohno(34, token.str ||" line "|| line_number)
  194.     #
  195.     # Read in RHS, then the action (if any) then the prec (if
  196.     # any).  If we see a BAR, then repeat, re-using the same
  197.     # left-hand side symbol.
  198.     #
  199.     while token := 
  200.         read_RHS(next_token, next_token_no_nl, out, toktbl, LHS,
  201.              grammar, module, source_fname) |
  202.         # if read_RHS fails, we're at EOF
  203.         break break
  204.     do token.sym == "BAR" | break
  205.     }
  206.  
  207.     # Copy the remainder of the file to out as Icon code.
  208.     write(out, "\n$line ", line_number, " ", image(source_fname))
  209.     every copy_icon_stuff(next_token, out, "EOFX")
  210.  
  211.     # Do final setup on the reverse token table.  This table will be
  212.     # used later to map integers to their original names in verbose or
  213.     # debugging displays.
  214.     #
  215.     insert(grammar.tbl,  0, "$")
  216.  
  217.     return grammar
  218.  
  219. end
  220.  
  221.  
  222. #
  223. # copy_icon_stuff:  coexpression x file x string  -> ib_TOK records
  224. #                   (next_token,   out,   except) -> token records
  225. #
  226. #     Copy Icon code to output stream, also suspending as we go.
  227. #     Insert separators between tokens where needed.  Do not output
  228. #     any token whose sym field matches except.  The point in
  229. #     suspending tokens as we go is to enable the calling procedure to
  230. #     look for signal tokens that indicate insertion or termination
  231. #     points.
  232. #
  233. procedure copy_icon_stuff(next_token, out, except)
  234.  
  235.     local separator, T
  236.  
  237.     separator := ""
  238.     while T := @next_token do {
  239.     if \T.sym then suspend T
  240.     if \T.sym == \except then next
  241.     if any(&digits ++ &letters ++ '_.', \T.str, 1, 2) & \T.sym ~== "DOT"
  242.     then writes(out, separator)
  243.     writes(out, T.str)
  244.     if any(&digits ++ &letters ++ '_.', \T.str, -1, 0) & \T.sym ~== "DOT"
  245.     then separator := " " else separator := ""
  246.     }
  247.  
  248.     # unexpected EOF error
  249.     (except === "EOFX") | iohno(4)
  250.  
  251. end
  252.  
  253.  
  254. #
  255. # read_decl:  coexpression     x table x string -> ib_TOK
  256. #             (next_token_no_nl, toktbl, assoc) -> token
  257. #
  258. #     Read in token declarations, assigning them the correct
  259. #     precedence and associativity.  Number the tokens for later
  260. #     $define preprocessor directives.  When done, return the last
  261. #     token processed.  Toktbl is the table that holds the stats for
  262. #     each declared token.
  263. #
  264. procedure read_decl(next_token_no_nl, toktbl, assoc)
  265.  
  266.     local   token, c
  267.     static  token_no, prec
  268.     initial {
  269.     token_no := 256
  270.     prec := 0
  271.     }
  272.  
  273.     # All tokens in this list have the same prec and assoc.
  274.     # Precedence is determined by order.  Associativity is determined
  275.     # by keyword in the calling procedure, and is passed as arg 3.
  276.     #
  277.     prec +:= 1
  278.     assoc === ("n"|"r"|"l"|&null) | iohno(5, image(assoc))
  279.  
  280.     # As long as we find commas and token names, keep on adding tokens
  281.     # to the token table.  Return the unused token when done.  If we
  282.     # reach EOF, there's been an error.
  283.     #
  284.     repeat {
  285.     token := @next_token_no_nl | iohno(4)
  286.     case token.sym of {
  287.         default  : iohno(31, token.str ||" line "|| line_number)
  288.         "CSETLIT" | "STRING": {
  289.         # Enter character literals as integers.
  290.         *escape(token.str[2:-1]) = 1 | iohno(49, token.str)
  291.         c := ord(escape(token.str[2:-1]))
  292.         toktbl[c] := tokstats(c, c, prec, assoc)
  293.         }
  294.         "IDENT"  : {
  295.         case token.str of {
  296.             "error"  :
  297.             toktbl[token.str] := tokstats("error", -1, prec, assoc)
  298.             "epsilon":
  299.             toktbl[token.str] := tokstats("epsilon",-2,prec, assoc)
  300.             default  : {
  301.             # Enter TOKENs as string-keyed records in toktbl.
  302.             token_no +:= 1
  303.             toktbl[token.str] :=
  304.                 tokstats(token.str, token_no, prec, assoc)
  305.             }
  306.         }
  307.         }
  308.     }
  309.     # As long as we're seeing commas, go back for more tokens.
  310.     token := @next_token_no_nl | iohno(4)
  311.     token.sym == "COMMA" | break
  312.     }
  313.  
  314.     # Skip past semicolon, if present (as set up now, it shouldn't be).
  315.     (token := token | @next_token_no_nl | iohno(4)).sym ~== "SEMICOL"
  316.     return token
  317.  
  318. end
  319.  
  320.  
  321. #
  322. # read_RHS:  coexpression x coexpression x file x table x
  323. #            string x ib_grammar record x string x string -> token
  324. #
  325. #     Read_RHS goes through the RHS of rule definitions, inserting the
  326. #     resulting productions into a master rule list.  At the same
  327. #     time, it outputs the actions corresponding to those productions
  328. #     as procedures that are given names corresponding to the numbers
  329. #     of the productions.  I.e. production 1, if endowed with an {
  330. #     action }, will correspond to procedure _1_.  Prec and assoc are
  331. #     automatically set to that of the last RHS nonterminal, but this
  332. #     may be changed explicitly by the %prec keyword, as in YACC.
  333. #     Source_fname is the name of the source grammar file we're pro-
  334. #     cessing (caller will give us some reasonable default if we're
  335. #     reading &input).
  336. #
  337. #     Fails on EOF.
  338. #
  339. procedure read_RHS(next_token, next_token_no_nl, out, toktbl, LHS,
  340.            grammar, module, source_fname)
  341.  
  342.     local   token, rule, c
  343.     static  rule_no
  344.     initial rule_no := 0
  345.  
  346.     rule_no +:= 1
  347.     #                  LHS  RHS     POS    LOOK   no       prec   assoc
  348.     rule := production(LHS, list(), &null, &null, rule_no, &null, &null)
  349.     put(grammar.rules, rule)
  350.  
  351.     # Read in RHS symbols.
  352.     #
  353.     repeat {
  354.     token := @next_token_no_nl | iohno(4)
  355.     case token.sym of {
  356.         default  :
  357.         iohno(35, "token "|| image(token.str)||"; line "|| line_number)
  358.         "CSETLIT" | "STRING": {
  359.         *escape(token.str[2:-1]) = 1 | iohno(49, token.str)
  360.         c := ord(escape(token.str[2:-1]))
  361.         if \toktbl[c] then {
  362.             rule.prec  := toktbl[c].prec
  363.             rule.assoc := toktbl[c].assoc
  364.         }
  365.         # literals not declared earlier will get caught here
  366.         else insert(grammar.tbl, c, image(char(c)))
  367.         put(rule.RHS, c)
  368.         }
  369.         "IDENT"  : {
  370.         # If it's a terminal (i.e. a declared token), assign
  371.         # this rule its precedence and associativity.  If it's
  372.         # not in toktbl, then it's not a declared token....
  373.         if \toktbl[token.str] then {
  374.             rule.prec  := toktbl[token.str].prec
  375.             rule.assoc := toktbl[token.str].assoc
  376.             put(rule.RHS, toktbl[token.str].no)
  377.             if toktbl[token.str].no = -2 then {
  378.             *rule.RHS > 1 & iohno(44, "line ", line_number)
  379.                 rule.POS := 2
  380.             }
  381.         }
  382.         # ...undeclared stuff.  Could be a nonterminal.  If
  383.         # error and/or epsilon weren't declared as tokens,
  384.         # they will get caught here, too.
  385.         else {
  386.             case token.str of {
  387.             &null     : stop("What is going on here?")
  388.             default   : put(rule.RHS, token.str)
  389.             "error"   : {
  390.                 put(rule.RHS, -1)
  391.                 insert(grammar.tbl, -1, "error")
  392.             }
  393.             "epsilon" : {
  394.                 if *put(rule.RHS, -2) > 1
  395.                 then iohno(44, "line ", line_number)
  396.                 else rule.POS := 2
  397.                 insert(grammar.tbl, -2, "epsilon")
  398.             }
  399.             }
  400.         }
  401.         }
  402.     }
  403.     # Comma means:  Go back for another RHS symbol.
  404.     token := @next_token_no_nl | fail
  405.     token.sym == "COMMA" | break
  406.     }
  407.  
  408.     # Skip semicolon token, if present.
  409.     (token := token | @next_token_no_nl | fail).sym ~== "SEMICOL"
  410.  
  411.     # Read and set (optional) precedence.
  412.     #
  413.     if token.sym == "MOD" then {
  414.     token := @next_token_no_nl | iohno(4)
  415.     (token.sym == "IDENT" & token.str == "prec") |
  416.         iohno(43, token.str || " line " || line_number)
  417.     token := @next_token_no_nl | iohno(4)
  418.     case token.sym of {
  419.         "CSETLIT" | "STRING" : {
  420.         *escape(token.str[2:-1]) = 1 | iohno(49, token.str)
  421.         c := ord(escape(token.str[2:-1])) &
  422.         rule.prec  := toktbl[c].prec &
  423.         rule.assoc := toktbl[c].assoc
  424.         }
  425.         "IDENT"    : {
  426.         \toktbl[token.str] |
  427.             iohno(43, token.str || " line " || line_number)
  428.         rule.prec  := toktbl[token.str].prec &
  429.         rule.assoc := toktbl[token.str].assoc
  430.         }
  431.         default    : 1 = 4    # deliberate failure
  432.     } | iohno(43, "line ", line_number)
  433.     token := @next_token_no_nl | fail
  434.     }
  435.  
  436.     # Skip semicolon token, if present.
  437.     (token := token | @next_token_no_nl | fail).sym ~== "SEMICOL"
  438.  
  439.     # Read in (optional) action.
  440.     #
  441.     if token.sym == "LBRACE" then {
  442.     write_action_as_procedure(next_token, out, rule,
  443.                   module, source_fname)
  444.     token := @next_token_no_nl | fail
  445.     }
  446.  
  447.     # Skip semicolon token, if present.
  448.     (token := token | @next_token_no_nl | fail).sym ~== "SEMICOL"
  449.     return token
  450.  
  451. end
  452.  
  453.  
  454. #
  455. # write_action_as_procedure
  456. #
  457. procedure write_action_as_procedure(next_token, out, rule,
  458.                     module, source_fname)
  459.  
  460.     local argstr, bracelevel, token, i, neg
  461.  
  462.     /module := ""
  463.      argstr := ""
  464.     #
  465.     # Decide the number of arguments based on the length of the RHS of
  466.     # rule.  Exception: Epsilon productions are empty, and pop nothing
  467.     # off the stack, so take zero args.
  468.     #
  469.     if rule.RHS[1] ~=== -2 then {
  470.     every argstr ||:= "arg" || (1 to *rule.RHS) || ","
  471.     argstr := trim(argstr, ',')
  472.     }
  473.     write(out, "procedure _", rule.no, "_", module, "(", argstr, ")")
  474.     write(out, "\n$line ", line_number, " ", image(source_fname))
  475.  
  476.     bracelevel := 1
  477.     until bracelevel = 0 do {
  478.     every token := copy_icon_stuff(next_token, out, "RHSARG") do {
  479.         case token.sym of {
  480.         default   : next
  481.         "LBRACE"  : bracelevel +:= 1
  482.         "RBRACE"  : bracelevel -:= 1
  483.         "RHSARG"  : {
  484.             until \ (token := @next_token).sym do
  485.             writes(out, token.str)
  486.             if neg := (token.sym == "MINUS") then
  487.             until \ (token := @next_token).sym do 
  488.                 writes(out, token.str)
  489.             else neg := &null
  490.             token.sym == "INTLIT"  | iohno(37, "$"||token.str)
  491.             if /neg & token.str ~== "0" then {
  492.             token.str <= *rule.RHS | iohno(38, "$"||token.str)
  493.             writes(out, " arg", token.str, " ")
  494.             } else {
  495.             # Code for $0, $-1, etc.
  496.             #
  497.             # Warning!  If the name of the stack is changed
  498.             # in iiparse.lib, it has to be changed here, too.
  499.             #
  500.             i := abs(token.str)+1
  501.             writes(out, " value_stack", module, "[", i, "] ")
  502.             }
  503.             }
  504.         }
  505.         if bracelevel = 0 then {
  506.         write(out, "\nend\n")
  507.         return token
  508.         }
  509.         }
  510.     }
  511.         
  512.     iohno(39, "line "|| line_number)
  513.  
  514. end
  515.  
  516.