编译原理与技术 第3章 语法分析 14学时.

Slides:



Advertisements
Similar presentations
编 译 原 理 指导教师:杨建国 二零一零年三月.
Advertisements

第6章 LR分析程序及其自动构造 6.1 自下而上分析及其LR分析概述 6.2 LR (0) 分析 6.3 SLR(1) 分析
习题与试题 认真复习,重点是掌握基本概念。基本概念掌握了,相当一部分试题的解就有了
编 译 原 理 指导教师:杨建国 二零一零年三月.
编 译 原 理 指导教师:杨建国 二零一零年三月.
常用逻辑用语复习课 李娟.
第2章 LR分 析 法 LR分析法是一种自下而上进行规范归约的语法分析方法,LR指“自左向右扫描和自下而上进行归约”。LR分析法比递归下降分析法、LL(1)分析法和算符优先分析法对文法的限制要少得多,对大多数用无二义的上下文无关文法描述的语言都可以用LR分析器予以识别,而且速度快,并能准确、及时地指出输入串的任何语法错误及出错位置。LR分析法的一个主要缺点是,若用手工构造分析器则工作量相当大,因此必须求助于自动产生LR分析器的产生器。
LR与LL分析 编译原理习题课二 胡云斌 PB
初中数学八年级下册 (苏科版) 10.4 探索三角形 相似的条件(2).
编译原理与技术 课程总结.
编译原理与技术 --文法和分析 2018/9/17 《编译原理与技术》讲义.
! 温故知新 上下文无关文法 最左推导 最右推导 自上而下 自下而上 句柄 归约 移进-归约冲突 移进-归约分析 递归下降预测分析
Chapter4 Syntax Analysis
编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法
Part5语法分析 授课:胡静.
第四章 语法分析 赵建华 南京大学计算机系
编译原理复习.
第三章 语法分析 本章内容 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开 词 法 分析器 记 号 取下一个记号
编译原理习题
2.2 语法分析器生成器YACC 分析器的构造步骤: 产生式→识别活前缀的DFA→分析表(+驱动器) YACC概述
自上而下分析 4.4.
自上而下分析 4.4.
第四章 语法分析.
第三章 词法分析.
Part5语法分析 授课:胡静.
第一单元 初识C程序与C程序开发平台搭建 ---观其大略
LL(1)分析方法 LL(1)是LL(k)的特例,其中的k则表示向前看k个符号. LL(1)方法和递归下降法属于同一级别的自顶向下分析法.
LL分析法 LL分析法的分析器由一张预测分析表(LL(1)分析表),一个控制程序(表驱动程序)及一分析栈组成 输入
第五章 语法分析——自下而上分析 自上而下分析法(Top-down) 自下而上分析法(Bottom-up) 国防科技大学计算机系602教研室.
《编译原理与技术》 期末复习 计算机科学与技术学院 郑启龙 李 诚 25/12/2018.
编译原理 第四章 语法分析—自上而下分析 编译原理.
第三章 语法分析 自顶向下语法分析思想 语法分析方法的分类: 自顶向下语法分析方法(Top-Down) ,亦称面向目标的分析方法;
语法分析 本章内容 语法分析器:把词法分析生成的词法单元流翻译成语法分析树(parse tree)
第五章 自底向上分析方法 LR(0)分析法.
第3,4次课 一个简单的语法制导翻译器 2.3~2.5.
LL(1)分析法 复 习 LL分析程序构造及分析过程 输入串 符号栈 执行程序 此过程有三部分组成: 分析表 执行程序 (总控程序)
1.3 C语言的语句和关键字 一、C语言的语句 与其它高级语言一样,C语言也是利用函数体中的可执行 语句,向计算机系统发出操作命令。按照语句功能或构成的不 同,可将C语言的语句分为五类。 goto, return.
第五章 自底向上分析方法 LR(0)分析法 1 LR(K)分析法 第一个L表示:相应的语法分析将按自左至右的顺序扫描输入符号串;
EBNF与操作语义 请用扩展的 BNF 描述 javascript语言里语句的结构;并用操作语义的方法描述对应的语义规则
简单介绍 用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)
学习目标 1、什么是字符集 2、字符集四个级别 3、如何选择字符集.
编译原理总结-1 第3~5章.
LALR(1)分析方法.
编译原理实践 13.语法分析程序的自动生成工具YACC.
第五章 语法分析-自下而上分析 5.1 自下而上分析的基本问题 Figure5.5LR演示自下而上分析 i+(i+i)*i
文法等价变换 文法的等价 对文法G1和G2,若有:L(G1)=L(G2),则称文法G1和G2等价, 记作:G1=G2. 文法等价变换
第四章 自顶向下语法分析方法 语法分析的主要工作:是识别由词法分析给出的单词 序列是否是给定的正确句子(程序)。
自底向上的语法分析 4.5.
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
第4章 Excel电子表格制作软件 4.4 函数(一).
第九节 赋值运算符和赋值表达式.
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
编译原理与技术 -- 自顶向下分析 2019/5/5 《编译原理与技术》讲义.
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
上杭二中 曾庆华 上杭二中 曾庆华 上杭二中 曾庆华.
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
SLR(1)分析方法.
2.2直接证明(一) 分析法 综合法.
本节内容 C语言的汇编表示 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
2.3.运用公式法 1 —平方差公式.
第四章 语法分析 南京大学计算机系 戴新宇
递归下降法 1 递归下降法语法分析原理 递归子程序方法/递归下降法 对每个非终极符按其产生式结构产生相应语法分析子程序。
基于列存储的RDF数据管理 朱敏
第五章 语法分析—自下而上分析 自下而上分析法:即是从输入串开始,逐步进行 “归约”,直至归约到文法的开始符号;
编译原理 第五章 语法分析——自下而上分析 编译原理.
第四章 UNIX文件系统.
编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法
编译原理实践 6.程序设计语言PL/0.
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法
Presentation transcript:

编译原理与技术 第3章 语法分析 14学时

内容提要 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开 词 法 分析器 记 号 取下一个记号 源程序 分析树 前端的 3 语法分析 内容提要 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开 词 法 分析器 记 号 取下一个记号 源程序 分析树 前端的 其余部分 语 法 中间表示 符号表

编译原理与技术 第3章 语法分析 3.1 上下文无关文法 0.5学时

正规式能定义一些简单的语言,能表示给定结构的固定次数 的重复或者没有指定次数的重复 例:a (ba)5, a (ba) 3.1 上下文无关文法 3.1.1 上下文无关文法的定义 正规式能定义一些简单的语言,能表示给定结构的固定次数 的重复或者没有指定次数的重复 例:a (ba)5, a (ba) 正规式不能用于描述配对或嵌套的结构 例1:配对括号串的集合 例2:{wcw | w是a和b的串}

例 ( {id, +, , -, (, )}, {expr, op}, expr, P ) 3.1 上下文无关文法 上下文无关文法是四元组(VT , VN , S, P) VT : 终结符集合 VN : 非终结符集合 S : 开始符号,非终结符中的一个 P : 产生式集合, 产生式形式 : A  α 以下简称“文法” 例 ( {id, +, , -, (, )}, {expr, op}, expr, P ) expr  expr op expr expr  (expr) expr  - expr expr  id op  + op  

符号的约定 终结符 非终结符 其它 3.1 上下文无关文法 字母表前面的小写字母,如a, b, c, … 词法分析中约定的记号,如id, num, if, while, … 数字0, 1, 2, … , 9 标点符号,如逗号,句号,… 运算符号,如+, -, , <, >, =, … 非终结符 字母表前面的大写字母,如A, B, C, … 字母S,通常代表开始符号 小写字母组成的名字,如expr, op, stmt, … 其它 字母表后面的大写字母,如X, Y, Z, 代表文法符号,包括非终结符或 终结符 字母表后面的小写字母,如u, v, w, …, z,代表终结符号串 小写希腊字母,如α, β, γ, …,代表文法符号串

expr  expr op expr expr  (expr) expr  - expr expr  id 3.1 上下文无关文法 expr  expr op expr expr  (expr) expr  - expr expr  id op  + op   简化表示 expr  expr op expr | (expr) | - expr | id op  + |  E  E A E | (E ) | -E | id A  + | 

把产生式看成重写规则,把符号串中的非终结符用其产生式右 部的串来代替 3.1 上下文无关文法 3.1.2 推导 把产生式看成重写规则,把符号串中的非终结符用其产生式右 部的串来代替 例:E  E + E | E  E | (E ) | -E | id E  -E  -(E)  -(E + E)  -(id + E)  -(id + id) 概念 上下文无关语言、等价的文法、句型 记号 S  α、 S + w

