cha3+文法和语言.ppt

《cha3+文法和语言.ppt》由会员分享，可在线阅读，更多相关《cha3+文法和语言.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第第3章章 文法和语言文法和语言n n引言引言n n3.1 文法的直观概念文法的直观概念n n3.2 符号和符号串符号和符号串n n3.3 文法和语言的形式定义文法和语言的形式定义（重点）（重点）n n3.4 文法的类型文法的类型n n3.5 上下文无关文法及其语法树上下文无关文法及其语法树（重点）（重点）n n3.6 句型的分析句型的分析（重点）（重点）n n本章练习本章练习n n作业作业课程目录课程目录课程目录课程目录2语言特征语言特征n n自然语言自然语言uu是人与人的通讯工具是人与人的通讯工具uu环境、背景知识、语气、二义性环境、背景知识、语气、二义性uu叙述性描述（非形式化方法）叙

2、述性描述（非形式化方法）n n计算机语言计算机语言uu计算机软件使用的通讯工具计算机软件使用的通讯工具uu严格的语法、语义严格的语法、语义uu记号描述（数学描述、形式化方法）记号描述（数学描述、形式化方法）3本章目的本章目的n n本章目的本章目的 为语言的为语言的为语言的为语言的语法描述语法描述语法描述语法描述寻求工具寻求工具寻求工具寻求工具n n通过该工具可以通过该工具可以uu对源语言给出对源语言给出对源语言给出对源语言给出精确精确精确精确的无二义性的语法描述的无二义性的语法描述的无二义性的语法描述的无二义性的语法描述 (严谨、简单和易读严谨、简单和易读严谨、简单和易读严谨、简单和易读)uu

3、根据语言文法的特点来指导语法根据语言文法的特点来指导语法根据语言文法的特点来指导语法根据语言文法的特点来指导语法分析分析分析分析的过程的过程的过程的过程uu从描述语言的文法可以自动构造出可用的分析程序从描述语言的文法可以自动构造出可用的分析程序从描述语言的文法可以自动构造出可用的分析程序从描述语言的文法可以自动构造出可用的分析程序uu制导语义制导语义制导语义制导语义翻译翻译翻译翻译4语言定义语言定义n n语言语言uu是由是由是由是由句子句子句子句子组成的集合，是由一组记号所构成的组成的集合，是由一组记号所构成的组成的集合，是由一组记号所构成的组成的集合，是由一组记号所构成的集合集合集合集合n

4、n汉语汉语汉语汉语所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体n n英语英语英语英语所有符合英语语法的句子的全体所有符合英语语法的句子的全体所有符合英语语法的句子的全体所有符合英语语法的句子的全体n n程序设计语言程序设计语言程序设计语言程序设计语言所有该语言的程序的全体所有该语言的程序的全体所有该语言的程序的全体所有该语言的程序的全体n n研究语言研究语言研究语言研究语言uu每个句子构成的规律每个句子构成的规律每个句子构成的规律每个句子构成的规律uu每个句子的含义每个句子的含义每个句子的含义每个句子的含义uu每个句子和使用者

5、的关系每个句子和使用者的关系每个句子和使用者的关系每个句子和使用者的关系5语言研究的三个方面语言研究的三个方面n n语法（语法（Syntax)Syntax)uu表示构成语言句子的各个记号之间的组合规律表示构成语言句子的各个记号之间的组合规律表示构成语言句子的各个记号之间的组合规律表示构成语言句子的各个记号之间的组合规律n n语义语义(Semantics)(Semantics)uu表示按照各种表示方法所表示的各个记号的特定表示按照各种表示方法所表示的各个记号的特定表示按照各种表示方法所表示的各个记号的特定表示按照各种表示方法所表示的各个记号的特定 含义含义含义含义(各个记号和记号所表示的对象之间

6、的关系各个记号和记号所表示的对象之间的关系各个记号和记号所表示的对象之间的关系各个记号和记号所表示的对象之间的关系)n n语用语用(Pragmatics)(Pragmatics)uu表示在各个记号所出现的行为中，它们的来源、表示在各个记号所出现的行为中，它们的来源、表示在各个记号所出现的行为中，它们的来源、表示在各个记号所出现的行为中，它们的来源、使用和影响使用和影响使用和影响使用和影响6形式语言理论简介形式语言理论简介n n形式语言理论（形式语言理论（Formal Language Theory)Formal Language Theory)uu是一种从语法上研究语言的理论是一种从语法上研究

