manual.html 74.4 KB
Newer Older
petter's avatar
petter committed
1 2
<html><head>
<title>CUP User's Manual</title></head><body>
3
<div class="container">
petter's avatar
petter committed
4 5
<hr>
<h1>CUP User's Manual</h1>
petter's avatar
petter committed
6 7
<h3><a href="http://www2.in.tum.de">Michael Petter, Technische Universit&auml;t M&uuml;nchen</a><br />
<a href="http://www.cc.gatech.edu/gvu/people/Faculty/Scott.E.Hudson.html">
petter's avatar
petter committed
8 9 10 11 12 13 14
Scott E. Hudson</a><br> 
<a href="http://www.cc.gatech.edu/gvu/gvutop.html">
Graphics Visualization and Usability Center</a><br> 
<a href="http://www.gatech.edu/TechHome.html">
Georgia Institute of Technology</a></h3>
Modified by <a href="http://www.princeton.edu/%7Efrankf">Frank
Flannery</a>, <a href="http://www.pdos.lcs.mit.edu/%7Ecananian/">C. Scott Ananian</a>, 
15
<a href="http://www.cs.princeton.edu/%7Edanwang">Dan Wang</a>, <a href="http://www2.cs.tum.edu/%7Epetter">Michael Petter</a> with advice from 
petter's avatar
petter committed
16
<a href="http://www.cs.princeton.edu/%7Eappel">Andrew W. Appel</a><br>
17 18
<br>
Last updated  06/2014 (v0.11b)
petter's avatar
petter committed
19 20 21
<hr>

<h3>Table of Contents</h3>
petter's avatar
petter committed
22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
<ol type="i">
       <li> <a href="#about">About CUP Version 0.10</a>
  </li><li> <a href="#about11">About CUP Version 0.11</a>
  </li>
</ol>
<ol>
       <li> <a href="#intro">Introduction and Example</a>
  </li><li> <a href="#spec">Specification Syntax</a>
        <ol><li><a href="#package_spec">Package and import specification</a>
  </li><li> <a href="#code_part">User code componentes</a>
  </li><li> <a href="#symbol_list">Symbol lists</a>
  </li><li> <a href="#precedence">Precedence and associativity declarations</a>
  </li><li>         <a href="#production_list">The grammar</a></li></ol>
  </li><li> Running CUP 
        <ol><li><a href="#running">Command line interface</a>
  </li><li>         <a href="#ant">CUP and ANT</a></li></ol>
  </li><li> <a href="#parser">Customizing the Parser</a>
  </li><li> <a href="#scanner">Scanner interface</a>
       <ol><li> <a href="#basic-symbols">Basic Symbol management</a>
  </li><li>  <a href="#advanced-symbols">Advanced Symbol management</a>
  </li><li>  <a href="#symbolstream-caching">Symbol Stream caching</a></li></ol>
  </li><li> <a href="#errors">Error Recovery</a>
        <ol><li><a href="#error_sym">The error symbol</a>
  </li><li>         <a href="#continuation_symbols">Viable continuations</a></li></ol>
  </li><li> <a href="#conclusion">Conclusion</a>
  </li>
</ol>
<a href="#refs">References</a>
<ol type="A">
       <li> <a href="#appendixa">Grammar for CUP Specification Files</a>
  </li><li> <a href="#appendixb">A Very Simple Example Scanner</a>
  </li><li> <a href="#changes">Incompatibilites between CUP 0.9 and CUP 0.10</a>
  </li><li> <a href="#bugs">Bugs</a>
  </li><li> <a href="#version">Change log</a>
  </li>
</ol>

<a name="about"></a> 
petter's avatar
petter committed
60
<h3>i. About CUP Version 0.10</h3>
petter's avatar
petter committed
61
Version
petter's avatar
petter committed
62 63 64 65 66 67 68
0.10 of CUP adds many new changes and features over the previous releases
of version 0.9.  These changes attempt to make CUP more like its
predecessor, YACC.  As a result, the old 0.9 parser specifications for CUP are
not compatible and a reading of <a href="#changes">appendix C</a> of the new
manual will be necessary to write new specifications.  The new version,
however, gives the user more power and options, making parser specifications
easier to write.
petter's avatar
petter committed
69
<a name="about11"></a><h3>ii. About CUP Version 0.11</h3>
petter's avatar
petter committed
70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198
in version 0.11 the TUM team tries to continue the success story of CUP 0.10, 
beginning with the introduction of generic data types for non-terminal symbols
as well as a modernisation of the user interface with a comfortable ANT plugin 
structure.
<a name="intro">
<h3>1. Introduction and Example</h3></a>

This manual describes the basic operation and use of the 
Java<a href="#trademark">(tm)</a>
Based Constructor of Useful Parsers (CUP for short).
CUP is a system for generating LALR parsers from simple specifications.
It serves the same role as the widely used program YACC 
<a href="#YACCref">[1]</a> and in fact offers most of the features of YACC.  
However, CUP is written in Java, uses specifications including embedded 
Java code, and produces parsers which are implemented in Java.<p>

Although this manual covers all aspects of the CUP system, it is relatively
brief, and assumes you have at least a little bit of knowledge of LR
parsing.  A working knowledge of YACC is also very helpful in
understanding how CUP specifications work.
A number of compiler construction textbooks (such as 
<a href="#dragonbook">[2</a>,<a href="#crafting">3]</a>) cover this material, 
and discuss the YACC system (which is quite similar to this one) as a 
specific example. </p><p> 

Using CUP involves creating a simple specification based on the
grammar for which a parser is needed, along with construction of a
scanner capable of breaking characters up into meaningful tokens (such
as keywords, numbers, and special symbols).</p><p> 

As a simple example, consider a 
system for evaluating simple arithmetic expressions over integers.  
This system would read expressions from standard input (each terminated 
with a semicolon), evaluate them, and print the result on standard output.  
A grammar for the input to such a system might look like: </p><pre>  expr_list ::= expr_list expr_part | expr_part
  expr_part ::= expr ';'
  expr      ::= expr '+' expr | expr '-' expr | expr '*' expr 
	      | expr '/' expr | expr '%' expr | '(' expr ')'  
              | '-' expr | number 
</pre>
To specify a parser based on this grammar, our first step is to identify and
name the set of terminal symbols that will appear on input, and the set of 
non-terminal symbols.  In this case, the non-terminals are: 

<pre><tt>  expr_list, expr_part </tt> and <tt> expr </tt>.</pre>

For terminal names we might choose:

<pre><tt>  SEMI, PLUS, MINUS, TIMES, DIVIDE, MOD, NUMBER, LPAREN,</tt>
and <tt>RPAREN</tt></pre>

The experienced user will note a problem with the above grammar.  It is
ambiguous.  An ambiguous grammar is a grammar which, given a certain
input, can reduce the parts of the input in two different ways such as
to give two different answers.  Take the above grammar, for
example. given the following input: <br>
<tt>3 + 4 * 6</tt><br>
The grammar can either evaluate the <tt>3 + 4</tt> and then multiply
seven by six, or it can evaluate <tt>4 * 6</tt> and then add three.
Older versions of CUP forced the user to write unambiguous grammars, but
now there is a construct allowing the user to specify precedences and
associativities for terminals.  This means that the above ambiguous
grammar can be used, after specifying precedences and associativities.
There is more explanation later.

Based on these namings we can construct a small CUP specification 
as follows:<br>
<hr>
<pre><tt>// CUP specification for a simple expression evaluator (no actions)

import java_cup.runtime.*;

/* Preliminaries to set up and use the scanner.  */
init with {: scanner.init();              :};
scan with {: return scanner.next_token(); :};

/* Terminals (tokens returned by the scanner). */
terminal            SEMI, PLUS, MINUS, TIMES, DIVIDE, MOD;
terminal            UMINUS, LPAREN, RPAREN;
terminal Integer    NUMBER;

/* Non terminals */
non terminal            expr_list, expr_part;
non terminal Integer    expr, term, factor;

/* Precedences */
precedence left PLUS, MINUS;
precedence left TIMES, DIVIDE, MOD;
precedence left UMINUS;

/* The grammar */
expr_list ::= expr_list expr_part | 
              expr_part;
expr_part ::= expr SEMI;
expr      ::= expr PLUS expr 
            | expr MINUS expr  
            | expr TIMES expr  
            | expr DIVIDE expr  
            | expr MOD expr 
	    | MINUS expr %prec UMINUS
            | LPAREN expr RPAREN
	    | NUMBER
	    ;
</tt></pre>
<hr><br>
We will consider each part of the specification syntax in detail later.  
However, here we can quickly see that the specification contains four 
main parts.  The first part provides preliminary and miscellaneous declarations
to specify how the parser is to be generated, and supply parts of the 
runtime code.  In this case we indicate that the <tt>java_cup.runtime</tt>
classes should be imported, then supply a small bit of initialization code,
and some code for invoking the scanner to retrieve the next input token.
The second part of the specification declares terminals and non-terminals,
and associates object classes with each.  In this case, the terminals
are declared as either with no type, or of type
<tt>Integer</tt>.  The specified type of the
terminal or non-terminal is the type of the value of those terminals or
non-terminals.  If no type is specified, the terminal or non-terminal
carries no value.  Here, no type indicates that these
terminals and non-terminals hold no value.  
The third part specifies the precedence and
associativity of terminals.  The last precedence declaration give its
terminals the highest precedence. The final 
part of the specification contains the grammar.<p>

 
To produce a parser from this specification we use the CUP generator.
If this specification were stored in a file <tt>parser.cup</tt>, then 
(on a Unix system at least) we might invoke CUP using a command like:
petter's avatar
petter committed
199
</p><pre><tt> java -jar java-cup-11b.jar parser.cup</tt> </pre>
petter's avatar
petter committed
200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287
In this case, the system will produce two Java source files containing 
parts of the generated parser: <tt>sym.java</tt> and <tt>parser.java</tt>.  
As you might expect, these two files contain declarations for the classes 
<tt>sym</tt> and <tt>parser</tt>. The <tt>sym</tt> class contains a series of 
constant declarations, one for each terminal symbol.  This is typically used 
by the scanner to refer to symbols (e.g. with code such as 
"<tt>return new Symbol(sym.SEMI);</tt>" ).  The <tt>parser</tt> class 
implements the parser itself.<p>

