编译原理第3章-词法分析-2讲义.ppt

3.1.2 单词符号及输出单词的形式 3.1.2 单词符号及输出单词的形式 3.1.2 单词符号及输出单词的形式 3.1.2 单词符号及输出单词的形式 3.1.2 单词符号及输出单词的形式 3.1.2 单词符号及输出单词的形式 3.1.2 单词符号及输出单词的形式 3.1.2 单词符号及输出单词的形式 3.1.2 单词符号及输出单词的形式 3.1.2 单词符号及输出单词的形式 3.1.3 把词法分析设计成一个独立程序 （1）组织成一遍扫描； （2）作为语法分析和语义分析的子程序 原因：-简化设计 -改进编译效率 -增加编译系统的可移植性 3.3 单词符号的两种定义方式 3.2.1 正规式和正规集 3.2.1 正规式和正规集 3.2.1 正规式和正规集 3.2.1 正规式和正规集 3.2.1 正规式和正规集 3.2.1 正规式和正规集 3.2.1 正规式和正规集 3.2.2 正规文法与正规式 例 有正规文法G[s]:S?aA|a A?aA?a?dA?d 试给出该文法生成语言的正规式。 A?(a?d)A?(a?d) A?(a?d)?(a?d) S=a(a?d)?(a?d)?a =a((a?d)?(a?d)??) =a((a?d)+??) R=a(a?d)? 3.2.2 正规文法与正规式 3.2.2 正规文法与正规式 3.2.2 正规文法与正规式 3.2.2 正规文法与正规式 3.2.2 正规文法与正规式 3.2.2 正规文法与正规式 3.3 正规式与有穷自动机 3.3.1 确定有穷自动机 3.3.1 确定有穷自动机 3.3.1 确定有穷自动机 3.3.1 确定有穷自动机 例：证明t=baab被下图的DFA所接受。 f（S，baab）=f（f（S，b），aab） = f（V，aab）= f（f（V，a），ab） =f（U，ab）=f（f（U，a），b） =f（Q，b）=Q Q属于终态。 得证。 DFA的行为很容易用程序来模拟. DFA M=（Q，Σ，f，S，Z）的行为的模拟程序 Q:=S； c:=getchar; while ceof do {Q:=f(Q,c); c:=getchar; }; if K is in Z then return (‘yes’) else return (‘no’) DFA的确定性表现在 1）转换函数f:Q×Σ→Q是一个单值函数，也就是说，对任何状态qk∈Q，和输入符号a∈Σ，f(qk,a)唯一地确定了下一个状态。从状态转换图来看，若字母表Σ含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。 2）初始状态是唯一的 3.3.2 非确定有穷自动机 3.3.2 非确定有穷自动机 3.3.2 非确定有穷自动机 3.3.3 NFA确定化为DFA的方法 2. 状态集合I的a弧转换，表示为move(I,a)定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体 3.3.3 NFA确定化为DFA的方法 例2 将下面的NFA N确定化。 3.3.4 DFA的化简 3.3.4 DFA的化简 3.4.1 由正规式R构造NFA 3.4.1 由正规式R构造NFA 3.4.1 由正规式R构造NFA 3.4.1 由正规式R构造NFA 3.4.1 由正规式R构造NFA 3.4.2 有穷自动机到正规式的转换 3.5 正规文法与有穷自动机 前面提到程序设计语言的单词符号可用乔母斯基3型文法——正规文法来描述 对于正规文法所描述的语言可用一种有穷自动机来识别 下面分别就左线性正规文法/右线性正规文法给出构造相应有穷自动机的方法 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.6 词法分析程序的编写方法 本章小结 本章小结 本章小结 本章小结 本章小结 对于 代换为 A B r1r2 A C B r1 r2 对于 A B r1| r2 代换为 代换为 A B r1r2*r3 A B r1 r2 对于 A C B r1 r3 r2 例1. 设有穷自动机的状态图如图所示。