Chapter04LexicalAnalysis词法分析.pptVIP

北京化工大学信息科学与技术学院计算机系 北京化工大学 信息科学与技术学院计算机系 赵瑞莲 rlzhao@ 编译感兴趣的问题是:　 给定x, G, 求x ? L(G) ? Chapter 4 Scanning (lexical analysis)词法分析 4.1?扫描处理 4.2 正则表达式 4.3 有穷自动机 4.4?从正规表达式到DFA 4.4.1 从正则表达式到NFA 4.4.2 从NFA到DFA 4.4.3 DFA的化简 4.5 TINY扫描程序的实现 4.6 利用L e x自动生成扫描程序 4.1?扫描处理 ● Tokens(记号)的枚举表示 4. 2 正则表达式 ● Basic Regular Expression 基本正则表达式 ● Regular Expression Operation 正则表达式的运算 ● 用正则表达式的运算符构造正则表达式 4.2.2 Extensions to Regular Expressions 4.2.3 Regular Expressions for Programming Language Tokens 记号的正则表达式 4.2.3 Regular Expressions for Programming Language Tokens 4.2.4 正则文法 4.3 有穷自动机 4.3.1 状态转换图 例2：识别标识符的转换图 文法： 1. 标识符::= 字母 | 标识符字母 | 标识符数字 2. 无符号整数::=数字 | 无符号整数数字 3. 单字符分界符::= : | + | * | , | ( | ) 4. 双字符分界符::= 冒号= 5. 冒号::= : 4.3.2 Finite Automata有穷自动机 ● Example： Numbers 数 ● 状态表 4. 3.2.2 Nondeterministic finite automation(NFA) 非确定有穷自动机 4.3.3 Implementation of finite automata in Code 用代码实现有穷自动机 4.4 From Regular Expression To DFA从正则表达式到DFA 4.4.1 From Regular Expression To NFAs从正则表达式到NFA 例：令∑={a,b}， ∑上所有含有两个相继的a或两个相继的b的字的集合——用NFA表示如下： 例1：NFA转换成DFA (符号合并) 4.4.3 DFA的化简 (极小化) Q and A Beijing University of Chemical Technology Beijing,?P R China 定义1：状态集合I的ε-闭包： 令I是一个状态集的子集，定义ε-closure（I）为： 1）若s∈I，则s∈ε-closure（I）； 2）若s∈I，则从s出发经过任意条ε弧能够到达的任何 状态都属于ε-closure（I）。 状态集ε-closure（I）称为I的ε-闭包 为了使得NFA确定化，给出两个定义： 5 6 4 3 2 a ε a a ε 1 例：如图所示的状态图： 令I={1}，求ε-closure（I）=？ 解：根据定义： ε-closure（I）={1，3} — J是从状态子集I中的每个状态出发，经过标记为a的弧而达到的状态集合。 — Ia是状态子集,其元素为J中的状态，加上从J中每一个状态出发通过ε弧到达的状态。 定义2: 状态子集的构造： s∈I Ia=ε-closure(J) =ε-closure(T(1，a)） =ε-closure({2，4}） ={2，4，6} 例：令I={1}，求Ia=? 5 6 4 3 2 a ε a a ε 1 令I是NFA M’的状态集的一个子集, a∈Σ 定义: Ia=ε-closure(J) 其中J = ∪T(s,a) 例：有NFA M，求DFA M’。 a 1 2 3 4 start a b a c c ε {2,3} φ φ {2} {4} {3,4} {2} {2} {4} φ {4} φ φ φ {3,4} φ φ {3,4} 初态 I=ε-closure({1})={1,4} Ia=ε-