文法和语法(lly).ppt

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

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

3、明 | 大学生 | 工人 | 英语 谓语:= 动词直接宾语 动词:= 是 | 学习 直接宾语:= 代词|名词,2、文法,文法：仅仅涉及语言句子的结构描述。,句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生 思考： “”的含义？ “我大学生是” 与“大学生是王明”是句子?,句子:= 主语谓语 主语:= 代词|名词 代词:= 你 | 我 | 他 名词:= 王明 | 大学生 | 工人 | 英语 谓语:= 动词直接宾语 动词:= 是 | 学习 直接宾语:= 代词|名词,语法规则 （文法）,3、程序设计语言与文法关系： 一个程序设计语言是一个记号系统，如自然语言一样，

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

5、保留字组成。,3.2 符号和符号串,1、符号,例如： =0,1,0,1,00,01,11,1001110等都是上的符号串.,注意： 符号串中的符号排列是有顺序的. 可以用字母表示符号串，如 x=aaca,1）符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。 空符号串(没有符号的符号串)是上的符号串 若x是上符号串,a是的元素,则xa和ax是上符号串 y是上的符号串,当且仅当它可以由1和2导出。,2、符号串,2）串的头与尾 如果 z = xy 是一符号串，那么： x 是 z 的头，y 是 z 的尾； 如果 x 非空，那么 y 是固有尾；如果 y 非空，那么 x 是固有头。,例：

6、设 z = abc, 那么 z 的头是： ,a ,ab , abc（固有头呢？） z 的尾是： ,c ,bc , abc（固有尾呢？）,3）串的几种表示法（x,z是符号串,t是符号）： z = xx 是符号串 z 的头 z = xx 在符号串z 中某处出现 z = t符号 t 是 符号串 z 的第一个符号,3、符号串的运算 1）符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。 的长度为0 2）连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy例： x=ST,y=abu 则 xy=STabu |x|=2,|y|=3,|xy|=5 x = x= x 3）方幂：符号串

7、x自身连接n次得到的符号串 xxxx(n个x)定义为 x n x0=, x1=x, x2=xx, x3=xxx x=AB, 则 x0=, x1=AB, x2=ABAB, 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

8、=xy|xA且yB 若 集合A=a,b B = c,d 则 AB =ac,ad,bc,bd A = A = A (x = x= x) 6）使用 * 表示上的所有有穷长的串（包括）的集合。 *称为的闭包。 7）从*中除去得到的集合记为+ 。 +称为的正闭包。,1、规则（重写规则、产生式或生成式）： 是形如或=的（，）有序对，其中是某字母表V的正闭包V+中的一个符号，是V*中的一个符号。（V+，V* why?) 称为规则的左部(或生成式的左部)。 称为规则的右部(或生成式的右部)。 例： 句子:= 主语谓语 主语:= 代词|名词 代词:= 你 | 我 | 他,3.3 文法和语言的形式定义,2、文法

9、G定义为四元组（VN，VT，P，S） 元素说明： VN ：非终结符集 VT ：终结符集 P：产生式（规则）集合 S：开始符号（识别符号） VN、VT 和 P 是非空有穷集。S 至少在一条规则中作为左部出现。 VNVT= ， SVN V=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,9 P= a, z 0, 9 S= 思考： C语言的标识符（变量命名）如何用文法定义？,文法习

10、惯上只将产生式写出。并有如下约定： 第一条产生式的左部是开始符号 用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符 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,3、推导的定义,直接推导“” 是文法G产生式，,V*，若v,w满足： v=, w = , 则说：v（应用规则）直接产生w 或说：w是v的直接推导 或说：w直接归约到v 记作 v w 例：G： S0S1， S01 的直接推导： 0S

11、10011 （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 =a,b,c,x,y,z,0,1,9 P= a, z 0, 9 S=,思考：指出下面直接推导所使用的规则 ？ abc abc5,例：G： S0S1， S01 0S1 00S11 000S111 00001111 即 0S1 00001111 也记作 0S1 00001111 思考： 的区别？,若存在v =w0 w1 . wn=w,

