编译原理形式语言.ppt

《编译原理形式语言.ppt》由会员分享，可在线阅读，更多相关《编译原理形式语言.ppt（90页珍藏版）》请在装配图网上搜索。

1、第二章形式语言概论,形式语言理论,什么是语言？ “为相当大地区的公众所懂得并使用的话，以及组成这些话的方法的统一体” “某一字母表上符号串（句子）的集合” 定义仍需精确化 1）字母表 2）语法 3）语义,形式语言理论,由数学方法研究自然语言(如英语)和人工语言(如程序语言)之语法的理论,主要讨论了语言和文法的数学机制以及语言和文法的分类 应用领域,(一)形式语言理论 (二)语言和文法的直观概念 (三)字母表、串、语言 (四)文法和语言的形式定义 (五)文法的类型 (六)上下文无关文法及语法树 (七)句型的分析 (八)有关文法实用中的一些说明,(一)形式语言理论 (二)语言和文法的直观概念 (三

2、)字母表、串、语言 (四)文法和语言的形式定义 (五)文法的类型 (六)上下文无关文法及语法树 (七)句型的分析 (八)有关文法实用中的一些说明,(一)形式语言理论 (二)语言和文法的直观概念 (三)字母表、串、语言 (四)文法和语言的形式定义 (五)文法的类型 (六)上下文无关文法及语法树 (七)句型的分析 (八)有关文法实用中的一些说明,(二)语言和文法的直观概念（引例）,我们从“产生语言”的角度出发,讨论文法和语言的形式定义 语言生成指制定出有限条规则，借助它们产生的句子的集合 英语语言为例。并设每个句子都是“主-谓-宾”结构 文法见右。其中，每个用括起来的部分是所要定义语言中的一个语法

3、实体（称为语法单位、语法结构、语法范畴、语法变量等）。“:=”是用于定义语法结构的符号，其含义（并读作）“定义为” 。文法也称为产生式(Production),:= := the := := :=monkey :=banana :=eat :=has :=the :=a,(二)语言和文法的直观概念（引例）,推导(derivation)从语言最大的一个语法实体（本例中是）开始，反复用语法规则中“:=” 右侧的符号串取代其左侧符号，直到所得的符号串中不再含有可被替换语法实体。每次替换称为一步（直接）推导，并用符号“”表示。 例如 首先用规则进行第一步推导，可得到，即 所得符号串含有两个语法实体，可

4、对其中任一个（例如对）进行新的推导 重复上述过程，可得到一个推导序列（见下页）。,推导 所用 所得的符号串 步 规则 1 2 3 the 4 the 5 the monkey 6 the monkey eat 7 the monkey eat a 8 the monkey eat a banana,推导序列,推导长度,用语法规则进行推导,从出发，经8步推导得到一个英语句子,则称前面的推导为长度为8的推导 若不关心推导的中间过程，可将从一符号串到另一符号串的推导用记号,规则的简化表示,在前面的语法规则定义中，有些语法范畴（如、）有若干条不同的规则来定义它，为简明起见，我们可以将它们写在同一个左部

5、语法范畴下，将其定义值用符号“|”（读作或）隔开。如、 、 的定义规则可简记为 := monkey | banana := eat | has := the | a,推导 所用 所得的符号串 步 规则 1 2 3 the 4 the 5 the monkey 6 the monkey eat 7 the monkey eat a 8 the monkey eat a banana,练习：请推导the banana eat a monkey,推导序列,语法规则及其产生的语言,前面的语法规则可以产生16个不同的句子，由这16个句子组成的集合，就是该规则所定义（或所产生）的语言 应指出，所产生的句子

