LL(1)分析方法 LL(1)是LL(k)的特例,其中的k则表示向前看k个符号. LL(1)方法和递归下降法属于同一级别的自顶向下分析法.

Slides:



Advertisements
Similar presentations
专题复习 --- 走进名著 亲近经典 读完《鲁滨孙漂流记》这本精彩的小说 后,一个高大的形象时时浮现在我的眼 前,他就是勇敢的探险家、航海家鲁滨 孙。他凭着顽强的毅力,永不放弃的精 神,实现了自己航海的梦想。 我仿佛看到轮船甲板上站着这样的一 个人:他放弃了富裕而又舒适的生活, 厌恶那庸庸碌碌的人生,从而开始了一.
Advertisements

四、后期物理复习备考建议 不同阶段复习课教学设计(知识建构)的目的 复习课教学 设计的目的 理 解 · 对某知识的全面、抽 象理解 · 抽象知识和具体情景 的转化 综 合 · 多知识点联合解决问 题 基本素质 · 审题、表达、审视答 案等基本能力 复习 ( 一 ) 复习(二) ☆ ☆☆☆ ☆☆  进行科学规划.
第二届直博会介绍 主办单位:天津市人民政府 中国航空工业集团公司 中国人民解放军总参谋部陆航部 支持单位:国家发展和改革委员会 工业和信息化部 公安部 交通运输部 体育总局 安全生产监督管理总局 林业局 国务院新闻办公室 国防科技工业局 中国民用航空局 中国人民解放军总参谋部作战部 中国人民解放军总参谋部司令部.
說 劍 《莊子‧雜篇》─ 第 一 組 賴泊錞 謝孟儒 張維真 羅苡芸
第四章 文学类文本阅读 增分突破一 金手一指,让你做好情节作 用分析题.
控制方长投下的子公司,需要编制合并报表的演示思路
妝點歌曲的神奇彩衣 part2 六年一班 設計與教學:陳映蓉.
98指考試題研討會 歷史考科試題分析 管美蓉 大學入學考試中心.
判断推理,必须学会这些 主讲老师:小胡胡 2016年3月25日20:00 YY频道:
P2P金融信用调查服务 2015年4月 诚信为先 中道厚德.
第五章 语法制导的翻译 赵建华 南京大学计算机系 2010年3月.
小微企业融资担保产品介绍 再担保业务二部 贾天
第二章 文法和语言 2.1 文法的基本概念 符号和符号串 2.2 句型的分析 文法和语言的形式定义 推导与递归 文法的分类 语法树
5.5可行性分析 可行性分析的概念 策略可行性分析 操作可行性分析 回报可行性分析.
现代企业高级职业经理人系列课程 管人理事与理人管事 —企业高效人力资源管理 主讲人:李青刚 副教授.
限时综合强化训练 限时综合强化训练.
第一单元 人在社会中生活 综合探究一 从地图上获取信息 第1课时 带着地图定向越野间.
长城国际酒店式公寓营销策划报告
104年振聲國中 志願選填個別序位 說明會 104年06月08日 輔導室關心您.
华东师范大学 软件工程硕士答辩名单 时间:2016年5月14日、15日.
組長:黃家逸 組員:殷浩賢、楊煜、吳家朗 毒品的害處.
编 译 原 理 指导教师:杨建国 二零一零年三月.
编 译 原 理 指导教师:杨建国 二零一零年三月.
第2章 LR分 析 法 LR分析法是一种自下而上进行规范归约的语法分析方法,LR指“自左向右扫描和自下而上进行归约”。LR分析法比递归下降分析法、LL(1)分析法和算符优先分析法对文法的限制要少得多,对大多数用无二义的上下文无关文法描述的语言都可以用LR分析器予以识别,而且速度快,并能准确、及时地指出输入串的任何语法错误及出错位置。LR分析法的一个主要缺点是,若用手工构造分析器则工作量相当大,因此必须求助于自动产生LR分析器的产生器。
了解太平天国运动的主要史实,认识农民起义在民主革命时期的作用与局限性。
第二十二章 生物药剂学及药物动力学.
第五章 电流和电路 制作人 魏海军
增分突破二 准确概括传主形象,深入分析传主的人格魅力和品质特征
八桥初中九年级思想品德课复习导学案之五---
软件工程 第八章 软件测试 制作者 程丽.
台州市2011年科学学业考试试题的命制 台州初级中学 郭海平.
编译原理与技术 课程总结.
Part5语法分析 授课:胡静.
Chapter 5 利率的風險結構與期間結構. Chapter 5 利率的風險結構與期間結構.
自上而下分析 4.4.
第6章 自底向上优先分析法 自底向上优先分析概述 简单优先分析 算符优先分析 返回目录.
第四章 语法分析.
3章 习题 1、设有文法G[N]: N→D|ND D→0|1|2|…|9 (1)试写出021和4321的最右推导和 最左推导。
Part5语法分析 授课:胡静.
LL分析法 LL分析法的分析器由一张预测分析表(LL(1)分析表),一个控制程序(表驱动程序)及一分析栈组成 输入
2019年1月16日9时17分 概率论 Probability 江西财经大学 2017年 2019年1月16日9时17分.
李元金 计算机与信息工程学院 第9讲 语法分析—自上而下分析(1) 李元金 计算机与信息工程学院
第五章 语法分析——自下而上分析 自上而下分析法(Top-down) 自下而上分析法(Bottom-up) 国防科技大学计算机系602教研室.
第三课时 匀变速直线运动的位移与时 间的关系
第三章 文法和语言 本章目的为语言的语法描述寻求工具,以便: 对源程序给出精确无二义的语法描述。(严谨、简洁、易读)
编译原理 第四章 语法分析—自上而下分析 编译原理.
第三章 语法分析 自顶向下语法分析思想 语法分析方法的分类: 自顶向下语法分析方法(Top-Down) ,亦称面向目标的分析方法;
语法分析 本章内容 语法分析器:把词法分析生成的词法单元流翻译成语法分析树(parse tree)
第五章 自底向上分析方法 LR(0)分析法.
第3,4次课 一个简单的语法制导翻译器 2.3~2.5.
第五章 自底向上分析方法 LR(0)分析法 1 LR(K)分析法 第一个L表示:相应的语法分析将按自左至右的顺序扫描输入符号串;
LALR(1)分析方法.
第四章 自底向上分析方法 主要内容 自底向上分析的基本思想 简单优先分析方法 LR类分析方法 LR(0)分析方法 SLR(1)分析方法
文法等价变换 文法的等价 对文法G1和G2,若有:L(G1)=L(G2),则称文法G1和G2等价, 记作:G1=G2. 文法等价变换
苏 教 版 五 年 级 数 学(上) 用字母表示数 青阳体仁小学 胡春雅.
第四章 自顶向下语法分析方法 语法分析的主要工作:是识别由词法分析给出的单词 序列是否是给定的正确句子(程序)。
自底向上的语法分析 4.5.
小学5.
不動產估價.
编译原理与技术 -- 自顶向下分析 2019/5/5 《编译原理与技术》讲义.
会计实务(第七讲) ——固定资产 讲师:天天老师.
上杭二中 曾庆华 上杭二中 曾庆华 上杭二中 曾庆华.
探索直线平行的条件 第一课时.
§12-5 同方向同频率两个简谐振动的合成 一. 同方向同频率的简谐振动的合成 1. 分振动 : 2. 合振动 : 解析法
國立政治大學 96學年度學雜費調整 第二次公聽會
编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法
编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法
2.2.2双曲线的简单几何性质 海口市灵山中学 吴潇.
第二章 柯西不等式与排序不等式及其应用.
2-2 圖形的放大與縮小.
Presentation transcript:

