compiler-principle03_2.ppt

程序设计语言编译原理 张淑艳zhang shu yan 温故知新 上下文无关文法 温故知新 P35第4题 2 P36第6题第8题 i i i i i第10题第11题L2和L4 温故知新 注释 编辑性字符 inta b 温故知新 3 2 3状态转换图有限方向图 结点表示状态 状态间用箭弧连接 箭弧上的标记 符号 代表射出结点状态下有可能出现的输入字符或字符类 0 1 2 X Y 一张状态转换图有 1 有限个状态 2 一个初态 3 一个或多个终态 用双圈表示 一个状态转换图可用于识别 或接受 一定字符串 上图为接受X和Y的状态转换图 温故知新 标识符 以字母开头的字母数字串 例 0 10 n n 0 D是死状态 3 2词法分析器的设计 在限制的基础上 步骤 1 了解该语言的单词符号步骤 2 为单词符号构造状态转换图步骤 3 状态转图的计算机实现 3 2词法分析器的设计 3 2 4状态转换图的实现每个状态对应一小段程序例 预备工作 1 ch字符变量 存放最新读入的字符 2 strToken字符数组 存放一个单词符号 1 GetChar读一个字符 存入ch 指针下移 2 GetBC检查当前ch是否为空白 若是 调用GetChar一直至找到一个非空白字符为止 3 Concat将ch中的字符接到strToken之后 全局部变 函数 3 2词法分析器的设计 4 IsLetter判断ch是否为字母 5 IsDigit判断ch是否为数字 6 Reserve将strToken中的字符串与保留字表对照若是保留字 则返回编号 否则返回0 7 Retract指针回调一个字符位置 8 InsertID将strToken中的标识符插入符号表 返回指针 9 InsertConst将strToken中的常数插入常数表 返回指针 函数 3 2词法分析器的设计 预备知识每个状态对应一小段程序自环状态 while for do GetChar While IsLetter orIsDigit getChar 状态j的对应程序 3 2词法分析器的设计 分叉状态 switch ifthenelse GetChar If IsLetter 状态j对应的程序 Elseif IsDigit 状态k对应的程序 Elseif ch 状态l对应的程序 Else 出错处理 intcode value strToken GetChar GetBC If IsLetter Beginwhile IsLetter orIsDigit beginConcat GetChar end Retract code Reserve if code 0 beginvalue InsertID strToken return ID value endelsereturn code End 0 0 1 2 例 3 3正规表达式与有限自动机 符号 字符串 单词符号 词法分析器 正规式 表达式 语句 程序块 程序 语法分析器 上下文无关文法 语法分析树 语言 集合 字母表 集合 组合 G VT VN S P E i E E E E E 3 3正规表达式与有限自动机 源程序字符流 单词符号 词法规则 非形式化描述 形式化描述 正规式 字母 组合 串 语言 集合 集合 字母表 名字 连接指数 连接UV闭包V 正闭包V 自动化的计算机实现 状态转换图 3 3正规表达式与有限自动机 3 3 1正规式与正规集正规式 对于字母表 按照一组定义规则 由较简单的正规式构成 每个正规式r表示一个语言L r 定义规则说明L r 是怎样以各种方式从r的子正规式所表示的语言组合而成 正规集 正规式表示的简单的字集 叫做正规集 正规式是用于说明词法单元如何到对应到单词符号的规则 3 3正规表达式与有限自动机 正规式正规集备注 a a a U L U U是正规式 U V L U L V U和V是正规式 U V L U L V U和V是正规式 U L U U是正规式由有限次上述步骤而得到的表达式是 上的正规式 这些正规式表达的字符串集合是正规集括号可省 运算符的优先级 连接运算 3 3正规表达式与有限自动机 正规式的例子 a b 3 3正规表达式与有限自动机 正规式的例子 a b 3 3正规表达式与有限自动机 正规式的例子 A B 0 1 正规式等价 若两个正规式U和V表示的正规集相同 则称二者等价 记为U V 例 b ab ba b a b a b 3 3正规表达式与有限自动机 性质 若U V和W都为正规式 则 U V V U 交换率 U V W U V W 结合率 U VW UV W 结合率 U V W UV UW 分配率 V W U VU WU U U U 计算机实现 状态转换图 不确定有限自动机 确定有限自动机 等价 3 3正规表达式与有限自动机 有限自动机 3 3正规表达式与有限自动机3 3 2确定有限自动机DFA 1 确定有限自动机DFA定义 DFA是一个五元组 M S s0 F 如 DFAM S s0 F 0 1 2 3 a b 0 3 0 a 1 0 b 2 1 a 3 1 b 2 2 a 1 2 b 3 3 a 3 3 b 3 3 状态转换矩阵 L aa bb abb baa abba baaa 0 1 2 a b 3 3正规表达式与有限自动机3 3 2确定有限自动机DFA 2 状态转换图 DFAM含有m个状态 n个输入字符 则状态转换图有m个结点 每个结点至多有n条箭弧射出 每条箭弧用 中一个不同的输入字符做标记 4 特点 1 初态唯一 2 输入字符不包括 3 有向边上只有一个字符 4 一个状态对于某个字符 最多只有一条出边 3 3正规表达式与有限自动机3 3 2确定有限自动机DFA 0 1 2 a b a 可被DFA识别的单词符号 对 中任意字 若存在从初态到某一终态的通路 且通路上所有弧标记符连接成的字等于 则称 可为DFA所识别 读出或接受 可识别空串 若M的初态结点同时也是终态结点 则空字 可为M所识别 DFAM所能识别的字的全体记为L M 3 3正规表达式与有限自动机3 3 2确定有限自动机NFA 3 3正规表达式与有限自动机3 3 3不确定有限自动机NFA 1 不确定有限自动机NFA定义NFAM是一个五元组 M S S0 F 1 a 0 a b b 例 识别语言 a b ab的NFA 2 特点 1 初态不唯一 2 输入字符包括 3 有向边上可以为字符串 4 一个状态对于某个字符 可能有多条输出边 即状态的后继不唯一 3 3正规表达式与有限自动机3 3 3不确定有限自动机NFA 可被NFA识别的单词符号 对 中任意字 若存在从初态到某一终态的通路 且通路上所有弧标记符连接成的字等于 则称 可为DFA所识别 读出或接受 可识别空串 若M的初态结点同时也是终态结点 或存在某初态到某终态的 通路 则空字 可为M所识别 NFAM所能识别的字的全体记为L M 3 3正规表达式与有限自动机3 3 3不确定有限自动机NFA 3 3正规表达式与有限自动机3 3 3NFA确定化 NFA DFA 子集法 DFA是NFA的特例对于每个NFAM存在一个DFAM 使得L M L M NFA缺点 其不确定性使得识别单词符号的速度较慢DFA缺点 占用空间太大NFA到DFA的变换子集构造法DFA的一个状态是NFA的一个状态集合 3 3正规表达式与有限自动机3 3 3NFA确定化 NFA DFA 子集法 NFAM S S0 F DFAM S I0 F 1 相关准备 1 对NFAM一个新的初态X和一个新的终态Y 将X指向所有的初态 将所有的终态指向Y 2 对M的状态转换图进一步替换得到M 且L M L M A 将NFA转化为只有一个初态和一个终态度 且每个箭弧上只有一个字符的状态转换图 2 子集法 1 closure q 从状态q出发 只经 转换能到达的所有状态的集合 a q closure q b 从q出发经任意条 弧而能到达的任何状态q closure q 2 closure I q q closure q q I 3 Ia closure J a 其中J为从I中任一状态出发经输入符号a所能到达状态结点的全体 3 3正规表达式与有限自动机3 3 3NFA确定化 NFA DFA 子集法 算法 NFAM S S0 F DFAM S I0 F 取I0 closure S0 将I0加入到S 中 设I0为未标记下图中 I0 closure X X 5 1 若状态集S 中存在有未标记的状态Ii S1 S2 Sj 则标记之 且求It closure Move Ii a 令 Ii a r1 r2 rt It 将It加入S 中 设It为未标记下图中 标记I0 Ia closure Move I0 a closure 5 3 5 3 1 I1Ib closure Move I0 b closure 5 4 5 4 1 I2 算法 NFAM S S0 F DFAM S I0 F 重复 直至S 中没有未标记状态为止 下图确定化 closure Move I1 a closure 5 2 3 5 2 3 1 6 Y I3 closure Move I1 b closure 5 4 5 4 1 I2 closure Move I2 a closure 5 3 5 3 1 I1 closure Move I2 b closure 5 2 4 5 2 4 1 6 Y I4 closure Move I3 a closure 5 2 3 6 5 2 3 1 6 Y I3 closure Move I3 b closure 5 4 6 5 4 6 1 Y I5 closure Move I4 a closure 5 3 6 5 3 1 6 Y I6 closure Move I4 b closure 5 2 4 6 5 2 4 6 1 Y I4 closure Move I5 a 5 3 1 6 Y I6 closure Move I5 b 5 2 4 6 1 Y I4 closure Move I6 a 5 3 1 2 6 Y I3 closure Move I6 b 5 4 6 1 Y I5S I0 I1 I2 I3 I4 I5 I6 初态为I0 终态为含有原终态的状态集 F I S I F I3 I4 I5 I6 I0 I4 a b 确定化后的DFA图 例 将下面NFA确定化 取I0 closure S0 closure 0 0 1 2 4 7 标记I0 closure Move T0 a closure 3 8 1 2 3 4 6 7 8 I1 closure Move T0 b closure 5 1 2 4 5 6 7 I2标记T1 closure Move I1 a 1 2 3 4 6 7 8 I1 closure Move I1 b 1 2 4 5 6 7 9 I3标记T2 closure Move I2 a 1 2 3 4 6 7 8 I1 closure Move I2 b 1 2 4 5 6 7 I2标记T3 closure Move I3 a 1 2 3 4 6 7 8 I1 closure Move I3 b 1 2 4 5 6 7 10 I4标记T4 closure Move I4 a 1 2 3 4 6 7 8 I1 closure Move I4 b 1 2 4 5 6 7 I2 确定化后的DFA图 3 3正规表达式与有限自动机3 3 6确定有限自动机的化简 合并等价的状态 死状态左图无须加死状态 右图加入死状态E 3 3正规表达式与有限自动机3 3 6确定有限自动机的化简 可区别的状态和等价的状态1和2是可区别的状态3和6是等价的状态 3 3正规表达式与有限自动机3 3 6确定有限自动机的化简 最小化的思路 将M的状态集合分成一些不相交的子集 使任何不同的两个子集的状态都是可区别的 而同一子集中的任何两个状态都是等价的 最后 在每个子集选出一个代表 同时消去其他等价状态 3 3正规表达式与有限自动机3 3 6确定有限自动机的化简 1 把DFA状态分割成两个状态S1 终止状态集 和S2 非终止状态集 2 对每个状态集按下述方法进行分割 设第i次分割把集合分割成S S1 i S2 i Sk i 检查状态集Sj i j 1 2 k 设Sj 和Sj Sj i Sj a Sm Sj a Sn若Sm Sn处于同一集合中 则放在同一集 若Sm Sn不处于同一集合中 则放在两个集 3 重复2直至不产生新的分割为止4 合并等价状态 在状态集中选一代表其它删除 如I q1 q2 qk 不可再分 则可选择q1代表这个子集 凡导入到q2 qk的弧都改成导入到q1 若I中含有原来的初态 则q1是新的初态 若I中含有原来的终态 则q1是新的终态 例 书P51图3 8 化简 终态集合S1 3 4 5 6 非终态集合S2 0 1 2 3 4 5 6 a 3 6 S1 3 4 5 6 b 4 5 S1 S1不再分割 0 1 2 a 1 3 S1且 S2 0 a 1 1 a 3 2 a