第2章-文法与语言.ppt

2.4 文法的类型 1型文法(CSG)：对任一产生式α→β，都有|β|=|α|， 仅仅 S→ε除外 1型文法（上下文有关文法context-sensitive）： 产生式的形式描述：α1Aα2?α1βα2 (其中，α1、α2、β∈（VN∪VT）*，β≠ε，A∈VN) 即：A只有出现在α1α2的上下文中，才允许用β替换。 产生的语言称“上下文有关语言” 例如：0A0?011000 1A1?101011 2型文法(CFG)：对任一产生式α→β，都有α∈VN，β∈（VN∪VT）* 产生式的形式描述：A?β(A∈VN) 即β取代A时，与A所处的上下文无关。 产生的语言称“上下文无关语言” 例如：G[S]：S?01 S?0S1 3型文法(RG)：也称正规文法 每个产生式均为 “A?aB”或“A?a” —— 右线性 “A?Ba”或“A?a” —— 左线性 其中，A、B∈VN，a∈VT* 产生的语言称“正规语言” 例如：G[S]： S?0A | 0 A?1B | B B?1 | 0 4个文法类的定义是逐渐增加限制的，因此每一种正规文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是0型文法。 0型文法 1型文法 2型文法 3型文法 　四种文法之间的关系是：包含关系.（原因：将产生式做进一步限制而定义的。） 文法举例 例：1型（上下文有关）文法 文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD 1型文法举例 例：2型（上下文无关）文法 文法G[S]： S→B A→AB|0 B→0BA|1 例：3型(正则（或正规）)文法 文法G[S]：S→0A|1B|0 A→0A|1B|0S B→1B|1|0 2型和3型文法举例 a. 0型文法产生的语言称为0型语言 b. 1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL） c. 2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CF L ） d. 3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言正则（正规）语言（ RL ） 四种类型文法产生的语言 2.5 上下文无关文法及其语法树 上下文无关文法有足够的能力描述现今程序设计语言的语法结构。 算术表达式 语句 赋值语句 条件语句 读语句 …… 算术表达式上下文无关文法表示 文法G[E]: E → E+E E → E*E E → (E) E → i 条件语句→if条件then语句 条件语句→if条件then语句else 语句 条件语句上下文无关文法表示 上下文无关文法的语法树 用于描述上下文无关文法的句型推导的直观方法 例: G[S]: S→aAS A→SbA A→SS S→a A→ba S a A S S b A a a b a 句型aabbaa的语法树（推导树） 叶子结点：树中没有子孙的结点。 从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。 推导过程中施用产生式的顺序 例: G[S]: S→aAS A→SbA A→SS S→a A→ba S a A S S b A a a b a 句型aabbaa的语法树（推导树） S?aAS?aAa?aSbAa?aSbbaa?aabbaa S?aAS?aSbAS?aabAS?aabbaS?aabbaa S?aAS?aSbAS?aSbAa?aabAa?aabbaa 最右推导 最左推导 最右推导被称为规范推导 由规范推导所得的句型称为规范句型 问题：一个句型是否对应唯一的一棵语法树？ 例：G[E]: E → i E →