《编译程序的组织 (10).ppt》由会员分享，可在线阅读，更多相关《编译程序的组织 (10).ppt（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、3.2 正规文法和状态转换图正规文法和状态转换图1.正规文法正规文法(RG)设设A、BVN，aVT 右线性右线性(Right Linear)文法：文法：AaB或或Aa左线性左线性(Left Linear)文法：文法：ABa或或Aa都是都是3型文法型文法(正规文法正规文法 Regular Grammar-RG)L(G)为为3型型/正规集正规集/正则集正则集/正则语言（正则语言（RL）注意：程序设计语言的注意：程序设计语言的多数词法特性多数词法特性 左、右左、右线性文法线性文法不可混用不可混用2.状态转换图状态转换图o有限个结点所组成的有向图o每个结点代表在识别分析过程中扫描器所处的状态，其中 含
2、有一个初始状态和若干个终态。在图中，状态用圆圈表示，终态用双层圆圈表示。o状态之间可用有向边连接，其上标记一字符a，表示从有向边的射出状态出发，识别一字符a后，将进入箭头所指状态（结点）0132abcda,b,c,d d 为字母表为字母表a01a状态转换图所识的语言状态转换图所识的语言初态出发,分别沿一切可能的路径到达终态结点,并将路径中弧线上所标记的字符依次连接起来,得到状态转换图所能识别的全部符号串。0132abcdd这些符号串组成的集合构成了该状态转换图所识别的语言3.根据正规文法，构建状态转换图根据正规文法，构建状态转换图 设设G=(VN,VT,P,S)是一右线性文法是一右线性文法,令
3、令|VN|=K，u则所要构造的状态转换图共有则所要构造的状态转换图共有K+1个状态个状态.uVN中的每个符号分别表示中的每个符号分别表示K个状态个状态G的开始符的开始符S为初态状态为初态状态u终止状态终止状态,用用F(VN)标记标记F是新加是新加(状态状态)节点节点(1)右线性文法右线性文法状态转换图状态转换图aA-aBABA-aAFaA-AFA若若A为为起始符起始符(GA)A 转换规则转换规则baabVSUa例如：文法例如：文法GS SaU|bV UbV|a VaU|bbF 对符号串对符号串对符号串对符号串W=aW=a1a a2a a3aan，a ai V VT T 识别过程：识别过程：识别
4、过程：识别过程：l l从从从从初态初态初态初态S S出发，出发，出发，出发，自左至右自左至右自左至右自左至右逐个扫描逐个扫描逐个扫描逐个扫描WW中的字符，中的字符，中的字符，中的字符，在在在在S S状态下扫视的符号为状态下扫视的符号为状态下扫视的符号为状态下扫视的符号为a a1；l l在节点在节点在节点在节点S S所射出弧中所射出弧中所射出弧中所射出弧中寻找标记为寻找标记为寻找标记为寻找标记为a a1的矢线的矢线的矢线的矢线(若若若若不存在，则说明不存在，则说明不存在，则说明不存在，则说明WW有错有错有错有错)；l l读入读入读入读入a a1，沿弧的方向到下一状态沿弧的方向到下一状态沿弧的方向
5、到下一状态沿弧的方向到下一状态，在此状态，在此状态，在此状态，在此状态时扫描时扫描时扫描时扫描a a2，l l直至直至直至直至WW中全部字符读完且进入中全部字符读完且进入中全部字符读完且进入中全部字符读完且进入终态终态终态终态F F，则则则则WW已已已已被接受。被接受。被接受。被接受。状态转换图对符号串的识别状态转换图对符号串的识别状态转换图对符号串的识别状态转换图对符号串的识别baabVSUabF识别串识别串baa的过程：的过程：SbVbaU baaSbVaUaF利用状态图识别串的过程，利用状态图识别串的过程，即是为串建立一个推导的过程。即是为串建立一个推导的过程。即是为串建立一个推导的过程
6、。即是为串建立一个推导的过程。自顶向下分析过程自顶向下分析过程规范句型规范句型(2)左线性文法左线性文法状态转换图状态转换图例：例：SUa|Vb UVb|a VUa|bbaabVSaQUbFS识别串：识别串：aab SVbUab aab 从初态到终态路径的标记连成的串为文法所定义串的从初态到终态路径的标记连成的串为文法所定义串的左序左序。解决这一矛盾把每条边改方向且把初态改终态，所有终态解决这一矛盾把每条边改方向且把初态改终态，所有终态合成一个初态即可。合成一个初态即可。一个问题：一个问题：u设设G=(VN,VT,P,S)是一左线性文法是一左线性文法,令令|VN|=K，则所要构造的状态转换图共
7、有则所要构造的状态转换图共有K+1个状态个状态.uVN中的每个符号分别表示中的每个符号分别表示K个状态个状态G的开始符的开始符S为终止状态为终止状态u起始状态起始状态,用用R(VN)标记标记R是新加是新加(状态状态)节点节点 左线性文法左线性文法状态转换图状态转换图 转换规则转换规则aA-BaBA若若A为起始符为起始符(GA)AA-aRAa对于符号串对于符号串W=a1a2a3an，aiVT 可对可对W识别。识别。l 从从初态初态R出发，自左至右逐个扫视出发，自左至右逐个扫视W中的各个中的各个字符，在字符，在R下扫视的符号为下扫视的符号为a1；l 在节点在节点R所射出的弧中所射出的弧中寻找标记为
8、寻找标记为a1的弧的弧（若（若不存在，则说明不存在，则说明W有错）；有错）；l 读入读入a1沿矢线所指方向到下一状态，在从此状沿矢线所指方向到下一状态，在从此状态扫描态扫描a2，l 直到直到W中全部字符读完且中全部字符读完且进入终态进入终态S，则则W已已被接受。被接受。符号串的识别符号串的识别识别串识别串aab的过程：的过程：baabVaUbRS利用状态图识别串的过程，利用状态图识别串的过程，即是为串建立一个即是为串建立一个规约规约的过程。的过程。RaUaVbSaabUabVb S自自底底向上分析过程向上分析过程句柄句柄4.状态转换图的一种实现状态转换图的一种实现状态矩阵状态矩阵o状态矩阵状态
9、矩阵 以图中各个状态以图中各个状态S1,S2,Sn为行为行,以以各个输入符号各个输入符号a1,a2,am为列为列,组成一个组成一个n m矩阵矩阵Bo元素元素Bij=BSi,aj指明下一状态指明下一状态Sk和扫描器此和扫描器此时应完成的语义动作时应完成的语义动作.其含义是其含义是,在在Si状态下状态下,扫扫描到描到aj符时符时,按序偶按序偶(Si,aj)查矩阵查矩阵B,扫描器根据扫描器根据Bij的指示的指示,先执行相应的语义动作先执行相应的语义动作,再转换到再转换到下个状态下个状态Sk.o若若Bij为为“出错出错”,则说明输入符号串有误则说明输入符号串有误,拒拒绝接受绝接受.扫描器将调用出错处理程序进行处理扫描器将调用出错处理程序进行处理.baabVSUabF a1 a2 am 5.小结正规文法右线性文法左线性文法规则规则状态转换图识别单词一种实现状态矩阵