6、中，有些句子的含义是荒谬的（如 the banana eat a monkey和the banana eat the banana等）。然而，若不考虑语义，则我们就必须承认它们是语法上合法的句子。,(二)语言和文法的直观概念,程序设计语言的定义 语言是一个记号系统。 汉语-符合汉语语法的句子的全体 英语-符合英语语法的句子的全体 程序设计语言-该语言的程序的全体 程序设计语言由语法和语义定义： 语法：定义每个程序构成的规则 语义：定义每个程序的意义,程序设计语言包括:语法和语义 语法(syntax) 定义: 是一组规则，用它可以形成和产生一个合适的程序 描述工具:文法 作用: 定义什么样的符号

7、序列是合法的，与符号的含义无关。,语义(semantics) 分类: 静态语义：一系列限定规则，确定哪些合乎语法的程序是合适的 动态语义：表明程序要做什么 描述工具: 指称语义,操作语义等 作用: 检查类型匹配，变量作用域等,文法的直观概念,如何来描述一种语言？ 如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示 如果语言是无穷的，要找出语言的有穷表示。 有两个途经： 生成方式 （产生式）：语言中的每个句子可以用严格定义的规则来构造 识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继

8、续下去。,例:“the monkey eat a banana”,back,back,(一)形式语言理论 (二)语言和文法的直观概念 (三)字母表、串、语言 (四)文法和语言的形式定义 (五)文法的类型 (六)上下文无关文法及语法树 (七)句型的分析 (八)有关文法实用中的一些说明,(一)形式语言理论 (二)语言和文法的直观概念 (三)字母表、串、语言 (四)文法和语言的形式定义 (五)文法的类型 (六)上下文无关文法及语法树 (七)句型的分析 (八)有关文法实用中的一些说明,(三)字母表、串、语言,字母表 定义:元素的非空有穷集合 例：=01 =ab,c 元素也称为符号，字母表也称符号集。

9、例：程序语言的字母表由字母数字和若干专用符号组成。,符号串 定义:由字母表中的符号组成的任何有穷序列 例： 0,00,10是字母表=01上的符号串 a,ab,aaca是=abc上的符号串 在符号串中，符号是有顺序的，顺序不同,代表不同的符号串，如:ab和ba不同 不含任何符号的符号串称为空串，用表示 注意:并不等于空集合 符号串长度: 符号串中含有符号的个数 如: |abc|=3| |=0,符号串的运算 符号串的连接：设x、y是符号串,它们的连接是把y的符号写在 x的符号之后得到的符号串xy 例如 x=ST，y=abu ，则 xy=STabu 显然x = x=x 符号串的方幂：把符号串a自身连

10、接n次得到的符号串an = aaaa (n个a) 例如 a1=a a2=aa a0=,符号串集合： 定义: 若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。 空集即 符号串集合的和与乘积(A和B为符号串集合) 和 A+B（或AB）=w | wA或 wB 乘积 AB =xy | xA且yB,若集合A = ab,cde B = 0,1 则 AB = ab0,ab1,cde0,cde1,注: A = A = A A= A = 注: = ,符号串集合的方幂: 设A是符号串的集合，则称Ai为符号串集A的方幂，其中i是非负整数。具体定义如下: A0 = A1 = A , A2 =

11、A A AK = AA.A(k个),集合的闭包 闭包 集合A的闭包A *定义如下： A * = A0 A1 A 2 A 3,例：设有字母表=0，1 则*=012 =,0,1,00,01,10,11,000, 即*表示上所有有穷长的串的集合。,正闭包 A+ = A1A2A3称为的正闭包 A + 表示上的除外的所有用穷长串的集合,注: * = 0+ 注: + = * = * ,字母表上的一个语言是上符合某种规则的一些符号串的集合 ，是*的一个子集 例如：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, 1. 集合ab,aabb,aaabbb,anbn,或 w|w*且w=anbn,n

