自底向上的语法分析 4.5.

Slides:



Advertisements
Similar presentations
组长:倪运超 小组成员:徐悦、曹吕卿、孙浩、徐圣尧.  上海的历史 上海的历史  上海的历史 上海的历史  上海的文化 —— 建筑 上海的文化 —— 建筑  上海的文化 —— 美食 上海的文化 —— 美食  香港的历史 香港的历史  香港的历史 香港的历史  香港的文化 —— 建筑 香港的文化.
Advertisements

一、 突出解析几何复习中的重点问题的通法通解 解析几何中的重点问题 一、 突出解析几何复习中的重点问题的通法通解 直线与圆锥曲线的位置关系 重点一.
必修2 第一单元 古代中国经济的基本结构和特点
600年前,鄭和率領世界上最強大的艦隊,浩浩蕩蕩的駛入印度洋,展開一場「文化帝國」的海上大秀。
第十三章 中国的传统科学技术 中国古代的科技曾经长期处于世界领先地位,对人类文明的进步作出过重要贡献,并形成了富有特色的科技文化。在今天,源自中国古代科技文化的中医学仍然在现实生活中发挥着积极的作用。
7.4 用矩阵初等行变换 解线性方程组 主要内容: 一.矩阵的行初等变换 二.用行初等变换求逆矩阵 三.用矩阵法求线性方程组.
歷史建築清水國小宿舍群修復工程 施工說明會
2011年10月31日是一个令人警醒的日子,世界在10月31日迎来第70亿人口。当日凌晨,成为象征性的全球第70亿名成员之一的婴儿在菲律宾降生。 ?
编 译 原 理 指导教师:杨建国 二零一零年三月.
第6章 LR分析程序及其自动构造 6.1 自下而上分析及其LR分析概述 6.2 LR (0) 分析 6.3 SLR(1) 分析
初级会计实务 第八章 产品成本核算 主讲人:杨菠.
雄伟的金字塔.
编 译 原 理 指导教师:杨建国 二零一零年三月.
中考阅读 复习备考交流 西安铁一中分校 向连吾.
中央广播电视大学开放教育 成本会计(补修)期末复习
二综防火设计分析.
人教版义务教育课程标准实验教科书 小学数学四年级上册第七单元《数学广角》 合理安排时间 248.
定风波.
第三单元 发展社会主义民主政治.
第2章 LR分 析 法 LR分析法是一种自下而上进行规范归约的语法分析方法,LR指“自左向右扫描和自下而上进行归约”。LR分析法比递归下降分析法、LL(1)分析法和算符优先分析法对文法的限制要少得多,对大多数用无二义的上下文无关文法描述的语言都可以用LR分析器予以识别,而且速度快,并能准确、及时地指出输入串的任何语法错误及出错位置。LR分析法的一个主要缺点是,若用手工构造分析器则工作量相当大,因此必须求助于自动产生LR分析器的产生器。
LR与LL分析 编译原理习题课二 胡云斌 PB
3.3 资源的跨区域调配 ——以南水北调为例 铜山中学 李启强.
中考语文积累 永宁县教研室 步正军 2015.9.
小学数学知识讲座 应用题.
勾股定理 说课人:钱丹.
倒装句之其他句式.
开 学 第 一 课 六年级3班.
编译原理与技术 --文法和分析 2018/9/17 《编译原理与技术》讲义.
! 温故知新 上下文无关文法 最左推导 最右推导 自上而下 自下而上 句柄 归约 移进-归约冲突 移进-归约分析 递归下降预测分析
Chapter4 Syntax Analysis
编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法
Part5语法分析 授课:胡静.
第四章 语法分析 赵建华 南京大学计算机系
编译原理复习.
第三章 语法分析 本章内容 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开 词 法 分析器 记 号 取下一个记号
编译原理与技术 第3章 语法分析 14学时.
第 22 课 孙中山的民主追求 1 .近代变法救国主张的失败教训: “师夷之长技以制 夷”“中体西用”、兴办洋务、变法维新等的失败,使孙中山
编译原理习题
自上而下分析 4.4.
第四章 语法分析.
第三章 词法分析.
Part5语法分析 授课:胡静.
LL(1)分析方法 LL(1)是LL(k)的特例,其中的k则表示向前看k个符号. LL(1)方法和递归下降法属于同一级别的自顶向下分析法.
人教版数学四年级(下) 乘法分配律 单击页面即可演示.
编译原理与技术 语法制导翻译 2019/1/17 《编译原理与技术》讲义.
第五章 语法分析——自下而上分析 自上而下分析法(Top-down) 自下而上分析法(Bottom-up) 国防科技大学计算机系602教研室.
内容提要 什么是句法分析 与形式语言句法分析的比较 上下文无关语法的分析策略 自顶向下分析法 自底向上分析法 左角分析法
语法制导的翻译 (Syntax-Directed Translation)
《编译原理与技术》 期末复习 计算机科学与技术学院 郑启龙 李 诚 25/12/2018.
第三章 语法分析 自顶向下语法分析思想 语法分析方法的分类: 自顶向下语法分析方法(Top-Down) ,亦称面向目标的分析方法;
语法分析 本章内容 语法分析器:把词法分析生成的词法单元流翻译成语法分析树(parse tree)
第五章 自底向上分析方法 LR(0)分析法.
第3,4次课 一个简单的语法制导翻译器 2.3~2.5.
LL(1)分析法 复 习 LL分析程序构造及分析过程 输入串 符号栈 执行程序 此过程有三部分组成: 分析表 执行程序 (总控程序)
第五章 自底向上分析方法 LR(0)分析法 1 LR(K)分析法 第一个L表示:相应的语法分析将按自左至右的顺序扫描输入符号串;
编译原理总结-1 第3~5章.
LALR(1)分析方法.
编译原理实践 13.语法分析程序的自动生成工具YACC.
第五章 语法分析-自下而上分析 5.1 自下而上分析的基本问题 Figure5.5LR演示自下而上分析 i+(i+i)*i
第四章 自底向上分析方法 主要内容 自底向上分析的基本思想 简单优先分析方法 LR类分析方法 LR(0)分析方法 SLR(1)分析方法
文法等价变换 文法的等价 对文法G1和G2,若有:L(G1)=L(G2),则称文法G1和G2等价, 记作:G1=G2. 文法等价变换
第五章 自底向上分析方法 LR(0)分析法 1 LR(K)分析法 第一个L表示:相应的语法分析将按自左至右的顺序扫描输入符号串;
编译原理与技术 -- 自顶向下分析 2019/5/5 《编译原理与技术》讲义.
SLR(1)分析方法.
第四章 语法分析 南京大学计算机系 戴新宇
第五章 语法分析—自下而上分析 自下而上分析法:即是从输入串开始,逐步进行 “归约”,直至归约到文法的开始符号;
编译原理 第五章 语法分析——自下而上分析 编译原理.
畢氏定理(百牛大祭)的故事 張美玲 製作 資料來源:探索數學的故事(凡異出版社).
 3.1.4 空间向量的正交分解及其坐标表示.
