编译原理 算符优先分析法

1、4.3 自下而上分析法的一般原理 1 1 自下而上语法分析概述自下而上语法分析概述 基本思想：基本思想：用一个寄存文法符号的栈栈，将一个输入串反向归约归约至文法的开始符号。 特点：特点：效率高、文法限制少。1 1 自下而上语法分析概述自下而上语法分析概述 移进归约过程实例。 例4.11 设有文法GA： (1)A aBcDe (2)B b (3)B Bb (4)D d对输入串abbcde$的移进归约分析过程 对输入串abbcde$移进归约分析过程： 步骤 符号栈 输入串 动作012345678910$a$ab$aB$aBb$aB$aBc$aBcd$aBcD$aBcDe$Aabbcde$bbcde

2、$bcde$bcde$cde$cde$de$e$e$a进栈b进栈用B b归约b进栈用B Bb归约c进栈d进栈用D d归约e进栈用A aBcDe归约分析成功2 2 移进归约的基本思想 (1)用一个栈寄存文法符号，将一个终结符推进栈; (2)是将0个或多个符号从栈中弹出，用相应产生式的左部一个非终结符压入栈; 把栈顶被归约的一串符号称为 (3)重复这一过程直至整个输入串分析完毕; (4)最终栈中，则所分析的输入串是文法的正确句子;否则，出错。可归约串可归约串3 分类 算符优先分析法算符优先分析法 规范归约分析法 简单优先分析法 LR分析法分析法用 刻画可归约串用 刻画可归约串4.4 4.4 算符优

3、先分析法算符优先分析法 4.4.1 方法概述 1 特点 适合分析各类表达式; 宜于手工实现; 规定运算符之间的优先顺序(优先关系，结合性质)。 通过比较算符之间的优先关系确定可归约串。4.4.1 方法概述 2 优先关系 例 文法GE： E E+E|E*E|(E)|id 对输入串id+id*id的规范归约过程。(1)id+id*id(2)E+id*id(3)E+E*id(4)E+E*E(5)E+E(6)E(1)id+id*id(2)E+id*id(3)E+E*id(4)E*id(5)E*E(6)E*优先于：优先于*：4.4.1 方法概述 3 优先关系种类 任何两个a和b可能的优先关系有3种： a

4、 b: a的优先级低于b a b: a的优先级等于b a b: a的优先级高于b注：优先关系与出现的有关，不同于数学符号。4.4.1 方法概述 4 优先关系矩阵(表) 矩阵的行和列都是文法的终结符; 矩阵元素是两终结符间的优先关系。 算符优先分析法借助优先关系表寻找句型的可归约串。 算符优先关系表实例 + * id ( ) $ + * id ( ) $栈顶第一个终结符当前输入串首字符4.4.2 算符优先文法的定义 1 算符文法的定义 设有文法G，若G中形如U VW的规则，其中V和W为，则G称为算符文法，也称OG文法。性质： 1.在算符文法中任何句型都不包含两个相邻的非终结符。 2.如Ab或bA

5、出现在算符文法的句型 中，则 中任何含b的短语必含有A。4.4.2 算符优先文法的定义 2 算符优先关系的定义 在OG中定义算符优先关系： (1)a b :含有P ab，或 P aQb的 规则。 (2)a b :含有P aR的规则，且R b或 R Qb (3)a b:含有P Rb的规则，且R a或 R aQ。4.4.2 算符优先文法的定义 2 算符优先关系的定义 规定： 若S a或S Ca，则$ a 若S a或S aC，则a $4.4.2 算符优先文法的定义 3 算符优先文法的定义 设有一个不含 规则的OG文法G， 如果任意两个终结符间至多有一种算符关系存在， 则称G是算符优先文法，也称OPG

