单元辅导（二） 词法分析与有穷自动机
1、词法分析的任务是对字符串表示的源程序从左到右地进行扫描和分解， 根据语言的词法规则识别出一个一个具有独立意义的单词符号。执行词分 析的程序称为词法分析程序，或称词法分析器或扫描器。 （1）单词符号及输出单词的形式： 词法分析程序是以字符串形式的源程序作为输入，以单词符号或单词 符号表示的源程序作为输出。 语言的单词符号是指语言中具有独立意义的最小语法单位。即单词符号是程序 语言的基本语法单位。分五种：关键字，标识符，常数，运算符，界符。表示为成 二元式： （单词种别，单词自身的值）
2、正规文法到正规式的转换： （1）将正规文法中的每个非终结符表示成关于它的一个正规式方程，获得 一个联立方程组。 （2）依照求解规则： 若x＝αx|β（或x＝αx＋β），则解为x＝α*β。 若x＝xα｜β（或x＝xα＋β），则解为x＝βα*。 以及正规式的分配律、交换律和结合律求关于文法开始符号的正规式方程组的解。 这个解是关于该文法开始符号S的一个正规式，显然它表示了由该正规文法所描述的语言。 举例说明见书P31 ：[例3.4]、[例3.5]、[例3.6]、 [例3.7] 3、正规式到正规文法的转换： 字母表∑上的正规式到正规文法G＝（VN，VT，P，S）的转换文法如下： （1）令VT＝ ∑； （2）对任意正规式R选择一个非终结符Z生成规则Z R，并令S＝Z； （3）若a和b都是正规式，对形如A ab的规则转换成A aB和B b两规则， 其中B是新增的非终结符； （4）在已转换的文法中，将形如A a*b的规则进一步转换成A aA｜b； （5）不断利用规则（3）和（4）进行变换，直到每条规则最多含有一个终结符为止。 举例说明见书P33 ：[例3.8]、[例3.9] ★正规式与有穷自动机 1、确定有穷自动机（DFA）：f是单值映射，S是惟一的一个初态。 2、非确定有穷自动机（NFA）：f是多值函数，S是非空初态集。 3、DFA与NFA均可由状态转换矩阵（状态表）和状态转换图。 举例说明见书P34 ：[例3.10]、[例3.11]
4、由正规表达式R构造NFA：举例说明见书P37 ：[例3.12]、[例3.13] 5、NFA确定化为DFA的方法：首先将从状态S出发经过任意条ε弧所能到达的 状态所组成的集合作为M的初态S ‘，然后从S ’出发，经过对输入符号a ∈∑的 状态转移所能到达的状态（包括读输入符号a之前或之后所有可能的ε转移所能 到达的状态）所组成的集合作为M的新状态，如此重复，直到不再有新的状态 出现为止。 举例说明见书P38 ：[例3.14]、[例3.15] 6、DFA的化简：寻找一个状态数比M少的DFA M‘，使得L（M）＝L（M’）。 满足（1）没有多余状态。 （2）它的状态集中，没有两个状态是互相等价的。 方法 把 M的状态集Q分划成一些不相交的子集，使得每个子集中任何两个状态是 等价的，而任何两个属于不同子集的状态都是可区别的；然后在每个子集中 任取一个状态作”代表” ，而删去子集中其余状态，并把射向其余状态的箭弧 都改为射向作为”代表“的状态中。 举例说明见书P41 ：[例3.16]、[例3.17] 7、有穷自动机到正规式的转换：举例说明见书P42 ：[例3.18] ★正规文法与有穷自动机 1、右线性正规文法到有穷自动机的转换方法 举例说明见书P43 ：[例3.19] 2、左线性正规文法到有穷自动机的转换方法 举例说明见书P44 ：[例3.20] 3、有穷自动机到正规文法的转换方法 举例说明见书P45 ：[例3.21]、[例3.22] ★构造词法分析程序方法：手工方式和利用词法分析程序的自动生成工具LEX。
小 结 （二） 本部分重点介绍了词法分析程序的设计思想和构造方法。主要内容有： 小 结 （二） 本部分重点介绍了词法分析程序的设计思想和构造方法。主要内容有： （1）词法分析程序的功能是从左到右扫描源程序字符串，根据语言的词法规 则识别出各类单词符号，并以二元组（单词种别，单词自身值）的形式输出。 （2）对程序语言单词符号有两种定义方式 正规式 正规文法 例如，定义”标识符“单词的正规式是l(l|d)*，正规文法是＜标识符＞ l｜＜标识符＞l| <标识符＞d。其中l代表任一字母，d代表任一数字。 从这两种描述中构造识别语言单词符号的词法分析程序是用有穷自动机来实现的。 （3）有穷自动机有确定的和非确定两大类： DFA N＝（Q，∑，f，S，Z），其中f是单值映射函数，S是惟一初态。 NFA N＝（Q，∑，f，S，Z），其中f是多值映射函数，S为非空初态集。 有穷自动机有通常表示为状态转换图，它是有穷自动机的非形式化描述。 由单词的两种定义方式来构造词法分析程序的过程是： （4）正规式、正规文法和有穷自动机三者都是描述正规集的工具，它们的描述能力是等 价的，它们之间可相互转换。 （5）证明两正规式是等价的。如果它们的最小状态DFA相同，或利用正规式的基本等价 关系将一个正规式化简都可证明两正规式之间的等价性。