课件及课后答案第3章文法和语法lly

1、第3章文法和语言考查重点基本概念 ： 文法；推导/归约；句型；句子；语言；文法的二义性；文法递归；语法树；短语；直接短语；句柄；正规文法；上下文无关文法。基本方法构造句型的推导/归约，规范推导/规范归约画出指定句型的语法树判别文法的二义性给出句型的短语、直接短语、句柄。文法与语言的互求（较简单）1、语言语言是由句子组成的集合，是由一组记号所构成的集合。汉语-所有符合汉语语法的句子的全体英语-所有符合英语语法的句子的全体程序设计语言-所有该语言的程序的全体研究语言 ：每个句子构成的规律每个句子的含义每个句子和使用者的关系3.1 语言与文法的直观概念研究程序设计语言及研究的三个方面： 每个程序构成

2、的规律（语法 Syntax）每个程序的含义（语义 Semantics）每个程序和使用者的关系（语用 Pragmatics）语言三个方面定义：语法 - 表示构成语言句子的各个记号之间的组合规律语义 - 表示按照各种表示方法所表示的各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用 -表示在各个记号所出现的行为中，它们的来源、使用和影响。以自然语言为例（用 EBNF 描述一种语言：）补讲：终端符与非终端符思考：“我是大学生”是否是该语言的句子？句子:= 主语谓语主语:= 代词|名词代词:= 你 | 我 | 他名词:= 王明 | 大学生 | 工人 | 英语谓语:= 动词直接宾语动词:=

3、 是 | 学习直接宾语:= 代词|名词2、文法文法：仅仅涉及语言句子的结构描述。句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生思考： “”的含义？“我大学生是” 与“大学生是王明”是句子?句子:= 主语谓语主语:= 代词|名词代词:= 你 | 我 | 他名词:= 王明 | 大学生 | 工人 | 英语谓语:= 动词直接宾语动词:= 是 | 学习直接宾语:= 代词|名词语法规则（文法）3、程序设计语言与文法关系：一个程序设计语言是一个记号系统，如自然语言一样，由语句组成，完整的定义应包含语法与语义两个方面。语法规定了语句形成的规则，（哪些符号序列是合法的，而与

4、其含义无关）；语义不仅要限定语法规则（静态），而且要表明程序要做什么（动态）。文法是阐述语法规则的工具，是形式语言理论基础。为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）形式工具-形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。字母表：元素的非空有穷集合。（符号集）符号：字母表中的元素。例如：汉语的字母表中包括汉字、数字及标点符号等。C语言字母表是由字母、数字、若干专用符号及保留字组成。3.2 符号和符号串1、符号例如： =0,1,0,1,00,01,11,1001110等都是上的符号串.注意

5、：符号串中的符号排列是有顺序的.可以用字母表示符号串，如 x=aaca1）符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。空符号串(没有符号的符号串)是上的符号串 若x是上符号串,a是的元素,则xa和ax是上符号串 y是上的符号串,当且仅当它可以由1和2导出。2、符号串2）串的头与尾如果 z = xy 是一符号串，那么：x 是 z 的头，y 是 z 的尾；如果 x 非空，那么 y 是固有尾；如果 y 非空，那么 x 是固有头。例：设 z = abc, 那么z 的头是： ,a ,ab , abc（固有头呢？）z 的尾是： ,c ,bc , abc（固有尾呢？）3）串的几种表示法

6、（x,z是符号串,t是符号）：z = xx 是符号串 z 的头z = xx 在符号串z 中某处出现z = t符号 t 是 符号串 z 的第一个符号3、符号串的运算1）符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。 的长度为02）连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy例： x=ST,y=abu 则 xy=STabu |x|=2,|y|=3,|xy|=5 x = x= x3）方幂：符号串x自身连接n次得到的符号串 xxxx(n个x)定义为 x n x0=, x1=x, x2=xx, x3=xxx x=AB, 则 x0=, x1=AB, x2=ABAB,