The specification above, while constructing a full parser, does not perform 
any semantic actions &amp;emdash; it will only indicate success or failure of a parse.
To calculate and print values of each expression, we must embed Java
code within the parser to carry out actions at various points.  In CUP,
actions are contained in <i>code strings</i> which are surrounded by delimiters 
of the form <tt>{:</tt> and <tt>:}</tt> (we can see examples of this in the 
<tt>init with</tt> and <tt>scan with</tt> clauses above).  In general, the 
system records all characters within the delimiters, but does not try to check 
that it contains valid Java code.</p><p>

A more complete CUP specification for our example system (with actions 
embedded at various points in the grammar) is shown below:<br>
</p><hr>
<pre><tt>// CUP specification for a simple expression evaluator (w/ actions)

import java_cup.runtime.*;

/* Preliminaries to set up and use the scanner.  */
init with {: scanner.init();              :};
scan with {: return scanner.next_token(); :};

/* Terminals (tokens returned by the scanner). */
terminal           SEMI, PLUS, MINUS, TIMES, DIVIDE, MOD;
terminal           UMINUS, LPAREN, RPAREN;
terminal Integer   NUMBER;

/* Non-terminals */
non terminal            expr_list, expr_part;
non terminal Integer    expr;

/* Precedences */
precedence left PLUS, MINUS;
precedence left TIMES, DIVIDE, MOD;
precedence left UMINUS;

/* The grammar */
expr_list ::= expr_list expr_part 
	      | 
              expr_part;

expr_part ::= expr:e 
	      {: System.out.println("= " + e); :} 
              SEMI              
	      ;

expr      ::= expr:e1 PLUS expr:e2    
	      {: RESULT = new Integer(e1.intValue() + e2.intValue()); :} 
	      | 
              expr:e1 MINUS expr:e2    
              {: RESULT = new Integer(e1.intValue() - e2.intValue()); :} 
	      | 
              expr:e1 TIMES expr:e2 
	      {: RESULT = new Integer(e1.intValue() * e2.intValue()); :} 
	      | 
              expr:e1 DIVIDE expr:e2 
	      {: RESULT = new Integer(e1.intValue() / e2.intValue()); :} 
	      | 
              expr:e1 MOD expr:e2 
	      {: RESULT = new Integer(e1.intValue() % e2.intValue()); :} 
	      | 
              NUMBER:n                 
	      {: RESULT = n; :} 
	      | 
              MINUS expr:e             
	      {: RESULT = new Integer(0 - e.intValue()); :} 
	      %prec UMINUS
	      | 
              LPAREN expr:e RPAREN     
	      {: RESULT = e; :} 
	      ;
</tt></pre>
<hr><br>
Here we can see several changes.  Most importantly, code to be executed at 
various points in the parse is included inside code strings delimited by 
<tt>{:</tt> and <tt>:}</tt>.  In addition, labels have been placed on various 
symbols in the right hand side of productions.  For example in:<br>
<pre>  expr:e1 PLUS expr:e2    
	{: RESULT = new Integer(e1.intValue() + e2.intValue()); :} 
</pre>
288
<a name="RES_part"></a>
petter's avatar
petter committed
289 290
the first non-terminal <tt>expr</tt> has been labeled with <tt>e1</tt>, and 
the second with <tt>e2</tt>.  The left hand side value 
petter's avatar
petter committed
291
of each production is always implicitly labeled as <tt>RESULT</tt>.<p>
petter's avatar
petter committed
292

petter's avatar
petter committed
293
Each symbol appearing in a production is represented at runtime by an
petter's avatar
petter committed
294 295 296 297 298 299 300 301
object of type <tt>Symbol</tt> on the parse stack.  The labels refer to
the instance variable <tt>value</tt> in those objects.  In the
expression <tt>expr:e1 PLUS expr:e2</tt>, <tt>e1</tt> and <tt>e2</tt>
refer to objects of type Integer.  These objects are in the value fields
of the objects of type <tt>Symbol</tt> representing those non-terminals
on the parse stack.  <tt>RESULT</tt> is of type <tt>Integer</tt> as
well, since the resulting non-terminal <tt>expr</tt> was declared as of 
type <tt>Integer</tt>.  This object becomes the <tt>value</tt> instance
petter's avatar
petter committed
302
variable of a new <tt>Symbol</tt> object.</a></p><p>
petter's avatar
petter committed
303 304 305 306 307 308 309 310 311

For each label, two more variables accessible to the user are declared.
A left and right value labels are passed to the code string, so that the
user can find out where the left and right side of each terminal or
non-terminal is in the input stream.  The name of these variables is the
label name, plus <tt>left</tt> or <tt>right</tt>.  for example, given
the right hand side of a production <tt>expr:e1 PLUS expr:e2</tt> the
user could not only access variables <tt>e1</tt> and <tt>e2</tt>, but
also <tt>e1left, e1right, e2left</tt> and <tt>e2right</tt>.  these
petter's avatar
petter committed
312
variables are of type <tt>int</tt>.</p><p>
petter's avatar
petter committed
313

petter's avatar
petter committed
314
<a name="lex_part"></a>
petter's avatar
petter committed
315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337

The final step in creating a working parser is to create a <i>scanner</i> (also
known as a <i>lexical analyzer</i> or simply a <i>lexer</i>).  This routine is 
responsible for reading individual characters, removing things things like
white space and comments, recognizing which terminal symbols from the 
grammar each group of characters represents, then returning Symbol objects
representing these symbols to the parser.
The terminals will be retrieved with a call to the
scanner function.  In the example, the parser will call
<tt>scanner.next_token()</tt>. The scanner should return objects of
type <tt>java_cup.runtime.Symbol</tt>.  This type is very different than
older versions of CUP's <tt>java_cup.runtime.symbol</tt>.  These Symbol
objects contains the instance variable <tt>value</tt> of type Object, 
which should be
set by the lexer.  This variable refers to the value of that symbol, and
the type of object in value should be of the same type as declared in
the <tt>terminal</tt> and <tt>non terminal</tt> declarations.  In the
above example, if the lexer wished to pass a NUMBER token, it should
create a <tt>Symbol</tt> with the <tt>value</tt> instance variable
filled with an object of type <tt>Integer</tt>.  <code>Symbol</code>
objects corresponding to terminals and non-terminals with no value
have a null value field.</a></p><p>

petter's avatar
petter committed
338 339

The code contained in the <tt>init with</tt> clause of the specification 
petter's avatar
petter committed
340 341 342 343 344 345 346 347 348 349 350
will be executed before any tokens are requested.  Each token will be 
requested using whatever code is found in the <tt>scan with</tt> clause.
Beyond this, the exact form the scanner takes is up to you; however
note that each call to the scanner function should return a new
instance of <code>java_cup.runtime.Symbol</code> (or a subclass).
These symbol objects are annotated with parser information and pushed
onto a stack; reusing objects will result in the parser annotations
being scrambled.  As of CUP 0.10j, <code>Symbol</code> reuse should be
detected if it occurs; the parser will throw an <code>Error</code>
telling you to fix your scanner.</a></p><p>

petter's avatar
petter committed
351 352

In the </a><a href="#spec">next section</a> a more detailed and formal 
petter's avatar
petter committed
353 354 355 356 357 358 359 360
explanation of all parts of a CUP specification will be given.  
<a href="#running">Section 3</a> describes options for running the 
CUP system.  <a href="#parser">Section 4</a> discusses the details 
of how to customize a CUP parser, while <a href="#scanner">section 5</a>
discusses the scanner interface added in CUP 0.10j. <a href="#errors">Section
 6</a> considers error recovery.  Finally, <a href="#conclusion">Section 7</a> 
provides a conclusion.

petter's avatar
petter committed
361 362
<a name="spec"></a>
<h3>2. Specification Syntax</h3>
petter's avatar
petter committed
363 364 365 366 367 368
Now that we have seen a small example, we present a complete description of all 
parts of a CUP specification.  A specification has four sections with 
a total of eight specific parts (however, most of these are optional).  
A specification consists of:
</p><ul>
<li> <a href="#package_spec">package and import specifications</a>,
369
</li><li> <a href="#parser_class_name">parser class name</a>,
petter's avatar
petter committed
370 371 372 373 374 375 376 377 378 379
</li><li> <a href="#code_part">user code components</a>,
</li><li> <a href="#symbol_list">symbol (terminal and non-terminal) lists</a>, 
</li><li> <a href="#precedence">precedence declarations</a>, and
</li><li> <a href="#production_list">the grammar</a>.
</li></ul>
Each of these parts must appear in the order presented here.  (A complete 
grammar for the specification language is given in 
<a href="#appendixa">Appendix A</a>.)  The particulars of each part of
the specification are described in the subsections below.<p>

petter's avatar
petter committed
380
</p><h4><a name="package_spec"></a>2.1 Package and Import Specifications</h4>
petter's avatar
petter committed
381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410

A specification begins with optional <tt>package</tt> and <tt>import</tt> 
declarations.  These have the same syntax, and play the same 
role, as the package and import declarations found in a normal Java program.
A package declaration is of the form:

<pre><tt>    package <i>name</i>;</tt></pre>

where name <tt><i>name</i></tt> is a Java package identifier, possibly in
several parts separated by ".".  In general, CUP employs Java lexical
conventions.  So for example, both styles of Java comments are supported,
and identifiers are constructed beginning with a letter, dollar
sign ($), or underscore (_), which can then be followed by zero or more
letters, numbers, dollar signs, and underscores.<p>

After an optional <tt>package</tt> declaration, there can be zero or more 
<tt>import</tt> declarations. As in a Java program these have the form:

