编译原理-第03章.pptVIP

3.4.5 DFA的化简 3.4.5 DFA的化简 3.4.5 DFA的化简 3.4.5 DFA的化简 3.4.5 DFA的化简 3.4.5 DFA的化简 3.4.5 DFA的化简 3.4.5 DFA的化简 3.4.6 有穷自动机到正规式的转换 3.4.6 有穷自动机到正规式的转换 3.4.6 有穷自动机到正规式的转换 3.4.6 有穷自动机到正规式的转换 3.5 正规文法与有穷自动机 前面提到程序设计语言的单词符号可用乔母斯基3型文法——正规文法来描述 对于正规文法所描述的语言可用一种有穷自动机来识别 下面分别就左线性正规文法/右线性正规文法给出构造相应有穷自动机的方法 3.5 正规文法与有穷自动机 3.5.1 右线性正规文法到有穷自动 机的转换方法 f(Z,0)=A f(Z,1)= Φ f(z, ε)= Φ f(A,0)=A,B f(A,1)= Φ f(A, ε)=Φ f(B,0)= Φ f(B,1)=A f(B, ε)=D 3.5.2 左线性正规文法到有穷自动 机的转换方法 3.5.2 左线性正规文法到有穷自动 机的转换方法 3.5.3 有穷自动机到正规文法的转换 3.5.3 有穷自动机到正规文法的转换 3.5.3 有穷自动机到正规文法的转换 3.5.3 有穷自动机到正规文法的转换 3.6 词法分析程序的编写方法 3.6 词法分析程序的编写方法 本章小结 本章小结 本章小结 本章小结 本章小结 本章小结 本章小结 本章小结 本章小结 G=({A,B,C},{0,1}, P, A)其中P为 或 A→0B | 0 B→1C C→0B | 0 A→0B B→1C | ε C→0B 例2 设DFA M=({A,B,C,D},{0,1}, δ, A,{B}) δ (A,0)=B δ (A,1)=D δ (B,0)=D δ (B,1)=C δ (C,0)=B δ (C,1)=D δ (D,0)=D δ (D,1)=D 其中： G=({A,B,C},{0,1}, P, A)其中P为 或 该自动机所识别的语言为 0(10)*。 A→0B | 0 B→1C C→0B | 0 根据转换规则所求右线性文法为 A→0B B→1C | ε C→0B B C A 0 0 1 构造词法分析程序的方法: 第二种方法是利用词法分析程序的自动生成工具LEX自动生成词法分析程序，本书附录对LEX作了简单介绍。 第一种方法是用手工方式，即根据识别语言单词的状态转换图，使用某种高级语言，例如C语言直接编写词法分析程序。 下面以某种简单语言为例，对第一种方法作简要的介绍。 例如，下表列出了某个简单语言的所有单词符号，以及它们的种别编码和单词值。 单词符号 种别编码 单词值 1 2 3 4 5 6 7 10 11 13 14 15 16 17 18 19 21 22 23 内部字符串 二进制数值表示 begin end if then else while do 标识符 整常数 + - * / = : := ; 右图是一张识别前表的单词符号的状态转换图。 图中, 状态0为初态, 凡带双圈者均为终态; 状态17是识别不出单词符号的出错情况。 l 代表任一字母，d 代表任一数字。 根据这张转换图，我们用C语言直接编写出识别该语言所有单词的词法分析程序。 在例中，我们规定所有关键字, 用户不得使用它们作为自己定义的标识符，这样我们可以把关键字作为一类特殊的标识符来处理，不再专设对应的转换图。但需把它们预先安排在一个表格中，此表叫关键字表。当利用状态转换图识别出一个标识符时，就去查关键字表，以确定它是否是一个关键字。 其次规定，若关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔，即此时的空白符是有意义的。 根据状态转换图构造出词法分析程序最简单的办法是让每个状态对应一小段程序。 1. ch 字符变量，存放当前读进的源程序字符。 2. token 字符数组, 存放构成单词符号的字符串。 3. getch( )读字符函数，每调用一次从输入缓冲区中读进源程序的下一个字符放在ch中，并把读字符指针指向下一个字符。 4. getbc( )函数，每次调用时，检查ch中的字符是否为空白字符，若是空白字符，则反复调用getbc( )，直至ch中进入一个非空白字符为止。 首先，我们引进词法分析程序