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