12、1为字母表上的一个语言 2. 集合a,aa,aaa,或w|w*且w=an,n1为字母表上的一个语言 3.为字母表上的一个语言 4. 即 为字母表上的一个语言,(一)形式语言理论 (二)语言和文法的直观概念 (三)字母表、串、语言 (四)文法和语言的形式定义 (五)文法的类型 (六)上下文无关文法及语法树 (七)句型的分析 (八)有关文法实用中的一些说明,(一)形式语言理论 (二)语言和文法的直观概念 (三)字母表、串、语言 (四)文法和语言的形式定义 (五)文法的类型 (六)上下文无关文法及语法树 (七)句型的分析 (八)有关文法实用中的一些说明,(四)文法和语言的形式定义,1文法的定义 2文

13、法的简化表示法 3推导与归约 4句型、句子、语言的定义 5文法的等价,1文法的定义,产生式（规则） 产生式是一个有序对(,)，通常写作 （或:= ） 文法定义: 文法G(Grammar)定义为四元组（VN，VT，P，S） VN (Nonterminal)：非终结符集 VT (Terminal)：终结符集 P (Production)：产生式（规则）集合 S：开始符号或识别符号,S = ,go,:= := the := := :=monkey :=banana :=eat :=has :=the :=a,back,说明: V=VNVT，V称为文法G的字母表 P中产生式形如：,其中V+且至少含一个

14、非终结符，V* VN,VT和P是非空有穷集 VNVT= S是一个非终结符，且至少要在一条产生式左部出现 非终结符代表一个语言中的语法成分，是构成程序的一个语法成分，这个符号本身不会在程序中出现 终结符是组成程序的具体的符号,例1：文法G=(VN,VT,P,S) 其中：VN=S，VT=0，1，P=S0S1，S01 开始符为S 例2：文法G=(VN,VT,P,S) VN =标识符，字母，数字， VT =a,b,c,x,y,z,_,0,1,9， P=， ， ， a, , z， _， 0,9 ， S=,2文法的简化表示法,简化表示法:通常不用将文法的四元组表示出来，只写出产生式 约定： 第一条产生式的

15、左部是开始符号 或用GS表示S是开始符号 用大写字母（或用尖括号括起来）表示非终结符 用小写字母表示终结符 左部相同的产生式A,A可以记为A|， 其中“|”是“或”的意思，,分别称为侯选式,例3改写例2 文法GS： SA|SA|SD A_|a|b|z D0|1|9,3. 推导(Derivation)与归约(Reduction),直接推导和直接归约： 是文法G的产生式，若有v，w满足：v=,w=, 其中,V* 则称v直接推导出w,也称w直接归约到v, 记作 v w 或 w |- v 直接推导就是用产生式的右部替换产生式的左部的过程 直接归约就是用产生式的左部替换产生式的右部的过程,例 文法G：

16、S0S1，S01 有直接推导： S 0S1（ S0S1 ） 0S1 00S11（ S0S1 ） 00S11 000S111（ S0S1 ） 000S111 00001111（ S01 ）,推导和归约 若存在v=w0 w1 . wn=w ,(n0) 则称v推导出w，或w归约到v,记为v =+ w 若有v =+ w或v = w，则记作v =* w,例 文法G： S0S1， S01 S 0S1 00S11 000111 S =+ 000111 S =* 000111 S =* S,4句型、句子、语言的定义,句型和句子 设有文法GS，若符号串是从开始符推导出来的,即 S =* ，则称是文法G的句型。若

17、仅由终结符组成,即 S =* ，且VT*，则称是文法G的句子 例 文法GS： S0S1， S01 因为S 0S1 00S11 000S111 00001111 所以S,0S1 ,00S11 ,000S111,00001111都是G的句型 00001111是G的句子,语言的定义 由文法G生成的语言记为L(G),它是文法G的一切句子的集合,即 L(G)=x|S =* x，且 xVT* 例 文法G： S0S1， S01 S0S1 00S11 03S13 0n-1S1n-1 0n1n L(G)=0n1n|n1 文法和语言的关系： 文法G生成的每个串都在L(G)中 L(G)中的每个串确实能被G生成,根据