</p><pre><tt>    import <i>package_name.class_name</i>;</tt>
</pre>
or
<pre><tt>    import <i>package_name</i>.*;</tt>
</pre>

The package declaration indicates what package the <tt>sym</tt> and 
<tt>parser</tt> classes that are generated by the system will be in.  
Any import declarations that appear in the specification will also appear
in the source file for the <tt>parser</tt> class allowing various names from
that package to be used directly in user supplied action code.

411 412 413 414 415 416 417 418 419 420 421 422 423
After the package and imports, a specification can include a parser
class name, as follows:

<pre><tt> class <i>name</i>;</tt>
</pre>

If a class name is supplied, then that is the name that will be used
for the generated parser code. As well, the generated symbols class
will have the given name followed by "<tt>Sym</tt>".

<p>If no class name is supplied, then the parser class is called
"<tt>parser</tt>", and the symbols class is called "<tt>sym</tt>".

petter's avatar
petter committed
424
<h4><a name="code_part"></a>2.2 User Code Components</h4>
petter's avatar
petter committed
425

426 427
Following these declarations are another series of optional declarations 
that allow user code to be included
petter's avatar
petter committed
428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487
as part of the generated parser (see <a href="#parser">Section 4</a> for a 
full description of how the parser uses this code).  As a part of the parser 
file, a separate non-public class to contain all embedded user actions is 
produced.  The first <tt>action code</tt> declaration section allows code to 
be included in this class.  Routines and variables for use by the code 
embedded in the grammar would normally be placed in this section (a typical 
example might be symbol table manipulation routines).  This declaration takes 
the form:

<pre><tt>    action code {: ... :};</tt>
</pre>

where <tt>{: ... :}</tt> is a code string whose contents will be placed
directly within the <tt>action class</tt> class declaration.<p>

After the <tt>action code</tt> declaration is an optional 
<tt>parser code</tt> declaration.  This declaration allows methods and
variable to be placed directly within the generated parser class.
Although this is less common, it can be helpful when customizing the 
parser &amp;emdash; it is possible for example, to include scanning methods inside
the parser and/or override the default error reporting routines.  This 
declaration is very similar to the <tt>action code</tt> declaration and 
takes the form:

</p><pre><tt>    parser code {: ... :};</tt>
</pre>

Again, code from the code string is placed directly into the generated parser
class definition.<p>

Next in the specification is the optional <tt>init</tt> declaration 
which has the form:

</p><pre><tt>    init with {: ... :};</tt></pre>

This declaration provides code that will be executed by the parser
before it asks for the first token.  Typically, this is used to initialize
the scanner as well as various tables and other data structures that might
be needed by semantic actions.  In this case, the code given in the code
string forms the body of a <tt>void</tt> method inside the <tt>parser</tt> 
class.<p>

The final (optional) user code section of the specification indicates how 
the parser should ask for the next token from the scanner.  This has the
form:

</p><pre><tt>    scan with {: ... :};</tt></pre>

As with the <tt>init</tt> clause, the contents of the code string forms
the body of a method in the generated parser.  However, in this case
the method returns an object of type <tt>java_cup.runtime.Symbol</tt>.
Consequently the code found in the <tt>scan with</tt> clause should 
return such a value.  See <a href="#scanner">section 5</a> for
information on the default behavior if the <code>scan with</code>
section is omitted.<p>

As of CUP 0.10j the action code, parser code, init code, and scan with
sections may appear in any order. They must, however, precede the
symbol lists.</p><p>

petter's avatar
petter committed
488
</p><h4><a name="symbol_list"></a>2.3 Symbol Lists</h4>
petter's avatar
petter committed
489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530

Following user supplied code comes the first required part of the 
specification: the symbol lists.  These declarations are responsible 
for naming and supplying a type for each terminal and non-terminal
symbol that appears in the grammar.  As indicated above, each terminal
and non-terminal symbol is represented at runtime with a <tt>Symbol</tt>
object.  In
the case of terminals, these are returned by the scanner and placed on
the parse stack.  The lexer should put the value of the terminal in the
<tt>value</tt> instance variable.  
In the case of non-terminals these replace a series
of <tt>Symbol</tt> objects on the parse stack whenever the right hand side of
some production is recognized.  In order to tell the parser which object
types should be used for which symbol, <tt>terminal</tt> and 
<tt>non terminal</tt> declarations are used.  These take the forms:

<pre><tt>    terminal <i>classname</i> <i>name1, name2,</i> ...;</tt>
<tt>    non terminal <i>classname</i> <i>name1, name2,</i> ...;</tt>
<tt>    terminal <i>name1, name2,</i> ...;</tt>
</pre>

and

<pre><tt>    non terminal <i>name1, name2,</i> ...;</tt>
</pre>

where <tt><i>classname</i></tt> can be a multiple part name separated with
"."s.  The
<tt><i>classname</i></tt> specified represents the type of the value of
that terminal or non-terminal.  When accessing these values through
labels, the users uses the type declared. the <tt><i>classname</i></tt>
can be of any type.  If no <tt><i>classname</i></tt> is given, then the
terminal or non-terminal holds no value.  a label referring to such a
symbol with have a null value. As of CUP 0.10j, you may specify
non-terminals the declaration "<code>nonterminal</code>" (note, no
space) as well as the original "<code>non terminal</code>" spelling.<p>

Names of terminals and non-terminals cannot be CUP reserved words;
these include "code", "action", "parser", "terminal", "non",
"nonterminal", "init", "scan", "with", "start", "precedence", "left",
"right", "nonassoc", "import", and "package".</p><p>

petter's avatar
petter committed
531
</p><h4><a name="precedence"></a>2.4 Precedence and Associativity declarations</h4>
petter's avatar
petter committed
532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594

The third section, which is optional, specifies the precedences and
associativity of terminals.  This is useful for parsing with ambiguous
grammars, as done in the example above. There are three type of
precedence/associativity declarations:
<pre><tt>
	precedence left     <i>terminal</i>[, <i>terminal</i>...];
	precedence right    <i>terminal</i>[, <i>terminal</i>...];
	precedence nonassoc <i>terminal</i>[, <i>terminal</i>...];
</tt></pre>

The comma separated list indicates that those terminals should have the
associativity specified at that precedence level and the precedence of
that declaration.  The order of precedence, from highest to lowest, is
bottom to top.  Hence, this declares that multiplication and division have
higher precedence than addition and subtraction:
<pre><tt>
	precedence left  ADD, SUBTRACT;
	precedence left  TIMES, DIVIDE;
</tt></pre>
Precedence resolves shift reduce problems.  For example, given the input
to the above example parser <tt>3 + 4 * 8</tt>, the parser doesn't know
whether to reduce <tt>3 + 4</tt> or shift the '*' onto the stack.
However, since '*' has a higher precedence than '+', it will be shifted
and the multiplication will be performed before the addition.<p>

CUP assigns each one of its terminals a precedence according to these
declarations.  Any terminals not in this declaration have lowest
precedence.  CUP also assigns each of its productions a precedence.
That precedence is equal to the precedence of the last terminal in that
production.  If the production has no terminals, then it has lowest
precedence. For example, <tt>expr ::= expr TIMES expr</tt> would have
the same precedence as <tt>TIMES</tt>.  When there is a shift/reduce
conflict, the parser determines whether the terminal to be shifted has a
higher precedence, or if the production to reduce by does.  If the
terminal has higher precedence, it it shifted, if the production has
higher precedence, a reduce is performed.  If they have equal
precedence, associativity of the terminal determine what happens.</p><p>

An associativity is assigned to each terminal used in the
precedence/associativity declarations.  The three associativities are
<tt>left, right</tt> and <tt>nonassoc</tt>  Associativities are also
used to resolve shift/reduce conflicts, but only in the case of equal
precedences.  If the associativity of the terminal that can be shifted
is <tt>left</tt>, then a reduce is performed.  This means, if the input
is a string of additions, like <tt>3 + 4 + 5 + 6 + 7</tt>, the parser
will <i>always</i> reduce them from left to right, in this case,
starting with <tt>3 + 4</tt>.  If the associativity of the terminal is
<tt>right</tt>, it is shifted onto the stack.  hence, the reductions
will take place from right to left.  So, if PLUS were declared with
associativity of <tt>right</tt>, the <tt>6 + 7</tt> would be reduced
first in the above string.  If a terminal is declared as
<tt>nonassoc</tt>, then two consecutive occurrences of equal precedence
non-associative terminals generates an error.  This is useful for
comparison operations.  For example, if the input string is 
<tt>6 == 7 == 8 == 9</tt>, the parser should generate an error.  If '=='
is declared as <tt>nonassoc</tt> then an error will be generated. </p><p>

All terminals not used in the precedence/associativity declarations are
treated as lowest precedence.  If a shift/reduce error results,
involving two such terminals, it cannot be resolved, as the above
conflicts are, so it will be reported.</p><p>

petter's avatar
petter committed
595
</p><h4><a name="production_list"></a>2.5 The Grammar</h4>
petter's avatar
petter committed
596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615

The final section of a CUP declaration provides the grammar.  This 
section optionally starts with a declaration of the form:

<pre><tt>    start with <i>non-terminal</i>;</tt>
</pre>

This indicates which non-terminal is the <i>start</i> or <i>goal</i> 
non-terminal for parsing.  If a start non-terminal is not explicitly
declared, then the non-terminal on the left hand side of the first 
production will be used.  At the end of a successful parse, CUP returns
an object of type <tt>java_cup.runtime.Symbol</tt>.  This
<tt>Symbol</tt>'s value instance variable contains the final reduction
result.<p>

The grammar itself follows the optional <tt>start</tt> declaration.  Each
production in the grammar has a left hand side non-terminal followed by 
the symbol "<tt>::=</tt>", which is then followed by a series of zero or more
actions, terminal, or non-terminal
symbols, followed by an optional contextual precedence assignment, 
petter's avatar
petter committed
616
and terminated with a semicolon (;).</p>
petter's avatar
petter committed
617

