编译原理与技术 第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型文法:AaB 或 Aa,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]=XY1Y2…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]=XY1Y2…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时出错(例如:a20d+5) 非终 结符 输 入 符 号 3.3 自上而下分析 例题 例:栈顶为T',面临id时出错(例如:a20d+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$ 移进 $Eid2 + id3$ 按 E id 归约 $EE + id3$ 移进 $EE+ id3$ 移进 $EE+id3 $ 按 E id 归约 $EE+E $ 按 E E+E 归约 $EE $ 按 E EE 归约 $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 归约 Fid,M[0,F]=3 0 F 3 id + id $ A[3,]=r4 归约 TF,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 归约 Fid,M[7,F]=10 0 T 2 7 F 10 + id $ A[10,+]=r3 归约 TTF,M[7,T]=2 0 T 2 + id $ A[2,+]=r2 归约 ET,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 归约 Fid,M[6,F]=3 0 E 1 + 6 F 3 $ A[3,$]=r4 归约 TF,M[6,$]=9 0 E 1 + 6 T 9 $ A[9,$]=r1 归约 EE+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 归约 Fid,M[0,F]=3 0 F 3 A[3,]=r4 归约 TF,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 归约 Fid,M[7,F]=10 0 T 2 7 F 10 A[10,+]=r3 归约 TTF,M[7,T]=2 A[2,+]=r2 归约 ET,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 归约 Fid,M[6,F]=3 0 E 1 + 6 F 3 A[3,$]=r4 归约 TF,M[6,$]=9 0 E 1 + 6 T 9 A[9,$]=r1 归约 EE+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 归约 Fid,M[0,F]=3 0 F 3 A[3,]=r4 归约 TF,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 归约 Fid,M[7,F]=10 0 T 2 7 F 10 A[10,+]=r3 归约 TTF,M[7,T]=2 A[2,+]=r2 归约 ET,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 归约 Fid,M[6,F]=3 0 E 1 + 6 F 3 A[3,$]=r4 归约 TF,M[6,$]=9 0 E 1 + 6 T 9 A[9,$]=r1 归约 EE+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)项目(简称项目) 在右部的某个地方加点的产生式 用加点来表示分析过程中的状态 例:AXYZ对应有四个项目 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+TF 的所有前缀都可接受
也可以构造一个识别活前缀的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•, $ 03132432 831802 6162762 961925 201 03132432 831802 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/$ 036136247 36289361 8902error 输入为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 •β Ab·γ b
1) 退栈,直至出现状态s, 它有预先确定的A的转移 3.6 二义文法的应用 (2)紧急方式错误恢复 例如,在分析非终结符A时发现错误 1) 退栈,直至出现状态s, 它有预先确定的A的转移 s . 栈 . . . . . . . . a . . A 发现错误 s : C α•Aβ A •bγ . . . s1 : C αA •β Ab·γ b
3.6 二义文法的应用 (2)紧急方式错误恢复 例如,在分析非终结符A时发现错误 1) 退栈,直至出现状态s, 它有预先确定的A的转移 2) 抛弃若干输入符号,直至找到a, 它是A的合法后继 s . 栈 . . . . . . . . a . . A s : C α•Aβ A •bγ . . . s1 : C αA •β Ab·γ 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 •β Ab·γ 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)