7、语言的理论是一种从语法上研究语言的理论是一种从语法上研究语言的理论uu是抽象的数学系统是抽象的数学系统是抽象的数学系统是抽象的数学系统uu着重研究符号串集合的表示法、结构及其特征着重研究符号串集合的表示法、结构及其特征着重研究符号串集合的表示法、结构及其特征着重研究符号串集合的表示法、结构及其特征uu是程序设计语言语法分析研究的基础（我们仅使是程序设计语言语法分析研究的基础（我们仅使是程序设计语言语法分析研究的基础（我们仅使是程序设计语言语法分析研究的基础（我们仅使 用与编译程序构造有关的结论，而不做证明）用与编译程序构造有关的结论，而不做证明）用与编译程序构造有关的结论，而不做证明）用与编译

8、程序构造有关的结论，而不做证明）n n形式语义形式语义(Formal Semantics)(Formal Semantics)uu(本课程不介绍）本课程不介绍）本课程不介绍）本课程不介绍）7计算机语言的组成结构计算机语言的组成结构自自然然语语言言程程序序语语言言语言语言句子的集合句子的集合句子句子多个单词按一定规则组成多个单词按一定规则组成单词单词多个字符按一定规则组成多个字符按一定规则组成编程语言编程语言程序的集合程序的集合程序程序多个单词按语法规则组成多个单词按语法规则组成单词单词多个字符按词法规则组成多个字符按词法规则组成8程序语言的定义程序语言的定义 p32p32n n一个程序语言是一

9、个记号系统一个程序语言是一个记号系统n n程序语言的定义程序语言的定义 语法语法和和语义语义n n语法语法 形成和产生形成和产生合适程序合适程序的规则集的规则集uu词法规则词法规则词法规则词法规则 形成形成形成形成单词符号单词符号单词符号单词符号的规则的规则的规则的规则uu语法规则语法规则语法规则语法规则 形成形成形成形成语法单位语法单位语法单位语法单位的规则的规则的规则的规则n n常用的语法描述方法常用的语法描述方法uu正规文法正规文法正规文法正规文法词法规则词法规则词法规则词法规则uu上下文无关文法上下文无关文法上下文无关文法上下文无关文法语法规则语法规则语法规则语法规则9程序语言的语法构

10、成程序语言的语法构成语语法法词法词法词法词法规则规则规则规则语法语法语法语法规则规则规则规则单词单词单词单词符号符号符号符号常数常数常数常数标识符标识符标识符标识符基本字基本字基本字基本字字符字符字符字符算符算符算符算符界符界符界符界符语法语法语法语法单位单位单位单位(范畴范畴范畴范畴)表达式表达式表达式表达式语句语句语句语句函数、过程函数、过程函数、过程函数、过程程序程序程序程序例例例例 源程序字符串源程序字符串源程序字符串源程序字符串 0.5*X1+C0.5*X1+C0.5*X1+C0.5*X1+C 0.5 0.5 0.5 0.5*X1 X1 X1 X1+C C C C 0.5*X1+C

11、0.5*X1+C 0.5*X1+C 0.5*X1+C(a+b)*2(a+b)*2(a+b)*2(a+b)*2(a a a a+b b b b)*2 2 2 2(a+b)*2(a+b)*2(a+b)*2(a+b)*210程序语言的定义程序语言的定义 p32p32n n语义语义 用以定义用以定义程序意义程序意义的规则集的规则集uu静态语义静态语义静态语义静态语义FF确定哪些合乎语法的程序是合适的规则集合确定哪些合乎语法的程序是合适的规则集合确定哪些合乎语法的程序是合适的规则集合确定哪些合乎语法的程序是合适的规则集合uu动态语义动态语义动态语义动态语义FF表明程序要做些什么，要计算什么表明程序要做些

12、什么，要计算什么表明程序要做些什么，要计算什么表明程序要做些什么，要计算什么uu在不同语言中完全相同的语法单位在不同语言中完全相同的语法单位在不同语言中完全相同的语法单位在不同语言中完全相同的语法单位 含义却可能完全不同含义却可能完全不同含义却可能完全不同含义却可能完全不同uu例如：例如：例如：例如：x=y Cx=y Cx=y Cx=y C语言语言语言语言赋值表达式赋值表达式赋值表达式赋值表达式 PascalPascalPascalPascal语言语言语言语言关系表达式关系表达式关系表达式关系表达式 C C C C中中中中x=yx=yx=yx=y11程序语言构成的共同点程序语言构成的共同点n

13、n语法：语法：uu语句的组成规则语句的组成规则uu描述方法：描述方法：BNFBNF范式、语法描述图范式、语法描述图n n词法：词法：uu单词的组成规则单词的组成规则uu描述方法：描述方法：BNFBNF范式、正规式范式、正规式n n单词：单词：uu具有语义的最小字符串（可区分的）具有语义的最小字符串（可区分的）章节目录章节目录章节目录章节目录123.1 3.1 文法的直观概念文法的直观概念 p32p32n n定义描述英语句子的文法定义描述英语句子的文法uu例如例如例如例如 He gave me a bookHe gave me a bookHe gave me a bookHe gave me

14、a bookn n文法的规则文法的规则如下：如下：(1)(1)(1)(1)(2)(2)(2)(2)(3)(3)(3)(3)(4)(4)(4)(4)(5)(5)(5)(5)(6)(6)(6)(6)He|meHe|meHe|meHe|me(7)(7)(7)(7)a a a a(8)(8)(8)(8)gavegavegavegave(9)(9)(9)(9)book|peachbook|peachbook|peachbook|peach13上下文无关文法上下文无关文法 实例实例例例例例 He gave me a bookHe gave me a bookHe gave me a bookHe gave

15、 me a book应用上述语法规则进行推导：应用上述语法规则进行推导：应用上述语法规则进行推导：应用上述语法规则进行推导：句子句子句子句子=主语主语主语主语 谓语谓语谓语谓语 间接宾语间接宾语间接宾语间接宾语 直接宾语直接宾语直接宾语直接宾语=代词代词代词代词 谓语谓语谓语谓语 间接宾语间接宾语间接宾语间接宾语 直接宾语直接宾语直接宾语直接宾语=He He He He 谓语谓语谓语谓语 间接宾语间接宾语间接宾语间接宾语 直接宾语直接宾语直接宾语直接宾语=He=He=He=He 动词动词动词动词 间接宾语间接宾语间接宾语间接宾语 直接宾语直接宾语直接宾语直接宾语=He=He=He=He gav

16、egavegavegave 间接宾语间接宾语间接宾语间接宾语 直接宾语直接宾语直接宾语直接宾语=He gave=He gave=He gave=He gave 代词代词代词代词 直接宾语直接宾语直接宾语直接宾语=He gave=He gave=He gave=He gave memememe 直接宾语直接宾语直接宾语直接宾语=He gave me=He gave me=He gave me=He gave me 冠词冠词冠词冠词 名词名词名词名词=He gave me=He gave me=He gave me=He gave me a a a a 名词名词名词名词=He gave me a=

17、He gave me a=He gave me a=He gave me a bookbookbookbookn n终结符号终结符号终结符号终结符号He,me,book,gave,aHe,me,book,gave,aHe,me,book,gave,aHe,me,book,gave,a等等等等n n非终结符号非终结符号非终结符号非终结符号句子句子句子句子,主语主语主语主语,谓语谓语谓语谓语,动词等动词等动词等动词等n n开始符号开始符号开始符号开始符号 句子句子句子句子n n产生式产生式产生式产生式 语法规则语法规则语法规则语法规则14上下文无关文法上下文无关文法 实例语法树实例语法树例例 He

18、 gave me a bookHe gave me a book HeHe gavegave meme a abookbook非终结符非终结符非终结符非终结符开始符开始符开始符开始符 终结符终结符终结符终结符由文法所定义的终结符串由文法所定义的终结符串由文法所定义的终结符串由文法所定义的终结符串句子句子句子句子15文法概念理解文法概念理解(课堂练习课堂练习)p32)p32n n描述汉语句子的文法规则描述汉语句子的文法规则:(1)(1)(1)(1)(2)(2)(2)(2)|(3)(3)(3)(3)我我我我|你你你你|他他他他(4)(4)(4)(4)王明王明王明王明|大学生大学生大学生大学生|工人