7、 x3=ABABAB对于 n0, x n = xxn-1 = xn-1x 4）符号串集合：若集合A中一切元素都是某字母表上的符号串，则称A为字母表上的符号串集合。* = 0 1 2 n + = 1 2 n * = 0 + = * = * + = * -例：设=a,b，则 *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,5）两个符号串集合A和B的乘积定义为AB =xy|xA且yB 若 集合A=a,b B = c,d 则 AB =ac,ad,bc,bd A = A = A (x = x= x)6）使用 * 表示上的所有有穷长的串（包括）的

8、集合。 *称为的闭包。7）从*中除去得到的集合记为+ 。 +称为的正闭包。1、规则（重写规则、产生式或生成式）： 是形如或=的（，）有序对，其中是某字母表V的正闭包V+中的一个符号，是V*中的一个符号。（V+，V* why?) 称为规则的左部(或生成式的左部)。 称为规则的右部(或生成式的右部)。例：句子:= 主语谓语主语:= 代词|名词代词:= 你 | 我 | 他3.3 文法和语言的形式定义2、文法G定义为四元组（VN，VT，P，S）元素说明：VN ：非终结符集VT ：终结符集P：产生式（规则）集合S：开始符号（识别符号）VN、VT 和 P 是非空有穷集。S 至少在一条规则中作为左部出现。V

9、NVT= ， SVNV=VNVT，称为文法G的字母表（字汇表）例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=思考： C语言的标识符（变量命名）如何用文法定义？文法习惯上只将产生式写出。并有如下约定：第一条产生式的左部是开始符号用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符G可写成GS，其中S是开始符号例3.1 文法G=（VN，VT，P，S）VN =

10、S , VT = 0, 1 P= S0S1, S01 S为开始符号可写成： G：S0S1 S01或写成： GS：S0S1 S013、推导的定义直接推导“”是文法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，=，= ）0S100S11 （v=0S1，w=00S11，使用规则？）例 文法G=（VN，VT，P，S）VN =标识符，字母，数字VT =

11、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 w+*+*+*和+*和4、文法的句型、句子的定义句型：设GS是一文法，如果符号串x是从识别符号推导出来的，即S x，则称x是文法GS的句型。句子：x仅由终结符号组成（即S

12、 x，且xVT*），则称x是GS的句子。例：G： S0S1， S01S 0S1 00S11 000S11100001111*思考：文法的句型与句子的关系？文法G能得到哪些句子？ 5、语言的定义：由文法G生成的语言记为L(G),它是文法G的一切句子的集合: 即L(G)=x|S x，其中S为文法的开始符号，且x VT* 例：G： S0S1， S01 L(G)=0n1n|n1*6、文法的等价：若L（G1）=L（G2），则称文法G1和G2是等价的。课堂作业：P44 2思考：文法G1A：A0R A01 RA1的语言？3.4 文法的类型Chomsky将文法分四类（对产生式施加不同限制 ）：0型文法（短语文

13、法）：对任一产生式，都有(VNVT)+且至少含一个非终结符， (VNVT)*1型文法（上下文有关文法）：对任一产生式，都有|， 仅仅 A除外。2型文法（上下文无关文法） ：对任一产生式，都有VN ， (VNVT)*3型文法（正规文法）：任一产生式的形式都为AaB或Aa，AVN ，BVN ，aVT (右线性文法)ABa或Aa，AVN ，BVN ，aVT (左线性文法)思考：四种文法之间的关系？四种文法之间的逐级“包含”关系2型文法1型文法0型文法3型文法例：判断下列文法的类型1： 文法GS： SaSBE SaBE EBBE aBab / aBbab ？ bBbb bEbe eEee2： 文法GS

14、： SaB|bA Aa|aS|bAA Bb|bS|aBB /B ？3: 文法GS： S0A|1B|0 A0A|1B|0S B1B|1|0 / BB1|1|0 ？文法和语言0型文法( PSG )产生的语言称为0型语言1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CF L ） 3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言正则（正规）语言（ RL ）思考：文法与语言的关系？ 3.5 上下文无关文法及其语法树1、上下文无关文法有足够的能力描述现今程序设计语言的语法结构

