编译原理算符优先分析法.ppt

4.3 自下而上分析法的一般原理•1 1 自下而上语法分析概述自下而上语法分析概述 基本思想：基本思想：用一个寄存文法符号的栈栈，将一个输入串反向归约归约至文法的开始符号 特点：特点：效率高、文法限制少1 1 自下而上语法分析概述自下而上语法分析概述•移进－归约过程实例 例4.11 设有文法G[A]： (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$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)最终栈中只剩下左界符只剩下左界符$ $和开始符号和开始符号S S，则所分析的输入串是文法的正确句子;否则，出错。

可归约串可归约串3 分类 ◆算符优先分析法算符优先分析法 ◆规范归约分析法 简单优先分析法 LR分析法分析法用 句柄句柄 刻画可归约串用 最左素短语最左素短语 刻画可归约串4.4 4.4 算符优先分析法算符优先分析法•4.4.1 方法概述•1 特点 适合分析各类表达式; 宜于手工实现; 规定运算符之间的优先顺序(优先关系，结合性质) 通过比较算符之间的优先关系确定可归约串4.4.1 方法概述•2 优先关系 例 文法G[E]： 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 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出现在算符文法的句型 中，则 中任何含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文法 结论：算符优先文法是无二义的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)计算算符之间的优先关系，并填表。

计算方法： ★ 关系:若A　…ab… 或A …aBb,则a b ★　 关系:若A …aB…,则 b FIRSTVT(B),a b ★　 关系:若A …Bb…,则 a LASTVT(B),a b (3) 最后，在表中填入界符界符的优先关系：　对FIRSTVT(S)中所有b,置$ b; 对 LASTVT(S)中所有a,置a $. 置 $￿￿￿￿￿￿$ 例4.12 文法G[E]: E E+T|T T T*F|F F (E)|id构造该文法的算符优先关系表 FIRSTVT LASTVT E T F {+,*,(,id} {*,(,id} {(,id} {+,*,),id} {*,),id} {),id}Homework: (P105)- 4.5 (2)4.4.4 算符优先分析算法的设计•0 算符优先分析法与规范归约的区别　算符优先分析法:　　　只考虑终结符之间的优先关系来确定可归约串，而与非终结符无关。

　规范归约:　　　自上而下最右推导的逆过程例4.12文法G[E]: E E+T|T T T*F|F F (E)|id 句子id*id+id的自下向上的语法分析过程规范归约是最右推导的逆过程算符优先分析法中，去掉了单个非终结符的归约EE+TTT*FFididFid4.4.4 算符优先分析算法的设计•1 最左素短语　定义： 句型的素短语是　 一个短语；　　　至少包含一个终结符；　　　除自身之外不再包含其他素短语．　处于句型最左边的素短语为最左素短语．求文法G[E]的句型T+T*F+id的素短语和最左素短语．　E E+T|T T T*F|F F (E)|idE+ETE+TTT*FFid短语：Ｔ,T*F,T+T*Fid,T+T*F+id素短语：最左素短语：T*F, idT*FHomework: (P105)-4.64.4.4 算符优先分析算法的设计•2 识别最左素短语方法　算符优先文法的句型可以表示为：　$N1a1N2a2…NnanNn+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$ 由优先表得: $ a1 a2 a3 a4 $ 故最左素短语为:N2a2N3 即:T*F4.4.4 算符优先分析算法的设计•3 算符优先算法过程(移进－归约) (1)使用栈存放文法符号,初始化为$ (2)如果当前栈顶终结符和待输入符号之间的关系是 或 ,则移进输入符号 (3)如果当前栈顶终结符和待输入符号之间的优先关系是 ,表明已找到最左素短语的尾,查找栈内优先关系相同的符号串,进行归约 (非终结符对可归约串的识别没有影响,在归约时可用任意的N代替) (4)如果出现两个终结符之间没有任何优先关系,则出错 (5)当读到句子结束符$,栈中只剩下$N时,成功对4.12中的文法G[E]： 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 一般语言的文法很难满足算符优先文法的条件，仅在表达式局部中应用;•2 由于忽略非终结符在归约过程中的作用，可能导致对错误的句子得到正确的归约。

例4.13 设有算符优先文法 A A;D|D D D(E)|F F a|(A) E E+A|A写出输入串(a+a)$的算符优先分析过程该文法的算符优先关系表为：文法4.13 算符优先关系表： ; a + ( ) $ ; a + ( ) $。