《山东理工大学计算机科学与技术学院编译原理课件第三章文法与语言.ppt》由会员分享，可在线阅读，更多相关《山东理工大学计算机科学与技术学院编译原理课件第三章文法与语言.ppt（69页珍藏版）》请在三一文库上搜索。
1、1,第3章 文法和语言,引言 3.1 文法的直观概念 3.2 符号和符号串 3.3 文法和语言的形式定义（重点） 3.4 文法的类型 3.5 上下文无关文法及其语法树（重点） 3.6 句型的分析（重点） 本章练习 作业,课程目录,2,语言特征,自然语言 是人与人的通讯工具 环境、背景知识、语气、二义性 叙述性描述（非形式化方法） 计算机语言 计算机软件使用的通讯工具 严格的语法、语义 记号描述（数学描述、形式化方法）,3,本章目的,本章目的 为语言的语法描述寻求工具 通过该工具可以 对源语言给出精确的无二义性的语法描述 (严谨、简单和易读) 根据语言文法的特点来指导语法分析的过程 从描述语言的
2、文法可以自动构造出可用的分析程序 制导语义翻译,4,语言定义,语言 是由句子组成的集合，是由一组记号所构成的集合 汉语所有符合汉语语法的句子的全体 英语所有符合英语语法的句子的全体 程序设计语言所有该语言的程序的全体 研究语言 每个句子构成的规律 每个句子的含义 每个句子和使用者的关系,5,语言研究的三个方面,语法（Syntax) 表示构成语言句子的各个记号之间的组合规律 语义(Semantics) 表示按照各种表示方法所表示的各个记号的特定 含义(各个记号和记号所表示的对象之间的关系) 语用(Pragmatics) 表示在各个记号所出现的行为中，它们的来源、 使用和影响,6,形式语言理论简介
3、,形式语言理论（Formal Language Theory) 是一种从语法上研究语言的理论 是抽象的数学系统 着重研究符号串集合的表示法、结构及其特征 是程序设计语言语法分析研究的基础（我们仅使 用与编译程序构造有关的结论，而不做证明） 形式语义(Formal Semantics) (本课程不介绍）,7,计算机语言的组成结构,自 然 语 言,程 序 语 言,语言,句子的集合,句子,多个单词按一定规则组成,单词,多个字符按一定规则组成,编程语言,程序的集合,程序,多个单词按语法规则组成,单词,多个字符按词法规则组成,8,程序语言的定义 p32,一个程序语言是一个记号系统 程序语言的定义 语法和
4、语义 语法 形成和产生合适程序的规则集 词法规则 形成单词符号的规则 语法规则 形成语法单位的规则 常用的语法描述方法 正规文法词法规则 上下文无关文法语法规则,9,程序语言的语法构成,语法,词法规则,语法规则,单词符号,常数 标识符 基本字 字符 算符 界符,语法 单位 (范畴),表达式 语句 函数、过程 程序,例 源程序字符串 0.5*X1+C,0.5,*,X1,+,C,0.5*X1+C,(a+b)*2,(,a,+,b,),*,2,(a+b)*2,10,程序语言的定义 p32,语义 用以定义程序意义的规则集 静态语义 确定哪些合乎语法的程序是合适的规则集合 动态语义 表明程序要做些什么，要
5、计算什么 在不同语言中完全相同的语法单位 含义却可能完全不同 例如：x=y C语言赋值表达式 Pascal语言关系表达式 C中x=y,11,程序语言构成的共同点,语法： 语句的组成规则 描述方法：BNF范式、语法描述图 词法： 单词的组成规则 描述方法：BNF范式、正规式 单词： 具有语义的最小字符串（可区分的）,章节目录,12,3.1 文法的直观概念 p32,定义描述英语句子的文法 例如 He gave me a book 文法的规则如下： (1) (2) (3) (4) (5) (6)He|me (7)a (8)gave (9)book|peach,13,上下文无关文法 实例,例 He g
6、ave me a book 应用上述语法规则进行推导： 句子 =主语 谓语 间接宾语 直接宾语 =代词 谓语 间接宾语 直接宾语 =He 谓语 间接宾语 直接宾语 =He 动词 间接宾语 直接宾语 =He gave 间接宾语 直接宾语 =He gave 代词 直接宾语 =He gave me 直接宾语 = He gave me 冠词 名词 = He gave me a 名词 = He gave me a book,终结符号 He,me,book,gave,a等 非终结符号 句子,主语,谓语,动词等 开始符号 句子 产生式 语法规则,14,上下文无关文法 实例语法树,例 He gave me a
7、 book, ,He,gave,me, ,a,book,非终结符,开始符 ,终结符,由文法所定义的终结符串句子,15,文法概念理解(课堂练习) p32,描述汉语句子的文法规则: (1) (2)| (3)我|你|他 (4)王明|大学生|工人|英语 (5) (6)是|学习 (7)| 请给出他学习英语的推导过程和语法树：,BEGIN,文法的特点： 以有穷的集合刻画无穷集合的一个工具。,章节目录,16,3.2 符号和符号串 p33,字母表 符号串 符号串的头尾 符号串的连接 符号串的方幂 符号串的集合,17,基本概念 符号和字母表 p33,符号(元素) 可以相互区别的记号 例 a b 0 1 字母表
8、符号的非空有穷集合 例=0，1 二进制数语言的字母表 A=a，b 由符号a和b组成的字母表 字母表包含语言中所允许出现的一切符号 一种程序设计语言的字母表是该语言的基本字符集 C语言是C程序的集合 C程序是在C基本字符集上定义的，按一定规则构成的符号串,18,基本概念 符号串 p33,符号串 由字母表中的符号所组成的任何有穷序 列称为该字母表上的符号串 例 001110是字母表上的符号串 a,b,aa,bb,abb,bba,都是字母表A上的符号串 注意 符号串中符号的顺序是重要的 例 ab不同于ba 符号串的长度 符号串中符号的个数 例 x=001110 则x长度|x|=6 空串 (空字) 长
9、度为0的符号串 |=0,19,关于符号串操作,运算 设x是某字母表上的符号串 连接(并置) x=123, y=45那么xy=12345 方幂：x的n次方幂即将n个x连接 x0= x1=x x2=xx 子符号串 v是xvy的子符号串，v非空 头，尾 x是xy的头，y是xy的尾,20,符号串集合,符号串集合 若集合A中的一切元素都是某字母表上的符号 串，则称A为该字母表上的符号串的集合 例 =0，1是字母表,其中0,1为符号 则D=0,1 其中0,1为符号串 E= , 0,1,00,01,10,11,000, 是上的符号串集合 特别 空集记为 = 注意与区别,21,符号串集合的运算 p25,乘积
10、UV = |U且V 例 A=a，b B=c，d 则AB=ac，ad，bc，bd 方幂 V的n次方幂就是将n个V相乘 设A=a，b A0= A1=A =a，b A2=AA=aa，ab，ba，bb An=AAA (n个A的乘积） 所有由A中符号构成的长度为n的符号串的集合,22,符号串集合的运算 p25,符号串集V的闭包 V* V* =V0 V1 V2 V3 设V=a，b，则 V* =a，b aa，ab，ba，bb =，a，b，aa，ab，ba，bb，aaa， V的闭包V*是V上的所有符号串(包括空字)的集合 符号串集V正则闭包 V+ V+ = V1 V2 V3 =V V* 设V=a，b，则 V+
11、 =a，b aa，ab，ba，bb =a，b，aa，ab，ba，bb，aaa， V的正则闭包V+是V上的所有的非空符号串的集合,23,语言的概念,语言 某个字母表上的符号串集合，是*的 一个子集 例 =0，1 * = ,0,1,00,01,10,11,000,001, 则 1,11,111,1111,是一种语言,章节目录,24,3.3 文法和语言的形式定义 p34,规则或产生式 文法的定义 (直接)推导和 (直接)归约 句型和句子 文法描述的语言 文法的等价性,25,规则或产生式 p34,形式 或:= 称为产生式的左部 称为产生式的右部 读作“定义为” 举例 Aa 这是关于A的一条规则 a|b
12、|z,26,文法G的形式定义 p35, = (T，N，S，P) Chomsky定义文法为一个四元式 T 非空有穷终结符集 N 非空有穷非终结符集 T N = N 开始符号 S至少在产生式左部出现一次 非空有穷产生式集合 (T N)*，且至少含有一个非终结符 (T N)*， 令=T N 称为文法符号，是文法G的字母表,27,例 算术表达式的文法 G,考虑含有+、*的算术表达式组成的文法 G =(i，+，*，(，)，E，E，P),P: E E + E E E * E E ( E ) E i,T,N,S,简写 GE:E E + E | E * E | ( E ) | i,表达式3*4可由该文法定义
13、E = E * E = i * E = i * i 3 4,直接推导,28,文法描述的约定 p35,用大写字母A、B、C或汉语词组代表非终结符号 用小写字母a、b、c代表终结符号 用希腊字母、代表终结符号 和非终结符号组成的符号串 若干个左部相同的产生式可以合并为一个 P1| 2 | n 每个i 称为P的一个候选式,29,直接推导（直接归约）p35-36,产生式右部代替左部 当是文法的一个产生式， 且、(TN)*， 则有 = ， 称是的直接推导 或称直接归约到 GE:EE + E|E * E|( E )|i i + E = i + E * E 特点：只能用一次产生式替换,30,推导（归约）p2
14、9,如果0=1=2=n，则称这个序列是从0至n的一个推导 用0=+n表示从0出发，经一步或多步推导，可推出n 用0=*n表示从0出发，经零步或多步推导，可推出n ，即0=n或0=+n 例如 E = E * E = i * E = i * i E =+ i * i 至少用一次产生式替换 例如 E = E E =* E 可以不用产生式替换,31,句型 p36,设 G 是一个文法，S 是开始符号， 若有 S =*，则称是文法G的一个句型 G(E):EE + E|E * E|( E )|i 例如 E=+i*E,则i*E是文法G(E)的一个句型 E=+i*i,则i*i是文法G(E)的一个句型 句子 完全
15、由终结符组成的句型 例如 E=+i*i,则i*i是文法G(E)的一个句子 合法句子的生成 从出发反复推导，每次得到一个句型，最终得到句子,32,例: 文法G(E)为： E E + E | E * E | ( E ) | i 表达式 (i * i + i) 的生成 E = ( E ) = ( E + E ) = ( E * E + E ) = ( i * E + E ) = ( i * i + E ) = ( i * i + i ),句型和句子生成举例,句型,句子,33,例: 文法GE为： E E + E | E * E | ( E ) | i 表达式 i + i * i 的生成 BEGIN E
16、 = E + E = i + E = i + E * E = i + i * E = i + i * i,句型和句子生成练习,句型,句子,34,文法G描述的语言 p36,由文法产生的所有句子的集合 ()+ &T* 文法G的作用 以有限的规则描述无限的语言现象 有限 产生式集合 终结符集合 非终结符集合 无限 由开始符号导出的句子 GE:EE + E|E * E|( E )|i 文法G所描述的语言：含有+、*和括号的算术表达式,35,例3.1 文法G=(VN,VT,P,S) 其中VN=S,VT=0,1,P=S0S1,S01 简写文法GS：S0S1 S01,文法和语言课堂练习 p35-36,文法G
17、描述的语言 S=01 (最短的句子) S=0S1 =00S11 =000S111 =0n-1S1n-1= 0n1n L(G)=0n1n|n=1,36,文法的等价性 p38,文法的等价 若L(G1)=L(G2)，则称文法G1和G2是等价的 （它们产生的句子集合相同） 文法G1E:EE+E | E*E |(E)| i 文法G2E:EE+T | T TT*F | F F(E)| i 因为L(G1)=L(G2),所以文法G1和G2是等价的。,章节目录,37,3.4 文法的类型( Chomsky p38),通过对产生式施加不同的限制，将文法分为 四种类型 0型文法 短语文法 phrase structu
18、re grammar 对任一产生式，都有(NT)* 且至少含有一个非终结符，(NT)* 限制最少，描述能力最强 例如 aABcD,38,文法的类型 p38,1型文法 上下文有关文法 context sensitive grammar 对任一产生式，都有 仅仅除外，并且不出现在其他产生式 的右部 例如 SaSBA AAAB,39,文法的类型 p38,2型文法 上下文无关文法 context free grammar 对任一产生式， 都有N，(NT)* 例如 EE+T|T 足以描述大多数程序设计语言语法特征,40,2型文法描述语法单位举例,G2(E): E E+T|T T T*F|F F (E)|
19、i ifthen |ifthenelse |,41,文法的类型 p39,3型文法 正规文法 regular grammar 右线性文法 对任一产生式的形式都为或 其中，N ，T* （可为） 左线性文法 对任一产生式的形式都为或 其中，N ，T* （可为） 足以描述大多数程序设计语言词法特性,42,3型文法描述单词符号举例,假设l=a,b,c,z d=0,1,2,9 l | l l|d|l|d d | d +|-|*|/|= ，|；|（|）,43,四类文法间关系,由于四种文法是按照将产生式做进一步限制而定义的，所以它们之间是逐级“包含”的关系，由四种文法产生的语言也是逐级“包含”关系。,0型文法
20、,1型文法,2型文法,3型文法,章节目录,44,3.5 上下文无关文法及其语法树 p39,上下文无关文法 语法树（推导树） 最左（最右）推导 规范推导和规范句型 二义性文法,45,上下文无关文法组成,终结符号 组成语言的基本符号，在程序语言中 是单词符号。 非终结符号 用来代表语法范畴(语法概念)，每 个非终结符号表示一定符号串的集合。 开始符号 一个特殊的非终结符号。 产生式 是定义语法范畴的一种书写规则。 形式 A A是一个非终结符，称为产生式的左部符号 是一个符号串，称为产生式的右部,46,语法分析树引例,给定文法G，对于G的任何句型都能构造与之相关 的语法树（该树叶结点自左至右排列即为
21、该句型）,句型(或句子)语法树,例文法G(E)为：E E + E | E * E | ( E ) | i,句子i+i*i的最左推导过程 E = E + E = i + E = i + E * E = i + i * E = i + i * i,对应语法树,E,E + E,i,E * E,i,i,47,语法树的构造特点 p40,每个结点都有一个V中的符号作标记 根结点开始符S 中间结点非终结符AN 叶结点非终结符或终结符(关于句型) 终结符aT (关于句子),如果结点n标记为A， 其直接子孙从左到右的 标记为A1,A2,Ak, 则 A A1A2Ak P,A,A1,A2,Ak,48,从推导构造语法
22、树,步骤1 根结点为开始符号 步骤2 对于每一次推导使用的产生式A， 找出A对应的结点(此时应该是末端结点)，从 该结点向下画分支，子结点从左到右分别是 中从左到右的符号 重复步骤2直到推导的最后一步,49,语法树的例子(课堂练习),文法G: SAB AaAb | ab BcBd | cd 请给出abccdd的 语法树： BEGIN,S,S=AB=abB=abcBd=abccdd 最左推导,S=AB=AcBd=Accdd=abccdd 最右推导,S=AB=AcBd=abcBd=abccdd 非最左最右推导,50,语法树的特点 p41,从语法树的构造过程可以看出: 句型的推导过程不同，语法树的生
23、长过程 也不同，但最终生成的语法树结构是完全 相同的。 可以说，一棵语法树包括了一个句型所有 可能的推导过程。整体上看不出推导的次 序(即产生式使用的次序)，只能看出使用 了哪些产生式。,51,最左(右)推导 p41,定义 在一个推导的过程中，如果每一步直接推导所 被替换的总是最左(右)的非终结符号。 举例 文法G(E)：EE+E|E*E|(E)|i 对于句子 i*i+i 的推导过程有以下几种方式,1.最左推导,E,=E+E =E*E+E =i*E+E =i*i+E =i*i+i,2.最右推导,E,=E+E =E+i =E*E+i =E*i+i =i*i+i,3.非最左最右推导,E,=E+E
24、=E+i =E*E+i =i*E+i =i*i+i,52,规范推导和规范句型 p41,最右推导常被称为规范推导。 由规范推导所得到的句型称为规范句型，也称为右句型。,53,一个句型是否对应唯一的一棵语法树？p41,例 文法G：EE+E | E*E | (E) | i 文法的句子: i+i*i，其语法树如下：,E,i,i,i,E,i,i,i,(一),(二),句子i+i*i对应两个不同的最左推导 文法G是二义性文法,54,文法的二义性 p41,若一个文法存在某个句型对应两棵不同的语法 树，则称这个文法是二义性文法。 或者，若一个文法存在某个句型有两个不同的 最左(最右)推导，则称这个文法是二义性文
25、法。 二义性一般是有害的 如果一个句子具有二义性，那么对这个句子的结构 可能有多种“正确”的解释。 通常情况下，我们希望对每个语句的分析是唯一的。 但是,只要我们能够控制和驾驭文法的二义性, 文法二义性的存在并不一定是坏事 。,55,文法的二义性和语言的二义性 p42,文法G1E：EE+E | E*E |(E)| i 二义性文法 文法的句子i+i*i 无二义性 文法所产生的语言L(G1) 无二义性语言,56,二义性文法的判定问题 p42,这个问题是不可判定的。 对某文法，若能找出一个句子对应两棵不同 的语法树，则该文法必是二义性文法。 二义性文法可以改造为无二义性文法。,G1E: E E +
26、E | E * E|( E )|i G1是二义性文法,对运算符规定优先顺序和结合率,将G1变为等价 的文法G2E: E E+T|T T T*F|F F (E)|i G2(E)是无二义性文法,57,无二义性文法,每个句子对应唯一的 一棵语法树 G2E: E E+T|T T T*F|F F (E)|i,句子i+i*i有唯一 的一棵语法树,E,E + T,T * F,F,F,T,i,i,i,58,文法与语言举例,文法G1S：SbA AaA|a S=bA=ba S=bA=baA=baa S=bA=baA=baaA =baaa L(G1)=ban|n=1,文法G2S：SAB AaA|a BbB|b S=
27、AB=aB=ab S=AB=aAB=aaB=aab S=AB=aAB=aaB=aabB =aabb S=AB=aB=abB=abb S=AB=aB=abB=abbB =abbb L(G2)=ambn|m，n=1,给定文法G，描述它 所生成的语言L(G),59,文法与语言举例,构造一个文法G3，使L(G3)=anbn|n=1 分析 每个句子，a在前，b在后，且个数相同 文法G3S: SaSb|ab 造一个文法G，使L(G)=anbnci|n=1,i=0 分析 每个句子分成两部分考虑 ab(至少出现一次) c(可以不出现) ab个数相同,与c的个数可以不同 文法GS: SAC|A AaAb|ab
28、CCc|c,构造文法G，使它能描述所给定的语言L(G),60,文法与语言练习,文法G4S： S bS | a 请给出所生成语言 BEGIN S=a S=bS=ba S=bS=bbS=bba L(G4)=bna|n=0,文法G5S：SAb AaaA|aa 请给出所生成语言 BEGIN S=Ab=aab S=Ab=aaAb=aaaab S=Ab=aaAb=aaaaAb =aaaaaab L(G5)=a2nb|n=1,章节目录,61,3.6 句型的分析 p42,基本概念 自上而下的分析方法 自下而上的分析方法 句型分析的有关问题 可归约串 短语 直接短语 句柄,62,基本概念 p42,句型分析问题
29、如何知道所给定的字符串是文法的句型。 句型的分析 就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。 或者说，是否能为一个符号串构造一颗语法树。 语法分析树（或分析树） 就是语法树。 分析程序（或识别程序） 完成句型分析的程序。分析算法又称为识别算法。,63,3.6.1 自上而下分析方法 p43,从开始符号出发，构造最左推导的过程。 从树根出发，利用推导生成语法树的过程。 问题：选用哪个产生式进行推导？ 例如 文法GS: (1) ScAd (2)Aab (3)Aa 输入串w=cabd,S,c A d,a b,64,3.6.2 自下而上分析方法 p43,从输入串出发，进行最左归约，直到
30、开始符号。 从叶子结点出发，修剪语法树直至只剩开始符。 问题：如何寻找可归约串？ 例如 文法GS: (1) ScAd (2)Aab (3)Aa 输入串w=cabd,S,A,c a b d,65,3.6.3 句型分析的有关问题 p44,短语 直接短语（简单短语） 句柄,章节目录,66,本章练习,1巴科斯瑙尔范式（EBNF）是一种广泛采用的 工具。 A 描述规则 B 描述语言 C 描述文法 D 描述句子 2由文法的开始符号经0步或多步推导产生的文法符号序列 是 。 A 短语 B 句柄 C 句型 D 句子,67,本章练习（续）,3. 如果一个文法满足 ，则称该文法是二义文法。 A 文法的某一个句子存
31、在两棵（包括两棵）以上不同的语法树 B 文法中存在某个句子，有两个（包括两个）以上不同的最右（最左）推导 C 文法中存在某个句子，有两个（包括两个）以上不同的最右（最左）归约 D 在进行归约时，文法的某些规范句型的句柄不惟一 4. 一个上下文无关文法G包括四个组成部分：一个表示语言的基本符号的 集合，一个表示语言的语法成分的 集合，一个 ，以及一个 集合。 A 字符串 B 字母数字串 C 产生式 D 结束符号 E 开始符号 F 文法 G 非终结符号 H终结符号,H,G,E,C,68,本章练习（续）,5. 请给出描述语言L=a2m+1bm+1| m=0a2mbm+2 | m=0的文法 6. 文法GS: SaSPQ|abQ答案:GZ:ZaaZb|ab|bb QPPQ bPbb bQbc cQcc 它是乔姆斯基哪一型文法？它生成的语言是什么？,答:GZ:ZaaZb|ab|bb,从规则形式上可以看出，文法G是乔姆斯基1型文法，即上下文有关文法。它生成的语言是L=anbncn|n=1。,答：从规则形式上可以看出，文法G是乔姆斯基1型文法，即上下文有关文法。它生成的语言是L=anbncn|n=1。,章节目录,69,作业 p48,2、4、5 9、10、11、13、14,章节目录,