petter's avatar
petter committed
618 619 620
<a name="label_part"></a>
<h5>2.5.1 Labels and locations for symbols</h5>
<p>Each symbol on the right hand side can optionally be labeled with a name.
petter's avatar
petter committed
621 622 623 624 625 626 627 628
Label names appear after the symbol name separated by a colon (:).  Label
names must be unique within the production, and can be used within action
code to refer to the value of the symbol.  Along with the label, two
more variables are created, which are the label plus <tt>left</tt> and
the label plus <tt>right</tt>.  These are <tt>int</tt> values that
contain the right and left locations of what the terminal or
non-terminal covers in the input file.  These values must be properly
initialized in the terminals by the lexer. The left and right values
petter's avatar
petter committed
629
then propagate to non-terminals to which productions reduce.</p><p>
petter's avatar
petter committed
630 631 632 633
If there are several productions for the same non-terminal they may be 
declared together.  In this case the productions start with the non-terminal 
and "<tt>::=</tt>".  This is followed by multiple right hand sides each 
separated by a bar (|).  The full set of productions is then terminated by a 
petter's avatar
petter committed
634 635 636 637 638 639 640 641 642 643 644
semicolon.</p>
<p>However, integers alone might not be good enough for locating symbols in
an input file. This is why CUP also supports more complex location information
in the form of <code>Location</code> objects. These objects need to be created
by the <a href="#advanced-symbols">scanner component</a>. They become available 
within the actions if the parser generator gets the right commandline parameter. 
They are accessible via the handles <code>??xleft</code> and <code>??xright</code>, 
with <code>??</code> being the label for the symbol.
</p>

<p>
petter's avatar
petter committed
645

petter's avatar
petter committed
646 647 648
<a name="action_part"></a>
<h5>2.5.2 User Actions</h5>
Actions appear in the right hand side as code strings (e.g., Java code inside
petter's avatar
petter committed
649 650 651 652
<tt>{:</tt> ... <tt>:}</tt> delimiters).  These are executed by the parser
at the point when the portion of the production to the left of the 
action has been recognized.  (Note that the scanner will have returned the 
token one past the point of the action since the parser needs this extra
petter's avatar
petter committed
653
<i>lookahead</i> token for recognition.)</p>
petter's avatar
petter committed
654

petter's avatar
petter committed
655 656
<a name="cpp"></a>
<h5>2.5.3 Contextual precedence</h5>
petter's avatar
petter committed
657

petter's avatar
petter committed
658
<p>Contextual precedence assignments follow all the symbols and actions of
petter's avatar
petter committed
659 660 661 662 663
the right hand side of the production whose precedence it is assigning.
Contextual precedence assignment allows a production to be assigned a
precedence not based on the last terminal in it.  A good example is
shown in the above sample parser specification:

petter's avatar
petter committed
664
</p><pre>
petter's avatar
petter committed
665 666 667 668 669 670 671
	precedence left PLUS, MINUS;
	precedence left TIMES, DIVIDE, MOD;
	precedence left UMINUS;

	expr ::=  MINUS expr:e             
	          {: RESULT = new Integer(0 - e.intValue()); :} 
	          %prec UMINUS
petter's avatar
petter committed
672
</pre>
petter's avatar
petter committed
673

petter's avatar
petter committed
674
<p>Here, there production is declared as having the precedence of UMINUS.
petter's avatar
petter committed
675 676
Hence, the parser can give the MINUS sign two different precedences,
depending on whether it is a unary minus or a subtraction operation. 
petter's avatar
petter committed
677
</p>
petter's avatar
petter committed
678

petter's avatar
petter committed
679 680
<a name="running"></a>
<h3>3. Running CUP</h3>
petter's avatar
petter committed
681 682 683 684 685 686 687
<h4>3.1 Command line interface</h4>
As mentioned above, CUP is written in Java.  To invoke it, one needs
to use the Java interpreter to invoke the static method 
<tt>java_cup.Main()</tt>, passing an array of strings containing options.  
Assuming a Unix machine, the simplest way to do this is typically to invoke it 
directly from the command line with a command such as: 

petter's avatar
petter committed
688
<pre><tt>    java -jar java-cup-11b.jar <i>options</i>  <i>inputfile</i></tt></pre>
petter's avatar
petter committed
689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804

Once running, CUP expects to find a specification file on standard input
and produces two Java source files as output. <p>

In addition to the specification file, CUP's behavior can also be changed
by passing various options to it.  Legal options are documented in
<code>Main.java</code> and include:
</p><dl>
  <dt><tt>-package</tt> <i>name</i>  
  </dt><dd>Specify that the <tt>parser</tt> and <tt>sym</tt> classes are to be 
       placed in the named package.  By default, no package specification 
       is put in the generated code (hence the classes default to the special 
       "unnamed" package).

  </dd><dt><tt>-parser</tt> <i>name</i>   
  </dt><dd>Output parser and action code into a file (and class) with the given
      name instead of the default of "<tt>parser</tt>".

  </dd><dt><tt>-symbols</tt> <i>name</i>  
  </dt><dd>Output the symbol constant code into a class with the given
      name instead of the default of "<tt>sym</tt>".

  </dd><dt><tt>-interface</tt>
  </dt><dd>Outputs the symbol constant code as an <code>interface</code>
      rather than as a <code>class</code>.

  </dd><dt><tt>-nonterms</tt>      
  </dt><dd>Place constants for non-terminals into the  symbol constant class.
      The parser does not need these symbol constants, so they are not normally
      output.  However, it can be very helpful to refer to these constants
      when debugging a generated parser.

  </dd><dt><tt>-expect</tt> <i>number</i>      
  </dt><dd>During parser construction the system may detect that an ambiguous 
      situation would occur at runtime.  This is called a <i>conflict</i>.  
      In general, the parser may be unable to decide whether to <i>shift</i> 
      (read another symbol) or <i>reduce</i> (replace the recognized right 
      hand side of a production with its left hand side).  This is called a 
      <i>shift/reduce conflict</i>.  Similarly, the parser may not be able 
      to decide between reduction with two different productions.  This is 
      called a <i>reduce/reduce conflict</i>.  Normally, if one or more of 
      these conflicts occur, parser generation is aborted.  However, in 
      certain carefully considered cases it may be advantageous to 
      arbitrarily break such a conflict.  In this case CUP uses YACC 
      convention and resolves shift/reduce conflicts by shifting, and 
      reduce/reduce conflicts using the "highest priority" production (the 
      one declared first in the specification).  In order to enable automatic 
      breaking of conflicts the <tt>-expect</tt> option must be given 
      indicating exactly how many conflicts are expected.  Conflicts
      resolved by precedences and associativities are not reported.

  </dd><dt><tt>-compact_red</tt>   
  </dt><dd>Including this option enables a table compaction optimization involving
      reductions.  In particular, it allows the most common reduce entry in 
      each row of the parse action table to be used as the default for that 
      row.  This typically saves considerable room in the tables, which can 
      grow to be very large.  This optimization has the effect of replacing 
      all error entries in a row with the default reduce entry.  While this 
      may sound dangerous, if not down right incorrect, it turns out that this 
      does not affect the correctness of the parser.  In particular, some
      changes of this type are inherent in LALR parsers (when compared to 
      canonical LR parsers), and the resulting parsers will still never 
      read past the first token at which the error could be detected.
      The parser can, however, make extra erroneous reduces before detecting
      the error, so this can degrade the parser's ability to do 
      <a href="#errors">error recovery</a>.
      (Refer to reference [2] pp. 244-247 or reference [3] pp. 190-194 for a 
      complete explanation of this compaction technique.) <br><br>

      This option is typically used to work-around the java bytecode
      limitations on table initialization code sizes.  However, CUP
      0.10h introduced a string-encoding for the parser tables which
      is not subject to the standard method-size limitations.
      Consequently, use of this option should no longer be required
      for large grammars.

  </dd><dt><tt>-nowarn</tt>        
  </dt><dd>This options causes all warning messages (as opposed to error messages)
      produced by the system to be suppressed.

  </dd><dt><tt>-nosummary</tt>     
  </dt><dd>Normally, the system prints a summary listing such things as the 
      number of terminals, non-terminals, parse states, etc. at the end of
      its run.  This option suppresses that summary.

  </dd><dt><tt>-progress</tt>      
  </dt><dd>This option causes the system to print short messages indicating its
      progress through various parts of the parser generation process.

  </dd><dt><tt>-dump_grammar</tt>  
  </dt><dt><tt>-dump_states</tt>   
  </dt><dt><tt>-dump_tables</tt>   
  </dt><dt><tt>-dump</tt>          
  </dt><dd> These options cause the system to produce a human readable dump of
       the grammar, the constructed parse states (often needed to resolve
       parse conflicts), and the parse tables (rarely needed), respectively.
       The <tt>-dump</tt> option can be used to produce all of these dumps.

  </dd><dt><tt>-time</tt>          
  </dt><dd>This option adds detailed timing statistics to the normal summary of
      results.  This is normally of great interest only to maintainers of 
      the system itself.

  </dd><dt><tt>-debug</tt>          
  </dt><dd>This option produces voluminous internal debugging information about
      the system as it runs.  This is normally of interest only to maintainers 
      of the system itself.

  </dd><dt><tt>-nopositions</tt>          
  </dt><dd>This option keeps CUP from generating code to propagate the left
      and right hand values of terminals to non-terminals, and then from
      non-terminals to other terminals.  If the left and right values aren't
      going to be used by the parser, then it will save some runtime
      computation to not generate these position propagations.  This option
      also keeps the left and right label variables from being generated, so
      any reference to these will cause an error.
