当前位置：文档之家 › 第5章 自底向上语法分析

第5章 自底向上语法分析

  • 格式：ppt
  • 大小：155.00 KB
  • 文档页数：25

下载文档原格式

  / 25

合集下载

自底向上语法分析

自底向上语法分析
2014-6-13
E E E
E + id *
E id
6
id
动作
栈
输入缓冲区
1) # id1+id2*id3# 例5.2 分析过程 2) 移进 #id1 +id2*id3# 3) 归约 E→id #E +id2*id3# E 4) 移进 #E+ id2*id3# 5) 移进 #E+id2 *id3# 6) 归约 E→id #E+E *id3# E 7) 8) 9) 移进 移进 归约 E→id #E+E* #E+E*id3 #E+E*E id3# # # # #
E E
E
E
E
* id
10
10) 归约 E→E*E #E+E 11) 归约 E→E+E #E 12) 接受
2014-6-13
id + id
移进-归约分析中的问题
1) 移进归约冲突 – 例5.2中的 6)可以移进 * 或按产生式 E→E+E归约 2) 归约归约冲突 – 存在两个可用的产生式 • 各种分析方法处理冲突的方法不同 • 如何识别句柄？
第5章 自底向上语法分析
5.1.1 移进-归约分析
•系统框架
–采用表驱动的方式实现 –输入缓冲区：保存输入符号串 –分析栈：保存语法符号—已经得到的那部 分分析结果 –控制程序：控制分析过程，输出分析结 果——产生式序列 –格局：栈+输入缓冲区剩余内容=“句型”
2014-6-13 2
移进-归约语法分析器的总体结构
23
例5.7 E→E+T|E-T|T T→T*F|T/F|F F→(E)|id， 试利用算符优先分析法对id+id进行分析

第5章 语法分析(2)自下而上分析

第5章 语法分析(2)自下而上分析

则成功，达不到这种格局则输入串有错误。

栈中符号串+剩余输入串 = 规范句型。
26
规范归约分析算法
1. 在栈底放入# ，在输入串尾附上#; 2. 逐个移入输入符号,当栈顶形成句柄时，进行归约; 3. 重复2 直到输入串已全部进栈，仅剩#, 4. 若栈中归约为#S, 表示分析成功，输入串为合法的 句子,否则为非法句子.
2
5.1 自下而上分析的基本问题

自下而上分析法的基本思想：
从输入串出发，反复利用产生式逐步进行 ‚归约‛，如果最后能归约到文法的开始符 号，则输入串是句子，否则输入串有语法错 误。

各种不同自下而上分析法一个共同特点是：
边输入单词符号（移进栈），边归约；
3
5.1 自下而上分析的基本问题

自下而上分析的基本技术是采用归约栈,如下图所示: #

或者说从文法的开始符号产生句子。

自下而上分析采用的方法是归约，从叶子到根构造分析树。

或者说从句子开始归约出文法的开始符号。

语法树的一个子树：由该树的某个结连同它的所有子孙组成。 在自下而上分析过程中，每一步归约都可画出一棵子树。
例如,上例中的归约过程可描述为如下分析树:
9
例5.2：文法G[S], 其4条产生式如下： ① S→aABe ② A→b ③ A→Abc ④ B→d 对句子abbcde的分析 最右推导 SaABeaAdeaAbcdeabbcde 最左归约 abbcde，aAbcde ，aAde，aABe ，S S S aABe aAde aAbcde abbcde
S （2）每次归约用的句柄： ， (a,(a))， ， ， ， ， ， ( (L,(S)) (L,(L)) (L,S) (L) S (S,(a)) (L,(a)) L )

第五章 语法分析-自底向上分析方法

第五章 语法分析-自底向上分析方法

