第2章语言分析基础优秀课件.ppt

《第2章语言分析基础优秀课件.ppt》由会员分享，可在线阅读，更多相关《第2章语言分析基础优秀课件.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2章语言分析基础章语言分析基础第1页，本讲稿共22页2语言分析基础语言分析基础l文法和语言概述文法和语言概述l字母表和符号串字母表和符号串l文法和语言的形式定义文法和语言的形式定义l文法的类型文法的类型l上下文无关文法及其语法树上下文无关文法及其语法树l句型的分析句型的分析l有关文法实用中的说明有关文法实用中的说明第2页，本讲稿共22页3让计算机熟悉和掌握源语言和目标语言编译程序研究如何将源语言程序翻译为目标语言程序。编译程序研究如何将源语言程序翻译为目标语言程序。源程序目标程序编译程序2.1 2.1 文法和语言概述文法和语言概述第3页，本讲稿共22页4源程序目标程序编译程序2.1 2.1

2、 文法和语言概述文法和语言概述让计算机掌握语言的语法和语义编译程序研究如何将源语言程序翻译为目标语言程序。编译程序研究如何将源语言程序翻译为目标语言程序。第4页，本讲稿共22页5文法是对语法进行形式化描述的工具源程序目标程序编译程序2.1 2.1 文法和语言概述文法和语言概述对语法和语义进行形式化描述编译程序研究如何将源语言程序翻译为目标语言程序。编译程序研究如何将源语言程序翻译为目标语言程序。第5页，本讲稿共22页6文法的直观概念文法的直观概念语言是由句子组成的集合，是由一组语言是由句子组成的集合，是由一组符号符号所构成的所构成的集合集合。自自然然语语言言语言语言句子的集合句子的集合句子句子

3、多个单词按一定规则组成多个单词按一定规则组成单词单词多个字符按一定规则组成多个字符按一定规则组成程程序序语语言言编程语言编程语言程序的集合程序的集合程序程序多个单词按语法规则组成多个单词按语法规则组成单词单词多个字符按词法规则组成多个字符按词法规则组成2.1 2.1 文法和语言概述文法和语言概述第6页，本讲稿共22页72.1 2.1 文法和语言概述文法和语言概述语言的描述语言的描述穷举：如，穷举：如，L=I am a teacher,You are studentsL=I am a teacher,You are students文法：文法：制定有限条规则，用来产生所要描述的语言中制定有限条规

4、则，用来产生所要描述的语言中 全部句子的集合。全部句子的集合。例：例：“我是大学生我是大学生”是否是汉语的一个句子？是否是汉语的一个句子？句子句子=主语主语谓语谓语主语主语=代词代词名词名词代词代词=我我 你你 他他 名词名词=王明王明 大学生大学生 工人工人 英语英语 谓语谓语=动词动词直接宾语直接宾语动词动词=是是 学习学习直接宾语直接宾语=代词代词名词名词如何定义句子的合法性?有穷语言：只需逐一列举句子 无穷语言：使用文法定义句子结构，用适当条数的 规则把语言的全部句子描述出来。文法 是以有穷集合刻划无穷的集合的工具。第7页，本讲稿共22页8如何定义句子的合法性？有穷语言：只需逐一列举句

5、子 无穷语言：使用文法定义句子结构，用适当条数的 规则把语言的全部句子描述出来。文法 是以有穷集合刻划无穷的集合的工具。第8页，本讲稿共22页92.1 2.1 文法和语言概述文法和语言概述句子句子=主语主语谓语谓语主语主语=代词代词名词名词代词代词=我我 你你 他他 名词名词=王明王明 大学生大学生 工人工人 英语英语 谓语谓语=动词动词直接宾语直接宾语动词动词=是是 学习学习直接宾语直接宾语=代词代词名词名词句子句子主语主语谓语谓语 代词代词谓语谓语 我我谓语谓语 我我动词动词直接宾语直接宾语 我是我是直接宾语直接宾语 我是我是名词名词 我是大学生我是大学生 “我是大学生我是大学生”是汉语的

