home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / pccts.zip / pccts / NOTES.newbie < prev    next >
Text File  |  1994-03-31  |  65KB  |  1,695 lines

  1. 31 March 94
  2. Version 1.10 of pccts
  3.  
  4. At the moment this help file is available via anonymous FTP at
  5.  
  6.         Node: marvin.ecn.purdue.edu
  7.         File: (sometimes)/pub/pccts/1.10/newbie.info
  8.         File: (now)      /pub/pccts/1.10/NOTES.newbie
  9.  
  10. Mail corrections or additions to moog@polhode.com
  11. ===============================================================================
  12. General
  13. -------------------------------------------------------------------------------
  14. 1.  Tokens begin with uppercase characters. Rules begin with lowercase
  15. characters.
  16.  
  17. 2.  Multiple parsers can coexist in the same application through use
  18. of the #parser directive.
  19.  
  20. 3.  When you see a syntax error message that has quotation marks on
  21. separate lines:
  22.  
  23.         line 1: syntax error at "
  24.         " missing ID
  25.  
  26. that probably means that the offending element contains a newline.
  27.  
  28. 4.  Even if your C compiler does not support C++ style comments,
  29. you can use them in the *non-action* portion of the ANTLR source code.
  30. Inside an action (i.e.  <<...>> ) you have to obey the comment
  31. conventions of your compiler.
  32.  
  33. 5.  ANTLR counts a line which is continued across a newline using
  34. the backslash convention as a single line.  For example:
  35.  
  36.         #header <<
  37.         #define abcd alpha\
  38.                 beta\
  39.                 gamma\
  40.                 delta
  41.         >>
  42.  
  43. Will cause line numbers in ANTLR error messages to be off by 3.
  44.  
  45. 6.  Don't confuse #[...] with #(...).
  46.  
  47. The first creates a single AST node (usually from a token identifier and
  48. an attribute) using the routine zzmk_ast().  The zzmk_ast routine must be
  49. supplied by the user (or selected from one of the pccts supplied ones such
  50. as charbuf or charptr).
  51.  
  52. The second creates an AST list (usually more than a single node) from other
  53. ASTs by filling in the "down" field of the first node in the list to create
  54. a root node, and the "sibling" fields of each of remaining ASTs in the
  55. list.  A null pointer is put in the sibling field of the last AST in the
  56. list.  This is performed by the pccts supplied routine zztmake().
  57.  
  58.      #token ID                  "[a-z]*"
  59.      #token COLON               ":"
  60.      #token STMT_WITH_LABEL
  61.  
  62.      id!   : ID <<#0=#[STMT_WITH_LABEL,$1];>>
  63.  
  64.                 Creates an AST.  The AST (a single node)
  65.                 contains STMT_WITH_LABEL in the token
  66.                 field - given a traditional version of
  67.                 zzmk_ast().
  68.  
  69.      rule! : id COLON expr
  70.                 <<#0=#(#1,#3);>>
  71.  
  72.                 Creates an AST list with the ID at its
  73.                 root and "expr" as its first (and only) child.
  74.  
  75. The following example is equivalent, but more confusing
  76. because the two steps above have been combined into a single
  77. action statement:
  78.  
  79.      rule! : ID COLON expr
  80.                 <<#0=#(#[STMT_WITH_LABEL,$1],#3);>>
  81.  
  82. ===============================================================================
  83. Section on switches and options
  84. -------------------------------------------------------------------------------
  85. 7.  Don't forget about the ANTLR -gd option which provides a trace of
  86. rules which are triggered and exited.
  87.  
  88. 8.  When you want to inspect the code generated by ANTLR you may want to
  89. use the ANTLR -gs switch.  This causes ANTLR to test for a token being
  90. an element of  a lookahead set by using explicit tests rather by using
  91. the faster bit oriented operations which are difficult to read.
  92.  
  93. 9.  When using the ANTLR -gk option you probably want to use the DLG -i
  94. option.  As far as I can tell neither option works by itself.
  95. Unfortunately they have different abbreviations so that one can't
  96. use the same symbol for both in a makefile.
  97.  
  98. 10.  When you are debugging code in the rule section and there is no
  99. change to the lexical scanner, you can avoid regeneration of scanner.c
  100. by using the ANTLR -gx option.  However some items from stdpccts.h
  101. can affect the scanner, such as -k -ck and the addition of semantic
  102. predicates - so this optimization should be used with a little care.
  103.  
  104. 11.  One cannot use an interactive scanner (ANTLR -gk option) with the
  105. ANTLR infinite lookahead and backtracking options (syntactic predicates).
  106.  
  107. 12.  If you want backtracking, but not the prefetching of characters and
  108. tokens that one gets with lookahead, then you might want to try using
  109. your own input routine and then using ANTLRs (input supplied by string)
  110. or ANTLRf (input supplied by function) rather than plain ANTLR which
  111. is used in most of the examples.
  112.  
  113. See Example 4 below for an example of an ANTLRf input function.
  114.  
  115. 13.  The format used in #line directive is controlled by the macro
  116.  
  117.                 #define LineInfoFormatStr "# %d \"%s\"\n"
  118.  
  119. which is defined in generic.h.  A change requires recompilation of ANTLR.
  120.  
  121. 14.  To make the lexical scanner case insensitive use the DLG -ci
  122. switch.  The analyzer does not change the text, it just ignores case
  123. when matching it against the regular expressions.
  124.  
  125. As of 24-Feb-94 there was an off-by-one problem in the testing for
  126. lowercase in range expressions. The problem appears if the last character
  127. in the range is "z" or "Z" (e.g. [a-z]).  The temporary workaround is to
  128. use a range of the form "[a-yz]".
  129.  
  130. 15.  The lexical routines zzmode(), zzskip(), and zzmore() do NOT work like
  131. coroutines.  Basically, all they do is set status bits or fields in a
  132. structure owned by the lexical analyzer and then return immediately.  Thus it
  133. is OK to call these routines anywhere from within a lexical action.  You
  134. can even call them from within a subroutine called from a lexical action
  135. routine.
  136.  
  137. See Example 5 below for routines which maintain a stack of modes.
  138. ===============================================================================
  139. Section on #token and lexical issues
  140. -------------------------------------------------------------------------------
  141. 16.  To gobble up everything to a newline use: "~[\n]*".
  142.  
  143. 17.  To match any single character use: "~[]".
  144.  
  145. 18.  If a #token symbol is spelled incorrectly in a rule it will not be
  146. reported by ANTLR.  ANTLR will assign it a new  #token number which,
  147. of course, will never be matched.  Look at token.h for misspelled
  148. terminals or inspect "zztokens[]" in err.c.
  149.  
  150. 19.  If you happen to define the same #token name twice (for instance
  151. because of inadvertent duplication of a line) you will receive no
  152. error message from ANTLR or DLG.  ANTLR will simply leave a hole in
  153. the assignment of token numbers, and you will find strange numbers in
  154. the test of LA(1) and LA(2) rather than the expected token names.
  155. Look at token.h or inspect "zztokens[]" in err.c.
  156.  
  157. 20.  One cannot continue a regular expression in a #token statement across
  158. lines.  If one tries to use "\" to continue the line the lexical analyzer
  159. will think you are trying to match a newline character.
  160.  
  161. 21.  The escaped literals in #token regular expressions are not identical
  162. to the ANSI escape sequences.  For instance "\v" will yield a match
  163. for "v", not a vertical tab.
  164.  
  165.         \t      \n      \r      \b      - the only escaped letters
  166.  
  167. 22.  In #token regular expressions spaces and tabs which are
  168. not escaped are ignored - thus making it easy to add white space to
  169. a regular expression.
  170.  
  171.         #token  symbol  "[a-z A-Z] [a-z A-Z 0-9]*"
  172.  
  173. 23.  You cannot supply an action (even a null action) for a #token
  174. statement without a regular expression. You'll receive the message:
  175.  
  176.         warning: action cannot be attached to a token name
  177.                 (...token name...); ignored
  178.  
  179. This is a minor problem when the #token is created for use with
  180. attributes or ASTs nodes and has not regular expression:
  181.  
  182.         #token  CAST_EXPR
  183.         #token  SUBSCRIPT_EXPR
  184.         #token  ARGUMENT_LIST
  185.  
  186.         <<
  187.         ... Code related to parsing
  188.         >>
  189.  
  190. ANTLR assumes the code block is the action associated with the #token
  191. immediately preceding it.  It is not obvious what the problem is because
  192. the line number referenced is the end of the code block (">>") rather
  193. than the beginning.  My solution is to follow such #token statements
  194. with a #token which does have a regular expression or a rule.
  195.  
  196. 24.  The #token statement allows the action to appear on a second line.
  197. This sometimes leads to the misinterpretation of a code block which
  198. follows:
  199.  
  200.         #token  RETURN  "return"
  201.  
  202.         <<
  203.         ... some code related to parsing ...
  204.         >>
  205.  
  206. ANTLR will interpret the code block as being the action of the
  207. #token.  The workaround is to put in an intervening #token statement
  208. or a null action:
  209.  
  210.         #token  RETURN  "return"  <<;>>
  211.  
  212. 25.  Since the lexical analyzer wants to find the longest possible string
  213. that matches a regular expression, it is probably best not to use expressions
  214. like "~[]*" which will gobble up everything to the end-of-file.
  215.  
  216. 26.  When a string is matched by two #token regular expressions, the lexical
  217. analyzer will choose the one which appears first in the source code.  Thus
  218. more specific regular expressions should appear before more general ones:
  219.  
  220.         #token  HELP    "help"         /*  should appear before "symbol" */
  221.         #token  symbol  "[a-zA-Z]*"    /*  should appear after keywords  */
  222.  
  223. Another example of this is defining hexadecimal characters before decimal
  224. characters.
  225.  
  226. Some of these may be caught by using the DLG switch -Wambiguity.
  227.  
  228. 27.  zzbegexpr and zzendexpr point to the start and end of the string last
  229. matched by a regular expression in a #token statement.
  230.  
  231. However, zzlextext may be larger than the string pointed to by zzbegexpr and
  232. zzendexpr because it includes substrings accumulated through the use of
  233. zzmore().
  234.  
  235. 28.  ZZCOL in the lexical scanner controls the update of column information.
  236. This doesn't cause the zzsyn routine to report the position of tokens
  237. causing the error.  You'll still have to write that yourself.  The
  238. problem, I think, is that, due to look-ahead, the value of zzendcol
  239. will not be synchronized with the token causing the error, so that
  240. the problem becomes non-trivial.
  241.  
  242. 29.  If you want to use ZZCOL to keep track of the column position
  243. remember to adjust zzendcol in the lexical action when a character is not
  244. one print position wide (e.g. tabs or non-printing characters).
  245.  
  246. 30.  In version 1.00 it was common to change the token code based on
  247. semantic routines in the #token actions.  With the addition of semantic
  248. predicates in 1.06 this technique is now frowned upon.
  249.  
  250. Old style:
  251.  
  252.         #token TypedefName
  253.         #token ID  "[a-z A-Z]*"
  254.                 <<{if (isTypedefName(LATEXT(1))) NLA=TypedefName;};>>
  255.  
  256. New Style:
  257.  
  258.         #token ID  "[a-z A-Z]*"
  259.  
  260.         typedefName : <<LA(1)==ID ? isTypedefName(LATEXT(1)) : 1>> ID;
  261.  
  262. See the section on semantic predicates for a longer explanation.
  263.  
  264. 31.  The macro #define ZZCHAR_T <character-type> allows the user to
  265. specify the type of character constants generated by ANTLR and DLG.  However
  266. the algorithms in DLG needs to be revised in order to be 8 bit clean
  267. or support wide characters.
  268.  
  269. 32.  DLG has no operator like grep's "^" which anchors a pattern to the
  270. beginning of a line.  One can use tests based on zzbegcol only if column
  271. information is selected (#define ZZCOL) AND one is not using infinite
  272. lookahead mode (syntactic predicates).  A technique which does not depend
  273. on zzbegcol is to look for the newline character and then enter a special
  274. #lexclass.
  275.  
  276. Consider the problem of recognizing lines which have a "!" as the first
  277. character of a line.  A possible solution suggested by Doug Cuthbertson
  278. is:
  279.  
  280.     #token "\n"          <<zzline++; zzmode(BEGIN_LINE);>>
  281.  
  282. *** or ***
  283.  
  284.     #token "\n"          <<zzline++;
  285.                            if (zzchar=='!') zzmode(BEGIN_LINE);>>
  286.  
  287.     #lexclass BEGIN_LINE
  288.     #token BANG "!"      <<zzmode(START);>>
  289.     #token      "~[]"    <<zzmode(START); zzmore();>>
  290.  
  291. When a newline is encountered the #lexclass BEGIN_LINE is entered.  If
  292. the next character is a "!" it returns the token "BANG" and returns
  293. to #lexclass START.  If the next character is anything else it calls
  294. zzmore to accumulate additional characters for the token and, as before,
  295. returns to #lexclass START.  (The order of calls to zzmode() and zzmore()
  296. is not significant).
  297.  
  298. There are two limitations to this.
  299.  
  300. a. If there are other single character tokens which can appear in the first
  301. column then zzmore() won't work because the entire token has already been
  302. consumed.  Thus all single character tokens which can appear in column 1
  303. must appear in both #lexclass START and #lexclass BEGIN_LINE.
  304.  
  305. b. The first character of the first line is not preceded by a newline.
  306. thus DLG will be starting in the wrong state.  Thus you might want to rename
  307. "BEGIN_LINE" to "START" and "START" to "NORMAL".
  308.  
  309. Another solution is to use ANTLRf (input from a function) to insert
  310. you own function to do a limited amount of lexical processing
  311. which is difficult to express in DLG.
  312.  
  313. See Example 4 below.
  314. ===============================================================================
  315. Section on #lexclass
  316. -------------------------------------------------------------------------------
  317. 33.  Special care should be taken when using "in-line" regular expressions
  318. in rules if there are multiple lexical classes #lexclass).  ANTLR will
  319. place such regular expressions in the last lexical class defined.  If
  320. the last lexical class was not START you may be surprised.
  321.  
  322.         #lexclass START
  323.         ....
  324.         #lexclass COMMENT
  325.         ....
  326.  
  327.         inline_example: symbol "=" expression
  328.  
  329.                 This will place "=" in the #lexclass COMMENT (where
  330.                 it will never be matched) rather than the START #lexclass
  331.                 where the user meant it to be.
  332.  
  333. Since it is okay to specify parts of the #lexclass in several pieces
  334. it might be a good idea when using #lexclass to place "#lexclass START"
  335. just before the first rule - then any in-line definitions of tokens
  336. will be placed in the START #lexclass automatically.
  337.  
  338.         #lexclass START
  339.         ...
  340.         #lexclass A
  341.         ...
  342.         #lexclass B
  343.         ...
  344.         #lexclass START
  345.  
  346. 34.  A good example of the use of #lexclass are the definitions for C
  347. and C++ style comments, character literals, and string literals which
  348. can be found in pccts/antlr/lang/C/decl.g - or see Example 1 below.
  349. ===============================================================================
  350. Section on rules
  351. -------------------------------------------------------------------------------
  352. 35.  If a rule is not used (is an orphan) it can lead to unanticipated
  353. reports of ambiguity.  Use the ANTLR cross-reference option (-cr) to
  354. locate rules which are not referenced.
  355.  
  356. 36.  There is no way to express the idea "Any single token is acceptable
  357. at this point in the parse".  In other words, there is no syntactic
  358. equivalent to the lexical regular expression "~[]".  There are plans to
  359. add such a capability (".") to version 1.20 or 2.00 of ANTLR.
  360.  
  361. 37.  Don't confuse init-actions with actions which precede a rule.
  362. If the first element following the start of a rule or sub-rule
  363. is an action it is always interpreted as an init-action.
  364.  
  365. An init-action occurs in a scope which include the entire rule or sub-rule.
  366. An action which is NOT an init-action is enclosed in "{" and "}" during
  367. generation of code for the rule and has essentially zero scope - the
  368. action itself.
  369.  
  370. The difference between an init-action and an action which precedes
  371. a rule can be especially confusing when an action appears at the start
  372. of an alternative:
  373.  
  374. These APPEAR to be almost identical, but they aren't:
  375.  
  376.       b  : <<int i=0;>>  b1 > [i]  /* b1  <<...>> is an init-action        */
  377.          | <<int j=0;>>  b2 > [j]  /* b2  <<...>> is part of the rule      */
  378.          ;                         /*  and will cause a compilation error  */
  379.  
  380. On line "b1" the <<...>> appears immediately after the beginning of the
  381. rule making it an init-action.  On line "b2" the <<...>> does NOT appear at
  382. the start of a rule or sub-rule, thus it is interpreted as an action which
  383. happens to precede the rule.
  384.  
  385. This can be especially dangerous if you are in the habit of rearranging
  386. the order of alternatives in a rule.  For instance:
  387.  
  388. Changing this:
  389.  
  390.       b  : <<int i=0,j=0;>> <<i++;>>  b1 > [i]       /* c1 */
  391.          | <<j++;>>  b1 > [i]                        /* c2 */
  392.          ; 
  393.  
  394. to:
  395.  
  396.       b  : /* empty production */                    /* d1 */
  397.          | <<int i=0,j=0;>> <<i++;>>  b1 > [i]       /* d2 */
  398.          | <<j++;>>  b1 > [i]
  399.          ;
  400.  
  401. or to this:
  402.  
  403.       b
  404.          : <<j++;>>  b1 > [i]                        /* e1 */
  405.          | <<int i=0,j=0;>> <<i++;>>  b1 > [i]       /* e2 */
  406.  
  407. changes an init-action into a non-init action, and vice-versa.
  408.  
  409. 38.   In the case of sub-rules such as (...)+ and (...)* the
  410. init-action is executed just once before the sub-rule is entered.
  411. Consider the following example from section 3.6.1 (page 29) of the 1.00
  412. manual:
  413.  
  414.         a : <<List *p=NULL;>>                   // initialize list
  415.             Type
  416.             (  <<int i=0;>>                     // initialize index
  417.                Var <<append(p,i++,$1);>>
  418.             )*
  419.             <<OperateOn(p);>>
  420.           ;
  421.  
  422. 39.  Associativity and precedence of operations is determined by
  423. nesting of rules.  In the example below "=" associates to the right
  424. and has the lowest precedence.  Operators "+" and "*" associate to
  425. the left with "*" having the highest precedence.
  426.  
  427.         expr0   : expr1 {"=" expr0};
  428.         expr1   : expr2 ("\+" expr2)*;
  429.         expr2   : expr3 ("\*" expr3)*;
  430.         expr3   : ID;
  431.  
  432. See Example 2.
  433.  
  434. 40.  Fail actions for a rule can be placed after the final ";" of
  435.      a rule.  These will be:
  436.  
  437.          "executed after a syntax error is detected but before
  438.           a message is printed and the attributes have been destroyed.
  439.           However, attributes are not valid here because one does not
  440.           know at what point the error occurred and which attributes
  441.           even exist.  Fail actions are often useful for cleaning up
  442.           data structures or freeing memory."
  443.  
  444.                                                 (Page 29 of 1.00 manual)
  445.  
  446.       Example of a fail action:
  447.  
  448.           a : <<List *p=NULL;>>
  449.               ( Var <<append(p,$1);>> )+
  450.                   <<operateOn(p);rmlist(p);>>
  451.             ; <<rmlist(p);>>
  452.               **************  <--- Fail Action
  453.  
  454. 41.  When you have rules with large amounts of lookahead (that may
  455. cross several lines) you can use the ANTLR -gk option to make an
  456. ANTLR-generated parser delay lookahead fetches until absolutely
  457. necessary. To get better line number information (e.g. for error
  458. messages or #line directives) place an action which will save
  459. "zzline" in a variable at the start of the production where you
  460. want better line number information:
  461.  
  462.     a : <<int saveCurrentLine;>>
  463.         <<saveCurrentLine = zzline;>>   A B C
  464.                  << /* use saveCurrentLine not zzline here */ >>
  465.       | <<saveCurrentLine = zzline;>>   A B D
  466.                  << /* use saveCurrentLine not zzline here */ >>
  467.       ;
  468.  
  469. After the production has been matched you can use saveCurrentLine
  470. rather than the bogus "zzline".
  471.  
  472. Contributed by Terence "The ANTLR Guy" Parr (parrt@acm.org)
  473.  
  474. A new macro ZZINF_LINE() has been added to extract line information
  475. that is save in a manner similar to LATEXT.  This patch was added
  476. to the pccts FTP site on 27-Feb-94.
  477.  
  478. 42.  An easy way to get a list of the names of all the rules is
  479. to grep tokens.h for the string "void", edit the output from the ANTLR -cr
  480. option (cross-reference).
  481. ===============================================================================
  482. Section on Attributes
  483. -------------------------------------------------------------------------------
  484. 43.  Attributes are built automatically only for terminals.  For
  485. rules (non-terminals) one must assign an attribute to $0, use the
  486. $[token,...] convention for creating attributes, or use zzcr_attr.
  487.  
  488. 44.  If you define a zzcr_attr or zzmk_attr which allocates resources
  489. such as strings from the heap don't forget to define a zzd_attr routine
  490. to release the resources when the attribute is deleted.
  491.  
  492. 45.  Attributes go out of scope when the rule or sub-rule that defines
  493. them is exited.  Don't try to pass them to an outer rule or a sibling
  494. rule.  The only exception is  $0 which may be passed back to the containing
  495. rule as a return argument.  However, if the attribute contains a pointer
  496. which is copied (e.g. charptr.c) then extra caution is required because
  497. of the actions of zzd_attr().  See the next item for more information.
  498.  
  499. 46.  The charptr.c routines use a pointer to a string.  The string itself
  500. will go out of scope when the rule or sub-rule is exited.  Why ?  The
  501. string is copied to the heap when ANTLR calls the routine zzcr_attr
  502. supplied by charptr.c - however ANTLR also calls the charptr.c supplied
  503. routine zzd_attr (which frees the allocated string) as soon as the rule
  504. or sub-rule exits.  The result is that in order to pass charptr.c strings
  505. to outer rules (for instance to $0) it is necessary to make an independent
  506. copy of the string using strdup or else zero the pointer to prevent its
  507. deallocation.
  508.  
  509. 47.  To initialize $0 of a sub-rule use a construct like the following:
  510.  
  511.         decl : typeID
  512.                Var      <<$2.type = $1;>>
  513.                ( "," Var  <<$2.type = $0;>>)*[$1]
  514.                                              ****
  515.      See section 4.1.6.1 (page 29) of the 1.00 manual
  516.  
  517. 48.  One can use the zzdef0 macro to define a standard method for
  518. initializing $0 of a rule or sub-rule.  If the macro is defined it is
  519. invoked as zzdef0(&($0)).
  520.  
  521.      See section 4.1.6.1 (page 29) of the 1.00 manual
  522.  
  523. 49.  The expression $$ refers to the attribute of the named rule.
  524. The expression $0 refers to the attribute of the the enclosing rule,
  525. (which might be a sub-rule).
  526.  
  527.         rule : a b (c d (e f g) h) i
  528.  
  529. For (e f g) $0 becomes $3 of (c d  ... h).  For (c d ... h) $0 becomes
  530. $3 of (a b ... i).  However $$ always is equivalent to $rule.
  531.  
  532. 50.  If you construct temporary attributes in the middle of the
  533. recognition of a rule, remember to deallocate the structure should the
  534. rule fail.  The code for failure goes after the ";" and before the next
  535. rule.  For this reason it is sometimes desirable to defer some processing
  536. until the rule is recognized rather than the most appropriate place.
  537. ===============================================================================
  538. Section on ASTs
  539. -------------------------------------------------------------------------------
  540. 51.  If you define a zzcr_ast or zzmk_ast which allocates resources
  541. such as strings from the heap don't forget to define a zzd_ast routine
  542. to release the resources when the AST is deleted.
  543.  
  544. 52.  If you construct temporary ASTs in the middle of the recognition of a
  545. rule, remember to deallocate the structure should the rule fail.  The code
  546. for failure goes after the ";" and before the next rule.  For this reason
  547. it is sometimes desirable to defer some processing until the rule is
  548. recognized rather than the most appropriate place.
  549.  
  550. 53.  If you want to place prototypes for routines that have an AST
  551. as an argument in the #header directive you should explicitly
  552. #include "ast.h" after the #define AST_FIELDS and before any references
  553. to AST:
  554.  
  555.         #define AST_FIELDS int token;char *text;
  556.         #include "ast.h"
  557.         #define zzcr_ast(ast,attr,tok,astText) \
  558.                 create_ast(ast,attr,tok,text)
  559.         void create_ast (AST *ast,Attr *attr,int tok,char *text);
  560.  
  561. 54.  The make-a-root operator for ASTs ("^") can be applied only to
  562. terminals.  I think this is because a child rule might return a tree rather
  563. than a single AST.  If it did then it could not be made into a root
  564. as it is already a root and the corresponding fields of the structure
  565. are already in use.  To make an AST returned by a called rule a root use
  566. the expression: #(root-rule sibling1 sibling2 sibling3).
  567.  
  568.         add !         :  expr ("\+"^ expr) ;    // Is ok
  569.  
  570.         addOperator ! :  expr (AddOp expr)      // Is NOT ok
  571.         addOp         : "\+" | "-";             //
  572.  
  573. Example 2 describes a workaround for this restriction.
  574.  
  575. 55.  Do not assign to #0 of a rule unless automatic construction of ASTs
  576. has been disabled using the "!" operator:
  577.  
  578.                 a! : x y z <<#0=#(#1 #2 #3);>>  // ok
  579.                 a  : x y z <<#0=#(#1 #2 #3);>>  // NOT ok
  580.  
  581. The reason for the restriction is that assignment to #0 will cause any
  582. ASTs pointed to by #0 to be lost when the pointer is overwritten.  (Three
  583. cheers for C++ copy constructors).
  584.  
  585. The stated restriction is somewhat stronger than necessary.  You can
  586. assign to #0 even when using automated AST construction, if the old
  587. tree pointed to by #0 is part of the new tree constructed by #(...).
  588. For example:
  589.  
  590.         #token COMMA    ","
  591.         #token STMT_LIST
  592.  
  593.         stmt_list: stmt (COMMA stmt)*  <<#0=#(#[STMT_LIST],#0);>>
  594.  
  595. The automatically constructed tree pointed to by #0 is just put at the
  596. end of the new list, so nothing is lost.
  597.  
  598. However, if you reassign to #0 in the middle of the rule, automatic tree
  599. construction will result in the addition of remaining elements at the end
  600. of the new tree.  This is not recommended by TJP.
  601.  
  602. 56.  If you use ASTs you have to pass a root AST to ANTLR.
  603.  
  604.                 AST     *root=NULL;
  605.         again:
  606.                 ANTLR (start(&root),stdin);
  607.                 walk_the_tree(root);
  608.                 zzfree_ast(root);
  609.                 root=NULL;
  610.                 goto again;
  611.  
  612. 57.  zzfree_ast(AST *tree) will recursively descend the AST tree and free
  613. all sub-trees.  The user should supply a routine zzd_ast to
  614. free any resources used by a single node - such as pointers to
  615. character strings allocated on the heap.  See Example 2 on associativity
  616. and precedence.
  617.  
  618. 58.  AST elements in rules are assigned numbers in the same fashion as
  619. attributes with three exceptions:
  620.  
  621.      1. A hole is left in the sequence when sub-rules are encountered.
  622.      2. #0 is the AST of the named rule, not the sub-rule - see the next item
  623.      3. There is nothing analogous to $i.j notation (which allows one
  624.         to refer to attributes from earlier in the rule).  In other words,
  625.         you can't use #i.j notation to refer to an AST created earlier
  626.         in the rule.
  627.  
  628.                 There are plans to add notation similar to Sorcerer's
  629.                 tagged elements, but this will not appear for a while.
  630.                 (24-Mar-94)
  631.  
  632. Consider the following example:
  633.  
  634.      a : b              // B is #1 for the rule
  635.          (c d)*         // C is #1 when scope is inside the sub-rule
  636.                         // D is #2 when scope is inside the sub-rule
  637.                         //   You may *NOT* refer to b as #1.1
  638.          e              // E is #3 for the rule
  639.                         // There is NO #2 for the rule
  640.  
  641. 59.  The expression #0 refers to the AST of the named rule.  Thus it is
  642. a misnomer and (for consistentcy) should probably have been named ## or #$.
  643. There is nothing equivalent to $0 for ASTs.  This is probably because
  644. sub-rules aren't assigned AST numbers in a rule.  See above.
  645.  
  646. 60.  Associativity and precedence of operations is determined by nesting
  647. of rules.  In the example below "=" associates to the right and has the
  648. lowest precedence.  Operators "+" and "*" associate to the left with "*"
  649. having the highest precedence.
  650.  
  651.         expr0   : expr1 {"=" expr0};
  652.         expr1   : expr2 ("\+" expr2)*;
  653.         expr2   : expr3 ("\*" expr3)*;
  654.         expr3   : ID;
  655.  
  656. In Example 2 the zzpre_ast routine is used to walk all the AST nodes.  The
  657. AST nodes are numbered during creation so that one can see the order in
  658. which they are created and the order in which they are deleted.  Do not
  659. confuse the "#" in the sample output with the AST numbers used to refer to
  660. elements of a rule in the action part of a the rule.  The "#" in the
  661. sample output are just to make it simpler to match elements of the
  662. expression tree with the order in which zzd_ast is called for each
  663. node in the tree.
  664.  
  665. 61.  If the make-as-root operator were not used in the rules:
  666.  
  667.         ;expr0  : expr1 {"=" expr0}
  668.         ;expr1  : expr2 ("\+" expr2)*
  669.          ;expr2  : expr3 ("\*" expr3)*
  670.         ;expr3  : ID
  671.  
  672.     With input:
  673.  
  674.         a+b*c
  675.  
  676.     The output would be:
  677.  
  678.          a <#1>  \+ <#2>  b <#3>  \* <#4>  c <#5>  NEWLINE <#6>
  679.  
  680.         zzd_ast called for <node #6>
  681.         zzd_ast called for <node #5>
  682.         zzd_ast called for <node #4>
  683.         zzd_ast called for <node #3>
  684.         zzd_ast called for <node #2>
  685.         zzd_ast called for <node #1>
  686.  
  687. 62.  Suppose that one wanted to replace the terminal "+" with the rule:
  688.  
  689.         addOp  : "\+" | "-" ;
  690.  
  691.      Then one would be unable to use the "make-as-root" operator because
  692.      it can be applied only to terminals.  This is one possible workaround:
  693.  
  694.         expr    : (expr0 NEWLINE)
  695.         ;expr0  : expr1 {"="^ expr0}
  696.         ;expr1! : expr2 <<#0=#1;>>
  697.                         (addOp expr2  <<#0=#(#1,#0,#2);>> )*
  698.         ;expr2  : expr3 ("\*"^ expr3)*
  699.         ;expr3  : ID
  700.         ;addOp  : "\+" | "\-"
  701.  
  702.      With input:
  703.  
  704.         a-b-c
  705.  
  706.      The output is:
  707.  
  708.         ( \- <#4> ( \- <#2>  a <#1>  b <#3> ) c <#5> ) NEWLINE <#6>
  709.  
  710. The "!" for rule "expr1" disables automatic constructions of ASTs in the
  711. rule.  This allows one to manipulate #0 manually.  If the expression had
  712. no addition operator then the sub-rule "(addOp expr)*" would not be
  713. executed and #0 will be assigned the AST constructed by rule expr2 (i.e.
  714. AST #1).  However if there is an addOp present then each time the sub-rule
  715. is rescanned due to the "(...)*" the current tree in #0 is placed as the
  716. first of two siblings underneath a new tree.  This new tree has the AST
  717. returned by addOp (AST #1 of the addOp sub-rule) as the root.
  718.  
  719. 63.  There is an option for doubly linked ASTs in the module ast.c. It
  720. is controlled by #define zzAST_DOUBLE.  See page 12 of the 1.06 manual
  721. for more information.
  722.  
  723. 64.  If a rule which creates an AST is called and the result is not
  724. linked into the tree being constructed then zzd_ast will not be called
  725. to release the resources used by the rule.  This it is important
  726. when rules are used in syntactic predicates.  The following construct
  727. is dangerous because the ASTs created when "b_predicate" calls "b" will
  728. be lost unless they are explicitly deallocated by a call to zzfree_ast().
  729.  
  730.         a             : (b_predicate) ? b
  731.         b_predicate ! : b !
  732.         b             : c d e ;
  733.  
  734. ===============================================================================
  735. Section on Semantic Predicates
  736. -------------------------------------------------------------------------------
  737. 65.  There is a bug in 1.10 which prevents semantic predicates from including
  738. an unescaped newline.  The predicate is incorrectly "string-ized" in the
  739. call to zzfailed_predicate.
  740.  
  741.                 rule: <<do_test();
  742.                         this_will_not_work()>>? x y z;
  743.  
  744.                 rule: <<do_test();\
  745.                         this_will_work()>>? x y z;
  746.  
  747. 66.  Semantic predicates are enclosed in "<<... >>?"  but because they are
  748. inside "if" statements they normally do not end with a ";" - unlike other
  749. code enclosed in "<<...>>" in ANTLR.
  750.  
  751. 67.  Semantic predicates which are not the first element in the rule or
  752. sub-rule become "validation predicates" and are not used for prediction.
  753. After all, if there are no alternatives, then there is no need for
  754. prediction - and alternatives exist only at the left edge of rules
  755. and sub-rules.  Even if the semantic predicates are on the left edge it
  756. is no guarantee that it will be part of the prediction expression.
  757. Consider the following two examples:
  758.  
  759.         a  :  << LA(1)==ID ? propX(LATEXT(1)) : 1 >>?  ID glob  /* a1 */
  760.            |  ID glob                                           /* a2 */
  761.            ;
  762.         b  :  << LA(1)==ID ? propX(LATEXT(1)) : 1 >>?  ID glob  /* b1 */
  763.            |  NUMBER glob                                       /* b2 */
  764.            ;
  765.  
  766. Rule a requires the semantic predicate to disambiguate alternatives
  767. a1 and a2 because the rules are otherwise identical.  Rule b has a
  768. token type of NUMBER in alternative b2 so it can be distinguished from
  769. b1 without evaluation of the semantic predicate during prediction.  In
  770. both cases the semantic predicate will be evaluated inside the rule.
  771.  
  772. When the tokens which can follow a rule allow ANTLR to disambiguate the
  773. expression without resort to semantic predicates ANTLR may not evaluate
  774. the semantic predicate in the prediction code.  For example:
  775.  
  776.         simple_func   : <<LA(1)==ID ? isSimpleFunc(LATEXT(1)) : 1>>? ID
  777.         complex_func  : <<LA(1)==ID ? isComplexFunc(LATEXT(1)) : 1>>? ID
  778.  
  779.         function_call : "("  ")"
  780.  
  781.         func : simple_func function_call
  782.              | complex_func "." ID function_call
  783.  
  784. In this case, a "simple_func" MUST be followed by a "(", and a
  785. "complex_func" MUST be followed by a ".", so it is unnecessary to evaluate
  786. the semantic predicates in order to predict which of the alternative to
  787. use.  A simple test of the lookahead tokens is sufficient. As stated before,
  788. the semantic predicates will still be used to validate the rule.
  789.  
  790. 68.  Suppose that the requirement that all semantic predicates used in
  791. prediction expressions were lifted.  Consider the following code
  792. segment:
  793.  
  794.         cast_expr                          /* a1  */
  795.             : LP typedef RP cast_expr      /* a2  */
  796.             | expr13                       /* a3  */
  797.         ;expr13                            /* a4  */
  798.             : id_name                      /* a5  */
  799.             | LP cast_expr RP              /* a6  */
  800.         ;typedef_name                      /* a7  */
  801.             : <<LA(1)==ID ? isTypedefName(LATEXT(1)) : 1 >>? ID    /* a8  */
  802.         ;id_name                           /* a9  */
  803.             : ID                           /* a10 */
  804.  
  805. Now consider the token sequences:
  806.  
  807.         Token:  #1           #2               #3   #4
  808.                 --   -----------------------  --   --
  809.                 "("  ID-which-is-typedef     ")"   ID
  810.                 "("  ID-which-is-NOT-typedef ")"
  811.  
  812. Were the semantic predicate at line a8 hoisted to predict which alternative
  813. of cast_expr to use (a2 or a3) the program would use the wrong lookahead
  814. token (LA(1) and LATEXT(1)) rather than LA(2) and LATEXT(2) to check for an
  815. ID which satisfies "isTypedefName()".  This problem could perhaps be
  816. solved by application of sufficient ingenuity, however, in the meantime
  817. the solution is to rewrite the rules so as to move the decision point
  818. to the left edge of the production.
  819.  
  820. First perform in-line expansion of expr13 in cast_expr:
  821.  
  822.         cast_expr                          /* b1 */
  823.             : LP typedef RP cast_expr      /* b2 */
  824.             | id_name                      /* b3 */
  825.             | LP cast_expr RP              /* b4 */
  826.  
  827. Secondly, move the alternatives (in cast_expr) beginning with LP to a
  828. separate rule so that "typedef" and "cast_expr" will be on the left edge:
  829.  
  830.         cast_expr                          /* c1  */
  831.             : LP cast_expr_suffix          /* c2  */
  832.             | id_name                      /* c3  */
  833.         ;cast_expr_suffix                  /* c4  */
  834.             : typedef RP cast_expr         /* c5  */
  835.             | cast_expr RP                 /* c6  */
  836.         ;typedef_name                      /* c7  */
  837.             : <<LA(1)==ID ? isTypedefName(LATEXT(1)) : 1 >>? ID    /* c8  */
  838.         ;id_name                           /* c9  */
  839.             : ID                           /* c10 */
  840.  
  841. This will result in the desired treatment of the semantic predicate to
  842. choose from alternatives c5 and c6.
  843.  
  844. 69.  Validation predicates are evaluated by the parser.  If they fail a
  845. call to zzfailed_predicate(string)) is made.  To disable the message
  846.  
  847. redefine the macro zzfailed_predicate(string) or use the optional
  848. "failed predicate" action which is enclosed in "[" and "]" and follows
  849. immediately after the predicate:
  850.  
  851.         a : <<LA(1)==ID ?
  852.               isTypedef(LATEXT(1)) : 1>>?[printf("Not a typedef\n");]
  853.  
  854. 70.  An expression in a semantic predicate (e.g. <<isFunc()>>? ) should not
  855. have side-effects. If there is no match then the rest of the rule using the
  856. syntactic predicate won't be executed.
  857.  
  858. 71.  A documented restriction of ANTLR is the inability to hoist multiple
  859. semantic predicates.  However, no error message is given when one attempts
  860. this. When compiled with k=1 and ck=2 this generates inappropriate code
  861. in "statement" when attempting to predict "expr":
  862.  
  863.         statement
  864.                 : expr
  865.                 | declaration
  866.         ;expr
  867.                 : commandName BARK
  868.                 | typedefName GROWL
  869.         ;declaration
  870.                 : typedefName BARK
  871.         ;typedefName
  872.                 : <<LA(1)==ID ? istypedefName(LATEXT(1)) : 1>>? ID
  873.         ;commandName
  874.                 : <<LA(1)==ID ? isCommand(LATEXT(1)) : 1>>? ID
  875.         ;
  876.  
  877. Some help is obtained by using leading actions to inhibit hoisting as
  878. described in the next note.
  879.  
  880. 72.  Leading actions will inhibit the hoisting of semantic predicates into
  881. the prediction of rules.
  882.  
  883.         expr_rhs
  884.                 : <<;>> <<>>  expr0
  885.                 | command
  886.  
  887. See the section on known bugs for a more complete example.
  888.  
  889. 73.  When using semantic predicates in ANTLR is is *IMPORTANT* to
  890. understand what the "-prc on" ("predicate context computation")
  891. option does and what "-prc off" doesn't do.  Consider the following
  892. example:
  893.  
  894.                 +------------------------------------------------------+
  895.                 | Note:  All examples in this sub-section are based on |
  896.                 | code generated with -k=1 and -ck=1.                  |
  897.                 +------------------------------------------------------+
  898.  
  899.         expr    : upper
  900.                 | lower
  901.                 | number
  902.                 ;
  903.  
  904.         upper   : <<isU(LATEXT(1))>>? ID ;
  905.         lower   : <<isL(LATEXT(1))>>? ID ;
  906.         number  : NUMBER ;
  907.  
  908. With "-prc on" ("-prc off" is the default) the code for expr() to predict
  909. upper() would resemble:
  910.  
  911.       if (LA(1)==ID && isU(LATEXT(1)) && LA(1)==ID) {   /* a1  */
  912.                 upper(zzSTR);                           /* a2  */
  913.         }                                               /* a3  */
  914.         else {                                          /* a4  */
  915.                 if (LA(1)==ID && isL(LATEXT(1)) && LA(1)==ID) {  /* a5  */
  916.                         lower(zzSTR);                   /* a6  */
  917.                 }                                       /* a7  */
  918.                 else {                                  /* a8  */
  919.                         if (LA(1)==NUMBER) {            /* a9  */
  920.                                 zzmatch(NUMBER);        /* a10 */
  921.                         }                               /* a11 */
  922.                         else                            /* a12 */
  923.                                 {zzFAIL();goto fail;}   /* a13 */
  924.                 }                                       /* a14 */
  925.         } ...
  926.         ...
  927.  
  928.         *******************************************************
  929.         ***                                                 ***
  930.         *** Starting with version 1.20:                     ***
  931.         ***   Predicate tests appear AFTER lookahead tests  ***
  932.         ***                                                 ***
  933.         *******************************************************
  934.  
  935. Note that each test of LATEXT(i) is guarded by a test of the token type
  936. (e.g. "LA(1)==ID && isU(LATEXT(1)").
  937.  
  938. With "-prc off" the code would resemble:
  939.  
  940.      if (isU(LATEXT(1)) && LA(1)==ID) {             /* b1  */
  941.                 upper(zzSTR);                       /* b2  */
  942.         }                                           /* b3  */
  943.         else {                                      /* b4  */
  944.                 if (isL(LATEXT(1)) && LA(1)==ID) {  /* b5  */
  945.                         lower(zzSTR);               /* b6  */
  946.                 }                                   /* b7  */
  947.                 else {                              /* b8  */
  948.                         if ( (LA(1)==NUMBER) ) {    /* b9  */
  949.                                 zzmatch(NUMBER);    /* b10 */
  950.                         }                           /* b11 */
  951.                         else                        /* b12 */
  952.                                 {zzFAIL();goto fail;}       /* b13 */
  953.                 }                                   /* b14 */
  954.         } ...
  955.         ...
  956.  
  957. Thus when coding the grammar for use with "-prc off" it is necessary
  958. to do something like:
  959.  
  960.         upper   : <<LA(1)==ID && isU(LATEXT(1))>>? ID ;
  961.         lower   : <<LA(1)==ID && isL(LATEXT(1))>>? ID ;
  962.  
  963. This will make sure that if the token is of type NUMBER that it is not
  964. passed to isU() or isL() when using "-prc off".
  965.  
  966. So, you say to yourself, "-prc on" is good and "-prc off" is bad. Wrong.
  967.  
  968. Consider the following slightly more complicated example in which the
  969. first alternative of rule "expr" contains tokens of two different types:
  970.  
  971.         expr    : ( upper | NUMBER ) NUMBER
  972.                 | lower
  973.                 | ID
  974.                 ;
  975.  
  976.         upper   : <<LA(1)==ID && isU(LATEXT(1))>>? ID ;
  977.         lower   : <<LA(1)==ID && isL(LATEXT(1))>>? ID ;
  978.         number  : NUMBER ;
  979.  
  980. With "-prc off" the code would resemble:
  981.  
  982.         ...
  983.         {                                                 /* c1  */
  984.         if (LA(1)==ID && isU(LATEXT(1)) &&                /* c2  */
  985.              ( LA(1)==ID || LA(1)==NUMBER) ) {            /* c3  */
  986.                 {                                         /* c4  */
  987.                         if (LA(1)==ID) {                  /* c5  */
  988.                                 upper(zzSTR);             /* c6  */
  989.                         }                                 /* c7  */
  990.                         else {                            /* c8  */
  991.                                 if (LA(1)==NUMBER) {      /* c9  */
  992.                                         zzmatch(NUMBER);  /* c10 */
  993.                                 }                         /* c11 */
  994.                                 else {zzFAIL();goto fail;}/* c12 */
  995.                         }                                 /* c13 */
  996.                 } ...
  997.         ...
  998.  
  999.  
  1000. Note that if the token is a NUMBER (i.e. LA(1)==NUMBER) then the clause at
  1001. line c2 ("LA(1)==ID && ...") will always be false, which implies that the
  1002. test in the "if" statement (lines c2/c3) will always be false. (In other
  1003. words LA(1)==NUMBER implies LA(1)!=ID).  Thus the sub-rule for NUMBER at
  1004. line c9 can never be reached.
  1005.  
  1006. With "-prc on" essentially the same code is generated, although it
  1007. is not necessary to manually code a test for token type ID preceding
  1008. the call to "isU()".
  1009.  
  1010. The workaround is to to bypass the heart of the  predicate when
  1011. testing the wrong type of token.
  1012.  
  1013.         upper   : <<LA(1)==ID ? isU(LATEXT(1)) : 1>>? ID ;
  1014.         lower   : <<LA(1)==ID ? isL(LATEXT(1)) : 1>>? ID ;
  1015.  
  1016. Then with "-prc off" the code would resemble:
  1017.         ...
  1018.         {                                           /* d1  */
  1019.         if ( (LA(1)==ID ? isU(LATEXT(1)) : 1) &&    /* d2  */
  1020.                 (LA(1)==ID || LA(1)==NUMBER) ) {    /* d3  */
  1021.                 ...
  1022.         ...
  1023.  
  1024. With this correction the body of the "if" statement is now reachable
  1025. even if the token type is NUMBER - the "if" statement does what one
  1026. wants.
  1027.  
  1028. With "-prc on" the code would resemble:
  1029.  
  1030.         ...                                       /* e1 */
  1031.         if (LA(1)==ID &&                          /* e2 */
  1032.              (LA(1)==ID ? isU(LATEXT(1)) : 1) &&  /* e3 */
  1033.              (LA(1)==ID || LA(1)==NUMBER) ) {     /* e4 */
  1034.                 ...
  1035.         ...
  1036.  
  1037. Note that the problem of the unreachable "if" statement body has
  1038. reappeared because of the redundant test ("e2") added by the predicate
  1039. computation.
  1040.  
  1041. The lesson seems to be: when using rules which have alternatives which
  1042. are "visible" to ANTLR (within the lookahead distance) that have different
  1043. token types it is probably dangerous to use "-prc on".
  1044.  
  1045. 74.  You cannot use downward inheritance to pass parameters
  1046. to semantic predicates which are NOT validation predicates.  The
  1047. problem appears when the semantic predicate is hoisted into a
  1048. parent rule to predict which rule to call:
  1049.  
  1050. For instance:
  1051.  
  1052.         a :  b1 [flag]
  1053.           |  b2
  1054.           |  b3
  1055.  
  1056.         b1 [int flag]
  1057.           : <<LA(1)==ID && flag && hasPropertyABC (LATEXT(1))>>? ID ;
  1058.  
  1059.         b2 :
  1060.           : <<LA(1)==ID && hasPropertyXYZ (LATEXT(1))>>? ID ;
  1061.  
  1062.         b3 : ID ;
  1063.  
  1064. When the semantic predicate is evaluated within rule "a" to determine
  1065. whether to call b1, b2, or b3 the compiler will discover that there
  1066. is no variable named "flag" for procedure "a()".  If you are unlucky
  1067. enough to have a variable named "flag" in a() then you will have a
  1068. VERY difficult-to-find bug.
  1069.  
  1070. The -prc option has no effect on this behavior.
  1071.  
  1072. 75.  Another reason why semantic predicates must not have side effects is
  1073. that when they are hoisted into a parent rule in order to decide which
  1074. rule to call they will be invoked twice: once as part of the prediction
  1075. and a second time as part of the validation of the rule.
  1076.  
  1077. Consider the example above of upper and lower.  When the input does
  1078. in fact match "upper" the routine isU() will be called twice: once inside
  1079. expr() to help predict which rule to call, and a second time in upper() to
  1080. validate the prediction.  If the second test fails the macro zzpred_fail()
  1081. is called.
  1082.  
  1083. As far as I can tell, there is no simple way to disable the use of a
  1084. semantic predicate for validation after it has been used for prediction.
  1085.  
  1086. ===============================================================================
  1087. Section on Syntactic Predicates (also known as "Guess Mode")
  1088. -------------------------------------------------------------------------------
  1089. 76.  The terms "infinite lookahead", "guess mode", and "syntactic
  1090. predicates" are all equivalent.  The term "syntactic predicate" emphasizes
  1091. that is handled by the parser. The term "guess mode" emphasizes that the
  1092. parser may have to backtrack.  The term "infinite lookahead" emphasizes
  1093. the implementation in ANTLR: the entire input is read, processed, and
  1094. tokenized by DLG before ANTLR begins parsing.
  1095.  
  1096. 77.  An expression in a syntactic predicate should not have side-effects.
  1097. If there is no match then the rule using the syntactic predicate won't be
  1098. executed.
  1099.  
  1100. 78.  When using syntactic predicates the entire input buffer is read and
  1101. tokenized by DLG before parsing by ANTLR begins.  If a "wrong" guess
  1102. requires that parsing be rewound to an earlier point all attributes
  1103. that were creating during the "guess" are destroyed and the parsing
  1104. begins again and create new attributes at it reparses the (previously)
  1105. tokenized input.
  1106.  
  1107. 79.  In infinite lookahead mode the line and column information is
  1108. hopelessly out-of-sync because zzline will contain the line number of
  1109. the last line of input - the entire input was parsed before
  1110. scanning was begun.  The line and column information is not restored
  1111. during backtracking.  To keep track of the line information in a meaningful
  1112. way one has to use the new ZZINF_LINE macro which was added as a patch
  1113. to the FTP site on 27-Feb-94.
  1114.  
  1115. Putting line and column information in a field of the attribute will not
  1116. help.  The attributes are created by ANTLR, not DLG, and when ANTLR
  1117. backtracks it destroys any attributes that were created in making the
  1118. incorrect guess.
  1119.  
  1120. 80.  As infinite lookahead mode causes the entire input to be scanned
  1121. by DLG before ANTLR begins parsing, one cannot depend on feedback from
  1122. the parser to the lexer to handle things like providing special token codes
  1123. for items which are in a symbol table (the "lex hack" for typedefs
  1124. in the C language).  Instead one MUST use semantic predicates which allow
  1125. for such decisions to be made by the parser.
  1126.  
  1127. 81.  One cannot use an interactive scanner (ANTLR -gk option) with the
  1128. ANTLR infinite lookahead and backtracking options (syntactic predicates).
  1129.  
  1130. 82.  An example of the need for syntactic predicates is the case where
  1131. relational expressions involving "<" and ">"  are enclosed in angle bracket
  1132. pairs.
  1133.  
  1134.         Relation:    a < b
  1135.         Array Index: b <i>
  1136.         Problem:     a < b<i>
  1137.                  vs. b < a>
  1138.  
  1139. I was going to make this into an extended example, but I haven't had
  1140. time yet.
  1141.  
  1142. 83. If your syntactic predicate invokes routines which build ASTs this
  1143. violates the rule that syntactic predicates should not have side effects.
  1144. You'll end up with lots of extra nodes added to the AST.
  1145.  
  1146. 84.  The following is an example of the use of syntactic predicates.
  1147.  
  1148.         program : ( s SEMI )* ;
  1149.  
  1150.         s       : ( ID EQUALS )? ID EQUALS e
  1151.                   | e
  1152.                   ;
  1153.  
  1154.         e       : t ( PLUS t | MINUS t )* ;
  1155.  
  1156.         t       : f ( TIMES f | DIV f )* ;
  1157.  
  1158.         f       : Num
  1159.                   | ID
  1160.                   | "\(" e "\)"
  1161.                   ;
  1162.  
  1163. When compiled with:
  1164.  
  1165.         antlr -fe err.c -fh stdpccts.h -fl parser.dlg -ft tokens.h \
  1166.                  -fm mode.h -k 1 test.g
  1167.  
  1168. One gets the following warning:
  1169.  
  1170.    warning: alts 1 and 2 of the rule itself ambiguous upon { ID }
  1171.  
  1172. even though the manual suggests that this is okay.  The only problem is
  1173. that ANTLR 1.10 should NOT issue this error message unless the -w2 option
  1174. is selected.
  1175.  
  1176. Included with permission of S. Salters
  1177.  
  1178. ===============================================================================
  1179. Section on Inheritance
  1180. -------------------------------------------------------------------------------
  1181. 85.  A rule which uses upward inheritance:
  1182.  
  1183.         rule > [int result] :  x | y | z;
  1184.  
  1185. Is simply declaring a function which returns an "int" as a function
  1186. value.  If the function has more than one item passed via upward
  1187. inheritance then ANTLR creates a structure to hold the result and
  1188. then copies each component of the structure to the upward inheritance
  1189. variables.
  1190.  
  1191. 86.  When writing a rule that uses downward inheritance:
  1192.  
  1193.         rule [int *x] : r1 r2 r3
  1194.  
  1195. one should remember that the arguments passed via downward inheritance are
  1196. simply arguments to a function.  If one is using downward inheritance
  1197. syntax to pass results back to the caller (really upward inheritance !)
  1198. then it is necessary to pass the address of the variable which will receive
  1199. the result.
  1200.  
  1201. 87.  ANTLR is smart enough to combine the declaration for an AST with
  1202. the items declared via downward inheritance when constructing the
  1203. prototype for a function which uses both ASTs and downward inheritance.
  1204.  
  1205. ===============================================================================
  1206. Section on LA, LATEXT, NLA, and NLATEXT
  1207. -------------------------------------------------------------------------------
  1208. 88.  Need examples of LATEXT for various forms of lookahead.
  1209.  
  1210. ===============================================================================
  1211. Section on Prototypes
  1212. -------------------------------------------------------------------------------
  1213. 89.  Prototype for typical create_ast routine:
  1214.  
  1215.      #define zzcr_ast(ast,attr,tok,astText) \
  1216.           create_ast(ast,attr,tok,text)
  1217.  
  1218.       void create_ast (AST *ast,Attr *attr,int tok,char *text);
  1219.  
  1220. 90.  Prototype for typical make_ast routine:
  1221.  
  1222.      AST *zzmk_ast (AST *ast,int token,char *text)
  1223.  
  1224. 91.  Prototype for typical create_attr routine:
  1225.  
  1226.      #define zzcr_attr(attr,token,text) \
  1227.                 create_attr(attr,token,text)
  1228.  
  1229.      void create_attr (Attrib *attr,int token,char *text);
  1230.  
  1231. 92.  Prototype for ANTLR (these are actually macros):
  1232.  
  1233.         read from file:     void ANTLR   (void startRule(...),FILE *)
  1234.         read from string:   void ANTLRs  (void startRule(...),zzchar_t *)
  1235.         read from function: void ANTLRf  (void startRule(...),int (*)())
  1236.  
  1237.              In the call to ANTLRf the function behaves like getchar()
  1238.              in that it returns EOF (-1) to indicate end-of-file.
  1239.  
  1240.      If ASTs are used or there is downward or upward inheritance then the
  1241.      call to the startRule must pass these arguments:
  1242.  
  1243.                 AST     *root;
  1244.                 ANTLRf (startRule(&root),stdin);
  1245.  
  1246. ===============================================================================
  1247. Section on ANTLR/DLG Internals Routines That Might Be Useful
  1248. -------------------------------------------------------------------------------
  1249.                 ****************************
  1250.                 ****************************
  1251.                 **                        **
  1252.                 **  Use at your own risk  **
  1253.                 **                        **
  1254.                 ****************************
  1255.                 ****************************
  1256.  
  1257. 93.  static int zzauto - defined in dlgauto.h
  1258.  
  1259.      Current DLG mode.  This is used by zzmode() only.
  1260.  
  1261. 94.  void zzerr (char * s) defined in dlgauto.h
  1262.  
  1263.      Defaults to zzerrstd(char *s) in dlgauto.h
  1264.  
  1265.      Unless replaced by a user-written error reporting routine:
  1266.  
  1267.              fprintf(stderr,
  1268.                         "%s near line %d (text was '%s')\n",
  1269.                         ((s == NULL) ? "Lexical error" : s),
  1270.                         zzline,zzlextext);
  1271.  
  1272. 95.  static char zzebuf[70] defined in dlgauto.h
  1273. ===============================================================================
  1274. Section on Known Minor Bugs
  1275. -------------------------------------------------------------------------------
  1276. 96.  FoLink() bug and its fix reported 24-Feb-94. This fixes a bug in
  1277. ANTLR which caused nodes to be revisited multiple times during a traversal
  1278. of trees.  Under some circumstances large grammars could take 50 times as
  1279. long to analyze.
  1280.  
  1281. 97.  As of 24-Feb-94 there was an off-by-one problem in the testing for
  1282. lowercase in range expressions. The problem appears if the last character
  1283. in the range is "z" or "Z" (e.g. [a-z]).  The temporary workaround is to
  1284. use a range of the form "[a-yz]".
  1285.  
  1286. 98.  As of 22-Mar-94 there was a bug in the hoisting of semantic predicates
  1287. when all alternatives of a rule have the same lookahead token.  (I believe
  1288. this is a special case of the inability of ANTLR to hoist multiple
  1289. semantic predicates).  The following example uses ANTLR options
  1290. "-prc off -k 1 -ck 3".  Consider the following:
  1291.  
  1292.         ;obj_name
  1293.                 : global_func_id
  1294.                 | simple_class SUFFIX_DOT
  1295.                 | ID
  1296.  
  1297.         ;simple_class
  1298.                 : <<(LA(1)==ID ? isClass(LATEXT(1)) : 1)>>? ID
  1299.  
  1300.         ;global_func_id
  1301.                 : <<(LA(1)==ID ? isFunction(LATEXT(1)) : 1)>>? ID
  1302.  
  1303. One would expect prediction code to look something like the following:
  1304.  
  1305.         if ( (test_for_class || test_for_function) && LA(1)==ID ...
  1306.            ...
  1307.            if (test_for_class && LA(1)==ID) simple_class()
  1308.            ...
  1309.            else if (test_for_function && LA(1)==ID) global_func_id()
  1310.            ...
  1311.            else if (LA(1)==ID) {match();consume();}
  1312.  
  1313. But what one sees is the use of "&&" rather than "||".  Below is the
  1314. complete example: It is not meant to execute, but only to be sufficient
  1315. to generate ANTLR output for inspection.
  1316.  
  1317. The workaround is to precede semantic predicates with an action
  1318. (such as "<<;>>") which inhibits hoisting into the prediction
  1319. expression.
  1320.  
  1321. #header
  1322. <<
  1323. #include "charptr.h"
  1324. >>
  1325.  
  1326. #token  QUESTION
  1327. #token  COMMA
  1328. #token  ID
  1329.  
  1330. #token  Eof     "@"
  1331.  
  1332. #token  SUFFIX_DOT
  1333.  
  1334. statement
  1335.         : (information_request)?
  1336.         | obj_name
  1337.  
  1338. ;information_request
  1339.         : QUESTION id_list ( QUESTION )*
  1340.         | id_list ( QUESTION )+
  1341.  
  1342. ;id_list
  1343.         : obj_name ( COMMA | obj_name )*
  1344.  
  1345. ;simple_class
  1346.         : <<(LA(1)==ID ? isClass(LATEXT(1)) : 1)>>? ID
  1347.  
  1348. ;global_func_id
  1349.         : <<(LA(1)==ID ? isFunction(LATEXT(1)) : 1)>>? ID
  1350.  
  1351. ;obj_name
  1352.         : <<;>> global_func_id
  1353.         | <<;>> simple_class SUFFIX_DOT
  1354.         | ID
  1355. ;
  1356. ===============================================================================
  1357. Example 1 of #lexclass
  1358. ===============================================================================
  1359. Borrowed code
  1360. -------------------------------------------------------------------------------
  1361. /*
  1362.  * Various tokens
  1363.  */
  1364. #token "[\t\ ]+"        << zzskip(); >> /* Ignore whitespace */
  1365. #token "\n"             << zzline++; zzskip(); >> /* Count lines */
  1366.  
  1367. #token "\""             << zzmode(STRINGS); zzmore(); >>
  1368. #token "'"              << zzmode(CHARACTERS); zzmore(); >>
  1369. #token "/\*"            << zzmode(COMMENT); zzskip(); >>
  1370. #token "//"             << zzmode(CPPCOMMENT); zzskip(); >>
  1371.  
  1372. /*
  1373.  * C++ String literal handling
  1374.  */
  1375. #lexclass STRINGS
  1376. #token STRING "\""      << zzmode(START); >>
  1377. #token "\\\""           << zzmore(); >>
  1378. #token "\\n"            << zzreplchar('\n'); zzmore(); >>
  1379. #token "\\r"            << zzreplchar('\r'); zzmore(); >>
  1380. #token "\\t"            << zzreplchar('\t'); zzmore(); >>
  1381. #token "\\[1-9][0-9]*"  << zzreplchar((char)strtol(zzbegexpr, NULL, 10));
  1382.                            zzmore(); >>
  1383. #token "\\0[0-7]*"      << zzreplchar((char)strtol(zzbegexpr, NULL, 8));
  1384.                            zzmore(); >>
  1385. #token "\\0x[0-9a-fA-F]*" << zzreplchar((char)strtol(zzbegexpr, NULL, 16));
  1386.                              zzmore(); >>
  1387. #token "\\~[\n\r]"      << zzmore(); >>
  1388. #token "[\n\r]"         << zzline++; zzmore(); /* Print warning */ >>
  1389. #token "~[\"\n\r\\]+"   << zzmore(); >>
  1390.  
  1391. /*
  1392.  * C++ Character literal handling
  1393.  */
  1394. #lexclass CHARACTERS
  1395. #token CHARACTER "'"    << zzmode(START); >>
  1396. #token "\\'"            << zzmore(); >>
  1397. #token "\\n"            << zzreplchar('\n'); zzmore(); >>
  1398. #token "\\r"            << zzreplchar('\r'); zzmore(); >>
  1399. #token "\\t"            << zzreplchar('\t'); zzmore(); >>
  1400. #token "\\[1-9][0-9]*"  << zzreplchar((char)strtol(zzbegexpr, NULL, 10));
  1401.                            zzmore(); >>
  1402. #token "\\0[0-7]*"      << zzreplchar((char)strtol(zzbegexpr, NULL, 8));
  1403.                            zzmore(); >>
  1404. #token "\\0x[0-9a-fA-F]*" << zzreplchar((char)strtol(zzbegexpr, NULL, 16));
  1405.                              zzmore(); >>
  1406. #token "\\~[\n\r]"      << zzmore(); >>
  1407. #token "[\n\r]"         << zzline++; zzmore(); /* Print warning */ >>
  1408. #token "~[\'\n\r\\]"    << zzmore(); >>
  1409.  
  1410. /*
  1411.  * C-style comment handling
  1412.  */
  1413. #lexclass COMMENT
  1414. #token "\*/"            << zzmode(START); zzskip(); >>
  1415. #token "~[\*]*"         << zzskip(); >>
  1416. #token "\*~[/]"         << zzskip(); >>
  1417.  
  1418. /*
  1419.  * C++-style comment handling
  1420.  */
  1421. #lexclass CPPCOMMENT
  1422. #token "[\n\r]"         << zzmode(START); zzskip(); >>
  1423. #token "~[\n\r]"        << zzskip(); >>
  1424.  
  1425. #lexclass START
  1426.  
  1427. /*
  1428.  * Assorted literals
  1429.  */
  1430. #token OCT_NUM "0[0-7]*"
  1431. #token L_OCT_NUM "0[0-7]*[Ll]"
  1432. #token INT_NUM "[1-9][0-9]*"
  1433. #token L_INT_NUM "[1-9][0-9]*[Ll]"
  1434. #token HEX_NUM "0[Xx][0-9A-Fa-f]+"
  1435. #token L_HEX_NUM "0[Xx][0-9A-Fa-f]+[Ll]"
  1436. #token FLOAT_NUM "([1-9][0-9]*{.[0-9]*} | {0}.[0-9]+) {[Ee]{[\+\-]}[0-9]+}"
  1437.  
  1438. /*
  1439.  * Identifiers
  1440.  */
  1441. #token Identifier "[_a-zA-Z][_a-zA-Z0-9]*"
  1442. ===============================================================================
  1443. Example 2: ASTs
  1444. ===============================================================================
  1445. #header <<
  1446.  
  1447. #include "charbuf.h"
  1448. #include <string.h>
  1449.  
  1450. int nextSerial;
  1451.  
  1452. #define AST_FIELDS int token; int serial; char *text;
  1453. #include "ast.h"
  1454.  
  1455. #define zzcr_ast(ast,attr,tok,astText) \
  1456.    (ast)->token=tok; \
  1457.    (ast)->text=strdup( (char *)  &(  (  (attr)->text  )  )  ); \
  1458.    nextSerial++; \
  1459.    (ast)->serial=nextSerial; \
  1460.  
  1461. #define zzd_ast(node) delete_ast(node)
  1462.  
  1463. void delete_ast (AST *node);
  1464.  
  1465. >>
  1466.  
  1467. <<
  1468.  
  1469. AST     *root=NULL;
  1470.  
  1471. void show(AST *tree) {
  1472.         if (tree->token==ID) {
  1473.           printf (" %s <#%d> ",
  1474.                 tree->text,tree->serial);}
  1475.         else {
  1476.           printf (" %s <#%d> ",
  1477.                 zztokens[tree->token],
  1478.                 tree->serial);
  1479.         };
  1480. }
  1481. void before (AST *tree) {
  1482.         printf ("(");
  1483. }
  1484. void after (AST *tree) {
  1485.         printf (")");
  1486. }
  1487.  
  1488.  
  1489. void delete_ast(AST *node) {
  1490.   printf ("\nzzd_ast called for <node #%d>\n",node->serial);
  1491.   free (node->text);
  1492.   return;
  1493. }
  1494.  
  1495. int main() {
  1496.         nextSerial=0;
  1497.         ANTLR (expr(&root),stdin);
  1498.         printf ("\n");
  1499.         zzpre_ast(root,show,before,after);
  1500.         printf ("\n");
  1501.         zzfree_ast(root);
  1502.         return 0;
  1503. }
  1504. >>
  1505.  
  1506. #token  WhiteSpace      "[\ \t]"                <<zzskip();>>
  1507. #token  ID              "[a-z A-Z]*"
  1508. #token  NEWLINE         "\n"
  1509. #token  OpenAngle       "<"
  1510. #token  CloseAngle      ">"
  1511.  
  1512. expr    : (expr0 NEWLINE)
  1513.  
  1514. ;expr0  : expr1 {"="^ expr0}
  1515. ;expr1  : expr2 ("\+"^ expr2)*
  1516. ;expr2  : expr3 ("\*"^ expr3)*
  1517. ;expr3  : ID
  1518. -------------------------------------------------------------------------------
  1519. Sample output from this program:
  1520.  
  1521. a=b=c=d
  1522. ( = <#2>  a <#1> ( = <#4>  b <#3> ( = <#6>  c <#5>  d <#7> ))) NEWLINE <#8>
  1523. zzd_ast called for <node #7>
  1524. zzd_ast called for <node #5>
  1525. zzd_ast called for <node #6>
  1526. zzd_ast called for <node #3>
  1527. zzd_ast called for <node #4>
  1528. zzd_ast called for <node #1>
  1529. zzd_ast called for <node #8>
  1530. zzd_ast called for <node #2>
  1531.  
  1532. a+b*c
  1533. ( \+ <#2>  a <#1> ( \* <#4>  b <#3>  c <#5> )) NEWLINE <#6>
  1534. zzd_ast called for <node #5>
  1535. zzd_ast called for <node #3>
  1536. zzd_ast called for <node #4>
  1537. zzd_ast called for <node #1>
  1538. zzd_ast called for <node #6>
  1539. zzd_ast called for <node #2>
  1540.  
  1541. a*b+c
  1542. ( \+ <#4> ( \* <#2>  a <#1>  b <#3> ) c <#5> ) NEWLINE <#6>
  1543. zzd_ast called for <node #3>
  1544. zzd_ast called for <node #1>
  1545. zzd_ast called for <node #5>
  1546. zzd_ast called for <node #2>
  1547. zzd_ast called for <node #6>
  1548. zzd_ast called for <node #4>
  1549. -------------------------------------------------------------------------------
  1550. Makefile (I don't know makefiles either)
  1551.  
  1552. DLG_FILE = parser.dlg
  1553. ERR_FILE = err.c
  1554. HDR_FILE = stdpccts.h
  1555. TOK_FILE = tokens.h
  1556. MOD_FILE = mode.h
  1557. K = 1
  1558. CK=2
  1559. ANTLR_H = /pccts/h
  1560. BIN = .
  1561. ANTLR = /pccts/bin/antlr
  1562. DLG = /pccts/bin/dlg
  1563. GD=-gd
  1564. GS=-gs
  1565. GX=
  1566. GK=-gk
  1567. INTER=-i
  1568. CFLAGS = -I. -I$(ANTLR_H) -ansi
  1569. AFLAGS = -fe $(ERR_FILE) -fh $(HDR_FILE) -fl $(DLG_FILE) -ft $(TOK_FILE) \
  1570.          -fm $(MOD_FILE) -k $(K) $(GS) -ck $(CK)  -gt $(GK)
  1571. DFLAGS = -C2
  1572.  
  1573. ..SUFFIXES :
  1574.  
  1575. ..SUFFIXES : .g .c .o
  1576.  
  1577. ..g:
  1578.         $(ANTLR) $(AFLAGS) $(A) $*.g
  1579.         make $*.o
  1580.         make scan.c
  1581.         make scan.o
  1582.         make err.o
  1583.         $(CC) -o $* $*.o scan.o err.o
  1584.  
  1585. scan.c : parser.dlg
  1586.         $(DLG) $(DFLAGS) $(INTER) $(D) parser.dlg scan.c
  1587. ===============================================================================
  1588. Example 3: Syntactic Predicates
  1589. ===============================================================================
  1590. Not completed.
  1591. ===============================================================================
  1592. Example 4: DLG input function
  1593. ===============================================================================
  1594. This example demonstrates the use of a DLG input function to work
  1595. around a limitation of DLG.  In this example the user wants to
  1596. recognize an exclamation mark as the first character of a line and
  1597. treat it differently from an exclamation mark elsewhere.  The
  1598. work-around is for the input function to return a non-printing
  1599. character (binary 1) when it finds an "!" in column 1.  If it reads a
  1600. genuine binary 1 in column 1 of the input text it returns a "?".
  1601.  
  1602. The parse is started by:
  1603.  
  1604.         int DLGchar (void);
  1605.         ...
  1606.         ANTLRf (expr(&root),DLGchar);
  1607.         ...
  1608. -------------------------------------------------------------------------------
  1609. #token  BANG            "!"
  1610. #token  BANG_COL1       "\01"
  1611. #token  WhiteSpace      "[\ \t]"        <<zzskip();>>
  1612. #token  ID              "[a-z A-Z]*"
  1613. #token  NEWLINE         "\n"
  1614.  
  1615. expr!   : (bang         <<printf ("\nThe ! is NOT in column 1\n");>>
  1616.            | bang1      <<printf ("\nThe ! is in column 1\n");>>
  1617.            | id         <<printf ("\nFirst token is an ID\n");>>
  1618.           )* "@"
  1619.  
  1620. ;bang!  : BANG ID NEWLINE
  1621.  
  1622. ;bang1! : BANG_COL1 ID  NEWLINE
  1623.  
  1624. ;id!    : ID  NEWLINE
  1625. ;
  1626. -------------------------------------------------------------------------------
  1627. #include <stdio.h>
  1628.  
  1629. /*
  1630.         Antlr DLG input function - See page 18 of pccts 1.00 manual
  1631. */
  1632.  
  1633. static int firstTime=1;
  1634.  
  1635. static int c;
  1636.  
  1637. int DLGchar (void) {
  1638.     if (feof(stdin)) {
  1639.         return EOF;
  1640.     };
  1641.     if (firstTime || c=='\n') {
  1642.       firstTime=0;
  1643.       c=fgetc(stdin);
  1644.       if (c==EOF) return (EOF);
  1645.       if (c=='!') return ('\001');
  1646.       if (c=='\001') return ('?');
  1647.       return (c);
  1648.     } else {
  1649.       c=fgetc(stdin);
  1650.       return (c);
  1651.     };
  1652. };
  1653. ===============================================================================
  1654. Example 5: Maintaining a Stack of DLG Modes
  1655. ===============================================================================
  1656. Contributed by David Seidel
  1657. -------------------------------------------------------------------------------
  1658. #define  MAX_MODE ????
  1659. #define  ZZMAXSTK (MAX_MODE * 2)
  1660.  
  1661. static int  zzmstk[ZZMAXSTK] = { -1 };
  1662. static int  zzmdep = 0;
  1663.  
  1664. void
  1665. #ifdef __STDC__
  1666. zzmpush( int m )
  1667. #else
  1668. zzmpush( m )
  1669. int m;
  1670. #endif
  1671. {
  1672.    if(zzmdep == ZZMAXSTK - 1)
  1673.    {  sprintf(zzebuf, "Mode stack overflow ");
  1674.       zzerr(zzebuf);
  1675.    }
  1676.    else
  1677.    {  zzmstk[zzmdep++] = zzauto;
  1678.       zzmode(m);
  1679.    }
  1680. }
  1681.  
  1682. void
  1683. zzmpop()
  1684. {
  1685.    if(zzmdep == 0)
  1686.    {  sprintf(zzebuf, "Mode stack underflow ");
  1687.       zzerr(zzebuf);
  1688.    }
  1689.    else
  1690.    {  zzmdep--;
  1691.       zzmode(zzmstk[zzmdep]);
  1692.    }
  1693. }
  1694.  
  1695.