Thomson's Construction (cont.) For regular expression ri r2 N(r2) Final state of N(r2)become final state of N(r r2) NFA for rr2 For regular expression r* N(r) NFA for r CS308 Compiler Theory 16
Thomson’s Construction (cont.) • For regular expression r1 r 2 i f N(r2 N(r ) 1) Final state of N(r 2) become final state of N(r1r 2 ) NFA for r1 r 2 • For re gular ex pression r * g p i N(r) f ε ε ε NFA for r * ε CS308 Compiler Theory 16
Converting Regular Expressions Directly to DFAs We may convert a regular expression into a DFA(without creating a NFA first). First we augment the given regular expression by concatenating it with a special symbol # r→(r)# augmented regular expression Then,we create a syntax tree for this augmented regular expression. In this syntax tree,all alphabet symbols(plus and the empty string)in the augmented regular expression will be on the leaves,and all inner nodes will be the operators in that augmented regular expression. Then each alphabet symbol(plus #)will be numbered(position numbers). CS308 Compiler Theory 17
Converting Regular Expressions Directly to DFAs • We may convert a regular expression into a DFA (without creating a NFA fi ) rst ). • First we augment the given regular expression by concatenating it with a speci l b l# i a l sym b o l #. r Î (r)# augmented regular expression • Th t t t f thi t d l i Then, we crea te a syn tax tree for this augmen t e d regu lar express ion. • In this syntax tree, all alphabet symbols (plus # and the empty string) in the augmented regular expression will be on the leaves and all inner the augmented regular expression will be on the leaves, and all inner nodes will be the operators in that augmented regular expression. • Then each alphabet symbol (plus #) will be numbered (position Then each alphabet symbol (plus #) will be numbered (position numbers). CS308 Compiler Theory 17
Minimizing Number of States of a DFA partition the set of states into two groups -G:set of accepting states -G2:set of non-accepting states ·For each new group G - partition G into subgroups such that states s and s2 are in the same group iff for all input symbols a,states s and s2 have transitions to states in the same group. 。 Start state of the minimized DFA is the group containing the start state of the original DFA. Accepting states of the minimized DFA are the groups containing the accepting states of the original DFA. CS308 Compiler Theory 18
Minimizing Number of States of a DFA • partition the set of states into two groups: – G1 : set of accepting states – G 2 : set of non-accepting states • For each new group G – partition G into subgroups such that states s1 and s 2 are in the same group iff for all input symbols a, states s1 and s 2 have transitions to states in the same group. • Start state of the minimized DFA is the group containing the start state of the original DFA. • A i f h i i i d DFA h i i Accept ing states o f t he m i n i m ize d DFA are t he groups conta i n ing the accepting states of the original DFA. CS308 Compiler Theory 18
Exercise 1 CS308 Compiler Construction 9
Exercise 1 CS308 Compiler Construction 19
Syntax Analyzer Syntax Analyzer creates the syntactic structure of the given source program. This syntactic structure is mostly a parse tree. Syntax Analyzer is also known as parser. The syntax of a programming is described by a context-free grammar (CFG).We will use BNF(Backus-Naur Form)notation in the description of CFGs. 。 The syntax analyzer(parser)checks whether a given source program satisfies the rules implied by a context-free grammar or not. -If it satisfies,the parser creates the parse tree of that program. Otherwise the parser gives the error messages. A context-free grammar gives a precise syntactic specification of a programming language. -the design of the grammar is an initial phase of the design of a compiler. a grammar can be directly converted into a parser by some tools. CS308 Compiler Theory 20
Syntax Analyzer • Syntax Analyzer creates the syntactic structure of the given source program. • Thi i i l This syntactic structure is mostly a parse tree. • Syntax Analyzer is also known as parser. • The syntax of a programming is described by a The syntax of a programming is described by a context context-free grammar (CFG) free grammar (CFG). We will We will use BNF (Backus-Naur Form) notation in the description of CFGs. • The syntax analyzer (parser) checks whether a given source program satisfies the rules i li d b implied by a context-free grammar or not. – If it satisfies, the parser creates the parse tree of that program. – Otherwise the parser gives the error messages. • A context-free grammar – gives a precise syntactic specification of a programming language. – the desigg p g p n of the grammar is an initial phase of the design of a compiler. – a grammar can be directly converted into a parser by some tools. CS308 Compiler Theory 20