1CS553 Lecture Scanning and Parsing 3Scanning and ParsingAnnouncements– Pick a partner by Monday– Makeup lecture will be on Monday August 29th at 3pmToday– Outline of planned topics for course– Overall structure of a compiler– Lexical analysis (scanning)– Syntactic analysis (parsing)– The first project! CS553 Lecture Scanning and Parsing 4Topics I. The Basics– Scanning and parsing– Dataflow analysis– Control flow analysis II. Analyses and Representations– SSA Form– Redundancy elimination– Aliases– Interprocedural analysis III. Low-Level Optimizations– Register allocation– Instruction scheduling– Profile-guided and dynamic optimizations2CS553 Lecture Scanning and Parsing 5Topics (cont) IV. High-Level Optimizations– Dependence analysis– Loop transformations– Tiling– Object-oriented optimizations V. Emerging Topics– Run-time reordering transformations– Security and program checking– Domain-specific program analysis and transformationCS553 Lecture Scanning and Parsing 6Structure of a Typical Interpreter“sentences”Synthesisoptimizationcode generationtarget languageIRIR code generationIRAnalysischaracter streamlexical analysis“words”tokenssemantic analysissyntactic analysisASTannotated ASTinterpreterCompiler3CS553 Lecture Scanning and Parsing 7Lexical Analysis (Scanning) Break character stream into tokens (“words”)– Tokens, lexemes, and patterns– Lexical analyzers are usually automatically generated from patterns(regular expressions) (e.g., lex) Examples“.*”“hi”, “mom”string[0-9]+ | [0-9]*.[0-9]+3.14159,570number[a-zA-Z_]+[a-zA-Z0-9_]*foo,indexidentifier< | <= | = | != | ...<,<=,=,!=,...relationifififconstconstconstpatternlexeme(s)tokenconst pi := 3.14159 ⇒ const, identifier(pi), assign,number(3.14159)CS553 Lecture Scanning and Parsing 8Interaction Between Scanning and ParsingLexicalanalyzerParsercharacter streamyylex()tokenIR4CS553 Lecture Scanning and Parsing 9Specifying Tokens with Flex Theory meets practice:– Regular expressions, formallanguages, grammars, parsing… Flex example input file: %{ #include <stdlib.h> #include "top-token.h"%} DIGIT [0-9] ID [a-zA-Z][a-zA-Z0-9]* %% [=\{\}] { return yytext[0]; } if { return T_IF; } => { return T_MAPSTO; }"\/\/"[^\n]*"\n" // eat up one-line comments [ \t\n]+ // eat up whitespace {ID} { char *retstr; retstr = malloc(strlen(yytext)+1); strcpy(retstr,yytext); yylval.sval = retstr; return T_ID; } %%CS553 Lecture Scanning and Parsing 10Recognizing Tokens with DFAs [a-zA-Z][a-zA-Z0-9]* <= [=\{\}]otherletter or digitletter123other=<14 65T_LTET_ID5CS553 Lecture Scanning and Parsing 11 Impose structure on token stream– Limited to syntactic structure (⇒ high-level)– Structure usually represented with an abstract syntax tree (AST)– Parsers are usually automatically generated from grammars (e.g., yacc,bison, cup, javacc) Example for i = 1 to 10 do a[i] = x * 5; for id(i) equal number(1) to number(10) do id(a) lbracket id(i) rbracket equal id(x) times number(5) semiSyntactic Analysis (Parsing)fori 1 10 asgaitmsx5arrCS553 Lecture Scanning and Parsing 12Interaction Between Scanning and ParsingLexicalanalyzerParsercharacter streamyylex()tokenIR6CS553 Lecture Scanning and Parsing 13Using bison or yacc with flex or lexbison assumes that yylex() function has been defined.bison example input file: %union { char* sval; int ival; Expr* exprptr; std::list<Stmt*> stmtlistptr; }; %token <sval> T_STR_LITERAL %token <ival> T_INT_LITERAL %token T_IF T_THEN T_ELSE %type <exprptr> Expr %type <stmtlistptr> StmtList Proc: StmtList ; StmtList: StmtList Stmt | /*empty*/ ; Stmt: T_IF Expr T_THEN StmtList T_ELSE StmtList | /*other stmts*/ ;CS553 Lecture Scanning and Parsing 14Shift-Reduce Parsing7CS553 Lecture Scanning and Parsing 15Parsing Terms CFG (Context-free Grammer) BNF (Backus-Naur Form) and EBNF (Extended BNF): equivalent to CFGCS553 Lecture Scanning and Parsing 16Parsing Terms cont … Top-down parsing– LL(1): left-to-right reading of tokens, leftmost derivation, 1 symbol lookahead– Predictive parser: an efficient non-backtracking top-down parser that can handleLL(1)– More generally recursive descent parsing may involve backtracking Bottom-up Parsing– LR(1): left-to-right reading of tokens, rightmost derivation in reverse, 1 symbollookahead– Shift-reduce parsers: for example, bison and yacc generated parsers– Methods for producing an LR parsing table– SLR, simple LR– Canonical LR, most powerful– LALR(1)8CS553 Lecture Scanning and Parsing 17Project 1: Scanners and Parsers for OpenAnalysis Test Input // int main() { PROCEDURE = { < ProcHandle("main"), SymHandle("main") > } // int x; LOCATION = { < SymHandle("x"), local > } // int *p; LOCATION = { < SymHandle("p"), local > } // all other symbols visible to this procedure LOCATION = { < SymHandle("g"), not local > } // x = g; MEMREFEXPRS = { StmtHandle("x = g;") => [ MemRefHandle("x_1") => < SymHandle("x"), DEF > MemRefHandle("g_1") => < SymHandle("g"), USE > ] }CS553 Lecture Scanning and Parsing 18OpenAnalysis Problem: Insufficient analysis support in existing compilerinfrastructures due to non-transferability of analysis implementations Decouples analysis algorithms from intermediate representations(IRs) by developing analysis-specific interfaces Analysis reuse across compiler infrastructures– Enable researchers to leverage prior work– Enable direct comparisons amongst analyses– Increase the impact of compiler analysis research9CS553 Lecture Scanning and Parsing 19Software Architecture for OpenAnalysisClientsToolkitIntermediateRepresentationCS553 Lecture Scanning and Parsing 20Project 1: Basic Outline1) Download and build OpenAnalysis2) Copy Project1.tar to your CS directory and build3) Implement 3 parsers that build up certain parts of a subsidiary IRusing the examples in testSubIR.cpp and Input/testSubIR.oa4) Next week start testing FIAlias implementation in OpenAnalysis10CS553 Lecture Scanning and Parsing 21Concepts Compilation stages in a compiler– Scanning, parsing, semantic analysis, intermediate code generation,optimization, code generation Lexical analysis or scanning– Tools: lex, flex, etc. Syntactic analysis or parsing– Tools: yacc, bison, etc.CS553 Lecture Scanning and Parsing 22Next TimeLecture– Undergrad compilers in a