LL(1)分析方法 LL(1)是LL(k)的特例,其中的k则表示向前看k个符号. LL(1)方法和递归下降法属于同一级别的自顶向下分析法. 括号中的“1”,则表示在分析过程中,每进行一步推导,只要查看一个输入符号便能确定当前所应选用的产生式.

1 LL(1)分析方法的思想 对给定的终极符串ace,分析过程: 符号栈 输入流 驱动程序 ace # #Z 替换[1] #eBa 例 G[z] : [1] Z aBe [2] Z Bd [3] B bB [4] B cK [5] D  d [6] K  ε {b,c} {b} {d} {c} {d,e} {a} 对给定的终极符串ace,分析过程: 符号栈 输入流 驱动程序 ace # #Z 替换[1] #eBa ace # 匹配Match #eB ce # 替换[4] #eKc ce # 匹配Match #eK e # 替换[6] #e e # 匹配Match # # Success

b c d e Z B D K Error # LL(1)分析表 a 例 G[z] : [1] Z aBe [2] Z Bd [3] B bB [4] B cK [5] D  d [6] K  ε {b,c} {b} {d} {c} {d,e} {a} a b c d e Z B D K Z aBe Z Bd Error K  ε B bB B cK D  d # LL(1)分析表

对给定的终极符串acb,分析过程: 符号栈 输入流 驱动程序 acb # #Z 替换[1] #eBa acb # 匹配Match #eB 例 G[z] : [1] Z aBe [2] Z Bd [3] B bB [4] B cK [5] D  d [6] K  ε {b,c} {b} {d} {c} {d,e} {a} 对给定的终极符串acb,分析过程: 符号栈 输入流 驱动程序 acb # #Z 替换[1] #eBa acb # 匹配Match #eB cb # 替换[4] #eKc cb # 匹配Match #eK b # Error

