Symbolic Differentiation Part II

Terry Brugger

A previous entry in the Field Guide explained how the Polynomial Parser from Language Translation Using PCCTS & C++ could be constructed in ANTLR 2. This Field Guide entry expands upon that to construct the AST for the Poly Parser.

The first advantage to ANTLR 2 that appears in this section is that a CommonAST class has already been constructed. This class performs all of the functions described by AST on page 54. CommonAST is a concrete subclass of abstract class BaseAST, which defines most of the behaviour for ASTs. In fact, very few changes need to be made. Most all of the changes stem from differences between Java and C++. Our PolyMain.java may remain unchanged. The interp described in the text is the same. The assign rule looks like:

assign
	: ID "="^ poly ";"!
		{ System.out.println( #assign.toStringList() ); }
	;

The only change here is in the action. Rules can be referred to using the syntax #name. The poly rule is unchanged. term is changed primarily due to writer's prerogative (described previously):

term
	:! coeff:coefficient
	   ( var:reg
	     ( "^" pow:exp
		{ #term = #(#[MULT, "MULT"], #coeff,
			  #(#[EXP, "EXP"], #var, #pow)); }
	     |  { #term = #(#[MULT, "MULT"], #coeff, #var); }
	     )
	   |    { #term = #coeff; }
	   )
	|! var2:reg ( "^" pow2:exp
			{ #term = #(#[EXP, "EXP"], #var2, #pow2); }
		    |	{ #term = #var2; }
		    )
		
	;

The two main changes that aren't related to variable name changes stem from the combination of bigterm and term (which was done for simplicity) and the breaking of the second option into two possible actions. Separate actions were created so that we could model the option both with and without an EXP node. We need to manually create the EXP node because our "^" is just interpreted as a string and only a literal string node is created for it by default. We changed the labels in the second option to var2 and pow2 to differentiate them from the labels in the first option. If we don't do this, ANTLR complains about them.

We add MULT and EXP as dummy tokens:

DummyTokens
	: MULT
	| EXP
	;

We add the buildAST option to our grammar and it becomes:

// Poly.g
// Defines a grammar for a Polynomial Parser
class PolyParser extends Parser;
options
{
	buildAST = true;
}

// The entry point for an interpreter
interp!
	: (assign )+
	;

// An assignment expression
assign
	: ID "="^ poly ";"!
		{ System.out.println(#assign.toStringList()); }
	;

// A polynomial
poly
	: term ( "+"^ term )*
	;

// A term in the polynomial
term
	:! coeff:coefficient
	   ( var:reg
	     ( "^" pow:exp
		{ #term = #(#[MULT, "MULT"], #coeff,
			  #(#[EXP, "EXP"], #var, #pow)); }
	     |  { #term = #(#[MULT, "MULT"], #coeff, #var); }
	     )
	   |    { #term = #coeff; }
	   )
	|! var2:reg ( "^" pow2:exp
			{ #term = #(#[EXP, "EXP"], #var2, #pow2); }
		    |	{ #term = #var2; }
		    )
		
	; 

// The coefficient of the term
coefficient
	: FLOAT
	;

// A register or variable
reg
	: ID
	;

// An exponent in a term
exp
	: reg
	| FLOAT
	;

dummyTokens
	: MULT
	| EXP
	;

class PolyLex extends Lexer;

// An ID for a register
ID
	: 'a'..'z'
	;

// A floating point number
FLOAT
	: ( '0'..'9' )+ ( '.' ( '0'..'9' )* )?
	;

// Operators
OPERATORS
	: '='
	| '+'
	| '^'
	| ';'
	;

// Eat the white space
WS
	: ( ' '
	 | '\t'
	 | '\r' '\n'	{ newline(); }
	 | '\n'	{ newline(); }
	 )
		/* All the characters are in a subrule so that this
		 action will apply to them: */
		{ $setType(Token.SKIP); } // ignore this token
	;

Walking the AST

Walking the AST that we just built is very easy in ANTLR 2. We'll start with defining a TreeParser in Poly.g:

class PolyWalker extends TreeParser;

Our assign and poly rules from page 60 have only a slight modification:

assign
	: #( "=" ID poly)
	;

poly
	: #( MULT poly poly )
	| #( "+" poly poly )
	| #( EXP poly poly )
	| ID
	| FLOAT
	;

that is, the ASSIGN and ADD tokens have been changed to their string forms. Using real tokens would require going back and changing the entire Poly grammar. The conversion to using Java syntax for the actions is equally straightforward:

assign
	{ double dbl=0.0; }
	: #( "=" id:ID dbl=poly )
		{ regs.store(id.getText(), dbl); }
	;

poly returns [double ret]
	{ double lhs = 0.0, rhs = 0.0; ret = -1.0; }
	: #( MULT lhs=poly rhs=poly )
		{ ret = lhs * rhs; }
	| #( "+" lhs=poly rhs=poly )
		{ ret = lhs + rhs; }
	| #( EXP lhs=poly rhs=poly )
		{ ret = java.lang.Math.pow(lhs, rhs); }
	| id:ID
		{ ret = regs.value(id.getText()); }
	| flt:FLOAT
		{ ret = (new Double(flt.getText())).doubleValue(); }
	;

We add in our registers and a specialized constructor for the register behaviour, just like we did for PolyParser when we had it perform semantic actions:

{
	private DblStorage regs;
	public PolyWalker (DblStorage regs)
	{
		this();
		this.regs = regs;
	} // end specialized constructor
}

And tell PolyParser to use the PolyWalker:

{
	protected PolyWalker walker;
	public PolyParser(Tokenizer tokenBuf, PolyWalker walker)
	{
		this(tokenBuf);
		this.walker = walker;
	} // end specialized constructor
}
assign
	: ID "="^ poly ";"!
		{ walker.assign(#assign); }
	;

Our resulting grammar is:

// Poly.g
// Defines a grammar for a Polynomial Parser
class PolyParser extends Parser;
options
{
	buildAST = true;
}
{
	protected PolyWalker walker;
	public PolyParser(Tokenizer tokenBuf, PolyWalker walker)
	{
		this(tokenBuf);
		this.walker = walker;
	} // end specialized constructor
}

// The entry point for an interpreter
interp!
	: (assign )+
	;

// An assignment expression
assign
	: ID "="^ poly ";"!
		{ walker.assign(#assign); }
	;

// A polynomial
poly
	: term ( "+"^ term )*
	;

// A term in the polynomial
term
	:! coeff:coefficient
	   ( var:reg
	     ( "^" pow:exp
		{ #term = #(#[MULT, "MULT"], #coeff,
			  #(#[EXP, "EXP"], #var, #pow)); }
	     |  { #term = #(#[MULT, "MULT"], #coeff, #var); }
	     )
	   |    { #term = #coeff; }
	   )
	|! var2:reg ( "^" pow2:exp
			{ #term = #(#[EXP, "EXP"], #var2, #pow2); }
		    |	{ #term = #var2; }
		    )
		
	;

// The coefficient of the term
coefficient
	: FLOAT
	;

// A register or variable
reg
	: ID
	;

// An exponent in a term
exp
	: reg
	| FLOAT
	;

dummyTokens
	: MULT
	| EXP
	;

class PolyWalker extends TreeParser;
{
	private DblStorage regs;
	public PolyWalker (DblStorage regs)
	{
		this();
		this.regs = regs;
	} // end specialized constructor
}

// Assignment of the result of a polynomial to a register
assign
	{ double dbl=0.0; }
	: #( "=" id:ID dbl=poly )
		{ regs.store(id.getText(), dbl); }
	;

// computation of polynomials
poly returns [double ret]
	{ double lhs = 0.0, rhs = 0.0; ret = -1.0; }
	: #( MULT lhs=poly rhs=poly )
		{ ret = lhs * rhs; }
	| #( "+" lhs=poly rhs=poly )
		{ ret = lhs + rhs; }
	| #( EXP lhs=poly rhs=poly )
		{ ret = java.lang.Math.pow(lhs, rhs); }
	| id:ID
		{ ret = regs.value(id.getText()); }
	| flt:FLOAT
		{ ret = (new Double(flt.getText())).doubleValue(); }
	;

class PolyLex extends Lexer;

// An ID for a register
ID
	: 'a'..'z'
	;

// A floating point number
FLOAT
	: ( '0'..'9' )+ ( '.' ( '0'..'9' )* )?
	;

// Operators
OPERATORS
	: '='
	| '+'
	| '^'
	| ';'
	;

// Eat the white space
WS
	: ( ' '
	  | '\t'
	  | '\r' '\n'	{ newline(); }
	  | '\n'	{ newline(); }
	  )
		/* All the characters are in a subrule so that this
		   action will apply to them: */
		{ $setType(Token.SKIP); } // ignore this token
	;

We also need a new main in order to construct everything with the proper behaviour:

import java.io.*;
import antlr.CommonAST;
import antlr.collections.AST;

class PolyMain
{
	public static void main(String[] args)
	{
		try {
			DblStorage regs = new Registers();
			PolyWalker walker = new PolyWalker(regs);
			PolyLex lexer = new PolyLex(new DataInputStream(System.in)); 
			PolyParser parser = new PolyParser(lexer, walker); 
			parser.interp();
		} catch(Exception exception) {
			System.err.println("exception: "+exception);
		} // end try
	} // end main()
} // end Main