102年人事預算編列說明 邁向頂尖大學辦公室製作.
Presentation transcript:

自底向上的语法分析 4.5

1. 移进归约的概念

4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d

4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde(读入ab) a b

4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde(归约) a A

4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde(再读入bc)

4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde(归约) a b A c

4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde(再读入d) a b A d c

4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde

4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde aABe(再读入e) e a b A d c B

4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde

S rm aABe rm aAde rm aAbcde rm abbcde 4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde aABe S S rm aABe rm aAde rm aAbcde rm abbcde S e a b A d c B

句型的句柄是和某产生式右部匹配的子串,并且,把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步 4.4 自下而上分析 4.4.2 句柄 句型的句柄是和某产生式右部匹配的子串,并且,把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步 S  aABe A  Abc | b B  d S rm aABe rm aAde rm aAbcde rm abbcde 句柄的右边仅含终结符 如果文法二义,那么句柄可能不唯一

4.4 自下而上分析 例 句柄不唯一 E  E + E | E  E | (E ) | id

4.4 自下而上分析 例 句柄不唯一 E  E + E | E  E | (E ) | id E rm E  E rm E  E + E rm E  E + id3 rm E  id2 + id3 rm id1  id2 + id3

4.4 自下而上分析 例 句柄不唯一 E  E + E | E  E | (E ) | id E rm E  E E rm E + E rm E  E + E rm E + id3 rm E  E + id3 rm E  E + id3 rm E  id2 + id3 rm E  id2 + id3 rm id1  id2 + id3 rm id1  id2 + id3 在句型E  E + id3中,句柄不唯一