12、(n0) 则称v推导出（产生）w（推导长度为n），或称w归约到v. 记作 v w 若有v w，或v=w，则记为v w,+ ,+ ,* ,+ ,* ,4、文法的句型、句子的定义,句型：设GS是一文法，如果符号串x是从识别符号推导出来的，即S x，则称x是文法GS的句型。 句子：x仅由终结符号组成（即S x，且xVT*），则称x是GS的句子。 例：G： S0S1， S01 S 0S1 00S11 000S11100001111,* ,* ,思考： 文法的句型与句子的关系？ 文法G能得到哪些句子？,5、语言的定义：由文法G生成的语言记为L(G),它是文法G的一切句子的集合: 即L(G)=x|S x，

13、其中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型文法（短语文法）：对任一产生式，都有(VNVT)+且至少含一个非终结符， (VNVT)* 1型文法（上下文有关文法）：对任一产生式，都有|， 仅仅 A除外。 2型文法（上下文无关文法） ：对任一产生式，都有VN ， (VNVT)* 3型文法（正规文法）：任一产生式的形式都为

14、AaB或Aa，AVN ，BVN ，aVT (右线性文法) ABa或Aa，AVN ，BVN ，aVT (左线性文法) 思考：四种文法之间的关系？,四种文法之间的逐级“包含”关系,例：判断下列文法的类型 1： 文法GS： SaSBE SaBE EBBE aBab / aBbab ？ bBbb bEbe eEee,2： 文法GS： 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

15、型语言或上下文有关语言（CSL） 2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CF L ） 3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言正则（正规）语言（ RL ）,思考：文法与语言的关系？,3.5 上下文无关文法及其语法树,1、上下文无关文法有足够的能力描述现今程序设计语言的语法结构。 注：无特殊说明，“文法”均指上下文无关文法 算术表达式 语句 赋值语句 条件语句 读语句 ,例：算术表达式文法表示（i为变量）,G=(E, +,*,i,(,), P, E P:E i E E+E E E*E E (E) 例：赋值语句文法表示 i = E 例：

16、条件语句文法表示 ifthen | ifthenelse ,思考：是上下文无关文法？文法的VN,VT, P, S ?,2、上下文无关文法的语法树,用于描述上下文无关文法的句型推导的直观方法,例: GS: SaAS ASbA ASS Sa Aba 能得到句型aabbaa？,叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。,推导过程中施用产生式的顺序,例: GS: SaAS ASbA ASS Sa Aba,S a A S S b A a a b a,句型aabbaa的语法树（推导树）,SaASaAaaSbAaaSbbaaaabb

17、aa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换。 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型,例: GS: SaAS ASbA ASS Sa Aba,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,思考：最右推导的逆过程？ 一个句型是否对应唯一的一棵语法树？,问题：一个句型是否对应唯一的一棵语法树？,例：GE: E i E

18、 E+E E E*E E (E) 思考：构造句型 i*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,二义性,文法二义性： 若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。（或者，若一个文法存在某个句子有两个不同的最左（右）推导） 语言先天二义： 产生某上下文无关语言的每一个文法都是二义的。,说明：判定任何文法或语言的二义性是不可解的。但可以为无二义性寻找一组充分条件。 例：二义文法改造为无二义文法（如：i*i+i的推导） GE: E

19、i GE： E T|E+T E E+E T F|T*F E E*E F （E）|i E (E) 规定优先顺序和结合律（第6章）,3.6 句型的分析,句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。 在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。 分析算法可分为： 自上而下分析法：从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。 自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。 两种方法反映了两种不同的语法树的构造过程,自上而下的语法分析,例：文法G：S cAd A ab A a识别输入串

20、w = cabd 是否该文法的句子,推导过程：S cAd cabd 思考：此种分析方法的关键是什么？,自下而上的语法分析,例：文法G：S cAd A ab A a识别输入串 w = cabd 是否该文法的句子。,规约过程：S cAd cabd 思考：此种分析方法的关键是什么？,句型分析的有关问题,1）如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符号是V，且有n条规则：VA1|A2|An，那么如何确定用哪个右部去替代V？ 2）如何识别可归约的串？ 在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”,短语、直接

21、短语、句柄的定义： 文法GS， 是G的一个句型， 如果：S A且A ， 则称是句型相对于非终结符A的短语。 若有A 则称是句型相对于规则A的直接短语（或简单短语）。 一个句型的最左直接短语称为该句型的句柄。,* ,+ ,例 文法： GE：EE+T|T TT*F|F F(E)|a1|a2|a3 求句型：a1+a2*a3的短语，直接短语与句柄？ 求解方式：定义或语法树来判定.,例 文法： 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,思考： +是短语吗？

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