例如 E  E + E | E  E | (E ) | -E | id 最左推导 3.1 上下文无关文法 例如 E  E + E | E  E | (E ) | -E | id 最左推导 E lm -E lm -(E) lm -(E + E) lm -(id + E) lm -(id + id) 最右推导(规范推导) E rm -E rm -(E) rm -(E + E) rm -(E + id) rm -(id + id)

例如 E  E + E | E  E | (E ) | -E | id 3.1 上下文无关文法 3.1.3 分析树 例如 E  E + E | E  E | (E ) | -E | id E  -E  -(E)  -(E + E)  -(id + E)  -(id + id) E  E ( E ) E + E id id

3.1.4 二义性 E  E  E E  E + E  id  E  E  E +E 3.1 上下文无关文法 3.1.4 二义性 E  E  E E  E + E  id  E  E  E +E  id  E + E  id  E + E  id  id + E  id  id + E  id  id + id  id  id + id 两个不同的最左推导 两棵不同的语法树 E  + id

编译原理与技术 第3章 语法分析 3.2 语言和文法 2学时

文法只能描述编程语言的大部分语法,不能描述语言中 上下文有关的语法特征 3.2 语言和文法 文法的优点 文法给出了精确的,易于理解的语法说明 自动产生高效的分析器 可以给语言定义出层次结构 以文法为基础的语言的实现便于语言的修改 文法的问题 文法只能描述编程语言的大部分语法,不能描述语言中 上下文有关的语法特征

3.2.1 正规式和上下文无关文法的比较 正规式 (a|b)ab 文法(由正规式构造文法) 开始 a 3.2 语言和文法 3.2.1 正规式和上下文无关文法的比较 正规式 (a|b)ab 文法(由正规式构造文法) A0  aA0 | bA0 | aA1 A1  bA2 A2  ε 1 2 开始 a b

从软件工程角度看,词法分析和语法分析的分离有如下好处 简化设计 编译器的效率会改进 编译器的可移植性加强 便于编译器前端的模块划分 3.2 语言和文法 3.2.2 分离词法分析器理由 为什么要用正规式定义词法 词法规则非常简单,不必用上下文无关文法 对于词法记号,正规式描述简洁且易于理解 从正规式构造出的词法分析器效率高 从软件工程角度看,词法分析和语法分析的分离有如下好处 简化设计 编译器的效率会改进 编译器的可移植性加强 便于编译器前端的模块划分

能否把词法分析并入到语法分析中,直接从字符流进行语法 分析 3.2 语言和文法 能否把词法分析并入到语法分析中,直接从字符流进行语法 分析 若把词法分析和语法分析合在一起,则必须将语言的注 解和空白的规则反映在文法中,文法将大大复杂 注解和空白由自己来处理的分析器,比注解和空格已由 词法分析器删除的分析器要复杂得多

G : S  (S) S | ε L(G) = 配对的括号串的集合 按推导步数进行归纳:推出的是配对括号串 归纳基础: S  ε 3.2 语言和文法 3.2.3 验证文法产生的语言 G : S  (S) S | ε L(G) = 配对的括号串的集合 按推导步数进行归纳:推出的是配对括号串 归纳基础: S  ε 归纳假设:少于n步的推导都产生配对的括号串 归纳步骤:n步的最左推导如下: S  (S)S  (x) S  (x) y 按串长进行归纳:配对括号串可由S推出 归纳假设:长度小于2n的都可以从S推导出来 归纳步骤:考虑长度为2n(n ≥ 1)的w = (x) y

id  id  (id+id) + id  id + id 3.2 语言和文法 3.2.4 适当的表达式文法 用一种层次观点看待表达式 id  id  (id+id) + id  id + id 文法 expr  expr + term | term term  term  factor | factor factor  id | (expr)

term  term  factor | factor factor  id | (expr) 3.2 语言和文法 expr  expr + term | term term  term  factor | factor factor  id | (expr) expr id term factor  expr + id factor term  id  id  id 分析树 id + id  id 分析树

| if expr then stmt else stmt | other 3.2 语言和文法 3.2.5 消除二义性 stmt  if expr then stmt | if expr then stmt else stmt | other 句型:if expr then if expr then stmt else stmt 两个最左推导: stmt  if expr then stmt  if expr then if expr then stmt else stmt stmt  if expr then stmt else stmt

matched_stmt  if expr then matched_stmt else matched_stmt | other 3.2 语言和文法 无二义的文法 stmt  matched _stmt | unmatched_stmt matched_stmt  if expr then matched_stmt else matched_stmt | other unmatched_stmt  if expr then stmt | if expr then matched_stmt else unmatched_stmt

stmt  if expr then stmt | matched_stmt 3.2 语言和文法 例题 下面的条件语句文法仍存在二义,请证明 stmt  if expr then stmt | matched_stmt matched_stmt  if expr then matched_stmt else stmt | other if  then             else  if  then  else  if  then 

3.2.6 消除左递归 文法左递归 A + Aα 直接左递归 A  Aα | β 串的特点 βα . . . α 消除直接左递归 3.2 语言和文法 3.2.6 消除左递归 文法左递归 A + Aα 直接左递归 A  Aα | β 串的特点 βα . . . α 消除直接左递归 A  βA' A'  αA' | ε

例题 例 算术表达文法 E  E + T | T ( T + T . . . + T ) 3.2 语言和文法 例题 例 算术表达文法 E  E + T | T ( T + T . . . + T ) T  T  F | F ( F  F . . .  F ) F  ( E ) | id 消除左递归后文法 E  T E' E'  + T E' | ε T  F T' T'   F T' | ε

非直接左递归 S  Aa | b A  Sd | ε 先变换成直接左递归 A  Aad | bd | ε 再消除左递归 3.2 语言和文法 非直接左递归 S  Aa | b A  Sd | ε 先变换成直接左递归 A  Aad | bd | ε 再消除左递归 A  bd A' | A' A'  adA' | ε

3.2 语言和文法 3.2.7 提左因子 有左因子的文法 A  αβ1 | αβ2 提左因子 A  αA' A'  β1 | β2

stmt  if expr then stmt else stmt | if expr then stmt | other 3.2 语言和文法 例题 例 悬空else的文法 stmt  if expr then stmt else stmt | if expr then stmt | other 提左因子 stmt  if expr then stmt optional_else_part optional_else_part  else stmt | ε

3.2.8 非上下文无关的语言构造 L1 = { wcw | w ∈ (a | b)} 3.2 语言和文法 3.2.8 非上下文无关的语言构造 L1 = { wcw | w ∈ (a | b)} 标识符的声明应先于其引用的抽象 L2 = { anbmcndm | n ≥ 0, m ≥ 0} 形参个数和实参个数应该相同的抽象 L3 = { anbncn | n ≥ 0} 早先排版描述的一个现象的抽象 b e g i n:5个字母键,5个回退键,5个下划线键

L1' = { wcwR | w ∈ (a|b)} S  aSa | bSb | c 3.2 语言和文法 L1' = { wcwR | w ∈ (a|b)} S  aSa | bSb | c L2' = { anbmcmdn | n ≥ 1, m ≥ 1} S  aSd | aAd A  bAc | bc L2" = { anbncmdm | n ≥ 1,m ≥ 1} S  AB A  aAb | ab B  cBd | cd

设读完ε, a, aa, …, ak 分别到达状态s0, s1, …, sk 3.2 语言和文法 L3' ={ anbn | n ≥ 1} S  aSb | ab L3' 是不能用正规式描述的语言的一个范例 若存在接受L3' 的DFA,状态数为k个 设读完ε, a, aa, …, ak 分别到达状态s0, s1, …, sk 至少有两个状态相同,例如是 si 和 sj,则 ajbi 属于L3' 标记为aj  i的路径 … si … f s0 标记为ai的路径 标记为bi的路径

0型文法:αβ,α,β∈(VN∪VT), |α|≥1 短语文法 3.2 语言和文法 3.2.9 形式语言鸟瞰 文法 G = (VT , VN , S , P) 0型文法:αβ,α,β∈(VN∪VT), |α|≥1 短语文法 1型文法:|α|≤|β|,但 Sε 可以例外 上下文有关文法 2型文法:Aβ,A∈VN , β∈(VN∪VT) 上下文无关文法 3型文法:AaB 或 Aa,A,B∈VN , a∈VT 正规文法

例 L3={ anbncn | n≥1 }的上下文有关文法 S  aSBC S  aBC CB  BC 3.2 语言和文法 例题 例 L3={ anbncn | n≥1 }的上下文有关文法 S  aSBC S  aBC CB  BC aB  ab bB  bb bC  bc cC  cc anbncn 的推导过程如下: S  an-1S(BC)n-1 用S  aSBC n-1次 + an(BC)n 用S  aBC 1次 + anBnCn 用CB  BC n(n-1)/2次 + anbBn-1Cn 用aB  ab 1次 + anbnCn 用bB  bb n-1次 + anbncCn-1 用bC  bc 1次 + anbncn 用cC  cc n-1次