2. 用栈实现移进归约

用栈实现移进归约分析 移进 归约 接受 报错 把下一个输入符号移进栈 分析器知道句柄的右端已在栈顶,然后确定句柄的左端在栈中的位置,再决定用什么样的非终结符代替句柄 接受 分析器宣告分析成功 报错 分析器发现语法错误,调用错误恢复例程

4.4 自下而上分析 4.4.3 用栈实现移进归约分析 先通过 来了解移进归约分析的工作方式 移进归约分析器在分析输入串id1  id2 + id3时的动作序列 来了解移进归约分析的工作方式

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约 按E  EE归约

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约 按E  EE归约

4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约 按E  EE归约 接受

3. 移进归约的冲突

要想很好地使用移进归约方式,尚需解决一些问题 4.4 自下而上分析 要想很好地使用移进归约方式,尚需解决一些问题 如何决策选择移进还是归约 进行归约时,确定右句型中将要归约的子串 进行归约时,如何确定选择哪一个产生式

4.4 自下而上分析 4.4.4 移进归约分析的冲突 1、移进归约冲突 例 stmt  if expr then stmt | if expr then stmt else stmt | other 如果移进归约分析器处于格局 栈 输入 … if expr then stmt else … $

4.4 自下而上分析 2、归约归约冲突 由A(I, J)开始的语句 栈 输入 … id ( id , id )… 归约成expr还 stmt  id (parameter_list) | expr = expr parameter_list  parameter_list, parameter | parameter parameter  id expr  id (expr_list) | id expr_list  expr_list, expr | expr 由A(I, J)开始的语句 栈 输入 … id ( id , id )… 归约成expr还 是parameter ?

4.4 自下而上分析 2、归约归约冲突 stmt  id (parameter_list) | expr = expr parameter_list  parameter_list, parameter | parameter parameter  id expr  id (expr_list) | id expr_list  expr_list, expr | expr 由A(I, J)开始的语句(词法分析查符号表,区分第一个id) 栈 输入 … procid ( id , id )… 需要修改上面的文法

4.4 自下而上分析 2、归约归约冲突 stmt  procid (parameter_list) | expr = expr parameter_list  parameter_list, parameter | parameter parameter  id expr  id (expr_list) | id expr_list  expr_list, expr | expr 由A(I, J)开始的语句(词法分析查符号表,区分第一个id) 栈 输入 … procid ( id , id )…

4. LR分析器

4.5 LR分析器 本节介绍LR(k)分析技术 特点 主要介绍构造LR分析表的三种技术 适用于一大类上下文无关文法 效率高 简单的LR方法(简称SLR) 规范的LR方法 向前看的LR方法(简称LALR)

4.5 LR分析器 4.5.1 LR分析算法 输入 LR分析程序 输出 栈 LR分析器的模型 action goto sm Xm Xm-1 … s0 a1 ai an $

LR语法分析 LR语法分析算法实例:图4.37 (1) E  E + T (2) E  T (3) T  T  F (4) T  F (5) F  ( E ) (6) F  id si:表示移进并将状态i压栈。 rj:表示按照编号为j的产生式进行归约。 Acc:表示接受。 空白:表示出错。

LR语法分析

可行前缀:右句型的前缀,该前缀不超过最右句柄的右端 4.5 LR分析器 4.5.2 LR文法和LR分析方法的特点 1、概念 可行前缀:右句型的前缀,该前缀不超过最右句柄的右端 S *rm  A w rm   w  的任何前缀(包括和 本身)都是可行前缀

4.5 LR分析器 4.5.2 LR文法和LR分析方法的特点 1、概念 可行前缀:右句型的前缀,该前缀不超过最右句柄的右端 2、定义 LR文法:我们能为之构造出所有条目都唯一的LR分析表

4.5 LR分析器 3、LR分析方法的特点 栈中的文法符号总是形成一个可行前缀

