![[CUP Logo Image]](cup_logo.gif){kind=logo}
Copyright 2008-2011 by Jochen Hoenicke
Copyright 2005-2006 by Michael Petter
Copyright 1996-1999 by Scott Hudson, Frank Flannery, C. Scott Ananian
Permission to use, copy, modify, and distribute this software and its documentation for any purpose and without fee is hereby granted, provided that the above copyright notice appear in all copies and that both the copyright notice and this permission notice and warranty disclaimer appear in supporting documentation, and that the names of the authors or their employers not be used in advertising or publicity pertaining to distribution of the software without specific, written prior permission.
The authors and their employers disclaim all warranties with regard to this software, including all implied warranties of merchantability and fitness. In no event shall the authors or their employers be liable for any special, indirect or consequential damages or any damages whatsoever resulting from loss of use, data or profits, whether in an action of contract, negligence or other tortious action, arising out of or in connection with the use or performance of this software.
Since version 0.9 there are many new changes and features. 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 appendix C 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.
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.
In Version 0.12 Java 5 support is extended. Furthermore there are some performance improvements in the CUP code and the generated parser. This comes with changes to the internal structure of the parser so it may lead to incompatibilities.
This manual describes the basic operation and use of the Java(tm) 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 [1] 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.
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 [2,3]) cover this material, and discuss the YACC system (which is quite similar to this one) as a specific example.
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).
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:
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
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:
expr_list, expr_part and expr .
For terminal names we might choose:
SEMI, PLUS, MINUS, TIMES, DIVIDE, MOD, NUMBER, LPAREN, and RPAREN
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:
3 + 4 * 6
The grammar can either evaluate the 3 + 4 and then multiply
seven by six, or it can evaluate 4 * 6 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:
// CUP specification for a simple expression evaluator (no actions)
import com.github.jhoenicke.javacup.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
;
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 com.github.jhoenicke.javacup.runtime 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 Integer. 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.
To produce a parser from this specification we use the CUP generator. If this specification were stored in a file parser.cup, then (on a Unix system at least) we might invoke CUP using a command like:
java -jar java-cup-11a.jar parser.cupIn this case, the system will produce two Java source files containing parts of the generated parser: sym.java and parser.java. As you might expect, these two files contain declarations for the classes sym and parser. The sym 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 "return new Symbol(sym.SEMI);" ). The parser class implements the parser itself.
The specification above, while constructing a full parser, does not perform any semantic actions &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 code strings which are surrounded by delimiters of the form {: and :} (we can see examples of this in the init with and scan with clauses above). In general, the system records all characters within the delimiters, but does not try to check that it contains valid Java code.
A more complete CUP specification for our example system (with actions embedded at various points in the grammar) is shown below. Note that this uses autoboxing for integers and thus needs Java 1.5 to run.
// CUP specification for a simple expression evaluator (w/ actions)
import com.github.jhoenicke.javacup.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 = e1 + e2; :}
|
expr:e1 MINUS expr:e2
{: RESULT = e1 - e2; :}
|
expr:e1 TIMES expr:e2
{: RESULT = e1 * e2; :}
|
expr:e1 DIVIDE expr:e2
{: RESULT = e1 / e2; :}
|
expr:e1 MOD expr:e2
{: RESULT = e1 % e2; :}
|
NUMBER:n
{: RESULT = n; :}
|
MINUS expr:e
{: RESULT = e; :}
%prec UMINUS
|
LPAREN expr:e RPAREN
{: RESULT = e; :}
;
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 {: and :}. In addition, labels have been placed on various symbols in the right hand side of productions. For example in:
expr:e1 PLUS expr:e2
{: RESULT = e1 + e2; :}
the first non-terminal expr has been labeled with e1, and the second with e2. The left hand side value of each production is always implicitly labeled as RESULT.
Each symbol appearing in a production is represented at runtime by an object of type Symbol on the parse stack. The labels refer to the instance variable value in those objects. In the expression expr:e1 PLUS expr:e2, e1 and e2 refer to objects of type Integer. These objects are in the value fields of the objects of type Symbol representing those non-terminals on the parse stack. RESULT is of type Integer as well, since the resulting non-terminal expr was declared as of type Integer. This object becomes the value instance variable of a new Symbol object.
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 left or right. for example, given the right hand side of a production expr:e1 PLUS expr:e2 the user could not only access variables e1 and e2, but also e1left, e1right, e2left and e2right. these variables are of type int.
The code contained in the init with clause of the specification
will be executed before any tokens are requested. Each token will be
requested using whatever code is found in the scan with 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 com.github.jhoenicke.javacup.runtime.Symbol (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, Symbol reuse should be
detected if it occurs; the parser will throw an Error
telling you to fix your scanner.
In the next section a more detailed and formal explanation of all parts of a CUP specification will be given. Section 3 describes options for running the CUP system. Section 4 discusses the details of how to customize a CUP parser, while section 5 discusses the scanner interface added in CUP 0.10j. Section 6 considers error recovery. Finally, Section 7 provides a conclusion.
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:
Each of these parts must appear in the order presented here. (A complete grammar for the specification language is given in Appendix A.) The particulars of each part of the specification are described in the subsections below.
A specification begins with optional package and import 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:
package name;
where name name 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.
After an optional package declaration, there can be zero or more import declarations. As in a Java program these have the form:
import package_name.class_name;or
import package_name.*;
The package declaration indicates what package the sym and parser 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 parser class allowing various names from that package to be used directly in user supplied action code.
Following the optional package and import declarations the user can configure the name of the parser and the symbol class and can give some additional options. An option is set using the keyword option. Here is an example.
parser ExprParser;
option symbols=ExprSymbols;
option interface, expect=2;
Some options take a parameter. The parameter should be added after an = symbol. In principle you can specify any option that you can also put on the command line. The following options are most useful to specify in the grammar file:
interface
rather than as a class.com.github.jhoenicke.javacup.runtime.Scanner. 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 noscanner option to suppress the
com.github.jhoenicke.javacup.runtime.Scanner references and allow
compatibility with old runtimes. Not many people should have reason
to do this.After the options a series of optional declarations can be added that allow user code to be included as part of the generated parser (see Section 4 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 action code 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:
action code {: ... :};
where {: ... :} is a code string whose contents will be placed directly within the action class class declaration. This contains auxiliary functions that can be called from the actions in the productions (see below).
After the action code declaration is an optional parser code 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 &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 action code declaration and takes the form:
parser code {: ... :};
Again, code from the code string is placed directly into the generated parser class definition.
Next in the specification is the optional init declaration which has the form:
init with {: ... :};
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 void method inside the parser class.
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:
scan with {: ... :};
As with the init 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 com.github.jhoenicke.javacup.runtime.Symbol.
Consequently the code found in the scan with clause should
return such a value. See section 5 for
information on the default behavior if the scan with
section is omitted.
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.
after reduce {: ... :};
Defines code that is executed whenever a production rule is reduced. The arrays symbols contains all terminal and non-terminal symbols of the current production rule. RESULT can be used to access and modify the value of the nonterminal created by the production rule. Example usage:
after reduce {:
int lineNumber = symbols[0].left + 1;
if (RESULT instanceof AST_Node) {
((AST_Node) RESULT).lineNumber = lineNumber
}
:}
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 Symbol object. In the case of terminals, these are created by the scanner. For non-terminals the generated code will create these symbols. Each Symbol has a value field which can store an optional value. In order to tell the parser which object types should be used as value for which symbol, terminal and non terminal declarations are used. These take the forms:
terminal classname name1, name2, ...;
non terminal classname name1, name2, ...;
terminal name1, name2, ...;
non terminal name1, name2, ...;
Here classname is a Java class name that specifies
the type of the value of that is stored together with the terminal or
non-terminal. You can also use an array type, e. g., String[],
or an instantiated template type, e.g., ArrayList<String>.
In the action code in the grammar the values can
be accessed and they will have the declared type.
If no classname is given, then the
terminal or non-terminal holds no value and it may not be accessed
in the action code. As of CUP 0.10j, you may also use the
declaration "nonterminal" (note, no
space) instead of the original "non terminal" spelling.
The lexer is responsible for putting a value for each terminal in the value instance variable. The type of the value must match its declared type or an exception will occur at run-time. In the case of non-terminals the value is generated by the action code of the production and placed into the Symbol created by the generated parser.
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".
The third section, which is optional, specifies the precedences and associativity of terminals. This is useful for parsing ambiguous grammars, as done in the example above. There are three type of precedence/associativity declarations:
precedence left terminal[, terminal...]; precedence right terminal[, terminal...]; precedence nonassoc terminal[, terminal...];
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:
precedence left ADD, SUBTRACT; precedence left TIMES, DIVIDE;
Internally, precedence is used to automatically resolve shift reduce problems. For example, consider the input to the above example parser 3 + 4 * 8. Without precedence declaration the parser doesn't know whether to reduce 3 + 4 to an expr non-terminal or shift the '*' onto the stack in order to later reduce 4 * 8 to expr. With the precedence declaration, since '*' has a higher precedence than '+', it will be shifted and the multiplication will be performed before the addition.
CUP assigns each one of its terminals a precedence according to these declarations. Any terminals not in this declaration have no precedence. CUP also assigns each of its productions a precedence. That precedence is usually equal to the precedence of the last terminal in that production but it can also be explicitly set in the grammar. If the production has no terminals, then it has no precedence. For example, expr ::= expr TIMES expr would have the same precedence as TIMES. 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 is shifted, if the production has higher precedence, a reduce is performed. If they have equal precedence, associativity of the terminal determine what happens.
An associativity is assigned to each terminal used in the precedence/associativity declarations. The three associativities are left, right and nonassoc 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 left, then a reduce is performed. This means, if the input is a string of additions, like 3 + 4 + 5 + 6 + 7, the parser will always reduce them from left to right, in this case, starting with 3 + 4. If the associativity of the terminal is right, it is shifted onto the stack. hence, the reductions will take place from right to left. So, if PLUS were declared with associativity of right, the 6 + 7 would be reduced first in the above string. If a terminal is declared as nonassoc, 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 6 == 7 == 8 == 9 should not be allowed by the grammar. If '==' is declared as nonassoc then a shift-reduce error will still be generated when such an expression is possible.
You should be careful when using precedences, as it can hide unexpected shift-reduce conflicts. It is usually safe to use it for infix operators and it is also safe to give a production a precedence explictly that is not an infix production such as int the example with the unary minus.
All terminals not used in the precedence/associativity declarations are treated as no precedence. If a shift/reduce error results, involving a terminal or a production rules with no precedence, it cannot be resolved. So it will be reported.
The final section of a CUP declaration provides the grammar. This section optionally starts with a declaration of the form:
start with non-terminal;
This indicates which non-terminal is the start or goal 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 com.github.jhoenicke.javacup.runtime.Symbol. This Symbol's value instance variable contains the final reduction result.
The grammar itself follows the optional start declaration. Each production in the grammar has a left hand side non-terminal followed by the symbol "::=", which is then followed by a series of zero or more actions, terminal, or non-terminal symbols, followed by an optional contextual precedence assignment, and terminated with a semicolon (;). 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 "::=". This is followed by multiple right hand sides each separated by a bar (|). The full set of productions is then terminated by a semicolon.
expr ::= expr:e1 PLUS expr:e2 {: RESULT = e1 + e2; :}
| expr:e1 TIMES expr:e2 {: RESULT = e1 * e2; :}
| MINUS expr:e {: RESULT = -e; :} %prec UMINUS
| LPAREN expr:e RPAREN {: RESULT = e; :}
| NUMBER:n {: RESULT = n; :}
;
Each symbol on the right hand side can optionally be labeled with a name. 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 an additional variable for the underlying symbol is created, which is the label plus a dollar ($) symbol. This can be used to access other information, such as the left and right position of that symbol in the source file. Unless the option -nopositions or -newpositions is given,two more variables are created, which are the label plus left and the label plus right. These are int values that contain the right and left locations.
Actions appear in the right hand side as code strings (e.g., Java code inside {: ... :} 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 lookahead token for resolving ambiguities. If no action is given and the right-hand-side consists of a single (terminal or non-terminal) symbol, the default action is to return the value of this symbol. This default action is handled very efficiently in the parser.
Contextual precedence assignments follow all the symbols and actions of 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:
precedence left PLUS, MINUS;
precedence left TIMES, DIVIDE, MOD;
precedence left UMINUS;
expr ::= MINUS expr:e
{: RESULT = -e; :}
%prec UMINUS
Here, there production is declared as having the precedence of UMINUS. Hence, the parser can give the MINUS sign two different precedences, depending on whether it is a unary minus or a subtraction operation.
terminal String sym
one can use sym?, sym* or sym+, as if the
following definitions and rules would have been added:
nonterminal String sym?
nonterminal String[] sym*, sym+
sym? ::= {: RESULT = null; :} | sym;
sym* ::= {: RESULT = new String[0]; :} | sym+;
sym+ ::= sym:s {: RESULT = new String[] { s }; :}
| sym+:list sym:s
{: RESULT = new String[list.length+1];
System.arraycopy(list, 0, RESULT, 0, nts.length);
RESULT[list.length] = s; :};
These definitions are only added when needed and they are implemented more
efficiently internally (e.g. the array is only created once).
As mentioned above, CUP is written in Java. To invoke it, one needs to use the Java interpreter to invoke the static method com.github.jhoenicke.javacup.Main(), 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:
java -jar java-cup-11a.jar options inputfile
Once running, CUP expects to find a specification file on standard input and produces two Java source files as output.
In addition to the specification file, CUP's behavior can also be changed
by passing various options to it. Legal options are documented in
Main.java and include:
interface
rather than as a class.
This option should better be set in the grammar file.com.github.jhoenicke.javacup.runtime.Scanner. 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 -noscanner option to suppress the
com.github.jhoenicke.javacup.runtime.Scanner references and allow
compatibility with old runtimes. Not many people should have reason
to do this.-version 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.To use cup in an ANT script, You have to add the following task definition to Your build.xml file:
<taskdef name="cup" classname="com.github.jhoenicke.javacup.anttask.CUPTask" classpathref="cupclasspath" />
Now, You are ready to use Your new <cup/> task to generate own parsers from within ANT. Such a generation statement could look like:
<target name="cup"> <cup srcfile="path/to/cupfile/Parser.cup" destdir="path/to/javafiles" interface="true" /> </target>
You can specify all commandline flags from chapter
Each generated parser consists of three generated classes. The sym class (which can be renamed using the -symbols option) simply contains a series of int constants, one for each terminal. Non-terminals are also included if the -nonterms option is given. The source file for the parser class (which can be renamed using the -parser option) actually contains two class definitions, the public parser class that implements the actual parser, and another non-public class (called CUP$action) which encapsulates all user actions contained in the grammar, as well as code from the action code declaration. In addition to user supplied code, this class contains one method: CUP$do_action 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 CUP$ are reserved for internal uses by CUP generated code.
The parser class contains the actual generated parser. It is a subclass of com.github.jhoenicke.javacup.runtime.LRParser which implements a general table driven framework for an LR parser. The generated parser class provides a series of tables for use by the general framework. Three tables are provided:
(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.)
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 LRParser base class and can be overridden with new versions (via the parser code declaration) to customize the system. Methods available for customization include:
getScanner().next_token().Parsing itself is performed by the method public Symbol parse(). This method starts by getting references to each of the parse tables, then initializes a CUP$action object (by calling protected void init_actions()). Next it calls user_init(), then fetches the first lookahead token with a call to scan(). Finally, it begins parsing. Parsing continues until done_parsing() is called (this is done automatically, for example, when the parser accepts). It then returns a Symbol with the value instance variable containing the RESULT of the start production, or null, if there is no value.
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 public void debug_message(String mess) whose default implementation prints a message to System.err).
Based on these routines, invocation of a CUP parser is typically done with code such as:
/* 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 */
}
In CUP 0.10j, scanner integration was improved according to suggestions made by David MacMahon. The changes make it easier to incorporate JLex and other automatically-generated scanners into CUP parsers.
To use the new code, your scanner should implement the
com.github.jhoenicke.javacup.runtime.Scanner interface, defined as:
package com.github.jhoenicke.javacup.runtime;
public interface Scanner {
public Symbol next_token() throws java.lang.Exception;
}
In addition to the methods described in section
4, the com.github.jhoenicke.javacup.runtime.lr_parser class has two new
accessor methods, setScanner() and getScanner().
The default implementation of scan()
is:
public Symbol scan() throws java.lang.Exception {
return getScanner().next_token();
}
The generated parser also contains a constructor which takes a
Scanner and calls setScanner() with it. In
most cases, then, the init with and scan
with directives may be omitted. You can simply create the
parser with a reference to the desired scanner:
/* create a parsing object */
parser parser_obj = new parser(new my_scanner());
or set the scanner after the parser is created:
/* create a parsing object */
parser parser_obj = new parser();
/* set the default scanner */
parser_obj.setScanner(new my_scanner());
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 scan() without first calling
setScanner(), a NullPointerException will be
thrown.
As an example of scanner integration, the following three lines in the lexer-generator input are all that is required to use a JLex scanner with CUP:
%implements com.github.jhoenicke.javacup.runtime.Scanner %function next_token %type com.github.jhoenicke.javacup.runtime.Symbol
Invoking the parser with the JLex scanner is then simply:
parser parser_obj = new parser( new Yylex( some_InputStream_or_Reader));
Note that you still have to handle EOF correctly; the JLex code to do so is something like:
%eofval{
return sym.EOF;
%eofval}
where sym is the name of the symbol class for your
generated parser.
The simple_calc example in the CUP distribution illustrates the use of the scanner integration features with a hand-coded scanner.
Since CUP v11a we offer the possibility of advanced symbol handling in CUP.
Therefore, You can implement Your own SymbolFactory, derived from
com.github.jhoenicke.javacup.runtime.SymbolFactory, and have CUP manage Your own type of
symbols. We've done that for You already in the pre-defined
com.github.jhoenicke.javacup.runtime.ComplexSymbolFactory, which provides support for
detailed location information in the symbol class. Just have a look at CUPs own
Lexer.jflex, which is already using the new feature.
All You have to do is providing Your CUP-generated parser with the new SymbolFactory which can be done like this:
SymbolFactory symbolFactory = new ComplexSymbolFactory(); MyParser parser = new MyParser(new Lexer(inputfile,symbolFactory),symbolFactory);
Also, You can use the factory methods in Your SymbolFactory to have callbacks/hooks into the semantic action methods. That is especially usefull, when You want to equip Your syntax tree with Location information as You can do as follows:
public Symbol newSymbol(String name, Symbol left, Symbol right, Object value){
ComplexSymbol sym = (ComplexSymbol)super.newSymbol(name,left,right,value);
SyntaxTreeNode node = (SyntaxTreeNode) value;
node.setLeft(left.getLeft());
node.setRight(right.getRight());
return sym;
}
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 error). This symbol plays the role of a special non-terminal which, instead of being defined by productions, instead matches an erroneous input sequence.
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 error and then continue parsing. For example, we might have productions such as:
stmt ::= expr SEMI | while_stmt SEMI | if_stmt SEMI | ... | error SEMI ;
This indicates that if none of the normal productions for stmt 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 error) 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 error symbol can be successfully parsed. (The number of tokens required is determined by the error_sync_size() method of the parser and defaults to 3).
Specifically, the parser first looks for the closest state to the top of the parse stack that has an outgoing transition under error. 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.
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.
This document covers version 0.12 of the system. Check the CUP home page: http://www.cs.princeton.edu/~appel/modern/java/CUP/ 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 cananian@alumni.princeton.edu
CUP was originally written by Scott Hudson, in August of 1995.
It was extended to support precedence by Frank Flannery, in July of 1996.
On-going improvements have been done by C. Scott Ananian, the CUP maintainer, from December of 1997 to the present.
TODO: TUM changes
In 2010 and later Jochen Hoenicke changed the precedence handling to report more shift-reduce conflicts and added the wildcard support (?,*,+). He also rewrote the runtime to generate smaller code.
javacup_spec ::= package_spec import_spec* code_parts
symbol+ preced* start_spec
production+
package_spec ::= PACKAGE multipart_id SEMI | empty
import_spec ::= IMPORT import_id SEMI
code_parts ::= code_parts code_part | empty
code_part ::= ACTION CODE CODE_STRING SEMI? |
PARSER CODE CODE_STRING SEMI? |
INIT WITH CODE_STRING SEMI? |
SCAN WITH CODE_STRING SEMI?
symbol ::= TERMINAL opt_type_id terminal_list SEMI |
non_terminal opt_type_id non_terminal_list SEMI
non_terminal ::= NON TERMINAL | NONTERMINAL
preced ::= PRECEDENCE LEFT terminal_list SEMI |
PRECEDENCE RIGHT terminal_list SEMI |
PRECEDENCE NONASSOC terminal_list SEMI
start_spec ::= START WITH nt_id SEMI | empty
production ::= nt_id COLON_COLON_EQUALS rhs_list SEMI opt_context_prec
rhs_list ::= rhs_list BAR rhs | rhs
rhs ::= prod_part* PERCENT_PREC term_id |
prod_part*
prod_part ::= symbol_id opt_label | CODE_STRING
opt_label ::= COLON label_id | empty
opt_type_id ::= type_id | empty
import_id ::= multipart_id DOT STAR | multipart_id
type_id ::= multipart_id | type_id LBRACK RBRACK
multipart_id LANGLE type_arg_list RANGLE
type_arg_list ::= type_arg_list COMMA type_arg | type_arg
type_arg ::= type_id | wildcard
wildcard ::= QUESTION | wildcard EXTENDS type_id |
wildcard SUPER type_id
multipart_id ::= multipart_id DOT ID | ID
terminal_list ::= terminal_list COMMA term_id | term_id
non_terminal_list ::= non_terminal_list COMMA non_term_id | non_term_id
term_id ::= symbol_id
non_term_id ::= ID
symbol_id ::= ID
label_id ::= ID
// Simple Example Scanner Class
import com.github.jhoenicke.javacup.runtime.*;
import sym;
public class scanner {
/* single lookahead character */
protected static int next_char;
// since cup v11 we use SymbolFactories rather than Symbols
private SymbolFactory sf = new DefaultSymbolFactory();
/* 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 >= '0' && next_char <= '9');
return sf.newSymbol("NUMBER",sym.NUMBER, i_val);
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);
case -1: return return sf.newSymbol("EOF",sym.EOF);
default:
/* in this simple scanner we just ignore everything else */
advance();
break;
}
}
};
For more information, refer to the manual on scanners.
terminal classname terminal [, terminal ...];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:
terminal terminal [, terminal ...];indicates the terminals in the list hold no value.
For more information, refer to the manual on declarations.
Label references do not refer to the object on the parse stack, as in the old CUP, but rather to the value of the value instance variable of the Symbol 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. The symbol is now accessible with label followed by a $ symbol.
For more information, refer to the manual on labels.
For more information, refer to the manual on RESULT.
For more information, refer to the manual on positions.
precedence {left| right | nonassoc} terminal[, terminal ...];
...
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.
left, right and nonassoc 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.For more information, refer to the manual on precedence.
lhs ::= {right hand side list of terminals, non-terminals and actions}
%prec {terminal};
this production would then have a precedence equal to the terminal
specified after the %prec. Hence, shift/reduce conflicts can be
contextually resolved. Note that the %prec terminal
part comes after all actions strings. It does not come before the
last action string.For more information, refer to the manual on contextual precedence. These changes implemented by:
This is because the parsing tables (and parsing engine) are in one object (belonging to class parser or whatever name is specified by the -parser directive), and the semantic actions are in another object (of class CUP$actions).
However, there is a way to do it, though it's a bit inelegant. The action object has a private final field named parser that points to the parsing object. Thus, methods and instance variables of the parser can be accessed within semantic actions as:
parser.report_error(message,info);
x = parser.mydata;
Perhaps this will not be necessary in a future release, and that such methods and variables as report_error and mydata will be available directly from the semantic actions; we will achieve this by combining the "parser" object and the "actions" object together.
For a list of any other currently known bugs in CUP, see http://www.cs.princeton.edu/~appel/modern/java/CUP/bugs.html.
com.github.jhoenicke.javacup.runtime.Scanner interface.