PPT《编译原理》

5、语言的定义: L(G)表示文法G产生的语言定义为: G产生的句子的集合{x?S?x, S为文法开始符号, x?VT* }该集合为语言,用L(G)表示.从定义可知: x是句型且x是文法G的句子. 想: 例1的语言表示为什么? *

5、语言的定义: L(G)表示文法G产生的语言定义为:集合 {x?S?x, S为文法开始符号, x?VT* }该集合为语言,用L(G)表示.从定义可知: x是句型且x是文法G的句子. 想: 例1的语言表示为什么?答案:L(G)={0n1n ?n?1} 因为S?0S1?00S11?…? 0n1n重复利用规则S?0S1 例5:设G=(VN ,VT ,P,S), VN={S,B,E} VT={a,b,e}P产生式为: (1) S →aSBE (2) S →aBE (3) EB → BE (4) aB →ab (5) bB →bb (6) bE →be (7) eE →ee想:L(G)表示为什么? 例5:设G=(VN ,VT ,P,S), VN={S,B,E} VT={a,b,e}P产生式为: (1) S →aSBE (2) S →aBE (3) EB → BE (4) aB →ab (5) bB →bb (6) bE →be (7) eE →ee想:L(G)表示为什么? L(G)={anbnen | n?1}解:S ?aSBE ?aaSBEBE ?aaaSBEBEBE ?…?aaaSBBEBEE?aaaSBBBEEE?aaaaBEBBBEEE?aaaaBBEBBEEE?aaaaBBBEBEEE?aaaaBBBBEEEE?aaaabBBBEEEE?aaaabbBBEEEE?aaaabbbBEEEE?aaaabbbbEEEE?aaaabbbbeEEE? aaaabbbbeeEE?aaaabbbbeeeE ? aaaabbbbeeee ? a4b4e4 同理:S?anbnen *

四、文法的类型:语言学家Chomsky把文法分成以下四种类型: 0型?短语文法1型?上下文有关文法2型?上下文无关文法3型?正规文法 文法类型逐渐增加限制如果文法是正规文法?一定也是上下文无关文法 设G=(VN,VT,P,S),如果它的每一个产生式?? ?满足:??(VN∪VT)*且至少包含一个非终结符, ? ?(VN ∪ VT)*,则G是0型文法. 设G=(VN,VT,P,S),如果它的每一个产生式?? ?满足: | ?|≥| ?|,仅仅S ??除外,则文法G是1型文法. 1型文法又称为上下文有关文法,它的每一个产生式也可描述为: ?1A?2 ? ?1??2,其中?1?2 ?都在(VN∪VT)*中, A在VN中.只有A出现在?1?2的上下文中,才允许用?取代A.

1、上下文无关文法: 设G=(VN ,VT ,P,S),若P中的每一个产生式?→?满足:?是一非终结符,??(VN ∪VT)*,则此文法称为上下文无关文法 (2型文法) .(用? 取代? 与? 所在的上下文无关) 例6:G=({S,A,B},{a,b},P,S),P的产生式如下: S→aB S→bAA→bAA A→aA→aS B→bB→bSB→aBB 上下文无关文法 该文法可以写成: S→aB | bAA→ a | aS | bAAB→ b | Bs | aBB

2、正规文法: 设G=(VN ,VT ,P,S),若P中的每一个产生式都是A→aB或A→a,A,B都是非终结符,a是终结符,则G是正规文法. 例6:G=({S,A,B},{0,1},P,S),P的产生式如下: S→0A S→1BS→0 A→0SA→0A A→1BB→1B→0B→1B 正规文法 该文法可以写成: S→

0 | 0A | 1BA→ 0S | 0A | 1BB→

0 |

1 | 1B 上下文无关文法有足够的能力描述现今程序设计语言的语法结构描述一种简单赋值语句的产生式:〈赋值语句〉→i∶=E描述条件语句的产生式:〈条件语句〉→if〈条件〉then〈语句〉if〈条件〉then〈语句〉else〈语句〉 给定一段程序,如何判断它是否符合程序设计语言的上下文无关文法? 给定一段程序,如何判断它是否符合程序设计语言的上下文无关文法?

五、上下文无关文法及其语法树

1、语法树(推导树)的定义: 给定文法G=(VN,VT,P,S),对于G的任何句型都能构造与之关联的语法树,须满足条件为: ? 每个结点都有一个标记,此标记是V的一个符号. ? 根的标记是S. ? 若一结点n至少有一个它自己除外的子孙,并且有标记A,则A肯定在VN中. ? 如果结点n的直接子孙,从左到右的次序是结点n1,n2,…,nK,其标记分别为A1,A2,…,A K ,那么A? A1A2…AK一定是P中的一个产生式. 描述上下文无关文法的句型推导的直观方法 . 例8:G=( {S,A},{a,b},P,S ),其中P为: S ? aASA ? SbAA ? SSS ? aA ? ba 想:请构造aabbaa的语法树 S a A S a S b A a a b 说明:语法树满足: ?树根是S. 每个节点的标记都是V的一个符号.? A有自己的子孙( S,b,A) ,A?VN中.?SbA是A? SbA的产生式,aAS是S? aAS的产生式. 语法树的理解: 语法树表示了在推导过程中用到什么样的产生式和用到哪些非........