19、工人工人工人|英语英语英语英语(5)(5)(5)(5)(6)(6)(6)(6)是是是是|学习学习学习学习(7)(7)(7)(7)|n n请给出请给出他学习英语他学习英语的推导过程和语法树：的推导过程和语法树：BEGINBEGINn n文法的特点：文法的特点：以有穷的集合刻画无穷集合的一个工具。以有穷的集合刻画无穷集合的一个工具。以有穷的集合刻画无穷集合的一个工具。以有穷的集合刻画无穷集合的一个工具。章节目录章节目录章节目录章节目录163.2 3.2 符号和符号串符号和符号串 p33p33n n字母表字母表n n符号串符号串n n符号串的头尾符号串的头尾n n符号串的连接符号串的连接n n符号串

20、的方幂符号串的方幂n n符号串的集合符号串的集合17基本概念基本概念 符号和字母表符号和字母表 p33n n符号符号(元素元素)可以相互区别的记号可以相互区别的记号uu例例例例 a b 0 1a b 0 1a b 0 1a b 0 1n n字母表字母表 符号的非空有穷集合符号的非空有穷集合uu例例例例=0=0=0=0，1 1 1 1 二进制数语言的字母表二进制数语言的字母表二进制数语言的字母表二进制数语言的字母表 A=aA=aA=aA=a，b b b b 由符号由符号由符号由符号a a a a和和和和b b b b组成的字母表组成的字母表组成的字母表组成的字母表uu字母表包含语言中所允许出现的

