第2章文法和语言 加引言 0 2.1文法的直观概念 0 2.2符号和符号串 ▣2.3文法和语言的形式定义 (重点) 0 2.4文法的类型 0 2.5上下文无关文法及其语法树（重点） 口补充实例：小C语言源程序及其文法（重点） 02.6句型的分析（重点) 0 作业 课程目录 L ☒2
1 第2章 文法和语言 引言 2.1 文法的直观概念 2.2 符号和符号串 2.3 文法和语言的形式定义（重点） 2.4 文法的类型 2.5 上下文无关文法及其语法树（重点） 补充实例：小C语言源程序及其文法（重点） 2.6 句型的分析（重点） 作业 课程目录
回顾本章目的：为语言的语法描述寻求工具-一文法 口一种程序设计语言的字母表是该语言的基本字符集合。 口C语言字符集：大小写字母a-zA-Z、数字0-9、空白符、 标点和特殊符号。 {a,b,.z,A.Z,0,.9,+,*>,.} C程序是在C基本字符集上按一定规则构成的符号串。 符合词法和语法规则的字符串。 int main() int main() integer a,b,c; int a,b,c; a=b c; c=a b; } 合法吗？ C语言字母表={所有C语言基本字符} C语言=符合C语言语法规则的符号串集合{所有C语言基本字符}*的子集。 如何构造语法规则一文法 9
2 回顾 本章目的:为语言的语法描述寻求工具-文法 一种程序设计语言的字母表是该语言的基本字符集合。 C语言字符集：大小写字母a-z A-Z、数字0-9、空白符、 标点和特殊符号。 {a,b,.z,A,.Z,0,.9,+,*,>,.} C程序是在C基本字符集上按一定规则构成的符号串。 符合词法和语法规则的字符串。 int main() { int a, b, c; c = a + b; } C语言字母表 = {所有C语言基本字符} C语言 = 符合C语言语法规则的符号串集合{所有C语言基本字符} *的子集。 如何构造语法规则-文法 int main() { integer a, b, c; a = b $ c; } 合法吗？
2.3文法和语言的形式定义p21 口规则或产生式 加文法的定义 口（直接）推导和（直接）归约 加句型和句子 口文法描述的语言 口文法的等价性 迎
3 2.3 文法和语言的形式定义 p21 规则或产生式 文法的定义 (直接)推导和 (直接)归约 句型和句子 文法描述的语言 文法的等价性
例算术表达式的文法G 考虑含有+、*的算术表达式组成的文法 加G=({i,*,(,)},{E},E, 终结符 非终结符 开始符号 产生式集合 集合Vn 集合VN P: E→ E+E 表达式3*4可由该文法定义 E→ E*E E=〉E米E E→ (E) =〉i米E E→ 直接推导 =>i米1 3 4 o简写G[E]:E→E+E|E*E|(E)|i
4 例 算术表达式的文法 G 考虑含有+、*的算术表达式组成的文法 G =({i，+，*，(，)}，{E}，E，P) P: E → E + E E → E * E E → ( E ) E → i 终结符 集合ＶT 非终结符 集合ＶN 开始符号 S 简写 G[E]:E → E + E | E * E | ( E ) | i 表达式3*4可由该文法定义 E => E * E => i * E => i * i 3 4 直接推导 产生式集合 P
文法G的形式定义p22 G=(VT,VN,S,P) 0 Chomsky?定义文法为一个四元式 口Vr非空有穷终结符集 oVN非空有穷非终结符集 VT∩VN=Φ 0 S∈VN开始符号 ▣S至少在产生式左部出现一次 口P非空有穷产生式集合α→B 口a∈(VUVN)*,且至少含有一个非终结符 oB∈(VT UVN)*, o令V=VT UVN ▣称V为文法符号，是文法G的字母表
5 文法G的形式定义 p22 Ｇ = (ＶT，ＶN，S，P) Chomsky定义文法为一个四元式 ＶT 非空有穷终结符集 ＶN 非空有穷非终结符集 ＶT ∩ＶN = ф Ｓ∈ＶN 开始符号 S至少在产生式左部出现一次 Ｐ非空有穷产生式集合 α→β α∈(ＶT ∪ＶN) * ，且至少含有一个非终结符 β∈(ＶT ∪ＶN) * ， 令Ｖ=ＶT ∪ＶN 称Ｖ为文法符号，是文法G的字母表
直接推导（直接归约）p22-23 口产生式右部代替左部 口当A→Y是文法G的一个产生式， 则有aAB=>aYB, 称aYB是aAB的直接推导 或称aYB直接归约到aAB G[E]E-E +EEE(E)i oE=>E+E=>i+E=>i+E米E 特点：只能用一次产生式替换 D
6 直接推导（直接归约）p22-23 产生式右部代替左部 当Ａ→γ是文法Ｇ的一个产生式， 则有αＡβ => αγβ， 称αγβ是αＡβ的直接推导 或称αγβ直接归约到αＡβ G[E]:E→E + E|E * E|( E )|i E=>E + E=>i + E => i + E * E 特点：只能用一次产生式替换
推导（归约)p23 0如果a0=〉a1=〉a2=>.=〉an,则称这个序列 是从ao至an的一个推导。 口用ao=t>an表示从ao出发，经一步或多步推 导，可推出ano 口例如E=>E*E=〉1*E=〉1*1 口E=+>i*i至少用一次产生式替换。 口用a>an表示从ao出发，经零步或多步推 导，可推出an,即aoan或a0t>an。 口例如E=E 加E=*〉E可以不用产生式替换
7 推导（归约）p23 如果α0=>α1=>α2=>.=>αn，则称这个序列 是从α0至αn的一个推导。 用α0= +>αn表示从α0出发，经一步或多步推 导，可推出αn。 例如 E => E * E => i * E => i * i E =+> i * i 至少用一次产生式替换。 用α0= *>αn表示从α0出发，经零步或多步推 导，可推出αn ，即α0=αn或α0= +>αn 。 例如 E = E E =*> E 可以不用产生式替换
句型和句子生成举例 口例：文法G(E)为： E→E+EE米E(E)i 口表达式（i*i+i)的生成 0E=>（E) => (E+E) =〉 （E米E+E) 句型(UV)* 0 =〉 (i E +E) 0 =〉 ii+E) 0 7 (i*i+i)句子V* ☒2
8 例: 文法G(E)为： E → E + E | E * E | ( E ) | i 表达式 (i * i + i) 的生成 E => ( E ) => ( E + E ) => ( E * E + E ) => ( i * E + E ) => ( i * i + E ) => ( i * i + i ) 句型和句子生成举例 句型(VT∪VN) * 句子 VT *
句型p23 口设G是一个文法 oS是开始符号，若有S=*>a,则称是α文法G的 一个句型。 0句子 0 完全由终结符组成的句型。 口合法句子的生成 口从S出发反复推导，每次得到一个句型，最终得 到句子。 L 9
9 句型 p23 设G是一个文法 S是开始符号，若有 S = *>α，则称是α文法G的 一个句型。 句子 完全由终结符组成的句型。 合法句子的生成 从Ｓ出发反复推导，每次得到一个句型，最终得 到句子
句型和句子生成练习 o例：文法G[E]为： E→E+EE*E（E)i 口表达式 i+i*i的生成BEGIN oE => E+E 0 => i+E 句型 0 => i+E米E => i+i米E => i+i*i 句子 口表达式i*(i+i)的生成过程 BEGIN 4 ☒ 0
10 例: 文法G[E]为： E → E + E | E * E | ( E ) | i 表达式 i + i * i 的生成 BEGIN E => E + E => i + E => i + E * E => i + i * E => i + i * i 句型和句子生成练习 句型 句子 表达式 i*(i+i)的生成过程 BEGIN