《编译原理与技术》期末复习.PDF

《编译原理与技术》 期末复习 计算机科学与技术学院 郑启龙 李 诚 25/12/2018 说明 考试时间1月15日下午（具体时间待定） 地点西区3教（具体时间待定） 闭卷考试 2019/1/1 李诚 @ 编译原理与技术 Fall 2018 2/89 重要知识点复习 第2章词法分析 理解并会使用正规式（即正则表达式） 掌握NFA和DFA，以及之间的转换 学会为正规式写NFA和DFA DFA的化简 2019/1/1 李诚 @ 编译原理与技术 Fall 2018 3/89 例题1 针对正规集L={含奇数个1的0、1串} 给出描述正规集L的正规式(即正则表达式)R 2019/1/1 李诚 @ 编译原理与技术 Fall 2018 4/89 例题1 针对正规集L={含奇数个1的0、1串} 给出描述正规集L的正规式(即正则表达式)R 解答过程： 可以先写出几个合法的串 1, 111,11111,可以在相邻的两个1之间或第一个1 之前或最后一个1之后插入任意多的0 排除0 以外，合法的1 串都可以看做两部分“1+偶 数个1的串” 0*1(10*1|0)* 2019/1/1 李诚 @ 编译原理与技术 Fall 2018 5/89 例题2 * 构造识别正规式 10 |(0 | 11)0 1的极小化 DFA M。 这里一定要注意优先级，不少同学把|的优 先级弄错了。 2019/1/1 李诚 @ 编译原理与技术 Fall 2018 6/89 例题2 * 构造识别正规式 10 |(0 | 11)0 1的极小化 DFA M。 解答过程 如果不熟练，可以先画出NFA 然后通过子集构造法将NFA转成DFA 最后通过化简得到极小化的DFA 2019/1/1 李诚 @ 编译原理与技术 Fall 2018 7/89 例题2 * 构造识别正规式 10 |(0 | 11)0 1的极小化 DFA M。 解答过程 如果不熟练，可以先画出NFA 0   4 5  0 1  6 10 11 12 2 3 1 1   7 8 9  