6、一个句子。是汉语的一个句子。有穷非空的规则的集合就称为文法。这些规则看成是一种元语言，用它描述汉语。文法是程序语言的产生系统文法是程序语言的产生系统“大学生是”？“我学习大学生”？句子句子=主语主语谓语谓语主语主语=代词代词名词名词代词代词=我我 你你 他他 名词名词=王明王明 大学生大学生 工人工人 英语英语 谓语谓语=动词动词直接宾语直接宾语|动词动词动词动词=是是 学习学习直接宾语直接宾语=代词代词名词名词第9页，本讲稿共22页102.1 2.1 文法和语言概述文法和语言概述规则集规则集 :=:=:=:=:=:=:=:=:=|:=|:=:=:=:=产生的语言产生的语言 Peter swi

7、ms in river,Peter swims in river,River swims in river,River swims in river,Peter swims in Peter,Peter swims in Peter,River swims in Peter River swims in Peter 产生语言的规则示例产生语言的规则示例第10页，本讲稿共22页112.1 2.1 文法和语言概述文法和语言概述l一个程序设计语言是一个记号系统。一个程序设计语言是一个记号系统。l程序设计语言研究的三个方面程序设计语言研究的三个方面语法（语法（SyntaxSyntax）：各记号之间的组

8、合规律。）：各记号之间的组合规律。语义（语义（SemanticsSemantics）：各记号的特定含义。）：各记号的特定含义。语用（语用（PragmaticsPragmatics）：各记号的来源、使用和影响。）：各记号的来源、使用和影响。例：对于赋值语句例：对于赋值语句 x:=a+bx:=a+b*c c 的非形式描述是：的非形式描述是：l 语法：赋值语句语法：赋值语句=变量变量+:=+:=+表达式表达式l 语义：先求右部，然后把结果给左部变量语义：先求右部，然后把结果给左部变量l 语用：赋值语句可用来计算和保存表达式的值语用：赋值语句可用来计算和保存表达式的值第11页，本讲稿共22页12l形式

9、化方法：形式化方法：用一整套带有严格规定的符号用一整套带有严格规定的符号 体系来描述问题的理论和方法。体系来描述问题的理论和方法。l形式语言：形式语言：一种不考虑含义的符号语言。一种不考虑含义的符号语言。l形式语言抽象地定义为一个数学系统。形式语言抽象地定义为一个数学系统。l形式语言是程序设计语言语法分析研究的基础。形式语言是程序设计语言语法分析研究的基础。2.1 2.1 文法和语言概述文法和语言概述第12页，本讲稿共22页13字母表字母表：符号的非空有限集：符号的非空有限集 例：例：=0，1 2.2 2.2 字母表和符号串字母表和符号串符号符号：字母表中的元素。例：字母表中的元素。例：0 0

10、，1 1符号串符号串：由字母表中的符号组成的任何有穷序列：由字母表中的符号组成的任何有穷序列 例：例：0,1,0,1,01,10 01,10,011,011，.空符号串空符号串：无任何符号的符号串，用：无任何符号的符号串，用表示表示符号串的长度符号串的长度：符号串：符号串S S中符号的个数中符号的个数,记为记为|S|S|。C语言的字母表：A a,b,0,1,9,+,/,(,),=，if,else,for，.不对，不对，=if,else,for,whileif,else,for,while符号就是字符，对吗？符号就是字符，对吗？第13页，本讲稿共22页14 从符号串从符号串s s的尾部删去若干个

11、的尾部删去若干个(包括包括0 0个个)符号之后所余下符号之后所余下的部分称为的部分称为s s的前缀；的前缀；从符号串从符号串s的前部删去若干个的前部删去若干个(包括包括0个个)符号之后所余下的部分称为符号之后所余下的部分称为s的后缀。的后缀。，0 0，0101及及011011都是符号串都是符号串011011的前缀的前缀，1 1，1111及及011011都是符号串都是符号串011011的后缀的后缀符号串集合符号串集合：若集合：若集合A A中的一切元素都是某字母表上的符中的一切元素都是某字母表上的符 号串，则称号串，则称A A为该字母表上的符号串集合。为该字母表上的符号串集合。例：例：=aa，b

12、b，c A=a,aa,acc A=a,aa,ac符号串的前缀和后缀符号串的前缀和后缀2.1 2.1 字母表和符号串字母表和符号串第14页，本讲稿共22页15 符号串符号串x x和和y y的的连接连接:是把是把y y的符号写的符号写在在x x的符号之后得到的符号串的符号之后得到的符号串xy xy 对于任意一个符号串对于任意一个符号串s s，有，有s=s=ss=s=s符号串的连接运算符号串的连接运算符号串的运算符号串的运算2.1 2.1 字母表和符号串字母表和符号串例如：例如：x=00 x=00，y=11y=11，则，则xy=xy=？0011第15页，本讲稿共22页16符号串自身连接符号串自身连接

