编译原理 第05章算符优先分析法

返回 相似 举报
编译原理 第05章算符优先分析法_第1页
第1页 / 共30页
编译原理 第05章算符优先分析法_第2页
第2页 / 共30页
编译原理 第05章算符优先分析法_第3页
第3页 / 共30页
编译原理 第05章算符优先分析法_第4页
第4页 / 共30页
编译原理 第05章算符优先分析法_第5页
第5页 / 共30页
编译原理 第05章算符优先分析法_第6页
第6页 / 共30页
编译原理 第05章算符优先分析法_第7页
第7页 / 共30页
编译原理 第05章算符优先分析法_第8页
第8页 / 共30页
编译原理 第05章算符优先分析法_第9页
第9页 / 共30页
编译原理 第05章算符优先分析法_第10页
第10页 / 共30页
亲,该文档总共30页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述:
找归约串,就可获得不同的分析方法 1、自下而上分析事例设文法G为1SaAcBe 2Ab 3AAb 4Bd试判断语句abbcde是 否是该文法的合法句子 怎样实现归约过程借鉴LL1分析法的体系结构 步内入 串 作 0abbcde 1a bbcde移 2ab bcde移 3aA bcde 4aAb cde移 5aA cde 6aAc de移 7aAcd e移 8aAcB e 9aAcBe 移 10S 11 成功 2、自下而上分析法的核心问题 1存在移进--归约冲突; 2存在归约--归约冲突; 核心问题是寻找句型中的归约串进行归约。 自下而上分析法 一、算符优先分析法 1、算符优先分析法的思想 对于文法GEEE|E-E|E*E|E/E|E|i,分析 ii-i*ii 规范推导 EE*EE*EE*EEE*EiE*ii EE*iiEE-E*iiEE-i*iiEi- i*则输入 串是合法句子,否则输入串有语法错误。 p核心 n寻找句型中的归约串进行归约,用不同的方 法寻iiii-i*ii 第5章 优先分析法 逆程是 范 另外一种推导 EE-EE-E*EE-E*EE-E*EEE- E*Ei E-E*iiE-i*iiEE- i*iiEi-i*iiii-i*ii 第5章 优先分析法 算符优先分析法的基本思想 定义终结符之间的优先关系,借助终结符之间的 优先关系确定归约对象,进行自下而上分析。 比相的2个 算符的先 2种推导过程对于87-5*32的计算结果 2、算符优先分析技术的引进 必须给出文法中两个可能在句子中相继出现的终结符之间 的优先关系。 1相继出现在句子中若有“ab”或 “aQb”.a,bT,QN,则称a,b相继出现。 2终结符号对优先关系的存储 优先关系表是一个矩阵Ma,b,aT,bT,矩阵行数、列 数都为||1。 如对于文法GEEE|E-E|E*E|E/E|E|i,对应的优先矩阵 为 矩阵元素Ma,b表示a在前,b在后时,a与b之间的优先关系。 矩阵元素Ma,b的取值,, 。 ii-i*ii EE-E p对文法EEE|E-E|E*E|E/E|E|i -*/i - * / i 如何获得一般的文法的优先分析表 先低于其 右部符号 源程序中不会出 的情形 如何获得一般的文法的优先分析表 3、优先表的构造方法 算符文法给定上下文无关文法G(VN,VT,P ,S)中不存在形如ABC的产生式,则称之为算符 文法OGOperator Grammar其中A,B,CN 即如果文法中不存在具有相邻非终结符的产生式 ,则称为算符文法。 算符优先文法设文法G是一个不包含有空串产生式的算 符文法,如果该文法中的任何终结符号对a,b之间,在三种 关系中最多只有一种成立,则称该文法为算符优先文法。 1求文法中每个非终结符P的首终结符集合FIRSTVTP 定义FIRSTVTPa|Pa或者PQa,a T,P,Q N 复习 FIRSTa|* a,aT 构造FIRSTVTN BEGIN kk1; SKSYM END ELSE ERROR UNTIL SYM END 分析if b then i else i 例给定文法N END OF WHILE; IF SjSYM OR SjSYM THE 把Sj1Sk归约为某个N; kj1; SkN jj-1 ELSE jj-2; UNTIL Sj Q; EPEAT QSj; IF Sj-1T THE WHILE SjSYM DO BEGIN R如下 第5章 算符先分析法 S-if Eb then E else E E-ET|T T读入SYM中; IF SkT THEN jk ELSE jk-1 k1; Sk; REPEAT 把下一个输入符号i 素短语,则转第2步继续,直到归 约为文法开始符号。 PROCEDUR BEGIN 直到 Sk-1Sk ,此时Sk到栈顶就是最左素短语。 如果当前栈中已经没有最左-T*F|F F-i Eb-b 构造算符优先表 FIRSTVTSiSYM。 入 从栈顶向下寻找最左素短语若Sk-1Sk,则k-1,j同SYM的优先关系,如果SjSYM或SjSYM ,则SYM入栈S,直到当前栈顶Sj第一个终结符入栈S。 把下一个输入符号读入SYM中,则比较当前栈顶 第一个终结符Saj1 , 例如EE-i 5通用算符优先分析 算法思想f FIRSTVTE,*,i FIRSTVTT*,i FIRSTVTF 3ajaj1 综合起来即 ai-1 aiai1aj-1aj j Nj1 其中1ai-1ai , 2aiai1aj-1aj ,i VT) 它的最左素短语是满足下列条件的最左子串 Niai Ni1ai1 Nja的一般形式为 N1a1 N2a2 NnanNn1 (Ni VN,a*i iE*ii 其中的素短语为 i i i 4寻找句型最左素短语的方法 设句型i FIRSTVTEbb 第5章 算符先分析法 S-if Eb then E el素短语是算符优先法每一 次的归约串,而句柄是规范归约 每一次的归约串。 i i E*i i iE E E E E E E E i E * i ii E * i i 最左E|E*E| E|i 句型iE*ii的短语 E E E E E F T F * T iT F * T i 第5章 算符优先分析法 文法EEse E E-ET|T T-T*F|F F-i Eb-b LASTVTS E E E E T T T F T 约的对象 按照文法EEE|E*E|E|i ,求 iE*ii的短语和素短语 E E语有 F*T i F*Ti TF*Ti 其中的素短语为 F*T i F*T为最左素短语,是被归符优先分析法 例 pETE|T TF*T|F FE|i 句型 TF*Ti 的短else,,*,i LASTVTE,*,i LASTVTT*,i LA符。 除自身之外不再含有更小的素短语最小性。 在句型中具有最左性。 第5章 算 最左素短语指处于句型最左边的那个素短语。 最左素短语具备三个条件 至少含有一个终结3最左素短语 素短语是指至少含有一个终结符,并且除它自身 之外不再含有更小的素短语。 ET*F ET E E ET i T*F ii 第5章 算符优先分析法 符优先分析法每一次归约时,可归约串中至少有一个终结符 。 ii*i Ei*i ET*iSTVTFi LASTVTEbb 第5章 算符先分析法 步 下推关 系T*i ET*F ET E E ET T F i T*F F i i 算规范归约分析 ii*i Fi*i Ti*i Ei*i EF*i E 例如E-ET|T T-T*F|F F-E|i 分析句子ii*i 的若干问题 1二义文法不是算符优先文法。 2算符优先分析是一种非规范规约分析。 入串 作 0if b then i else i 1if b then i els“负”和双目“减”的算术表达式不好处理。 xyzxr 5、直观算符优先分析缺点 会把错误句子当作合法句子分析 无法指出输入串的出错位置 对单目 ELSE ERROR END END; 4直观算符优先分析法的 将d1Rd2压入栈内; 上弹OPTR END e i移 2if b then i else i移 3if N then BEGIN 上弹OPND栈顶二项d1和d2; SYM进栈; ADVANCE END ELSE IF 算符栈顶RSYM THEN IF 算符栈顶RSYM THEN BEGIN BEGIN 将SYM压入OPND ; ADVANCE END; ELSE TR ; ADVANCE END ELSE IF SYM运算量 THEN i else i 4if N then i else i移 5ifE IF 算符栈顶R AND SYM THEN BEGIN上弹OP算符栈顶R AND SYM THEN FLAGfalse ELSCE; WHILE FLAG DO BEGIN IF ; OPTR; FLAGTRUE; ADVAN N then i else i移 6if N then N 算法 PROCEDURE BEGIN OPND顶运算;否则,将SYM加入算符栈 。 2直观算符优先法分析过程 3直观算符优先是运算符,则判断是否 将SYM加入算符栈如果当前OPTR栈顶符号优先级高于 SYM,则先执行当前栈存放运算量 当前读头下符号SYM如果是运算量,则进入算量 栈。 当前读头下符号SYM如果 else i 7if N then N else i移 8 两个工作栈算符栈OPTR用于存放运算符 算量栈OPND用于先分析法 IF iaQb 4、直观算法优先算法 1直观算符优先法的下推自动机IF Xi和Xi1均为终结符THEN 置 XiXi1; 形如P-ab 第5章 算符优2Xn DO FOR i1 TO n-1 DO BEGIN 符优先分析法 PROCEDURE OPT; // 构造优先表算法 FOR 每条产生式PX1Xif N then N else i 移 9if N then N EET|T TPT|P PE|i 求此文法的算符优先表。 第5章 算;P|P PS|i Di 练习题SS SfStS SiE i, LASTVTD i 文法SS SDR RRSTVTS LASTVTR ;,i, LASTVTPelse N 10N 11成功 LASTVTS LA TVTD i ; i ; i FIRSTVTR ;,,i FIRSTVTP ,i FIRS LL1的体系结构 输入缓冲区符号序列 栈栈 控制程序 预测分析表M 输出的输出的 产生 析表。 FIRSTVTS FIRSTVTS ,i SDR RR;P|P PS|i Di 构造其算符优先分终结符P,则使用第三条规则,即有LASTVTPa 例如下述文法 SS 终结符a后面有非终结符P;则 使用第二条规则,即有aFIRSTVTP;如果某终结符a前面有非 ,则a b 对于文法的每个产生式,找出其中的终结符,同一产生式中 的终结符使用第一条规则,如果某式序列产生式序列 返回返回 作 1、定算符文法 Sa | | T TTSTVTP求出a b的符号对 方法对形如PRb的产生式,若有aLASTVTR 方法对形如PaR的产生式,若有bFIRSTVTR ,则 ab 利用构造的LAb其中a,b T, P,Q N 利用构造的FIRSTVTP求出ab的符号对用产生式求出ab的符号对 方法对形如Pab或PaQb的产生式,有 a,S | S (1)构造算符先关系表; (2)文法是否算符先文法什么如果是算 符先文P ;,i, iLASTVTS i, 3构造算符优先表 LASTVTP LASTVTD i ;LASTVT LASTVTS LASTVTR P|P PS|i Di 求其每个非终结符P的LASTVTP LASTVTS法,出句子a, a, a的算符先分析 程(指出堆和冲区的化)。 2、定算符文STVTP 例如下述文法 SS SDR RR;或者PaQ,则aLASTVTP 2若有产生式PQ,则LASTVTQ LA|S*Aa,aT 构造LASTVTP的算法 1若有产生式Pa|pa或者PaQ,a T,P,Q N 复习FOLLOWAa2求文法中每个非终结符P的尾终结符集合LASTVTP 定义LASTVTPa法 SS SfStS SiE EET|T TPT|PFIRSTVTD,i ;FIRSTVTP;,,i FIRSTVTP ,i FIRSTVTD i IRSTVTS FIRSTVTR 每个非终结符P的FIRSTVTP FIRSTVTS F PE|i 构造此文法的算符先表。 S SDR RR;P|P PS|i Di 求其若有产生式PQ,则FIRSTVTQFIRSTVTP 例如下述文法 SP的算法 1若有产生式Pa或者PQa,则aFIRSTVTP 2自下而上分析法 p思想 n从输入串出发,反复利用产生式进行规范归 约,如果最后能得到文法的开始符号,
展开阅读全文

最新标签

电脑版 |技术文库版权所有
经营许可证:粤ICP备16048919号-1 | 粤公网安备 44060602000677号