Robust/cup/manual.html

   1 <html><head>
   2 <title>CUP User's Manual</title>
   3 </head>
   4 <body>
   5
   6 <hr>
   7 <img src="cup_logo.gif" alt="[CUP Logo Image]">
   8 <hr>
   9 <h1>CUP User's Manual</h1>
  10 <h3><a href="http://www.cc.gatech.edu/gvu/people/Faculty/Scott.E.Hudson.html">
  11 Scott E. Hudson</a><br>
  12 <a href="http://www.cc.gatech.edu/gvu/gvutop.html">
  13 Graphics Visualization and Usability Center</a><br>
  14 <a href="http://www.gatech.edu/TechHome.html">
  15 Georgia Institute of Technology</a></h3>
  16 Modified by <a href="http://www.princeton.edu/~frankf">Frank
  17 Flannery</a>, <a href="http://www.pdos.lcs.mit.edu/~cananian/">C. Scott Ananian</a>,
  18 <a href="http://www.cs.princeton.edu/~danwang">Dan Wang</a> with advice from
  19 <a href="http://www.cs.princeton.edu/~appel">Andrew W. Appel</a><br>
  20 Last updated July 1999 (v0.10j)
  21 <hr>
  22
  23 <h3>Table of Contents</h3>
  24 <dl compact>
  25   <dt> i.  <dd> <a href="#about">About CUP Version 0.10</a>
  26   <dt> 1.  <dd> <a href="#intro">Introduction and Example</a>
  27   <dt> 2.  <dd> <a href="#spec">Specification Syntax</a>
  28   <dt> 3.  <dd> <a href="#running">Running CUP</a>
  29   <dt> 4.  <dd> <a href="#parser">Customizing the Parser</a>
  30   <dt> 5.  <dd> <a href="#scanner">Scanner interface</a>
  31   <dt> 6.  <dd> <a href="#errors">Error Recovery</a>
  32   <dt> 7.  <dd> <a href="#conclusion">Conclusion</a>
  33   <dt>     <dd> <a href="#refs">References</a>
  34   <dt> A.  <dd> <a href="#appendixa">Grammar for CUP Specification Files</a>
  35   <dt> B.  <dd> <a href="#appendixb">A Very Simple Example Scanner</a>
  36   <dt> C.  <dd> <a href="#changes">Incompatibilites between CUP 0.9 and CUP 0.10</a>
  37   <dt> D.  <dd> <a href="#bugs">Bugs</a>
  38   <dt> E.  <dd> <a href="#version">Change log</a>
  39 </dl>
  40
  41 <a name=about>
  42 <h3>i. About CUP Version 0.10</h3>
  43 </a> Version
  44 0.10 of CUP adds many new changes and features over the previous releases
  45 of version 0.9.  These changes attempt to make CUP more like its
  46 predecessor, YACC.  As a result, the old 0.9 parser specifications for CUP are
  47 not compatible and a reading of <a href="#changes">appendix C</a> of the new
  48 manual will be necessary to write new specifications.  The new version,
  49 however, gives the user more power and options, making parser specifications
  50 easier to write.
  51
  52 <a name=intro>
  53 <h3>1. Introduction and Example</h3></a>
  54
  55 This manual describes the basic operation and use of the
  56 Java<a href="#trademark">(tm)</a>
  57 Based Constructor of Useful Parsers (CUP for short).
  58 CUP is a system for generating LALR parsers from simple specifications.
  59 It serves the same role as the widely used program YACC
  60 <a href="#YACCref">[1]</a> and in fact offers most of the features of YACC.
  61 However, CUP is written in Java, uses specifications including embedded
  62 Java code, and produces parsers which are implemented in Java.<p>
  63
  64 Although this manual covers all aspects of the CUP system, it is relatively
  65 brief, and assumes you have at least a little bit of knowledge of LR
  66 parsing.  A working knowledge of YACC is also very helpful in
  67 understanding how CUP specifications work.
  68 A number of compiler construction textbooks (such as
  69 <a href="#dragonbook">[2</a>,<a href="#crafting">3]</a>) cover this material,
  70 and discuss the YACC system (which is quite similar to this one) as a
  71 specific example.  In addition, Andrew Appel's <a
  72 href="http://www.cs.princeton.edu/~appel/modern/java/">Modern Compiler
  73 Implementation in Java</a> textbook <a href="#modernjava">[4]</a> uses
  74 and describes CUP in the context of compiler construction.
  75 <p>
  76
  77 Using CUP involves creating a simple specification based on the
  78 grammar for which a parser is needed, along with construction of a
  79 scanner capable of breaking characters up into meaningful tokens (such
  80 as keywords, numbers, and special symbols).<p>
  81
  82 As a simple example, consider a
  83 system for evaluating simple arithmetic expressions over integers.
  84 This system would read expressions from standard input (each terminated
  85 with a semicolon), evaluate them, and print the result on standard output.
  86 A grammar for the input to such a system might look like: <pre>
  87   expr_list ::= expr_list expr_part | expr_part
  88   expr_part ::= expr ';'
  89   expr      ::= expr '+' expr | expr '-' expr | expr '*' expr
  90               | expr '/' expr | expr '%' expr | '(' expr ')'
  91               | '-' expr | number
  92 </pre>
  93 To specify a parser based on this grammar, our first step is to identify and
  94 name the set of terminal symbols that will appear on input, and the set of
  95 non-terminal symbols.  In this case, the non-terminals are:
  96
  97 <pre><tt>  expr_list, expr_part </tt> and <tt> expr </tt>.</pre>
  98
  99 For terminal names we might choose:
 100
 101 <pre><tt>  SEMI, PLUS, MINUS, TIMES, DIVIDE, MOD, NUMBER, LPAREN,</tt>
 102 and <tt>RPAREN</tt></pre>
 103
 104 The experienced user will note a problem with the above grammar.  It is
 105 ambiguous.  An ambiguous grammar is a grammar which, given a certain
 106 input, can reduce the parts of the input in two different ways such as
 107 to give two different answers.  Take the above grammar, for
 108 example. given the following input: <br>
 109 <tt>3 + 4 * 6</tt><br>
 110 The grammar can either evaluate the <tt>3 + 4</tt> and then multiply
 111 seven by six, or it can evaluate <tt>4 * 6</tt> and then add three.
 112 Older versions of CUP forced the user to write unambiguous grammars, but
 113 now there is a construct allowing the user to specify precedences and
 114 associativities for terminals.  This means that the above ambiguous
 115 grammar can be used, after specifying precedences and associativities.
 116 There is more explanation later.
 117
 118 Based on these namings we can construct a small CUP specification
 119 as follows:<br>
 120 <hr>
 121 <pre><tt>// CUP specification for a simple expression evaluator (no actions)
 122
 123 import java_cup.runtime.*;
 124
 125 /* Preliminaries to set up and use the scanner.  */
 126 init with {: scanner.init();              :};
 127 scan with {: return scanner.next_token(); :};
 128
 129 /* Terminals (tokens returned by the scanner). */
 130 terminal            SEMI, PLUS, MINUS, TIMES, DIVIDE, MOD;
 131 terminal            UMINUS, LPAREN, RPAREN;
 132 terminal Integer    NUMBER;
 133
 134 /* Non terminals */
 135 non terminal            expr_list, expr_part;
 136 non terminal Integer    expr, term, factor;
 137
 138 /* Precedences */
 139 precedence left PLUS, MINUS;
 140 precedence left TIMES, DIVIDE, MOD;
 141 precedence left UMINUS;
 142
 143 /* The grammar */
 144 expr_list ::= expr_list expr_part |
 145               expr_part;
 146 expr_part ::= expr SEMI;
 147 expr      ::= expr PLUS expr
 148             | expr MINUS expr
 149             | expr TIMES expr
 150             | expr DIVIDE expr
 151             | expr MOD expr
 152             | MINUS expr %prec UMINUS
 153             | LPAREN expr RPAREN
 154             | NUMBER
 155             ;
 156 </tt></pre>
 157 <hr><br>
 158 We will consider each part of the specification syntax in detail later.
 159 However, here we can quickly see that the specification contains four
 160 main parts.  The first part provides preliminary and miscellaneous declarations
 161 to specify how the parser is to be generated, and supply parts of the
 162 runtime code.  In this case we indicate that the <tt>java_cup.runtime</tt>
 163 classes should be imported, then supply a small bit of initialization code,
 164 and some code for invoking the scanner to retrieve the next input token.
 165 The second part of the specification declares terminals and non-terminals,
 166 and associates object classes with each.  In this case, the terminals
 167 are declared as either with no type, or of type
 168 <tt>Integer</tt>.  The specified type of the
 169 terminal or non-terminal is the type of the value of those terminals or
 170 non-terminals.  If no type is specified, the terminal or non-terminal
 171 carries no value.  Here, no type indicates that these
 172 terminals and non-terminals hold no value.
 173 The third part specifies the precedence and
 174 associativity of terminals.  The last precedence declaration give its
 175 terminals the highest precedence. The final
 176 part of the specification contains the grammar.<p>
 177
 178
 179 To produce a parser from this specification we use the CUP generator.
 180 If this specification were stored in a file <tt>parser.cup</tt>, then
 181 (on a Unix system at least) we might invoke CUP using a command like:
 182 <pre><tt> java java_cup.Main &lt; parser.cup</tt> </pre>
 183 or (starting with CUP 0.10k):
 184 <pre><tt> java java_cup.Main parser.cup</tt> </pre>
 185 The system will produce two Java source files containing
 186 parts of the generated parser: <tt>sym.java</tt> and <tt>parser.java</tt>
 187 (these names can be changed with command-line options; see
 188 <A HREF="#running">below</a>).
 189 As you might expect, these two files contain declarations for the classes
 190 <tt>sym</tt> and <tt>parser</tt>. The <tt>sym</tt> class contains a series of
 191 constant declarations, one for each terminal symbol.  This is typically used
 192 by the scanner to refer to symbols (e.g. with code such as
 193 "<tt>return new Symbol(sym.SEMI);</tt>" ).  The <tt>parser</tt> class
 194 implements the parser itself.<p>
 195
 196 The specification above, while constructing a full parser, does not perform
 197 any semantic actions &emdash; it will only indicate success or failure of a parse.
 198 To calculate and print values of each expression, we must embed Java
 199 code within the parser to carry out actions at various points.  In CUP,
 200 actions are contained in <i>code strings</i> which are surrounded by delimiters
 201 of the form <tt>{:</tt> and <tt>:}</tt> (we can see examples of this in the
 202 <tt>init with</tt> and <tt>scan with</tt> clauses above).  In general, the
 203 system records all characters within the delimiters, but does not try to check
 204 that it contains valid Java code.<p>
 205
 206 A more complete CUP specification for our example system (with actions
 207 embedded at various points in the grammar) is shown below:<br>
 208 <hr>
 209 <pre><tt>// CUP specification for a simple expression evaluator (w/ actions)
 210
 211 import java_cup.runtime.*;
 212
 213 /* Preliminaries to set up and use the scanner.  */
 214 init with {: scanner.init();              :};
 215 scan with {: return scanner.next_token(); :};
 216
 217 /* Terminals (tokens returned by the scanner). */
 218 terminal           SEMI, PLUS, MINUS, TIMES, DIVIDE, MOD;
 219 terminal           UMINUS, LPAREN, RPAREN;
 220 terminal Integer   NUMBER;
 221
 222 /* Non-terminals */
 223 non terminal            expr_list, expr_part;
 224 non terminal Integer    expr;
 225
 226 /* Precedences */
 227 precedence left PLUS, MINUS;
 228 precedence left TIMES, DIVIDE, MOD;
 229 precedence left UMINUS;
 230
 231 /* The grammar */
 232 expr_list ::= expr_list expr_part
 233               |
 234               expr_part;
 235
 236 expr_part ::= expr:e
 237               {: System.out.println("= " + e); :}
 238               SEMI
 239               ;
 240
 241 expr      ::= expr:e1 PLUS expr:e2
 242               {: RESULT = new Integer(e1.intValue() + e2.intValue()); :}
 243               |
 244               expr:e1 MINUS expr:e2
 245               {: RESULT = new Integer(e1.intValue() - e2.intValue()); :}
 246               |
 247               expr:e1 TIMES expr:e2
 248               {: RESULT = new Integer(e1.intValue() * e2.intValue()); :}
 249               |
 250               expr:e1 DIVIDE expr:e2
 251               {: RESULT = new Integer(e1.intValue() / e2.intValue()); :}
 252               |
 253               expr:e1 MOD expr:e2
 254               {: RESULT = new Integer(e1.intValue() % e2.intValue()); :}
 255               |
 256               NUMBER:n
 257               {: RESULT = n; :}
 258               |
 259               MINUS expr:e
 260               {: RESULT = new Integer(0 - e.intValue()); :}
 261               %prec UMINUS
 262               |
 263               LPAREN expr:e RPAREN
 264               {: RESULT = e; :}
 265               ;
 266 </tt></pre>
 267 <hr><br>
 268 Here we can see several changes.  Most importantly, code to be executed at
 269 various points in the parse is included inside code strings delimited by
 270 <tt>{:</tt> and <tt>:}</tt>.  In addition, labels have been placed on various
 271 symbols in the right hand side of productions.  For example in:<br>
 272 <pre>  expr:e1 PLUS expr:e2
 273         {: RESULT = new Integer(e1.intValue() + e2.intValue()); :}
 274 </pre>
 275 <a name="RES_part">
 276 the first non-terminal <tt>expr</tt> has been labeled with <tt>e1</tt>, and
 277 the second with <tt>e2</tt>.  The left hand side value
 278 of each production is always implicitly labeled as <tt>RESULT</tt>.<p>
 279
 280 Each symbol appearing in a production is represented at runtime by an
 281 object of type <tt>Symbol</tt> on the parse stack.  The labels refer to
 282 the instance variable <tt>value</tt> in those objects.  In the
 283 expression <tt>expr:e1 PLUS expr:e2</tt>, <tt>e1</tt> and <tt>e2</tt>
 284 refer to objects of type Integer.  These objects are in the value fields
 285 of the objects of type <tt>Symbol</tt> representing those non-terminals
 286 on the parse stack.  <tt>RESULT</tt> is of type <tt>Integer</tt> as
 287 well, since the resulting non-terminal <tt>expr</tt> was declared as of
 288 type <tt>Integer</tt>.  This object becomes the <tt>value</tt> instance
 289 variable of a new <tt>Symbol</tt> object.<p>
 290
 291 For each label, two more variables accessible to the user are declared.
 292 A left and right value labels are passed to the code string, so that the
 293 user can find out where the left and right side of each terminal or
 294 non-terminal is in the input stream.  The name of these variables is the
 295 label name, plus <tt>left</tt> or <tt>right</tt>.  for example, given
 296 the right hand side of a production <tt>expr:e1 PLUS expr:e2</tt> the
 297 user could not only access variables <tt>e1</tt> and <tt>e2</tt>, but
 298 also <tt>e1left, e1right, e2left</tt> and <tt>e2right</tt>.  these
 299 variables are of type <tt>int</tt>.<p>
 300
 301 <a name="lex_part">
 302
 303 The final step in creating a working parser is to create a <i>scanner</i> (also
 304 known as a <i>lexical analyzer</i> or simply a <i>lexer</i>).  This routine is
 305 responsible for reading individual characters, removing things things like
 306 white space and comments, recognizing which terminal symbols from the
 307 grammar each group of characters represents, then returning Symbol objects
 308 representing these symbols to the parser.
 309 The terminals will be retrieved with a call to the
 310 scanner function.  In the example, the parser will call
 311 <tt>scanner.next_token()</tt>. The scanner should return objects of
 312 type <tt>java_cup.runtime.Symbol</tt>.  This type is very different than
 313 older versions of CUP's <tt>java_cup.runtime.symbol</tt>.  These Symbol
 314 objects contains the instance variable <tt>value</tt> of type Object,
 315 which should be
 316 set by the lexer.  This variable refers to the value of that symbol, and
 317 the type of object in value should be of the same type as declared in
 318 the <tt>terminal</tt> and <tt>non terminal</tt> declarations.  In the
 319 above example, if the lexer wished to pass a NUMBER token, it should
 320 create a <tt>Symbol</tt> with the <tt>value</tt> instance variable
 321 filled with an object of type <tt>Integer</tt>.  <code>Symbol</code>
 322 objects corresponding to terminals and non-terminals with no value
 323 have a null value field.<p>
 324
 325 The code contained in the <tt>init with</tt> clause of the specification
 326 will be executed before any tokens are requested.  Each token will be
 327 requested using whatever code is found in the <tt>scan with</tt> clause.
 328 Beyond this, the exact form the scanner takes is up to you; however
 329 note that each call to the scanner function should return a new
 330 instance of <code>java_cup.runtime.Symbol</code> (or a subclass).
 331 These symbol objects are annotated with parser information and pushed
 332 onto a stack; reusing objects will result in the parser annotations
 333 being scrambled.  As of CUP 0.10j, <code>Symbol</code> reuse should be
 334 detected if it occurs; the parser will throw an <code>Error</code>
 335 telling you to fix your scanner.<p>
 336
 337 In the <a href="#spec">next section</a> a more detailed and formal
 338 explanation of all parts of a CUP specification will be given.
 339 <a href="#running">Section 3</a> describes options for running the
 340 CUP system.  <a href="#parser">Section 4</a> discusses the details
 341 of how to customize a CUP parser, while <a href="#scanner">section 5</a>
 342 discusses the scanner interface added in CUP 0.10j. <a href="#errors">Section
 343  6</a> considers error recovery.  Finally, <a href="#conclusion">Section 7</a>
 344 provides a conclusion.
 345
 346 <a name="spec">
 347 <h3>2. Specification Syntax</h3></a>
 348 Now that we have seen a small example, we present a complete description of all
 349 parts of a CUP specification.  A specification has four sections with
 350 a total of eight specific parts (however, most of these are optional).
 351 A specification consists of:
 352 <ul>
 353 <li> <a href="#package_spec">package and import specifications</a>,
 354 <li> <a href="#code_part">user code components</a>,
 355 <li> <a href="#symbol_list">symbol (terminal and non-terminal) lists</a>,
 356 <li> <a href="#precedence">precedence declarations</a>, and
 357 <li> <a href="#production_list">the grammar</a>.
 358 </ul>
 359 Each of these parts must appear in the order presented here.  (A complete
 360 grammar for the specification language is given in
 361 <a href="#appendixa">Appendix A</a>.)  The particulars of each part of
 362 the specification are described in the subsections below.<p>
 363
 364 <h5><a name="package_spec">Package and Import Specifications</a></h5>
 365
 366 A specification begins with optional <tt>package</tt> and <tt>import</tt>
 367 declarations.  These have the same syntax, and play the same
 368 role, as the package and import declarations found in a normal Java program.
 369 A package declaration is of the form:
 370
 371 <pre><tt>    package <i>name</i>;</tt></pre>
 372
 373 where name <tt><i>name</i></tt> is a Java package identifier, possibly in
 374 several parts separated by ".".  In general, CUP employs Java lexical
 375 conventions.  So for example, both styles of Java comments are supported,
 376 and identifiers are constructed beginning with a letter, dollar
 377 sign ($), or underscore (_), which can then be followed by zero or more
 378 letters, numbers, dollar signs, and underscores.<p>
 379
 380 After an optional <tt>package</tt> declaration, there can be zero or more
 381 <tt>import</tt> declarations. As in a Java program these have the form:
 382
 383 <pre><tt>    import <i>package_name.class_name</i>;</tt>
 384 </pre>
 385 or
 386 <pre><tt>    import <i>package_name</i>.*;</tt>
 387 </pre>
 388
 389 The package declaration indicates what package the <tt>sym</tt> and
 390 <tt>parser</tt> classes that are generated by the system will be in.
 391 Any import declarations that appear in the specification will also appear
 392 in the source file for the <tt>parser</tt> class allowing various names from
 393 that package to be used directly in user supplied action code.
 394
 395 <h5><a name="code_part">User Code Components</a></h5>
 396
 397 Following the optional <tt>package</tt> and <tt>import</tt> declarations
 398 are a series of optional declarations that allow user code to be included
 399 as part of the generated parser (see <a href="#parser">Section 4</a> for a
 400 full description of how the parser uses this code).  As a part of the parser
 401 file, a separate non-public class to contain all embedded user actions is
 402 produced.  The first <tt>action code</tt> declaration section allows code to
 403 be included in this class.  Routines and variables for use by the code
 404 embedded in the grammar would normally be placed in this section (a typical
 405 example might be symbol table manipulation routines).  This declaration takes
 406 the form:
 407
 408 <pre><tt>    action code {: ... :};</tt>
 409 </pre>
 410
 411 where <tt>{: ... :}</tt> is a code string whose contents will be placed
 412 directly within the <tt>action class</tt> class declaration.<p>
 413
 414 After the <tt>action code</tt> declaration is an optional
 415 <tt>parser code</tt> declaration.  This declaration allows methods and
 416 variable to be placed directly within the generated parser class.
 417 Although this is less common, it can be helpful when customizing the
 418 parser &emdash; it is possible for example, to include scanning methods inside
 419 the parser and/or override the default error reporting routines.  This
 420 declaration is very similar to the <tt>action code</tt> declaration and
 421 takes the form:
 422
 423 <pre><tt>    parser code {: ... :};</tt>
 424 </pre>
 425
 426 Again, code from the code string is placed directly into the generated parser
 427 class definition.<p>
 428
 429 Next in the specification is the optional <tt>init</tt> declaration
 430 which has the form:
 431
 432 <pre><tt>    init with {: ... :};</tt></pre>
 433
 434 This declaration provides code that will be executed by the parser
 435 before it asks for the first token.  Typically, this is used to initialize
 436 the scanner as well as various tables and other data structures that might
 437 be needed by semantic actions.  In this case, the code given in the code
 438 string forms the body of a <tt>void</tt> method inside the <tt>parser</tt>
 439 class.<p>
 440
 441 The final (optional) user code section of the specification indicates how
 442 the parser should ask for the next token from the scanner.  This has the
 443 form:
 444
 445 <pre><tt>    scan with {: ... :};</tt></pre>
 446
 447 As with the <tt>init</tt> clause, the contents of the code string forms
 448 the body of a method in the generated parser.  However, in this case
 449 the method returns an object of type <tt>java_cup.runtime.Symbol</tt>.
 450 Consequently the code found in the <tt>scan with</tt> clause should
 451 return such a value.  See <a href="#scanner">section 5</a> for
 452 information on the default behavior if the <code>scan with</code>
 453 section is omitted.<p>
 454
 455 As of CUP 0.10j the action code, parser code, init code, and scan with
 456 sections may appear in any order. They must, however, precede the
 457 symbol lists.<p>
 458
 459 <h5><a name="symbol_list">Symbol Lists</a></h5>
 460
 461 Following user supplied code comes the first required part of the
 462 specification: the symbol lists.  These declarations are responsible
 463 for naming and supplying a type for each terminal and non-terminal
 464 symbol that appears in the grammar.  As indicated above, each terminal
 465 and non-terminal symbol is represented at runtime with a <tt>Symbol</tt>
 466 object.  In
 467 the case of terminals, these are returned by the scanner and placed on
 468 the parse stack.  The lexer should put the value of the terminal in the
 469 <tt>value</tt> instance variable.
 470 In the case of non-terminals these replace a series
 471 of <tt>Symbol</tt> objects on the parse stack whenever the right hand side of
 472 some production is recognized.  In order to tell the parser which object
 473 types should be used for which symbol, <tt>terminal</tt> and
 474 <tt>non terminal</tt> declarations are used.  These take the forms:
 475
 476 <pre><tt>    terminal <i>classname</i> <i>name1, name2,</i> ...;</tt>
 477 <tt>    non terminal <i>classname</i> <i>name1, name2,</i> ...;</tt>
 478 <tt>    terminal <i>name1, name2,</i> ...;</tt>
 479 </pre>
 480
 481 and
 482
 483 <pre><tt>    non terminal <i>name1, name2,</i> ...;</tt>
 484 </pre>
 485
 486 where <tt><i>classname</i></tt> can be a multiple part name separated with
 487 "."s.  The
 488 <tt><i>classname</i></tt> specified represents the type of the value of
 489 that terminal or non-terminal.  When accessing these values through
 490 labels, the users uses the type declared. the <tt><i>classname</i></tt>
 491 can be of any type.  If no <tt><i>classname</i></tt> is given, then the
 492 terminal or non-terminal holds no value.  a label referring to such a
 493 symbol with have a null value. As of CUP 0.10j, you may specify
 494 non-terminals the declaration "<code>nonterminal</code>" (note, no
 495 space) as well as the original "<code>non terminal</code>" spelling.<p>
 496
 497 Names of terminals and non-terminals cannot be CUP reserved words;
 498 these include "code", "action", "parser", "terminal", "non",
 499 "nonterminal", "init", "scan", "with", "start", "precedence", "left",
 500 "right", "nonassoc", "import", and "package".<p>
 501
 502 <h5><a name="precedence">Precedence and Associativity declarations</a></h5>
 503
 504 The third section, which is optional, specifies the precedences and
 505 associativity of terminals.  This is useful for parsing with ambiguous
 506 grammars, as done in the example above. There are three type of
 507 precedence/associativity declarations:
 508 <pre><tt>
 509         precedence left     <i>terminal</i>[, <i>terminal</i>...];
 510         precedence right    <i>terminal</i>[, <i>terminal</i>...];
 511         precedence nonassoc <i>terminal</i>[, <i>terminal</i>...];
 512 </tt></pre>
 513
 514 The comma separated list indicates that those terminals should have the
 515 associativity specified at that precedence level and the precedence of
 516 that declaration.  The order of precedence, from highest to lowest, is
 517 bottom to top.  Hence, this declares that multiplication and division have
 518 higher precedence than addition and subtraction:
 519 <pre><tt>
 520         precedence left  ADD, SUBTRACT;
 521         precedence left  TIMES, DIVIDE;
 522 </tt></pre>
 523 Precedence resolves shift reduce problems.  For example, given the input
 524 to the above example parser <tt>3 + 4 * 8</tt>, the parser doesn't know
 525 whether to reduce <tt>3 + 4</tt> or shift the '*' onto the stack.
 526 However, since '*' has a higher precedence than '+', it will be shifted
 527 and the multiplication will be performed before the addition.<p>
 528
 529 CUP assigns each one of its terminals a precedence according to these
 530 declarations.  Any terminals not in this declaration have lowest
 531 precedence.  CUP also assigns each of its productions a precedence.
 532 That precedence is equal to the precedence of the last terminal in that
 533 production.  If the production has no terminals, then it has lowest
 534 precedence. For example, <tt>expr ::= expr TIMES expr</tt> would have
 535 the same precedence as <tt>TIMES</tt>.  When there is a shift/reduce
 536 conflict, the parser determines whether the terminal to be shifted has a
 537 higher precedence, or if the production to reduce by does.  If the
 538 terminal has higher precedence, it it shifted, if the production has
 539 higher precedence, a reduce is performed.  If they have equal
 540 precedence, associativity of the terminal determine what happens.<p>
 541
 542 An associativity is assigned to each terminal used in the
 543 precedence/associativity declarations.  The three associativities are
 544 <tt>left, right</tt> and <tt>nonassoc</tt>  Associativities are also
 545 used to resolve shift/reduce conflicts, but only in the case of equal
 546 precedences.  If the associativity of the terminal that can be shifted
 547 is <tt>left</tt>, then a reduce is performed.  This means, if the input
 548 is a string of additions, like <tt>3 + 4 + 5 + 6 + 7</tt>, the parser
 549 will <i>always</i> reduce them from left to right, in this case,
 550 starting with <tt>3 + 4</tt>.  If the associativity of the terminal is
 551 <tt>right</tt>, it is shifted onto the stack.  hence, the reductions
 552 will take place from right to left.  So, if PLUS were declared with
 553 associativity of <tt>right</tt>, the <tt>6 + 7</tt> would be reduced
 554 first in the above string.  If a terminal is declared as
 555 <tt>nonassoc</tt>, then two consecutive occurrences of equal precedence
 556 non-associative terminals generates an error.  This is useful for
 557 comparison operations.  For example, if the input string is
 558 <tt>6 == 7 == 8 == 9</tt>, the parser should generate an error.  If '=='
 559 is declared as <tt>nonassoc</tt> then an error will be generated. <p>
 560
 561 All terminals not used in the precedence/associativity declarations are
 562 treated as lowest precedence.  If a shift/reduce error results,
 563 involving two such terminals, it cannot be resolved, as the above
 564 conflicts are, so it will be reported.<p>
 565
 566 <h5><a name="production_list">The Grammar</a></h5>
 567
 568 The final section of a CUP declaration provides the grammar.  This
 569 section optionally starts with a declaration of the form:
 570
 571 <pre><tt>    start with <i>non-terminal</i>;</tt>
 572 </pre>
 573
 574 This indicates which non-terminal is the <i>start</i> or <i>goal</i>
 575 non-terminal for parsing.  If a start non-terminal is not explicitly
 576 declared, then the non-terminal on the left hand side of the first
 577 production will be used.  At the end of a successful parse, CUP returns
 578 an object of type <tt>java_cup.runtime.Symbol</tt>.  This
 579 <tt>Symbol</tt>'s value instance variable contains the final reduction
 580 result.<p>
 581
 582 The grammar itself follows the optional <tt>start</tt> declaration.  Each
 583 production in the grammar has a left hand side non-terminal followed by
 584 the symbol "<tt>::=</tt>", which is then followed by a series of zero or more
 585 actions, terminal, or non-terminal
 586 symbols, followed by an optional contextual precedence assignment,
 587 and terminated with a semicolon (;).<p>
 588
 589 <a name="label_part">
 590
 591 Each symbol on the right hand side can optionally be labeled with a name.
 592 Label names appear after the symbol name separated by a colon (:).  Label
 593 names must be unique within the production, and can be used within action
 594 code to refer to the value of the symbol.  Along with the label, two
 595 more variables are created, which are the label plus <tt>left</tt> and
 596 the label plus <tt>right</tt>.  These are <tt>int</tt> values that
 597 contain the right and left locations of what the terminal or
 598 non-terminal covers in the input file.  These values must be properly
 599 initialized in the terminals by the lexer. The left and right values
 600 then propagate to non-terminals to which productions reduce.<p>
 601
 602 If there are several productions for the same non-terminal they may be
 603 declared together.  In this case the productions start with the non-terminal
 604 and "<tt>::=</tt>".  This is followed by multiple right hand sides each
 605 separated by a bar (|).  The full set of productions is then terminated by a
 606 semicolon.<p>
 607
 608 Actions appear in the right hand side as code strings (e.g., Java code inside
 609 <tt>{:</tt> ... <tt>:}</tt> delimiters).  These are executed by the parser
 610 at the point when the portion of the production to the left of the
 611 action has been recognized.  (Note that the scanner will have returned the
 612 token one past the point of the action since the parser needs this extra
 613 <i>lookahead</i> token for recognition.)<p>
 614
 615 <a name="cpp">
 616
 617 Contextual precedence assignments follow all the symbols and actions of
 618 the right hand side of the production whose precedence it is assigning.
 619 Contextual precedence assignment allows a production to be assigned a
 620 precedence not based on the last terminal in it.  A good example is
 621 shown in the above sample parser specification:
 622
 623 <pre><tt>
 624         precedence left PLUS, MINUS;
 625         precedence left TIMES, DIVIDE, MOD;
 626         precedence left UMINUS;
 627
 628         expr ::=  MINUS expr:e
 629                   {: RESULT = new Integer(0 - e.intValue()); :}
 630                   %prec UMINUS
 631 </tt></pre>
 632
 633 Here, there production is declared as having the precedence of UMINUS.
 634 Hence, the parser can give the MINUS sign two different precedences,
 635 depending on whether it is a unary minus or a subtraction operation.
 636
 637 <a name="running">
 638 <h3>3. Running CUP</h3></a>
 639
 640 As mentioned above, CUP is written in Java.  To invoke it, one needs
 641 to use the Java interpreter to invoke the static method
 642 <tt>java_cup.Main()</tt>, passing an array of strings containing options.
 643 Assuming a Unix machine, the simplest way to do this is typically to invoke it
 644 directly from the command line with a command such as:
 645
 646 <pre><tt>    java java_cup.Main <i>options</i> &lt; <i>inputfile</i></tt></pre>
 647
 648 Once running, CUP expects to find a specification file on standard input
 649 and produces two Java source files as output. Starting with CUP 0.10k,
 650 the final command-line argument may be a filename, in which case the
 651 specification will be read from that file instead of from standard input.<p>
 652
 653 In addition to the specification file, CUP's behavior can also be changed
 654 by passing various options to it.  Legal options are documented in
 655 <code>Main.java</code> and include:
 656 <dl>
 657   <dt><tt>-package</tt> <i>name</i>
 658   <dd>Specify that the <tt>parser</tt> and <tt>sym</tt> classes are to be
 659        placed in the named package.  By default, no package specification
 660        is put in the generated code (hence the classes default to the special
 661        "unnamed" package).
 662
 663   <dt><tt>-parser</tt> <i>name</i>
 664   <dd>Output parser and action code into a file (and class) with the given
 665       name instead of the default of "<tt>parser</tt>".
 666
 667   <dt><tt>-symbols</tt> <i>name</i>
 668   <dd>Output the symbol constant code into a class with the given
 669       name instead of the default of "<tt>sym</tt>".
 670
 671   <dt><tt>-interface</tt>
 672   <dd>Outputs the symbol constant code as an <code>interface</code>
 673       rather than as a <code>class</code>.
 674
 675   <dt><tt>-nonterms</tt>
 676   <dd>Place constants for non-terminals into the  symbol constant class.
 677       The parser does not need these symbol constants, so they are not normally
 678       output.  However, it can be very helpful to refer to these constants
 679       when debugging a generated parser.
 680
 681   <dt><tt>-expect</tt> <i>number</i>
 682   <dd>During parser construction the system may detect that an ambiguous
 683       situation would occur at runtime.  This is called a <i>conflict</i>.
 684       In general, the parser may be unable to decide whether to <i>shift</i>
 685       (read another symbol) or <i>reduce</i> (replace the recognized right
 686       hand side of a production with its left hand side).  This is called a
 687       <i>shift/reduce conflict</i>.  Similarly, the parser may not be able
 688       to decide between reduction with two different productions.  This is
 689       called a <i>reduce/reduce conflict</i>.  Normally, if one or more of
 690       these conflicts occur, parser generation is aborted.  However, in
 691       certain carefully considered cases it may be advantageous to
 692       arbitrarily break such a conflict.  In this case CUP uses YACC
 693       convention and resolves shift/reduce conflicts by shifting, and
 694       reduce/reduce conflicts using the "highest priority" production (the
 695       one declared first in the specification).  In order to enable automatic
 696       breaking of conflicts the <tt>-expect</tt> option must be given
 697       indicating exactly how many conflicts are expected.  Conflicts
 698       resolved by precedences and associativities are not reported.
 699
 700   <dt><tt>-compact_red</tt>
 701   <dd>Including this option enables a table compaction optimization involving
 702       reductions.  In particular, it allows the most common reduce entry in
 703       each row of the parse action table to be used as the default for that
 704       row.  This typically saves considerable room in the tables, which can
 705       grow to be very large.  This optimization has the effect of replacing
 706       all error entries in a row with the default reduce entry.  While this
 707       may sound dangerous, if not down right incorrect, it turns out that this
 708       does not affect the correctness of the parser.  In particular, some
 709       changes of this type are inherent in LALR parsers (when compared to
 710       canonical LR parsers), and the resulting parsers will still never
 711       read past the first token at which the error could be detected.
 712       The parser can, however, make extra erroneous reduces before detecting
 713       the error, so this can degrade the parser's ability to do
 714       <a href="#errors">error recovery</a>.
 715       (Refer to reference [2] pp. 244-247 or reference [3] pp. 190-194 for a
 716       complete explanation of this compaction technique.) <br><br>
 717
 718       This option is typically used to work-around the java bytecode
 719       limitations on table initialization code sizes.  However, CUP
 720       0.10h introduced a string-encoding for the parser tables which
 721       is not subject to the standard method-size limitations.
 722       Consequently, use of this option should no longer be required
 723       for large grammars.
 724
 725   <dt><tt>-nowarn</tt>
 726   <dd>This options causes all warning messages (as opposed to error messages)
 727       produced by the system to be suppressed.
 728
 729   <dt><tt>-nosummary</tt>
 730   <dd>Normally, the system prints a summary listing such things as the
 731       number of terminals, non-terminals, parse states, etc. at the end of
 732       its run.  This option suppresses that summary.
 733
 734   <dt><tt>-progress</tt>
 735   <dd>This option causes the system to print short messages indicating its
 736       progress through various parts of the parser generation process.
 737
 738   <dt><tt>-dump_grammar</tt>
 739   <dt><tt>-dump_states</tt>
 740   <dt><tt>-dump_tables</tt>
 741   <dt><tt>-dump</tt>
 742   <dd> These options cause the system to produce a human readable dump of
 743        the grammar, the constructed parse states (often needed to resolve
 744        parse conflicts), and the parse tables (rarely needed), respectively.
 745        The <tt>-dump</tt> option can be used to produce all of these dumps.
 746
 747   <dt><tt>-time</tt>
 748   <dd>This option adds detailed timing statistics to the normal summary of
 749       results.  This is normally of great interest only to maintainers of
 750       the system itself.
 751
 752   <dt><tt>-debug</tt>
 753   <dd>This option produces voluminous internal debugging information about
 754       the system as it runs.  This is normally of interest only to maintainers
 755       of the system itself.
 756
 757   <dt><tt>-nopositions</tt>
 758   <dd>This option keeps CUP from generating code to propagate the left
 759       and right hand values of terminals to non-terminals, and then from
 760       non-terminals to other terminals.  If the left and right values aren't
 761       going to be used by the parser, then it will save some runtime
 762       computation to not generate these position propagations.  This option
 763       also keeps the left and right label variables from being generated, so
 764       any reference to these will cause an error.
 765
 766   <dt><tt>-noscanner</tt>
 767   <dd>CUP 0.10j introduced <a href="#scanner">improved scanner
 768   integration</a> and a new interface,
 769   <code>java_cup.runtime.Scanner</code>.  By default, the
 770   generated parser refers to this interface, which means you cannot
 771   use these parsers with CUP runtimes older than 0.10j.  If your
 772   parser does not use the new scanner integration features, then you
 773   may specify the <code>-noscanner</code> option to suppress the
 774   <code>java_cup.runtime.Scanner</code> references and allow
 775   compatibility with old runtimes.  Not many people should have reason
 776   to do this.
 777
 778   <dt><tt>-version</tt>
 779   <dd>Invoking CUP with the <code>-version</code> flag will cause it
 780   to print out the working version of CUP and halt.  This allows
 781   automated CUP version checking for Makefiles, install scripts and
 782   other applications which may require it.
 783 </dl>
 784
 785 <a name="parser">
 786 <h3>4. Customizing the Parser</h3></a>
 787
 788 Each generated parser consists of three generated classes.  The
 789 <tt>sym</tt> class (which can be renamed using the <tt>-symbols</tt>
 790 option) simply contains a series of <tt>int</tt> constants,
 791 one for each terminal.  Non-terminals are also included if the <tt>-nonterms</tt>
 792 option is given.  The source file for the <tt>parser</tt> class (which can
 793 be renamed using the <tt>-parser</tt> option) actually contains two
 794 class definitions, the public <tt>parser</tt> class that implements the
 795 actual parser, and another non-public class (called <tt>CUP$action</tt>) which
 796 encapsulates all user actions contained in the grammar, as well as code from
 797 the <tt>action code</tt> declaration.  In addition to user supplied code, this
 798 class contains one method: <tt>CUP$do_action</tt> which consists of a large
 799 switch statement for selecting and executing various fragments of user
 800 supplied action code.  In general, all names beginning with the prefix of
 801 <tt>CUP$</tt> are reserved for internal uses by CUP generated code. <p>
 802
 803 The <tt>parser</tt> class contains the actual generated parser.  It is
 804 a subclass of <tt>java_cup.runtime.lr_parser</tt> which implements a
 805 general table driven framework for an LR parser.  The generated <tt>parser</tt>
 806 class provides a series of tables for use by the general framework.
 807 Three tables are provided:
 808 <dl compact>
 809 <dt>the production table
 810 <dd>provides the symbol number of the left hand side non-terminal, along with
 811     the length of the right hand side, for each production in the grammar,
 812 <dt>the action table
 813 <dd>indicates what action (shift, reduce, or error) is to be taken on each
 814     lookahead symbol when encountered in each state, and
 815 <dt>the reduce-goto table
 816 <dd>indicates which state to shift to after reduces (under each non-terminal
 817 from each state).
 818 </dl>
 819 (Note that the action and reduce-goto tables are not stored as simple arrays,
 820 but use a compacted "list" structure to save a significant amount of space.
 821 See comments the runtime system source code for details.)<p>
 822
 823 Beyond the parse tables, generated (or inherited) code provides a series
 824 of methods that can be used to customize the generated parser.  Some of these
 825 methods are supplied by code found in part of the specification and can
 826 be customized directly in that fashion.  The others are provided by the
 827 <tt>lr_parser</tt> base class and can be overridden with new versions (via
 828 the <tt>parser code</tt> declaration) to customize the system.  Methods
 829 available for customization include:
 830 <dl compact>
 831 <dt><tt>public void user_init()</tt>
 832 <dd>This method is called by the parser prior to asking for the first token
 833     from the scanner.  The body of this method contains the code from the
 834     <tt>init with</tt> clause of the the specification.
 835 <dt><a name="scan_method"><tt>public java_cup.runtime.Symbol scan()</tt></a>
 836 <dd>This method encapsulates the scanner and is called each time a new
 837     terminal is needed by the parser.  The body of this method is
 838     supplied by the <tt>scan with</tt> clause of the specification, if
 839     present; otherwise it returns <code>getScanner().next_token()</code>.
 840 <dt><tt>public java_cup.runtime.Scanner getScanner()</tt>
 841 <dd>Returns the default scanner.  See <a href="#scanner">section 5</a>.
 842 <dt><tt>public void setScanner(java_cup.runtime.Scanner s)</tt>
 843 <dd>Sets the default scanner.  See <a href="#scanner">section 5</a>.
 844 <dt><tt> public void report_error(String message, Object info)</tt>
 845 <dd>This method should be called whenever an error message is to be issued.  In
 846     the default implementation of this method, the first parameter provides
 847     the text of a message which is printed on <tt>System.err</tt>
 848     and the second parameter is simply ignored.  It is very typical to
 849     override this method in order to provide a more sophisticated error
 850     reporting mechanism.
 851 <dt><tt>public void report_fatal_error(String message, Object info)</tt>
 852 <dd>This method should be called whenever a non-recoverable error occurs.  It
 853     responds by calling <tt>report_error()</tt>, then aborts parsing
 854     by calling the parser method <tt>done_parsing()</tt>, and finally
 855     throws an exception.  (In general <tt>done_parsing()</tt> should be called
 856     at any point that parsing needs to be terminated early).
 857 <dt><tt>public void syntax_error(Symbol cur_token)</tt>
 858 <dd>This method is called by the parser as soon as a syntax error is detected
 859     (but before error recovery is attempted).  In the default implementation it
 860     calls: <tt>report_error("Syntax error", null);</tt>.
 861 <dt><tt>public void unrecovered_syntax_error(Symbol cur_token)</tt>
 862 <dd>This method is called by the parser if it is unable to recover from a
 863     syntax error.  In the default implementation it calls:
 864     <tt>report_fatal_error("Couldn't repair and continue parse", null);</tt>.
 865 <dt><tt> protected int error_sync_size()</tt>
 866 <dd>This method is called by the parser to determine how many tokens it must
 867     successfully parse in order to consider an error recovery successful.
 868     The default implementation returns 3.  Values below 2 are not recommended.
 869     See the section on <a href="#errors">error recovery</a> for details.
 870 </dl>
 871
 872 Parsing itself is performed by the method <tt>public Symbol parse()</tt>.
 873 This method starts by getting references to each of the parse tables,
 874 then initializes a <tt>CUP$action</tt> object (by calling
 875 <tt>protected void init_actions()</tt>). Next it calls <tt>user_init()</tt>,
 876 then fetches the first lookahead token with a call to <tt>scan()</tt>.
 877 Finally, it begins parsing.  Parsing continues until <tt>done_parsing()</tt>
 878 is called (this is done automatically, for example, when the parser
 879 accepts).  It then returns a <tt>Symbol</tt> with the <tt>value</tt>
 880 instance variable containing the RESULT of the start production, or
 881 <tt>null</tt>, if there is no value.<p>
 882
 883 In addition to the normal parser, the runtime system also provides a debugging
 884 version of the parser.  This operates in exactly the same way as the normal
 885 parser, but prints debugging messages (by calling
 886 <tt>public void debug_message(String mess)</tt> whose default implementation
 887 prints a message to <tt>System.err</tt>).<p>
 888
 889 Based on these routines, invocation of a CUP parser is typically done
 890 with code such as:
 891 <pre>
 892       /* create a parsing object */
 893       parser parser_obj = new parser();
 894
 895       /* open input files, etc. here */
 896       Symbol parse_tree = null;
 897
 898       try {
 899         if (do_debug_parse)
 900           parse_tree = parser_obj.debug_parse();
 901         else
 902           parse_tree = parser_obj.parse();
 903       } catch (Exception e) {
 904         /* do cleanup here - - possibly rethrow e */
 905       } finally {
 906         /* do close out here */
 907       }
 908 </pre>
 909
 910 <a name="scanner">
 911 <h3>5. Scanner Interface</h3></a>
 912
 913 In CUP 0.10j scanner integration was improved according to
 914 suggestions made by <a href="http://www.smartsc.com">David MacMahon</a>.
 915 The changes make it easier to incorporate JLex and other
 916 automatically-generated scanners into CUP parsers.<p>
 917
 918 To use the new code, your scanner should implement the
 919 <code>java_cup.runtime.Scanner</code> interface, defined as:
 920 <pre>
 921 package java_cup.runtime;
 922
 923 public interface Scanner {
 924     public Symbol next_token() throws java.lang.Exception;
 925 }
 926 </pre><p>
 927
 928 In addition to the methods described in <a href="#parser">section
 929 4</a>, the <code>java_cup.runtime.lr_parser</code> class has two new
 930 accessor methods, <code>setScanner()</code> and <code>getScanner()</code>.
 931 The default implementation of <a href="#scan_method"><code>scan()</code></a>
 932 is:
 933 <pre>
 934   public Symbol scan() throws java.lang.Exception {
 935     Symbol sym = getScanner().next_token();
 936     return (sym!=null) ? sym : new Symbol(EOF_sym());
 937   }
 938 </pre><p>
 939 The generated parser also contains a constructor which takes a
 940 <code>Scanner</code> and calls <code>setScanner()</code> with it. In
 941 most cases, then, the <code>init with</code> and <code>scan
 942 with</code> directives may be omitted.  You can simply create the
 943 parser with a reference to the desired scanner:
 944 <pre>
 945       /* create a parsing object */
 946       parser parser_obj = new parser(new my_scanner());
 947 </pre>
 948 or set the scanner after the parser is created:
 949 <pre>
 950       /* create a parsing object */
 951       parser parser_obj = new parser();
 952       /* set the default scanner */
 953       parser_obj.setScanner(new my_scanner());
 954 </pre><p>
 955 Note that because the parser uses look-ahead, resetting the scanner in
 956 the middle of a parse is not recommended. If you attempt to use the
 957 default implementation of <code>scan()</code> without first calling
 958 <code>setScanner()</code>, a <code>NullPointerException</code> will be
 959 thrown.<p>
 960 As an example of scanner integration, the following three lines in the
 961 lexer-generator input are all that is required to use a
 962 <a href="http://www.cs.princeton.edu/~appel/modern/java/JLex/">JLex</a>
 963 or <a href="http://www.jflex.de/">JFlex</A>
 964 scanner with CUP:
 965 <pre>
 966 %implements java_cup.runtime.Scanner
 967 %function next_token
 968 %type java_cup.runtime.Symbol
 969 </pre>
 970 The JLex directive <code>%cup</code>
 971 abbreviates the above three directive in JLex versions 1.2.5 and above.
 972 Invoking the parser with the JLex scanner is then simply:
 973 <pre>
 974 parser parser_obj = new parser( new Yylex( some_InputStream_or_Reader));
 975 </pre><p>
 976
 977 Note CUP handles the JLex/JFlex convention of returning null on EOF
 978 without a problem, so an <code>%eofval</code> directive is not
 979 required in the JLex specification (this feature was added in CUP 0.10k).
 980
 981 The simple_calc example in the CUP distribution illustrates the use of
 982 the scanner integration features with a hand-coded scanner.
 983 The CUP website has a minimal CUP/JLex integration example for study.<p>
 984
 985 <a name="errors">
 986 <h3>6. Error Recovery</h3></a>
 987
 988 A final important aspect of building parsers with CUP is
 989 support for syntactic error recovery.  CUP uses the same
 990 error recovery mechanisms as YACC.  In particular, it supports
 991 a special error symbol (denoted simply as <tt>error</tt>).
 992 This symbol plays the role of a special non-terminal which, instead of
 993 being defined by productions, instead matches an erroneous input
 994 sequence.<p>
 995
 996 The error symbol only comes into play if a syntax error is
 997 detected.  If a syntax error is detected then the parser tries to replace
 998 some portion of the input token stream with <tt>error</tt> and then
 999 continue parsing.  For example, we might have productions such as:
