1、1第 二 讲 文 法 和 语 言文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法的句型分析有关文法实用中的一些说明2第一节 语语 言言语言语言: : 是由句子组成的集合。是由句子组成的集合。 汉语 - 所有符合汉语语法的句子的全体 英语 - 所有符合英语语法的句子的全体 程序设计语言 - 所有该语言的程序的全体 研究语言 ： 每个句子构成的规律 每个句子的含义 每个句子和使用者的关系3 研究程序设计语言： 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系 语言研究的三个方面： 语法 Syntax 语义 Semantics 语用 Pragmatics4语法 ： 表示
2、构成语言句子的各个记号之间的 组合规律 语义 ：表示按照各种表示方法所表示的各个 记号的特定含义。（各个记号和记号所 表示的对象之间的关系） 语用 ：表示在各个记号所出现的行为中，它 们的来源、使用和影响。 5第二节 文 法“我是大学生” 是否是该语言的句子？句子:= 主语谓语主语:= 代词|名词代词:= 你 | 我 | 他名词:= 王明 | 大学生 | 工人 | 英语谓语:= 动词直接宾语动词:= 是 | 学习直接宾语:= 代词|名词以自然语言为例，用 EBNF 描述一种语言：6句子 主语谓语 句子:= 主语谓语 主语:= 代词|名词 代词:= 你 | 我 | 他 名词:= 王明 | 大学生
3、 | 工人 | 英语 谓语:= 动词直接宾语 动词:= 是 | 学习 直接宾语:= 代词|名词 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生 7 句子:= 主语谓语 主语:= 代词|名词 代词:= 你 | 我 | 他 名词:= 王明 | 大学生 | 工人 | 英语 谓语:= 动词直接宾语 动词:= 是 | 学习 直接宾语:= 代词|名词下列是否是句子? 我大学生是 大学生是王明文法以有穷的集合刻画无穷的集合8第三节 符号和符号串 字母表：元素的非空有穷集合。（符号集） 符号符号：字母表中的元素。例如： 汉语的字母表中 包括汉字、数字及标点符号等。 C+语言的字母表 是由
4、字母、数字、若干专用符号及FOR、 IF之类的保留字组成。9 符号串符号串：由字母表中的符号组成的任何有穷序列 称为该字母表上的符号串。1. 空符号串(没有符号的符号串)是上的符号串。 2. 若x是上的符号串，a是的元素，则xa和ax是上的符号串 。3. y是上的符号串,当且仅当它可以由1和2导出。 例如： =a,b ,a,b,aa,ab,aabba,都是上的符号串。10例： =0,1,0,1,00,01,11,1001110 等都是上的符号串.例： =a,b,c上的符号串有：a, b, c, ab, ba, aaca, acaa 等.注意：1. 符号串中的符号排列是有顺序的.2. 可以用字母
5、表示符号串，如： x = aaca11如果 z = xy 是一符号串，那么：v x 是 z 的头(前缀)，y 是 z 的尾(后缀) ；v 如果 x 非空，那么 y 是固有尾(真后缀)；v 如果 y 非空，那么 x 是固有头(真前缀) 。例：设 z = abc, 那么z 的头是： ,a ,ab , abc（除 abc 外都是固有头）z 的尾是： ,c ,bc , abc（除 abc 外都是固有尾） 12几种表示法（x，z是符号串，t是符号）：z = x x 是符号串 z 的头z = x x 是符号串 z 的尾z = x x 在符号串z 中某处出现z = t 符号 t 是 符号串 z 的第一个符号
6、z = t 符号 t 是 符号串 z 的最后一个符号13符号串的运算 符号串的长度 ： 符号串中符号的个数。符号串s的 长度记为|s|。 的长度为0。 连 接 ： 符号串x、y的连接,是把y的符号写在x的符 号之后得到的符号串xy 例： x=ST，y=abu 则 xy=STabu |x|=2，|y|=3，|xy|=5 x = x= x14 方 幂 符号串x自身连接n次得到的符号串 xxxx(n个x)表示为 xn x0=, x1=x, x2=xx， ， xn =xx x x=AB, 则 x0=, x1=AB, x2=ABAB, x3=ABABAB 对于 n0, xn = xxn-1 = xn-1
7、x 15 符号串集合：若集合A中一切元素都是某字母表上 的符 号串，则称A为字母表上的符号串集合。 两个符号串集合A和B的乘积： 定义为 AB = AB = xyxy | x | x A A 且且 y y B B 例： 若， 集合A=a,b B = c,d 则 ，AB =ac,ad,bc,bd A = A A = A = A= A (x = x= x) 闭 包： 使用 * 表示上的所有有穷长的串（包括）的 集合。*称为的闭包。 正闭包： 从*中除去得到的集合记为+ 。 +称为的 正闭包。16* = 0 1 2 n + = 1 2 n * = 0 + = * = * + = * -例例1 1：设
8、 = 0, 1 ，则：* = ，0， 1， 00， 01， 10， 11， 000，001， 010， 例例2 2：设=a,b，则 * = ，a，b，aa，ab，ba，bb，aaa，aab， + = a，b，aa，ab，ba，bb，aaa，aab， 是非空有穷集17第四节 文法和语言的形式定义 产生式（重写规则、规则或生成式），是形如或=的（，）有序对，其中是某字母表V的正闭包V+中的一个符号串，是V*中的一个符号串。（V+，V*) 称为产生式的左部(或规则的左部)。 称为产生式的右部(或规则的右部)。18 句子:= 主语谓语 主语:= 代词|名词 代词:= 你 | 我 | 他 名词:= 王明
9、 | 大学生 | 工人 | 英语 谓语:= 动词直接宾语 动词:= 是 | 学习 直接宾语:= 代词|名词一、 文 法 的 定 义VN= . VT= . P= . S19 文 法 G：定义为四元组四元组（VN，VT，P，S），其中VN ： 非终结符集VT ： 终结符集P ： 产生式（规则）集合S ： 开始符号（起始符、识别符号） VN、VT 和 P 是非空有穷集。 S 至少在一条规则中作为左部出现。 VNVT= ， SVN ， V=VNVT-文法G的字母表（字汇表） 注：有的参考书用（VT , VN , S , P）表示文法。20 例3.1 文法G=（VN，VT，P，S） VN = S , V
10、T = 0, 1 P = S0S1, S01 S为开始符号 或写成： GS： S0S1, S01 21例3.2 文法G=（VN，VT，P，S）VN =标识符，字母，数字VT =a，b，c，x，y，z，0，1，9P = a ， ， z 0 ，, 9 S = 22 习惯上只将产生式写出。并有如下约定： 第一条产生式的左部是开始符号 用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符 G可写成GS，其中S是开始符号23 例3.4 文法 G =（VN，VT，P，S）VN = S , VT = 0, 1 P = S0S1, S01 S为开始符号 可写成： GS：S0S1
11、 S01 或写成： GS：S0S1 01注：把 “0S1” 和 “01” 称为产生式 S0S1 01 的候选式24二、 推 导 的 定 义 直接推导 “”是文法G的产生式，,V*，若有v,w满足：v=,w= ,则说：v（应用规则）直接产生w或说：w是v的直接推导直接推导，或说：w直接归约直接归约到v，记作 v w例：G： S0S1， S01直接推导： 0S1 0011 （v=0S1，w=0011，使用规则S01，=0，=1） S 0S1 （v=S，w=0S1，使用规则S0S1，=，= ） 0S1 00S11 （v=0S1，w=00S11，使用规则S0S1，=0，=1）25例 文法G=（VN，V
12、T，P，S）VN = 标识符，字母，数字 ； VT = a,b,c,x,y,z,0,1,9P = a, z 0, 9 S = 指出下面直接推导所使用的规则： abc abc526例：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+*+*和和注： 包含0步推导；而 不包含0步推导。*+ 推推 导导27例 G: abz 019 x x 1即
13、： x1 也可记作： x1 +*28三、三、 文法的句型、句子的定义文法的句型、句子的定义 句型 设GS是一文法，如果符号串x是从开始符号推导出来的，即S x，则称x是文法GS的句型。 句子 x仅由终结符号组成（即S x，且xVT*），则称x是GS的句子。例：G： S0S1， S01S 0S1 00S11 000S111 00001111*29四、四、 语语 言言 的的 定定 义义 由文法G生成的语言记为L(G)，它是文法G的全部句子的集合: L(G) = x | S x，且x VT*， 其中S为文法的开始符号 例：G： S0S1， S01 L(G) = 0n1n | n1 *30例3.3 设
14、G=(VN,VT,P,S), VN=S,B,E,VT=a,b,e, P由下列产生式组成：(1)SaSBE(2)S aBE(3)EB BE(4)aB ab(5)bB bb(6)bE be(7)eE ee*(3)(4), (5)(6), (7)31五、 文 法 的 等 价 若L(G1) = L(G2)，则称文法G1和G2是等价的。如文法G1A：A0R A01 RA1注：语言和文法的对应关系是一对多（1：n）的关系。与G2S：S0S1 S01 等价32第五节 文 法 的 类 型 通过对产生式施加不同的限制，Chomsky将文法分为四种类型（称为Chomsky 文法） 33一、文 法 的 类 型0型文
15、法：对任一产生式，都有(VNVT)+， (VNVT)* 1型文法：对任一产生式，都有|， 仅仅 S 除外 2型文法：对任一产生式，都有VN ， (VNVT)* 3型文法：任一产生式的形式都为 (1) AaB 或 Aa，其中AVN ，BVN ，aVT (右线性文法) 或 (2) ABa 或 Aa，其中AVN ，BVN ，aVT (左线性文法)至少含有一个非终结符34 1型文法：对任一产生式，都有|， 仅仅 S除外 上下文有关文法： 1A212(A在VN中，其他在V*中，) 2型文法：对任一产生式，都有VN ， (VNVT)* 上下文无关文法：A(A在VN中，在V*中，) 3型文法也叫正规文法35
16、 例：1型（上下文有关）文法 文法GS：SaSBESaBEEBBEaBabbBbbbEbeeEee36 例： 2型（上下文无关）文法 文法GS：SaB|bAAa|aS|bAABb|bS|aBB 例: 3型文法 GS： S0A|1B|0A0A|1B|0SB1B|1|037二、 文 法 和 语 言0型文法( PSG )产生的语言称为0型语言1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CF L ） 3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言或正则（正规）语言（
17、RL ）38第六节 上下文无关文法及其语法树 上下文无关文法有足够的能力描述现今程序设计语言的语法结构算术表达式语句赋值语句条件语句读语句39 算术表达式上下文无关文法表示：文法 G = (E, +,*,i,(,), P, E ） P:E iE E+EE E*EE (E) 条件语句上下文无关文法表示 if then | if then else 40一、一、 上下文无关文法的语法树上下文无关文法的语法树 用于描述上下文无关文法的句型推导的直观方法 例: GS:SaASASbAASSSaAba S a A S S b A a a b a句型aabbaa的语法树（推导树）叶子结点：树中没有子孙的结
18、点。 从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。41推导过程中施用产生式的顺序 例: GS:SaASASbAASSSaAba S a A S S b A a a b a句型aabbaa的语法树（推导树） S aAS aAa aSbAa aSbbaa aabbaa S aAS aSbAS aabAS aabbaS aabbaa S aAS aSbAS aSbAa aabAa aabbaa42 最右（最左）推导最右（最左）推导：在推导的任何一步，其中、是句型，都是对中的最右（左）非终结符进行替换 最右推导被称为规范推导规范推导。 由规范推导所得的句型称
19、为规范句型规范句型SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa 例: GS:SaASASbAASSSaAba最右推导，规范推导43 例：GE:E iE E+EE E*EE (E) 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问题：一个句型是否对应唯一的一棵语法树？44二、二、 二二 义义 文
20、文 法法 若一个文法存在某个句型对应两棵不同的语法树，则称这个文法是二义的。 或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。 产生某上下文无关语言的每一个文法都是二义的，则称此语言是先天二义的。45 判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的。但可以为无二义性寻找一组充分条件。 二义文法改造为无二义文法GE: E i GE：E T|E+T E E+E T F|T*F E E*E F （E）|i E (E) 规定优先顺序和结合律对于程序设计语言而言，文法无二义，语句分析才唯一。不存在一个算法，能在有限步
21、骤内确切的判定任给的一个文法是否为二义的。46第七节 句 型 的 分 析 句型分析句型分析 就是识别一个符号串是否为某文法的句型， 是某个推导的构造过程。句型分析是一个识别输入符号串是否为语法上正确的程序的过程。 在语言的编译实现中，把完成句型分析的程序称为分分析程序析程序或识别程序识别程序。分析算法又称识别算法识别算法。 从左到右的分析算法从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。47分析算法可分为： 自上而下分析法（推导）： 从文法的开始符号出发，反复使用各种 产生式，寻找与输入符号匹配的推导。 自下而上分析法（归约）： 从
22、输入符号串开始，逐步进行归约，直 至归约到文法的开始符号。 两种方法反映了两种不同的语法树的构造过程48一、 自上而下的语法分析 例：文法 G：S cAd A ab A a识别输入串 w = cabd 是否为该文法的句子？SSScAdcAd a b推导过程：S cAd cabd49二、 自下而上的语法分析 例：文法G：S cAd A ab A a识别输入串 w = cabd 是否该文法的句子S AA c a b d c a b d c a b d 规约过程： cabd cAd S 50三、 句型分析的有关问题1）如何选择使用哪个产生式进行推导？在自上而下的分析方法中，假定要被代换的最左非终结符
23、号是V，且有n条规则：VA1|A2|An，那么如何确定用哪个右部去替代V？ 2）如何识别可归约的串？在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”？51四、短语、直接短语、句柄的定义 文法 GS， 是G的一个句型，如果：S A且 A 则称是句型相对于非终结符A的 短语短语。 若有 A 则称是句型相对于规则A的直接短语直接短语（或（或简单短语简单短语）。一个句型的最左直接短语称为该句型的句柄句柄。*+52GE：EE+T|T TT*F|F F(E)|i句型：i1*i2+i3短语：i1 , i2 , i3 , i1*i2
24、, i1*i2+i3 直接短语：i1 , i2 , i3 句柄：i1i3i2i1*FTFE+TEFTi2+i3是句型的短语吗？53 例: GS:SaASASbAASSSaAba S a1 A S S b1 A a4 a2 b2 a3句型aabbaa的语法树（推导树）短语：a2,b2a3,a4,a2b1b2a3,a1a2b1b2a3a4直接短语：a2,b2a3,a4句柄：a254v 句型、短语和句柄(1) 每一句型都有一棵语法树，每个语法树的 叶组成一句型。(2) 每棵子树的叶组成短语，每棵直接子树的 叶组成直接短语，最左直接子树的叶组成 句柄。55五、有关文法实用中的一些说明 实际应用中需要对
25、文法提出一些限制条件-不会限制由文法所能描述的语言 需要对文法进行扩充，在上下文无关文法中允许有A的 的生式。56六、有关文法的实用限制 文法中不得含有有害规则有害规则：形如UU的产生式。会引起文法的二义性，而无任何用处。例如：GU:UU,Ua|b，句型a存在两 法： U U a U a57六、有关文法的实用限制 文法中不得含有多余规则多余规则：指文法中任何句子的推导都不会用到的规则。1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达的。2）文法中某些非终结符，由它不能推出终结符号串来，称为不可终止的。58 对于文法GS，为了保证任一非终结符A在句子推导中出现，必须满足如下两
26、个条件：1）A必须在某句型中出现。2）必须能从A推出终结符号串t来。 即 1）文法GS，对某两个符号串和： S A 2） A t ,tVT*+有害规则和多余规则体现在程序设计语言里就是语法规则错误-检查文法是否包含此类规则很必要！59七、 化 简 文 法 例：GS 1) SBe GS: SBe BAf AAe Ae 7) Df 6) CCf 2) BCe 3) BAf 4) AAe5) Ae60 上下文无关文法的定义中规则可具有形式A（A VN ）。 具有形式A的规则称为规则规则，其中AVN 某些著作和讲义中限制这种规则的出现。因为规则会使有关文法的一些讨论和证明变得复杂 两种定义的唯一差别是
27、句子在不在语言中。上下文无关文法中的规则61 如果语言L有一个有穷的描述，则L也同样有一个有穷描述。 并且可以证明，若L是上下文有关语言、上下文无关语言或正规语言，则L和L-分别是上下文有关语言、上下文无关语言和正规语言。62 定理3.1 若L是由文法G产生的语言，其中P的每一个产生式的形式均为A，其中AVN，(VN VT)*(即可能为)， 则L(G)也能由这样一种文法产生：每一个产生式或者为A形式，其中AVN， (VN VT)+(即)，或者 S且 S不出现在任何产生式右边。63 定理3.2 G是上下文有关文法，则存在另一个上下文有关文法G1，L(G)=L(G1)，且G1的开始符号不出现在G1的任何产生式的右边。 若G为上下文无关文法或正规文法，类似结论成立。
