第3章-文法和语言

第3章:文法和语言的概念和表示3.0概述3.1形式语言基础3.2文法的直观理解3.3文法和语言的定义3.4文法的类型3.5语法树与二义性3.6句型的分析3.0概述用高级语言编程比用低级语言方便，但要解决两个问题：(1)计算机怎样懂得高级语言程序，这就需要一个翻译程序实现从源程序到目标程序的转换。(2)用什么方法来精确定义高级语言，即怎样精确描述高级语言。要构造一个编译程序，应深刻理解被编译的源语言的结构（即词法和语法）及其含义（即语义），同时要弄清源语言的语法规则和语义规则是采用什么理论或什么方法来描述的。本章目的为语言的语法描述寻求工具，该工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）形式工具----形式语言抽象地定义为一个数学系统。“形式”----：语言的所有规则只以符号串能出现的方式来陈述。语言概述语言是由句子组成的集合，或说是由一组符号串所构成的集合。汉语——所有符合汉语语法的句子的全体英语——所有符合英语语法的句子的全体程序设计语言——所有该语言的程序的全体每个句子构成的规律研究语言每个句子的含义每个句子和使用者的关系研究程序设计语言每个程序构成的规律每个程序的含义每个程序和使用者的关系语言研究的三个方面语法Syntax语义Semantics语用Pragmatics语法——表示构成语言句子的各个记号之间的组合规律。语义——表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用——表示在各个记号所出现的行为中，它们的来源、使用和影响。每种语言具有两个可开始的特性，即语言的形式和该形式相关联的意义。语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。任何语言均可看作一个集合。这个集合中的每个元素都是在一定符号集（字母表）上的一个符号串。对于自然语言来说，它们是定义在某个字母表上的句子的集合。对于程序语言来说，它们也是定义在某个字母表上的句子的集合。这里的句子，就是一个源程序。通常，源程序是由关键字、标识符、常数、运算符以及一些界限符组成。这些语法成分统称为单词或单词符号。单词符号是语言中具有独立意义的最基本单位。语言的单词符号是由词法规则所确定的，即词法规则规定了单词符号的形成规则。当我们表述一种语言时，无非是要说明这种语言的句子，如果语言只含有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，就存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语。“我是大学生”。是汉语的一个句子用语法来描述：〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉｜〈名词〉〈代词〉∷=我｜你｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉有了一组规则以后，按照如下方式用它们导出句子：开始去找∷=左端的带有〈句子〉的规则并把它由∷=右端的符号串代替，这个动作表示成：〈句子〉〈主语〉〈谓语〉，然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应规则的∷=右端代替之。比如，选取了〈主语〉，并采用规则〈主语〉∷=〈代词〉，那么得到：〈主语〉〈谓语〉〈代词〉〈谓语〉，重复做下去，句子：“我是大学生”的全部动作过程是：〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。3.1形式语言基础基本概念:一、字母表和符号串1.字母表：符号的非空有限集合例：={a，b，c}2.符号：字母表中的元素例：a，b，c3.符号串：符号的有穷序列例：a,aa,ac,abc，..特别地,空符号串：无任何符号的符号串(ε)符号串的形式定义有字母表，定义：（1）ε是上的符号串；（2）若x是上的符号串，且a，则ax或xa是上的符号串；（3）y是上的符号串，iff（当且仅当）y可由（1）和（2）产生。4.符号串集合：由符号串构成的集合。二、符号串和符号串集合的运算5.符号串相等：若x、y是集合上的两个符号串，则x＝yiff（当且仅当）组成x的每一个符号和组成y的每一个符号依次相等。6.符号串的长度：x为符号串，其长度|x|等于组成该符号串的符号个数。例：x＝STV，|x|=3特别地,|ε|=0例：A＝{a,b},B={c,d},AB=？8.符号串集合的乘积运算：令A、B为符号串集合，定义AB＝{xy|x∈A，y∈B}{ac，ad，bc，bd}因为εx＝xε＝x，所以{ε}A=A{ε}=A7.符号串的联接：若x、y是定义在Σ是上的符号串，且x＝XY，y＝YX，则x和y的联接xy＝XYYX也是Σ上的符号串。注意：一般xy≠yx，而εx＝xε＝x9.方幂运算：符号串集合的方幂符号串的方幂有任一符号串集合A，定义:有任一符号串X，定义:A0={ε},X0=εA1=A,X1=XA2=AA,X2=XXA3=AAA,X3=XXX……An＝An-1A=AAn-1Xn=XX…X＝AA…An个n个其中:n≥010.符号串集合的闭包运算：设A是符号串集合，定义A＋=A1∪A2∪A3∪……∪An∪……称为集合A的正则闭包。A*=A0∪A1∪A2∪A3∪……∪An∪……=A0∪A＋称为集合A的星闭包。例：A={x,y}A＋＝？A*＝？{x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}A1A2A3{ε,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}A0A1A2A3为什么对符号、符号串、符号串集合以及它们的运算感兴趣？若A为某语言的基本字符集A＝{a,b,……z,0,1,……,9,+,－,×,_/,(,),=……}B为单词集B={begin,end,if,then,else,for,……,标识符,常量,……}则BA*。语言的句子是定义在B上的符号串。若令C为句子集合，则CB*,程序C3.2文法的直观理解1.什么是文法：文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称为“语法”）。例：有一句子：“我是大学生”。这是一个在语法、语义上都正确定句子，该句子的结构（称为语法结构）是由它的语法决定的。在本例中它为“主谓结构”。如何定义句子的合法性？•有穷语言•无穷语言2.语法规则：我们通过建立一组规则（产生式），来描述句子的语法结构。规定用“::=”表示“由……组成”。句子::=主语谓语主语::=代词|名词代词::=你|我|他名词::=王民|大学生|工人|英语谓语::=动词直接宾语动词::=是|学习直接宾语::=代词|名词3.由产生式推导句子：句子=主语谓语主语谓语=代词谓语…………这种推导一直进行下去，直到所有带的符号都由终结符号替代为止。有了一组产生式之后，可以按照一定的方式用它们去推导或产生句子。推导方法：从一个要开始的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。句子主语谓语代词谓语我谓语我动词直接宾语我是直接宾语我是名词我是大学生句子::=主语谓语主语::=代词|名词代词::=你|我|他名词::=王民|大学生|工人|英语谓语::=动词直接宾语动词::=是|学习直接宾语::=代词|名词推导方法：从一个要开始的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。例：给定一组语法规则，考察一个句子：“我是大学生”的推导过程。例：有一英语句子：Thebigelephantatethepeanut.句子::=主语谓语主语::=冠词形容词名词冠词::=the形容词::=big名词::=elephant谓语::=动词宾语动词::=ate宾语::=冠词名词名词::=peanut句子=主语谓语=冠词形容词名词谓语=the形容词名词谓语=thebig名词谓语=thebigelephant谓语=thebigelephant动词宾语=thebigelephantate宾语=thebigelephantate冠词名词=thebigelephantatethe名词=thebigelephantatethepeanut句子::=主语谓语主语::=冠词形容词名词冠词::=the形容词::=big名词::=elephant|peanut谓语::=动词宾语动词::=ate宾语::=冠词名词Thebigelephantatethepeanut.上述推导可写成句子=thebigelephantatethepeanut+说明：(1)有若干语法成分同时存在时，我们总是从最左的语法成分进行推导，这称之为最左推导，类似的有最右推导（一般推导）。(2)从一组产生式可推出不同的句子，如以上产生式还可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它们在语法上都正确，但在语义上都不正确。所谓文法是在形式上对句子结构的定义与描述，而未涉及语义问题。4.语法树：我们用语法树来描述一个句子的语法结构。句子主语谓语冠词形容词名词动词宾语冠词名词Thebigelephantatethepeanut语法成分（在形式语言中又称“非终结符”）单词符号（在形式语言中又称“终结符号”)3.3.1文法的定义3.3文法和语言的形式定义定义1:文法G=（VN，VT，P，Z）VN：非终结符号集VT：终结符号集P：产生式或规则的集合Z：开始符号（识别符号）Z∈VNV＝VN∪VT称为文法的字汇表产生式：U::xU∈VN,x∈V*其中:①产生式：产生式是一个有序对(U,x),通常写为:U::x或Ux；|U|=1|x|0②非终结符号：出现在产生式的左部,且能推出符号或符号串的那些符号。其全体构成非终结符号集，记为VN。③终结符号：不出现在产生式的左部,且不能推出符号或符号串的那些符号。其全体构成终结符号集，记为VT。P={无符号整数→数字串；数字串→数字串数字；数字串→数字；数字→0；数字→1；…………数字→9；}Z=无符号整数；例：无符号整数的文法：G[无符号整数]=（VN，VT，P，Z）VN＝{无符号整数,数字串,数字}VT={0,1,2,3,……9}几点说明：产生式左边符号构成集合VN，且Z∈VN有些产生式具有相同的左部，可以合在一起例、无符号整数→数字串；数字串→数字串数字|数字；数字→0|1|2|3|……|9文法的BNF表示给定一个文法