import java.io.IOException; import java.io.PrintWriter; import java.io.FileWriter; import java.util.Vector; import java.util.Iterator; /** * An example parser/code-generator for a simple language. * * For CS 212, Feb 2004. * * program -> {statement} end . * statement -> name = expression ; * statement -> do expression : {statement} end ; * expression -> part [(+|-|*|/) part] * part -> ( name | number | (expression) ) * name -> ( x|y|z ) * * @author Paul Chew */ public class SimpleLanguage { public static void main (String[] args) throws IOException { SimpleTokenizer tokenizer = new SimpleTokenizer("test.txt"); PrintWriter out = new PrintWriter(new FileWriter("try.sam")); Program tree = new Program(tokenizer); System.out.println(tree); tree.generate(out); tokenizer.close(); out.close(); } } class ParseException extends RuntimeException { public ParseException (String string) { super(string); } } /** * Parent class for all AST nodes. This class is not instantiated, but it makes * a good place for parse-related tools. */ abstract class ASTNode { static int count = 0; // Used to generate unique numbers for labels static String[] operatorCommands = new String[]{"ADD", "SUB", "TIMES", "DIV"}; /** * Increment the current count and return it. */ public static int getCount () { count += 1; return count; } /** * Generate code for this AST node. */ abstract public void generate (PrintWriter output); /** * Throw an exception if token does not match. */ public static void match (String token, String expectedToken) { if (token.equals(expectedToken)) return; throw new ParseException("Expected <" + expectedToken + "> not <" + token + ">"); } /** * Parse a statement. This is here because there are no 'statement' nodes * in the AST; instead, each type of statement has its own node. */ public static ASTNode statement (SimpleTokenizer tokenizer) throws IOException { String token = tokenizer.next(); tokenizer.pushBack(); if (token.equals("do")) return new DoStatement(tokenizer); return new AssignmentStatement(tokenizer); } /** * Parse an expression. This is here because there are no 'expression' nodes * in the AST; instead, there are Operator, Variable, and Number nodes. */ public static ASTNode expression (SimpleTokenizer tokenizer) throws IOException { ASTNode tree = part(tokenizer); String token = tokenizer.next(); tokenizer.pushBack(); if ((token.length() == 1) && ("+-*/".indexOf(token) >= 0)) tree = new Operator(tokenizer, tree); return tree; } /** * Parse part of an expression. Again, there are no 'part' nodes in the AST; * instead, there are Operator, Variable, and Number nodes. */ public static ASTNode part (SimpleTokenizer tokenizer) throws IOException { String token = tokenizer.next(); tokenizer.pushBack(); if ((token.length() == 1) && ("xyz".indexOf(token) >= 0)) return new Variable(tokenizer); if (Character.isDigit(token.charAt(0))) return new Number(tokenizer); if (token.equals("(")) { ASTNode.match(tokenizer.next(), "("); ASTNode exp = ASTNode.expression(tokenizer); ASTNode.match(tokenizer.next(), ")"); return exp; } throw new ParseException("Bad token in expression: " + token); } } /** * Program. */ class Program extends ASTNode { Vector statements = new Vector(); // List of all statements in program public Program (SimpleTokenizer tokenizer) throws IOException { String token = tokenizer.next(); tokenizer.pushBack(); while (!token.equals("end")) { statements.add(ASTNode.statement(tokenizer)); token = tokenizer.next(); tokenizer.pushBack(); } ASTNode.match(tokenizer.next(), "end"); ASTNode.match(tokenizer.next(), "."); } public String toString () { if (statements.size() == 0) return "Prog()"; String s = "Prog("; Iterator it = statements.iterator(); s = s + it.next(); while (it.hasNext()) s = s + "," + it.next(); return s + ")"; } public void generate (PrintWriter output) { ASTNode statement; output.println("ADDSP 3"); Iterator it = statements.iterator(); while (it.hasNext()) { statement = (ASTNode) it.next(); statement.generate(output); } output.println("WRITE"); output.println("WRITE"); output.println("WRITE"); output.println("STOP"); } } /** * Do statement. */ class DoStatement extends ASTNode { ASTNode exp; Vector statements = new Vector(); public DoStatement (SimpleTokenizer tokenizer) throws IOException { ASTNode.match(tokenizer.next(), "do"); exp = ASTNode.expression(tokenizer); ASTNode.match(tokenizer.next(), ":"); String token = tokenizer.next(); tokenizer.pushBack(); while (!token.equals("end")) { statements.add(ASTNode.statement(tokenizer)); token = tokenizer.next(); tokenizer.pushBack(); } ASTNode.match(tokenizer.next(), "end"); ASTNode.match(tokenizer.next(), ";"); } public String toString () { String s = "do(" + exp; Iterator it = statements.iterator(); while (it.hasNext()) s = s + "," + it.next(); return s + ")"; } public void generate (PrintWriter output) { ASTNode statement; int doNumber = ASTNode.getCount(); exp.generate(output); output.println("do" + doNumber + ": DUP"); output.println("NOT"); output.println("JUMPC end" +doNumber); Iterator it = statements.iterator(); while (it.hasNext()) { statement = (ASTNode) it.next(); statement.generate(output); } output.println("PUSHIMM 1"); output.println("SUB"); output.println("JUMP do" + doNumber); output.println("end" + doNumber + ": ADDSP -1"); } } /** * Assignment statement. */ class AssignmentStatement extends ASTNode { String variable; ASTNode exp; public AssignmentStatement (SimpleTokenizer tokenizer) throws IOException { String token = tokenizer.next(); if ((token.length() == 1) && ("xyz".indexOf(token) >= 0)) variable = token; else throw new ParseException("Expected x, y, or z, not " + token); ASTNode.match(tokenizer.next(), "="); exp = ASTNode.expression(tokenizer); ASTNode.match(tokenizer.next(), ";"); } public String toString () { return "Assign(" + variable + "," + exp + ")"; } public void generate (PrintWriter output) { exp.generate(output); output.println("STOREOFF " + "xyz".indexOf(variable)); } } /** * Variable. */ class Variable extends ASTNode { String variable; public Variable (SimpleTokenizer tokenizer) throws IOException { variable = tokenizer.next(); } public String toString () { return variable; } public void generate (PrintWriter output) { output.println("PUSHOFF " + "xyz".indexOf(variable)); } } /** * Number. */ class Number extends ASTNode { int number; public Number (SimpleTokenizer tokenizer) throws IOException { number = Integer.parseInt(tokenizer.next()); } public String toString () { return String.valueOf(number); } public void generate (PrintWriter output) { output.println("PUSHIMM " + number); } } /** * Operator. */ class Operator extends ASTNode { String op; ASTNode left, right; public Operator (SimpleTokenizer tokenizer, ASTNode leftTree) throws IOException { left = leftTree; op = tokenizer.next(); right = ASTNode.part(tokenizer); } public String toString () { return op + "(" + left + "," + right + ")"; } public void generate (PrintWriter output) { left.generate(output); right.generate(output); String command = operatorCommands["+-*/".indexOf(op)]; output.println(command); } }