18、文法，可以通过推导得到该文法相应的语言； 例：GE：EE+T|TTTF|F F(E)|a EE+T T+T F+T a+T a+TF a+FF a+aF a+aa 表示一切能用符号a，+，(，)构成的算术表达式 有了语言的要求，也可以为该语言设计文法 例：若语言由0、1符号串组成，串中0和1的个数相同，构造其文法为：A 0B|1CB 1|1A|0BBC 0|0A|1CC,5文法的等价,若L(G1)=L(G2)，则称文法G1和G2是等价的。 例如 文法G1A：A0R A01 RA1 G2S：S0S1 S01 所定义的语言都是0n1n 故,两文法等价,(一)形式语言理论 (二)语言和文法的直观概念

19、 (三)字母表、串、语言 (四)文法和语言的形式定义 (五)文法的类型 (六)上下文无关文法及语法树 (七)句型的分析 (八)有关文法实用中的一些说明,(一)形式语言理论 (二)语言和文法的直观概念 (三)字母表、串、语言 (四)文法和语言的形式定义 (五)文法的类型 (六)上下文无关文法及语法树 (七)句型的分析 (八)有关文法实用中的一些说明,(五)文法的类型,通过对产生式施加不同的限制，Chomsky将文法分为四种类型： 0型文法(短语文法)：对任一产生式，都有(VNVT)*且至少含一个非终结符，(VNVT)*,1型文法(上下文有关)：是0型文法的特例，对P中的任一产生式，都|， 仅仅

20、S除外 例 文法GS： SaSBC SabCCBBC bBbb bCbc cCcc 1型文法产生式的一般形式是 A ， , V* ，AVN , V ,它表示当A的上文为且下文为时可把A替换成，因此称1型文法为上下文有关文法。,2型文法（上下文无关文法） ：它是1型文法的特例，对任一产生式，都有VN ， (VNVT)* 例 文法GS：SAB ABS|0 BSA|1 2型文法产生式的一般形式是: A，它表示不管A的上下文如何都可把A替换成，因此被称为上下文无关文法 通常程序设计语言的语法，可用2型文法来描述，因此重点研究,3型文法(正规文法)：它是2型文法的特例，任一产生式的形式都为 AaB或Aa

21、，其中A ，BVN ，aVT 例如 文法GS：S0A|1B|0 A0A|1B|0S B1B|1|0 在程序设计语言中，3型文法通常用来描述单词的结构。因此重点研究,四种文法之间的逐级“包含”关系,(一)形式语言理论 (二)语言和文法的直观概念 (三)字母表、串、语言 (四)文法和语言的形式定义 (五)文法的类型 (六)上下文无关文法及语法树 (七)句型的分析 (八)有关文法实用中的一些说明,(一)形式语言理论 (二)语言和文法的直观概念 (三)字母表、串、语言 (四)文法和语言的形式定义 (五)文法的类型 (六)上下文无关文法及语法树 (七)句型的分析 (八)有关文法实用中的一些说明,(六)上

22、下文无关文法及语法树,1上下文无关文法(Context-Free Grammar) 上下文无关文法有足够的能力描述现今程序设计语言的语法结构 A (AVN ， (VNVT)* ) 例：算术表达式：Ei|E+E|E*E|（E） i:=E if then | if then else ,2. 规范推导和规范句型 如果在推导的任何一步，其中、是句型，都是对中的最左（最右）非终结符进行替换,则称这种推导为最左(最右)推导 最右推导被称为规范推导 由规范推导所得的句型称为规范句型,例 文法G：EE + T|T TTF|F F(E)|i 句子i+ii的推导过程如下： 最左推导： E=E+T=T+T=F+T

23、=i+T=i+TF=i+FF =i+iF=i+ii 最右推导： E=E+T=E+TF=E+Ti=E+Fi=E+ii = T+ii=F+ii=i+ii,3.语法树（推导树Parse Tree） 作用:直观地描述上下文无关文法的句型推导过程。给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树,例：文法G：EE+T|TTTF|F F（E）|i 句型T+TF的推导过程与语法树,E=E+T,E=E+T,=E+TF,=T+TF,=T+T,=T+TF,从语法树中看不出句型中的符号被替代的顺序,从左到右读出叶子结点得到的符号串，为文法的句型。也把该语法树称为该句型的语法树。,例 文法

