[工学]02 文法.ppt

* 定理2-4 左线性文法的产生式与右线性文法的产生式混用所得到的文法不是 RG。 证明： 设有文法 G16：S?0A A?S1 | 1 不难看出，L(G16)={ 0n1n | n≥1 }。 我们构造不出 RG G，使得 L(G)= L(G16)={ 0n1n | n≥1 }。 因为 L(G16) = { 0n1n | n≥1 } 不是 RL。 (该语言不是 RL 的证明留到研究 RL 的性质时去完成 ) 所以，G16 不是 RG。 * 2.5 空语句 形如A?ε的产生式叫做空产生式，也可叫做ε产生式。 在RG、CFG、CSG中，都不能含有空产生式。所以，任何CSL中都不含有空语句ε。从而 CFL 和 RL 中都不能含空语句ε。 空语句ε在一个语言中的存在并不影响该语言的有穷描述的存在性，甚至除了为生成空语句ε外，空产生式可以不被用于语言中其他任何句子的推导中。 允许 CSL、CFL、RL 包含空语句ε后，还会给我们进行问题的处理提供一些方便。 允许在 RG、CFG、CSG 中含有空产生式。 允许 CSL、CFL、RL 包含空语句ε。 * 定理2-5 设G=(V,T,P,S)为一文法，则存在与G同类型的文法G=(V,T,P, S )，使得L(G)=L(G )，但G 的开始符号S 不出现在G 的任何产生式的右部。 证明思路： 当文法G=(V, T, P, S)的开始符号S不出现在P中的任何产生式的右部时，G就是所求。 否则，构造 G =(V∪{S }, T, P , S ) P =P∪{S ?α| S?α∈P} 证明L(G)= L(G ) 即可。 * 空语句 设G=(V, T, P, S) 是一个文法，如果S不出现在G的任何产生式的右部，则： ⑴如果G是CSG，则仍然称G=(V,T,P∪{S?ε}，S)为CSG； G产生的语言仍然称为CSL。 ⑵如果G是CFG，则仍然称G=(V,T,P∪{S?ε}，S)为CFG； G产生的语言仍然称为CFL。 ⑶如果G是RG，则仍然称G=(V,T,P∪{S?ε}，S)为RG。 G产生的语言仍然称为RL。 * 定理2-6 下列命题成立： ⑴ 如果L是CSL，则L∪{ε}仍然是CSL。 ⑵ 如果L是CFL，则L∪{ε}仍然是CFL。 ⑶ 如果L是RL， 则L∪{ε}仍然是RL。 * 定理2-7 下列命题成立 ⑴ 如果L是CSL，则L-{ε}仍然是CSL。 ⑵ 如果L是CFL，则L-{ε}仍然是CFL。 ⑶ 如果L是RL， 则L-{ε}仍然是RL。 * 空语句 对于任意文法G=(V, T, P, S)，对于G中的其他变量A，出现形如A?ε的产生式是不会改变文法产生的语言的类型的。 约定：对于G中的任何变量A，在需要的时候，可以出现形如A?ε的产生式。 * 2.6 本章小结 ⑴ 文法G=(V,T,P,S)。任意A∈V表示集合L(A)={w | w∈T*且A ?* w}。 ⑵ 推导与归约。文法中的推导是根据文法的产生式进行的。如果α?β∈P，γ,δ∈(V∪T)*，则称γαδ在G中直接推导出γβδ：γαδ?G γβδ；也称γβδ在文法G中直接归约成γαδ。 ⑶ 语言、句子和句型。 文法G产生的语言L(G)={w | w∈T*且S ?* w}，w∈L(G)为句子。 一般地，由开始符号推出来的任意符号行叫做G的句型。 ⑷ 一个语言可以被多个文法产生，产生相同语言的文法被称是等价的。 ⑸ 右线性文法的产生式都可以是形如A?a和A?aB的产生式。 左线性文法的产生式都可以是形如A?a和A?Ba的产生式。 左线性文法与右线性文法是等价的。 左线性文法的产生式与右线性文法的产生式混用所得到的文法不是正则文法。 * 作业 2、3、4、8、9 巴科斯—瑙尔范式 在类 Pascal 语言中，语句是用下述一组规则定义的： 语句 ::= 条件语句∣当语句∣复合语句∣赋值语句 条件语句 ::= if 布尔表达式 then 语句 else 语句 当语句 ::= while 布尔表达式 do 语句 复合语句 ::= begin 语句表 end 语句表 ::= 语句∣语句；语句表 赋值语句 : := 变量 := 算术表达式 布尔表达式 : := 算术表达式关系运算符算术表达式 关系运算符 : := | |≦∣≧∣=∣≠ 算术表达式 : := 常量|变量|（算术表达式算术运算符算术表达式） 算术运算符 : := + | - | * | / 常量: := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 变量::= a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z 以上这