在逻辑上,一个LL(1)分析器由输入流、LL(1)分析表、符号栈和驱动程序组成: 输入流:待分析的符号串 . 符号栈:存放分析过程中的文法符号串. LL(1)分析表:用来表示相应文法的全部信息 的一个矩阵(或二维数组). 驱动程序:语法分析程序.

4.5.2 LL(1)分析表的构造 LL(1)分析表的定义: T:VN  VT → P  { Error } T(A,t)=A→ 若tPredict( A→ ) T(A,t)=Error 否则 其中P表示所有产生式的集合.

E  T E’[1] i + * ( ) # E 1 E’ 2 3 T 4 T’ 6 5 F 7 8 E’  + T E’[2] | ε[3] T  F T’[4] T’  * F T’[5] | ε[6] F  i[7] | ( E )[8] Predict( [1]) = { i , ( } Predict( [2] )= { + } Predict( [3] ) = { ) , # } Predict( [4] ) = { i , ( } Predict( [5] ) = { * } Predict( [6] = { + , ) , # } Predict( [7] ) = { i } Predict( [8] ) = { ( }

4.5.3 LL(1)驱动程序构造 LL(1)分析的动作:设当前格局为 (..... X1, Y1.....), 替换:当X1VN时选相应候选式去替换X1. 匹配:当X1VT时,它与Y1进行匹配,其结果可能成功,也可能失败,如果成功则去掉X1和Y1,否则报错. 接受:当格局为(#,#)时报分析成功. 报错:

LL(1)分析方法的驱动器 a X Input  栈顶为#情形的处理  X VT情形的处理  X  VN情形的处理 Stack  栈顶为#情形的处理  X VT情形的处理  X  VN情形的处理 X LL[1]分析表

LL_驱动程序 Stack = empty ; Push(#); Push(S); Read(a);//读第一个输入符 令X=栈顶符号; //X=S while(X!=# && a!=#) { //栈不空,输入没结束 if (X VT ){ if( X= a) { Pop(1); Read(a);} else {Error( );return(-1);} } else if ( T(X, a) = X→Y1 Y2........ Yn ) { Pop(1);Push(Yn ,.....,Y1);// Y1在栈顶 } else { Error( ); return(-1); } 令X=栈顶符号; if ( X=# && a=#) Success( ); else Error( );

例2:文法G: E’  + T E’[2] | ε[3] T  F T’[4] T’  * F T’[5] | ε[6] F  i[7] | ( E )[8] 符号串 i + i * i # 的LL[1]分析过程:

E  T E’[1] { i , ( } 分析栈 输入流 矩阵元素 # E i + i * i # LL[ E ,i ] = [1] 分析栈 输入流 矩阵元素 # E i + i * i # LL[ E ,i ] = [1] # E’ T i + i * i # LL [ T ,i ] = [4] # E’ T’ F i + i * i # LL [ F ,i ] = [7] # E’ T’ i i + i * i # Match # E’ T’ + i * i # LL [ T’,+] = [6] # E’ +i * i # LL [ E’,+ ] = [2] # E’ T+ +i * i # Match # E’ T i * i # LL [ T,i ] =[4] # E’ T’ F i* i # LL [ F,i ] = [7] # E’ T’ i i * i # Match # E’ T’ * i # LL [ T’,* ] = [5] # E’T’F* * i # Match # E’T’F i # LL[F,i] = [7] # E’T’i i # Match # E’T’ # LL[T’,#] = [6] # E’ # LL[E’, #] = [3] # # ok E  T E’[1] { i , ( } E’  + T E’[2] { + } | ε[3] { ) , # } T  F T’[4] { i , ( } T’  * F T’[5] { * } | ε[6] { + , ) , # } F  id[7] { i } | ( E )[8] { ( }

E  T E’[1] { i , ( } 分析栈 输入流 矩阵元素 # E i + i *+ i # LL[ E ,i ] = [1] 分析栈 输入流 矩阵元素 E  T E’[1] { i , ( } E’  + T E’[2] { + } | ε[3] { ) , # } T  F T’[4] { i , ( } T’  * F T’[5] { * } | ε[6] { + , ) , # } F  id[7] { i } | ( E )[8] { ( } # E i + i *+ i # LL[ E ,i ] = [1] # E’ T i + i * +i # LL [ T ,i ] = [4] # E’ T’ F i + i * +i # LL [ F ,i ] = [7] # E’ T’ i i + i * +i # Match # E’ T’ + i * +i # LL [ T’,+] = [6] # E’ +i * +i # LL [ E’,+ ] = [2] # E’ T+ +i * +i # Match # E’ T i *+i # LL [ T,i ] =[4] # E’ T’ F i* + i # LL [ F,i ] = [7] # E’ T’ i i * + i # Match # E’ T’ *+ i # LL [ T’,* ] = [5] # E’T’F* *+ i # Match # E’T’F +i # LL[F,+] =Error

自顶向下语法分析方法的总结 一、自顶向下语法分析条件 predict(Aβk)predict(Aβj)= 当kj

二、LL(1)方法和递归下降法的区别 递归下降法对每个非终极符产生子程序,而LL(1)方法算法不变只是LL分析表不同;

练习:构造下述文法的LL(1)分析表. G[D]: D  TL T  int | float L  id R R  , id R | ε 文法符号 First集 Follow集 D { int,float } { # } T { int,float} { id } L { # } R { , ,  } Predict( D  TL ) = { int,float } Predict( T  int ) = { int } Predict( T  float) = { float} Predict( L  id R) = {id} Predict( R  , id R ) = { ,} Predict( R  ε ) = {#}

G[D]: D  TL T  int | float L  id R R  , id R | ε int float id , # Predict( D  TL ) = { int,float } Predict( T  int ) = { int } Predict( T  float) = { float} Predict( L  id R) = {id} Predict( R  , id R ) = { ,} Predict( R  ε ) = {#} int float id , # D D  TL T T  int T  float L L  id R R R  , id R R  ε

练习 课后题1:设有如下文法G[S] SaABbcd1|2 AASd3|4 BSAh5|eC6|7 CSf8|Cg9|10 求每个产生式的Predict集 该文法是否为LL(1)文法,为什么?

First集 G[S]: SaABbcd1|2 AASd3|4 BSAh5|eC6|7 CSf8|Cg9|10 First(S)={,a} First(A)={,a,d} First(B)={,a,d,h,e} First(C)={,a,f,g} First(aABbcd)={a} First(ASd)={a,d} First(SAh)={a,d,h} First(eC)={e} First(Sf)={a,f} First(Cg)={a,f,g}

Follow集 G[S]: SaABbcd1|2 AASd3|4 BSAh5|eC6|7 CSf8|Cg9|10 First(S)={,a} First(A)={,a,d} First(B)={,a,d,h,e} First(C)={,a,f,g} Follow(S)={#,a,d,h,f} Follow(A)={a,b,d,h,e} Follow(B)={b} Follow(C)={g,b}

Predict集 Predict(1)={a} Predict(2)={a,d,h,f,#} Predict(3)={a,d} G[S]: SaABbcd1|2 AASd3|4 BSAh5|eC6|7 CSf8|Cg9|10 Predict集 Predict(1)={a} Predict(2)={a,d,h,f,#} Predict(3)={a,d} Predict(4)={a,d,e,h} Predict(5)={a,d,h} Predict(6)={e} Predict(7)={b} Predict(8)={a,f} Predict(9)={a,f,g} Predict(10)={g,b} First(aABbcd)={a} First(ASd)={a,d} First(SAh)={a,d,h} First(eC)={e} First(Sf)={a,f} First(Cg)={a,f,g} Follow(S)={a,d,h,f,#} Follow(A)={a,b,d,h,e} Follow(B)={b} Follow(C)={g,b} 由于不同产生式规则的Predict集有交集,所以该文法不是LL(1)文法。

课后题2 判断下列文法那些是LL(1)文法 S(SS’| S’)| S(S)S| SS(S)S| S(S|S’ Predict(S(SS’)={(} Predict(S)={),#} Predict(S’))={)} Predict(S’)={),#} 不是LL(1)文法 Predict(S(S)S)={(} Predict(S)={),#} 是LL(1)文法 Predict(SS(S)S)={(} Predict(S)={),(,#} 左递归,不是LL(1)文法 Predict(S(S)={(} Predict(SS’)={(,#} Predict(S’(S’))={(} 判断下列文法那些是LL(1)文法 S(SS’| S’)| S(S)S| SS(S)S| S(S|S’ S’(S’)|

课后题3 已知文法G[E] EE+T|T TT*F|F Fi|(E) 按递归下降法构造此文法的语法分析程序 步骤: 判断文法类型 文法变换 消除左递归 提取公共前缀 求Predict集 设计程序

文法变换 EE+T|T ETE’ E’+TE’| TT*F|F TFT’ T’*FT’| G[E] EE+T|T TT*F|F Fi|(E) EE+T|T ETE’ E’+TE’| TT*F|F TFT’ T’*FT’| 消除左递归 对直接左递归形如: AA| 消除左递归可得: AA AA|

课后题4 A S 1 B 构造LL(1)文法G以识别语言L,其中={0,1} L={x|x为不包括两个相邻的1的非空串} S0A[1]|1B[2] A0A[3]|1B[4]|[5] B0A[6]|[7] Predict集 P(1)={0}=P(3)=P(6) P(2)={1}=P(4) P(5)={#}=P(7) S A B 1

课后题5 已知文法G[A] AaABe|a BBb|d 求G的LL(1)等价文法G’ [A] 构造G’[A]的LL(1)分析表并给出输入串aade#的分析过程。 AaABe|a 消除公共前缀得 AaA’[1] A’ABe[2]|[3] BBb|d 消除左递归得 BdB’[4] B’bB’[5]|[6] 26

a b d e # A 1 A’ 2 3 B 4 B’ 5 6 AaA’[1] A’ABe[2]|[3] BdB’[4] B’bB’[5]|[6] (#A,aade#) 1 (#A’a,aade#) m (#A’,ade#) 2 (#eBA,ade#) 1 (#eBA’a,ade#) m (#eBA’,de#) 3 (#eB,de#) 4 (#eB’d,de#) m (#eB’,e#) 6 (#e,e#) m (#,#) ok P(1)={a} P(2)={a} P(3)={d,#} P(4)={d} P(5)={b} P(6)={e} a b d e # A 1 A’ 2 3 B 4 B’ 5 6 27