24、G：EE+T|T TTF|F F(E)|i 句子i+ii的推导过程如下： 最左推导： E=E+T=T+T=F+T=i+T=i+TF=i+FF =i+iF=i+ii 最右推导： E=E+T=E+TF=E+Ti=E+Fi=E+ii = T+ii=F+ii=i+ii,E=E+T =T+T =T+TF,E=E+T =E+TF =T+TF,4.文法的二义性(Ambiguity),文法G：EE+E|EE|（E）|i 句子 ii+i 对应的语法树,两个不同的最左推导： 推导1：E E+E EE+E iE+E ii+E ii+i 推导2：E EE iE iE+E ii+E ii+i,例,定义: 如果一个文法存

25、在某个句子对应两棵不同的语法树，则说这个文法是二义的。二义性文法存在某个句子,它有两个不同的最左（右）推导 对于一个程序设计语言来说，希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。,文法G1： EE+E | EE | (E) | i,文法G2： ET|E+T TF|TF F(E)| i,(一)形式语言理论 (二)语言和文法的直观概念 (三)字母表、串、语言 (四)文法和语言的形式定义 (五)文法的类型 (六)上下文无关文法及语法树 (七)句型的分析 (八)有关文法实用中的一些说明,(一)形式语言理论 (二)语言和文法的直观概念 (三)字母表、串、语言 (四)文法和语言的形式定义

26、 (五)文法的类型 (六)上下文无关文法及语法树 (七)句型的分析 (八)有关文法实用中的一些说明,(七)句型的分析,任务: 句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。 对于程序设计语言来说，句型分析就是一个识别输入符号串是否为语法上正确的程序的过程。,从左到右的分析算法即总是从左到右地识别输入符号串.句型分析算法采用从左到右的分析算法 句型的分析算法分类 自上而下分析法 (Top-Down parsing) 自下而上分析法 (Bottom-Up parsing),1 自上而下的分析方法,定义: 从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。

27、 语法树的构造：将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。,例 文法G：S cAd A ab A a识别输入串w=cabd是否为该文法的句子,S,推导过程：,=cabd,S,=cAd,自上而下方法的主要问题,不成功，不成功的原因是选错产生式Aa,自上而下分析的主要问题选择产生式 假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？,S,观察输入串cabd自上而下构造语法树的另一过程,G：S cAd A ab|a,2 自下而上的分析方法,定义:从输入符号串开始，逐步进行归约，直至归约到文法的开始符

28、号。 语法树的构造：从输入符号串开始，以它作为语法树的末端结点符号串，自底向上的构造语法树,例 文法G：S cAd A ab A a识别输入串w=cabd是否为该文法的句子,归约过程：,用“|-”表示归约，下划线部分为被归约符号,cabd,|-cAd,|-S,自下而上分析的主要问题 对输入串cabd的两种归约过程 （1）cabd|-cAd|-S 归约到开始符 （2）cabd|-cAbd 不能归约到开始符 在自下而上的分析方法中，每一步都是从当前串中选择一个子串加以归约，该子串暂称“可归约串”。 主要问题如何确定“可归约串”,为了刻划“可归约串”,引入下面的概念,G:ScAd Aab|a,短语，

29、直接短语和句柄 定义: 设是文法GS中的一个句型，如果有S=*A且A=+，则称是句型相对于非终结符A的短语 特别的如有A=，则称是句型相对于规则A的直接短语 一个句型的最左直接短语称为该句型的句柄(Handle) 句柄就是“可归约串”,go,例：文法GE: EE+T|T TTF|F F（E）| i 的一个句型是 TF+i，相应的语法树见右图：,因为E=* T+i 且 T=+ TF，所以 TF是句型相对于T的短语 因为E=* TF+F 且 F =+ i，所以 i 是句型相对于F的短语 因为E=* E 且E=+ TF+i，所以TF+i 是句型相对于E的短语 故句型的短语有： TF、 i、 TF+i