6、文法。 结论：算符优先文法是无二义的。4.4.3 算符优先关系表的构造 1 FIRSTVT集、 LASTVT集 FIRSTVT(A)=b|A b 或 A Bb ,b VT,B VN 即：非终结符往下推导所有可能出现的首个算符的集合LASTVT(A)=a|A a A aB, a VT,B VN 即：非终结符往下推导所有可能出现的最后一个算符的集合4.4.3 算符优先关系表的构造 2 算符优先关系表的构造方法 (1)为每个非终结符计算FIRSTVT(A),LASTVT(A) (2)计算算符之间的优先关系，并填表。计算方法： 关系:若Aab 或A aBb,则a b 关系:若A aB,则 b FIRS

7、TVT(B),a b 关系:若A Bb,则 a LASTVT(B),a b (3) 最后，在表中填入的优先关系：对FIRSTVT(S)中所有b,置$ b; 对 LASTVT(S)中所有a,置a $. 置 $ $。 例4.12 文法GE: E E+T|T T T*F|F F (E)|id构造该文法的算符优先关系表。 FIRSTVT LASTVT E T F +,*,(,id *,(,id (,id +,*,),id *,),id ),idHomework: (P105)- 4.5 (2)4.4.4 算符优先分析算法的设计 0 算符优先分析法与规范归约的区别算符优先分析法:只考虑终结符之间的优先关

8、系来确定可归约串，而与非终结符无关。规范归约:自上而下最右推导的逆过程。例4.12文法GE: E E+T|T T T*F|F F (E)|id 句子id*id+id的自下向上的语法分析过程。规范归约是最右推导的逆过程。算符优先分析法中，去掉了单个非终结符的归约。EE+TTT*FFididFid4.4.4 算符优先分析算法的设计 1 最左素短语定义： 句型的素短语是 一个短语；至少包含一个终结符；除自身之外不再包含其他素短语处于句型最左边的素短语为最左素短语求文法GE的句型T+T*F+id的素短语和最左素短语E E+T|T T T*F|F F (E)|idE+ETE+TTT*FFid短语：,T*

9、F,T+T*Fid,T+T*F+id素短语：最左素短语：T*F, idT*FHomework: (P105)-4.64.4.4 算符优先分析算法的设计 2 识别最左素短语方法算符优先文法的句型可以表示为：$N1a1N2a2NnanNn+1$ ,Ni为VN或空,ai为VT.句型的最左素短语是满足下列条件的最左子串NiaiNi+1ai+1.NjajNj+1 : ai-1 ai ai ai+1 , . ,aj-1 aj aj aj+1注意:出现在ai左端的Ni和aj右端的Nj+1属于素短语.求句型 $T+T*F+id$ 的最左素短语。 把该句型写成算符优先分析形式: $N1a1N2a2N3a3a4$

10、 由优先表得: $ a1 a2 a3 a4 $ 故最左素短语为:N2a2N3 即:T*F4.4.4 算符优先分析算法的设计 3 算符优先算法过程(移进归约) (1)使用栈存放文法符号,初始化为$。 (2)如果当前栈顶终结符和待输入符号之间的关系是 或 ,则移进输入符号。 (3)如果当前栈顶终结符和待输入符号之间的优先关系是 ,表明已找到最左素短语的尾,查找栈内优先关系相同的符号串,进行归约。 (非终结符对可归约串的识别没有影响,在归约时可用任意的N代替。) (4)如果出现两个终结符之间没有任何优先关系,则出错。 (5)当读到句子结束符$,栈中只剩下$N时,成功。对4.12中的文法GE： E E+T|T T T*F|F F (E)|id写出输入串id+id$的算符优先分析过程。 S栈优先关系 当前符号 输入流 动作$id$N$N+$N+id$N+N$N id + + id $ $ $+id$id$id$ 移进 归约 移进 移进 归约 归约 接受 S栈优先关系 当前符号 输入流 动作 4.4.6 算符优先分析法的局限性 1 一般语言的文法很难满足算符优先文法的条件，仅在表