文法和语法.ppt
《文法和语法.ppt》由会员分享,可在线阅读,更多相关《文法和语法.ppt(64页珍藏版)》请在三一办公上搜索。
1、第2章文法和语言,文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法的句型分析有关文法实用中的一些说明,2.1语言,语言是由句子组成的集合,是由一组记号所构成的集合。汉语-所有符合汉语语法的句子的全体英语-所有符合英语语法的句子的全体程序设计语言-所有该语言的程序的全体研究语言:每个句子构成的规律每个句子的含义每个句子和使用者的关系,研究程序设计语言:每个程序构成的规律 每个程序的含义 每个程序和使用者的关系语言研究的三个方面:语法 Syntax 语义 Semantics 语用 Pragmatics,语法-表示构成语言句子的各个记号之间的组合规律语义-表示按照各种表示方法所表
2、示的各个记号的特定含义。(各个记号和记号所表示的对象之间的关系)语用-表示在各个记号所出现的行为中,它们的来源、使用和影响。,如果不考虑语义和语用,即只从语法这一侧面来看语言,这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实:语言的所有规则只以什么符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,2.2形式语言,以自然语言为例:,“我是大学生”是否是该语言的句子?,句子:=主语谓语主语:=代词|名词代词:=你|我|他名词:=王明|大学生|工人|英语谓语:=动词直接宾语动词:=是|学习直接宾
3、语:=代词|名词,用 EBNF 描述一种语言:,文法,句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生,句子:=主语谓语主语:=代词|名词代词:=你|我|他名词:=王明|大学生|工人|英语谓语:=动词直接宾语动词:=是|学习直接宾语:=代词|名词,句子:=主语谓语主语:=代词|名词代词:=你|我|他名词:=王明|大学生|工人|英语谓语:=动词直接宾语动词:=是|学习直接宾语:=代词|名词,下列是否是句子:我是大学生王明是大学生王明学习英语他学习英语你是工人,下列是否是句子:我大学生是大学生是王明英语学习王明大学生学习他工人是英语,2.3符号和符号串,字母表:
4、元素的非空有穷集合。(符号集)符号:字母表中的元素。,例如:汉语的字母表中包括汉字、数字及标点符号等。PASCAL语言的字母表是由字母、数字、若干专用符号及BEGIN、IF之类的保留字组成。,符号串:由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串(没有符号的符号串)是上的符号串 2.若x是上的符号串,a是的元素,则xa是上的符号串 3.y是上的符号串,当且仅当它可以由1和2导出。例如:=a,b,a,b,aa,ab,aabba,都是上的符号串,例:=0,1,0,1,00,01,11,1001110等都是上的符号串.,例:=a,b,c上的符号串有:a,b,c,ab,ba,a
5、aca,acaa等.,注意:符号串中的符号排列是有顺序的.可以用字母表示符号串,如 x=aaca,如果 z=xy 是一符号串,那么:x 是 z 的头,y 是 z 的尾;如果 x 非空,那么 y 是固有尾;如果 y 非空,那么 x 是固有头。,例:设 z=abc,那么z 的头是:,a,ab,abc(除 abc 外都是固有头)z 的尾是:,c,bc,abc(除 abc 外都是固有尾),几种表示法(x,z是符号串,t是符号):z=xx 是符号串 z 的头z=xx 在符号串z 中某处出现z=t符号 t 是 符号串 z 的第一个符号,符号串的运算符号串的长度:符号串中符号的个数.符号串s的长度记为|s|
6、。的长度为0连接:符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy例 x=ST,y=abu 则 xy=STabu|x|=2,|y|=3,|xy|=5 x=x=x,方幂:符号串x自身连接n次得到的符号串 xxxx(n个x)定义为 xn x0=,x1=x,x2=xx,x3=xxx x=AB,则 x0=,x1=AB,x2=ABAB,x3=ABABAB对于 n0,xn=xxn-1=xn-1x,符号串集合:若集合A中一切元素都是某字母表上的符号串,则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为AB=xy|xA且yB若 集合A=a,b B=c,d则 AB=ac,ad,bc,
7、bd A=A=A(x=x=x)使用*表示上的所有有穷长的串(包括)的集合。*称为的闭包。从*中除去得到的集合记为+。+称为的正闭包。,*=0 1 2 n+=1 2 n*=0+=*=*+=*-,例:设=0,1,则*=,0,1,00,01,10,11,000,001,010,例:设=a,b,则*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,文法和语言的形式定义,规则(重写规则、产生式或生成式),是形如或=的(,)有序对,其中是某字母表V的正闭包V+中的一个符号,是V*中的一个符号。(V+,V*)称为规则的左部(或生成式的左部)。称为规则的右
8、部(或生成式的右部)。,文法G定义为四元组(VN,VT,P,S)VN:非终结符集VT:终结符集P:产生式(规则)集合S:开始符号(识别符号)VN、VT 和 P 是非空有穷集。S 至少在一条规则中作为左部出现。VNVT=,SVNV=VNVT,称为文法G的字母表(字汇表),2.4文法的定义,例3.1 文法G=(VN,VT,P,S)VN=S,VT=0,1 P=S0S1,S01 S为开始符号,例3.2 文法G=(VN,VT,P,S)VN=标识符,字母,数字VT=a,b,c,x,y,z,0,1,9P=a,z 0,9 S=,习惯上只将产生式写出。并有如下约定:第一条产生式的左部是开始符号用尖括号括起的是非
9、终结符,否则为终结符。或者大写字母表示非终结符,小写字母表示终结符G可写成GS,其中S是开始符号,例3.1 文法G=(VN,VT,P,S)VN=S,VT=0,1 P=S0S1,S01 S为开始符号,可写成:G:S0S1 S01,或写成:GS:S0S1 S01,2.5推导的定义,一、直接推导“”是文法G的产生式,,V*,若有v,w满足:v=,w=,则说:v(应用规则)直接产生w或说:w是v的直接推导或说:w直接归约到v记作 v w,例:G:S0S1,S01直接推导:0S10011(v=0S1,w=0011,使用规则S01,=0,=1)S 0S1(v=S,w=0S1,使用规则S0S1,=,=)0S
10、100S11(v=0S1,w=00S11,使用规则S0S1,=0,=1),例 文法G=(VN,VT,P,S)VN=标识符,字母,数字VT=a,b,c,x,y,z,0,1,9P=a,z 0,9 S=,指出下面直接推导所使用的规则:abc abc5,例:G:S0S1,S010S1 00S11 000S111 00001111 即 0S1 00001111也记作 0S1 00001111,若存在v=w0 w1.wn=w,(n0)则称v推导出(产生)w(推导长度为n),或称w归约到v.记作 v w若有v w,或v=w,若存在v=w0 w1.wn=w,(n=0)则记为v w,+,+,+,*,+,*,*,
11、二、,和,三、最左(最右)推导:在推导的任何一步,其中、是句型,都是对中的最左(右)非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型,例:GS:SaASASbAASSSaAba,SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa,四、语法树,用于描述上下文无关文法的句型推导的直观方法。,例:GS:SaASASbAASSSaAba,S a A S S b A a a b a,句型aabbaa的语法树(推导树),叶子结点:树中没有子孙的结点。从左到右读出推导树的叶子标记,所得
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 文法 语法
链接地址:https://www.31ppt.com/p-2432895.html