编译原理与技术 第3章 语法分析 3.3 自上而下分析 3学时

3.3.1 自上而下分析的一般方法 例 文法 S  aCb C  cd | c 为输入串 acb 建立分析树 S a C b S a C 3.3 自上而下分析 3.3.1 自上而下分析的一般方法 例 文法 S  aCb C  cd | c 为输入串 acb 建立分析树 S a C b S a C b c d S a C b c 复杂的回溯技术 回溯导致语义工作推倒重来 难以报告出错的确切位置 效率低 不能处理左递归

不能处理左递归的例子:算术表达文法 E  E + T | T T  T  F | F F  ( E ) | id E E + T E 3.3 自上而下分析 不能处理左递归的例子:算术表达文法 E  E + T | T T  T  F | F F  ( E ) | id E E + T E + T E + T … … …

FIRST(α) = {a | α  a…, a∈VT} 特别当 α  ε 时,规定 ε ∈ FIRST(α) 3.3 自上而下分析 3.3.2 LL(1)文法 对文法加什么样的限制可以保证没有回溯? 先定义两个和文法有关的函数 FIRST(α) = {a | α  a…, a∈VT}  特别当 α  ε 时,规定 ε ∈ FIRST(α) FOLLOW(A) = {a | S  …Aa…,a∈VT}  如果A是某个句型的最右符号,那么$属于FOLLOW(A)

若B  ε, FIRST(α)  FIRST(A) A  ε ε∈FIRST(A) $∈FOLLOW(S) B  αAβ 3.3 自上而下分析 FIRST 、FOLLOW计算规则: A  aα a∈FIRST(A) A  Bα FIRST(B)  FIRST(A) 若B  ε, FIRST(α)  FIRST(A) A  ε ε∈FIRST(A) $∈FOLLOW(S) B  αAβ FIRST(β)  FOLLOW(A) 若β  ε, FOLLOW(B)  FOLLOW(A)