15、。 注：无特殊说明，“文法”均指上下文无关文法算术表达式语句赋值语句条件语句读语句例：算术表达式文法表示（i为变量）G=(E, +,*,i,(,), P, E P:E iE E+EE E*EE (E)例：赋值语句文法表示 i = E例：条件语句文法表示 ifthen | ifthenelse 思考：是上下文无关文法？文法的VN,VT, P, S ?2、上下文无关文法的语法树用于描述上下文无关文法的句型推导的直观方法 例: GS:SaASASbAASSSaAba能得到句型aabbaa？ S a A S S b A a a b a句型aabbaa的语法树（推导树）叶子结点：树中没有子孙的结点。从左

16、到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。推导过程中施用产生式的顺序 例: GS:SaASASbAASSSaAba S a A S S b A a a b a句型aabbaa的语法树（推导树）SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换。最右推导被称为规范推导。由规范推导所得的句型称为规范句型 例: GS:SaASASbAASSSaAbaSaASaAaaSbAaa

17、SbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa思考：最右推导的逆过程？ 一个句型是否对应唯一的一棵语法树？问题：一个句型是否对应唯一的一棵语法树？例：GE:E iE E+EE E*EE (E)思考：构造句型 i*i+i语法树？ E E + E E * E i i i E E * E i E + E i i句型 i*i+i 的两个不同的最左推导：推导1：E E+E E*E+E i*E+E i*i+E i*i+i推导2：E E*E i*E i*E+E i*i+E i*i+i二义性文法二义性： 若一个文法存在某个句子对应两

18、棵不同的语法树，则称这个文法是二义的。（或者，若一个文法存在某个句子有两个不同的最左（右）推导）语言先天二义： 产生某上下文无关语言的每一个文法都是二义的。说明：判定任何文法或语言的二义性是不可解的。但可以为无二义性寻找一组充分条件。例：二义文法改造为无二义文法（如：i*i+i的推导）GE: E i GE： E T|E+T E E+E T F|T*F E E*E F （E）|i E (E) 规定优先顺序和结合律（第6章）3.6 句型的分析句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。分析

19、算法可分为：自上而下分析法：从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。 两种方法反映了两种不同的语法树的构造过程自上而下的语法分析例：文法G：S cAd A ab A a识别输入串 w = cabd 是否该文法的句子推导过程：S cAd cabd思考：此种分析方法的关键是什么？自下而上的语法分析例：文法G：S cAd A ab A a识别输入串 w = cabd 是否该文法的句子。规约过程：S cAd cabd思考：此种分析方法的关键是什么？句型分析的有关问题1）如何选择使用哪个产生式进行推导？

20、假定要被代换的最左非终结符号是V，且有n条规则：VA1|A2|An，那么如何确定用哪个右部去替代V？2）如何识别可归约的串？在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”短语、直接短语、句柄的定义：文法GS， 是G的一个句型， 如果：S A且A ， 则称是句型相对于非终结符A的短语。 若有A 则称是句型相对于规则A的直接短语（或简单短语）。 一个句型的最左直接短语称为该句型的句柄。*+例 文法：GE：EE+T|T TT*F|F F(E)|a1|a2|a3求句型：a1+a2*a3的短语，直接短语与句柄？求解方式：定义或

21、语法树来判定.例 文法：GE：EE+T|T TT*F|F F(E)|a句型：a1+a2*a3短语：a1 , a2 , a3 , a2*a3 , a1+a2*a3 直接短语：a1 , a2 , a3句柄：a1思考：+是短语吗？a1 + a2是短语？F*a3是短语？语法树中句型,短语和句柄(1)每一句型都有一棵语法树，每个语法树的所有有序叶子组成一句型（句子？）。(2)每棵子树的所有叶子组成短语，每棵直接子树的所有叶子组成直接短语，最左直接子树的叶子组成句柄（直接子树？一层分支） 思考：句型的a1+T*F的短语？注：若语法树不易判时，可结合定义判定！3.8有关文法实用中的一些说明1、有关文法的实用限制 （文法中不得含有有害规则和多余规则）有害规则：形如UU的产生式。引起文法二义性（why）。多余规则：文法中任何句子推导都不会用到的规则。文法中某些非终结符不在任何规则的右部出现（开始符号除外），该非终结符称为不可到达的文法中某些非终结符，由它不能推出终结符号串来，称为不可终止的对于文法GS，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件：1）A（