805 806 807 808 809 810 811 812 813 814 815 816 817
  </dd><dt><tt>-locations</tt>          
  </dt><dd>This option makes CUP generate xleft/xright handles for
      accessing Location objects for symbol start/end inside actions.
  </dd><dt><tt>-xmlactions</tt>          
  </dt><dd>This option makes CUP generate generic actions that produce
      XMLElement-objects for any symbol, that is labeled by the CUP spec
      author. These objects directly mirror the according parse subtree. For this
      option, You will want to remove types from any symbol as well as
      ignore the RESULT-handle in any action, should you still want
      to perform any.
  </dd><dt><tt>-genericlabels</tt>          
  </dt><dd>This option goes one step further then -xmlactions by producing
      the full parse tree as XMLElement-tree.
petter's avatar
petter committed
818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835
  </dd><dt><tt>-noscanner</tt>
  </dt><dd>CUP 0.10j introduced <a href="#scanner">improved scanner
  integration</a> and a new interface,
  <code>java_cup.runtime.Scanner</code>.  By default, the 
  generated parser refers to this interface, which means you cannot
  use these parsers with CUP runtimes older than 0.10j.  If your
  parser does not use the new scanner integration features, then you
  may specify the <code>-noscanner</code> option to suppress the
  <code>java_cup.runtime.Scanner</code> references and allow
  compatibility with old runtimes.  Not many people should have reason
  to do this.

  </dd><dt><tt>-version</tt>
  </dt><dd>Invoking CUP with the <code>-version</code> flag will cause it
  to print out the working version of CUP and halt.  This allows
  automated CUP version checking for Makefiles, install scripts and
  other applications which may require it.
</dd></dl>
petter's avatar
petter committed
836
<a name="ant"></a>
petter's avatar
petter committed
837 838
<h4>3.2 Integrating CUP into an <a href="http://ant.apache.org/">ANT</a>
script</h4>
petter's avatar
petter committed
839 840
<p>To use cup in an ANT script, You have to add the following task definition to
Your <tt>build.xml</tt> file:</p>
petter's avatar
petter committed
841 842 843 844 845
<pre>&lt;taskdef name="cup"
  classname="java_cup.anttask.CUPTask"
  classpathref="cupclasspath"
/&gt;
</pre>
petter's avatar
petter committed
846 847
<p>Now, You are ready to use Your new &lt;cup/&gt; task to generate own parsers
from within ANT. Such a generation statement could look like:</p>
petter's avatar
petter committed
848 849 850 851 852 853 854
<pre>&lt;target name="cup"&gt;
&lt;cup srcfile="path/to/cupfile/Parser.cup"
  destdir="path/to/javafiles"
  interface="true"
/&gt;
&lt;/target&gt;
</pre>
petter's avatar
petter committed
855
<p>You can specify all commandline flags from chapter <bf>3.1</bf> as boolean
petter's avatar
petter committed
856
parameters to Your cuptask to achieve a similar behaviour (as done with
petter's avatar
petter committed
857
<tt>-interface</tt> in this little example).</p>
petter's avatar
petter committed
858

petter's avatar
petter committed
859 860
<a name="parser"></a>
<h3>4. Customizing the Parser</h3>
petter's avatar
petter committed
861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908

Each generated parser consists of three generated classes.  The 
<tt>sym</tt> class (which can be renamed using the <tt>-symbols</tt>
option) simply contains a series of <tt>int</tt> constants,
one for each terminal.  Non-terminals are also included if the <tt>-nonterms</tt>
option is given.  The source file for the <tt>parser</tt> class (which can
be renamed using the <tt>-parser</tt> option) actually contains two 
class definitions, the public <tt>parser</tt> class that implements the 
actual parser, and another non-public class (called <tt>CUP$action</tt>) which 
encapsulates all user actions contained in the grammar, as well as code from 
the <tt>action code</tt> declaration.  In addition to user supplied code, this
class contains one method: <tt>CUP$do_action</tt> which consists of a large 
switch statement for selecting and executing various fragments of user 
supplied action code.  In general, all names beginning with the prefix of 
<tt>CUP$</tt> are reserved for internal uses by CUP generated code. <p> 

The <tt>parser</tt> class contains the actual generated parser.  It is 
a subclass of <tt>java_cup.runtime.lr_parser</tt> which implements a 
general table driven framework for an LR parser.  The generated <tt>parser</tt>
class provides a series of tables for use by the general framework.  
Three tables are provided:
</p><dl compact="compact">
<dt>the production table 
</dt><dd>provides the symbol number of the left hand side non-terminal, along with
    the length of the right hand side, for each production in the grammar,
</dd><dt>the action table
</dt><dd>indicates what action (shift, reduce, or error) is to be taken on each 
    lookahead symbol when encountered in each state, and
</dd><dt>the reduce-goto table
</dt><dd>indicates which state to shift to after reduces (under each non-terminal
from each state). 
</dd></dl>
(Note that the action and reduce-goto tables are not stored as simple arrays,
but use a compacted "list" structure to save a significant amount of space.
See comments the runtime system source code for details.)<p>

Beyond the parse tables, generated (or inherited) code provides a series 
of methods that can be used to customize the generated parser.  Some of these
methods are supplied by code found in part of the specification and can 
be customized directly in that fashion.  The others are provided by the
<tt>lr_parser</tt> base class and can be overridden with new versions (via
the <tt>parser code</tt> declaration) to customize the system.  Methods
available for customization include:
</p><dl compact="compact">
<dt><tt>public void user_init()</tt>
</dt><dd>This method is called by the parser prior to asking for the first token 
    from the scanner.  The body of this method contains the code from the 
    <tt>init with</tt> clause of the the specification.  
909
</dd><dt><a name="scan_method"></a><tt>public java_cup.runtime.Symbol scan()</tt>
petter's avatar
petter committed
910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930
</dt><dd>This method encapsulates the scanner and is called each time a new
    terminal is needed by the parser.  The body of this method is 
    supplied by the <tt>scan with</tt> clause of the specification, if
    present; otherwise it returns <code>getScanner().next_token()</code>.
</dd><dt><tt>public java_cup.runtime.Scanner getScanner()</tt>
</dt><dd>Returns the default scanner.  See <a href="#scanner">section 5</a>.
</dd><dt><tt>public void setScanner(java_cup.runtime.Scanner s)</tt>
</dt><dd>Sets the default scanner.  See <a href="#scanner">section 5</a>.
</dd><dt><tt> public void report_error(String message, Object info)</tt>
</dt><dd>This method should be called whenever an error message is to be issued.  In
    the default implementation of this method, the first parameter provides 
    the text of a message which is printed on <tt>System.err</tt> 
    and the second parameter is simply ignored.  It is very typical to
    override this method in order to provide a more sophisticated error
    reporting mechanism.
</dd><dt><tt>public void report_fatal_error(String message, Object info)</tt>
</dt><dd>This method should be called whenever a non-recoverable error occurs.  It 
    responds by calling <tt>report_error()</tt>, then aborts parsing
    by calling the parser method <tt>done_parsing()</tt>, and finally
    throws an exception.  (In general <tt>done_parsing()</tt> should be called 
    at any point that parsing needs to be terminated early).
931 932 933 934 935 936 937 938 939 940 941 942 943
</dd><dt><tt>public List<Integer> expected_token_ids()</tt>
</dt><dd>This method informs during parsing and especially when handling
    parsing problems and invalid input about valid continuations for parsing.
    It returns a list of integer constants which correspond to the constants
    in the generated <tt>sym.java</tt>. You can retranslate the ids to their
    string representations, which where used in the grammar specification to
    declare (non)terminal names, with <tt>symbol_name_from_id(id)</tt>
    This can be typically used to implement syntax completion or more detailed
    error messages.
</dd><dt><tt>public String symbol_name_from_id(int id)</tt>
</dt><dd>This method translates numerical constants, representing symbol ids 
    back to their textual representation, declared in the <tt>.cup</tt>
    parser specification file.
petter's avatar
petter committed
944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995
</dd><dt><tt>public void syntax_error(Symbol cur_token)</tt>
</dt><dd>This method is called by the parser as soon as a syntax error is detected
    (but before error recovery is attempted).  In the default implementation it
    calls: <tt>report_error("Syntax error", null);</tt>.
</dd><dt><tt>public void unrecovered_syntax_error(Symbol cur_token)</tt>
</dt><dd>This method is called by the parser if it is unable to recover from a 
    syntax error.  In the default implementation it calls:
    <tt>report_fatal_error("Couldn't repair and continue parse", null);</tt>.
</dd><dt><tt> protected int error_sync_size()</tt>
</dt><dd>This method is called by the parser to determine how many tokens it must
    successfully parse in order to consider an error recovery successful.
    The default implementation returns 3.  Values below 2 are not recommended.
    See the section on <a href="#errors">error recovery</a> for details.
</dd></dl>

Parsing itself is performed by the method <tt>public Symbol parse()</tt>.  
This method starts by getting references to each of the parse tables, 
then initializes a <tt>CUP$action</tt> object (by calling 
<tt>protected void init_actions()</tt>). Next it calls <tt>user_init()</tt>,
then fetches the first lookahead token with a call to <tt>scan()</tt>.
Finally, it begins parsing.  Parsing continues until <tt>done_parsing()</tt>
is called (this is done automatically, for example, when the parser
accepts).  It then returns a <tt>Symbol</tt> with the <tt>value</tt>
instance variable containing the RESULT of the start production, or
<tt>null</tt>, if there is no value.<p>

In addition to the normal parser, the runtime system also provides a debugging
version of the parser.  This operates in exactly the same way as the normal
parser, but prints debugging messages (by calling 
<tt>public void debug_message(String mess)</tt> whose default implementation
prints a message to <tt>System.err</tt>).</p><p>

Based on these routines, invocation of a CUP parser is typically done
with code such as:
</p><pre>      /* create a parsing object */
      parser parser_obj = new parser();

      /* open input files, etc. here */
      Symbol parse_tree = null;

      try {
        if (do_debug_parse)
          parse_tree = parser_obj.debug_parse();
        else
          parse_tree = parser_obj.parse();
      } catch (Exception e) {
        /* do cleanup here - - possibly rethrow e */
      } finally {
	/* do close out here */
      }
