《形式语言理论》PPT课件.ppt

《《形式语言理论》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《形式语言理论》PPT课件.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章 形式形式语言理言理论形式语言nChomsky于1956年提出了一种用来描述语言的数学系统。人们把用一组数学符号和规则来描述语言的方式称为形式描述，而把所用的数学符号和规则称为形式语言。n形式语言，只是从语法上研究语言。它是抽象的数学系统，用于模拟程序设计语言的语法，或者是并不很成功地模拟自然语言如英语的语法。n形式语言理论是编译理论的重要基础，它主要研究组成符号语言的符号串的集合及它们的表示法、结构与特性。形式语言和编译理论中的最基本概念符号串和符号串集合2.1字母表和符号串1.字母表定义:元素的非空有穷集合，记为。例：=01 =ab,c元素也称为符号，字母表也称符号集。程序语言

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

3、如 a1=a a2=aa a0=4.符号串集合：定义:若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。符号串集合的乘积：符号串集合A和B的乘积定义为:AB=xy|xA且yB，即AB是由A中的串x和B中的串y连接而成的串xy组成的集合。若集合A=ab,cde B=0,1 则 AB=ab0,ab1,cde0,cde1 显然 A=A=A符号串集合的方幂:设A是符号串的集合，则称Ai为符号串集A的方幂，其中i是非负整数。具体定义如下:qA0=qA1 =A ,A2 =A AqAK=AA.A(k个)5.集合的闭包闭包集合的闭包*定义如下：*=0 1 2 3例：设有字母表=0，1则*

4、=012=,0,1,00,01,10,11,000,即*表示上所有有穷长的串的集合。正闭包+=123称为的正闭包。+表示上的除外的所有有穷长串的集合自反闭包*=0+=*=*2.2文法和语言1、文法定义:文法G(Grammar)定义为四元组（VN，VT，P，S）VN(Nonternimal)：非终结符集VT(Terminal)：终结符集P (Production)：产生式（规则）集合S：开始符号或识别符号q说明:V=VNVT，V称为文法G的字母表P中产生式形如：,其中V+且至少含一个非终结符，V*VN,VT和P是非空有穷集VNVT=S是一个非终结符，且至少要在一条产生式的左部出现非终结符代表一个

5、语言中的语法成分，如，它是构成程序的一个语法成分，这个符号本身不会在程序中出现，而终结符是组成程序的具体的符号。2.推导和规范推导：是文法G的产生式，若有v，w满足：v=,w=,其中,V*则称v直接推导出w,也称w直接归约到v,记作 v w直接推导就是用产生式的右部替换产生式的左部的过程直接归约就是用产生式的左部替换产生式的右部的过程2、直接推导序列：或 +若存在v=u0 u1.un=w,(n0)则称v +w，v推导出w，或w归约到v（至少有1步推导），这个直接推导序列的长度为n。3、广义推导：或 *若有v +w 或 v=w，则记为v *w，v广义推导出w，w广义规约到v（可以包含0步推导）+

6、*三种推导的比较n直接推直接推导（）的）的长度度为1 1n直接推直接推导序列（序列（+）的）的长度度n1n1n广广义推推导（*）的）的长度度00规范推导与规范规约n考虑两种特殊推导：最左推导和最右推导，即 对于一个推导序列中的每一步直接推导，都是对最左（最右）非终结符进行替换。n最右推导也称规范推导，它的逆过程称为最左规约，也称规范规约。2.3 文法的分类 Chomsky对文法中的规则施加不同限制，将文法和语言分为四大类：v0型文法（PSG）0型语言或短语结构语言v1型文法（CSG）1型语言或上下文有关语言v2型文法（CFG）2型语言或上下文无关语言v3型文法（RG）3型语言或正则（正规）语言

7、n如果对于某文法G，P中每个规则具有下列形式：其中V+，V*，则该文法G为（Chomsky）0型文法或短语结构文法。相应的语言 称为0型语言或短语结构语言。n如文法G，其中VN=A,B,S VT=0,1 P=S0AB 1B0 BSA|01 A1SB1 A0S0B 0型文法1型文法(上下文有关)它是0型文法的特例,对P中的任一产生式，都有|1，仅仅 S除外,但S不得出现在任何产生式的右部。例 文法GS：SaSBE SaBEEBBEaBab bBbb bEbe eEee1型文法产生式的一般形式是 A，,V*，AVN,V，它表示当A的上文为且下文为时可把A替换成，因此称1型文法为上下文有关文法。2