21、一切符号字母表包含语言中所允许出现的一切符号字母表包含语言中所允许出现的一切符号字母表包含语言中所允许出现的一切符号uu一种程序设计语言的字母表是该语言的一种程序设计语言的字母表是该语言的一种程序设计语言的字母表是该语言的一种程序设计语言的字母表是该语言的基本字符基本字符基本字符基本字符集集集集uuC C C C语言语言语言语言是是是是C C C C程序程序程序程序的集合的集合的集合的集合uuC C C C程序程序程序程序是在是在是在是在C C C C基本字符集基本字符集基本字符集基本字符集上定义的，按一定规则构上定义的，按一定规则构上定义的，按一定规则构上定义的，按一定规则构成的成的成的成的

22、符号串符号串符号串符号串18基本概念基本概念 符号串符号串 p33n n符号串符号串符号串符号串 由字母表中的符号所组成的任何有穷序由字母表中的符号所组成的任何有穷序由字母表中的符号所组成的任何有穷序由字母表中的符号所组成的任何有穷序 列称为该字母表上的符号串列称为该字母表上的符号串列称为该字母表上的符号串列称为该字母表上的符号串uu例例例例 001110001110001110001110是字母表是字母表是字母表是字母表上的符号串上的符号串上的符号串上的符号串 a,b,aa,bb,abb,bba,a,b,aa,bb,abb,bba,a,b,aa,bb,abb,bba,a,b,aa,bb,ab

23、b,bba,都是字母表都是字母表都是字母表都是字母表A A A A上的符号串上的符号串上的符号串上的符号串uu注意注意注意注意 符号串中符号的符号串中符号的符号串中符号的符号串中符号的顺序顺序顺序顺序是重要的是重要的是重要的是重要的 例例例例 abababab不同于不同于不同于不同于babababan n符号串的符号串的符号串的符号串的长度长度长度长度 符号串中符号的个数符号串中符号的个数符号串中符号的个数符号串中符号的个数uu例例例例 x=001110 x=001110 x=001110 x=001110 则则则则x x x x长度长度长度长度|x|=6|x|=6|x|=6|x|=6n n空

24、串空串空串空串 (空字空字空字空字)长度为长度为长度为长度为0 0 0 0的符号串的符号串的符号串的符号串uu|=0|=0|=0|=019关于符号串操作关于符号串操作 n n运算运算 设设设设x x x x是某字母表上的符号串是某字母表上的符号串是某字母表上的符号串是某字母表上的符号串uu连接连接连接连接(并置并置并置并置)x=123,y=45x=123,y=45x=123,y=45x=123,y=45那么那么那么那么xy=12345xy=12345xy=12345xy=12345uu方幂方幂方幂方幂：x x x x的的的的n n n n次方幂即将次方幂即将次方幂即将次方幂即将n n n n个

