石河子大学信息科学与技术学院编译原理课件第三章 文法和语言.ppt

定义或表示语言的方法： 当一个语言有有限个句子时，可采用枚举法 如：L语言只有两个句子，则可表示为： L={ I am a teacher，You are student} 例： 句子::=主语短语动词短语 主语短语::=the名词 动词短语::=动词宾语短语 宾语短语::=冠词名词 名词::=monkey|banana 动词::=ate|has 冠词::=the|a 几个概念： 1. 字母表 2. 符号串 3. 符号串的长度 4. 空符号串 5. 符号串的前缀（头） 符号串的后缀（尾） 符号串的真前缀（真后缀） 6. 符号串的子串 7. 符号串的连接 8. 符号串的方幂 规则——重写规则、产生式或生成式。 是形如α→β或α ∷= β的（ α ， β ）有序对， 其中α是某字母表V的的正闭包V+的一个符号， β是V*的一个符号。 α称为规则的左部， β称为规则的右部。 →和∷=含义相同，读作“生成”。 例：G[E]： E→E+T|T T→T*F|F F→(E)|a 对于文法 G[S] ： 　　S → 1A | 0B | ε 　　A → 0S | 1AA 　　B → 1S | 0BB 　　⑴ 请写出三个关于 G[S] 的句子； 　　⑵ 符号串 11A0S 是否为 G [S] 的句型？试证明你的结论。 例 文法G[S]： （1）S→aSBE （2）S→aBE （3）EB→BE （4）aB→ab （5）bB→bb （6）bE→be （7）eE→ee S ?a S BE (S→aSBE) ?a aBEBE (S→aBE) ?aabEBE ( aB→ab ) ?aabBEE ( EB→BE ) ?aabbEE （bB→bb) ?aabbeE （bE→be) ?aabbee （eE→ee) G生成的每个串都在L(G)中 L(G)中的每个串确实能被G生成 使用产生式(1)n-1次，得到推导序列： S =* an-1S(BE)n-1，然后使用产生式(2)一次，得到：S =* an-1S(BE)n-1 ? an(BE)n。然后从an(BE)n继续推导，总是对EB使用产生式(3)的右部进行替换，而最终在得到的串中，所有的B都先于所有的E。例如，若n=3, aaaBEBEBE ? aaaBBEEBE ? aaaBBEBEE ? aaaBBBEEE。即有： S =* anBnEn 接着，使用产生式(4)一次，得到S =* anbBn-1En，然后使用产生式(5)n-1次得到： S =* anbnEn，最后使用产生式(6)一次，使用产生式(7)n-1次，得到：S =* anbnen 也能证明，对于n≥1，串anbnen是唯一形式的终结符号串 文法的等价 若L（G1）=L（G2），则称文法G1和G2是等价的。 如文法G1[A]：A→0R 与G2[S]：S→0S1 A→01 S→01 R→A1 是否等价呢？ 文法的类型 通过对产生式施加不同的限制，Chomsky将文法分为四种类型： 0型文法：对任一产生式α→β，都有α∈(VN∪VT)+， β∈(VN∪VT)* 1型文法：对任一产生式α→β，都有|β|≥|α|， 仅仅 S→ε除外 2型文法：对任一产生式α→β，都有α∈VN ， β∈(VN∪VT)* 3型文法：任一产生式α→β的形式都为A→aB或A→a，其中A∈VN ，B∈VN ，a∈VT 文法的类型 例：1型（上下文有关）文法 文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD 文法的类型 例：2型（上下文无关）文法 文法G[S]： S→AB A→BS|0 B→SA|1 3型文法 G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0 G[I]： I → lT I → l T → lT T → dT T → l T → d 文法的类型 四种文法之间的逐级“包含”关系 文法和语言 0型文法产生的语言称为0型语言 1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL） 2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CF L