西北工业大学编译原理课件第三章 词法分析及词法分析程序2.pptVIP

3.2 正规文法和状态转换图 正规文法定义了3型语言，常见的单词可由正规文法定义。 状态转换图可用于识别3型语言；它是设计和实现扫描器的一种有效工具，是有限自动机的直观图示 3.2.1 由正规文法构造状态转换图 程序设计语言的单词都能用正规文法描述； 例如，标识符可定义为 标识符?标识符字母 标识符?标识符数字 标识符 ?字母 若把字母、数字视为终结符，则上述产生式为（左线性）正规文法 若我们用d表示0-9间的数字，则C语言的无符号数的文法也是（右线性）正规文法（见P48） 一般说来，凡能用正规文法描述的语言，均可由某种有限状态算法——状态转换图进行分析。 状态转换图 由有限个结点所组成的有向图。 每个结点代表在识别分析过程中扫描器所处的状态，其中 含有一个初始状态和若干个终态。在图中，状态用圆圈表示，终态用双层圆圈表示。 状态之间可用有向边连接，其上标记一字符a??，表示从有向边的射出状态出发，识别一字符a后，将进入箭头所指状态（结点） 由右线性文法构造状态转换图 设G=(VN,VT,P,S)是一右线性文法,并设|VN|=K,则所要构造的状态转换图共有K+1个状态(结点).用VN中的每个符号分别标记其中的K个结点,且令G的开始符S为初态结点;余下的一个结点作为终态结点,用F(?VN)标记.我们用如下规则来连接这K+1个结点: (1)对于G中产生式A?aB,从结点A引一有向边到结点B,并用a标记这一有向边; (2)对于G中产生式A?a,从结点A引一有向边到终态结点F,并用a标记这一有向边; (3)对于G中产生式A??(若有的话),则将结点A设为终态. 例如,P48中定义的无符号数的文法对应的~为(化简后): 利用状态转换图识别符号串的方法 对于已给的字符串w=a1a2…an,ai?VT,利用~对w 识别的步骤如下: (1)从初始状态S出发,自左至右逐个扫描w的各个字符(当前为a1),此时在结点S所射出的诸矢线中,寻找标记为a1的矢线(若不存在,则表明w有语法错误),读入a1并沿矢线所指方向前进,过渡到下一状态(设为A1). (2)设当前处在Ai状态,所扫描的字符为ai+1,在结点Ai所射出的诸矢线中,寻找标记为ai+1的矢线(若不存在,则表明w有语法错误),读入ai+1,并进入状态Ai+1; (3)重复(2),直到w中所有字符被读完且恰好进入终态F时,宣告整个识别结束,w可被接受. 显然,若我们从初态出发,分别沿一切可能的路径到达终态结点,并将中径中矢线上所标记的字符依次连接起来,便得到状态转换图所能识别的全部符号串,这些符号串组成的集合构成了该~识别的语言 状态转换图与文法推导 用状态转换图识别符号串w的过程，就是为w建立一个推导S?* w的过程。 在第一步（在初始状态S下，扫描到a1而过渡到下一状态A1），由状态转换图的构造规则可知，G中必有产生式S?a1A1;对于识别过程的后续步骤，由状态Ai识别ai+1后过渡到Ai+1恰好对应了使用产生式Ai ?ai+1Ai+1,…,最后在状态An-1识别an后到达终态F，对应了使用产生式 A ?an 进行推导： S ?a1A1 ?a1a2A2 ?…… ?a1a2…an-1An-1 ?a1a2…an 右线性文法与状态转换图 设G是一右线性文法,M是相应的状态转换图,则从前面的讨论可以看出如下事实： (1)在利用M对符号串w进行识别时,M中每次状态的转换都模拟了一步直接推导,即识别方法(或称分析方法) 是“?”的; (2)因右线性文法只有形如A?aB、A ?a的产生式，所以推导的每一步所得句型只含一个非终结符，所以推导的规范的，每步所得的句型也必为规范句型； (3)对于M所识别的任一符号串x,必存在G中的一个推导S ?* x (即有x?L(G);反之,对于L(G)中任一句子y,必存在一条从初态S到终态F的路径,此路径上各矢线的标记依次拼接起来所组成的符号串恰为y 由左线性文法构造状态转换图 设G=(VN,VT,P,S)是一左线性文法,构造相应的状态转换图的方法是: 首先用G的VN符标记M的结点,其中,开始符S对应的结点为终态结点.另外,再引入一个新结点R(?VN)作为初态.矢线的连接规则为: (1)对于G中形如A?a 的产生式,引矢线:R?A,且标记为a; (2)对于G中形如A?Ba 的产生式,引矢线 B?A,且标记为a. 识别符号串与归约 由构造状态转换图的方法可知,从初态R到下一状态A的转换,对应了形如B?a 的产生式,即将终结符a归约成非终结符B; 类似地,从状态B转换到状态A,对应了形如A?Ba的产生式,即将Ba归约为A; 如此下去,直到从某状态A转换到状态S(终态),对应了形如S ?Aa的产生式,即将Aa归约为开始符S.此时归约成功,也恰好进入了终