13、n n次得到的符号串次得到的符号串s sn n 定义为定义为 ssssssss，包括，包括n n个个s s，称为符号串的，称为符号串的幂运算。幂运算。s s0 0=，s s1 1=s=s，s s2 2=ss=ss，设：设：s=01s=01，则：，则：s s0 0=？s s1 1=？s s2 2=？符号串的幂运算符号串的幂运算2.1 2.1 字母表和符号串字母表和符号串 010101第16页，本讲稿共22页17设设A A、B B为符号串集合，则为符号串集合，则A A和和B B的的乘积乘积定义为：定义为：ABABxy|xA,yBxy|xA,yB例如，例如，A Aa,ba,b，B=c,dB=c,d则

14、则AB=AB=？符号串集合的乘积符号串集合的乘积2.1 2.1 字母表和符号串字母表和符号串ac,ad,bc,bd ac,ad,bc,bd 第17页，本讲稿共22页18有符号串集合有符号串集合A，定义，定义A0=,A1=A,A2=AA,A3=AAA,AnAn-1A=AAn-1 ，n0例如：例如：A A0,10,1，则：，则：A A0 0=？A A1 1=？A A2 2=？A A3 3=？符号串集合的幂运算符号串集合的幂运算2.1 2.1 字母表和符号串字母表和符号串0,10,100,01,10,1100,01,10,11000,001,010,011,100,101,110,111000,00

15、1,010,011,100,101,110,111第18页，本讲稿共22页19设设A A是符号串集合，定义：是符号串集合，定义：AA1 A2 A3 An 称为集合称为集合A A的的正闭包正闭包。A*A0 A 称为集合称为集合A A的的闭包闭包。例：A=x,y A？A*=？x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,A1 A2 A3,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,A0 A1 A2 A3符号串集合的闭包运算符号串集合的闭包运算2.1 2.1 字母表和符号串字母表和符号串第19页，本讲稿共22页20的闭包的闭包*:表示表示 上的一切符号串（包括上

16、的一切符号串（包括）组成的集合）组成的集合的正闭包的正闭包+:表示表示 上的上的除除外的所有符号串组成的集合外的所有符号串组成的集合例：例：=a,b=a,b *=？+=？2.1 2.1 字母表和符号串字母表和符号串,a,b,aa,ab,ba,bb,aaa,aab,a,b,aa,ab,ba,bb,aaa,aab,a,b,aa,ab,ba,bb,aaa,aab,a,b,aa,ab,ba,bb,aaa,aab,第20页，本讲稿共22页21若：A为某语言的字母表 Aa,b,0,1,9,+,_/,(,),=if,else,for.B为单词集 B=if,else,for,则：B A*。语言的句子是定义在B

17、上的符号串。若令C为句子集合，则C B*,程序 C为什么对符号、符号串、符号串集合以及它们的运算感兴趣？为什么对符号、符号串、符号串集合以及它们的运算感兴趣？2.1 2.1 字母表和符号串字母表和符号串第21页，本讲稿共22页22 例：字母表例：字母表=a,b=a,b，则字母表，则字母表 上上的语言有：的语言有：(1)(1)*=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,(2)(2)集合集合ab,aabb,aaabbb,ab,aabb,aaabbb,a,an nb bn n,或或 表示为表示为 w|ww|w*且且w=aw=an nb bn n,n1,n1。(3)(3)集合集合a,aa,aaa,a,aa,aaa,或表示为或表示为 w|ww|w*且且w=aw=an n,n1,n1 (4)(4)是一个语言。是一个语言。(5)(5)即即 是一个语言。是一个语言。语言是由句子组成的集合，是由一组符号所构成的集合。语言是由句子组成的集合，是由一组符号所构成的集合。换言之换言之,字母表字母表 上上的一个语言是的一个语言是 上的一些符号串的集合上的一些符号串的集合(字母表字母表 上上的的每个语言是每个语言是*的一个子集的一个子集)。(列举法)(命题法)2.1 2.1 字母表和符号串字母表和符号串第22页，本讲稿共22页