FIRST(E) = FIRST(T) = FIRST(F) = { ( , id } FIRST(E') = {+, ε} 3.3 自上而下分析 例题 例 E  TE' E'  + TE' | ε T  FT' T'   FT' | ε F  (E) | id FIRST(E) = FIRST(T) = FIRST(F) = { ( , id } FIRST(E') = {+, ε} FIRST(T') = {, ε} FOLLOW(E) = FOLLOW(E') = { ), $} FOLLOW(T) = FOLLOW (T') = {+, ), $} FOLLOW(F) = {, +, ), $}

任何两个产生式A  α | β 都满足下列条件: FIRST(α) ∩ FIRST(β) = Ø 3.3 自上而下分析 LL(1)文法: 任何两个产生式A  α | β 都满足下列条件: FIRST(α) ∩ FIRST(β) = Ø 若 β  ε,那么FIRST(α) ∩ FOLLOW(A) = Ø 例如,对于下面文法,面临a…时,第2步推导不知用哪个产 生式 S  A B A  a b | ε a ∈ FIRST(ab) ∩ FOLLOW(A) B  a C C  …

1代表在分析过程中执行每一步推导都要向前查看一个输 入符号——当前正在处理的输入符号 3.3 自上而下分析 LL(1)文法 第一个L代表从左向右扫描输入符号串; 第二个L代表产生最左推导; 1代表在分析过程中执行每一步推导都要向前查看一个输 入符号——当前正在处理的输入符号 LL(1)文法有一些明显的性质 没有公共左因子 不是二义的 不含左递归

| array [simple] of type 3.3 自上而下分析 3.3.3 递归下降的预测分析 为每一个非终结符写一个分析过程 这些过程可能是递归的 例 simple  integer | char | num dotdot num type  simple | ↑ id | array [simple] of type

void match (terminal t) { 3.3 自上而下分析 一个辅助过程 void match (terminal t) { if (lookahead == t) lookahead = nextToken( ); else error( ); }

if ( lookahead == integer) match(integer); 3.3 自上而下分析 void simple( ) { if ( lookahead == integer) match(integer); else if (lookahead == char) match(char); else if (lookahead == num) { match(num); match(dotdot); match(num); } else error( ); simple  integer | char | num dotdot num

| array [simple] of type 3.3 自上而下分析 void type( ) { if ( (lookahead == integer) || (lookahead == char) || (lookahead == num) ) simple( ); else if ( lookahead == '↑' ) { match( '↑' ); match(id);} else if (lookahead == array) { match(array); match( '[' ); simple( ); match( ']' ); match(of ); type( ); } else error( ); type  simple |  id | array [simple] of type

else if (M[X,a]是出错入口) error; else if (M[X,a]=XY1Y2…Yk) { 3.3 自上而下分析 3.3.4 非递归的预测分析 输入 预测分析程序 分析表M 输出 栈 a + b $ X Y Z while(X!=$ ) { if ( X==a) X出栈, 指针推进; else if (X是终结符) error; else if (M[X,a]是出错入口) error; else if (M[X,a]=XY1Y2…Yk) { X出栈; 输出产生式; Yk…Y1入栈; }

分析表的例子 E  TE' T  FT' F  (E) | id E'  +TE' | ε T'  FT' | ε 教材表3.1 3.3 自上而下分析 分析表的例子 E  TE' T  FT' F  (E) | id E'  +TE' | ε T'  FT' | ε 教材表3.1 非终 结符 输 入 符 号 id +  ( ) $ E E  TE E E  +TE E'   T T  FT T T   T  FT T'   F F  id F  (E)

预测分析器接受输入 id  id + id 的前一部分动作 栈 输 入 输 出 3.3 自上而下分析 例题 预测分析器接受输入 id  id + id 的前一部分动作 栈 输 入 输 出 $ E id  id + id$ $ E T id  id + id$ E  TE $ E T F id  id + id$ T  FT $ E T id id  id + id$ F  id $ E T  id + id$ $ E T F   id + id$ T  FT $ E T F id + id$ $ E T id id + id$ F  id $ E T + id$

例题 栈 输 入 输 出 $ E + id$ T   $ E T + + id$ E  +TE $ E T id$ 3.3 自上而下分析 例题 栈 输 入 输 出 $ E + id$ T   $ E T + + id$ E  +TE $ E T id$ $ E T F id$ T  FT $ E T id id$ F  id $ E T $ $ E $ T   $ E  

3.3 自上而下分析 例题 输出构成分析树: E T E' F T' id   +

(1) 对文法的每个产生式 A  α ,执行(2)和(3) (2) 对FIRST(α)的每个终结符a, 把 A  α 加入M[A, a] 3.3 自上而下分析 3.3.5 构造预测分析表 (1) 对文法的每个产生式 A  α ,执行(2)和(3) (2) 对FIRST(α)的每个终结符a, 把 A  α 加入M[A, a] (3) 如果 ε 在FIRST(α)中,对FOLLOW(A)的每个终结符b(包 括$), 把 A  α 加入M[A, b] (4) M中其它没有定义的条目都是error

FIRST(TE') = FIRST(FT') = { ( , id } FOLLOW(E') = { ), $} 3.3 自上而下分析 分析表的构造 E  TE' T  FT' F  (E) | id E'  +TE' | ε T'  FT' | ε FIRST(TE') = FIRST(FT') = { ( , id } FOLLOW(E') = { ), $} FOLLOW (T') = {+, ), $} 非终 结符 输 入 符 号 id +  ( ) $ E E  TE E E  +TE E'   T T  FT T T   T  FT T'   F F  id F  (E)

stmt  if expr then stmt e_part | other e_part  else stmt |  非终 结符 3.3 自上而下分析 多重定义的条目 stmt  if expr then stmt e_part | other e_part  else stmt |  非终 结符 输 入 符 号 other b else . . . stmt stmt  other e_part e_part else stmt e_part   expr expr  b 消除方法: 修改文法,消除二义性 根据语法约定消去多重定义

词法错误,如标识符、关键字或算符的拼写错 语法错误,如算术表达式的括号不配对 语义错误,如算符作用于不相容的运算对象 3.3 自上而下分析 3.3.6 预测分析的错误恢复 (1) 先对编译器的错误处理做一个概述 词法错误,如标识符、关键字或算符的拼写错 语法错误,如算术表达式的括号不配对 语义错误,如算符作用于不相容的运算对象 逻辑错误,如无穷的递归调用 (2) 分析器对错误处理的基本目标 清楚而准确地报告错误的出现,并尽量少出现伪错误 迅速地从每个错误中恢复过来,以便诊断后面的错误 它不应该使正确程序的处理速度降低太多

栈顶是非终结符A,输入符号是a,但M[A , a]是空白 3.3 自上而下分析 (3) 非递归预测分析在什么场合下发现错误 栈顶是终结符,但和输入符号不匹配 栈顶是非终结符A,输入符号是a,但M[A , a]是空白 输入 预测分析程序 分析表M 输出 栈 a + b $ X Y Z

(4) 非递归预测分析:采用紧急方式的错误恢复 发现错误时,分析器每次抛弃一个输入记号,直到输入记号 属于某个指定的同步记号集合为止 3.3 自上而下分析 (4) 非递归预测分析:采用紧急方式的错误恢复 发现错误时,分析器每次抛弃一个输入记号,直到输入记号 属于某个指定的同步记号集合为止 (5) 同步 词法分析器当前提供的记号流能够构成的语法构造,正是语 法分析器所期望的 不同步的例子 语法分析器期望剩余的前缀构成过程调用语句,而实际剩余的前缀 形成赋值语句

把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合 3.3 自上而下分析 (6) 同步记号集合的选择 把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合 例如: if expr then stmt then和分号等记号是expr的同步记号 把高层构造的开始符号加到低层构造的同步记号集合中 例如:a = expr; if … 语句的开始符号作为表达式的同步记号,以免表达式出错又遗漏分 号时忽略 if 语句等一大段程序 把FIRST(A)的终结符加入A的同步记号集合 例如:a = expr; , if … 语句的开始符号作为语句的同步符号,以免多出一个逗号时会把 if 语句忽略了 如果终结符在栈顶而不能匹配,弹出此终结符 如果非终结符可以产生空串,若出错时栈顶是这样的非终结 符,则可以使用推出空串的产生式

例:栈顶为T',面临id时出错(例如:a20d+5) 非终 结符 输 入 符 号 3.3 自上而下分析 例题 例:栈顶为T',面临id时出错(例如:a20d+5) 非终 结符 输 入 符 号 id +  ( ) $ E E  TE E E  +TE E'   T T  FT T err T   T  FT T'   F F  id F  (E) err, T T 可以产生空串,报错并用 T。 相当于丢弃了一个输入

编译原理与技术 第3章 语法分析 3.4 自下而上分析 1.5学时

S rm aABe rm aAde rm aAbcde rm abbcde 3.4 自下而上分析 3.4.1 归约 例 S  aABe 输入abbcde A  Abc | b B  d abbcde(读入ab) aAbcde(归约) aAbcde(读入bc) aAde(归约) aAde(读入d) aABe(归约) aABe(读入e) S(归约) S A B A a b b c d e S rm aABe rm aAde rm aAbcde rm abbcde

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

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

先通过例子 id1  id2 +id3 了解移进—归约分析的工作方式 栈 输 入 动 作 3.4 自下而上分析 3.4.3 用栈实现移进—归约分析 先通过例子 id1  id2 +id3 了解移进—归约分析的工作方式 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $id1  id2 + id3$ 按 E  id 归约 $E  id2 + id3$ 移进 $E id2 + id3$ 移进 $Eid2 + id3$ 按 E  id 归约 $EE + id3$ 移进 $EE+ id3$ 移进 $EE+id3 $ 按 E  id 归约 $EE+E $ 按 E  E+E 归约 $EE $ 按 E  EE 归约 $E $ 接受

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

| if expr then stmt else stmt | other 3.4 自下而上分析 3.4.4 移进—归约分析的冲突 (1)移进—归约冲突 例 stmt  if expr then stmt | if expr then stmt else stmt | other 如果移进—归约分析器处于格局 栈 输入 … if expr then stmt else … $ 解决方法:消除二义性 归约? 移进?

stmt  id (parameter_list) | expr = expr 3.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 ( id , id )… 解决方法:查符号表,区分第一个id。上下文有关文法 procid 归约成expr还是parameter ? procid

编译原理与技术 第3章 语法分析 3.5 LR分析器 6学时

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

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

3.5 LR分析器 LR分析程序: 栈顶状态为s0;a指向第一个符号; while(1) { s=栈顶状态 if ( action[s,a] == 移进t) { 把a和t入栈; a取下一个输入符号; } else if ( action[s,a] == 归约 Aβ) { 栈顶退掉2|β|个符号; 把A和goto[s,A]入栈; 输出产生式 Aβ; } else if (action[s,a] == 接受) break; else 调用错误恢复例程; }

例题 例 E  E + T | T T  T  F | F F  (E ) | id 教材表3.7 3.5 LR分析器 si: 移进,状态i进栈 rj: 按产生式(j)归约 acc: 表示接受 i: 转移到状态i (1) E  E + T (2) E  T (3) T  T  F (4) T  F (5) F  (E ) (6) F  id 教材表3.7 状态 动 作 action 转 移 goto id +  ( ) $ E T F s5 s4 1 2 3 s6 acc r2 s7 r4 4 8 …

例题 3.5 LR分析器 栈 输 入 动 作 id  id + id $ A[0,id]=s5 移进 0 id 5  id + id $ 输 入 动 作 id  id + id $ A[0,id]=s5 移进 0 id 5  id + id $ A[5,]=r6 归约 Fid,M[0,F]=3 0 F 3  id + id $ A[3,]=r4 归约 TF,M[0,T]=2 0 T 2  id + id $ A[2,]=s7 移进 0 T 2  7 id + id $ A[7,id]=s5 移进 0 T 2  7 id 5 + id $ A[5,+]=r6 归约 Fid,M[7,F]=10 0 T 2  7 F 10 + id $ A[10,+]=r3 归约 TTF,M[7,T]=2 0 T 2 + id $ A[2,+]=r2 归约 ET,M[0,E]=1 0 E 1 + id $ A[1,+]=s6 移进 0 E 1 + 6 id $ A[6,id]=s5 移进 0 E 1 + 6 id 5 $ A[5,$]=r6 归约 Fid,M[6,F]=3 0 E 1 + 6 F 3 $ A[3,$]=r4 归约 TF,M[6,$]=9 0 E 1 + 6 T 9 $ A[9,$]=r1 归约 EE+T, M[0,E]=1 0 E 1 $ A[1,$]=acc 接受

活前缀:右句型的前缀,该前缀不超过最右句柄的右端 S rm γAw rm γβw γβ的任何前缀(包括 ε 和 γβ 本身)都是活前缀 3.5 LR分析器 3.5.2 LR文法和LR分析方法的特点 (1)概念 活前缀:右句型的前缀,该前缀不超过最右句柄的右端 S rm γAw rm γβw γβ的任何前缀(包括 ε 和 γβ 本身)都是活前缀 (2)定义 LR文法:我们能为之构造出所有条目都唯一的LR分析表

3.5 LR分析器 (3)LR分析方法的特点 栈中的文法符号总是形成一个活前缀

3.5 LR分析器 栈 输 入 动 作 id  id + id $ A[0,id]=s5 移进 0 id 5  id + id $ A[5,]=r6 归约 Fid,M[0,F]=3 0 F 3 A[3,]=r4 归约 TF,M[0,T]=2 0 T 2 A[2,]=s7 移进 0 T 2  7 id + id $ A[7,id]=s5 移进 0 T 2  7 id 5 + id $ A[5,+]=r6 归约 Fid,M[7,F]=10 0 T 2  7 F 10 A[10,+]=r3 归约 TTF,M[7,T]=2 A[2,+]=r2 归约 ET,M[0,E]=1 0 E 1 A[1,+]=s6 移进 0 E 1 + 6 id $ A[6,id]=s5 移进 0 E 1 + 6 id 5 $ A[5,$]=r6 归约 Fid,M[6,F]=3 0 E 1 + 6 F 3 A[3,$]=r4 归约 TF,M[6,$]=9 0 E 1 + 6 T 9 A[9,$]=r1 归约 EE+T, M[0,E]=1 A[1,$]=acc 接受

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

绿色部分构成识别活前缀DFA的状态转换表 3.5 LR分析器 E  E + T | T T  T  F | F F  (E ) | id 绿色部分构成识别活前缀DFA的状态转换表 教材表3.7 状态 动 作 action 转 移 goto id +  ( ) $ E T F s5 s4 1 2 3 s6 acc r2 s7 r4 4 8 …

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

3.5 LR分析器 栈 输 入 动 作 id  id + id $ A[0,id]=s5 移进 0 id 5  id + id $ A[5,]=r6 归约 Fid,M[0,F]=3 0 F 3 A[3,]=r4 归约 TF,M[0,T]=2 0 T 2 A[2,]=s7 移进 0 T 2  7 id + id $ A[7,id]=s5 移进 0 T 2  7 id 5 + id $ A[5,+]=r6 归约 Fid,M[7,F]=10 0 T 2  7 F 10 A[10,+]=r3 归约 TTF,M[7,T]=2 A[2,+]=r2 归约 ET,M[0,E]=1 0 E 1 A[1,+]=s6 移进 0 E 1 + 6 id $ A[6,id]=s5 移进 0 E 1 + 6 id 5 $ A[5,$]=r6 归约 Fid,M[6,F]=3 0 E 1 + 6 F 3 A[3,$]=r4 归约 TF,M[6,$]=9 0 E 1 + 6 T 9 A[9,$]=r1 归约 EE+T, M[0,E]=1 A[1,$]=acc 接受

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

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

在下面的推导中,最后一步用的是 A  a β S +rm γ A b w +rm γ a β b w LR(1)决定用该 产生式的位置 LL(1)决定用该 产生式的位置

根据栈顶状态和下一个符号便可以确定句柄和归约所用产生式 无句柄概念 3.5 LR分析器 LR(1)方 法 LL(1)方 法 对文法的显式限制 对文法没有限制 无左递归、无公共左因子 分析表比较 状态×文法符号 分析表大 非终结符×终结符 分析表小 分析栈比较 状态栈,通常状态比文法符号包含更多信息 文法符号栈 确定句柄 根据栈顶状态和下一个符号便可以确定句柄和归约所用产生式 无句柄概念 语法错误 决不会将出错点后的符号移入分析栈 和LR一样,决不会读过出错点而不报错

• 3.5.3 构造SLR(1)分析表 术语:LR(0)项目(简称项目) 在右部的某个地方加点的产生式 用加点来表示分析过程中的状态 例:AXYZ对应有四个项目 A  •XYZ A  X•YZ A  XY•Z A  XYZ• 例:Aε只对应一个项目 A  • expr  expr + •term term  •term  factor term  term • factor expr + term •  term factor

3.5 LR分析器 构造SLR分析表的两大步骤 (1)从文法构造识别活前缀的DFA (2)从上述DFA构造分析表

(1)从文法构造识别活前缀的DFA 1)拓广文法 E'  E E  E + T | T T  T  F | F 3.5 LR分析器 (1)从文法构造识别活前缀的DFA 1)拓广文法 E'  E E  E + T | T T  T  F | F F  ( E ) | id

(1)从文法构造识别活前缀的DFA 2)构造LR(0)项目集规范族 I0: E'  •E (核心项目) E  •E + T (非核心项目,通过对核心 E  •T 项目求闭包而获得) T  •T  F T  •F F  •( E ) F  •id E'  E E  E + T | T T  T  F | F F  ( E ) | id

goto ( I0, E ) = I1 I5: I0: F  id• E'  •E id I1: E  •E + T E 3.5 LR分析器 goto ( I0, E ) = I1 I5: F  id• I0: E'  •E E  •E + T E  •T T  •T  F T  •F F  •( E ) F  •id id I1: E'  E• E  E •+ T E I4: F  ( •E ) E  •E + T E  •T T  •T  F T  •F F  •( E ) F  •id T I2: E  T• T  T • F ( F E'  E E  E + T | T T  T  F | F F  ( E ) | id I3: T  F•

E + I0 I1 I6 I1: E'  E• E  E •+ T + T I6: I2 E  E + •T T  •T  F 3.5 LR分析器 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I1: E'  E• E  E •+ T + I6: E  E + •T T  •T  F T  •F F  •( E ) F  •id E'  E E  E + T | T T  T  F | F F  ( E ) | id

I1 I0 E I3 I2 I4 I5 T F ( id + I6 I2: E  T• T  T • F  I7: 3.5 LR分析器 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I2: E  T• T  T • F  I7: T  T  •F F  •( E ) F  •id I7  E'  E E  E + T | T T  T  F | F F  ( E ) | id

I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I3: T  F• 无转换 E'  E 3.5 LR分析器 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I3: T  F• 无转换 E'  E E  E + T | T T  T  F | F F  ( E ) | id

I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I4: F  ( •E ) E  •E + T 3.5 LR分析器 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I4: F  ( •E ) E  •E + T E  •T T  •T  F T  •F F  •( E ) F  •id I8: F  ( E •) E  E •+ T E T I2 F I3 I4 ( I5 id I8 E ( id 指向I2 T E'  E E  E + T | T T  T  F | F F  ( E ) | id 指向I3 F

I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 T 指向I3 F 指向I4 ( 3.5 LR分析器 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 T 指向I3 F 指向I4 ( 指向I5 id I6: E  E + •T T  •T  F T  •F F  •( E ) F  •id I9: E  E + T• T  T • F T F I3 E'  E E  E + T | T T  T  F | F F  ( E ) | id I5 id I4 (

I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10: 3.5 LR分析器 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10: T  T  F• F I7: T  T  •F F  •( E ) F  •id I10 F 指向I4 ( 指向I5 id I5 id I4 ( E'  E E  E + T | T T  T  F | F F  ( E ) | id

I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 3.5 LR分析器 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11: F  ( E )• ) I8: F  ( E •) E  E •+ T I6 + I11 ) 指向I6 + E'  E E  E + T | T T  T  F | F F  ( E ) | id

I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 3.5 LR分析器 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6  指向I7 I9: E  E + T• T  T • F I7  E'  E E  E + T | T T  T  F | F F  ( E ) | id

I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 3.5 LR分析器 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6 指向I7 所有状态都作为接受状态 这是一个判断活前缀的DFA E  E  E+T  E+T  F  E+T  id  E+T  F  id E+TF 的所有前缀都可接受

也可以构造一个识别活前缀的NFA 每个项目作为一个状态 E'  E E  E + T | T T  T  F | F 3.5 LR分析器 也可以构造一个识别活前缀的NFA 每个项目作为一个状态 E'  E E  E + T | T T  T  F | F F  ( E ) | id E E'  •E E'  E• ε ε ε ε E  •E + T E  •T ε ε ε ε T  •T  F T  •F ε ε F  •( E ) F  •id

从文法构造的识别活前缀的DFA的一些特点 概念:有效项目 3.5 LR分析器 从文法构造的识别活前缀的DFA的一些特点 概念:有效项目 如果S'rm αAw rm αβ1β2w,那么就说项目Aβ1•β2对 活前缀 αβ1 是有效 (1)一个项目可能对好几个活前缀都是有效的 E  •E+T 对 ε 和 ( 这两个活前缀都有效 E'  E  E+T (α,β1都为空) E'  E  (E)  (E+T) (α =“(”, β1为空) 该DFA读过 ε 和 ( 后到达不同的状态,那么项目 E•E+T 就出现在对应的不同项目集中

从文法构造的识别活前缀的DFA的一些特点 概念:有效项目 3.5 LR分析器 从文法构造的识别活前缀的DFA的一些特点 概念:有效项目 如果S'rm αAw rm αβ1β2w,那么就说项目Aβ1•β2对 活前缀 αβ1 是有效 (1)一个项目可能对好几个活前缀都是有效的 从项目 Aβ1•β2 对活前缀 αβ1 有效这个事实可以知道 如果 β2 ≠ ε,应该移进 如果 β2 = ε,应该用产生式 Aβ1 归约 (2)一个活前缀可能有多个有效项目 一个活前缀 γ 的有效项目集就是从这个DFA的初态出发, 沿着标记为 γ 的路径到达的那个项目集(状态)

例 串 E + T  是活前缀,读完它后,DFA处于状态I7 3.5 LR分析器 例 串 E + T  是活前缀,读完它后,DFA处于状态I7 E'  E E'  E E'  E  E+T  E+T  E+T  E+T  F  E+T  F  E+T  F  E+T  id  E+T  ( E )  E+T  id  E+T  F  id I7: T  T  •F F  •( E ) F  •id

(2)从识别活前缀的DFA构造SLR分析表 状态 i 由项目集 Ii 构造,它的action函数如下确定: 如果 Ii 中包含 [Aα•aβ],并且 goto(Ii, a ) = Ij,那么 置action[i, a]为sj 如果 Ii中包含 [Aα•],那么对 FOLLOW(A) 中的所有a, 置 action[i, a] 为rj,j是产生式 Aα 的编号 如果 Ii中包含 [S'S•],那么置 action[i, $]为接受acc 如果出现动作冲突,那么该文法就不是SLR(1)的 使用下面规则构造状态i的goto函数: 如果 goto(Ii, A) = Ij, 那么置goto[i, A] = j 不能由上面两步定义的条目都置为error 分析器的初始状态是包含[S'•S]的项目集对应的状态

action[2, $]=action[2, +]=action[2, )]=r2 E'  E E  E + T | T 3.5 LR分析器 例题 例 I2: 因为FOLLOW(E) = {$, +, )}, 所以 action[2, ] = s7 action[2, $]=action[2, +]=action[2, )]=r2 E'  E E  E + T | T T  T  F | F F  ( E ) | id I2: E  T• T  T • F

例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 3.5 LR分析器 例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6 指向I7 •id + id  id  id 栈: E'  E E  E + T | T T  T  F | F F  ( E ) | id

例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 3.5 LR分析器 例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6 指向I7 id •+ id  id  id 栈: 0 id 5 0 F 3 0 T 2 0 E 1 E'  E E  E + T | T T  T  F | F F  ( E ) | id

例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 3.5 LR分析器 例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6 指向I7 id + •id  id  id 栈: 0 E 1 + 6 E'  E E  E + T | T T  T  F | F F  ( E ) | id

例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 3.5 LR分析器 例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6 指向I7 id + id • id  id 栈: 0 E 1 + 6 id 5 0 E 1 + 6 F 3 0 E 1 + 6 T 9 E'  E E  E + T | T T  T  F | F F  ( E ) | id

例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 3.5 LR分析器 例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6 指向I7 id + id  •id  id 栈: 0 E 1 + 6 T 9  7 E'  E E  E + T | T T  T  F | F F  ( E ) | id

例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 3.5 LR分析器 例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6 指向I7 id + id  id • id 栈: 0 E 1 + 6 T 9  7 id 5 0 E 1 + 6 T 9  7 F 10 0 E 1 + 6 T 9 E'  E E  E + T | T T  T  F | F F  ( E ) | id

例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 3.5 LR分析器 例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6 指向I7 id + id  id  •id 栈: 0 E 1 + 6 T 9  7 E'  E E  E + T | T T  T  F | F F  ( E ) | id

例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 3.5 LR分析器 例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6 指向I7 id + id  id  id• 栈: 0 E 1 + 6 T 9  7 id 5 0 E 1 + 6 T 9  7 F 10 0 E 1 + 6 T 9 0 E 1 acc E'  E E  E + T | T T  T  F | F F  ( E ) | id

action[2, = ] =r5,因为"="是E的一个后继符 该文法不是SLR(1)的 例:带指针的计算、赋值语句 (1) S  V = E (2) S  E (3) V   E (4) V  id (5) E  V I0 : S   •S S  •V = E S  •E V  • E V  •id E  •V I2 : S  V •= E E  V• V 第一项目使得 action[2, = ] = s6 第二项目使得 action[2, = ] =r5,因为"="是E的一个后继符 该文法不是SLR(1)的 S $  V = E $ 移进的场合 S $  E $  V $ 规约的场合

重新定义项目,让它带上搜索符,成为如下形式 [Aα • β, a] 3.5 LR分析器 3.5.4 构造规范的LR分析表 LR(1)项目: 重新定义项目,让它带上搜索符,成为如下形式 [Aα • β, a] LR(1)项目[Aβ1•β2, a]对活前缀 αβ1 有效: 如果存在着推导 S rm αAw rm αβ1β2w,其中: a 是 w 的第一个符号,或者 w 是 ε 且 a 是 $

从最右推导S rm bbBba rm bbbBba看出: [B  b•B, b]对活前缀 bbb 是有效的 3.5 LR分析器 例 S  BB B  bB | a 从最右推导S rm bbBba rm bbbBba看出: [B  b•B, b]对活前缀 bbb 是有效的 对于项目[A  α•β, a],当 β为空时,是根据搜索符a来填表 (归约项目),而不是根据A的后继符来填表

I5 : S I1 : I0 : S BB•, $ S S•, $ S •S, $ S •BB, $ B •bB, b/a B 3.5 LR分析器 I5 : S BB•, $ B I0 : S •S, $ S •BB, $ B •bB, b/a B •a, b/a I1 : S S•, $ S I6 : B b•B, $ B •bB, $ B •a, $ b I2 : S B•B, $ B •bB, $ B •a, $ B I3 : B b•B, b/a B •bB, b/a B •a, b/a b I4 : B a•, b/a a b a I9 : B bB•, $ B I7 : B a•, $ a b I8 : B bB•, b/a B a

(1) 基于LR(1)项目来构造识别 G' 活前缀的DFA (2) 状态 i 由项目集 Ii 构造,它的action函数如下确定: 如果 Ii 中包含 [Aα•aβ, b],并且 goto(Ii, a ) = Ij,那 么置action[i, a]为sj 如果 Ii中包含 [Aα•, a],且A≠S,那么置 action[i, a] 为rj,j是产生式 Aα 的编号 如果 Ii中包含 [S'S•, $],那么置 action[i, $]为接受acc 如果出现动作冲突,那么该文法就不是SLR(1)的 使用下面规则构造状态i的goto函数: 如果 goto(Ii, A) = Ij,那么置goto[i, A] = j 不能由上面两步定义的条目都置为error 分析器的初始状态是包含 [S'•S, $] 的项目集对应的状态

先前基于SLR(1)有移进-归约冲突的例子,在基于规范LR(1) 时无冲突 (1) S  V = E (2) S  E (3) V   E (4) V  id (5) E  V I0 : S   •S, $ S  •V = E, $ S  •E, $ V  • E, =/$ V  •id, =/$ E  •V, $ I2 : S  V •= E, $ E  V•, $ V

LALR和SLR的分析表有同样多的状态,比规范LR分析表 要小得多 LALR的能力介于SLR和规范LR之间

I5 : S I1 : I0 : S BB•, $ S S•, $ S •S, $ S •BB, $ B •bB, b/a 3.5 LR分析器 I0 : S •S, $ S •BB, $ B •bB, b/a B •a, b/a I1 : S S•, $ S I2 : S B•B, $ B •bB, $ B •a, $ B I4 : B a•, b/a a I3 : B b•B, b/a b I5 : S BB•, $ I6 : B b•B, $ I7 : B a•, $ I8 : B bB•, b/a I9 : B bB•, $ I4和I7仅搜索符不一样 I4和I7合并

I5 : S I1 : I0 : S BB•, $ S S•, $ S •S, $ S •BB, $ B •bB, b/a 3.5 LR分析器 I0 : S •S, $ S •BB, $ B •bB, b/a B •a, b/a I1 : S S•, $ S I2 : S B•B, $ B •bB, $ B •a, $ B I4 : B a•, b/a a I3 : B b•B, b/a b I5 : S BB•, $ I6 : B b•B, $ I7 : B a•, $ I8 : B bB•, b/a I9 : B bB•, $ 有三组同心集,都合并

I5 : S I1 : I0 : S BB•, $ S S•, $ S •S, $ S •BB, $ B •bB, b/a 3.5 LR分析器 I0 : S •S, $ S •BB, $ B •bB, b/a B •a, b/a I1 : S S•, $ S I2 : S B•B, $ B •bB, $ B •a, $ B I47 : B a•, b/a/$ a I36 : B b•B, b/a/$ B •bB, b/a/$ B •a, b/a/$ b I5 : S BB•, $ I89 : B bB•, b/a/$ 有三组同心集,都合并

I5 : S I1 : I0 : S BB•, $ S S•, $ S •S, $ S •BB, $ B •bB, b/a 3.5 LR分析器 I0 : S •S, $ S •BB, $ B •bB, b/a B •a, b/a I1 : S S•, $ S I2 : S B•B, $ B •bB, $ B •a, $ B I4 : B a•, b/a a I3 : B b•B, b/a b I5 : S BB•, $ I6 : B b•B, $ I7 : B a•, $ I8 : B bB•, b/a I9 : B bB•, $ 03132432 831802 6162762 961925 201 03132432 831802 error 输入为bbabba$ 输入为bba$

I5 : S I1 : I0 : S BB•, $ S S•, $ S •S, $ S •BB, $ B •bB, b/a 3.5 LR分析器 I0 : S •S, $ S •BB, $ B •bB, b/a B •a, b/a I1 : S S•, $ S I2 : S B•B, $ B •bB, $ B •a, $ B I47 : B a•, b/a/$ a I36 : B b•B, b/a/$ B •bB, b/a/$ B •a, b/a/$ b I5 : S BB•, $ I89 : B bB•, b/a/$ 036136247 36289361 8902error 输入为bbabba$ 输入为bba$

同心的LR(1)项目集:略去搜索符后它们是相同的集合 同心集的合并不会引起新的移进—归约冲突 若合并后有冲突,则合并前就有冲突。例如: (1)合并同心项目集可能会引起冲突 同心的LR(1)项目集:略去搜索符后它们是相同的集合 同心集的合并不会引起新的移进—归约冲突 若合并后有冲突,则合并前就有冲突。例如: 项目集1 项目集2 [A  α•, a] [B  β•aγ, b] [B  β•aγ, c] [A  α•, d] . . . . . .

同心集的合并有可能产生新的归约—归约冲突 3.5 LR分析器 (1)合并同心项目集可能会引起冲突 同心集的合并有可能产生新的归约—归约冲突 S  S S  aAd | bBd | aBe | bAe A  c B  c 对ac有效的项目集 对bc有效的项目集 A  c•, d B  c•, e A  c•, e B  c•, d 合并同心集后 该文法是LR(1)的, 但不是LALR(1)的 A  c•, d/e B  c•, d/e

1)构造LR(1)项目集规范族C = {I0, I1, …, In} (2)构造LALR(1)分析表 1)构造LR(1)项目集规范族C = {I0, I1, …, In} 2)寻找LR(1)项目集规范族中同心的项目集,用它们的并集代 替它们 3)按构造规范LR(1)分析表的方式构造分析表

下面文法是LALR(1)的,因无同心集可合并 但不是SLR(1)的 S  V = E S  E V   E V  id E  V I0 : S   •S S  •V = E S  •E V  • E V  •id E  •V I2 : S  V •= E E  V• V

若自左向右扫描的移进—归约分析器能及时识别出现在栈顶 的句柄,那么相应的文法就是LR的 语言L = {wwR| w ∈ (a | b)*}的文法 S  aSa | bSb | ε 不是LR的 ababbbbaba 语言L = {wcwR| w ∈ (a | b)*}的文法 S  aSa | bSb | c 是LR的 ababbcbbaba

例:为语言L = { ambn | n > m ≥ 0 }写三个文法,它们分别是 LR(1)的、二义的和非二义且非LR(1)的 例题1 例:为语言L = { ambn | n > m ≥ 0 }写三个文法,它们分别是 LR(1)的、二义的和非二义且非LR(1)的 LR(1)文法:S  AB A  aAb | ε B  Bb | b 非二义且非LR(1)的文法:S  aSb | B B  Bb | b 二义的文法:S  aSb | Sb | b a a a b b b b b a a a b b b b b a a a b b b b b

例题2 例:试说明下面文法不是LR(1)的: L  M L b | a M  ε M b L a  句子abbb的分析树

例:下面的文法不是LR(1)的,对它略做修改,使之成为 一个等价的SLR(1)文法 例题3 例:下面的文法不是LR(1)的,对它略做修改,使之成为 一个等价的SLR(1)文法 program  begin declist ; statement end declist  d ; declist | d statement  s ; statement | s 该文法产生的句子的形式是 begin d ; d ; … ; d ; s ; s ; … ; s end 修改后的文法如下: program  begin declist statement end declist  d ; declist | d ;

3.5 LR分析器 例题4 例:一个C语言的文件如下,第四行的if误写成fi: long gcd(p,q) long p,q; { fi (p%q == 0) return q; else return gcd(q, p%q); } 基于LALR(1)方法的一个编译器的报错情况如下: parse error before ‘return’ ( line 5). 是否违反了LR分析的活前缀性质?

编译原理与技术 第3章 语法分析 3.6 二义文法的应用 1学时

例:二义文法 E  E + E | E  E | (E) | id 非二义的文法: E  E + T | T 3.6 二义文法的应用 二义文法的特点: 二义文法决不是LR文法 简洁、自然 例:二义文法 E  E + E | E  E | (E) | id 非二义的文法: E  E + T | T T  T  F | F F  (E) | id 该文法有单个非终结符为右部的产生式 可以用文法以外的信息来消除二义 语法分析的效率高(基于消除二义后得到的分析表)

例 二义文法 E  E + E | E  E | (E) | id 规定:  优先级高于 +,两者都是左结合 3.6 二义文法的应用 3.6.1 使用文法以外信息来解决分析动作冲突 例 二义文法 E  E + E | E  E | (E) | id 规定:  优先级高于 +,两者都是左结合

I0 E'  •E E  •E + E E  •E  E E  •(E) E  •id I1 E'  E• 3.6 二义文法的应用 I0 E'  •E E  •E + E E  •E  E E  •(E) E  •id I1 E'  E• E  E •+ E E  E • E E I2 E  ( •E) ( I3 E  id• id I4 E  E + •E I5 E  E  •E I6 E  (E •) I7 E  E + E• I8 E  E  E• I9 E  (E)• +  )

state action goto id +  ( ) $ E s3 s2 1 s4 s5 acc 2 6 3 r4 4 7 5 8 s9 3.6 二义文法的应用 state action goto id +  ( ) $ E s3 s2 1 s4 s5 acc 2 6 3 r4 4 7 5 8 s9 s4/r1 s5/r1 r1 s4/r2 s5/r2 r2 9 r3

LR(0)项目集I7 I7 id + id + id 面临+,归约 E  E + E• id + id  id 面临,移进 3.6 二义文法的应用 LR(0)项目集I7 id + id + id 面临+,归约 id + id  id 面临,移进 面临 ) 和$,归约 LR(0)项目集I8 id  id + id 面临+,归约 id  id  id 面临,归约 I7 E  E + E• E  E •+ E E  E • E I8 E  E  E• E  E •+ E E  E • E

state action goto id +  ( ) $ E s3 s2 1 s4 s5 acc 2 6 3 r4 4 7 5 8 s9 3.6 二义文法的应用 state action goto id +  ( ) $ E s3 s2 1 s4 s5 acc 2 6 3 r4 4 7 5 8 s9 r1 r2 9 r3

从定义形式语言的角度说,第一个产生式是多余的 联系到语义处理,第一个产生式是必要的 对a sub i sup 2,需要下面第一种输出 3.6 二义文法的应用 3.6.2 特殊情况产生式引起的二义性 例:E  E sub E sup E E  E sub E E  E sup E E  {E} E  c 从定义形式语言的角度说,第一个产生式是多余的 联系到语义处理,第一个产生式是必要的 对a sub i sup 2,需要下面第一种输出 可归约可移进时,移进 I11: E  E sub E sup E· E  E sup E· . . . 按前面一个产生式归约

规范的LR分析器甚至在报告错误之前决不做任何无效归约 3.6 二义文法的应用 3.6.3 LR分析的错误恢复 (1)LR分析器在什么情况下发现错误 访问动作表时若遇到出错条目 访问转移表时它决不会遇到出错条目 决不会把不正确的后继移进栈 规范的LR分析器甚至在报告错误之前决不做任何无效归约

(2)紧急方式错误恢复 例如,在分析非终结符A时发现错误 3.6 二义文法的应用 (2)紧急方式错误恢复 例如,在分析非终结符A时发现错误 s . 栈 . . . . . . . . a . . A 发现错误 s : C α•Aβ A •bγ . . . s1 : C αA •β Ab·γ b

1) 退栈,直至出现状态s, 它有预先确定的A的转移 3.6 二义文法的应用 (2)紧急方式错误恢复 例如,在分析非终结符A时发现错误 1) 退栈,直至出现状态s, 它有预先确定的A的转移 s . 栈 . . . . . . . . a . . A 发现错误 s : C α•Aβ A •bγ . . . s1 : C αA •β Ab·γ b

3.6 二义文法的应用 (2)紧急方式错误恢复 例如,在分析非终结符A时发现错误 1) 退栈,直至出现状态s, 它有预先确定的A的转移 2) 抛弃若干输入符号,直至找到a, 它是A的合法后继 s . 栈 . . . . . . . . a . . A s : C α•Aβ A •bγ . . . s1 : C αA •β Ab·γ b

