• 1. 第3章 文法和语言考查重点 基本概念 : 文法;推导/归约;句型;句子;语言;文法的二义性;文法递归;语法树;短语;直接短语;句柄;正规文法;上下文无关文法。 基本方法 构造句型的推导/归约,规范推导/规范归约 画出指定句型的语法树 判别文法的二义性 给出句型的短语、直接短语、句柄。 文法与语言的互求(较简单)
  • 2. 1、语言语言是由句子组成的集合,是由一组记号所构成的集合。 汉语--所有符合汉语语法的句子的全体 英语--所有符合英语语法的句子的全体 程序设计语言--所有该语言的程序的全体 研究语言 : 每个句子构成的规律 每个句子的含义 每个句子和使用者的关系3.1 语言与文法的直观概念
  • 3. 研究程序设计语言及研究的三个方面: 每个程序构成的规律(语法 Syntax) 每个程序的含义(语义 Semantics) 每个程序和使用者的关系(语用 Pragmatics) 语言三个方面定义: 语法 -- 表示构成语言句子的各个记号之间的组合规律 语义 -- 表示按照各种表示方法所表示的各个记号的特定含义。(各个记号和记号所表示的对象之间的关系) 语用 --表示在各个记号所出现的行为中,它们的来源、使用和影响。
  • 4. 以自然语言为例(用 EBNF 描述一种语言:)补讲:终端符与非终端符 思考:“我是大学生”是否是该语言的句子?〈句子〉::= 〈主语〉〈谓语〉 〈主语〉::= 〈代词〉|〈名词〉 〈代词〉::= 你 | 我 | 他 〈名词〉::= 王明 | 大学生 | 工人 | 英语 〈谓语〉::= 〈动词〉〈直接宾语〉 〈动词〉::= 是 | 学习 〈直接宾语〉::= 〈代词〉|〈名词〉2、文法文法:仅仅涉及语言句子的结构描述。
  • 5. 〈句子〉  〈主语〉〈谓语〉  〈代词〉〈谓语〉  我〈谓语〉  我〈动词〉〈直接宾语〉  我是〈直接宾语〉  我是〈名词〉  我是大学生 思考: “”的含义? “我大学生是” 与“大学生是王明”是句子?〈句子〉::= 〈主语〉〈谓语〉 〈主语〉::= 〈代词〉|〈名词〉 〈代词〉::= 你 | 我 | 他 〈名词〉::= 王明 | 大学生 | 工人 | 英语 〈谓语〉::= 〈动词〉〈直接宾语〉 〈动词〉::= 是 | 学习 〈直接宾语〉::= 〈代词〉|〈名词〉语法规则 (文法)
  • 6. 3、程序设计语言与文法关系: 一个程序设计语言是一个记号系统,如自然语言一样,由语句组成,完整的定义应包含语法与语义两个方面。语法规定了语句形成的规则,(哪些符号序列是合法的,而与其含义无关);语义不仅要限定语法规则(静态),而且要表明程序要做什么(动态)。 文法是阐述语法规则的工具,是形式语言理论基础。 为语言的语法描述寻求工具 工具要对程序设计语言给出精确无二义的语法描述。(严谨、简洁、易读) 形式工具--形式语言抽象地定义为一个数学系统。“形式”是指这样的事实:语言的所有规则只以什麽符号串能出现的方式来陈述。
  • 7. 字母表:元素的非空有穷集合。(符号集) 符号:字母表中的元素。例如: 汉语的字母表中包括汉字、数字及标点符号等。 C语言字母表是由字母、数字、若干专用符号及保留字组成。3.2 符号和符号串1、符号
  • 8. 例如: Σ={0,1} ε,0,1,00,01,11,1001110等都是上的符号串.注意: 符号串中的符号排列是有顺序的. 可以用字母表示符号串,如 x=aaca1)符号串:由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。 空符号串ε(没有符号的符号串)是上的符号串 若x是上符号串,a是的元素,则xa和ax是上符号串 y是上的符号串,当且仅当它可以由1和2导出。2、符号串
  • 9. 2)串的头与尾 如果 z = xy 是一符号串,那么: x 是 z 的头,y 是 z 的尾; 如果 x 非空,那么 y 是固有尾;如果 y 非空,那么 x 是固有头。例:设 z = abc, 那么 z 的头是: ε,a ,ab , abc(固有头呢?) z 的尾是: ε,c ,bc , abc(固有尾呢?)3)串的几种表示法(x,z是符号串,t是符号): z = x… x 是符号串 z 的头 z = …x… x 在符号串z 中某处出现 z = t… 符号 t 是 符号串 z 的第一个符号
  • 10. 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)方幂:符号串x自身连接n次得到的符号串 xx…xx(n个x)定义为 x n x0=ε, x1=x, x2=xx, x3=xxx x=AB, 则 x0=ε, x1=AB, x2=ABAB, x3=ABABAB 对于 n>0, x n = xxn-1 = xn-1x 4)符号串集合:若集合A中一切元素都是某字母表上的符号串,则称A为字母表上的符号串集合。
  • 11. Σ* = Σ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|xA且yB 若 集合A=a,b B = c,d 则 AB =ac,ad,bc,bd {ε}A = A {ε}= A (εx = xε= x) 6)使用 * 表示上的所有有穷长的串(包括ε)的集合。 Σ*称为Σ的闭包。 7)从*中除去ε得到的集合记为+ 。 Σ+称为Σ的正闭包。
  • 12. 1、规则(重写规则、产生式或生成式): 是形如α→β或α∷=β的(α,β)有序对,其中α是某字母表V的正闭包V+中的一个符号,β是V*中的一个符号。(α∈V+,β∈V* why?) α称为规则的左部(或生成式的左部)。 β称为规则的右部(或生成式的右部)。 例: 〈句子〉::= 〈主语〉〈谓语〉 〈主语〉::= 〈代词〉|〈名词〉 〈代词〉::= 你 | 我 | 他3.3 文法和语言的形式定义
  • 13. 2、文法G定义为四元组(VN,VT,P,S) 元素说明: VN :非终结符集 VT :终结符集 P:产生式(规则)集合 S:开始符号(识别符号) VN、VT 和 P 是非空有穷集。S 至少在一条规则中作为左部出现。 VN∩VT= φ, S∈VN V=VN∪VT,称为文法G的字母表(字汇表)例3.1 文法G=(VN,VT,P,S) VN = { S }, VT ={ 0, 1 } P={ S→0S1, S→01 } S为开始符号
  • 14. 例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语言的标识符(变量命名)如何用文法定义?
  • 15. 文法习惯上只将产生式写出。并有如下约定: 第一条产生式的左部是开始符号 用尖括号括起的是非终结符,否则为终结符。或者大写字母表示非终结符,小写字母表示终结符 G可写成G[S],其中S是开始符号例3.1 文法G=(VN,VT,P,S) VN = { S }, VT ={ 0, 1 } P={ S→0S1, S→01 } S为开始符号可写成: G:S→0S1 S→01或写成: G[S]:S→0S1 S→01
  • 16. 3、推导的定义直接推导“” α→β是文法G产生式,γ,δ∈V*,若v,w满足: v=γαδ, w = γβδ, 则说:v(应用规则α→β)直接产生w 或说:w是v的直接推导 或说:w直接归约到v 记作 v  w 例:G: S→0S1, S→01 的直接推导: 0S10011 (v=0S1,w=0011,使用规则S→01,γ=0,δ=1) S 0S1 (v=S,w=0S1,使用规则S→0S1,γ=ε,δ= ε ) 0S100S11 (v=0S1,w=00S11,使用规则?)
  • 17. 例 文法G=(VN,VT,P,S) VN ={标识符,字母,数字} VT ={a,b,c,…x,y,z,0,1,…,9} P={<标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字> <字母>→a,…, <字母>→z <数字>→0,…, <数字>→9 } S=<标识符>思考:指出下面直接推导所使用的规则 ? <标识符>  <标识符><字母> <标识符> <字母> <数字>  <字母> <字母> <数字> abc <数字> abc5
  • 18. 例:G: S→0S1, S→01 0S1 00S11 000S111 00001111 即 0S1 00001111 也记作 0S1 00001111 思考: 的区别?若存在v =w0 w1 ... wn=w, (n>0) 则称v推导出(产生)w(推导长度为n),或称w归约到v. 记作 v w 若有v w,或v=w,则记为v w + + * + * + * 和+ * 和
  • 19. 4、文法的句型、句子的定义句型:设G[S]是一文法,如果符号串x是从识别符号推导出来的,即S x,则称x是文法G[S]的句型。 句子:x仅由终结符号组成(即S x,且x∈VT*),则称x是G[S]的句子。 例:G: S→0S1, S→01 S 0S1 00S11 000S11100001111* * 思考: 文法的句型与句子的关系? 文法G能得到哪些句子?
  • 20. 5、语言的定义:由文法G生成的语言记为L(G),它是文法G的一切句子的集合: 即L(G)={x|S x,其中S为文法的开始符号,且x ∈VT*} 例:G: S→0S1, S→01 L(G)={0n1n|n≥1}* 6、文法的等价:若L(G1)=L(G2),则称文法G1和G2是等价的。 课堂作业:P44 2思考:文法G1[A]:A→0R A→01 R→A1的语言?
  • 21. 3.4 文法的类型Chomsky将文法分四类(对产生式施加不同限制 ): 0型文法(短语文法):对任一产生式α→β,都有α∈(VN∪VT)+且至少含一个非终结符, β∈(VN∪VT)* 1型文法(上下文有关文法):对任一产生式α→β,都有|β|≥|α|, 仅仅 A→ε除外。 2型文法(上下文无关文法) :对任一产生式α→β,都有α∈VN , β∈(VN∪VT)* 3型文法(正规文法):任一产生式α→β的形式都为 A→aB或A→a,A∈VN ,B∈VN ,a∈VT (右线性文法) A→Ba或A→a,A∈VN ,B∈VN ,a∈VT (左线性文法) 思考:四种文法之间的关系?
  • 22. 四种文法之间的逐级“包含”关系2型文法1型文法0型文法3型文法
  • 23. 例:判断下列文法的类型 1: 文法G[S]: S→aSBE S→aBE EB→BE aB→ab // aBb→ab ? bB→bb bE→be eE→ee2: 文法G[S]: S→aB|bA A→a|aS|bAA B→b|bS|aBB //B→ε ? 3: 文法G[S]: S→0A|1B|0 A→0A|1B|0S B→1B|1|0 // B→B1|1|0 ?
  • 24. 文法和语言0型文法( PSG )产生的语言称为0型语言 1型文法或上下文有关文法( CSG )产生的语言称为1型语言或上下文有关语言(CSL) 2型文法或上下文无关文法( CFG )产生的语言称为2型语言或上下文无关语言( CF L ) 3型文法或正则(正规)文法( RG )产生的语言称为3型语言正则(正规)语言( RL )思考:文法与语言的关系?
  • 25. 3.5 上下文无关文法及其语法树1、上下文无关文法有足够的能力描述现今程序设计语言的语法结构。 注:无特殊说明,“文法”均指上下文无关文法 算术表达式 语句 赋值语句 条件语句 读语句 ……
  • 26. 例:算术表达式文法表示(i为变量)G=({E}, {+,*,i,(,)}, P, E} P: E → i E → E+E E → E*E E → (E) 例:赋值语句文法表示 <赋值语句>→i = E 例:条件语句文法表示 <条件语句>→if<条件>then<语句> | if<条件>then<语句>else <语句>思考:是上下文无关文法?文法的VN,VT, P, S ?
  • 27. 2、上下文无关文法的语法树用于描述上下文无关文法的句型推导的直观方法 例: G[S]: S→aAS A→SbA A→SS S→a A→ba 能得到句型aabbaa? S a A S S b A a a b a句型aabbaa的语法树(推导树)叶子结点:树中没有子孙的结点。 从左到右读出推导树的叶子标记,所得的句型为推导树的结果。也把该推导树称为该句型的语法树。
  • 28. 推导过程中施用产生式的顺序 例: G[S]: S→aAS A→SbA A→SS S→a A→ba 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aabbaa
  • 29. 最左(最右)推导:在推导的任何一步αβ,其中α、β是句型,都是对α中的最左(右)非终结符进行替换。 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型 例: G[S]: S→aAS A→SbA A→SS S→a A→baSaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa思考:最右推导的逆过程? 一个句型是否对应唯一的一棵语法树?
  • 30. 问题:一个句型是否对应唯一的一棵语法树?例:G[E]: E → i E → E+E E → E*E E → (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
  • 31. 二义性文法二义性: 若一个文法存在某个句子对应两棵不同的语法树,则称这个文法是二义的。(或者,若一个文法存在某个句子有两个不同的最左(右)推导) 语言先天二义: 产生某上下文无关语言的每一个文法都是二义的。说明:判定任何文法或语言的二义性是不可解的。但可以为无二义性寻找一组充分条件。 例:二义文法改造为无二义文法(如:i*i+i的推导) G[E]: E → i G[E]: E → T|E+T E → E+E T → F|T*F E → E*E F → (E)|i E → (E) 规定优先顺序和结合律(第6章)
  • 32. 3.6 句型的分析句型分析就是识别一个符号串是否为某文法的句型,是某个推导的构造过程。 在语言的编译实现中,把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。 分析算法可分为: 自上而下分析法: 从文法的开始符号出发,反复使用各种产生式,寻找与输入符号匹配的推导。 自下而上分析法: 从输入符号串开始,逐步进行归约,直至归约到文法的开始符号。 两种方法反映了两种不同的语法树的构造过程
  • 33. 自上而下的语法分析例:文法G:S → cAd A → ab A → a 识别输入串 w = cabd 是否该文法的句子推导过程:S  cAd  cabd 思考:此种分析方法的关键是什么?
  • 34. 自下而上的语法分析例:文法G:S → cAd A → ab A → a 识别输入串 w = cabd 是否该文法的句子。规约过程:S  cAd  cabd 思考:此种分析方法的关键是什么?
  • 35. 句型分析的有关问题1)如何选择使用哪个产生式进行推导? 假定要被代换的最左非终结符号是V,且有n条规则:V→A1|A2|…|An,那么如何确定用哪个右部去替代V? 2)如何识别可归约的串? 在自下而上的分析方法中,在分析程序工作的每一步,都是从当前串中选择一个子串,将它归约到某个非终结符号,该子串称为“可归约串”
  • 36. 短语、直接短语、句柄的定义: 文法G[S], αβδ是G的一个句型, 如果:S αAδ且A β, 则称β是句型αβδ相对于非终结符A的短语。 若有A β则称β是句型αβδ相对于规则A→β的直接短语(或简单短语)。 一个句型的最左直接短语称为该句型的句柄。* + 例 文法: G[E]:E→E+T|T T→T*F|F F→(E)|a1|a2|a3 求句型:a1+a2*a3的短语,直接短语与句柄? 求解方式:定义或语法树来判定.
  • 37. 例 文法: G[E]:E→E+T|T T→T*F|F F→(E)|a 句型:a1+a2*a3短语:a1 , a2 , a3 , a2*a3 , a1+a2*a3 直接短语:a1 , a2 , a3 句柄:a1思考: +是短语吗? a1 + a2是短语? F*a3是短语?
  • 38. 语法树中句型,短语和句柄 (1)每一句型都有一棵语法树,每个语法树的所有有序叶子组成一句型(句子?)。 (2)每棵子树的所有叶子组成短语,每棵直接子树的所有叶子组成直接短语,最左直接子树的叶子组成句柄(直接子树?一层分支) 思考:句型的a1+T*F的短语…? 注:若语法树不易判时,可结合定义判定!
  • 39. 3.8有关文法实用中的一些说明1、有关文法的实用限制 (文法中不得含有有害规则和多余规则)有害规则:形如U→U的产生式。引起文法二义性(why)。 多余规则:文法中任何句子推导都不会用到的规则。 文法中某些非终结符不在任何规则的右部出现(开始符号除外),该非终结符称为不可到达的 文法中某些非终结符,由它不能推出终结符号串来,称为不可终止的
  • 40. 对于文法G[S],为了保证任一非终结符A在句子推导中出现,必须满足如下两个条件: 1)A(开始符号除外)必须在某句型中出现。 2)必须能从A推出终结符号串t来。 即 文法G[S],对某两个符号串α和β: S αAβ A t ,t∈VT** + 
  • 41. 化简文法例:G[S] 1) S→Be G[S]: S→Be B→Af A→Ae A→e 7) D→f 8) A→A 6) C→Cf 2) B→Ce 3) B→Af 4) A→Ae 5) A→e
  • 42. 2、上下文无关文法中的ε规则(了解)具有形式A→ε的规则称为ε规则,其中A∈VN( 某些著作和讲义中限制这种规则的出现。因为ε规则会使有关文法的一些讨论和证明变得复杂) 两种定义的唯一差别是ε句子在不在语言中。 如果语言L有一个有穷的描述,则L∪{ε}也同样有一个有穷描述。 并且可以证明,若L是上下文有关语言、上下文无关语言或正规语言,则L∪{ε}和L-{ε}分别是上下文有关语言、上下文无关语言和正规语言
  • 43. 上下文无关法的两种定义 定理3.1: 文法G,P中的每一个产生式的形式均为A→α,其中A∈VN,α∈(VN ∪VT)*(即α可能为ε),则L(G)也能由这样一种文法产生:每一个产生式或者为A→β形式,其中A∈VN,β ∈(VN ∪VT)+(即β≠ε),或者 S→ε且 S不出现在任何产生式右边。 定理3.2: G是上下文有关文法,则存在另一个上下文有关文法G1,L(G)= L(G1),且G1的开始符号不出现在G1的任何产生式的右边。若G为上下文无关文法或正规文法,类似结论成立。
  • 44. 知识体系结构
  • 45. 考查重点 基本概念 : 文法;推导/归约;句型;句子;语言;文法的二义性;递归规则;文法递归;语法树;短语;直接短语;句柄;正规文法;上下文无关文法。 基本方法 构造句型的推导/归约,规范推导/规范归约 画出指定句型的语法树 判别文法的二义性 给出句型的短语、直接短语、句柄。 文法与语言的互求(较简单)。作业:p45 11, 13 ,14(1,2)