第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的字母表