构造LRSM的思想： 如果在状态项目集ISi 中有项目A→B， 且B→是B的产生式，则在ISi 中增加项目 B→；对于ISi 这个过程继续到不可再扩 充为止。
构造LR(0)活前缀状态机LRSM的算法要点
构造初始状态 IS0：IS0=CLOSURE({Z→S})，并给 IS0标
Stack
LR分析模型
LR分析表
Action矩阵：行代表状态，列代表输入 符，而矩阵元素则表示相应的分析动作： Shift / Reduce / Accept / Error 。 GoTo矩阵：行代表状态，而列则代表语 法符号（非终极符，终极符），而矩阵 元素则表示移入或归约后的转向状态。 定义 若IS是一个LR(0)项目集，X是一个 文法符号，函数GO（IS, X）定义为 GO（IS, X）=CLOSURE（IS(X)），其中 IS(X)为LR(0)项目集IS的投影。
id
E→E+ T T→ id T→ (E)
E
7
S→E $ E→E +T
+
T→(E ) E→E +T
$
2 4
T
8
)
T→(E)
S→E $
E→E+T
GE的LRSM
LRSM给出了所有的可归活前缀
LRSM中的每个状态将对应一个饱和项目集： （1）其中一部分是由先驱状态分出来 (称为基本项目)； （2）一部分则是由基本项目扩展出来的 (称为扩展项目或派生项目)。派生部 分项目的特点是其中的“”出现在 产 生式右部的最左侧。

识别规约活前缀的LRSM的构造
派生定理


开始符产生式的右部是归约活前缀。 如果A是归约活前缀，且A→是产生式， 则也是归约活前缀。 任何归约活前缀，都可按上述方式被派生。 设文法开始符的产生式是： S →1|2|…|n RPSG={1,…,n}{|ARPSG,A→P}

5第五章 自底向上语法分析法1

5第五章 自底向上语法分析法1

• 总结： 采用图的遍历完成自底向上的分析。
分析过程中有个急需解决的问题：谁先规约？
解决方法：通过比较终结符号之间的优先关系来确定谁 先规约。 由于自底向上的分析过程就是一个图的遍历过程，因此 分析程序通常会使用一个分析栈来辅助分析。 自底向上的分析开始时栈是空的，在成功分析的末尾就 只有开始符号。
文法G[A]={A→(A) | a}分隔如下：
A→.(A)
表示正准备开始分析
A→(.A)
表示(已被吸收，准备吸收A
A→(A.)
表示(A已被吸收，准备吸收)
A→(A).
表示(A)已被吸收，可以归约了
A→.a
表示正准备开始分析
A→a.
表示a已被吸收，可以归约了
有两个开始的地方,到底从谁开始? 解决方法:引入新的开始符号，扩充文法。
• LR(0)文法(LR(0) grammar)： LR(0) 项DFA图的 所有状态均不存在移进-归约冲突(shift-reduce conflict) 和归约-归约冲突(reduce-reduce conflict) 。
移进-归约冲突：即某个状态不能既包含一个“移 进的”项目A→.X （X是一个终结符)，又包含 一个如B→.的归约项。
$V+V *n
$V+V* n
$V+V*n
$V+V*V
$V+V
$V
• 试分析文法G[A]={A→(A) | a}所对应的串((a))。
（1）构造终结符优先关系表 （2）分析过程
分析栈 $ $( $(( $((a $((A $((A) $(A $(A) $A
输入串 ((a)) (a)) a)) )) )) ) )
主要内容

第 5 讲 自底向上优先分析法

第 5 讲 自底向上优先分析法

