吉大编译课件scanning-5.ppt

Compiler Construction Principles & Implementation Techniques
Dr. Zheng Xiaojuan
Professor
Software College of Northeast Normal University
March. 2010
1
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
2
Outline
Overview
General Function of a Scanner
Some Issues about Scanning
Finite Automata
Definition and Implementation of DFA
Non-Determinate Finite Automata
Transforming NFA into DFA
Minimizing DFA
Regular Expressions
Definition of Regular Expressions
Regular Definition
From Regular Expression to DFA
Design and Implementation of a Scanner
Developing a Scanner from DFA
A Scanner Generator – Lex
√
√
√
3
Design and Implementation of a Scanner
Developing a Scanner Manually
A Scanner Generator – Lex
4
Developing a Scanner Manually
Develop a
Scanner
Lexical Definition in
Regular Expression
NFA
DFA
transforming
transforming
minimized
DFA
minimizing
implement
5
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>
6
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?
7
立即接受状态和延迟接受状态
;
:
=
other
d
d
other
立即接受状态
立即接受状态
延迟接受状态
延迟接受状态
 return(SEMI,;)
 return(ASS,:=)
 return(COLON,:) BACK()
 return(NUM,number) BACK()
*
*
8
Defining Lexical Structure of C0
letter = a|…|z|A|…|Z
digit = 0|…|9
NZ-digit = 1|…|9
Reserved = {| }| read| write
Identifier =letter(letter|digit)*