程序设计语言——编译原理 第三章总结

• 知识点

1.

CHP3.1词法分析器，单词符号，单词种别

CHP3.2超前搜索，状态转换图（初态，终态）

CHP3.3正规式（正规式的等价，性质），正规集，确定有限自动机（功能，等价），非确定有限自动机，正规文法与有限自动机的等价性，正规式与有限自动机的等价性（空字闭包，子集法），确定有限自动机的简化（状态等价，状态可区别，）

确定有限自动机，非确定有限自动机的区别

      函数值的对应（DFA中的映射是单值映射，NFA不是），初态的个数；

2.自己觉得重要的

2.1有限自动机的表示

     状态转换矩阵；状态转换图

2.2产生式与正规式

     产生式与正规式可以互求

2.3正规文法与有限自动机等价性

2.4正规式与有限自动机等价性

   正规式<——>FA

  正规式——>NFA; 正规式——>DFA;而NFA——>DFA，无论正规式如何转化，都要先产生NFA；若要从正规式产生DFA，要NFA——>DFA

       正规式——>NFA

       有正规式画出状态转换图（根据替换规则，得到的是带空字的状态转换图，即NFA的状态转换图），由正规式得到正规式的状态转换矩阵（第一列第一个是初态的空字闭包，第一列向左是根据空字闭包与字母表得到的新空字闭包，第一列是产生的新空字闭包的组合），重新命名得到新状态转换矩阵，由矩阵再画出新的状态转换矩阵（得到的是不带空字的状态转换图，即DFA的状态转换图）

2.5DFA的简化

例子

• 作业

课后题7，8，9，10，12，14

• 体会

         经过练习对正规式与FA的转换有了一定的基础，由FA得到正规式比较好求。但在由正规式得到FA时，求状态转换矩阵，一不小心就会犯错；尤其是J这个集合，再由J得J的空字闭包，状态转换矩阵写对了，后面就容易。在对DFA的简化中，刚开始还不太熟练，在对集合的分解中，老是漏掉元素，认真看做的多了，也就熟练了。还有对词法分析器的代码实现，感觉自己以前学的数据结构有关知识都忘得差不多了，要重新再来，希望能完成。