Greibach范式.ppt

Company Name LOGO LOGO Greibach范式 西安电子科技大学计算机学院 姓名：张 鹏 学号：1021121276 提 纲 为什么提出Greibach范式 1 西安电子科技大学 什么是Greibach范式 2 介绍两个引理 3 CFG→GNF转换方法 4 西安电子科技大学 为什么提出Greibach范式 自上而下的语法分析中---回溯问题 回溯问题导致语法分析的效率降低 产生回溯的原因： 存在 A→Ab. 左递归的非终结符 同一非终结符的候选产生式有公共的左因子 如何避免回溯的产生？ 消除左递归 西安电子科技大学 什么是Greibach范式 如果 CFG G=(V, T, P, S)中的所有产生式具有 A?a?，其中，A?V, a?T, ??V* --则称 G为格雷巴赫范式文法(GNF)； --简称为格雷巴赫文法或格雷巴赫范式 -- ?只能是非终结符组成的串，其中不能含终 结符  西安电子科技大学 什么是Greibach范式 根据定义，GNF有如下两种形式的产生式 A?a A?aA1A2…Am (m?1) 例如： S?bA | aB A?bAA | aS | a B?aBB | bS | b  西安电子科技大学 引理1: 对A→α的A生成式可进行变换 设 G = (N,T,P,S) A→αBβ是P中的生成式 B∈N，α、β∈(N∪T)* B→r1| r2|…| rk是P中的B生成式 可生成G1 = (N1,T, P1,S)P1中的生成式是将P中的A→αBβ用A→αr1β|…|αrkβ取代 例如有文法G：S → a B S |b B → a S S | b? 则替换后可以得到等价的文法： G1：S → aaSSS|abS | b 介绍两个引理 提出该引理的目的是： 为了支持消除间接左递归 西安电子科技大学 引理2: 消除直接左递归 设G = (N, T, P, S), P中有A生成式： A→Aα1 | Aα2 | … | Aαm |β1 |β2 | … |βn 其中βi的第一个字符不是非终结符A (可以是其它非终结符)，可构成G1= (N∪{A’}, T, P1, S), A’为新引入的非终结符 G1中的P1为：将P中的A生成式用以下生成式取代 A→β1|β2|…|βn| β1A’|β2A’|…|βnA’ A’→α1|α2|…|αm| α1A’|α2A’|…|αmA’ 介绍两个引理 应用引理二：根据：A→Aα | β 构造：A→β|βA’ A’→α|αA’ 西安电子科技大学 CFG→GNF转换方法 将文法G变换为CNF 变换为A→a、A→BC形式 将非终结符排序，再进行代换 对形如Ai→Ajβ（ji）的生成式进行代换，直至使Ai→Akβ（ki） 消左递归 对最高的An→Anγ进行变换，使An生成式变为终结符开头 回代 将An生成式回代入An－1，使其右部首符为终结符，将An－1生成式回代入An－2生成式，使其右部首符为终结符，依次类推 最后将消除直接左递归时引入的A1’、 A2’、…An’生成式右部进行代换，使其首符变为终结符 西安电子科技大学 设CNF文法： A→BC ① B→CA∣b ② C→AB∣a ③ 将其变换为GNF 变换步骤如下： ⑴ 按其非终结符排列为A、B、C，A是低位，C是高位 ⑵ ①、②中，右部首符序号高于左部的非终结符，无需变换 ③则需要做如下变换： 将①代入③得 C→BCB∣a ④ 将②代入④得 C→CACB∣bCB∣a ⑤  CFG→GNF转换方法 西安电子科技大学 ⑶ 消除直接左递归