* This is a simple recursive descent parser. All lexical analysis is done here as well. */ public class Parser { /** * A Global Static, unique to each compilation. This is a public, so we * can make constants everywhere without having to thread the StartNode * through the entire parser and optimizer. *
* To make the compiler multithreaded, this field will have to move into a TLS. */ public static StartNode START; public static ConstantNode ZERO; public static XCtrlNode XCTRL; public StopNode STOP; // Debugger Printing. public static boolean SCHEDULED; // True if debug printer can use schedule info // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; /** * Current ScopeNode - ScopeNodes change as we parse code, but at any point of time * there is one current ScopeNode. The reason the current ScopeNode can change is to do with how * we handle branching. See {@link #parseIf()}. *
* Each ScopeNode contains a stack of lexical scopes, each scope is a symbol table that binds * variable names to Nodes. The top of this stack represents current scope. *
* We keep a list of all ScopeNodes so that we can show them in graphs.
* @see #parseIf()
* @see #_xScopes
*/
public ScopeNode _scope;
/**
* List of keywords disallowed as identifiers
*/
private static final HashSet
* '{' statements '}'
*
* Does not parse the opening or closing '{}'
* @return a {@link Node} or {@code null}
*/
private Node parseBlock() {
// Enter a new scope
_scope.push();
while (!peek('}') && !_lexer.isEOF())
parseStatement();
// Exit scope
_scope.pop();
return null;
}
/**
* Parses a statement
*
*
* returnStatement | declStatement | blockStatement | ifStatement | expressionStatement
*
* @return a {@link Node} or {@code null}
*/
private Node parseStatement() {
if( false ) return null;
else if (matchx("return") ) return parseReturn();
else if (match ("{") ) return require(parseBlock(),"}");
else if (matchx("if") ) return parseIf();
else if (matchx("while") ) return parseWhile();
else if (matchx("break") ) return parseBreak();
else if (matchx("continue")) return parseContinue();
else if (matchx("struct") ) return parseStruct();
else if (matchx("#showGraph")) return require(showGraph(),";");
else if (matchx(";") ) return null; // Empty statement
// declarations of vars with struct type are handled in parseExpressionStatement due
// to ambiguity
else return parseExpressionStatement();
}
/**
* Parse a struct field.
*
* type IDENTIFIER ;
*
*/
private Field parseField() {
Type t = type();
if( t==null )
throw errorSyntax("Requires a field type, found '"+_lexer.getAnyNextToken()+"'");
return require(Field.make(requireId().intern(),t),";");
}
/**
* Parse a struct declaration, and return the following statement.
* Only allowed in top level scope.
* Structs cannot be redefined.
*
* @return null
*/
private Node parseStruct() {
if (_xScopes.size() > 1) throw errorSyntax("struct declarations can only appear in top level scope");
String typeName = requireId();
Type t = TYPES.get(typeName);
if( t!=null && !(t instanceof TypeStruct ts && ts._fields==null) ) throw errorSyntax("struct '" + typeName + "' cannot be redefined");
ArrayList
* while ( expression ) statement
*
* @return a {@link Node}, never {@code null}
*/
private Node parseWhile() {
var savedContinueScope = _continueScope;
var savedBreakScope = _breakScope;
require("(");
// Loop region has two control inputs, the first is the entry
// point, and second is back edge that is set after loop is parsed
// (see end_loop() call below). Note that the absence of back edge is
// used as an indicator to switch off peepholes of the region and
// associated phis; see {@code inProgress()}.
ctrl(new LoopNode(ctrl()).peephole()); // Note we set back edge to null here
// At loop head, we clone the current Scope (this includes all
// names in every nesting level within the Scope).
// We create phis eagerly for all the names we find, see dup().
// Save the current scope as the loop head
ScopeNode head = _scope.keep();
// Clone the head Scope to create a new Scope for the body.
// Create phis eagerly as part of cloning
_xScopes.push(_scope = _scope.dup(true)); // The true argument triggers creating phis
// Parse predicate
var pred = require(parseExpression(), ")");
// IfNode takes current control and predicate
Node ifNode = new IfNode(ctrl(), pred).peephole();
// Setup projection nodes
Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep();
Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole();
// Clone the body Scope to create the break/exit Scope which accounts for any
// side effects in the predicate. The break/exit Scope will be the final
// scope after the loop, and its control input is the False branch of
// the loop predicate. Note that body Scope is still our current scope.
ctrl(ifF);
_xScopes.push(_breakScope = _scope.dup());
// No continues yet
_continueScope = null;
// Parse the true side, which corresponds to loop body
// Our current scope is the body Scope
ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection
parseStatement(); // Parse loop body
// Merge the loop bottom into other continue statements
if (_continueScope != null) {
_continueScope = jumpTo(_continueScope);
_scope.kill();
_scope = _continueScope;
}
// The true branch loops back, so whatever is current _scope.ctrl gets
// added to head loop as input. endLoop() updates the head scope, and
// goes through all the phis that were created earlier. For each phi,
// it sets the second input to the corresponding input from the back
// edge. If the phi is redundant, it is replaced by its sole input.
var exit = _breakScope;
head.endLoop(_scope, exit);
head.unkeep().kill();
_xScopes.pop(); // Cleanup
_xScopes.pop(); // Cleanup
_continueScope = savedContinueScope;
_breakScope = savedBreakScope;
// At exit the false control is the current control, and
// the scope is the exit scope after the exit test.
return _scope = exit;
}
private ScopeNode jumpTo(ScopeNode toScope) {
ScopeNode cur = _scope.dup();
ctrl(XCTRL); // Kill current scope
// Prune nested lexical scopes that have depth > than the loop head
// We use _breakScope as a proxy for the loop head scope to obtain the depth
while( cur._scopes.size() > _breakScope._scopes.size() )
cur.pop();
// If this is a continue then first time the target is null
// So we just use the pruned current scope as the base for the
// "continue"
if (toScope == null)
return cur;
// toScope is either the break scope, or a scope that was created here
assert toScope._scopes.size() <= _breakScope._scopes.size();
toScope.ctrl(toScope.mergeScopes(cur));
return toScope;
}
private void checkLoopActive() { if (_breakScope == null) throw Parser.error("No active loop for a break or continue"); }
private Node parseBreak () { checkLoopActive(); return ( _breakScope = require(jumpTo( _breakScope ),";")); }
private Node parseContinue() { checkLoopActive(); return (_continueScope = require(jumpTo( _continueScope ),";")); }
/**
* Parses a statement
*
*
* if ( expression ) statement [else statement]
*
* @return a {@link Node}, never {@code null}
*/
private Node parseIf() {
require("(");
// Parse predicate
var pred = require(parseExpression(), ")").keep();
// IfNode takes current control and predicate
Node ifNode = new IfNode(ctrl(), pred).peephole();
// Setup projection nodes
Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep();
Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole().keep();
// In if true branch, the ifT proj node becomes the ctrl
// But first clone the scope and set it as current
int ndefs = _scope.nIns();
ScopeNode fScope = _scope.dup(); // Duplicate current scope
_xScopes.push(fScope); // For graph visualization we need all scopes
// Parse the true side
ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection
_scope.upcast(ifT,pred,false); // Up-cast predicate
parseStatement(); // Parse true-side
ScopeNode tScope = _scope;
// Parse the false side
_scope = fScope; // Restore scope, then parse else block if any
ctrl(ifF.unkeep()); // Ctrl token is now set to ifFalse projection
_scope.upcast(ifF,pred,true); // Up-cast predicate
if (matchx("else")) {
parseStatement();
fScope = _scope;
}
pred.unkeep();
if( tScope.nIns() != ndefs || fScope.nIns() != ndefs )
throw error("Cannot define a new name on one arm of an if");
// Merge results
_scope = tScope;
_xScopes.pop(); // Discard pushed from graph display
return ctrl(tScope.mergeScopes(fScope));
}
/**
* Parses a return statement; "return" already parsed.
* The $ctrl edge is killed.
*
*
* 'return' expr ;
*
* @return an expression {@link Node}, never {@code null}
*/
private Node parseReturn() {
var expr = require(parseExpression(), ";");
Node ret = STOP.addReturn(new ReturnNode(ctrl(), expr, _scope).peephole());
ctrl(XCTRL); // Kill control
return ret;
}
/**
* Dumps out the node graph
* @return {@code null}
*/
Node showGraph() {
System.out.println(new GraphVisualizer().generateDotOutput(STOP,_scope,_xScopes));
return null;
}
/**
* Parses an expression statement or a declaration statement where type is a struct
*
*
* name; // Error
* type name; // Define name with default initial value
* type name = expr; // Define name with given initial value
* name = expr; // Reassign existing
* expr // Something else
*
* @return an expression {@link Node}, never {@code null}
*/
private Node parseExpressionStatement() {
int old = _lexer._position;
Type t = type();
String name = requireId();
Node expr;
if( match(";") ) { // Assign a default value
// No type and no expr is an error
if( t==null ) throw errorSyntax("expression");
expr = new ConstantNode(t.makeInit()).peephole();
} else if( match("=") ) { // Assign "= expr;"
expr = require(parseExpression(), ";");
} else { // Neither, so just a normal expression parse
_lexer._position = old;
return require(parseExpression(),";");
}
// Defining a new variable vs updating an old one
if( t != null ) {
if( _scope.define(name,t,expr) == null )
throw error("Redefining name '" + name + "'");
} else {
if( _scope.lookup(name)==null )
throw error("Undefined name '" + name + "'");
t = _scope.lookupDeclaredType(name);
}
// Auto-widen int to float
if( expr._type instanceof TypeInteger && t instanceof TypeFloat )
expr = new ToFloatNode(expr).peephole();
// Auto-deepen forward ref types
Type e = expr._type;
if( e instanceof TypeMemPtr tmp && tmp._obj._fields==null )
e = tmp.make_from((TypeStruct)TYPES.get(tmp._obj._name));
// Type is sane
if( !e.isa(t) )
throw error("Type " + e.str() + " is not of declared type " + t.str());
return _scope.update(name,expr);
}
// Parse a "type id" and return "type" (and re-parse "id" in caller) or
// return null.
private Type type() {
int old = _lexer._position;
String tname = _lexer.matchId();
if( tname==null ) return null;
boolean nullable = match("?");
Type t = TYPES.get(tname);
// Assume a forward-reference type
if( t == null ) {
int old2 = _lexer._position;
String id = _lexer.matchId();
if( id==null ) {
_lexer._position = old;
return null;
}
TYPES.put(tname,t = TypeStruct.make(tname));
_lexer._position = old2; // Reparse ID in caller
}
return t instanceof TypeStruct obj ? TypeMemPtr.make(obj,nullable) : t;
}
/**
* Parse an expression of the form:
*
*
* expr : compareExpr
*
* @return an expression {@link Node}, never {@code null}
*/
private Node parseExpression() { return parseComparison(); }
/**
* Parse an expression of the form:
*
*
* expr : additiveExpr op additiveExpr
*
* @return an comparator expression {@link Node}, never {@code null}
*/
private Node parseComparison() {
var lhs = parseAddition();
while( true ) {
int idx=0; boolean negate=false;
// Test for any local nodes made, and "keep" lhs during peepholes
if( false ) ;
else if( match("==") ) { idx=2; lhs = new BoolNode.EQ(lhs, null); }
else if( match("!=") ) { idx=2; lhs = new BoolNode.EQ(lhs, null); negate=true; }
else if( match("<=") ) { idx=2; lhs = new BoolNode.LE(lhs, null); }
else if( match("<" ) ) { idx=2; lhs = new BoolNode.LT(lhs, null); }
else if( match(">=") ) { idx=1; lhs = new BoolNode.LE(null, lhs); }
else if( match(">" ) ) { idx=1; lhs = new BoolNode.LT(null, lhs); }
else break;
// Peepholes can fire, but lhs is already "hooked", kept alive
lhs.setDef(idx,parseAddition());
lhs = lhs.widen().peephole();
if( negate ) // Extra negate for !=
lhs = new NotNode(lhs).peephole();
}
return lhs;
}
/**
* Parse an additive expression
*
*
* additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)*
*
* @return an add expression {@link Node}, never {@code null}
*/
private Node parseAddition() {
Node lhs = parseMultiplication();
while( true ) {
if( false ) ;
else if( match("+") ) lhs = new AddNode(lhs,null);
else if( match("-") ) lhs = new SubNode(lhs,null);
else break;
lhs.setDef(2,parseMultiplication());
lhs = lhs.widen().peephole();
}
return lhs;
}
/**
* Parse an multiplicativeExpr expression
*
*
* multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)*
*
* @return a multiply expression {@link Node}, never {@code null}
*/
private Node parseMultiplication() {
var lhs = parseUnary(); boolean mul;
while( true ) {
if( false ) ;
else if( match("*") ) lhs = new MulNode(lhs,null);
else if( match("/") ) lhs = new DivNode(lhs,null);
else break;
lhs.setDef(2,parseUnary());
lhs = lhs.widen().peephole();
}
return lhs;
}
/**
* Parse a unary minus expression.
*
*
* unaryExpr : ('-') | '!') unaryExpr | postfixExpr | primaryExpr
*
* @return a unary expression {@link Node}, never {@code null}
*/
private Node parseUnary() {
if (match("-")) return new MinusNode(parseUnary()).widen().peephole();
if (match("!")) return new NotNode(parseUnary()).peephole();
return parsePostfix(parsePrimary());
}
/**
* Parse a primary expression:
*
*
* primaryExpr : integerLiteral | Identifier | true | false | null | new Identifier | '(' expression ')'
*
* @return a primary {@link Node}, never {@code null}
*/
private Node parsePrimary() {
if( _lexer.isNumber(_lexer.peek()) ) return parseLiteral();
if( match("(") ) return require(parseExpression(), ")");
if( matchx("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole();
if( matchx("false") ) return ZERO;
if( matchx("null" ) ) return new ConstantNode(TypeMemPtr.NULLPTR).peephole();
if( matchx("new") ) {
String structName = requireId();
Type t = TYPES.get(structName);
if( !(t instanceof TypeStruct obj) || obj._fields==null )
throw error("Unknown struct type '" + structName + "'");
return newStruct(obj);
}
String name = _lexer.matchId();
if( name == null) throw errorSyntax("an identifier or expression");
Node n = _scope.lookup(name);
if( n!=null ) return n;
throw error("Undefined name '" + name + "'");
}
/**
* Return a NewNode but also generate instructions to initialize it.
*/
private Node newStruct(TypeStruct obj) {
Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep();
int alias = START._aliasStarts.get(obj._name);
for( Field field : obj._fields ) {
memAlias(alias, new StoreNode(field._fname, alias, field._type, ctrl(), memAlias(alias), n, new ConstantNode(field._type.makeInit()).peephole(),true).peephole());
alias++;
}
return n.unkeep();
}
// We set up memory aliases by inserting special vars in the scope these
// variables are prefixed by $ so they cannot be referenced in Simple code.
// Using vars has the benefit that all the existing machinery of scoping
// and phis work as expected
private Node memAlias(int alias ) { return _scope.lookup(memName(alias) ); }
private Node memAlias(int alias, Node st) { return _scope.update(memName(alias), st); }
public static String memName(int alias) { return ("$"+alias).intern(); }
/**
* Parse postfix expression. For now this is just a field
* expression, but in future could be array index too.
*
*
* expr ('.' IDENTIFIER)* [ = expr ]
*
*/
private Node parsePostfix(Node expr) {
if( !match(".") ) return expr;
if( !(expr._type instanceof TypeMemPtr ptr) )
throw error("Expected struct reference but got " + expr._type.str());
String name = requireId().intern();
if( expr._type == TypeMemPtr.TOP ) throw error("Accessing field '" + name + "' from null");
if( ptr._obj == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'");
TypeStruct base = (TypeStruct)TYPES.get(ptr._obj._name);
int idx = base==null ? -1 : base.find(name);
if( idx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'");
int alias = START._aliasStarts.get(ptr._obj._name)+idx;
if( match("=") ) {
// Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment
if( peek('=') ) _lexer._position--;
else {
Node val = parseExpression();
Type glb = base._fields[idx]._type;
memAlias(alias, new StoreNode(name, alias,glb, ctrl(), memAlias(alias), expr, val, false).peephole());
return expr; // "obj.a = expr" returns the expression while updating memory
}
}
Type declaredType = base._fields[idx]._type;
return parsePostfix(new LoadNode(name, alias, declaredType.glb(), memAlias(alias), expr).peephole());
}
/**
* Parse integer literal
*
*
* integerLiteral: [1-9][0-9]* | [0]
* floatLiteral: [digits].[digits]?[e [digits]]?
*
*/
private ConstantNode parseLiteral() {
return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole();
}
//////////////////////////////////
// Utilities for lexical analysis
// Return true and skip if "syntax" is next in the stream.
private boolean match (String syntax) { return _lexer.match (syntax); }
// Match must be "exact", not be followed by more id letters
private boolean matchx(String syntax) { return _lexer.matchx(syntax); }
// Return true and do NOT skip if 'ch' is next
private boolean peek(char ch) { return _lexer.peek(ch); }
private boolean peekIsId() { return _lexer.peekIsId(); }
// Require and return an identifier
private String requireId() {
String id = _lexer.matchId();
if (id != null && !KEYWORDS.contains(id) ) return id;
throw error("Expected an identifier, found '"+id+"'");
}
// Require an exact match
private Parser require(String syntax) { require(null, syntax); return this; }
private