第2章形式语言的基本知识精选PPT.ppt

第2章形式语言的基本知识第1页，此课件共68页哦二、二、符号串和符号串集合的运算符号串和符号串集合的运算 1.符号串相等符号串相等：若x、y是集合上的两个符号串，则xy，iff（当且仅当）组成x的每一个符号和组成y的每一个每一个符号依次相等。2.符号串的长度符号串的长度：x为符号串，其长度|x|等于组成该符 号串的符号个数。例：xSTR，|x|=3 3.3.符号串的联接符号串的联接：若x、y是定义在是上的符号串，且xXY，yYX，则x和y的联接 xyXYYX也是上的符号串。注意：一般xyyx，而xx第2页，此课件共68页哦例：Aa,b,B=c,d,AB=？4.符号串集合的乘积运算符号串集合的乘积运算：令A、B为符号串集合，定义 AB xy|xA,yB ac，ad，bc，bd 因为xxx，所以A=A=A符号串集合符号串集合：若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。例：=a，b，c A=a,aa,ac第3页，此课件共68页哦6.6.符号串集合的闭包运算符号串集合的闭包运算：设A是符号串集合，定义 A A1 A2 A3 An 称为集合A的正闭包。A*A0 A称为集合A的闭包。例：A=x,y A？A*？5.符号串集合的幂运算符号串集合的幂运算：有符号串集合A，定义A0=,A1=A,A2=AA,A3=AAA,AnAn-1A=AAn-1 ，n0 x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,A1 A2 A3,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,A0 A1 A2 A3第4页，此课件共68页哦的闭包的闭包*表示表示 上的一切符号串（包括上的一切符号串（包括）组成的集合）组成的集合的正闭包的正闭包+表示表示 上的上的除除外的所有符号串组成的集合外的所有符号串组成的集合例：例：=a,b=a,b *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,=a,b,aa,ab,ba,bb,aaa,aab,第5页，此课件共68页哦7.符号串的符号串的 前缀：前缀：s为符号串,把s从尾部删去若干个（包括0个）符号后所余下的部分称为s的前缀。符号串abc的前缀是什么？8.符号串的符号串的 后缀：后缀：s为符号串,把s从前部删去若干个（包括0个）符号后所余下的部分称为s的后缀。符号串abc的后缀是什么？第6页，此课件共68页哦若A为某语言的字母表 Aa,b,0,1,9,+,_/,(,),=.B为单词集 B=if,else,for,则B A*。语言的句子是定义在B上的符号串。若令C为句子集合，则C B*,程序 C为什么对符号、符号串、符号串集合以及它们的运算感兴趣？为什么对符号、符号串、符号串集合以及它们的运算感兴趣？第7页，此课件共68页哦语言语言是由句子组成的集合，是由一组符号所构成的集合是由句子组成的集合，是由一组符号所构成的集合字母表字母表 上上的一个语言是的一个语言是 上的一些符号串的集合上的一些符号串的集合字母表字母表 上上的每个语言是的每个语言是*的一个子集的一个子集 集合集合a,aa,aaa,a,aa,aaa,或表示为或表示为w|ww|w*且且w=aw=an n,n1,n1 为字母为字母表表 上上的一个语言的一个语言 例如：字母表=a,b,*=,a,b,aa,ab,ba,bb,aaa,aab,集合集合ab,aabb,aaabbb,ab,aabb,aaabbb,a,an nb bn n,或表示为或表示为w|ww|w*且且w=aw=an nb bn n,n1,n1为字母表为字母表 上上的一个语言的一个语言第8页，此课件共68页哦:=“=”:=“+”|“*”:=“(”“)”|文法文法第9页，此课件共68页哦赋值语句赋值语句标识符标识符表达式表达式表达式表达式表达式表达式表达式表达式标识符标识符整数整数标识符标识符表达式表达式y=x+r*6y =x+r*6第10页，此课件共68页哦3.2文法的非形式讨论文法的非形式讨论 1.什么是文法：文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称为“语法”）。例：有一句子：“我是大学生”。这是一个在语法、语义上都正确定句子，该句子的结构（称为语法结构）是由它的语法决定的。在本例中它为“主谓结构”。如何定义句子的合法性？有穷语言：只需逐一列举句子无穷语言：使用文法定义句子的结构，用适当条数的规 则把语言的全部句子描述出来。文法是以有穷的集 合刻划无穷的集合的工具。第11页，此课件共68页哦 2.2.语法规则语法规则：我们通过建立一组规则，来描述句子的语法结构结构。规定用“:=”表示“定义为”。:=:=|:=你|我|他:=王民|大学生|工人|英语:=:=是|学习:=|文法的BNF表示第12页，此课件共68页哦3.由规则推导推导句子：有了一组规则之后，可以按照一定的方式用它们去推导或产生句子。推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。=这种推导一直进行下去，直到所有带的符号都由终结符号替代为止。第13页，此课件共68页哦 =我我=我我 =我我是是 =我是我是=我是我是大学生大学生:=:=:=:=|:=:=你你|我我|他他:=:=王民王民|大学生大学生|工人工人|英语英语:=:=:=:=是是|学习学习:=:=|推导方法：推导方法：从一个要识别的符号从一个要识别的符号开始推导，即用相应规则的开始推导，即用相应规则的右部右部来替代规则的来替代规则的左部左部，每次仅用一条规则去进行推导。每次仅用一条规则去进行推导。第14页，此课件共68页哦例：有一英语句子：The big elephant ate the peanut.:=:=:=the:=big:=elephant:=:=ate:=:=peanut第15页，此课件共68页哦 =the =the big =the big elephant =the big elephant =the big elephant ate =the big elephant ate =the big elephant ate the =the big elephant ate the peanut:=:=:=:=:=:=the:=:=big:=:=elephant|peanut:=:=:=:=ate:=:=第16页，此课件共68页哦上述推导可写成=the big elephant ate the peanut+说明：(1)有若干语法成分同时存在时，我们总是从最左的语法成 分进行推导，这称之为最左推导（一般推导），类似的有最右推导。(2)从一组规则可推出不同的句子，如以上规则还可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它们 在语法上都正确，但在语义上都不正确。所谓文法文法是在形式上对句子结构的定义与描述，而未涉及语义问题。第17页，此课件共68页哦 4.语法树：我们用语法树来描述一个句子的语法结构。Thebigelephantatethepeanut语法成分（在形式语言中又称“非终结符”）单词符号（在形式语言中又称“终结符号”)第18页，此课件共68页哦3.3.1文法的定义文法的定义3.3 文法和语言的形式定义 定义1.文法GS=（Vn，Vt，P，S）Vn：非终结符号集 Vt：终结符号集 P：产生式或规则的集合 S：开始符号（识别符号）SVn，S至少要在 一条规则 中作为左部出现VVn Vt称为文法的字汇表规则：U:xU Vn,xV*补补:规则的定义规则的定义规则是一个有序对(U,x),通常写为:U:x 或U x第19页，此课件共68页哦文法GS=（Vn，Vt，P，S）Vn：代表程序的语法成份，如“赋值语句”，它不会 出现在程序中Vt：会出现在程序中，如i=i+1第20页，此课件共68页哦P=；0；1；9；S=；例：无符号整数的文法：G=（Vn，Vt，P，S）Vn,Vt =0,1,2,3,9第21页，此课件共68页哦几点说明几点说明：产生式左边符号构成集合Vn，且 S Vn有些产生式具有相同的左部，可以和在一起例、；|；0|1|2|3|9给定一个 文法，实际只需给出产生式集合，并指定识别符号例、G ；|；0|1|2|3|9第22页，此课件共68页哦3.3.2 推导的形式定义推导的形式定义 定义2：文法G（Vn，Vt，P，S）,若有vxUy，wxuy,其中x、y V*，UVn,u V*,若U:uP，则v w。若xy，有U:u，则U u根据文法和推导定义，可推出终结符号串，推出句子来。第23页，此课件共68页哦 1 1 0(6)=(1)=(3)(5)=(2)当符号串已没有非终结符号时，推导就必须终止。因为当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在规则左部，所以将在规则左部出现的符终结符不可能出现在规则左部，所以将在规则左部出现的符号称为非终结符号。号称为非终结符号。例如：例如：G (1)；(2)(3)(4)0|1|2|3|9文法G：vxUy，wxuy,其中x、y V*，UVn,uV*,若U:uP，则v w。若xy，有U:u，则U u第24页，此课件共68页哦 定义3：文法G，U0,U1,U2,，Un V+if v=U0 U1 U2 Unw，且n0 则称v产生w，或w归约到v，并记作 v=w =例：=1 =1 0即 10=第25页，此课件共68页哦 定义4：文法G，v，w V+if v w,或v=w，则v w *=定义5：规范推导：有xUy=xuy,if y Vt*,则此推导为规范的|直观意义：规范推导最右推导最右推导：若符号串中有两个以上的非终结符时，先推右边的。最左推导：若符号串中有两个以上的非终结符时，先推左边的。第26页，此课件共68页哦3.3.3 语言的形式定义语言的形式定义 定义6：文法GS （1）句型句型：x是句型 S x,且xV*；（2）句子句子：x是句子 S x,且xVt*；（3）语言语言：L（GS）=x|xVt*,S x；*文法GS所产生的所有句子的集合 形式语言理论可以证明以下两点：（1）G L（G）；（2）L(G)G1，G2，Gn；已知文法，求语言，通过推导；已知语言，构造文法，无形式化方法，更多是凭经验*句子是所有终结符号组成的句型第27页，此课件共68页哦例例3.1：GS S:=:=aSb|ab求其所产生的语言。求其所产生的语言。若S:=:=aSb|，如何？L(GS)=anbn|n1L(GS)=anbn|n0已知文法，求语言，通过推导课堂练习1：GS S:=:=bA A:=:=aA|aL(GS)=ban|n1课堂练习2：GS S:=:=AB A:=:=aA|a B:=:=bB|bL(GS)=ambn|m,n1第28页，此课件共68页哦例3.2：abna|n1,构造其文法 定义7.G和G是两个不同的文法，若 L(G)=L(G),则G和G为等价文法。若n0，如何？课堂练习3：anbnci|n1,i 0,构造其文法 GS：S AB A aAb|ab BcB|G1S：SaBa,Bb|bBG2S：SaBa,Bb|BbG1S：SaBa,B|bBG2S：SaBa,B|Bb第29页，此课件共68页哦3.3.4 递归文法递归文法1.递归规则递归规则：规则右部有与左部相同的符号 对于 U:=xUy 若x=,即U:=Uy，左递归；若y=,即U:=xU，右递归；2.递归文法递归文法：文法G，存在U Vn if U=U,则G为递归文法；if U=U,则G为左递归文法；if U=U,则G为右递归文法；+第30页，此课件共68页哦4.递归文法的优点：可用有穷条规则，定义无穷语言 例：对于前面给出的无符号整数的文法是有递归文法，用13条规则就可以定义出所有的无符号整数。若不用递归文法，那将要用多少条规则呢？!3.左递归文法的缺点：不能用自顶向下的方法来进行语法分析会造成死循环（后面将详细论述）第31页，此课件共68页哦3.3.5 句型的短语、简单短语和句柄句型的短语、简单短语和句柄定义8.给定文法GS,w=xuyV+，为该文法的句型,若 S=xUy,且U=u,则u是句型w相对于U的短语；若 S=xUy,且U=u,则u是句型w相对于U的简单短语。其中U Vn，u V+，x,y V*直观理解：短语是前面句型中的某个非终结符所能推出的短语是前面句型中的某个非终结符所能推出的符号串符号串。第32页，此课件共68页哦(5)句型10短语 10,1,0简单短语 1,0定义8.给定文法GS,w=xuyV+，为该文法的句型,若 S=xUy,且U=u,则u是句型w相对于U的短语；若 S=xUy,且U=u,则u是句型w相对于U的简单短语。其中U Vn，u V+，x,y V*直观理解：短语是前面句型中的短语是前面句型中的某个非终结符所能推出的符号串某个非终结符所能推出的符号串。=1 =1 0=0 =0 =1 0第33页，此课件共68页哦定义9.任一句型的最左简单短语称为该句型的句柄句柄。给定句型找句柄的步骤：短语 简单短语 句柄注意：短语、简单短语是相对于句型而言，一个句型可能有多个短语、简单短语，句柄只能有一个。第34页，此课件共68页哦3.4文法和语言的分类 形式语言(乔姆斯基)：通过抽象，对语言进行形式化描述*的任何子集称作的任何子集称作 上的形式语言上的形式语言 由文法定义语言：L（GS）=x|xVt*,S=x+第35页，此课件共68页哦 文法和语言分类：0型、1型、2型、3型 这几类文法的差别在于对产生式施加不同的限制。0型：P：u:=v 其中uV，u中至少含有一个非终结符，vV*0型语言：L0 0型文法称为无约束短语结构文法。规则的左部和右部都可以是符号串，一个短语可以产生另一个短语。第36页，此课件共68页哦SACaBSACaBaBBaaBBaCBECBE aDDaaDDaADACADACaEEaaEEaAEAE例：例：0 0型型文法文法GSGS：第37页，此课件共68页哦 1型：P：xUy:=xuy 其中 UVn，x、yV*，uV 1型语言：L1称为上下文敏感或上下文有关。也即只有在x、y这样的上下文中才能把U改写为u第38页，此课件共68页哦SaSBESaSBEaBcabcaBcabc bBdbbdbBdbbd BEdBedBEdBedeEBeaBeEBeaB例：例：1 1型（上下文有关）文型（上下文有关）文法法GSGS：第39页，此课件共68页哦 2型：P：U:=u 其中 UVn，uV*2型语言：L2 称为上下文无关文法。也即把U改写为u时，不必考虑上下文。第40页，此课件共68页哦例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS：SABABABS|0BS|0BSA|1SA|1 S第41页，此课件共68页哦（右线性）P：U:=a 或 U:=aA 其中 U、AVn aVt3型语言：L3 又称正则语言.3型文法称为正则文法。它是对2型文法进行进一步限制。左线性 和右线性文法是相互等价的（左线性）P：U:=a 或 U:=Aa 其中 U、AVn aVt 3型文法：第42页，此课件共68页哦GS：S0A|1B|00A|1B|0 A0A|1B|0S0A|1B|0S B1B|1|01B|1|0GI：I lT lTI l lT lT lTT dT dTT l lT d d例：例：3 3型文法型文法第43页，此课件共68页哦根据上述讨论，L0 L1 L2 L30型文法可以产生L0、L1、L2、L3，但2型文法只能产生L2，不能产生L1。2型文法型文法1型文法型文法0型文法型文法3型文法型文法四种文法之间的逐级四种文法之间的逐级“包含包含”关系关系第44页，此课件共68页哦2 2型文法型文法（不确定（不确定的下推自动机）的下推自动机）1 1型文法型文法（不确定（不确定的界限自动机）的界限自动机）0 0型文法型文法（图灵机）（图灵机）3 3型文法型文法（有限（有限自动机）自动机）形式语言与自动机形式语言与自动机第45页，此课件共68页哦图灵机图灵机第46页，此课件共68页哦3.5 上下文关文法及其语法树3.5.1 推导与语法树推导与语法树（1）语法树：句子结构的图示表示法，它是一种有向图，由结点和有向边组成。结点：符号 根结点：识别符号识别符号 中间结点：非终结符非终结符 叶结点：终结符或非终结符终结符或非终结符 有向边：表示结点间的派生关系。SUVabcd第47页，此课件共68页哦 注意一个重要事实：文法所能产生的句子，可以 用不同的推导原则（使用产生式顺序不同）将其 推导出来。语法树的生长过程不同，但最终生成的语 法树形状完全相同。把产生相同语法树的推导看作是 等价的。某些文法有此性质，而某些文法不具此性质。(2)句型的推导及语法树的生成（自顶向下）给定GS，句型w：可建立推导序列，S=w 可建立语法树，以S为树根结点，每步推导生成语法树的一枝，最终可生成句型的语法树。G*第48页，此课件共68页哦 1(1)(2)(4)(5)(3)0最右推导：例如：例如：G (1)；(2)(3)(4)0|1|2|3|9第49页，此课件共68页哦(3)子树与短语 子树：由语法树中的某个结点（子树的根）连同它向下派生的部分所组成。短语：短语：某子树的所有叶子结点叶子结点自左向右顺序为句型中的符号串，则该符号串为该句型相对于该子树根的短语。简单短语：简单短语：简单子树简单子树（只有父子两代父子两代）叶子结点所组成的符号串。句柄：句柄：最左最左简单子树叶子结点所组成的符号串。只需画出句型的语法树，然后根据子树找短语简单短语句柄。第50页，此课件共68页哦 (1)(2)(4)1(5)(3)0(2)句型数字串 数字短语数字串 数字简单短语数字串 数字句柄数字串 数字(3)句型数字串0短语数字串 0,0简单短语0句柄0(4)句型数字0短语数字 0,数字,0简单短语数字,0句柄数字(5)句型10短语 10,1,0简单短语 1,0句柄 1(1)句型数字串 短语数字串简单短语数字串句柄数字串短语：短语：某子树的所有叶子结点叶子结点自左向右顺序为句型中的符号串，则该符号串为该句型相对于该子树根的短语。简单短语：简单短语：简单子树简单子树（只有父子两代父子两代）叶子结点所组成的符号串。句柄：句柄：最左最左简单子树叶子结点所组成的符号串。短语：短语：某子树的所有叶子结点叶子结点自左向右顺序为句型中的符号串，则该符号串为该句型相对于该子树根的短语。简单短语：简单短语：简单子树简单子树（只有父子两代父子两代）叶子结点所组成的符号串。句柄：句柄：最左最左简单子树叶子结点所组成的符号串。短语：短语：某子树的所有叶子结点叶子结点自左向右顺序为句型中的符号串，则该符号串为该句型相对于该子树根的短语。简单短语：简单短语：简单子树简单子树（只有父子两代父子两代）叶子结点所组成的符号串。句柄：句柄：最左最左简单子树叶子结点所组成的符号串。第51页，此课件共68页哦定义8.给定文法GS,w=xuyV+，为该文法的句型,若 S=xUy,且U=u,则u是句型w相对于U的短语；若 S=xUy,且U=u,则u是句型w相对于U的简单短语。其中U Vn，u V+，x,y V*(1)(2)(4)1(5)(3)0(5)句型10短语 10,1,0简单短语 1,0句柄 1 第52页，此课件共68页哦例如：例如：GEE T E+T F F T*FF (E)i句型句型i*i+i的短语、直接短语和句柄的短语、直接短语和句柄ETE+TFT*FFi1i2i3 句型i1*i2+i3 短语 i1,i2,i3,i1*i2,i1*i2+i3 简单短语 i1,i2,i3句柄 i1 第53页，此课件共68页哦(4)树与推导句型推导过程句型语法树的生长过程 由推导构造语法树由推导构造语法树1从识别符号开始，逐步建立推导序列。由根结点开始，自上而下建立语法树。第54页，此课件共68页哦例：G句型10=0 0=0=110=规范推导第55页，此课件共68页哦 由语法树构造推导由语法树构造推导2自下而上地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次规约。从句型开始，自右向左地逐步进行规约，建立推导序列。定义12.对句型中最左简单短语（句柄）进行的规约称为 规范规约。第56页，此课件共68页哦01=0=10 0=规范规约与规范推导互为逆过程第57页，此课件共68页哦定义13.通过规范推导或规范规约所得到的句型称为规范句型。在上例中，就不是规范句型，因为：=不是规范推导第58页，此课件共68页哦3.5.2 文法的二义性文法的二义性下面举一个二义性文法的例子：GE:E:=E+E|E*E|(E)|i Vn=E Vt=+,*,(,),i 课堂练习：对于句子Sii *i ，给出两种不同的规范推导，并画出语法树定义14.1 若一个文法的某句子存在两个不同的最右(最左)推导，则该文法是二义性的，否则是无二义性的。第59页，此课件共68页哦 对于句子Sii *i L（GE），存在不同的规范推导：EEE+EE*iiiEEE*EE+iii这两种不同的推导对应了两种不同的语法树(1)E=E+E=E+E*E=E+E*i=E+i*i=ii *i(2)E=E*E=E*i=E+E*i=E+i*i=ii*i第60页，此课件共68页哦 以上是自顶向下来看文法的二义性，我们还可以自底向上来看文法的二义性。上例中，规范句型E+E*i 是由ii *i通过两步规范规约得到的，但对于同一个句型E+E*i，它有两个不同的句柄句柄（对应上述两棵不同的语法树）：i 和 EE。因此语法的二义性意味着句型的句柄不唯一。第61页，此课件共68页哦EEE+EE*iEEE*EE+i句柄：i句柄：EE 定义14.2 若一个文法的某规范句型的句柄不唯一，则该文法是二义性的，否则是无二义性的。第62页，此课件共68页哦 若文法是二义性的，则在编译时就会产生不确定性，遗憾的是在理论上已经证明：文法的二义性是不可判定的，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。改写文法，把排除二义性的规则合并到原有文法中改写文法，把排除二义性的规则合并到原有文法中第63页，此课件共68页哦EiET+TF*iFTFi例例:算术表达式的文法算术表达式的文法 E:=E+E|E*E|(E)|iE:=E+T|TT:=T*F|FF:=(E)|i第64页，此课件共68页哦3.7 有关文法的实用限制1、若文法中有如U:=U的规则，则这就是有害规则，它会引起二义性，而无任何用处。例如存在U:=U，U:=a|b,则有两棵语法树：UaUUa文法中不能含有有害规则和多余规则，。第65页，此课件共68页哦 2、多余规则：（1）某条规则U:=u的左部非终结符U（U不是识别符号），不在任何其他规则右部出现，即所有的推导始终不会用到此规则。（2）在推导句子的过程中，一旦使用了该规则，将推不出任何终结符号串。即该规则中含有推不出任何终结符号串的非终结符。例如给定GS，若其中关于U的规则只有如下一条：U:=xUy 该规则是多余规则。若还有U:=a，则此规则并非多余若某文法中无有害规则或多余规则，则称该文法是压缩过的。第66页，此课件共68页哦小小 结结内容：内容：符号串和符号串集合的运算、文法和语言的定义符号串和符号串集合的运算、文法和语言的定义几个重要概念：递归、短语、简单短语和句柄、语法树、文法的二义性、文几个重要概念：递归、短语、简单短语和句柄、语法树、文法的二义性、文法的实用限制等法的实用限制等文法和语言的分类文法和语言的分类重点：重点：在理解基本概念的基础上在理解基本概念的基础上会求句型的短语、简单短语和句柄会求句型的短语、简单短语和句柄根据给定的语言写出文法、根据给定的文法确定语言根据给定的语言写出文法、根据给定的文法确定语言判断文法的二义性判断文法的二义性难点：难点：关于文法和语言的概念是形式语言的理论基础，形式语言抽象地定关于文法和语言的概念是形式语言的理论基础，形式语言抽象地定义为一个数学系统义为一个数学系统“形式形式”是指：语言的所有规则以符号串的方式来描述。文法就是这样一个是指：语言的所有规则以符号串的方式来描述。文法就是这样一个工具工具推导，文法与语言的相互转换推导，文法与语言的相互转换第67页，此课件共68页哦思考题思考题1.已知文法已知文法GA，写出它定义的语言描述，写出它定义的语言描述 如：如：GA:A 0B|1C B 1|1A|0BB C 0|0A|1CC答案答案:L=w|w 0,1+，且且0和和1的个数相同的个数相同或或GA定义的语言由定义的语言由0、1符号串组成，串中符号串组成，串中0和和1的个数相同的个数相同.2.给出语言描述，构造文法给出语言描述，构造文法.如：构造一文法如：构造一文法,其定义的语言是由算符其定义的语言是由算符+,*,(,)和运算对象和运算对象a构成的算术表达式的集合构成的算术表达式的集合.答案答案1:GE EE+T|T TT*F|F F(E)|a答案答案2:GE EE+E|E*E|(E)|a第68页，此课件共68页哦