第二章 文法和语言基本知识.ppt

例如,对于条件语句，经常使用二义性文法描述它：S? if expr then S ?if expr then S else S ? other 二义性的句子: if c1 then if c2 then S1 else S2 下面是描述if语句的无二义性文法的产生式: S?mathed_s ? unmathed_s mathed_s ?if expr then mathed_s else mathed_s ?other unmathed_s ?if expr then S ? if expr then mathed_s else unmathed_s 它显然比较复杂，因此： 在能驾驭的情况下，可以使用二义性文法。 化简了的文法（限制条件） 1．产生式： ?A→A ?P ； ?2. 每个非终结符号A必须都有用处。即， ???S αAβ ， 且 A γ， γ∈VT* ?????? *? +? 2.7 文法的实用限制 2.6 文法和语言分类 语言的分类： 对文法中的规则施加不同的限制 四种类型： 0型，1型，2型，3型 0型(无限制)：G=(VT,VN,S,P) 规则形式 ： ??? ?,?? (VT?VN)*, 并且?至少含有一个非终结符号； 1型（上下文有关） ： ?A?? ?u? u ? (VT?VN)+, ??A???? ?u?? ，S ? ?除外； 2型（上下文无关）：规则形式 ： A?? A ?VN，? ? (VT?VN)* ； 3型（右线性）： A? ? B或 A? ? （左线性） A? B ?或 A ? ?， ? ?VT*， A,B ?VN L0 ? L1 ? L2 ? L3 说明： 1型文法也称上下文有关文法，非终结符的替换要考虑上下文。 规则形式如 ?A?? ??? 2型文法也称上下文无关文法，非终结符的替换不考虑上下文。 A? ? 3型文法等价于正规式，正规文法。 上下文无关文法足够描述多数程序设计语言的语法结构。 考虑文法G: S ?AB A ?aA|a B ?bB|b 定义的语言为：L(G[S])= ?anbm?n,m?1? 是2型文法。这个是线性问题，也可以写3型文法： S ?aA A ?aA| bB B ?bB| ? 本章小结： 语言语法结构的形式化描述： 上下文无关文法 语法树 句子 句型 推导 短语、直接短语、句柄 文法的二义性 作业: 1、为语言L1={ ambm bnan| m≥1 ,n ≥0} 语言L2={ akbm bnan| k≥m≥0 ,n ≥1}各构造一个上下文无关文法。 作业 2、有文法 S → aB | bA A → a | aS | bAA B → b | bS | aBB 给出其句子aabbba的最左和最右推导，构造其语法树，并指出最右推导过程中形成的各句型的短语、直接短语和句柄。 本章知识点： 第二章 文法和语言基本知识 字母表和符号串的概念 文法和语言的形式定义 直接推导、推导、句型、句子 短语、直接短语、句柄 语法树、文法的二义性 了解文法和语言的分类 2.1 概述 程序设计语言的精确定义和描述： 语法：语言结构的定义 语义：描述语言的含义 语用：从使用的角度来描述语言 非形式化描述 形式化描述：用一整套带有严格规定的符号体系来描述问题。 编译程序是针对某种程序设计语言的。 2.2 字母表和符号串的基本概念 1、字母表 字母表：字母表是元素的非空有穷集合。 任何程序语言都有自己的字母表，例如: 机器语言：由符号“0”和“1”组成的字母表，∑={0，1} ASCII字符集； C语言字母表为： ∑= {A?Z, a?z, 0?9, +, -, *, /, , =, ,:, ‘,’, ; ，.，!, ~,%,, |,^, (, ), {, },[, ] } 2.2.1 字母表和符号串 2.2 字母表和符号串的基本概念 1、字母表：元素的非空有穷集合。 2、符号：字母表∑中的元素。 3、符号串（字） 符号串：字