编译第4章概要.ppt

复习 DFA最小化的方法 删除多余状态，合并等价状态。 NFA?r的方法 r?NFA的方法 作业： 习题8 * + 确定化：初态，终态 4.5 正规文法和有穷自动机的等价性 设G=(VN,VT,P,S)是正规文法(右线性文法和左线性文法)，则存在一个有限自动机 M=(Q,?,f,q0,Z)，使得L(G)=L(M)。 对每个有限自动机M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)=L(GR)=L(GL)。 一、等价性 1. 右线性正规文法?NFA p65 例4.12求与文法G[S]等价的NFA G[S]: S→aA|bB|ε A→aB|bA B→aS|bA|ε S Z A B a a a b b b ε ε 求得： 习题7 2. NFA?右线性正规文法p65 例4.13.给出如图NFA等价的正规文法G A B C D a a a b b b b G=({ A,B,C,D},{a,b},P,A) 其中P为： A→aB A→bD B→bC C→aA C→bD C→? D→aB D→bD D→? 3.左线性正规文法?NFA P73 10 词法分析程序的构造方法 按照词法规则构造正规式（正规文法）； 正规式?NFA（正规文法?NFA）； NFA?DFA； DFA最小化； 根据DFA构造词法分析程序。 词法分析程序的自动构造工具LEX 功能： 依据语言的正规式，自动生成该语言的词法分析程序。 执行过程： lex源程序由三部分组成 说明部分 %% 转换规则 %% 辅助过程 P71 3 P67 复习 DFA和NFA的区别。 如何证明符号串t被DFA接受？不被接受？ 如何画DFA的状态转换图和状态转换矩阵 a b 0 {0,3} {0,1} 1 {2} 2 {2} {2} 3 {4} 4 {4} {4} 该非确定自动机对应的状态转换图和状态转换矩阵(?) 0 0 1 0 1 对不包含回路的结点 i 字母 数字 / j k l 状态i对应的代码： i(){ ch=Getchar(); if(isletter(ch)){j} else if(isdigit(ch)){k} else if (ch=“/”){l} } 对包含回路的结点 状态P对应的代码： P(){ ch=Getchar(); while(isletter(ch) or isdigit(ch) ) getchar(); 状态Q对应的程序段 } P 字母|数字 Q 其他 作业 词法分析程序 待分析的简单语言的语法： 关键字：begin if then end (小写) 运算符：:= + - * / 界符：; # 标识符：ID=letter (letter|digit)* 常数：NUM=digit digit* 要求编写词法分析程序， 键盘输入源程序，输出单词符号的二元式。 输入： begin x:=9;if x0 then x:=2*x+1/3;end# 输出： 3 begin 1 x 4 := 2 9 5 ; 提示1 char expression[512], *pExpression; gets(expression); pExpression=expression; void GetChar() { ch=*(pExpression++); } 提示2 #include ctype.h if (isalpha(ch)) {//是字母，则进入状态1； while (isalpha(ch)||isdigit(ch)) { Concat(); GetChar(); } Retract(); code=Reserve(); } S 字母 P 字母|数字 Q 其他 * ()界符， =,