搜索
13.3.3形式语言与自动机简介对0型文法施加以下第i条限制，即得到i型文法。1.G的任何产生式α→β（S→ε除外）满足|α|≤|β|；2.G的任何产生式形如A→β，其中A∈N，β∈(N∪T)*；3.G的任何产生式形如A→a或者A→aB(或者A→Ba)，其中A和B∈N，a∈T。■文法、语言与自动机文法语言自动机短语文法(0型)短语结构语言图灵机CSG(1型)CSL线性界线自动机CFG(2型)CFL下推自动机正规文法(3型)正规集有限自动机定义3.8若文法G=(N，T，P，S)的每个产生式α→β中，均有α∈(N∪T)*，且至少含有一个非终结符，β∈(N∪T)*，则称G为0型文法。23.3.3形式语言与自动机简介（续）L3={anbncn|n≥1}L3'={ambmcn|m,n≥1}（S→ACA→aAb|abC→cC|c）L3''={akbmcn|k，m，n≥1}（a+b+c+）例3.15L3可用下述CSG描述：S→aSBC(1)S→aBC(2)CB→BC(3)aB→ab(4)bB→bb(5)bC→bc(6)cC→cc(7)句子akbkck的推导：S=...=ak-1S(BC)k-1(by1)=ak(BC)k(by2)=...=akBkCk(by3)=akbBk-1Ck(by4)=...=akbkCk(by5)=akbkcCk-1(by6)=...=akbkck(by7)结论：0型文法、CSG、CFG、正规式能力递减但是：能力越强的文法，其文法的设计和自动机的构造越困难因此：语法分析仅用到CFG（除特别指出，文法即指CFG）再考察L3：0型文法CSGCFG正规文法语言0型语言CSLCFL正规集∪∪∪33.4自上而下语法分析3.4.1自上而下分析的一般方法用推导的方法分析输入序列（记号流）：基本思想：•对任何一个输入序列ω，从S开始进行最左推导，直到得到一个合法的句子或发现一个非法结构。特点：•在推导的过程中，从左到右扫描输入序列，并试图用一切可能的方法，自上而下建立它的分析树。•自上而下分析是一种试探的过程，是反复使用不同产生式谋求与输入序列匹配的过程。43.4.1自上而下分析的一般方法（续1）例3.20用下述文法分析输入序列：cadS→cAdA→ab|a问题：•若有A→αβ1|αβ2，(公共左因子)，则会虚假匹配和大量回溯；造成分析效率低、语义动作难以恢复、以及出错位置的报告不确切等。•若有A→Aα，(左递归)，则死循环使分析无法进行下去。重写文法：1.提取左因子，以避免回溯。2.消除左递归，以避免陷入死循环；ScAdScAdabScAdaAAαAα......X53.4.2消除左递归定义3.9若文法G中的非终结符A，对某个文法符号序列α存在推导AAα，则称G是左递归的。若G中有形如A→Aα的产生式，则称该产生式对A直接左递归。■1消除文法的直接左递归考虑：A→Aα|β产生的语言：替换为：A→βA'A'→αA'|ε消除了一个直接左递归+βα*61消除文法的直接左递归(续1)A→Aα1|Aα2|...|Aαm|β1|β2|...|βn其中αi非空，βj均不以A开始。然后用下述产生式代替A产生式：算法3.1消除直接左递归A→β1A'|β2A'|...|βnA'A'→α1A'|α2A'|...|αmA'|ε■输入含直接左递归的G输出等价的不含直接左递归的G'方法对于每个含直接左递归的产生式A：首先，整理A产生式为如下形式：A→Aα|βA→βA'A'→αA'|ε71消除文法的直接左递归(续1)例3.17用算法3.1消除算术表达式文法的直接左递归：消除直接左递归的结果：E→TE'(1)E'→+TE'|ε(2)(G3.4')T→FT'(3)T'→*FT'|ε(4)F→(E)|-F|id(5)..(7)E→E+T|TT→T*F|F(G3.4)F→(E)|-F|id算法3.1:替换：A→Aα|β为：A→βA'A'→αA'|ε关键：将实际文法符号对应到A、α和β具体到E产生式：E→E+T|TAAαβ81消除文法的直接左递归(续2)分析输入序列：id+id*id改写的代价E→E+T|TT→T*F|FF→(E)|-F|id(G3.4)E→TE'(1)E'→+TE'|ε(2)T→FT'(3)T'→*FT'|ε(4)F→(E)|-F|id(5)..(7)(G3.4')E→E+E|E*E|(E)|-E|id(G3.2)EE+TTT*FFFidididEE+EE*EidididEE*EE+EidididETE'FT'+TE'idεFT'εid*FT'idε92消除文法的左递归文法：S→Aa|bA→Ac|Sd|ε因为：S=Aa=Sda所以：S左递归(但不是直接左递归)注意：若G产生句子的过程中出现AA的推导，则无法消除左递归+=核心思想：将无直接左递归的非终结符展开到其他产生式中foriin2..nloopforjin1..i-1loopendloop;endloop;■对每个形如Ai→Ajγ产生式中的Aj用Aj→δ1|δ2|...|δk的右部替换,得到新产生式Ai→δ1γ|δ2γ|...|δkγ;消除Ai产生式中的直接左递归;算法3.2消除左递归输入无回路文法G输出无左递归的等价文法G'方法将非终结符合理排序：A1，A2，...，An;102消除文法的左递归（续1）例3.18用算法3.2消除文法S→Aa|bA→Ac|Sd|ε中的左递归。核心思想：将无直接左递归的非终结符展开到其他产生式关键步骤：合理排序非终结符：A1，A2，...，An;用Aj→δ1|δ2|...|δk右部替换Ai→Ajγ中的Aj得到Ai→δ1γ|δ2γ|...|δkγ;消除Ai产生式中的直接左递归;①将S的右部展开在A中，得到：A→Ac|Aad|bd|ε②消除新产生式中的直接左递归，得到：S→Aa|bA→bdA'|A'(G3.8')A'→cA'|adA'|ε113.4.3提取左因子•当不确定用A产生式的哪个候选项替换A时，可以重写A产生式来推迟这种决定，直到看见足够的输入，能正确决定所需选择为止。•这一过程被称为提取左因子，它类似于有限自动机的确定化。公共左因子（前缀）：A→αβ1|αβ2将：A→αβ1|αβ2替换为：A→αA'A'→β1|β2它等价于：A→α(β1|β2)（对照算术表达式中的提取公因式）S→cAdA→ab|a123.4.3提取左因子（续1）算法3.3提取文法的左因子输入文法G输出等价的无左因子文法G'方法对于每个有左因子的产生式A：例3.20考察悬空else文法：S→iCtS|iCtSeS|aC→b用算法3.3提取左因子，得到如下文法：既有左递归又含左因子？先消除左递归。（为什么？试试P66例3.19）S→iCtSS'|aS'→ε|eSC→b（1）重排A产生式：A→αβ1|αβ2|...|αβn|γ；（2）用A→αA’|γ和A’→β1|β2|...|βn取代原A产生式。重复该过程，直到所有A、A’的候选项中不再有公共前缀。■133.4.4递归下降分析(器)直接以程序代码（的方式）模拟产生式产生语言的过程:基本思想：每个非终结符对应一个子程序（函数），过程体中：产生式右部的非终结符：对应子程序调用，产生式右部的终结符：与输入记号进行匹配。特点：1.子程序是递归的（因为文法是递归的）；2.程序与文法相关；3.它对文法的限制是不能有公共左因子和左递归；4.它是一种非形式化的方法，只要能写出子程序，用什么样的方法和步骤均可。14稳妥的方法：递归下降分析的文法：L→E;L|εE→E+T|E-T|TT→T*F|T/F|TmodF|FF→(E)|id|num文法G3.9(p66)消除左递归后的等价文法:L→E;L|εE→TE'E'→+TE'|-TE'|εG3.9’T→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|num1构造状态转换图且化简1.构造文法的状态转换图并且化简；2.将转换图转化为EBNF表示；3.从EBNF构造子程序。E的状态图EBNF表示15文法的状态转换图：（每个非终结符对应一个状态转换图）：1.为非终结符A建立一个初态和一个终态；2.为A→X1X2...Xn构造从初态到终态的路径，边标记为X1，X2，...，Xn。3.根据识别同一集合的原则，化简转换图。L→E;L|εE→TE'E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|num文法状态转换图：0321L:E;Lε465E:TE'109871211E':+TE'-TE'ε131514T:FT'191817162120T':*FT'/FT'ε2322modFT'27262524F:(E)idnum16状态图的化简：1.标记为A的边可等价为标记ε的边转向A转换图的初态；2.ε边连接的两个状态可以合并；3.标记相同的路径可以合并；4.不可区分的状态可以合并。化简前E的状态图：1.合并E’的路径：2.转向E'的初态：3.合并ε连接的节点：4.将E'的转换图代入E：5.合并ε连接的节点：6.合并相同路径：465E:TE'109871211E':+TE'-TE'ε10987E':+,-TE'ε10987E':+,-Tεε810E':+,-T810E:Tε+,-T45810E:T+,-T410E:T4+,-文法17状态图的化简（续1）最终全部化简的转换图：2文法的扩展BNF（EBNF）表示①{}：重复0或若干次（while）②[]：可选择（if或while）③|：括弧()之内的或关系（case）④()：改变运算的优先级和结合性将状态图转换为EBNF表示：L→{E;}E→T{(+|-)T}G3.9’’T→F{(*|/|mod)F}F→(E)|id|num1L:E0;3E:T2+,-9876F:(E)idnum5T:F4*,/,mod文法G3.9’183递归下降子程序L→{E;}E→T{(+|-)T}T→F{(*|/|mod)F}F→(E)|id|numprocedureL()isbeginlookahead:=lexan()；while(lookahead≠eof)loopE();match(';');endloop;endL;procedureE()isbeginT();whilelookahead∈(+|-)loopmatch(lookahead);T();endloop;endE;procedureF()isbegincaselookaheadis‘(':match(‘(');E();match(‘)');id:match(id);num:match(num);others:error(syntaxerror2);endcase;endF;193递归下降子程序（续）再看左递归问题：若存在产生式E→E+id，则E的递归下降子程序如下：procedureEisbeginE;match('+');match(id);endE;此程序永不停机。#includeiostream.hconstintid=0;voidmatch(intx){};voidE(){coutmatchEendl;E();match('+');match(id);coutmatch+andidendl;//永远不执行}intmain(){E();return0;}同样，文法中的公共左因子也会给递归下降分析造成困难。