3.6 二义文法的应用 (2)紧急方式错误恢复 例如,在分析非终结符A时发现错误 1) 退栈,直至出现状态s, 它有预先确定的A的转移 2) 抛弃若干输入符号,直至找到a, 它是A的合法后继 3) 再把A和状态goto[s, A]压进栈,恢复正常分析 s A . s1 栈 . . . . . . . . a . . s : C α•Aβ A •bγ . . . s1 : C αA •β Ab·γ b

例 二义文法 E  E + E | E  E | (E) | id 规定: 优先级高于+,两者都是左结合 3.6 二义文法的应用 例 例 二义文法 E  E + E | E  E | (E) | id 规定: 优先级高于+,两者都是左结合 LR(0)项目集I4 I4 E  E + •E E  •E + E E  •E  E E  •(E) E  •id + . 栈 . . . id +  . . 4 本例无需退栈, 也无需丢弃符号 报错:缺少运算对象 将E和I7入栈

state action goto id +  ( ) $ E s3 s2 1 s4 s5 acc 2 6 3 r4 4 e7 7 5 8 3.6 二义文法的应用 state action goto id +  ( ) $ E s3 s2 1 s4 s5 acc 2 6 3 r4 4 e7 7 5 8 s9 r1 r2 9 r3

3.6 二义文法的应用 (3)短语级恢复 删除或插入符号,纠正局部错误

