manual.html

java cup constructor to compiler

<dt><tt> protected int error_sync_size()</tt>
<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.
</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>

Based on these routines, invocation of a CUP parser is typically done
with code such as:
<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>

<a name="scanner">
<h3>5. Scanner Interface</h3></a>

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

To use the new code, your scanner should implement the
<code>java_cup.runtime.Scanner</code> interface, defined as:
<pre>
package java_cup.runtime;

public interface Scanner {
    public Symbol next_token() throws java.lang.Exception;
}
</pre><p>

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:
<pre>
  public Symbol scan() throws java.lang.Exception {
    Symbol sym = getScanner().next_token();
    return (sym!=null) ? sym : new Symbol(EOF_sym());
  }
</pre><p>
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:
<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>
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/~appel/modern/java/JLex/">JLex</a>
or <a href="http://www.jflex.de/">JFlex</A>
scanner with CUP:
<pre>
%implements java_cup.runtime.Scanner
%function next_token
%type java_cup.runtime.Symbol
</pre>
The JLex directive <code>%cup</code>
abbreviates the above three directive in JLex versions 1.2.5 and above.
Invoking the parser with the JLex scanner is then simply:
<pre>
parser parser_obj = new parser( new Yylex( some_InputStream_or_Reader));
</pre><p>

Note CUP handles the JLex/JFlex convention of returning null on EOF
without a problem, so an <code>%eofval</code> directive is not
required in the JLex specification (this feature was added in CUP 0.10k).

The simple_calc example in the CUP distribution illustrates the use of
the scanner integration features with a hand-coded scanner.
The CUP website has a minimal CUP/JLex integration example for study.<p>

<a name="errors">
<h3>6. Error Recovery</h3></a>

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>

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:

<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.

<a name="conclusion">
<h3>7. Conclusion</h3></a>

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>

This document covers version 0.10j of the system.  Check the CUP home
page:
<a href="http://www.cs.princeton.edu/~appel/modern/java/CUP/">
http://www.cs.princeton.edu/~appel/modern/java/CUP/</a>
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, 
C. Scott Ananian, at
<a href="mailto:[e-mail]">
[e-mail]</a><p>

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

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

On-going improvements have been done by
<A HREF="http://www.pdos.lcs.mit.edu/~cananian">
C. Scott Ananian</A>, the CUP maintainer, from December of 1997 to the
present.<p>

<a name="refs">
<h3>References</h3></a>
<dl compact>

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

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

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

<dt><a name = "modernjava">[4]</a>
<dd>Andrew W. Appel,
<i>Modern Compiler Implementation in Java</i>,
Cambridge University Press,
New York, NY,
1998.

</dl>

<h3><a name="appendixa">
Appendix A. Grammar for CUP Specification Files</a> (0.10j)</h3>
<hr><br>
<pre><tt>java_cup_spec      ::= package_spec import_list code_parts
		       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
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