25、个个个x x x x连接连接连接连接 x x x x0 0 0 0=x=x=x=x1 1 1 1=x x=x x=x x=x x2 2 2 2=xx=xx=xx=xxn n子符号串子符号串 v v是是xvyxvy的子符号串，的子符号串，v v非空非空n n头，尾头，尾 x x是是xyxy的头，的头，y y是是xyxy的尾的尾20符号串集合符号串集合n n符号串集合符号串集合 uu若集合若集合若集合若集合A A A A中的一切元素都是某字母表上的符号中的一切元素都是某字母表上的符号中的一切元素都是某字母表上的符号中的一切元素都是某字母表上的符号 串，则称串，则称串，则称串，则称A A A A为该

26、字母表上的符号串的集合为该字母表上的符号串的集合为该字母表上的符号串的集合为该字母表上的符号串的集合uu例例例例 =0=0=0=0，1111是字母表是字母表是字母表是字母表,其中其中其中其中0,10,10,10,1为符号为符号为符号为符号 则则则则D=0,1 D=0,1 D=0,1 D=0,1 其中其中其中其中0,10,10,10,1为符号串为符号串为符号串为符号串 E=,0,1,00,01,10,11,000,E=,0,1,00,01,10,11,000,E=,0,1,00,01,10,11,000,E=,0,1,00,01,10,11,000,是是是是上的符号串集合上的符号串集合上的符号串

27、集合上的符号串集合 uu特别特别特别特别 空集记为空集记为空集记为空集记为=注意与注意与注意与注意与区别区别区别区别21符号串集合的运算符号串集合的运算 p25p25n n乘积乘积 UV=|UV=|U U且且 V V uu例例例例 A=aA=aA=aA=a，b B=cb B=cb B=cb B=c，dddd 则则则则AB=acAB=acAB=acAB=ac，adadadad，bcbcbcbc，bdbdbdbdn n方幂方幂 V V的的n n次方幂就是将次方幂就是将n n个个V V相乘相乘uu设设设设A=aA=aA=aA=a，bbbbuuA A A A0 0 0 0=uuA A A A1 1 1