state action goto id +  ( ) $ E s3 e1 s2 d 1 e4 s4 s5 acc 2 e6 6 3 r4 3.6 二义文法的应用 state action goto id +  ( ) $ E s3 e1 s2 d 1 e4 s4 s5 acc 2 e6 6 3 r4 4 e7 7 5 e8 8 s9 e9 r1 r2 9 r3

I0 E'  •E E  •E + E E  •E  E E  •(E) E  •id I1 E'  E• 3.6 二义文法的应用 I0 E'  •E E  •E + E E  •E  E E  •(E) E  •id I1 E'  E• E  E •+ E E  E • E E I2 E  ( •E) ( I3 E  id• id I4 E  E + •E I5 E  E  •E I6 E  (E •) I7 E  E + E• I8 E  E  E• I9 E  (E)• +  )

例:下面的二义文法描述命题演算公式的语法,为它写一个 等价的非二义文法 3.6 二义文法的应用 例题1 例:下面的二义文法描述命题演算公式的语法,为它写一个 等价的非二义文法 S  S and S | S or S | not S | p | q | (S) 非二义文法的产生式如下 E  E or T | T T  T and F | F F  not E | ( E) | p | q ? not p and q有两种不同的最左推导 not p and q not p and q F  not F | ( E) | p | q