</pre>

petter's avatar
petter committed
996 997
<a name="scanner"></a>
<h3>5. Scanner Interface</h3>
petter's avatar
petter committed
998

petter's avatar
petter committed
999
<a name="basic-symbols" ></a>
petter's avatar
petter committed
1000 1001
<h4>5.1 Basic Symbol management</h4>

petter's avatar
petter committed
1002
<p>In CUP 0.10j, scanner integration was improved according to
petter's avatar
petter committed
1003 1004
suggestions made by <a href="http://www.smartsc.com/">David MacMahon</a>.
The changes make it easier to incorporate JLex and other
petter's avatar
petter committed
1005
automatically-generated scanners into CUP parsers.</p>
petter's avatar
petter committed
1006

petter's avatar
petter committed
1007
<p>To use the new code, your scanner should implement the
petter's avatar
petter committed
1008
<code>java_cup.runtime.Scanner</code> interface, defined as:
petter's avatar
petter committed
1009 1010 1011
</p>
<pre>
package java_cup.runtime;
petter's avatar
petter committed
1012 1013 1014 1015

public interface Scanner {
    public Symbol next_token() throws java.lang.Exception;
}
petter's avatar
petter committed
1016 1017
</pre>
<p>
petter's avatar
petter committed
1018 1019 1020 1021 1022 1023 1024 1025
In addition to the methods described in <a href="#parser">section
4</a>, the <code>java_cup.runtime.lr_parser</code> class has two new
accessor methods, <code>setScanner()</code> and <code>getScanner()</code>.
The default implementation of <a href="#scan_method"><code>scan()</code></a>
is:
</p><pre>  public Symbol scan() throws java.lang.Exception {
    return getScanner().next_token();
  }
petter's avatar
petter committed
1026 1027
</pre>
<p>
petter's avatar
petter committed
1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058
The generated parser also contains a constructor which takes a
<code>Scanner</code> and calls <code>setScanner()</code> with it. In
most cases, then, the <code>init with</code> and <code>scan
with</code> directives may be omitted.  You can simply create the
parser with a reference to the desired scanner:
</p><pre>      /* create a parsing object */
      parser parser_obj = new parser(new my_scanner());
</pre>
or set the scanner after the parser is created:
<pre>      /* create a parsing object */
      parser parser_obj = new parser();
      /* set the default scanner */
      parser_obj.setScanner(new my_scanner());
</pre><p>
Note that because the parser uses look-ahead, resetting the scanner in
the middle of a parse is not recommended. If you attempt to use the
default implementation of <code>scan()</code> without first calling
<code>setScanner()</code>, a <code>NullPointerException</code> will be
thrown.</p><p>
As an example of scanner integration, the following three lines in the
lexer-generator input are all that is required to use a 
<a href="http://www.cs.princeton.edu/%7Eappel/modern/java/JLex/">JLex</a>
scanner with CUP:
</p><pre>%implements java_cup.runtime.Scanner
%function next_token
%type java_cup.runtime.Symbol
</pre>
It is anticipated that the JLex directive <code>%cup</code> will
abbreviate the above three directive in the next version of JLex.
Invoking the parser with the JLex scanner is then simply:
<pre>parser parser_obj = new parser( new Yylex( some_InputStream_or_Reader));
petter's avatar
petter committed
1059
</pre>
petter's avatar
petter committed
1060

petter's avatar
petter committed
1061
<p>
petter's avatar
petter committed
1062 1063 1064 1065 1066 1067 1068 1069 1070 1071
Note that you still have to handle EOF correctly; the JLex code to do
so is something like:
</p><pre>%eofval{
  return sym.EOF;
%eofval}
</pre>
where <code>sym</code> is the name of the symbol class for your
generated parser.<p>

The simple_calc example in the CUP distribution illustrates the use of
petter's avatar
petter committed
1072
the scanner integration features with a hand-coded scanner.</p>
petter's avatar
petter committed
1073

1074
<a name="advanced-symbols"></a>
petter's avatar
petter committed
1075 1076 1077 1078
<h4>5.2 Advanced Symbol management</h4>

<p>Since CUP v11a we offer the possibility of advanced symbol handling in CUP.
Therefore, You can implement Your own SymbolFactory, derived from
petter's avatar
petter committed
1079
<code>java_cup.runtime.SymbolFactory</code>, and have CUP manage Your own type of
petter's avatar
petter committed
1080
symbols. We've done that for You already in the pre-defined
petter's avatar
petter committed
1081
<code>java_cup.runtime.ComplexSymbolFactory</code>, which provides support for
1082
detailed location information in the symbol class. Just have a look at CUP's own
petter's avatar
petter committed
1083
<code>Lexer.jflex</code>, which is already using the new feature.</p>
petter's avatar
petter committed
1084 1085 1086 1087 1088 1089 1090 1091

<p>All You have to do is providing Your CUP-generated parser with the new
SymbolFactory which can be done like this:</p>
<pre>
SymbolFactory symbolFactory = new ComplexSymbolFactory();
MyParser parser = new MyParser(new Lexer(inputfile,symbolFactory),symbolFactory); 
</pre>

1092 1093 1094 1095 1096 1097 1098
<p>The <code>ComplexSymbolFactory</code> is used straight-forward: In Your
lexer, instead of directly creating <code>Symbol</code>-Objects, You call
the factory's creation methods, called <code>newSymbol(...)</code>.</p>

<p>Most of the times, You will want to use just the <code>ComplexSymbolFactory</code>.
You can do that, by adding convenience methods into Your parser's body, like the following one
for symobls with an attached String-value:</p>
petter's avatar
petter committed
1099
<pre>
1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114
 public Symbol symbol(String plainname, int terminalcode, String lexem){
    return symbolFactory.newSymbol(plainname, terminalcode, new Location(yyline+1, yycolumn +1), new Location(yyline+1,yycolumn+yylength()), lexem);
 }