28、 1=A=a=A=a=A=a=A=a，bbbbuuA A A A2 2 2 2=AA=aa=AA=aa=AA=aa=AA=aa，abababab，babababa，bb bb bb bb uuA A A An n n n=AA=AA=AA=AAA(nA(nA(nA(n个个个个A A A A的乘积）的乘积）的乘积）的乘积）所有由所有由所有由所有由A A A A中符号构成的长度为中符号构成的长度为中符号构成的长度为中符号构成的长度为n n n n的符号串的集合的符号串的集合的符号串的集合的符号串的集合22符号串集合的运算符号串集合的运算 p25p25n n符号串集符号串集V V的的闭包闭包 V V

29、*uuV V V V*=V=V=V=V0 0 0 0 V V V V1 1 1 1 V V V V2 2 2 2 V V V V3 3 3 3 uu设设设设V=aV=aV=aV=a，bbbb，则，则，则，则 V V V V*=a=a=a=a，b aab aab aab aa，abababab，babababa，bbbbbbbb =，a a a a，b b b b，aaaaaaaa，abababab，babababa，bbbbbbbb，aaaaaaaaaaaa，uuV V V V的闭包的闭包的闭包的闭包V V V V*是是是是V V V V上的所有符号串上的所有符号串上的所有符号串上的所有符号串

30、(包括空字包括空字包括空字包括空字)的集合的集合的集合的集合n n符号串集符号串集V V正正则闭包则闭包 V V+uuV V V V+=V V V V1 1 1 1 V V V V2 2 2 2 V V V V3 3 3 3 =V V=V V=V V=V V*uu设设设设V=aV=aV=aV=a，bbbb，则，则，则，则 V V V V+=a=a=a=a，b aab aab aab aa，abababab，babababa，bbbbbbbb =a =a =a =a，b b b b，aaaaaaaa，abababab，babababa，bbbbbbbb，aaaaaaaaaaaa，uuV V V

31、V的正则闭包的正则闭包的正则闭包的正则闭包V V V V+是是是是V V V V上的所有的非空符号串的集合上的所有的非空符号串的集合上的所有的非空符号串的集合上的所有的非空符号串的集合23语言的概念语言的概念n n语言语言 某个字母表某个字母表上的符号串集合，是上的符号串集合，是*的的一个子集一个子集uu例例例例 =0=0=0=0，1111uu*=,0,1,00,01,10,11,000,001,=,0,1,00,01,10,11,000,001,=,0,1,00,01,10,11,000,001,=,0,1,00,01,10,11,000,001,uu则则则则 1,11,111,1111,1

32、,11,111,1111,1,11,111,1111,1,11,111,1111,是一种语言是一种语言是一种语言是一种语言章节目录章节目录章节目录章节目录243.3 3.3 文法和语言的形式定义文法和语言的形式定义 p34p34n n规则或产生式规则或产生式n n文法的定义文法的定义n n(直接直接)推导和推导和(直接直接)归约归约n n句型和句子句型和句子n n文法描述的语言文法描述的语言n n文法的等价性文法的等价性25规则或产生式规则或产生式 p34 p34 n n形式形式uu或或或或:=:=:=:=uu称为产生式的左部称为产生式的左部称为产生式的左部称为产生式的左部uu称为产生式的右部

33、称为产生式的右部称为产生式的右部称为产生式的右部uu读作读作读作读作“定义为定义为定义为定义为”n n举例举例uuAa Aa Aa Aa 这是关于这是关于这是关于这是关于A A A A的一条规则的一条规则的一条规则的一条规则uu uu a|b|a|b|a|b|a|b|z|z|z|z26文法文法G G的形式定义的形式定义 p35 p35 =(=(T T，N N，S S，P)P)n nChomskyChomsky定义文法为一个四元式定义文法为一个四元式n nT T 非空有穷终结符集非空有穷终结符集n nN N 非空有穷非终结符集非空有穷非终结符集 T T N N =n nN N 开始符号开始符号

34、uuS S S S至少在产生式左部出现一次至少在产生式左部出现一次至少在产生式左部出现一次至少在产生式左部出现一次n n非空有穷产生式集合非空有穷产生式集合 uu(T T T T N N N N)*，且至少含有一个非终结符，且至少含有一个非终结符，且至少含有一个非终结符，且至少含有一个非终结符uu(T T T T N N N N)*，n n令令=T T N N uu称为称为称为称为文法符号，是文法文法符号，是文法文法符号，是文法文法符号，是文法G G G G的字母表的字母表的字母表的字母表 27例例 算术表达式的文法算术表达式的文法 G G 考虑含有考虑含有+、*的算术表达式组成的文法的算术表

35、达式组成的文法n nG G =(=(ii，+，*，(，)，EE，E E，P P)P:E E+E P:E E+E E E*E E E*E E (E)E (E)E i E iT T T TN N N NS S S Sn n简写简写 GGE E:E E E E+E|E E|E*E|E|(E E)|i i表达式表达式表达式表达式3*43*43*43*4可由该文法定义可由该文法定义可由该文法定义可由该文法定义 E=E*EE=E*EE=E*EE=E*E =i*E =i*E =i*E =i*E =i*i i*i i*i i*i 3 4 3 4 3 4 3 4直接推导直接推导直接推导直接推导28文法描述的约定

36、文法描述的约定 p35p35n n用用大写字母大写字母A A、B B、C C或汉语词组或汉语词组 代表代表非终结符号非终结符号n n用用小写字母小写字母a a、b b、c c代表代表终结符号终结符号n n用用希腊字母希腊字母、代表终结符号代表终结符号 和非终结符号组成的和非终结符号组成的符号串符号串n n若干个左部相同的产生式可以合并为一个若干个左部相同的产生式可以合并为一个 PP1 1|2 2|n n 每个每个i i 称为称为P P的一个候选式的一个候选式29直接推导（直接归约）直接推导（直接归约）p35-36p35-36n n产生式右部代替左部产生式右部代替左部uu当当当当是文法的一个产生

37、式，是文法的一个产生式，是文法的一个产生式，是文法的一个产生式，且且且且、(T T T TN N N N)*，则有则有则有则有 =，称称称称是是是是的的的的直接推导直接推导直接推导直接推导或称或称或称或称直接归约直接归约直接归约直接归约到到到到n nGE:EGE:EE+E|E+E|E*EE*E|(E)|i|(E)|iuui+i+i+i+E E E E =i+=i+=i+=i+E*EE*EE*EE*En n特点：只能用一次产生式替换特点：只能用一次产生式替换30推导（归约）推导（归约）p29p29n n如果如果0 0=1 1=2 2=n n，则称这个序列，则称这个序列是从是从0 0至至n n的一

38、个的一个推导推导n n用用0 0=+n n表示从表示从0 0出发，经出发，经一步或多步一步或多步推推导，可推出导，可推出n nn n用用0 0=*n n表示从表示从0 0出发，经出发，经零步或多步零步或多步推推导，可推出导，可推出n n，即，即0 0=n n或或0 0=+n nn n例如例如 E E=E*E=i*E=E*E=i*E=i*i i*i uuE=E=E=E=+i*i i*i i*i i*i 至少用一次产生式替换至少用一次产生式替换至少用一次产生式替换至少用一次产生式替换n n例如例如 E=EE=EuuE=E=E=E=*E E E E 可以不用产生式替换可以不用产生式替换可以不用产生式

39、替换可以不用产生式替换31句型句型 p36p36n n设设 G G 是一个文法，是一个文法，S S 是开始符号，是开始符号，若有若有 S=S=*，则称是，则称是文法文法G G的一个的一个句型句型uuG(E):EG(E):EG(E):EG(E):EE+E|E+E|E+E|E+E|E*EE*EE*EE*E|(E)|i|(E)|i|(E)|i|(E)|iuu例如例如例如例如 E=E=E=E=+i*E,i*E,i*E,i*E,则则则则i*Ei*Ei*Ei*E是文法是文法是文法是文法G(E)G(E)G(E)G(E)的一个句型的一个句型的一个句型的一个句型uu E=E=E=E=+i*i,i*i,i*i,i

40、*i,则则则则i*ii*ii*ii*i是文法是文法是文法是文法G(E)G(E)G(E)G(E)的一个句型的一个句型的一个句型的一个句型n n句子句子 完全由完全由终结符终结符组成的句型组成的句型uu例如例如例如例如 E=E=E=E=+i*i,i*i,i*i,i*i,则则则则i*ii*ii*ii*i是文法是文法是文法是文法G(E)G(E)G(E)G(E)的一个句子的一个句子的一个句子的一个句子n n合法句子的生成合法句子的生成uu从从从从出出出出发发发发反反反反复复复复推推推推导导导导，每每每每次次次次得得得得到到到到一一一一个个个个句句句句型型型型，最最最最终终终终得到得到得到得到句子句子句子

41、句子32n n例例:文法文法G(E)G(E)为：为：E E+E|E*E|(E)|iE E+E|E*E|(E)|in n表达式表达式 (i*i+i)(i*i+i)的生成的生成 uu E =(E)E =(E)uu =(E+E)=(E+E)uu =(E*E+E)=(E*E+E)uu =(i*E+E)=(i*E+E)uu =(i*i+E)=(i*i+E)uu =(i*i+i)(i*i+i)句型和句子生成举例句型和句子生成举例句型句型句子句子33n n例例:文法文法GEGE为：为：E E+E|E*E|(E)|iE E+E|E*E|(E)|in n表达式表达式 i+i*i i+i*i 的生成的生成 BEG

42、INBEGIN uuE =E+E E =E+E uu =i+E =i+E uu =i+E*E =i+E*E uu =i+i*E =i+i*E uu =i+i*i =i+i*i句型和句子生成练习句型和句子生成练习句型句型句子句子34文法文法G G描述的语言描述的语言 p36p36n n由文法产生的所有句子的集合由文法产生的所有句子的集合uu()+&T T T T*n n文法文法G G的作用的作用以有限的规则描述无限的语言现象以有限的规则描述无限的语言现象以有限的规则描述无限的语言现象以有限的规则描述无限的语言现象uu有限有限有限有限 产生式集合产生式集合产生式集合产生式集合uu 终结符集合终结符

43、集合终结符集合终结符集合uu 非终结符集合非终结符集合非终结符集合非终结符集合uu无限无限无限无限 由开始符号导出的句子由开始符号导出的句子由开始符号导出的句子由开始符号导出的句子n nGE:EGE:EE E+E|E E|E*E|E|(E E)|i iuu文法文法文法文法G G G G所描述的语言：含有所描述的语言：含有所描述的语言：含有所描述的语言：含有+、*和括号的算术表达式和括号的算术表达式和括号的算术表达式和括号的算术表达式35n n例例3.1 3.1 文法文法G=(VG=(VN N,V,VT T,P,S),P,S)uu其中其中其中其中V V V VN N N N=S,V=S,V=S,

44、V=S,VT T T T=0,1,P=S0S1,S01=0,1,P=S0S1,S01=0,1,P=S0S1,S01=0,1,P=S0S1,S01uu简写文法简写文法简写文法简写文法GSGSGSGS：S0S1 S01S0S1 S01S0S1 S01S0S1 S01文法和语言课堂练习文法和语言课堂练习 p35-36n n文法文法G G描述的语言描述的语言 uu S=01 (S=01 (最短的句子最短的句子)uu S=0 S=0S S1 1 =0 =00 0S S1 11 1 =00 =000 0S S1 11111 =0=0n-1n-1S S1 1n-1n-1=0=0n n1 1n nuu L(G

45、)=0 L(G)=0n n1 1n n|n=1|n=136文法的等价性文法的等价性 p38p38n n文法的等价文法的等价文法的等价文法的等价 若若若若L(GL(GL(GL(G1 1 1 1)=L(G)=L(G)=L(G)=L(G2 2 2 2)，则称文法，则称文法，则称文法，则称文法G G G G1 1 1 1和和和和G G G G2 2 2 2是等价的是等价的是等价的是等价的 （它们产生的句子集合相同）（它们产生的句子集合相同）（它们产生的句子集合相同）（它们产生的句子集合相同）n n文法文法文法文法G G G G1 1 1 1E:EE+E|E*E|(E)|iE:EE+E|E*E|(E)|

46、iE:EE+E|E*E|(E)|iE:EE+E|E*E|(E)|i n n文法文法文法文法G G G G2 2 2 2E:EE+T|TE:EE+T|TE:EE+T|TE:EE+T|T TT*F|F TT*F|F TT*F|F TT*F|F F(E)|i F(E)|i F(E)|i F(E)|in n因为因为因为因为L(GL(GL(GL(G1 1 1 1)=L(G)=L(G)=L(G)=L(G2 2 2 2),),),),所以文法所以文法所以文法所以文法G G G G1 1 1 1和和和和G G G G2 2 2 2是等价的。是等价的。是等价的。是等价的。章节目录章节目录章节目录章节目录373.

47、4 3.4 文法的类型文法的类型(Chomsky p38)(Chomsky p38)通过通过对产生式施加不同的限制对产生式施加不同的限制，将文法分为，将文法分为四种类型四种类型n n0 0型型文法文法 短语文法短语文法 phrase structure grammarphrase structure grammar 对任一产生式对任一产生式对任一产生式对任一产生式，都有，都有，都有，都有(N N N NT T T T)*且且且且至少含有一个非终结符至少含有一个非终结符至少含有一个非终结符至少含有一个非终结符，(N N N NT T T T)*限制最少，描述能力最强限制最少，描述能力最强限制最少

48、，描述能力最强限制最少，描述能力最强uu例如例如例如例如 aABcDaABcDaABcDaABcD38文法的类型文法的类型 p38p38n n1 1型型文法文法 上下文有关文法上下文有关文法 context sensitive grammarcontext sensitive grammar 对任一产生式对任一产生式，都有，都有 仅仅仅仅除外，并且不出现在其他产生式除外，并且不出现在其他产生式 的右部的右部uu例如例如例如例如 SaSBA AASaSBA AASaSBA AASaSBA AA ABABABAB39文法的类型文法的类型 p38p38n n2 2型型文法文法 上下文无关文法上下文无

49、关文法 context free grammarcontext free grammar 对任一产生式对任一产生式对任一产生式对任一产生式，都有都有都有都有N N N N，(N N N NT T T T)*uu例如例如例如例如 EE+T|TEE+T|TEE+T|TEE+T|Tuu足以描述大多数程序设计语言语法特征足以描述大多数程序设计语言语法特征足以描述大多数程序设计语言语法特征足以描述大多数程序设计语言语法特征402 2型文法描述语法单位举例型文法描述语法单位举例n nG G2 2(E):E E+T|T(E):E E+T|T T T*F|F T T*F|F F(E)|i F(E)|in n

50、ififthenthen|if|ifthenthenelseelse|41文法的类型文法的类型 p39p39n n3 3型文法型文法 正规文法正规文法 regular grammarregular grammaruu右线性文法右线性文法右线性文法右线性文法 对任一产生式的形式都为对任一产生式的形式都为对任一产生式的形式都为对任一产生式的形式都为或或或或 其中，其中，其中，其中，N N N N，T T T T*（可为（可为（可为（可为）uu左线性文法左线性文法左线性文法左线性文法 对任一产生式的形式都为对任一产生式的形式都为对任一产生式的形式都为对任一产生式的形式都为或或或或 其中，其中，其中，