4.5 LR分析器 栈 输 入 动 作 id  id + id $ 移进 0 id 5  id + id $ 按F  id归约 输 入 动 作 id  id + id $ 移进 0 id 5  id + id $ 按F  id归约 0 F 3 按T  F归约 0 T 2 0 T 2  7 id + id $ 0 T 2  7 id 5 + id $ 0 T 2  7 F 10 按T  TF归约 . . . 0 E 1 $ 接受

4.5 LR分析器 3、LR分析方法的特点 栈中的文法符号总是形成一个可行前缀 分析表的转移函数本质上是识别可行前缀的DFA

4.5 LR分析器 例 E  E + T | E  T 下表绿色部分构成 T  T  F | T  E 识别可行前缀DFA的 F  (E ) | F  id 状态转换表 状态 动 作 转 移 id +  ( ) $ E T F s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 8 2 3

4.5 LR分析器 3、LR分析方法的特点 栈中的文法符号总是形成一个可行前缀 分析表的转移函数本质上是识别可行前缀的DFA 栈顶的状态符号包含了确定句柄所需要的一切信息

4.5 LR分析器 栈 输 入 动 作 id  id + id $ 移进 0 id 5  id + id $ 按F  id归约 输 入 动 作 id  id + id $ 移进 0 id 5  id + id $ 按F  id归约 0 F 3 按T  F归约 0 T 2 0 T 2  7 id + id $ 0 T 2  7 id 5 + id $ 0 T 2  7 F 10 按T  TF归约 . . . 0 E 1 $ 接受

4.5 LR分析器 3、LR分析方法的特点 栈中的文法符号总是形成一个可行前缀 分析表的转移函数本质上是识别可行前缀的DFA 栈顶的状态符号包含了确定句柄所需要的一切信息 是已知的最一般的无回溯的移进归约方法 能分析的文法类是预测分析法能分析的文法类的真超集 能及时发现语法错误 手工构造分析表的工作量太大

4.5 LR分析器 4、LR分析方法和LL分析方法的比较 LR(1)方 法 LL(1)方 法 建立分析树的方式 自 下 而 上 自 上 而 下

4.5 LR分析器 4、LR分析方法和LL分析方法的比较 LR(1)方 法 LL(1)方 法 建立分析树的方式 自 下 而 上 自 上 而 下 归约还是推导 规 范 归 约 最 左 推 导

4.5 LR分析器 4、LR分析方法和LL分析方法的比较 在下面的推导中,最后一步用的是A l S rm …  rm  A b w  rm  l  b w LR(1)决定用该 产生式的位置 LL(1)决定用该 产生式的位置

4.5 LR分析器 4、LR分析方法和LL分析方法的比较 LR(1)方 法 LL(1)方 法 建立分析树的方式 自 下 而 上 自 上 而 下 归约还是推导 规 范 归 约 最 左 推 导 决定使用产生式的时机 看见产生式右部推出的整个终结符串后,才确定用哪个产生式进行归约 看见产生式右部推出的第一个终结符后,便要确定用哪个产生式推导

4.5 LR分析器 4、LR分析方法和LL分析方法的比较 LR(1)方 法 LL(1)方 法 对文法的显式限制 对文法没有限制 无左递归、无公共左因子

4.5 LR分析器 4、LR分析方法和LL分析方法的比较 LR(1)方 法 LL(1)方 法 对文法的显式限制 对文法没有限制 无左递归、无公共左因子 分析表比较 状态×文法符号 分析表大 非终结符×终结符 分析表小

4.5 LR分析器 4、LR分析方法和LL分析方法的比较 LR(1)方 法 LL(1)方 法 对文法的显式限制 对文法没有限制 无左递归、无公共左因子 分析表比较 状态×文法符号 分析表大 非终结符×终结符 分析表小 分析栈比较 状态栈,通常状态比文法符号包含更多信息 文法符号栈

4.5 LR分析器 4、LR分析方法和LL分析方法的比较 LR(1)方 法 LL(1)方 法 确定句柄 根据栈顶状态和下一个符号便可以确定句柄和归约所用产生式 无句柄概念

4.5 LR分析器 4、LR分析方法和LL分析方法的比较 LR(1)方 法 LL(1)方 法 确定句柄 根据栈顶状态和下一个符号便可以确定句柄和归约所用产生式 无句柄概念 语法错误 决不会将出错点后的符号移入分析栈 和LR一样,决不会读过出错点而不报错