吉大编译课件scanning-5.ppt

Compiler Construction Principles Implementation Techniques Dr. Zheng Xiaojuan Professor Software College of Northeast Normal University March. 2010 Summary for Last Lecture Regular Expression (RE) Some concepts and operations on strings set of strings; Definition of RE Regular Definition Generating NFA from Regular Expression rules Outline 2.1 Overview 2.1.1 General Function of a Scanner 2.1.2 Some Issues about Scanning 2.2 Finite Automata 2.2.1 Definition and Implementation of DFA 2.2.2 Non-Determinate Finite Automata 2.2.3 Transforming NFA into DFA 2.2.4 Minimizing DFA 2.3 Regular Expressions 2.3.1 Definition of Regular Expressions 2.3.2 Regular Definition 2.3.4 From Regular Expression to DFA 2.4 Design and Implementation of a Scanner 2.4.1 Developing a Scanner from DFA 2.4.2 A Scanner Generator – Lex 2.4 Design and Implementation of a Scanner Developing a Scanner Manually A Scanner Generator – Lex Developing a Scanner Manually Implement Scanner with DFA Implementation of DFA Just checking whether a string is acceptable by the DFA; Implementation of a Scanner not checking; but recognizing an acceptable string(word) and establish its internal representation token-type, semantic information Implement Scanner with DFA Some Issues Independent or Attached Skip these special characters Blank, Tab, comments, return (line number) When to stop scanning At the end of the source file Keywords identifier How to know the end of recognizing one token? 立即接受状态和延迟接受状态 Defining Lexical Structure of C0 letter = a|…|z|A|…|Z digit = 0|…|9 NZ-digit = 1|…|9 Reserved = {| }| read| write Identifier =letter(letter|digit)* Constant: int = NZ-digit digit* | 0 Other symbols: syms = +|*| := | ; Lexical structure: lex = Reserved | identifier |int | syms DFA for C0 Developing a Scanner from DFA Input: a sequence of symbols, with a special symbol EOF as the end of the sequence; Output: a sequence of tokens; Developing a Scanner from DFA Developing a Sc