例:设计一个文法:字母表{a, b}上a和b的个数相等的所有 串的集合 3.6 二义文法的应用 例题2 例:设计一个文法:字母表{a, b}上a和b的个数相等的所有 串的集合 二义文法:S  a S b S | b S a S | ε aabbabab aabbabab S S S S 二义文法:S  a B | b A | ε A  a S | b A A B  b S | a B B aabbabab aabbabab aabbabab B B B B B B

例:设计一个文法:字母表{a, b}上a和b的个数相等的所有 串的集合 3.6 二义文法的应用 例题2 例:设计一个文法:字母表{a, b}上a和b的个数相等的所有 串的集合 非二义文法:S  a B S | b A S | ε A  a | b A A B  b | a B B a abb abab a B S b, abb, aabbb, ababb,

编译原理与技术 第3章 语法分析 3.7 语法分析器的生成器 

3.7.1 分析器的生成器Yacc Yacc源程序 Yacc y.tab.c translate.y 编译器 C a.out 输出 输入 3.7 语法分析器的生成器 3.7.1 分析器的生成器Yacc Yacc 编译器 Yacc源程序 translate.y y.tab.c C a.out 输入 输出

3.7 语法分析器的生成器 3.7.2 用Yacc处理二义文法 例:简单计算器 输入一个表达式并回车,显示计算结果 也可以输入一个空白行

