第 2 讲 与 文法和语法 .ppt

第 二 讲 文 法 和 语 言 文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 上下文无关文法的句型分析 有关文法实用中的一些说明 第一节 语 言 第二节 文 法 第三节 符号和符号串 第四节 文法和语言的形式定义 二、 推 导 的 定 义 四、 语 言 的 定 义 由文法G生成的语言记为L(G)，它是文法G的全部句子的集合: L(G) = { x | S x，且x ∈VT*， 其中S为文法的开始符号 } 例：G： S→0S1， S→01 L(G) = { 0n1n | n≥1 } 例3.3 设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(G1) = L(G2)，则称文法G1和G2是等价的。 如文法G1[A]：A→0R A→01 R→A1 第五节 文 法 的 类 型 通过对产生式施加不同的限制，Chomsky将文法分为四种类型（称为Chomsky 文法） 一、文 法 的 类 型 0型文法：对任一产生式α→β，都有α∈(VN∪VT)+， β∈(VN∪VT)* 1型文法：对任一产生式α→β，都有|β|≥|α|， 仅仅 S→ε 除外 2型文法：对任一产生式α→β，都有α∈VN ， β∈(VN∪VT)* 3型文法：任一产生式α→β的形式都为 (1) A→aB 或 A→a，其中A∈VN ，B∈VN ，a∈VT (右线性文法) 或 (2) A→Ba 或 A→a，其中A∈VN ，B∈VN ，a∈VT (左线性文法) 1型文法：对任一产生式α→β，都有|β|≥|α|， 仅仅 S→ε除外 上下文有关文法： α1Aα2→α1βα2(A在VN中，其他在V*中，β≠ε) 2型文法：对任一产生式α→β，都有α∈VN ， β∈(VN∪VT)* 上下文无关文法：A→β(A在VN中，β在V*中，) 3型文法也叫正规文法 例：1型（上下文有关）文法 文法G[S]： S→aSBE S→aBE EB→BE aB→ab bB→bb bE→be eE→ee 例： 2型（上下文无关）文法 文法G[S]： S→aB|bA A→a|aS|bAA B→b|bS|aBB 例: 3型文法 G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0 二、 文 法 和 语 言 0型文法( PSG )产生的语言称为0型语言 1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL） 2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CF L ） 3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言或正则（正规）语言（ RL ） 第六节 上下文无关文法及其语法树 上下文无关文法有足够的能力描述现今程序设计语言的语法结构 算术表达式 语句 赋值语句 条件语句 读语句 …… 算术表达式上下文无关文法表示： 文法 G = ({E}, {+,*,i,(,)}, P, E ） P: E → i E → E+E E → E*E E → (E) 条件语句上下文无关文法表示 条件语句 → if 条件 then 语句 |  if 条件 then 语句 else 语句 一、 上下文无关文法的语法树 用于描述上下文无关文法的句型推导的直观方法 推导过程中施用产生式的顺序 最右（最左）推导：在推导的任何一步α?β，其中α、β是句型，都是对α中的最右（左）非终结符进行替换 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型 例：G[E]: E → i E → E+E E → E*E E → (E) 二、 二 义 文 法 若一个文法存在某个句型对应两棵不同的语法树，则称这个文