移进一归约分析冲突 n归约-归约冲突 eg20文法Gg 1) Stat >id para list) expr: = expr 2) para list>para list, para para 3 para->id 4)expr>id( expr list 5)expr-id 6) expr_list->expr_list, expr |expr 2021/2/2 《编译原理与技术》讲义 21
2021/2/2 《编译原理与技术》讲义 21 移进－归约分析冲突 归约-归约冲突 e.g.20 文法G9 1）Stat→id ( para_list ) | expr := expr 2）para_list→para_list , para | para 3）para→id 4）expr→id ( expr_list ) 5）expr→id 6）expr_list→expr_list , expr | expr
e.9.20分析输入串id(id,id) expr>id 分析栈 目标:数、输入串 S id( id 组引用 ,id)$ 1) S id (expr d)$ 2) $id( para ,id)$ para->id,目标:过程 调用语句 2021/2/2 《编译原理与技术》讲义 22
2021/2/2 《编译原理与技术》讲义 22 e.g.20分析输入串id(id,id)$ 分析栈 输入串 $ id ( id , id ) $ 1) $ id ( expr , id ) $ 2) $ id ( para , id ) $ para→id，目标：过程 调用语句 expr→id 目标：数 组引用
LR分析器 高效易实现的自底向上的分析方法 ■文法限制少,适用于大多数CFG(包括含左 递归、左因子的文法) nLR(k)分析器 L一从左自右读( read from Left to right) R一构造最右推导的逆( for constructing a Rightmost derivation in reverse k一向前看符号的个数( the number of input symbols of lockhead 2021/2/2 《编译原理与技术》讲义
2021/2/2 《编译原理与技术》讲义 23 LR分析器 高效易实现的自底向上的分析方法 文法限制少，适用于大多数CFG（包括含左 递归、左因子的文法） LR（k）分析器 L － 从左自右读（read from Left to right） R－ 构造最右推导的逆（for constructing a Rightmost derivation in reverse） k － 向前看符号的个数（the number of input symbols of lookhead）
LR分析器 输入串a1a Top LR控制程序 输出 状态符号栈 LR分析表 0 动作表转移表 Bottom Action GOTO 2021/2/2 《编译原理与技术》讲义 24
2021/2/2 《编译原理与技术》讲义 24 LR分析器 输入串 LR控制程序 LR分析表 Sm Xm . . S0 a1 . . ai . . $ 状 态 符 号 栈 输出 Top Bottom 动作表 Action 转移表 GOTO
LR分析器 ■格局:状态符号栈输入 S0…X1S1S,X+1…n$> n分析表 动作表( Action): S×(Σ{})→>{shit, reduce, accept,eror} 转移表(GOTO): S×V→>S 2021/2/2 《编译原理与技术》讲义 25
2021/2/2 《编译原理与技术》讲义 25 格局： 状态符号栈 输入串 <S0… …Xi-1Si-1XiSi， Xi+1……Xn$> 分析表 ∙ 动作表（Action）： S （{$}）→ { shift , reduce, accept, error} ∙ 转移表（GOTO）： S VN → S LR分析器