24文法的化筒与改滋 S4PMOAWMAMHZIAWIESMPMOHAWHMAMHZIAV 对文法进行化简和改造 希望定义语言的文法尽可能简单 某些语法分析技术对文法有要求和限制:LL分析 要求文法无左递归;算符优先分析要求文法不含 有8产生式;LR分析要求文法无二义性 本节主要内容 无用符号和无用产生式的删除 8-产生式的消除 单产生式的消除
1 2.4 文法的化简与改造 • 对文法进行化简和改造 – 希望定义语言的文法尽可能简单 – 某些语法分析技术对文法有要求和限制：LL分析 要求文法无左递归；算符优先分析要求文法不含 有-产生式；LR分析要求文法无二义性 • 本节主要内容 – 无用符号和无用产生式的删除 – -产生式的消除 – 单产生式的消除
无用符号和无用产生式的除 无用符号和无用产生式 设G=(V,Vr,P,S)是一文法,X∈V,X称为是有用的,若X至 少出现在一个句子的推导过程中,即X满足: (1)存在aB∈V*,有S→*axB (212) (2)存在w∈Vr,使αXβ→*w 213) 否则,称X是无用的。 若一产生式含有无用符号,则此产生式称为无用产生式。 无用产生式给语法分析带来了许多麻烦,应予以 删除
2 无用符号和无用产生式的删除 • 无用符号和无用产生式 设G=(VN,VT,P,S)是一文法, XV, X称为是有用的, 若X至 少出现在一个句子的推导过程中, 即X满足: (1) 存在, V* ,有 S* X (2.12) (2) 存在w VT*,使 X * w (2.13) 否则，称X是无用的。 若一产生式含有无用符号，则此产生式称为无用产生式。 • 无用产生式给语法分析带来了许多麻烦，应予以 删除
无用符号和无用产生式的识别 找出文法G中的全部无用符号,删除这些无用 符号以及包含它们的所有产生式。 识别文法G中的无用符号:对于任一符号Ⅹ, 如果X是有用的,则 Ⅹ至少出现在一个句型中(条件2.12),否则,用 算法22进行改造 符号X能推导出终结符号串(条件2.13),否则, 用算法2.进行改造
3 无用符号和无用产生式的识别 • 找出文法G中的全部无用符号，删除这些无用 符号以及包含它们的所有产生式。 • 识别文法G中的无用符号：对于任一符号X， 如果X是有用的，则 – X至少出现在一个句型中（条件2.12），否则，用 算法2.2进行改造 – 符号X能推导出终结符号串（条件2.13），否则， 用算法2.1进行改造
改造算法 算法21将文法G=(Vr,PS)改造为 G=(Vvr,P1S),使得对于每个X∈V”,存在w ∈V,满足X→*w 算法22任给文法G=(VVr,PS),构造 G=Vwvn,P’,S),使x∈(VwV,孔aB∈ ∪V")*,有S→*axB
4 改造算法 算法2.1 将文法G = (VN,VT,P,S),改造为 G1=(V’N,VT,P1 ,S),使得对于每个X V’N,存在w VT*,满足 X* w. 算法2.2 任给文法G= (VN,VT,P,S),构造 G’=(V’N,V’T,P’,S), 使x (V’NV’T), , (V’N V’T)*, 有 S * x
算法2的形式化描述 算法21将文法G=(,vr,PS),改造为G=(v,v,P1,S),使 得对于每个X∈V,存在w∈Ⅵ,满足X→*w. 1)置vP1为空; (2)对于P中每个产生式A→>8若8∈(VV),则将A加入 v中 (3)重复(2),直到v不再增大; (4)对于每个A→>6∈P,若δ∈(Vw),则置A→>8于P中
5 算法2.1的形式化描述 算法2.1 将文法G = (VN,VT,P,S),改造为G1=(V’N,VT,P1 ,S),使 得对于每个X V’N,存在w VT*,满足 X* w. (1)置V’N,P1为空; (2)对于P中每个产生式A→,若 (V’NVT)*,则将A加入 V’N中; (3)重复(2),直到V’N不再增大; (4)对于每个A→ P,若 (V’NVT)*,则置A→ 于P1中