编译原理自底向上优先分析法.ppt

编译原理自底向上优先分析法
学****目标:
掌握:构造算符优先关系表,进行算符优先分析,构造优先函数
理解:算符优先文法,最左素短语
了解:简单优先分析法
1 自底向上分析方法概述
2 自底向上优先分析方法概述
3 算符优先分析法
1 自底向上分析方法概述
基本思想
从输入符号串开始,利用文法的产生式逐步进行归约,试图归约到文法开始符
从语法树角度看,是以输入符号串作为语法树的末端结点符号串,自底向上的构造语法树,使文法开始符正好是该语法树的根。如果最终根结点是开始符,则输入符号串是语言的一个句子,否则不是。
自底向上分析过程实际上是一个不断进行直接归约的过程。
遇到的问题
如何找出进行直接归约的“可归约串”(句柄)
基本实现方法-“移进-归约”方法
引进一个先进后出的符号栈来存放符号
对输入符号串自左向右进行扫描,并把当前输入符号下推入栈中(移进),
边移进边分析,一旦栈顶符号串形成某个句型的句柄(为某产生式的右部)时,就用相应的非终结符(产生式的左部)替换它(归约)。
重复这一过程,直到输入符号串的末端,此时如果栈中只剩文法开始符号,则输入符号串是文法的句子,否则不是。
规范归约:
自底向上分析的移进-归约过程是自顶向下最右推导的逆过程,因为最右推导为规范推导,所以自左向右的归约称为规范归约。
例文法: (1) S→aAcBe (2)   A→b
(3)   A→Ab (4) B→d
输入串 abbcde#的最右推导的过程为:
S=>aAcBe=>aAcde=>aAbcde=>abbcde
自底向上分析的过程为:
abbcde|-aAbcde|-aAcde|-aAcBe|-S
例文法: (1) S→aAcBe (2)   A→b
(3)   A→Ab (4) B→d
判断输入串 abbcde# 是否为该文法的句子
用符号栈对输入符号串自底向上的分析过程为:
归约(S→aAcBe)
#
#aAcBe
10)
接受
#
#S
11)
移进e
e#
#aAcB
9)
归约(B→d)
e#
#aAcd
8)
移进d
de#
#aAc
7)
归约(A→Ab)
cde#
#aAb
5)
移进c
cde#
#aA
6)
移进b
bcde#
#aA
4)
归约(A→b)
bcde#
#ab
3)
移进b
bbcde#
#a
2)
移进a
abbcde#
#
1)
动作
输入符号串
符号栈
步骤
关键问题:如何在分析的过程中确定句柄
何时移进?栈顶末形成句柄
何时归约?栈顶形成句柄
常用自底向上分析法:
算符优先分析法(3)
LR类分析法(第7章)
2 自底向上优先分析法概述
优先分析法两类:
简单优先分析法
基本思想:按一定原则定义文法中所有符号(终结符和非终结符)之间的优先关系,按照这种关系确定归约过程中的句柄并实行归约。
是一种规范归约。
简单优先分析法准确、规范,但效率低,不实用,不介绍。
算符优先分析法
基本思想:只定义文法中终结符之间的优先关系(不考虑非终结符),并由这种关系指导分析过程
不是规范归约
算符优先分析法分析速度快,特别适用于表达式的分析。缺点是不规范,常常要采用适当措施克服其缺点。
3 算符优先分析法
算符优先分析法特别适用于表达式的分析
从表达式得到的启发:
表达式的归约顺序与运算顺序是一样的
通常算术表达式的运算次序是先乘除后加减,同优先级时服从左结合
E→E+T|T
T→T×F|F
F→(E)|i
符号串E+T+T×F的归约过程为:
E+T+T×F |- E+T×F |- E+T |- E