30、,back,例：文法GE: EE+T|T TTF|F F（E）| i 的一个句型是 TF+i，相应的语法树见右图：,句型的短语有： TF、 i、 TF+i 因为E=* T+i 且 T=TF，所以 TF 是句型相对于TTF的直接短语 因为E=* TF+F 且 F=i，所以 i 是句型相对于Fi的直接短语 因为E=* E 且E=+ TF+i（无法实现一步推导），所以 TF+i 不是句型的直接短语 故句型的直接短语有： TF、 i,back,例：文法GE: EE+T|T TTF|F F（E）| i 的一个句型是 TF+i，相应的语法树见右图：,句型的短语有： TF、 i、 TF+i 句型的直接短语有

31、： TF、 i 因为TF在最左, 故TF为句柄,back,例 文法G：EE+T|T TTF|F F(E)|i 句子i+ii的推导过程如下： 最左推导： E=E+T=T+T=F+T=i+T=i+TF=i+FF =i+iF=i+ii 最右推导： E=E+T=E+TF=E+Ti=E+Fi=E+ii = T+ii=F+ii=i+ii,文法GE:EE+T|T TTF|F F（E）|i 的一个句型 是TF+i,虽然F+i是句型TF+i的一部分， 但不是短语，因为尽管有E=+ F+i， 但是不存在从文法开始符 E=* TE的推导,例：文法GE: EE+T|T TTF|F F（E）| i 的一个句型是 TF+

32、i，相应的语法树见右图：,因为E=* T+i 且 T=+ TF，所以 TF是句型相对于T的短语 因为E=* TF+F 且 F =+ i，所以 i 是句型相对于F的短语 因为E=* E 且E=+ TF+i，所以TF+i 是句型相对于E的短语 故句型的短语有： TF、 i、 TF+i,短语与语法树 语法树中每棵子树的末端结点构成相对于子树根的短语,五棵子树,两层子树的末端结点构成直接短语 两棵两层子树对应两个直接短语： TF，i 位于最左边的两层子树的末端结点构成句柄： TF,例：文法GE的句型TF+i语法树,(子)树的边沿,三个短语：T F，i，T F+i,结论1,课堂习题 文法GS： SaAB

33、e AAbc|b Bd 试写出句子abbcde的归约过程,(一)形式语言理论 (二)语言和文法的直观概念 (三)字母表、串、语言 (四)文法和语言的形式定义 (五)文法的类型 (六)上下文无关文法及语法树 (七)句型的分析 (八)有关文法实用中的一些说明,(一)形式语言理论 (二)语言和文法的直观概念 (三)字母表、串、语言 (四)文法和语言的形式定义 (五)文法的类型 (六)上下文无关文法及语法树 (七)句型的分析 (八)有关文法实用中的一些说明,(八)有关文法实用中的一些说明,1 有关文法的实用限制 有害规则和多余规则,有害规则：UU ,无用且引起文法的二义 多余规则：所有句子推导都用不到

34、的规则，表现形式： 不可到达：不在任何句型中出现的非终结符的规则 不可终止：不可推出终结符号串的非终结符的规则,UU,例：文法GS： （1）SBe （2）BCe （3）BAf （4）AAe （5）Ae （6）CCf （7）Df 多余规则为： （7）不可到达 （6）不可终止 （2）也是多余的,不可终止：不可推出终结符号串的非终结符的规则,2 上下文无关文法中的规则 上下文无关文法中允许使用A产生式，A称为规则,(一)形式语言理论 (二)语言和文法的直观概念 (三)字母表、串、语言 (四)文法和语言的形式定义 (五)文法的类型 (六)上下文无关文法及语法树 (七)句型的分析 (八)有关文法实用中的一些说明,