编译原理 第 3 讲 词法分析.ppt

作 业 PP 72-73 题4(a) ；题7；题8 六、正规文法和有穷自动机间的转换 1.采用下面的规则从正规文法G=(VT, VN, S, P)直接构造一个有穷自动机NFA M=(∑, K, f, k0, Z)，使得：L(M)=L(G)： 字母表与 G 的终结符集相同， ∑ = VT； 增加一个新状态kf ，作为NFA的终态，Z = {kf }；G中的每个非终结符作为M的一个状态，(不妨取称相同的名字), K = VN ∪{kf}；G的开始符号为M的开始状态，k0=S； 对G中的形如A→aB的产生式（其中a为终结符或ε，A和B为非终结符），构造M的一个转换函数f(A,a)=B； 对G中形如A→a的产生式,构造M的一个转换函数f(A,a)=Z。 右线性文法 例1：与文法G[S]等价的NFA M(右线性) G[S]：S→aA S→bB S→ε A→aB A→bA B→aS B→bA B→ε S A B Z a a b b a ε ε b 采用下面的规则将一个有穷自动机NFA M转换成正规文法G ，使得L(G)=L(M)： G的终结符集与字母表相同； M的每一个状态对应G中的每个非终结符,开始状态S是G的开始符号； 转换函数f(A,a)=B对应G中的形如A→aB的产生式（其中a为终结符或ε，A和B为非终结符）； 对终态结点Z,对应G中形如Z→ε的产生式。 例:为下面的DFA N，构造出等价的正规文法G。 B C a b A D a a b b b 文法G[A]： A→aB | bD B→bC C→aA |bD |ε D→aB |bD |ε 七、词法分析程序的自动构造工具 把正规式转换为一个NFA进而转换为相应的DFA，由此构造出词法分析程序。 LEX编译系统 二、不确定的有穷自动机NFA 定义 N = (K，?，f，S，Z)，其中K为状态的有穷非空集， ? 为有穷输入字母表，f为映射函数，f: K? ?* → 2K，S?K是初始状态集，Z ?K为终止状态集。 1. 状 态 图 表 示 例子 NFA N=（{S，P，Z}，{0，1}，f，{S，P}，{Z}） 其中 ： f（S，0）={P} f（S，1）={S，Z} f（P，1）={Z} f（Z，0）={P} f（Z，1）={P} S P Z 0 0,1 1 1 1 2. 矩 阵 表 示 简化为 例：NFA N=（{S，P，Z}，{0，1}，f，{S，P}，{Z}）其中：  f（S，0）= {P} f（S，1）= {S，Z} f（P，1）= {Z} f（Z，0）= {P} f（Z，1）= {P} ∑*上的符号串t在NFA N上运行。 ∑*上的符号串t被NFA N接受（识别）。 具有 ? 转移的不确定的有穷自动机 NFAf为 K? （? ? {?}）到2K的的映射。 对任何一个具有?转移的不确定的有穷自动机NFA N，一定存在一个不具有?转移的不确定的有穷自动机NFA　Ｍ ，使得L(M)=L(N)。 DFA M=（K，Σ，f，S，Z） 的行为的模拟程序 K:=S； c:=getchar; while ceof do {K:=f(K,c); if K= ? then break else c:=getchar; }; if K is in Z then return (‘yes’) else return (‘no’) 三、 NFA 的 确 定 化 DFA是NFA的特例.对每个DFA M一定存在一个NFA Ｍ ，使得 L(M)=L(M )。 对每个NFA M存在着与之等价的DFA M 。与某一NFA等价的DFA不唯一。 1. 定义对状态集合I的几个有关运算 1 状态集合 I 的 ?-闭包，表示为 ?-closure(I)，定义为一状态集，是状态集 I 中的任何状态 R 经任意条 ? 弧而能到达的状态的集合。状态集合I的任何状态 R 都属于 ?-closure(I)。 2 状态集合 I 的 a 弧转换，表示为 move(I,a) 定义为状态集合 J，其中 J 是所有那些可从 I 的某一状态经过一条 a 弧而到达的状态的全体。 3 定义：Ia = ?-closure(J)，其中：J= move(I,a) 例 I = {1}, ?-closure(I) = {1, 2}； I = {5}, ?-closure(I) = {5, 6, 2}； move({1,2},a) = { 5,4