2013-05-06 18:36:51| 分类： 编译器 | 标签：编译器 算符优先分析法 |字号 订阅
自下而上的语法分析：（规约）
由叶节点到根节点，构造树
规范规约：最左规约（对应于最右推导）
例：
对于文法：
S→aABe
A→Ab|b
B→d
串abbde的规约过程：
对应的最右推导:
S→aABe→aAde→aAbde→abbde
存在的问题：遇到Ab的时候，有两种可能A→Ab和A→b
解决：
短语的概念：
如果S=> αAw=>αβw，则称β为相对于A的、句型αβw 的短语
直接短语
若A→ β为一产生式，则称β为相对于A的、句型αβw 的直接短语
例：
句型aAbde所包含的直接短语：
Ab、d、
句柄：
最左直接短语是句柄
例：句型aAbde所包含的句柄:Ab
素短语
①它首先是一个短语②至少含有一个终结符③除自身外，不再含有其它的素短语
最左素短语LPP ( leftmost Prime Phrase)
算符优先分析过程中归约的是最左素短语
例：关于文法E→E+T|T
T→T*F|F
F→(E)|id
对于句型F+F*id3
语法树是：
短语：F1, F2, id3, F2*id3,
F1+F2*id3
直接短语： F1, F2, id3
句柄： F1
最左素短语： id3
用栈实现移进归约分析
例
关于文法：
E→E+T|T
T→T*F|F
F→(E)|id
对于串 id1*id2+id3 的分析
方法：对于符号栈中的非终结符，能规约就规约，不能规约就从输入串中移入符号
算符优先分析法：
表示a和b的优先级相等
表示a的优先级不如b
表示a的优先级比b高
注：
算术关系“”与优先关系具有十分不同的性质。例如，a＜·b并不一定意味着b·>a
例如：+ +不一定存在。 具体如：2+(3+5)
算符优先关系矩阵：
关于文法
的优先关系矩阵：
FIRSTVT和LASTVT集：
FIRSTVT(P)={a|P=>a…或P=>Qa…,
LASTVT(P)={a|P=> … a或P=>…aQ
上面文法的FIRSTVT和LASTVT集：
关于上面文法对于串id+id*id$的分析：
方法：如果 或者=就规约
2013-05-06 18:36:51| 分类： 编译器 | 标签：编译器 算符优先分析法 |字号 订阅
自下而上的语法分析：（规约）
由叶节点到根节点，构造树
规范规约：最左规约（对应于最右推导）
例：
对于文法：
S→aABe
A→Ab|b
B→d
串abbde的规约过程：
对应的最右推导:
S→aABe→aAde→aAbde→abbde
存在的问题：遇到Ab的时候，有两种可能A→Ab和A→b
解决：
短语的概念：
如果S=> αAw=>αβw，则称β为相对于A的、句型αβw 的短语
直接短语
若A→ β为一产生式，则称β为相对于A的、句型αβw 的直接短语
例：
句型aAbde所包含的直接短语：
Ab、d、
句柄：
最左直接短语是句柄
例：句型aAbde所包含的句柄:Ab
素短语
①它首先是一个短语②至少含有一个终结符③除自身外，不再含有其它的素短语
最左素短语LPP ( leftmost Prime Phrase)
算符优先分析过程中归约的是最左素短语
例：关于文法E→E+T|T
T→T*F|F
F→(E)|id
对于句型F+F*id3
语法树是：
短语：F1, F2, id3, F2*id3,
F1+F2*id3
直接短语： F1, F2, id3
句柄： F1
最左素短语： id3
用栈实现移进归约分析
例
关于文法：
E→E+T|T
T→T*F|F
F→(E)|id
对于串 id1*id2+id3 的分析
方法：对于符号栈中的非终结符，能规约就规约，不能规约就从输入串中移入符号
算符优先分析法：
表示a和b的优先级相等
表示a的优先级不如b
表示a的优先级比b高
注：
算术关系“”与优先关系具有十分不同的性质。例如，a＜·b并不一定意味着b·>a
例如：+ +不一定存在。 具体如：2+(3+5)
算符优先关系矩阵：
关于文法
的优先关系矩阵：
FIRSTVT和LASTVT集：
FIRSTVT(P)={a|P=>a…或P=>Qa…,
LASTVT(P)={a|P=> … a或P=>…aQ
上面文法的FIRSTVT和LASTVT集：
关于上面文法对于串id+id*id$的分析：
方法：如果 或者=就规约