《《语言分析基础》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《语言分析基础》PPT课件.ppt（22页珍藏版）》请在三一办公上搜索。
1、1,第二章 语言分析基础,2,语言分析基础,文法和语言概述字母表和符号串文法和语言的形式定义文法的类型上下文无关文法及其语法树句型的分析有关文法实用中的说明,3,让计算机熟悉和掌握源语言和目标语言,编译程序研究如何将源语言程序翻译为目标语言程序。,源程序,目标程序,编译程序,2.1 文法和语言概述,4,源程序,目标程序,编译程序,2.1 文法和语言概述,让计算机掌握语言的语法和语义,编译程序研究如何将源语言程序翻译为目标语言程序。,5,文法是对语法进行形式化描述的工具,源程序,目标程序,编译程序,2.1 文法和语言概述,对语法和语义进行形式化描述,编译程序研究如何将源语言程序翻译为目标语言程序
2、。,6,文法的直观概念,语言是由句子组成的集合，是由一组符号所构成的集合。,2.1 文法和语言概述,7,2.1 文法和语言概述,语言的描述穷举：如，L=I am a teacher,You are students,文法：制定有限条规则，用来产生所要描述的语言中 全部句子的集合。,例：“我是大学生”是否是汉语的一个句子？,句子=主语谓语主语=代词名词代词=我 你 他 名词=王明 大学生 工人 英语 谓语=动词直接宾语动词=是 学习直接宾语=代词名词,如何定义句子的合法性?有穷语言：只需逐一列举句子 无穷语言：使用文法定义句子结构，用适当条数的 规则把语言的全部句子描述出来。文法 是以有穷集合刻
3、划无穷的集合的工具。,8,如何定义句子的合法性？有穷语言：只需逐一列举句子 无穷语言：使用文法定义句子结构，用适当条数的 规则把语言的全部句子描述出来。文法 是以有穷集合刻划无穷的集合的工具。,9,2.1 文法和语言概述,句子=主语谓语主语=代词名词代词=我 你 他 名词=王明 大学生 工人 英语 谓语=动词直接宾语动词=是 学习直接宾语=代词名词,句子主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生,“我是大学生”是汉语的一个句子。,这些规则看成是一种元语言，用它描述汉语。,文法是程序语言的产生系统,“大学生是”？“我学习大学生”？,句子=主语谓语主语=代词名词
4、代词=我 你 他 名词=王明 大学生 工人 英语 谓语=动词直接宾语|动词动词=是 学习直接宾语=代词名词,10,2.1 文法和语言概述,规则集:=:=:=:=:=|:=:=,产生的语言 Peter swims in river,River swims in river,Peter swims in Peter,River swims in Peter,产生语言的规则示例,11,2.1 文法和语言概述,一个程序设计语言是一个记号系统。,程序设计语言研究的三个方面语法（Syntax）：各记号之间的组合规律。语义（Semantics）：各记号的特定含义。语用（Pragmatics）：各记号的来源、
5、使用和影响。,例：对于赋值语句 x:=a+b*c 的非形式描述是：,语法：赋值语句=变量+:=+表达式 语义：先求右部，然后把结果给左部变量 语用：赋值语句可用来计算和保存表达式的值,12,形式化方法：用一整套带有严格规定的符号 体系来描述问题的理论和方法。形式语言：一种不考虑含义的符号语言。形式语言抽象地定义为一个数学系统。形式语言是程序设计语言语法分析研究的基础。,2.1 文法和语言概述,13,字母表：符号的非空有限集 例：=0，1,2.2 字母表和符号串,符号：字母表中的元素。例：0，1符号串：由字母表中的符号组成的任何有穷序列 例：0,1,01,10,011，.空符号串：无任何符号的符
6、号串，用表示符号串的长度：符号串S中符号的个数,记为|S|。,C语言的字母表：A a,b,0,1,9,+,/,(,),=，if,else,for，.,不对，=if,else,for,while,符号就是字符，对吗？,14,从符号串s的尾部删去若干个(包括0个)符号之后所余下的部分称为s的前缀；从符号串s的前部删去若干个(包括0个)符号之后所余下的部分称为s的后缀。,，0，01及011都是符号串011的前缀，1，11及011都是符号串011的后缀,符号串集合：若集合A中的一切元素都是某字母表上的符 号串，则称A为该字母表上的符号串集合。例：=a，b，c A=a,aa,ac,符号串的前缀和后缀,2
7、.1 字母表和符号串,15,符号串x和y的连接:是把y的符号写在x的符号之后得到的符号串xy,对于任意一个符号串s，有s=s=s,符号串的连接运算,符号串的运算,2.1 字母表和符号串,例如：x=00，y=11，则xy=？,0011,16,符号串自身连接n次得到的符号串sn 定义为 ssss，包括n个s，称为符号串的幂运算。,s0=，s1=s，s2=ss，设：s=01，则：s0=？s1=？s2=？,符号串的幂运算,2.1 字母表和符号串,010101,17,设A、B为符号串集合，则A和B的乘积定义为：ABxy|xA,yB,例如，Aa,b，B=c,d则AB=？,符号串集合的乘积,2.1 字母表和
8、符号串,ac,ad,bc,bd,18,有符号串集合A，定义A0=,A1=A,A2=AA,A3=AAA,AnAn-1A=AAn-1，n0,例如：A0,1，则：A0=？A1=？A2=？A3=？,符号串集合的幂运算,2.1 字母表和符号串,0,100,01,10,11000,001,010,011,100,101,110,111,19,设A是符号串集合，定义：AA1 A2 A3 An 称为集合A的正闭包。A*A0 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,xy
9、x,xyy,A0 A1 A2 A3,符号串集合的闭包运算,2.1 字母表和符号串,20,的闭包*:表示上的一切符号串（包括）组成的集合的正闭包+:表示上的除外的所有符号串组成的集合,例：=a,b*=？+=？,2.1 字母表和符号串,a,b,aa,ab,ba,bb,aaa,aab,a,b,aa,ab,ba,bb,aaa,aab,21,若：A为某语言的字母表 Aa,b,0,1,9,+,_/,(,),=if,else,for.B为单词集 B=if,else,for,则：B A*。语言的句子是定义在B上的符号串。若令C为句子集合，则C B*,程序 C,为什么对符号、符号串、符号串集合以及它们的运算感兴趣？,2.1 字母表和符号串,22,例：字母表=a,b，则字母表上的语言有：(1)*=,a,b,aa,ab,ba,bb,aaa,aab,(2)集合ab,aabb,aaabbb,anbn,或 表示为 w|w*且w=anbn,n1。(3)集合a,aa,aaa,或表示为 w|w*且w=an,n1(4)是一个语言。(5)即 是一个语言。,语言是由句子组成的集合，是由一组符号所构成的集合。换言之,字母表上的一个语言是上的一些符号串的集合(字母表上的每个语言是*的一个子集)。,(列举法),(命题法),2.1 字母表和符号串,