1000
1001 <pre><tt>    stmt ::= expr SEMI | while_stmt SEMI | if_stmt SEMI | ... |
1002              error SEMI
1003              ;</tt></pre>
1004
1005 This indicates that if none of the normal productions for <tt>stmt</tt> can
1006 be matched by the input, then a syntax error should be declared, and recovery
1007 should be made by skipping erroneous tokens (equivalent to matching and
1008 replacing them with <tt>error</tt>) up to a point at which the parse can
1009 be continued with a semicolon (and additional context that legally follows a
1010 statement).  An error is considered to be recovered from if and only if a
1011 sufficient number of tokens past the <tt>error</tt> symbol can be successfully
1012 parsed.  (The number of tokens required is determined by the
1013 <tt>error_sync_size()</tt> method of the parser and defaults to 3). <p>
1014
1015 Specifically, the parser first looks for the closest state to the top
1016 of the parse stack that has an outgoing transition under
1017 <tt>error</tt>.  This generally corresponds to working from
1018 productions that represent more detailed constructs (such as a specific
1019 kind of statement) up to productions that represent more general or
1020 enclosing constructs (such as the general production for all
1021 statements or a production representing a whole section of declarations)
1022 until we get to a place where an error recovery production
1023 has been provided for.  Once the parser is placed into a configuration
1024 that has an immediate error recovery (by popping the stack to the first
1025 such state), the parser begins skipping tokens to find a point at
1026 which the parse can be continued.  After discarding each token, the
1027 parser attempts to parse ahead in the input (without executing any
1028 embedded semantic actions).  If the parser can successfully parse past
1029 the required number of tokens, then the input is backed up to the point
1030 of recovery and the parse is resumed normally (executing all actions).
1031 If the parse cannot be continued far enough, then another token is
1032 discarded and the parser again tries to parse ahead.  If the end of
1033 input is reached without making a successful recovery (or there was no
1034 suitable error recovery state found on the parse stack to begin with)
1035 then error recovery fails.
1036
1037 <a name="conclusion">
1038 <h3>7. Conclusion</h3></a>
1039
1040 This manual has briefly described the CUP LALR parser generation system.
1041 CUP is designed to fill the same role as the well known YACC parser
1042 generator system, but is written in and operates entirely with Java code
1043 rather than C or C++.  Additional details on the operation of the system can
1044 be found in the parser generator and runtime source code.  See the CUP
1045 home page below for access to the API documentation for the system and its
1046 runtime.<p>
1047
1048 This document covers version 0.10j of the system.  Check the CUP home
1049 page:
1050 <a href="http://www.cs.princeton.edu/~appel/modern/java/CUP/">
1051 http://www.cs.princeton.edu/~appel/modern/java/CUP/</a>
1052 for the latest release information, instructions for downloading the
1053 system, and additional news about CUP.  Bug reports and other
1054 comments for the developers should be sent to the CUP maintainer,
1055 C. Scott Ananian, at
1056 <a href="mailto:cananian@alumni.princeton.edu">
1057 cananian@alumni.princeton.edu</a><p>
1058
1059 CUP was originally written by
1060 <a href="http://www.cs.cmu.edu/~hudson/">
1061 Scott Hudson</a>, in August of 1995.<p>
1062
1063 It was extended to support precedence by
1064 <a href="http://www.princeton.edu/~frankf">
1065 Frank Flannery</a>, in July of 1996.<p>
1066
1067 On-going improvements have been done by
1068 <A HREF="http://www.pdos.lcs.mit.edu/~cananian">
1069 C. Scott Ananian</A>, the CUP maintainer, from December of 1997 to the
1070 present.<p>
1071
1072 <a name="refs">
1073 <h3>References</h3></a>
1074 <dl compact>
1075
1076 <dt><a name = "YACCref">[1]</a>
1077 <dd>S. C. Johnson,
1078 "YACC &emdash; Yet Another Compiler Compiler",
1079 CS Technical Report #32,
1080 Bell Telephone Laboratories,
1081 Murray Hill, NJ,
1082 1975.
1083
1084 <dt><a name = "dragonbook">[2]</a>
1085 <dd>A. Aho, R. Sethi, and J. Ullman,
1086 <i>Compilers: Principles, Techniques, and Tools</i>,
1087 Addison-Wesley Publishing,
1088 Reading, MA,
1089 1986.
1090
1091 <dt><a name = "crafting">[3]</a>
1092 <dd>C. Fischer, and R. LeBlanc,
1093 <i>Crafting a Compiler with C</i>,
1094 Benjamin/Cummings Publishing,
1095 Redwood City, CA,
1096 1991.
1097
1098 <dt><a name = "modernjava">[4]</a>
1099 <dd>Andrew W. Appel,
1100 <i>Modern Compiler Implementation in Java</i>,
1101 Cambridge University Press,
1102 New York, NY,
1103 1998.
1104
1105 </dl>
1106
1107 <h3><a name="appendixa">
1108 Appendix A. Grammar for CUP Specification Files</a> (0.10j)</h3>
1109 <hr><br>
1110 <pre><tt>java_cup_spec      ::= package_spec import_list code_parts
1111                        symbol_list precedence_list start_spec
1112                        production_list
1113 package_spec       ::= PACKAGE multipart_id SEMI | empty
1114 import_list        ::= import_list import_spec | empty
1115 import_spec        ::= IMPORT import_id SEMI
1116 code_part          ::= action_code_part | parser_code_part |
1117                        init_code | scan_code
1118 code_parts         ::= code_parts code_part | empty
1119 action_code_part   ::= ACTION CODE CODE_STRING opt_semi
1120 parser_code_part   ::= PARSER CODE CODE_STRING opt_semi
1121 init_code          ::= INIT WITH CODE_STRING opt_semi
1122 scan_code          ::= SCAN WITH CODE_STRING opt_semi
1123 symbol_list        ::= symbol_list symbol | symbol
1124 symbol             ::= TERMINAL type_id declares_term |
1125                        NON TERMINAL type_id declares_non_term |
1126                        NONTERMINAL type_id declares_non_term |
1127                        TERMINAL declares_term |
1128                        NON TERMINAL declares_non_term |
1129                        NONTERMIANL declared_non_term
1130 term_name_list     ::= term_name_list COMMA new_term_id | new_term_id
1131 non_term_name_list ::= non_term_name_list COMMA new_non_term_id |
1132                        new_non_term_id
1133 declares_term      ::= term_name_list SEMI
1134 declares_non_term  ::= non_term_name_list SEMI
1135 precedence_list    ::= precedence_l | empty
1136 precedence_l       ::= precedence_l preced + preced;
1137 preced             ::= PRECEDENCE LEFT terminal_list SEMI
1138                        | PRECEDENCE RIGHT terminal_list SEMI
1139                        | PRECEDENCE NONASSOC terminal_list SEMI
1140 terminal_list      ::= terminal_list COMMA terminal_id | terminal_id
1141 start_spec         ::= START WITH nt_id SEMI | empty
1142 production_list    ::= production_list production | production
1143 production         ::= nt_id COLON_COLON_EQUALS rhs_list SEMI
1144 rhs_list           ::= rhs_list BAR rhs | rhs
1145 rhs                ::= prod_part_list PERCENT_PREC term_id |
1146                        prod_part_list
1147 prod_part_list     ::= prod_part_list prod_part | empty
1148 prod_part          ::= symbol_id opt_label | CODE_STRING
1149 opt_label          ::= COLON label_id | empty
1150 multipart_id       ::= multipart_id DOT ID | ID
1151 import_id          ::= multipart_id DOT STAR | multipart_id
1152 type_id            ::= multipart_id
1153 terminal_id        ::= term_id
1154 term_id            ::= symbol_id
1155 new_term_id        ::= ID
1156 new_non_term_id    ::= ID
1157 nt_id              ::= ID
1158 symbol_id          ::= ID
1159 label_id           ::= ID
1160 opt_semi           ::= SEMI | empty
1161
1162 </tt></pre>
1163 <hr><p><p>
1164
1165 <h3><a name = "appendixb">Appendix B. A Very Simple Example Scanner<a></h3>
1166 <hr><br>
1167 <pre>
1168 <tt>// Simple Example Scanner Class
1169
1170 import java_cup.runtime.*;
1171 import sym;
1172
1173 public class scanner {
1174   /* single lookahead character */
1175   protected static int next_char;
1176
1177   /* advance input by one character */
1178   protected static void advance()
1179     throws java.io.IOException
1180     { next_char = System.in.read(); }
1181
1182   /* initialize the scanner */
1183   public static void init()
1184     throws java.io.IOException
1185     { advance(); }
1186
1187   /* recognize and return the next complete token */
1188   public static Symbol next_token()
1189     throws java.io.IOException
1190     {
1191       for (;;)
1192         switch (next_char)
1193           {
1194             case '0': case '1': case '2': case '3': case '4':
1195             case '5': case '6': case '7': case '8': case '9':
1196               /* parse a decimal integer */
1197               int i_val = 0;
1198               do {
1199                 i_val = i_val * 10 + (next_char - '0');
1200                 advance();
1201               } while (next_char >= '0' && next_char <= '9');
1202             return new Symbol(sym.NUMBER, new Integer(i_val));
1203
1204             case ';': advance(); return new Symbol(sym.SEMI);
1205             case '+': advance(); return new Symbol(sym.PLUS);
1206             case '-': advance(); return new Symbol(sym.MINUS);
1207             case '*': advance(); return new Symbol(sym.TIMES);
1208             case '/': advance(); return new Symbol(sym.DIVIDE);
1209             case '%': advance(); return new Symbol(sym.MOD);
1210             case '(': advance(); return new Symbol(sym.LPAREN);
1211             case ')': advance(); return new Symbol(sym.RPAREN);
1212
1213             case -1: return new Symbol(sym.EOF);
1214
1215             default:
1216               /* in this simple scanner we just ignore everything else */
1217               advance();
1218             break;
1219           }
1220     }
1221 };
1222 </tt></pre>
1223
1224
1225 <a name=changes>
1226 <h3>Appendix C:  Incompatibilites between CUP 0.9 and CUP 0.10</a></h3>
1227
1228 CUP version 0.10a is a major overhaul of CUP.  The changes are severe,
1229 meaning no backwards compatibility to older versions.
1230
1231 The changes consist of:
1232 <ul>
1233 <li> <a href="#lex_inter">A different lexical interface</a>,
1234 <li> <a href="#new_dec">New terminal/non-terminal declarations</a>,
1235 <li> <a href="#label_ref">Different label references</a>,
1236 <li> <a href="#RESULT_pass">A different way of passing RESULT</a>,
1237 <li> <a href="#pos_prop">New position values and propagation</a>,
1238 <li> <a href="#ret_val">Parser now returns a value</a>,
1239 <li> <a href="#prec_add">Terminal precedence declarations</a> and
1240 <li> <a href="#con_prec">Rule contextual precedence assignment</a>
1241 </ul>
1242
1243 <h5><a name="lex_inter">Lexical Interface</a></h5>
1244
1245 CUP now interfaces with the lexer in a completely different
1246 manner.  In the previous releases, a new class was used for every
1247 distinct type of terminal.  This release, however, uses only one class:
1248 The <tt>Symbol</tt> class.  The <tt>Symbol</tt> class has three instance
1249 variables which
1250 are significant to the parser when passing information from the lexer.
1251 The first is the <tt>value</tt> instance variable.  This variable
1252 contains the
1253 value of that terminal.  It is of the type declared as the terminal type
1254 in the parser specification file.  The second two are the instance
1255 variables <tt>left</tt> and <tt>right</tt>.  They should be filled with
1256 the <tt>int</tt> value of
1257 where in the input file, character-wise, that terminal was found.<p>
1258
1259 For more information, refer to the manual on <a href="#lex_part">scanners</a>.
1260
1261 <h5><a name="new_dec">Terminal/Non-Terminal Declarations</a></h5>
1262
1263 Terminal and non-terminal declarations now can be declared in two
1264 different ways to indicate the values of the terminals or
1265 non-terminals.  The previous declarations of the form
1266
1267 <pre><tt>
1268 terminal <i>classname terminal</i> [, <i>terminal ...</i>];
1269 </tt></pre>
1270
1271 still works.  The classname, however indicates the type of the value of
1272 the terminal or non-terminal, and does not indicate the type of object
1273 placed on the parse stack.
1274
1275 A declaration, such as:
1276
1277 <pre><tt>
1278 terminal <i>terminal</i> [, <i>terminal ...</i>];
1279 </tt></pre>
1280
1281 indicates the terminals in the list hold no value.<p>
1282
1283 For more information, refer to the manual on <a
1284 href="#symbol_list">declarations</a>.
1285
1286 <h5><a name="label_ref">Label References</a></h5>
1287
1288 Label references do not refer to the object on the parse stack, as in
1289 the old CUP, but rather to the value of the <tt>value</tt>
1290 instance variable of
1291 the <tt>Symbol</tt> that represents that terminal or non-terminal.  Hence,
1292 references to terminal and non-terminal values is direct, as opposed to
1293 the old CUP, where the labels referred to objects containing the value
1294 of the terminal or non-terminal.<p>
1295
1296 For more information, refer to the manual on <a href="#label_part">labels</a>.
1297
1298 <h5><a name="RESULT_pass">RESULT Value</a></h5>
1299
1300 The <tt>RESULT</tt> variable refers directly to the value of the
1301 non-terminal
1302 to which a rule reduces, rather than to the object on the parse stack.
1303 Hence, <tt>RESULT</tt> is of the same type the non-terminal to which
1304 it reduces,
1305 as declared in the non-terminal declaration.  Again, the reference is
1306 direct, rather than to something that will contain the data.<p>
1307
1308 For more information, refer to the manual on <a href="#RES_part">RESULT</a>.
1309
1310 <h5><a name="pos_prop">Position Propagation</a></h5>
1311
1312 For every label, two more variables are declared, which are the label
1313 plus <tt>left</tt> or the label plus <tt>right</tt>.  These correspond
1314 to the left and
1315 right locations in the input stream to which that terminal or
1316 non-terminal came from.  These values are propagated from the input
1317 terminals, so that the starting non-terminal should have a left value of
1318 0 and a right value of the location of the last character read.<p>
1319
1320 For more information, refer to the manual on <a href="#label_part">positions</a>.
1321
1322 <h5><a name="ret_val">Return Value</a></h5>
1323
1324 A call to <tt>parse()</tt> or <tt>debug_parse()</tt> returns a
1325 Symbol.  This Symbol is the start non-terminal, so the <tt>value</tt>
1326 instance variable contains the final <tt>RESULT</tt> assignment.
1327
1328 <h5><a name="prec_add">Precedence</a></h5>
1329
1330 CUP now has precedenced terminals.  a new declaration section,
1331 occurring between the terminal and non-terminal declarations and the
1332 grammar specifies the precedence and associativity of rules.  The
1333 declarations are of the form:
1334
1335 <pre><tt>
1336 precedence {left| right | nonassoc} <i>terminal</i>[, <i>terminal</i> ...];
1337 ...
1338 </tt>
1339 </pre>
1340
1341 The terminals are assigned a precedence, where terminals on the same
1342 line have equal precedences, and the precedence declarations farther
1343 down the list of precedence declarations have higher precedence.
1344 <tt>left, right</tt> and <tt>nonassoc</tt> specify the associativity
1345 of these terminals.  left
1346 associativity corresponds to a reduce on conflict, right to a shift on
1347 conflict, and nonassoc to an error on conflict.  Hence, ambiguous
1348 grammars may now be used.<p>
1349
1350 For more information, refer to the manual on <a
1351 href="#precedence">precedence</a>.
1352
1353 <h5><a name="con_prec">Contextual Precedence</a></h5>
1354
1355 Finally the new CUP adds contextual precedence.  A production may be
1356 declare as followed:
1357
1358 <pre><tt>
1359 lhs ::= <i>{right hand side list of terminals, non-terminals and actions}</i>
1360         %prec <i>{terminal}</i>;
1361 </tt></pre>
1362
1363 this production would then have a precedence equal to the terminal
1364 specified after the <tt>%prec</tt>.  Hence, shift/reduce conflicts can be
1365 contextually resolved.  Note that the <tt>%prec</tt> <i>terminal</i>
1366 part comes after all actions strings.  It does not come before the
1367 last action string.<p>
1368
1369 For more information, refer to the manual on <a href="#cpp">contextual
1370 precedence</a>.
1371
1372 These changes implemented by:
1373 <h3>
1374 <a href="http://www.princeton.edu/~frankf">Frank Flannery</a><br>
1375 <a href="http://www.cs.princeton.edu">Department of Computer Science</a><br>
1376 <a href="http://www.princeton.edu">Princeton University</a><br>
1377 </h3>
1378 <a name=bugs>
1379 <h3>Appendix D:  Bugs</a></h3>
1380 In this version of CUP it's difficult for the semantic action phrases (Java code attached
1381 to productions) to access the <tt>report_error</tt> method and other similar methods and
1382 objects defined in the <tt>parser code</tt> directive.
1383 <p>
1384 This is because the parsing tables (and parsing engine) are in one object (belonging to
1385 class <tt>parser</tt> or whatever name is specified by the <strong>-parser</strong> directive),
1386 and the semantic actions are in another object (of class <tt>CUP$actions</tt>).
1387 <p>
1388 However, there is a way to do it, though it's a bit inelegant.
1389 The action object has a <tt>private final</tt> field named
1390 <tt>parser</tt> that points to the parsing object.  Thus,
1391 methods and instance variables of the parser can be accessed within semantic actions as:
1392 <pre>
1393     parser.report_error(message,info);
1394     x = parser.mydata;
1395 </pre>
1396 <p>
1397 Perhaps this will not be necessary in a future release, and that
1398 such methods and variables as <tt>report_error</tt> and
1399 <tt>mydata</tt> will be available
1400 directly from the semantic actions; we will achieve this by combining the
1401 "parser" object and the "actions" object together.
1402
1403 <p>
1404 For a list of any other currently known bugs in CUP, see
1405 <A HREF="http://www.cs.princeton.edu/~appel/modern/java/CUP/bugs.html">
1406 http://www.cs.princeton.edu/~appel/modern/java/CUP/bugs.html</A>.
1407
1408 <a name=version>
1409 <h3>Appendix E:  Change log</a></h3>
1410
1411 <dl>
1412 <dt>0.9e<dd>March 1996, Scott Hudson's original version.
1413 <dt>0.10a<dd>August 1996, <a href="#about">several major changes</a> to
1414 the interface.
1415 <dt>0.10b<dd>November 1996, fixes a few minor bugs.
1416 <dt>0.10c<dd>July 1997, fixes a bug related to precedence declarations.
1417 <dt>0.10e<dd>September 1997, fixes a bug introduced in 0.10c relating
1418 to <tt>nonassoc</tt> precedence.  Thanks to
1419 <a href="http://www.cs.purdue.edu/homes/hosking">Tony Hosking</a>
1420 for reporting the bug and providing the fix.
1421 Also recognizes carriage-return character as white space and fixes a
1422 number of other small bugs.
1423 <dt>0.10f<dd>December 1997, was a maintenance release.  The CUP source
1424 was cleaned up for JDK 1.1.
1425 <dt>0.10g<dd>March 1998, adds new features and fixes old bugs.
1426 The behavior of RESULT assignments was normalized, and a problem
1427 with implicit start productions was fixed.  The CUP grammar was
1428 extended to allow array types for terminals and non-terminals, and
1429 a command-line flag was added to allow the generation of a symbol
1430 <i>interface</i>, rather than class.  Bugs associated with multiple
1431 invocations of a single parser object and multiple CUP classes in one
1432 package have been stomped on.  Documentation was updated, as well.
1433 <dt>0.10h-0.10i<dd>February 1999, are maintenance releases.
1434 <dt>0.10j<dd>July 1999, broadened the CUP input grammar to allow more
1435 flexibility and improved scanner integration via the
1436 <code>java_cup.runtime.Scanner</code> interface.
1437 </dl>
1438
1439
1440 <hr>
1441
1442 <a name="trademark">
1443 Java and HotJava are
1444 trademarks of <a href="http://www.sun.com/">Sun Microsystems, Inc.</a>,
1445 and refer to Sun's Java programming language and HotJava browser
1446 technologies.
1447 CUP is not sponsored by or affiliated with Sun Microsystems, Inc.
1448
1449 <hr>
1450
1451
1452 </body></html>