第2章文法和语言 n引言 n 2.1文法的直观概念（预习） n 2.2符号和符号串（预习） n 2.3文法和语言的形式定义（重点) n 2.4文法的类型 n 2.5上下文无关文法及其语法树（重点) n补充实例：小C语言源程序及其文法（重点) n 2.6句型的分析（重点第5章讲解) n 作业 课程目录 4 ☒D 1/38
第2章 文法和语言 n 引言 n 2.1 文法的直观概念（预习） n 2.2 符号和符号串（预习） n 2.3 文法和语言的形式定义（重点） n 2.4 文法的类型 n 2.5 上下文无关文法及其语法树（重点） n 补充实例：小C语言源程序及其文法（重点） n 2.6 句型的分析（重点 第5章讲解） n 作业 课程目录 1/38
语言特征及本章目的 n语言（由句子组成的集合，由一组记号所构成) n自然语言（人与人的通信工具） u汉语一所有符合汉语语法的句子的全体。 u英语一所有符合英语语法的句子的全体。 n计算机语言（计算机软件使用的通信工具） u程序设计语言—所有该语言的程序的全体。 n研究语言 u每个句子构成的规律 语法形式语言 u每个句子的含义 语义形式语义 本章目的：为语言的语法描述寻求工具。 国 2/38
语言特征及本章目的 n 语言（由句子组成的集合，由一组记号所构成） n 自然语言（人与人的通信工具） u 汉语——所有符合汉语语法的句子的全体。 u 英语——所有符合英语语法的句子的全体。 n 计算机语言（计算机软件使用的通信工具） u 程序设计语言——所有该语言的程序的全体。 n 研究语言 u 每个句子构成的规律 语法 形式语言 u 每个句子的含义 语义 形式语义 本章目的:为语言的语法描述寻求工具。 2/38
计算机语言的组成结构 自然 语言 句子的集合 言 句子 多个单词按一定规则组成 单词 多个字符按一定规则组成 编程语言 程序的集合 序语言 程序 多个单词按语法规则组成 单词 多个字符按词法规则组成
3 计算机语言的组成结构 自 然 语 言 程 序 语 言 语言 句子的集合 句子 多个单词按一定规则组成 单词 多个字符按一定规则组成 编程语言 程序的集合 程序 多个单词按语法规则组成 单词 多个字符按词法规则组成
程序语言的定义p19 一个程序语言是一个记号系统 n程序语言的定义语法和语义 n语法形成和产生合适程序的规则集 u词法规则 形成单词符号的规则 u语法规则 形成语法单位的规则 n 常用的语法描述方法 u正规文法—一词法规则 u上下文无关文法—一 语法规则 u 单词—一具有语义的最小字符串 ☒
4 程序语言的定义 p19 n 一个程序语言是一个记号系统 n 程序语言的定义 语法和语义 n 语法 形成和产生合适程序的规则集 u 词法规则 形成单词符号的规则 u 语法规则 形成语法单位的规则 n 常用的语法描述方法 u 正规文法——词法规则 u 上下文无关文法——语法规则 u 单词——具有语义的最小字符串
程序语言的语法构成 例源程序字符串0.5*X1+0 (a+b)*2 0.5 2 词法 单词 常数 X1 C 规则 符号 标识符 a b 关键字 语 算符 米+ + 界符 () 语法 语法 表达式 0.5*X1+0 (a+b)*2 规则 单位 语句 (范畴) 函数、过程 程序 5/38
程序语言的语法构成 语 法 词法 规则 语法 规则 单词 符号 常数 标识符 关键字 算符 界符 语法 单位 (范畴) 表达式 语句 函数、过程 程序 例 源程序字符串 0.5*X1+C 0.5 * X1 + C 0.5*X1+C (a+b)*2 ( a + b ) * 2 (a+b)*2 5/38
程序语言语义 n语义用以定义程序意义的规则集 在不同语言中完全相同的语法单位 含义却可能完全不同 u例如：x=y C语言—赋值表达式 Pascal语言一关系表达式C中x=y 章节目录 ☒ 6/38
程序语言语义 n 语义 用以定义程序意义的规则集 u 在不同语言中完全相同的语法单位 含义却可能完全不同 u 例如：x=y C语言——赋值表达式 Pascal语言——关系表达式 C中x==y 章节目录 6/38
2.1文法的直观概念p19 n定义描述英语句子的文法 u例如He gave me a book n文法的规则如下： (1)→ (2)+ (⑤)→ (6)→Heme (7)→gave 推导和语法树 (9)→book peach ☒位
7 2.1 文法的直观概念 p19 n 定义描述英语句子的文法 u 例如 He gave me a book n 文法的规则如下： (1)→ (2)→ (3)→ (4)→ (5)→ (6)→He|me (7)→a (8)→gave (9)→book|peach 请给出句子的 推导和语法树
例 He gave me a book 应用上述语法规则进行推导： 上下文无关文法 句子) 实例 =〉主语 谓语间接宾语直接宾语 =〉代词谓语间接宾语直接宾语 n 终结符号 He,me,book,gave,a等 =>He谓语间接宾语直接宾语 n 非终结符号 =>He动词 间接宾语 直接宾语 句子，主语，谓语，动词等 n 开始符号句子 =>He gave 间接宾语直接宾语 n 产生式语法规则 =>He gave代词直接宾语 =>He gave me直接宾语 9条规则 (1) =〉He gave me a名词 (3)→〈名词〉 (6)+a (8)→gave 注：省略非终结符的尖括号 (9)→book|peach ☒>
8 上下文无关文法 实例 例 He gave me a book 应用上述语法规则进行推导： =>主语 谓语 间接宾语 直接宾语 =>代词 谓语 间接宾语 直接宾语 =>He 谓语 间接宾语 直接宾语 =>He 动词 间接宾语 直接宾语 =>He gave 间接宾语 直接宾语 =>He gave 代词 直接宾语 =>He gave me 直接宾语 => He gave me 冠词 名词 => He gave me a 名词 => He gave me a book 注：省略非终结符的尖括号<> n 终结符号 He,me,book,gave,a等 n 非终结符号 句子,主语,谓语,动词等 n 开始符号 句子 n 产生式 语法规则 9条规则 (1)→ (2)→ (3)→ (4)→ (5)→ (6)→He|me (7)→a (8)→gave (9)→book|peach
9条规用 (1)(句→（主） 〈谓语〉 《动词〉 <代词〉 <冠词〉 <名词〉 He gave me a book 终结符 由文法所定义的终结符串 句子
9 上下文无关文法 实例语法树 例 He gave me a book He gave me a book 非终结符 开始符 → 终结符 由文法所定义的终结符串——句子
2.1文法概念理解（课堂练习）p19 6.川 7.→)： 小C语言源程序 |Kif关键字)(《表达式>)： &.《hi1e语句>→)： mainO n 9.→(《表达式>：) n { →{《语句序列>】 n int a,b; n 1山.赋值语句>→： a=1;/赋值语句 12.表达式>→布尔表达式> n 13.布尔表达式>◆ b=a+1; |算澉表达式>关系运算符> 14. 关系运算符>→>K==|= 15.→+K项 -K项水因于>川+川(《算数表达式>) 1. 程序)·◆（字母>K标识符> 2、声明序列心>→ n 19.无符号整数>+ 声明语句>川空> n 20. →ab小.zaB.Z 3.声明语句>→： 21、 +011123145617819 4标识符表>→，标识符> n 22。《ain关键字)◆ain 5.《语句序列>+川语句> 28.→hi1e BEGIN语法树推导 26.<for关键字)→for 27.int关键字)→int 文法的特点：以有穷的集合刻画无穷集合的一个工具。 章节目录 1U158
2.1 文法概念理解(课堂练习) p19 一个小C语言及其文法 n 小C语言文法 n 1. →(){} n 2. → || n 3. →; n 4. →,| n 5. →| n 6. →|| || n 7. →(); | (); n 8. → (); n 9. →(;;) ; n 10. →{} n 11. →; n 12. →=| n 13. → | n 14. →>|=|→+ |-| n 16. →*|/| n 17. →||() n 18. →|| n 19. →| n 20. →a|b|.|z|A|B|.|Z n 21. →0|1|2|3|4|5|6|7|8|9 n 22. →main n 23. →if n 24. →else n 25. →while n 26. →for n 27. →int n 小C语言源程序 n main() n { n int a, b; n a=1; //赋值语句 n b = a + 1; n } 文法的特点：以有穷的集合刻画无穷集合的一个工具。 10/38 BEGIN 语法树推导 章节目录