</pre>
<p>The <code>Location</code>-Objects provide a convenient way to manage detailed 
position informations for Your symbols. In order to use them in Your action specifications,
don't forget to set the <code>-locations</code>-commandline-parameter when running CUP!
This generates into the frame of each production no plain integer values (referred to via <code>??left,??right</code>,
with ?? being Your symbol name) any more, but Your beloved Location objects (<code>??xleft,??xright</code>, again
with ?? Your symbol's name). You can then access all its information like this:</p>
<pre>
expr      ::= expr:e1 PLUS expr:e2    
	      {: RESULT = BinExpr.createAdd(e1,e2);           :} 
	      | NUMBER:n                 
	      {: RESULT = Expr.createConst(nxleft,n,nxright); :}
petter's avatar
petter committed
1115
</pre>
1116 1117 1118 1119 1120 1121 1122 1123
<p>In the example, we create an expression tree from our input language. Here,
we store the location information for the subexpressions in the AST. 
This can be seen in the action for the <code>NUMBER</code>, where we access
<code>nxleft</code> and <code>nxright</code>. Note, that in this example we
only store the locations of leaves directly. In a convenient implementation
of the AST, we would expect a recursive function, that computes the locations for each
intermediary node in the tree.
</p>
petter's avatar
petter committed
1124

petter's avatar
petter committed
1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142
<a name="symbolstream-caching"></a>
<h4>5.3 Symbolstream caching</h4>

<p>CUP offers an additional layer between scanner and parser, in order to cache the
actual sequence of terminal symbols, provided by the scanner for potential later use.
This comes in handy, if e.g. a pretty printer or syntax highlighter is applied.</p>

<p>Given that the <code>Lexer</code> class implements CUP's <code>Scanner</code>
interface, we can buffer its output with the <code>ScannerBuffer</code> and access
the tokenstream with <code>getBuffered()</code>, once the parsing is finished:</p>
<pre>
Scanner scanner = new Lexer();
ScannerBuffer buffer = new ScannerBuffer(lexer);
Parser p = new Parser(buffer,new ComplexSymbolFactory);
p.parse();
System.out.println(buffer.getBuffered());
</pre>

1143 1144
<a name="errors"></a>
<h3>6. Error Recovery</h3>
petter's avatar
petter committed
1145 1146
<a name="error_sym"></a>
<h4>6.1 The error symbol</h4>
petter's avatar
petter committed
1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195
A final important aspect of building parsers with CUP is 
support for syntactic error recovery.  CUP uses the same 
error recovery mechanisms as YACC.  In particular, it supports
a special error symbol (denoted simply as <tt>error</tt>).
This symbol plays the role of a special non-terminal which, instead of
being defined by productions, instead matches an erroneous input 
sequence.</p><p>

The error symbol only comes into play if a syntax error is
detected.  If a syntax error is detected then the parser tries to replace
some portion of the input token stream with <tt>error</tt> and then
continue parsing.  For example, we might have productions such as:

</p><pre><tt>    stmt ::= expr SEMI | while_stmt SEMI | if_stmt SEMI | ... |
	     error SEMI
	     ;</tt></pre>

This indicates that if none of the normal productions for <tt>stmt</tt> can
be matched by the input, then a syntax error should be declared, and recovery
should be made by skipping erroneous tokens (equivalent to matching and 
replacing them with <tt>error</tt>) up to a point at which the parse can 
be continued with a semicolon (and additional context that legally follows a 
statement).  An error is considered to be recovered from if and only if a 
sufficient number of tokens past the <tt>error</tt> symbol can be successfully 
parsed.  (The number of tokens required is determined by the 
<tt>error_sync_size()</tt> method of the parser and defaults to 3). <p>

Specifically, the parser first looks for the closest state to the top
of the parse stack that has an outgoing transition under
<tt>error</tt>.  This generally corresponds to working from
productions that represent more detailed constructs (such as a specific
kind of statement) up to productions that represent more general or
enclosing constructs (such as the general production for all
statements or a production representing a whole section of declarations) 
until we get to a place where an error recovery production
has been provided for.  Once the parser is placed into a configuration
that has an immediate error recovery (by popping the stack to the first
such state), the parser begins skipping tokens to find a point at
which the parse can be continued.  After discarding each token, the
parser attempts to parse ahead in the input (without executing any
embedded semantic actions).  If the parser can successfully parse past
the required number of tokens, then the input is backed up to the point
of recovery and the parse is resumed normally (executing all actions).
If the parse cannot be continued far enough, then another token is
discarded and the parser again tries to parse ahead.  If the end of
input is reached without making a successful recovery (or there was no
suitable error recovery state found on the parse stack to begin with)
then error recovery fails.

petter's avatar
petter committed
1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214
<a name="continuation_symbols"></a>
<h4>6.2 Viable continuation Symbols</h4>
<p>In case of parsing errors, CUP offers support in delivering meaningful
user feedback. Consider that the specified parser is to be applied in a
fancy IDE which registers parsing errors and makes propositions, on how
to fix these errors. In these cases, an implementation for the action code
of an error symbol could consist in telling the IDE about the exact
location of the unmatched input, as well as the list of viable symbols, with
which the parser can advance a step in the current state, reaching an
accepting state. These symbols are coded as integers, and can be decoded to
their string representations via calls to <code>symbol_name_from_id()</code>.
Such an action can look like:</p>
<pre><tt>    stmt ::= expr SEMI | while_stmt SEMI | if_stmt SEMI | ... |
	     error:e {: 
                 List<Integer> expected = expected_token_ids();
                 myIDE.registerParseError(exleft,exright,expected);
             :} SEMI
	     ;</tt></pre>

1215 1216
<a name="conclusion"></a>
<h3>7. Conclusion</h3>
petter's avatar
petter committed
1217 1218 1219 1220 1221 1222 1223 1224 1225

This manual has briefly described the CUP LALR parser generation system.
CUP is designed to fill the same role as the well known YACC parser
generator system, but is written in and operates entirely with Java code 
rather than C or C++.  Additional details on the operation of the system can 
be found in the parser generator and runtime source code.  See the CUP
home page below for access to the API documentation for the system and its
runtime.</p><p>

1226
This document covers version 0.11b of the system.  Check the CUP home
petter's avatar
petter committed
1227
page:
1228 1229
<a href="http://www2.in.tum.de/projects/cuptum">
http://www2.in.tum.de/projects/cuptum/</a>
petter's avatar
petter committed
1230 1231 1232
for the latest release information, instructions for downloading the
system, and additional news about CUP.  Bug reports and other 
comments for the developers should be sent to the CUP maintainer, 
1233 1234 1235 1236 1237
M. Petter, at
<a href="mailto:petterATcs.tum.edu">
petterATcs.tum.edu</a></p><p>

Before this, it was maintained by
petter's avatar
petter committed
1238
C. Scott Ananian, at
1239
<a href="cananian@alumni.princeton.edu">
petter's avatar
petter committed
1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254
cananian@alumni.princeton.edu</a></p><p>

CUP was originally written by 
<a href="http://www.cs.cmu.edu/%7Ehudson/">
Scott Hudson</a>, in August of 1995.</p><p>

It was extended to support precedence by 
<a href="http://www.princeton.edu/%7Efrankf">
Frank Flannery</a>, in July of 1996.</p><p>

On-going improvements have been done by
<a href="http://www.pdos.lcs.mit.edu/%7Ecananian">
C. Scott Ananian</a>, the CUP maintainer, from December of 1997 to the
present.</p><p>

1255 1256
<a name="refs"></a>
<h3>References</h3>
petter's avatar
petter committed
1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282
</p><dl compact="compact">

<dt><a name="YACCref">[1]</a> 
</dt><dd>S. C. Johnson, 
"YACC &amp;emdash; Yet Another Compiler Compiler",
CS Technical Report #32, 
Bell Telephone Laboratories,  
Murray Hill, NJ, 
1975.

</dd><dt><a name="dragonbook">[2]</a> 
</dt><dd>A. Aho, R. Sethi, and J. Ullman, 
<i>Compilers: Principles, Techniques, and Tools</i>, 
Addison-Wesley Publishing,
Reading, MA, 
1986.

</dd><dt><a name="crafting">[3]</a> 
</dt><dd>C. Fischer, and R. LeBlanc,
<i>Crafting a Compiler with C</i>,
Benjamin/Cummings Publishing,
Redwood City, CA,
1991.

</dd></dl>

1283
<h3><a name="appendixa" />
petter's avatar
petter committed
1284 1285
Appendix A. Grammar for CUP Specification Files</a> (0.10j)</h3>
<hr><br>
1286
<pre><tt>java_cup_spec      ::= package_spec import_list class_name code_parts
petter's avatar
petter committed
1287 1288 1289 1290 1291
		       symbol_list precedence_list start_spec 
		       production_list
package_spec       ::= PACKAGE multipart_id SEMI | empty
import_list        ::= import_list import_spec | empty
import_spec        ::= IMPORT import_id SEMI
1292
class_name         ::= CLASS ID SEMI | empty
petter's avatar
petter committed
1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341
code_part          ::= action_code_part | parser_code_part |
                       init_code | scan_code
code_parts         ::= code_parts code_part | empty
action_code_part   ::= ACTION CODE CODE_STRING opt_semi
parser_code_part   ::= PARSER CODE CODE_STRING opt_semi
init_code          ::= INIT WITH CODE_STRING opt_semi
scan_code          ::= SCAN WITH CODE_STRING opt_semi
symbol_list        ::= symbol_list symbol | symbol
symbol             ::= TERMINAL type_id declares_term |
                       NON TERMINAL type_id declares_non_term |
		       NONTERMINAL type_id declares_non_term |
		       TERMINAL declares_term |
		       NON TERMINAL declares_non_term |
		       NONTERMIANL declared_non_term
term_name_list     ::= term_name_list COMMA new_term_id | new_term_id
non_term_name_list ::= non_term_name_list COMMA new_non_term_id |
	               new_non_term_id
declares_term      ::= term_name_list SEMI
declares_non_term  ::= non_term_name_list SEMI
precedence_list    ::= precedence_l | empty
precedence_l       ::= precedence_l preced + preced;
preced             ::= PRECEDENCE LEFT terminal_list SEMI
	               | PRECEDENCE RIGHT terminal_list SEMI
	               | PRECEDENCE NONASSOC terminal_list SEMI
terminal_list      ::= terminal_list COMMA terminal_id | terminal_id 
start_spec         ::= START WITH nt_id SEMI | empty
production_list    ::= production_list production | production
production         ::= nt_id COLON_COLON_EQUALS rhs_list SEMI
rhs_list           ::= rhs_list BAR rhs | rhs
rhs                ::= prod_part_list PERCENT_PREC term_id |
                       prod_part_list
prod_part_list     ::= prod_part_list prod_part | empty
prod_part          ::= symbol_id opt_label | CODE_STRING
opt_label          ::= COLON label_id | empty
multipart_id       ::= multipart_id DOT ID | ID
import_id          ::= multipart_id DOT STAR | multipart_id
type_id            ::= multipart_id
terminal_id        ::= term_id
term_id            ::= symbol_id
new_term_id        ::= ID
new_non_term_id    ::= ID
nt_id              ::= ID
symbol_id          ::= ID
label_id           ::= ID
opt_semi	   ::= SEMI | empty

</tt></pre>
<hr><p></p><p>

petter's avatar
petter committed
1342
</p><h3><a name="appendixb"></a>Appendix B. A Very Simple Example Scanner</h3>
1343 1344
<hr><br>
<pre><tt>// Simple Example Scanner Class
petter's avatar
petter committed
1345 1346 1347 1348 1349 1350 1351

import java_cup.runtime.*;
import sym;

public class scanner {
  /* single lookahead character */
  protected static int next_char;
petter's avatar
petter committed
1352 1353
  // since cup v11 we use SymbolFactories rather than Symbols
  private SymbolFactory sf = new DefaultSymbolFactory();
petter's avatar
petter committed
1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379

  /* advance input by one character */
  protected static void advance()
    throws java.io.IOException
    { next_char = System.in.read(); }

  /* initialize the scanner */
  public static void init()
    throws java.io.IOException
    { advance(); }

  /* recognize and return the next complete token */
  public static Symbol next_token()
    throws java.io.IOException
    {
      for (;;)
        switch (next_char)
	  {
	    case '0': case '1': case '2': case '3': case '4': 
	    case '5': case '6': case '7': case '8': case '9': 
	      /* parse a decimal integer */
	      int i_val = 0;
	      do {
	        i_val = i_val * 10 + (next_char - '0');
	        advance();
	      } while (next_char &gt;= '0' &amp;&amp; next_char &lt;= '9');
petter's avatar
petter committed
1380
	    return sf.newSymbol("NUMBER",sym.NUMBER, new Integer(i_val));
petter's avatar
petter committed
1381

petter's avatar
petter committed
1382 1383 1384 1385 1386 1387 1388 1389
	    case ';': advance(); return sf.newSymbol("SEMI",sym.SEMI);
	    case '+': advance(); return sf.newSymbol("PLUS",sym.PLUS);
	    case '-': advance(); return sf.newSymbol("MINUS",sym.MINUS);
	    case '*': advance(); return sf.newSymbol("TIMES",sym.TIMES);
	    case '/': advance(); return sf.newSymbol("DIVIDE",sym.DIVIDE);
	    case '%': advance(); return sf.newSymbol("MOD",sym.MOD);
	    case '(': advance(); return sf.newSymbol("LPAREN",sym.LPAREN);
	    case ')': advance(); return sf.newSymbol("RPAREN",sym.RPAREN);
petter's avatar
petter committed
1390

petter's avatar
petter committed
1391
	    case -1: return return sf.newSymbol("EOF",sym.EOF);
petter's avatar
petter committed
1392 1393 1394 1395 1396 1397 1398 1399

	    default: 
	      /* in this simple scanner we just ignore everything else */
	      advance();
	    break;
	  }
    }
};
1400
</tt></pre>
petter's avatar
petter committed
1401 1402


1403
<a name="changes" /><h3><a name="changes">Appendix C:  Incompatibilites between CUP 0.9 and CUP 0.10</a></h3>
petter's avatar
petter committed
1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419

CUP version 0.10a is a major overhaul of CUP.  The changes are severe,
meaning no backwards compatibility to older versions.

The changes consist of:
<ul>
<li> <a href="#lex_inter">A different lexical interface</a>,
</li><li> <a href="#new_dec">New terminal/non-terminal declarations</a>,
</li><li> <a href="#label_ref">Different label references</a>,
</li><li> <a href="#RESULT_pass">A different way of passing RESULT</a>,
</li><li> <a href="#pos_prop">New position values and propagation</a>,
</li><li> <a href="#ret_val">Parser now returns a value</a>,
</li><li> <a href="#prec_add">Terminal precedence declarations</a> and
</li><li> <a href="#con_prec">Rule contextual precedence assignment</a>
</li></ul>

1420
<h5><a name="lex_inter"></a>Lexical Interface</h5>
petter's avatar
petter committed
1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582

CUP now interfaces with the lexer in a completely different
manner.  In the previous releases, a new class was used for every
distinct type of terminal.  This release, however, uses only one class:
The <tt>Symbol</tt> class.  The <tt>Symbol</tt> class has three instance
variables which 
are significant to the parser when passing information from the lexer.
The first is the <tt>value</tt> instance variable.  This variable 
contains the 
value of that terminal.  It is of the type declared as the terminal type
in the parser specification file.  The second two are the instance
variables <tt>left</tt> and <tt>right</tt>.  They should be filled with 
the <tt>int</tt> value of
where in the input file, character-wise, that terminal was found.<p>

For more information, refer to the manual on <a href="#lex_part">scanners</a>.

</p><h5><a name="new_dec">Terminal/Non-Terminal Declarations</a></h5>

Terminal and non-terminal declarations now can be declared in two
different ways to indicate the values of the terminals or
non-terminals.  The previous declarations of the form

<pre><tt>
terminal <i>classname terminal</i> [, <i>terminal ...</i>];
</tt></pre> 

still works.  The classname, however indicates the type of the value of
the terminal or non-terminal, and does not indicate the type of object
placed on the parse stack.

A declaration, such as:

<pre><tt>
terminal <i>terminal</i> [, <i>terminal ...</i>];
</tt></pre> 

indicates the terminals in the list hold no value.<p>

For more information, refer to the manual on <a href="#symbol_list">declarations</a>.

</p><h5><a name="label_ref">Label References</a></h5>

Label references do not refer to the object on the parse stack, as in
the old CUP, but rather to the value of the <tt>value</tt> 
instance variable of
the <tt>Symbol</tt> that represents that terminal or non-terminal.  Hence,
references to terminal and non-terminal values is direct, as opposed to
the old CUP, where the labels referred to objects containing the value
of the terminal or non-terminal.<p>

For more information, refer to the manual on <a href="#label_part">labels</a>.

</p><h5><a name="RESULT_pass">RESULT Value</a></h5>

The <tt>RESULT</tt> variable refers directly to the value of the 
non-terminal
to which a rule reduces, rather than to the object on the parse stack.
Hence, <tt>RESULT</tt> is of the same type the non-terminal to which 
it reduces, 
as declared in the non-terminal declaration.  Again, the reference is
direct, rather than to something that will contain the data.<p>

For more information, refer to the manual on <a href="#RES_part">RESULT</a>.

</p><h5><a name="pos_prop">Position Propagation</a></h5>

For every label, two more variables are declared, which are the label
plus <tt>left</tt> or the label plus <tt>right</tt>.  These correspond 
to the left and
right locations in the input stream to which that terminal or
non-terminal came from.  These values are propagated from the input
terminals, so that the starting non-terminal should have a left value of
0 and a right value of the location of the last character read.<p>

For more information, refer to the manual on <a href="#label_part">positions</a>. 

</p><h5><a name="ret_val">Return Value</a></h5>

A call to <tt>parse()</tt> or <tt>debug_parse()</tt> returns a
Symbol.  This Symbol is the start non-terminal, so the <tt>value</tt> 
instance variable contains the final <tt>RESULT</tt> assignment. 

<h5><a name="prec_add">Precedence</a></h5>

CUP now has precedenced terminals.  a new declaration section,
occurring between the terminal and non-terminal declarations and the
grammar specifies the precedence and associativity of rules.  The
declarations are of the form:

<pre><tt>
precedence {left| right | nonassoc} <i>terminal</i>[, <i>terminal</i> ...];
...
</tt>
</pre>

The terminals are assigned a precedence, where terminals on the same
line have equal precedences, and the precedence declarations farther
down the list of precedence declarations have higher precedence.  
<tt>left, right</tt> and <tt>nonassoc</tt> specify the associativity 
of these terminals.  left
associativity corresponds to a reduce on conflict, right to a shift on
conflict, and nonassoc to an error on conflict.  Hence, ambiguous
grammars may now be used.<p>  

For more information, refer to the manual on <a href="#precedence">precedence</a>.

</p><h5><a name="con_prec">Contextual Precedence</a></h5>

Finally the new CUP adds contextual precedence.  A production may be
declare as followed:

<pre><tt>
lhs ::= <i>{right hand side list of terminals, non-terminals and actions}</i>
        %prec <i>{terminal}</i>;
</tt></pre>

this production would then have a precedence equal to the terminal
specified after the <tt>%prec</tt>.  Hence, shift/reduce conflicts can be
contextually resolved.  Note that the <tt>%prec</tt> <i>terminal</i> 
part comes after all actions strings.  It does not come before the 
last action string.<p>

For more information, refer to the manual on <a href="#cpp">contextual
precedence</a>.

These changes implemented by:
</p><h3>
<a href="http://www.princeton.edu/%7Efrankf">Frank Flannery</a><br>
<a href="http://www.cs.princeton.edu/">Department of Computer Science</a><br>
<a href="http://www.princeton.edu/">Princeton University</a><br>
</h3>
<a name="bugs">
</a><h3><a name="bugs">Appendix D:  Bugs</a></h3>
In this version of CUP it's difficult for the semantic action phrases (Java code attached
to productions) to access the <tt>report_error</tt> method and other similar methods and
objects defined in the <tt>parser code</tt> directive.
<p>
This is because the parsing tables (and parsing engine) are in one object (belonging to
class <tt>parser</tt> or whatever name is specified by the <strong>-parser</strong> directive),
and the semantic actions are in another object (of class <tt>CUP$actions</tt>).
</p><p>
However, there is a way to do it, though it's a bit inelegant.
The action object has a <tt>private final</tt> field named
<tt>parser</tt> that points to the parsing object.  Thus,
methods and instance variables of the parser can be accessed within semantic actions as:
</p><pre>    parser.report_error(message,info);
    x = parser.mydata;
