CSc 453Compilers and Systems Software2 : Teensy Simple IDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergIntroductionA simple language and compilerTo understand the overall organization of a modern compiler,we will design a minimal language, Teensy, and a compilerfor this language, Simple.Get the source from the file Simple1.zip from the class website.Then unzip Simple1.zip; cd PROGRAMS; make; make test.Here’s a simple Teensy program:¨¥BEGINx = 5 ; y = 9 9 ; z = y + x + 9 ; PRINT z ;END§¦Teensy’s concrete grammarprogram → ’BEGIN’ stats ’END’stats → stat stats | ǫstat → ident ’=’ expr ’;’| ’PRINT’ expr ’;’expr → expr ’+’ expr | ident | intident → LETTER idpidp → LETTER idp | DIGIT idp | ǫint → DIGIT intpintp → DIGIT intp | ǫJava classes in the Simple compilerlexical analysis (Token, Lex),parsing (Matcher, Parse),abstract syntax tree construction (Parse, AST, PROGRAM,STAT, STATSEQ, ASSIGN, PRINT, EXPR, NULL, IDENT, INTLIT,BINOP),semantic analysis (SyTab, Sem),tree-walk interpretation (Eval), optimization (Opt),intermediate code generation (IR, GenIR),stack-code interpretation (Interpreter), andmachine-code generation (Mips).The class Compiler ties it all together.Overview – Lexing and ParsingsourceBEGIN,PRINT,INTLIT/42,PLUS,INTLIT/3,SEMICOLON,END,EOFPRINTPROGRAMNULLINTLIT/42INTLIT/3PLUSLexBEGINENDPRINT 42+3;ParseOverview – Semantics & OptimizationGenCPRINTPROGRAMNULLINTLIT/45PRINTPROGRAMNULLINTLIT/42INTLIT/3PLUSint main(char** args) {}printf("%i\n",45);GenIROptASTSem45Evalgcc45Overview – IR & Code GenerationGenIR .datanewline:.asciiz "\n" .text .align 2 .globl mainmain: li $s0,45 move $a0,$s0 li $v0,1 syscall la $a0,newline li $v0,4 syscall li $v0,10 syscall6,42,0,4,5,7# HEADER 42,0# PRINT# PRINTLN# EXIT3,45, # PUSH 45Interpreter45spim45MipsToken.javapublic class Token {public final static int ILLEGAL = 0;public final static int PLUS = 1;public final static int INTLIT = 2;public final static int IDENT = 3;public final static int SEMICOLON = 4;public final static int EQUAL = 5;public final static int BEGIN = 6;public final static int END = 7;public final static int PRINT = 8;public final static int EOF = 9;public int kind;public String ident; public int value;public int position;}Lex.javachar ch; // lookahead characterboolean done = false; // reached end-of-filepublic Lex(String filename) throws IOException {str = new LineNumberReader(new FileReader(filename));get();}// read the next input charactervoid get() {...}Token scanNumber() {...return new Token(Token.INTLIT, ival);}Lex.java. . .Token scanName() {String ident = "";while ((!done) && Character.isLetterOrDigit(ch)) {ident+=ch; get();}if (ident.equals("BEGIN"))return new Token(Token.BEGIN);else if (ident.equals("END"))return new Token(Token.END);else if (ident.equals("PRINT"))return new Token(Token.PRINT);elsereturn new Token(Token.IDENT, ident);}Lex.java. . .public Token nextToken() {while ((!done) && ch <= ’ ’) get();if (done) return new Token(Token.EOF);switch (ch) {case ’+’: get(); return new Token(Token.PLUS);case ’;’: get(); return new Token(Token.SEMICOLON);case ’=’: get(); return new Token(Token.EQUAL);default: if (Character.isLetter(ch))return scanName();else if (Character.isDigit(ch))return scanNumber();else {get(); return new Token(Token.ILLEGAL);}}}ParsingThe Lexer takes an input Teensy source fileBEGINPRINT y;ENDand generates a stream of tokensBEGINPRINTIDENT: ySEMICOLONENDEOFwhich is then consumed by the parser.ParsingThe parser does two things:1it checks that the input program conforms to the syntax of thelanguage. If not, error messages are generated.2it generates an abstract syntax tree (AST), a treerepresentation of the input program.Simple supports two parsers: Matcher only tests for syntaxconformance, Parse also generates the AST.The AST forms the basis for all further processing in Simple.Matcher.java. . .Lex scanner;Token currentToken;public Matcher (Lex scanner) {this.scanner = scanner;next();}void next() {currentToken = scanner.nextToken();}boolean lookahead(int tokenKind) {return currentToken.kind == tokenKind;}Matcher.java. . .void match(int tokenKind) {if (!lookahead(tokenKind)) {System.err.println("Parsing error");}next();}public void parse() {ENTER("parse");match(Token.BEGIN);stats();match(Token.END);match(Token.EOF);EXIT("parse");}Matcher.java. . .void stats() {if (lookahead(Token.IDENT)) {assign(); match(Token.SEMICOLON); stats();} else if (lookahead(Token.PRINT)) {print(); match(Token.SEMICOLON); stats();}}void assign() {match(Token.IDENT); match(Token.EQUAL); expr();}void print() {match(Token.PRINT); expr();}Matcher.java. . .void expr() {factor();while (lookahead(Token.PLUS)) {match(Token.PLUS);factor();}}void factor() {if (lookahead(Token.IDENT)) {match(Token.IDENT);} else if (lookahead(Token.INTLIT)) {match(Token.INTLIT);}}Parsing. . .> cat test23BEGINPRINT y;END> java Matcher test2ENTER parseENTER statsENTER printENTER exprENTER factorEXIT factorEXIT exprEXIT printENTER statsEXIT statsEXIT statsEXIT parseConcrete vs. Abstract SyntaxA language’s concrete syntax describes how it is written bythe programmer – where whitspace goes, where semicolonsare needed, etc.The abstract syntax describes the “logical structure” of thelanguage – that while-statements have two parts (theexpresion and the loop body), that procedure calls consist of asequence of actual parameters (expression) and the name ofthe called procedure, etc.The abstract syntax also defines the nodes of the abstractsyntax tree. For example, an AST while-node would have twochildren, one pointing to the expression subtree, the other tothe loop body subtree.Teensy’s Abstract SyntaxPROGRAM → STATSEQSTATSEQ → STAT STATSEQ| NULLSTAT → ASSIGN| PRINTASSIGN → ident EXPRPRINT → EXPREXPR → BINOP | IDENT | INTLITBINOP → op EXPR EXPRIDENT → identINTLIT → intAST, EXPR, INTLIT¨ ¥p u bli c a bs t r ac t c l a s s AST {}§¦¨¥p u bli c a bs t r ac t c l a s s EXPR ext en ds AST {}§¦¨¥p u bli c c l a s s INTLIT ex ten ds EXPR {p u bli c i n t v a l ;p u bli c INTLIT ( i n t v a l ) { t h i s . val = v a l ;}}§¦¨¥p u bli c c l a s s IDENT ex tends EXPR {p u bli c S t r i n g i d e n t ;p u bli c IDENT( Str i n g i d e n t ) {t h i s . ide n t = i d e n t ;