最左素短语
只规定算符（终结符）之间的优先关系。找到句 只规定算符（终结符）之间的优先关系。找到句 就归约，并不考虑规约到哪个非终结符名， 柄就归约，并不考虑规约到哪个非终结符名，不 是规范归约。 是规范归约。
简单优先分析法
按照文法符号（包括终结符和非终结符） 按照文法符号（包括终结符和非终结符） 的优先关系确定句柄。 的优先关系确定句柄。
动作
#<i,移进 移进 #<i>+,规约 规约 #<+,移进 移进 +<i,移进 移进 +<i>*,规约 规约 +<*,移进 移进 *<i,移进 移进 *<i>#,规约 规约 +<*>#,规约 规约 #<+>#,规约 规约 接受
+ + > - > * > / > ↑ > ( < ) > i > # <
算符优先关系表
算符文法的定义
定义 如果不含空产生式的上下文无关文法 G 中没 VW…的产生式 则称G 有形如 U→…VW 的产生式，其中V,W∈VN则称G 为 VW 的产生式，其中V,W 算符文法（OG）。 算符文法（OG）。 性质1 性质1：在算符文法中任何句型都不包含两个相邻的非 终结符.(数学归纳法) .(数学归纳法 终结符.(数学归纳法) 性质2 性质2：如 Vx 或 xV 出现在算符文法的句型 α 中， 其中V 其中V∈VN,x∈VT, 则 α 中任何含 x 的短语必含有 V.（反证法） V.（反证法） 注：证明的具体步骤见书P100 证明的具体步骤见书P100
1.
2.
将输入符号串a 将输入符号串a1a2a3...an#依次逐个存入符 号栈S 直到遇到栈顶符号a 的优先性> 号栈S中，直到遇到栈顶符号ai的优先性> 下一个待输入符号a 时为止。 下一个待输入符号aj时为止。 栈顶当前符号a 为句柄尾， 栈顶当前符号ai为句柄尾，由此向左在栈 中找句柄的头符号a 即找到a 为止。 中找句柄的头符号ak，即找到ak-1<ak为止。

自底向上的语法分析解读

自底向上的语法分析解读

程序4-4 简单优先分析驱动程序
int parser(void){ int i=0,k=0,r;stack[0]='#'; r=a[k++]; do{ int j,LeftSide; while(!IsHigherThan(stack[i],r)) {stack[++i]=r;r=a[k++];} j=i; while(! IsLowerThan (stack[j-1], stack[j])) j--; LeftSide= RightSideOfAProduction (stack[j],stack[i],i-j+1); if(LeftSide){ /*LeftSide!=0 means the production exists */ i=j;stack[i]=LeftSide; }else /* There is no production which matches the right side */ if(i==2 && r=='#' && stack[i] == STARTSYSBOL) return SUCCESS; else return ERROR; } while (1); } /* end of parser */
与的句柄之间的关系必有下述情况之一: A A
A
… … s t ... … … s t … ... … … s t … ... 1. s在句柄中, 3. s不在句柄中,而t 2. s与t均在句 而t不在句柄中 在句柄中 柄中 对于上述情况,我们规定, 情况1: s>t; 情况2: s=t; 情况3: s<t 另外,还有一种情况,就是s和t均不在句柄中,那么一定存在某句 型使得它们进入上述三种情况之一.

第5章 语法分析——自底向上分析


(d) aAcBe归约为S
(e)
5.2自底向上分析方法的一般过程
自底向上分析方法，也称为移进归约法，其过程是： 设置一个寄存符号的先进后出栈，称为符号栈。在 分析进行时，把输入符号逐个按扫描顺序移进栈里， 当栈顶符号串形成句柄(即为某条规则的右部)时，就 归约，把栈顶构成句柄的那个符号串用相应规则左 部的非终结符号来代替。再检查栈顶是否又出现了 新的句柄，若有，继续归约；若没有形成新的句柄， 则再从输入符号串移进新的符号，如此继续直到整 个输入符号串处理完毕。最终如果栈里只有识别符 号，则所分析的输入符号串为合法的句子，报告成 功；否则，输入串是不合法的符号串，报告错误。
5.3.2 LR分析表的构成
分析表的动作有下列四种：
1. 移进(Sn)：将输入符号aj移进符号栈，将状态n移进状态栈， 输入指针指向下一个输入符号。
2. 归约(R)：当栈顶形成句柄时，按照相应的产生式U→W进 行归约。若产生式右部W的长度为n，则将符号栈栈顶n个 符号和状态栈栈顶n个状态出栈，然后将归约后的文法符号 U移入符号栈，并根据此时状态栈顶的状态Si及符号栈顶的 符号U，查GOTO标，将GOTO[Si，U]移入状态栈。
第5章 语法分析——自底向上分析
在自底向上的分析方法中，分析过程从输入符号串开始， 通过反复查找当前句型的句柄，并使用规则，将找到的 句柄归约成相应的非终结符号，直到归约到开始符号。
5.1 规范推导、规范句型和规范归约
规范推导就是最右推导，而通过规范推导能得到的句型 就是规范句型。规范归约也称为最左归约，是规范推导 的逆过程，即在分析的每一步，将当前句型的句柄归约 成相应的非终结符号。
5.3.2 LR分析表的构成
LR分析表是LR分析器的核心部分，它由两部分组成，一是动作部 分ACTION表，二是状态转换部分GOTO表。表中S1、S2、…、Sn 为分析器的各个状态；a1、a2、…、am为文法的全部终结符号及 右界符#；X1、X2、…、Xk为文法的非终结符号。

语法分析--自底向上分析技术

5.3.3算符优先关系与算符优先文法 5.3.4算符优先文法句型的识别
• 质短语 • 算符优先识别算法
第五章 语法分析----自底向上分析技术
5.3算符优先分析技术
5.3.4算符优先文法句型的识别
• 质短语 • 算符优先识别算法
例 文法G[Z]: Z∷=E E∷=T|E+T T∷=F|T*F F∷=(E)|i 设有输入符号串i+(i+i)*i， 试识别它是否是文法的句子。
第五章 语法分析----自底向上分析技术
5.2 简单优先分析技术
5.2.1 优先关系与优先文法
5.2.2 简单优先分析技术的实现 5.2.3 简单优先分析技术的局限性及克服
第五章 语法分析----自底向上分析技术
5.2 简单优先分析技术
5.2.1优先关系与优先文法
• 寻找句柄的基本思想 • 优先关系及其应用 • 简单优先文法
5.3.1算符优先分析技术的引进 Tj＜Ti 当且仅当文法G中存在形如U∷=…TjV…的规则，其中V=>Ti…或V=>WTi…；
+
Tj ＞Ti 当且仅当文法G中存在形如U∷=…VTi…的规则，其中V=>…Tj 或V=>…TjW。
+ 5.3.2算符文法 Z∷=E E∷=T|E+T T∷=F|T*F F∷=(E)|i 例 设有文法G[Z]:
例5.1
步骤 （ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （ 7） （ 8） （ 9） （ 10） （ 11）
设有文法G[E]：E∷=E+E|E*E|(E)|i
栈 # #i #E #E* #E*i #E*E #E #E+ #E+i #E+E #E 输入 i*i+i# *i+i# *i+i# i+i# +i# +i# +i# i# # # # 动作 移入 归约 移入 移入 归约 归约 移入 移入 归约 归约 接受 E∷ =i E∷ =E+E E∷ =i E∷ =E*E E∷ =i 规则

编译原理 第5章

（3）X >·Y 当且仅当G中存在产生式A …BD…， 且B +…X和D *Y… （ X在 Y 的下层或X比 Y 先归约——规范归约/最左归约 ）
例：有文法G(S):
S→bAb A→( B | a B→Aa ) 解：文法符号优先关系推导如下： (1) 求=· 关系: 由S→bAb ， A→( B， B→Aa ) b =· A， A =· b， (=· B ， A =· a， a =· )
自底向上的语法分析
• 核心问题
– 寻找可归约串。对“可归约串”概念的不同定义， 就形成了不同的自底向上的分析方法。在算符优 先分析法中我们用“最左素短语”来刻画“可归 约串”，在“规范归约”中，则用“句柄”来刻 画“可归约串”
分析方法
• 输入串：
abbcde
S → a A c B e A → A b｜b B → d
S
b
>·
=· <·
>·
A
(
=·
<· <· =·
=·
<·
B
a
>·
>·
>·
>· =· =·
)
#
寻找句柄
>·
<· <·
>·
简单优先文法的定义： （1）在文法符号集中，任意两个符号之间最多只有 一种优先关系； （2）在文法中任意两个产生式没有相同的右部。
语法树结构如下：
S S S b S b
b
A b
B
b
U S0…Sj-1SjSj+1Sj+2… …Si-1SiSi+1…Sn
算符优先分析
• 我们要通过两个相邻符号SiSi+1之间的关系来找到句 柄： – SiSi+1在句柄内：必然有规则U …SiSi+1… – Si在句柄内部，但是Si+1在句柄之后：必然有规则 U …Si，且存在规范句型…USi+1…。 – 如果Si+1在句柄内，而Si在句柄外，那么必然存在 规范句型…SiU…，且U Si+1…。

编译原理作业集-第五章-修订

第五章语法分析—自下而上分析本章要点1. 自下而上语法分析法的基本概念：2. 算符优先分析法；3. LR分析法分析过程；4. 语法分析器自动产生工具Y ACC；5. LR分析过程中的出错处理。

本章目标掌握和理解自下而上分析的基本问题、算符优先分析、LR分析法及语法分析器的自动产生工具YACC等内容。

本章重点1．自下而上语法分析的基本概念：归约、句柄、最左素短语；2．算符优先分析方法：FirstVT, LastVT集的计算，算符优先表的构造，工作原理；3．LR分析器：（1）LR(0)项目集族，LR(1)项目集簇；（2）LR(0)、SLR、LR(1)和LALR(1)分析表的构造；（3）LR分析的基本原理，分析过程；4．LR方法如何用于二义文法；本章难点1. 句柄的概念；2. 算符优先分析法；3. LR分析器基本；作业题一、单项选择题：1. LR语法分析栈中存放的状态是识别________的DFA状态。

a. 前缀；b. 可归前缀；c. 项目；d. 句柄；2. 算符优先分析法每次都是对________进行归约：(a)句柄（b）最左素短语(c)素短语(d)简单短语3. 有文法G＝（｛S｝，｛a｝，｛S→SaS，S→ε｝，S），该文法是________。

a. LL(1)文法；b.二义性文法；c.算符优先文法；d.SLR(1)文法；4. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，和LL(1)分析法属于自顶向下分析；a. 深度分析法b. 宽度优先分析法c. 算符优先分析法d. 递归下降子程序分析法5. 自底向上语法分析采用分析法，常用的是自底向上语法分析有算符优先分析法和LR分析法。

a. 递归b. 回溯c. 枚举d. 移进－归约6. 一个LR(k)文法，无论k取多大，。

a. 都是无二义性的；b. 都是二义性的；c. 一部分是二义性的；d. 无法判定二义性；7. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，和LR分析法属于自底向上分析。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第五章 自底向上语法分析
思想： 思想： 移进－ 移进－归约 关键词： 关键词： 优先级、归约、 优先级、归约、句柄 1 自底向上优先分析法概述： 自底向上优先点 简单优先分析法基本思想 算符优先分析的基本思想
2
① a. b. c. • • •
简单优先分析法
优先关系 X ·=· Y 表示 和Y的优先级相等 表示X和 的优先级相等 X ·> Y 表示 的优先级比 的优先级高 表示X的优先级比 的优先级比Y的优先级高 X <· Y 表示 的优先级比 的优先级低 表示X的优先级比 的优先级比Y的优先级低 X ·=· Y 若G中存在产生式规则 →···XY··· 中存在产生式规则A 中存在产生式规则 X <· Y 若G中存在产生式规则 →···XB···,且B⇒+Y··· 中存在产生式规则A 中存在产生式规则 且 ⇒ X ·> Y 若G中存在产生式规则 →···BD···,且B⇒+···X 中存在产生式规则A 中存在产生式规则 且 ⇒ 和D ⇒*Y···
II.
按最左素短语归约 最左素短语归约
区别于规范归约 区别于规范归约 什么是最左素短语 最左素短语？ 什么是最左素短语？ III. 算符优先分析归约过程算法
5. 优先函数： 优先函数： 引进优先函数的原因 原因： 引进优先函数的原因：节省空间 优先函数的优缺点 优先函数的优缺点 优点： 优点：省空间 缺点：与优先关系矩阵不完全等价、无法及时纠错（ 缺点：与优先关系矩阵不完全等价、无法及时纠错（无法体 现无优先关系的情况） 现无优先关系的情况）
③ 简单优先分析算法 首先构造优先关系矩阵，并保存文法的产生式，设置符号栈S: 首先构造优先关系矩阵，并保存文法的产生式，设置符号栈 I. 将输入符号串a 依次存入符号栈S中 直到遇到栈顶 将输入符号串 1···an#依次存入符号栈 中,直到遇到栈顶 依次存入符号栈 符号a 的优先性·>下个待输入符号 为止。 下个待输入符号a 符号 i的优先性 下个待输入符号 j为止。 II. 栈顶当前符号a 为句柄尾，由此向下找句柄的头符号a 栈顶当前符号 i为句柄尾，由此向下找句柄的头符号 k 使得a 使得 k-1 <·ak III. 由句柄 k···ai在文法的产生式中查找右部为 k···ai的产生 由句柄a 在文法的产生式中查找右部为a 若找到则用左部替换句柄，否则出错。 式，若找到则用左部替换句柄，否则出错。 IV. 重复以上步骤直到规约完输入符号串，栈中只剩下文法 重复以上步骤直到规约完输入符号串， 的开始符号为止。 的开始符号为止。
4. 算符优先分析算法： 算符优先分析算法： I. 算符优先分析句型的性质 任何一个句型应为如下形式： 句型应为如下形式 任何一个句型应为如下形式： ＃N1a1 N2a2···NnanNn+1 ＃ Ni为非终结符或空，ai为终结符 为非终结符或空， 若有N 若有 iai Ni+1ai+1···NjajNj+1为句柄 该句柄中终结符之间的关系为： 该句柄中终结符之间的关系为： ai-1 <· ai ai ·=·ai+1 ·=· ··· ·=· aj-1 ·=·aj aj ·> aj+1
E → E - E | E + E | E * E | E / E | E ^ E | - E | ( E ) | id 构造优先关系表
+ + * / ^ id ( ) $ ·> ·> ·> ·> ·> ·> <· ·> <·
·> ·> ·> ·> ·> ·> <· ·> <·
* <· <· ·> ·> ·> ·> <· ·> <·
• 作业 课本116页)： 作业(课本 课本 页： 1，2，3 ， ，
G[S]:
S → aABe A → Abc | b B→d
求出其简单优先关系矩阵
② I. II.
简单优先文法定义 在文法符号集V中 在文法符号集 中，任意两个符号之间最多只有一种 优先关系成立。 优先关系成立。 文法中任意两个产生式没有相同的右部。 为什么 为什么?) 文法中任意两个产生式没有相同的右部。(为什么
* ·> <· ·> <·
$ ·> ·> ·>
g_id
f_id
f_*
g_*
g_+
f_+
f g
+ 2 1
* id 4 4 3 5
$ 0 0
f_$
g_$
本章要点
优先分析思想 算符优先分析：如何构造优先关系矩阵、 算符优先分析：如何构造优先关系矩阵、如何分析以及使 用范围 简单优先分析与算符优先分析的区别
1、构造文法G的算符优先关系矩阵 构造文法G 2、利用矩阵分析符号串#cadbc# 利用矩阵分析符号串#cadbc#
G[S]:
S → f StS | i=E E → E+T | T T → P^T | P P → (E) | i
1、求该文法每个非终结符的FIRSTVT集和LASTVT集 求该文法每个非终结符的FIRSTVT集和LASTVT集 FIRSTVT集和LASTVT 2、构造文法G的算符优先关系矩阵 构造文法G
定义：设有一不含 产生式的算符文法 产生式的算符文法G， 定义：设有一不含ε产生式的算符文法 ，若对任意两个终 结符对a， 之间至多只有 之间至多只有<·， ·=· ， ·>三种关系的一 结符对 ，b之间至多只有 三种关系的一 种成立，则称G是一个算符优先文法 是一个算符优先文法（ 种成立，则称 是一个算符优先文法（OPG）。 ）。 E → E - E | E + E | E * E | E / E | E ^ E | - E | ( E ) | id 是否是算符优先文法
选取两个优先函数f和 选取两个优先函数 和g: – f(a) < g(b) 当 a <· b – f(a) = g(b) 当 a ·= b – f(a) > g(b) 当 a ·> b
+ f g 2 1
2 1
* 4 3
/ 4 3
↑
4 5
( 0 5
) 6 0
id 6 5
$ 0 0
id + * $
id + ·> <· ·> <· ·> <· <·
定义： 是一个不含ε产生式的算符文法 定义：设G是一个不含 产生式的算符文法，a和b是任意两 是一个不含 产生式的算符文法， 和 是任意两 个终结符， 、 、 是非终结符 是非终结符， 个终结符，A、B、C是非终结符，算符优先关系定义 如下： 如下： a. a ·=· b 当且仅当 中有形如 →···ab···或A →···aBb···的 当且仅当G中有形如 中有形如A 或 的 产生式 b. a <· b 当且仅当 中有形如 →···aB···的产生式，且 当且仅当G中有形如 中有形如A 的产生式， 的产生式 B⇒+b···或B⇒+Cb ··· ⇒ 或 ⇒ c. a ·> b 当且仅当 中有形如 →···Bb···的产生式，且 当且仅当G中有形如 中有形如A 的产生式， 的产生式 B⇒+ ··· a或B⇒+ ··· aC ⇒ 或 ⇒
/ <· <· ·> ·> ·> ·> <· ·> <·
↑
<· <· <· <· <· ·> <· ·> <·
id <· <· <· <· <· <· <·
( <· <· <· <· <· <· <·
) ·> ·> ·> ·> ·> ·> ·= ·>
$ ·> ·> ·> ·> ·> ·> ·>
算符优先文法定义： ② 算符优先文法定义： 算符文法：设有一文法G， 中没有形如A 算符文法：设有一文法 ，若G中没有形如 →···BC···的 中没有形如 的 产生式，B,C ∈VN ，则称G为算符文法（OG文法）。 产生式， 则称 为算符文法（ 文法）。 为算符文法 文法 重要性质1：在算符文法中任何句型都不包含两个相邻的 重要性质 ： 非终结符。（归纳法） 。（归纳法 非终结符。（归纳法） 重要性质2： 出现在算符文法的句型γ 重要性质 ：若Ab(bA)出现在算符文法的句型γ中，其中 出现在算符文法的句型 A ∈VN ,b ∈VT ，则γ中任何含b的短语必含有A。(反证法) 中任何含b的短语必含有A 反证法)
G[E]: ①E → E + E ②E → E * E ③E → ( E ) ④ E → id 输入： 输入： id1 + id2 * id3
3. 算符优先分析法
直观算符优先分析法： ① 直观算符优先分析法： 注意：有时需要人为定义运算的优先性和结合性。 注意：有时需要人为定义运算的优先性和结合性。
算符优先关系表的构造： ③ 算符优先关系表的构造： 首先定义两个集合： 首先定义两个集合： FIRSTVT(B)={ b | B⇒+b···或B⇒+Cb···} ⇒ b···或 ⇒ LASTVT(B)={ a | B⇒+···a或B⇒+···aC} ⇒ 或 ⇒
三种优先关系的计算为： 三种优先关系的计算为： I. ·=·关系 关系 可直接查看产生式右部， 可直接查看产生式右部，对形如产生式 A →···ab··· A →···aBb··· 则有a ·=· b成立 则有 成立 II. <·关系 关系 对形如产生式： 对形如产生式： A →···aB···对每一个 ∈ FIRSTVT(B) 对每一个b 对每一个 则有a 则有 <· b成立 成立 III. ·>关系 关系 对形如产生式： 对形如产生式： A →···Bb···对每一个 ∈ LASTVT(B) 对每一个a 对每一个 则有a 则有 ·> b成立 成立