</pre>
<p>
Perhaps this will not be necessary in a future release, and that
such methods and variables as <tt>report_error</tt> and
<tt>mydata</tt> will be available
directly from the semantic actions; we will achieve this by combining the 
"parser" object and the "actions" object together.
 
</p><p>
For a list of any other currently known bugs in CUP, see
<a href="http://www.cs.princeton.edu/%7Eappel/modern/java/CUP/bugs.html">
http://www.cs.princeton.edu/~appel/modern/java/CUP/bugs.html</a>.

<a name="version">
1583
</a></p><h3>Appendix E:  Change log</h3>
petter's avatar
petter committed
1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610

<dl>
<dt>0.9e</dt><dd>March 1996, Scott Hudson's original version.
</dd><dt>0.10a</dt><dd>August 1996, <a href="#about">several major changes</a> to
the interface.
</dd><dt>0.10b</dt><dd>November 1996, fixes a few minor bugs.
</dd><dt>0.10c</dt><dd>July 1997, fixes a bug related to precedence declarations.
</dd><dt>0.10e</dt><dd>September 1997, fixes a bug introduced in 0.10c relating
to <tt>nonassoc</tt> precedence.  Thanks to 
<a href="http://www.cs.purdue.edu/homes/hosking">Tony Hosking</a> 
for reporting the bug and providing the fix.
Also recognizes carriage-return character as white space and fixes a
number of other small bugs.
</dd><dt>0.10f</dt><dd>December 1997, was a maintenance release.  The CUP source
was cleaned up for JDK 1.1.
</dd><dt>0.10g</dt><dd>March 1998, adds new features and fixes old bugs.
The behavior of RESULT assignments was normalized, and a problem
with implicit start productions was fixed.  The CUP grammar was
extended to allow array types for terminals and non-terminals, and
a command-line flag was added to allow the generation of a symbol
<i>interface</i>, rather than class.  Bugs associated with multiple
invocations of a single parser object and multiple CUP classes in one 
package have been stomped on.  Documentation was updated, as well.
</dd><dt>0.10h-0.10i</dt><dd>February 1999, are maintenance releases.
</dd><dt>0.10j</dt><dd>July 1999, broadened the CUP input grammar to allow more
flexibility and improved scanner integration via the
<code>java_cup.runtime.Scanner</code> interface.
petter's avatar
petter committed
1611 1612 1613 1614 1615 1616
</dd>
<dt>0.11a</dt>
<dd>the changelog has <a href="http://www2.cs.tum.edu/repos/cup/develop/changelog.txt">moved</a> to the
internet to sustain a more up-to-date state.
</dd>
</dl>
petter's avatar
petter committed
1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629


<hr>

<a name="trademark">
Java and HotJava are
trademarks of </a><a href="http://www.sun.com/">Sun Microsystems, Inc.</a>,
and refer to Sun's Java programming language and HotJava browser
technologies.
CUP is not sponsored by or affiliated with Sun Microsystems, Inc.

<hr>

1630
</div>
1631
</body></html>