8、2型文法（上下文无关文法）型文法（上下文无关文法）它是它是1 1型文法的特例，型文法的特例，对任一任一产生式生式，都有，都有VVN N ，(V(VN NVVT T)*例例 文法文法GSGS：SAB ABS|0 BSA|1SAB ABS|0 BSA|12 2型文法型文法产生式的一般形式是生式的一般形式是:A:A，它表示不管它表示不管A A的上下文如何都可把的上下文如何都可把A A替替换成成，因此被称，因此被称为上下文上下文无关文法。无关文法。通常程序通常程序设计语言的文法，可用言的文法，可用2 2型文法来描述，因型文法来描述，因此我此我们重点研究重点研究2 2型文法。型文法。3型文法(右线性文法

9、和正规文法)它是2型文法的特例，任一产生式的形式都为 AaB或 Aa，其中A，BVN，aVT*在正规文法中，任一产生式的形式都为 AaB或 Aa，其中A，BVN，aVT 例如 文法GS：S0A|1B|0A0A|1B|0SB1B|1|0在程序设计语言中，正规文法通常用来描述单词的结构。文法类别产生式形式产生的语言说明0型文法(短语文法)V+,且至少含一个非终结符，V*0型语言对产生式基本无限制1型文法(上下文有关文法)，|1型语言（上下文有关语言）将A替换成时，必须考虑A的上下文2型文法(上下文无关文法)A，AVN，V*2型语言（上下文无关语言）无需考虑A在上下文中的出现情况3型文法(正规文法)

10、AaB 或 Aa，A,BVN，aVT3型语言(正规语言)产生式全部是规定的形式四种文法之四种文法之间的逐的逐级“包含包含”关系关系2型文法型文法1型文法型文法3型文法型文法0型文法型文法2.4语言和语法1、句型和句子设有文法GS，若符号串是从开始符推导出来的,即 S=*，则称是文法G的句型。若仅由终结符组成,即 S=*，且VT*，则称是文法G的句子。例 文法GS：S0S1，S01因为S 0S1 00S11 000S111 00001111所以S,0S1,00S11,000S111,00001111都是G的句型,00001111是G的句子由规范推导所得的句型称为规范句型2、语言的定义由文法G生成

11、的语言记为L(G),它是文法G的一切句子的集合,即 L(G)=x|S=*x，且 xVT*例 文法G：S0S1，S01S0S1 00S11 03S13 0n-1S1n-1 0n1nL(G)=0n1n|n13、文法和语言的关系：文法G生成的每个终结符号串都在L(G)中L(G)中的每个串确实能被G生成2.语法树1、定义：语法树是这样的一个语法结构，它的结点由符号组成。根结点对应于开始符号。只有非终结符号对应的结点有子结点。并且，一个结点和它的子结点分别对应于文法中的一个规则的左部和右部。2、引入语法树的意义：作为识别句子的辅助工具，语法树可以表示句子的结构。这一点对于其后的语义分析有非常重要的意义。

12、3、作用:直观地描述上下文无关文法的句型推导过程。给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树语法树的相关概念n结点：每个树的结点对应于一个符号。结点的名字就是该符号。n边：两个结点之间的连线。n根结点：没有边进入的结点。n分支：某个结点向下射出的边和其结点称为分支。（父子结点，兄弟结点）n子树：语法树的某个结点和它向下射出的部分n末端结点：没有向下射出的边的结点成为末端结点。在相对于句型的语法树中，末端结点可能是非终结符号。语法树的特征 给定文法G，G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树（推导树）。这棵树具有下列特征：1、根结点的

13、标记是开始符号S；2、每个结点的标记都是V中的一个符号；3、若一棵子树的根结点为A，且其所有直接子孙的标记从左向右的排列次序为A1A2AR，那么 A A1A2.AR一定是P中的一条规则；4、若一标记为A的结点至少有一个除它以外的子孙，则AVN5、若树的所有叶结点上的标记从左到右排列为字符串w，则w是文法G的句型；若w中仅含终结符号，则w为文法G所产生的句子。构造语法树n方法：把开始符号做为根结点，对每一个直接推导画一个分支，分支的名字是直接推导中被替换的非终结符号，直到再无分支可画结束。n例如：推导S AB AcBd Accdd abccddSBBdbaAcdc语法树的构造过程S AB AcB

14、d Accdd abccddSSBASBBdAcSBBdAcdcSBBdbaAcdc（1）（2）（3）（5）（4）例：文法G：EE+T|TTTF|F F（E）|i句型T+TF的推导过程与语法树EET+TFTE=E+TEET+TFTE=E+T=E+TF=T+TF=T+T=T+TF从从语法法树中看不出句型中的符号被替代的中看不出句型中的符号被替代的顺序序从左到右从左到右读出叶子出叶子结点得到的符号点得到的符号串串，为文法文法的句型。也把的句型。也把该语法法树称称为该句型的句型的语法法树。2.5 文法和语言的一些特性 1 1、无用非无用非终结符：符：某个非终结符不出现在文法的任何一个句型中，并且不能

15、从它推出终结符号串。含有该非终结符的规则即不可终止。2、不可达文法符号：如果一个非终结符不出现在该文法的任何其他的产生式的右部。该非终结符为不可达文法符号，含有该非终结符的规则即不可达规则3、有害规则：UU ,无用且引起文法的二义4、可空非终结符：2型文法允许以下产生式 S，该产生式称为空产生式，S称为可空非终结符。在消除左递归方法中用到空产生式。例：文法GS：（1）SBe （2）BCe（3）BAf（4）AAe （5）Ae（6）CCf（7）Df 多余规则为：（6）不可终止 （7）不可到达文法G：EE+E|EE|（E）|i句子 ii+i 对应的语法树两个不同的最左推两个不同的最左推导：推推导1

16、1：E E E E+E+E E EEE+E+E i iE E+E+E i ii i+E E ii+ii+i i推推导2 2：E E E EEE i iE E i iE E+E+E i ii i+E E ii+ii+i iiEE+EEEiiEEEiEE+ii2.52.5文法的二文法的二义性性(Ambiguity)(Ambiguity)如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的。二义性文法存在某个句子,它有两个不同的最左（右）推导。为什么要避免文法产生二义性？n二义性的文法将给编译程序的执行带来问题。当编译程序对二义性文法生成的句子结构进行语法分析时，就会产生两种甚至更多种

17、不同的理解。语法结构上的不确定性，必将导致语义处理上的不确定性。因此，希望描述语言的文法是无二义性的。如何消除文法的二义性？(1)n方法一：不改变文法中原有的语法规则，仅加进一些语法的非形式规定。n如1：对于文法 GE:E i E E+E E E*E E (E)规定运算符优先顺序和结合律，即*优先于+，+、*服从左结合。如何消除文法的二义性？(2)n方法二：构造一个等价的无二义性的文法，即把排除二义性的规则合并到原有文法中，改写原有的文法。n如文法 GE:E i E E+E E E*E E (E)将运算符的优先顺序和结合规则加到原有文法中，则可构造无二义性的文法 GE:E T|E+T T F|

18、T*F F （E）|i2.6 分析方法简介 对于2型文法,如何识别一个符号串是否为某文法的句型或句子，有两种分析方法：自顶向下分析法(Top-Down parsing)自底向上分析法(Bottom-Up parsing)2.6.1 自顶向下的分析方法1、定义:从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。2、语法树的构造：将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。例 文法G：S cAd A ab A a识别输入串w=cabd是否为该文法的句子S推推导过程：程：cAdab=cabdS=cAd3、自顶向下方法的主要问题对

19、输入串cabd自上而下构造语法树的另一过程不不成成功功，不不成成功功的的原原因因是是选错产生式生式AaAa自自顶向下分析的主要向下分析的主要问题是是选择产生式生式 :假定要被代假定要被代换的最左非的最左非终结符号是符号是B B，且有，且有n n条条规则：BABA1 1|A|A2 2|A|An n，那么如何确定用哪个右部去，那么如何确定用哪个右部去替代替代B B？只能？只能试探性地构造，如果探性地构造，如果选错了了产生式，生式，必必须退回原来的状退回原来的状态，往前回退称，往前回退称为回溯。回溯。ScA da2.6.2 确定的自顶向下的分析方法 当文法的某一个非终结符有几条产生式、而且每条产生式

20、右部都是终结符时，应保证它们是互不相同的终结符。2.6.3 自底向上的分析方法1、定义:从输入符号串开始，在其中寻找句柄，此句柄如果与某一产生式右部相匹配，就用产生式左部去替换句柄，替换之后得一新符号串，继续进行同样的句柄替换处理。这种处理过程是一种归约过程，直至归约到文法的开始符号。2、语法树的构造：从输入符号串开始，以它作为语法树的末端结点符号串，自底向上的构造语法树例 文法G：S cAd A ab A a识别输入串w=cabd是否为该文法的句子cabd归约过程：程：用用“|-”“|-”表示表示归约，下划，下划线部分部分为被被归约符号符号cabd|-cAd|-SAS3、自底向上分析的主要问

21、题对输入串cabd的两种归约过程（1）cabd|-cAd|-S 归约到开始符（2）cabd|-cAbd 不能归约到开始符在自下而上的分析方法中，每一步都是从当前串中选择一个子串加以归约，该子串暂称“可归约串”。如何确定“可归约串”是自下而上分析的主要问题。为了刻划了刻划“可可归约串串”,”,引入下面的概念引入下面的概念1、短语，直接短语和句柄定义:设是文法GS中的一个句型，如果有S=*A且A=+，则称是句型相对于非终结符A的短语特别的如有A=，则称是句型相对于规则A的简单短语。一个句型的最左简单短语称为该句型的句柄(Handle)。句柄就是“可归约串”文法在内存中的表示n在计算机中，可以为相关文法建立一个产生式表，把文法的所有产生式都放在这个产生式表中。为了在自下而上分析过程中迅速找到可规约子串相匹配的产生式右部，可以为产生式建立一个目录表。在目录表的每一项中，都存放着一个产生式右部的尾符号和一个指针，这个指针指示该产生式在产生式表中的位置。具有相同产生式右部尾符号的产生式被连接成一个产生式链。