Topic 2 Compiler Front End Reading List Aho Sethi Ullman Chapter 3 1 3 3 3 5 Chapter 4 1 4 3 Chapter 5 1 5 3 Note Glance through it only for ntuitive understanding Also some slides from 2 and 2a are from other sources such as Prof Nelson Prof W M Hsu s slides with modification 01 14 19 course cpeg421 08s Topic 2 ppt 1 What Does the Front end Do 1 Translate programs from source language representation to an internal form suitable for compiler optimization and code generation 2 Consist of those phases that depend on the source language but largely independent of the target machine 01 14 19 course cpeg421 08s Topic 2 ppt 2 The Structure of Front End Lexical analysis Stream of characters are grouped into tokens for follow up processing Syntax analysis Tokens are grouped hierarchically with target syntactic structure Semantic Analysis Ensure the components of a program fit together Intermediate Code Generation A internal representation for later processing code optimization and generation 01 14 19 course cpeg421 08s Topic 2 ppt 3 Lexical Analysis Example a b c 100 Lexical analysis characters are grouped into seven tokens a b c identifiers assignment symbol operators 100 number 01 14 19 course cpeg421 08s Topic 2 ppt 4 Syntax Analysis Example a b c 100 The seven tokens are grouped into a parse tree Assignment stmt identifier a expression expression expression identifier c 100 b 01 14 19 course cpeg421 08s Topic 2 ppt 5 Semantic Analysis Example a b c 100 Checks for semantic errors and gathers type information for code generation a a b b c c 01 14 19 100 course cpeg421 08s Topic 2 ppt Int to real 100 6 Intermediate Representative Example a b c Int to real temp1 int to real 100 temp2 id3 c temp1 temp3 id2 b temp2 id1 a temp3 100 01 14 19 course cpeg421 08s Topic 2 ppt 7 Lexical Analyzer and Parser source program lexical analyzer token attribute value get next token Parser IR symbol table pass token and 01 14 19 course cpeg421 08s Topic 2 ppt 8 Lexical Analysis Perform lexical analysis on the input program i e partition input program text into subsequences of characters corresponding to tokens while leaving out white space and comments 01 14 19 course cpeg421 08s Topic 2 ppt 9 Lexical Analyzer Functions Grouping input characters into tokens Stripping out comments and white spaces Correlating error messages with the source program Issues why separating lexical analysis from parsing Simpler design Compiler efficiency Compiler portability 01 14 19 course cpeg421 08s Topic 2 ppt 10 Token definition How are tokens defined for a programming language and recognized by a scanner By using regular expressions to specify tokens as a formal regular language Example Specify language of unsigned numbers e g 5280 39 37 0 1 1 0 as a regular expression 01 14 19 course cpeg421 08s Topic 2 ppt 11 Examples of Tokens token smallest logically cohesive sequence of characters of interest in source program Single character operators Multi character operators Keywords if while Identifiers my variable flag1 My Variable Numeric constants literals 123 45 67 8 9e 05 Character literals a String literals abcd 01 14 19 course cpeg421 08s Topic 2 ppt 12 Examples of Non Tokens White space space tab end of line Comments None of this text forms a token 01 14 19 course cpeg421 08s Topic 2 ppt 13 Regular Expressions RE Why RE Suitable for specifying the structure of tokens in programming languages Basic concept A RE defines a set of strings called regular set Vocabulary Alphabet a finite character set V Strings are built from V via catenation Three basic operations concatenation 01 14 19 14 alternation course cpeg421 08s Topic 2 ppt and closure Solution For convenience in defining the regular expression we introduce a sequence of regular definitions of the form digit int optional fraction num 0 1 9 digit int int optional fraction Observation Only three rules to build a regular expression concatenation alternation and closure 01 14 19 course cpeg421 08s Topic 2 ppt 15 Building a Recognizer for a Regular Language General approach 1 Directly build deterministic finite automaton DFA from regular expression E 2 Build a NFA from regular expression E Simulate execution of NFA to determine whether an input string belongs to L E Note These days the DFA construction will be done automatically by the lex tool 01 14 19 course cpeg421 08s Topic 2 ppt 16 Example Use Transition Diagram to Recognize Identifier ID letter letter digit letter or digit letter start 9 other 10 11 return id indicates input retraction 01 14 19 course cpeg421 08s Topic 2 ppt 17 Mapping transition diagrams into C code letter or digit start 9 letter 10 other 11 return id switch state case 9 c nextchar if isletter c state 10 else state failure break case 10 case 11 retract 1 insert id return 01 14 19 course cpeg421 08s Topic 2 ppt 18 LEX Lex A Language for Specifying Lexical Analyzers Implemented by Lesk and Schmidt of Bell Lab initially for Unix Not only a table generator but also allows actions to associate with RE s Lex is widely used in the Unix community Lex is not efficient enough for production compilers however 01 14 19 course cpeg421 08s Topic 2 ppt 19 Using Lex Lex source program lex l Lex compiler lex yy c lex yy c C compiler a out a out sequence of tokens Input stream 01 14 19 course cpeg421 08s Topic 2 ppt 20 Syntactic Analysis Syntax analysis and context free grammars Bottom up parsing Syntax analysis Parsing tokens parse tree syntactic structure of input program Based on context free grammar CFG 01 14 19 course cpeg421 08s Topic 2 ppt 21 Context Free Grammar CFG A context free grammar is a formal system that describes a language by specifying how any legal text can be derived from a distinguished symbol It consists of a set of productions each of which states that a given symbol can be replaced by a given sequence of symbols 01 14 19 course cpeg421 08s Topic 2 ppt 22 Why CFG CFG gives a precise syntactic specification of a programming language Automatic efficient parser generator Enabling automatic translator generator Language extension becomes easier CFG can be used to replace RE 01 14 19 course cpeg421 08s Topic 2 ppt 23 Syntax Analysis Problem Statement Find a derivation sequence in grammar G for the input token stream or say that none exists Rightmost derivation sequence a derivation sequence in which the rightmost nonterminal is replaced in every step Leftmost derivation sequence is defined analogously 01 14 19 course cpeg421 08s Topic 2 ppt 24