第三章 文法和语言.pptVIP

1 1 定义3.4：若有v　　w，或v=w，则记作： + * 定义3.5：若有S　　x，则称x是文法G[S]的句型，若x仅 　由终结符组成，则称x为G[S]的句子 * 定义3.6：文法G所产生的语言定义为集合 　L(G)=｛x|S　　x，其中S为文法识别符号，且x∈VT*｝ 文法描述的语言是该文法一切句子的集合 例：G： S　　0S1， S　　01 　　　L(G)={0n1n|n≥1} * 例3.3　文法文法G[S]： （1）S　　aSBE （2）S　　aBE （3）EB　　BE （4）aB　　ab （5）bB　　bb （6）bE　　be （7）eE　　ee L（G）={ anbnen | n≥1 } 思考：a4b4e4怎么推导？ 定义3.7：若L(G1)＝L(G2)，则称文法G1和G2是等价的 例如文法G[A]： A　　0R A　　01 R　　A1 　和文法G[S]： S　　0S1 S　　01 等价　L(G)={0n1n|n≥1} 3.4 文法的类型 乔姆斯基(Chomsky)于1956年建立形式语言的描述 他把文法分成：0型、1型、2型、3型 四个文法类的定义是逐渐增加限制的 0型 1型 2型 3型 设G＝（VN，VT，P，S），如果它的每个产生式 　α　　β是这样一种结构：α∈(VN∪VT)*且α至少包 　含一个非终结符， β∈(VN∪VT)*，则G是一个0型文法 　（短语文法、无限制文法） 思考：这样定义可以吗？ 设G＝（VN，VT，P，S），如果它的每个产生式 　α　　β是这样一种结构：α∈(VN∪VT)+， β∈(VN∪VT)*，则G是一个0型文法 重要的理论结果： 0型文法的能力相当于图灵机（Turing） 或者说，任何0型语言都是递归可枚举的 反之，递归可枚举集必定是一个0型语言 设G＝（VN，VT，P，S），如果它的每个产生式 　α　　β均满足：|β| ≥ |α|，仅仅S　　ε除外， 　则文法G是1型文法（上下文有关文法） 例3.1、3.2、3.3 例：文法G[S]： 　　　　　　 S　　CD Ab　　bA C　　aCA Ba　　aB C　　bCB Bb　　bB AD　　aD C　　ε BD　　bD D　　ε Aa　　bD L(G)={w|w∈{a,b}*} 有些定义中，将上下文有关文法的产生式的形式描述为 　α1Aα2　　α1βα2，其中α1、α2和β都在V*中， 　β≠ε，A在VN中 设G＝（VN，VT，P，S），如果它的每个产生式 　α　　β均满足：α是一个非终结符，β∈V*，则文法 　G是2型文法（上下文无关文法） 有时将2型文法的产生式表示为A　　β的形式，其中 　A∈VN，也就是用β取代非终结符A时，与A所在的上下 　文无关，因此取名为上下文无关 例3.1、3.2 例3.4：文法G[S]： 　　　　S　　aB|bA 　A　　a|aS|bAA 　B　　b|bS|aBB 设G＝（VN，VT，P，S），如果它的每个产生式 　A　　αB或A 　　α，其中A和B都是非终结符， 　α∈VT*，则文法G是3型文法（正规文法） 例3.5：文法G[S]： 　　　　S　　0A|1B|0 　A　　0A|1B|0S 　B　　1B|1|0 你会忘记我吗？ 4个文法类的定义是逐渐增加限制的，因此，每一种正规 　文法都是上下文无关的，每一种上下文无关文法都是上 　下文有关的，而每一种上下文有关文法都是0型文法 称0型文法产生的语言为0型语言，上下文有关文法、上 　下文无关文法和正规文法产生的语言分别称为上下文有 　关语言、上下文无关语言和正规语言 3.5 上下文无关文法及其语法树 上下文无关文法有足够的能力描述现今程序设计语言的 　语法结构，比如描述算术表达式、描述各种语句等 例3.6：文法G=({E},{+,*,i,(,)},P,E)其中P为： 　　　　E　　i 　E　　E+E 　E　　E*E E (E) 条件语句　　if条件then语句| 　　　　　　　　if条件then语句else 语句 给定文法G=（VN，VT，P，S），对于G的任何句型都 　能构造与之关联的语法树（推导树、语法分析树、分 　析树）。这棵树满足下列4个条件： （1）每个结点都有一个V中的符号作标记 （2）根的标记是开始符号S （3）若一结点n至少有一个它自己除外的子孙，并且有标记 　　A，则A∈VN （4）如果结点n的直接子孙，从左到右的次序是结点 n1,n2,…,nk，其标记分别为A1,A2,…,Ak，那么 A　　A1A2…Ak一定是P中的一个产生式 例3.7：文法G=({S，A},{a,b},P,E)其中P为： 　　　　(1