3.7 语法分析器的生成器 %{ # include <ctype .h> # include <stdio.h > # define YYSTYPE double / 将栈定义为double类型 / %} %token NUMBER %left ‘+’ ‘-’ %left ‘’ ‘/ ’ %right UMINUS %%

3.7 语法分析器的生成器 lines : lines expr '\n' {printf ( "%g \n", $2 ) } | lines '\n' | / ε / ; expr : expr '+' expr {$$ = $1 + $3; } | expr '-' expr {$$ = $1 - $3; } | expr '' expr {$$ = $1  $3; } | expr '/' expr {$$ = $1 / $3; } | '(' expr ')' {$$ = $2; } | '-' expr %prec UMINUS {$$ = -$2; } | NUMBER %% -5+10看成是 (-5)+10

3.7 语法分析器的生成器 yylex ( ) { int c; while ( ( c = getchar ( ) ) == ' ' ); if ( ( c == '.' ) | | (isdigit (c) ) ) { ungetc (c, stdin); scanf ( "% lf", &yylval); return NUMBER; } return c; 为了C编译器能准确报告yylex函数中错误的位置,需要在生成 的程序y.tab.c中使用编译命令#line,指示编译后代码行号

决定哪些“主要的”非终结符将有错误恢复与它们相关 联 3.7 语法分析器的生成器 3.7.3 Yacc的错误恢复 编译器设计者的工作 决定哪些“主要的”非终结符将有错误恢复与它们相关 联 为各主要非终结符A加入形式为 A  error α 的错误产 生式,其中 α 是文法符号串 为这样的产生式配上语义动作 Yacc把错误产生式当作普通产生式处理

遇到语法错误时 s . 栈 . . . . . . . . . . . A 发现错误 s : C  β1 •Aβ2 3.7 语法分析器的生成器 遇到语法错误时 s . 栈 . . . . . . . . . . . A 发现错误 s : C  β1 •Aβ2 A  •error α . . . s1 : C  β1A •β2 s2 : A  error •α error 

从栈中弹出状态,直到发现栈顶状态的项目集包含形为 A  •error α 的项目为止 把虚构的终结符 error“移进”栈 3.7 语法分析器的生成器 遇到语法错误时 从栈中弹出状态,直到发现栈顶状态的项目集包含形为 A  •error α 的项目为止 把虚构的终结符 error“移进”栈 s . 栈 . . . . . . . . . . . A 发现错误 s : C  β1 •Aβ2 A  •error α . . . s1 : C  β1A •β2 s2 : A  error •α error  error

从栈中弹出状态,直到发现栈顶状态的项目集包含形为 A  •error α 的项目为止 把虚构的终结符 error“移进”栈 3.7 语法分析器的生成器 遇到语法错误时 从栈中弹出状态,直到发现栈顶状态的项目集包含形为 A  •error α 的项目为止 把虚构的终结符 error“移进”栈 忽略若干输入符号,直至找到 α,把 α 移进栈 s error . α 栈 . . . . . . . . . . . A s : C  β1 •Aβ2 A  •error α . . . s1 : C  β1A •β2 s2 : A  error •α 

从栈中弹出状态,直到发现栈顶状态的项目集包含形为 A  •error α 的项目为止 把虚构的终结符 error“移进”栈 3.7 语法分析器的生成器 遇到语法错误时 从栈中弹出状态,直到发现栈顶状态的项目集包含形为 A  •error α 的项目为止 把虚构的终结符 error“移进”栈 忽略若干输入符号,直至找到 α,把 α 移进栈 把 error α 归约为A,恢复正常分析 s s1 . 栈 . . . . . . . . . . . A s : C  β1 •Aβ2 A  •error α . . . s1 : C  β1A •β2 s2 : A  error •α error 

lines : lines expr '\n' {printf ( "%g \n", $2 ) } | lines '\n' 3.7 语法分析器的生成器 增加错误恢复的简单计算器 lines : lines expr '\n' {printf ( "%g \n", $2 ) } | lines '\n' | / ε / | error '\n' {yyerror ( "重新输入上一行"); yyerrok;} ;

0型文法(短语文法)、1型文法(上下文有关文法)、2 型文法(上下文无关文法)、3型文法(正规文法) 推导、最左推导、最右推导、分析树 3 语法分析 本章要点 文法和语言的基本知识 0型文法(短语文法)、1型文法(上下文有关文法)、2 型文法(上下文无关文法)、3型文法(正规文法) 推导、最左推导、最右推导、分析树 二义性的消除、左递归的消除、提左因子的方法 从正规式构造文法、从语言构造文法 自上而下分析(无左递归,无公共左因子) FIRST集合和FOLLOW集合的计算,LL(1)文法的条件及 判断 递归下降预测分析(函数形式) 非递归预测分析:预测分析表的编写,多重定义的消除

句柄、活前缀、项目与项目集、拓广文法、搜索符 识别活前缀的DFA构造 SLR(1)分析:分析表的编写 规范LR(1)分析:分析表的编写 3 语法分析 本章要点 自下而上分析 句柄、活前缀、项目与项目集、拓广文法、搜索符 识别活前缀的DFA构造 SLR(1)分析:分析表的编写 规范LR(1)分析:分析表的编写 LALR(1)分析:同心项目集的合并 二义文法:移进-归约冲突、归约-归约冲突 非SLR/LR/LALR文法的判定:寻找冲突 语法分析的错误恢复方法

习题 文法和语言基础 3.2 3.4(b)(c) 3.6(a)(b)(c) 自上而下分析、LL(1) 3.8 3.10 3 语法分析 习题 文法和语言基础 3.2 3.4(b)(c) 3.6(a)(b)(c) 自上而下分析、LL(1) 3.8 3.10 3.15(第二版3.14) 自下而上分析 3.16(第二版3.15)

习题 SLR(1) 3.19(a) (第二版3.18(a)) 3.21 (a) (第二版3.20 (a)) LR(1) 3 语法分析 习题 SLR(1) 3.19(a) (第二版3.18(a)) 3.21 (a) (第二版3.20 (a)) LR(1) 3.30(第二版3.28) LALR(1) 3.22(第二版3.21) 3.24(第二版3.23)