语法分析自底向上分析技术ppt课件.ppt

《语法分析自底向上分析技术ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5.1引言5.2算符优先分析技术5.3LR(k)分析技术本章小结第五章语法分析----自底向上分析技术5.1引言5.1.1自底向上分析技术及识别算法5.1.2讨论的前提5.1.3基本实现方法第五章语法分析----自底向上分析技术5.1引言5.1.1自底向上分析技术及识别算法基本思想是:从输入符号串出发，在每一分析步对相应句型中的某个简单短语进行归约。如果最终能归约到识别符号，则该输入符号串是相应文法的句子，否则就不是。当句型分析过程中每个分析步都对最左的简单短语进行直接归约时，自底向上分析技术的两个基本问题可以更确切地叙述为：如何找出句柄及把此句柄直接归约为哪个非终结符号。第五章语法分析

2、----自底向上分析技术5.1引言5.1.1自底向上分析技术及识别算法5.1.2讨论的前提识别过程是从左到右、自底向上地进行的，一般都将采用规范归约；除了特别指明的以外，每一步总是对句柄——最左的简单短语进行直接归约。第五章语法分析----自底向上分析技术5.1.3基本实现方法采用自底向上分析技术时，通常以移入-归约法为基础。一般地，动作共有4类，即移入、归约、接受与报错。移入：读入下一个输入符号并把它下推进栈；归约：当栈顶的(部分)符号串形成一个句柄时，对此句柄进行直接归约；接受：当识别程序发现栈中除了栈底标志符号#外仅有识别符号，而输入也已到达右端#，则接受；报错：当识别程序察觉一个

3、错误，因此输入符号串不是句子而无法继续识别工作时，调用一个出错处理子程序进行处理或停止。第五章语法分析----自底向上分析技术例5.1设有文法G[E]：E∷=E+E

4、E*E

5、(E)

6、i自底向上分析技术的步骤:1)找出句柄u;2)找出规则U∷=u；3)把u直接归约成U。分析技术不同,寻找句柄的方法也不同。第五章语法分析----自底向上分析技术5.2算符优先分析技术一、算符优先分析技术的引进二、算符文法三、算符优先关系与算符优先文法四、算符优先文法句型的识别五、实际应用中的算符优先分析技术第五章语法分析----自底向上分析技术一、算符优先分析技术的引进对算术表达式，运算符完全决定了运算次序，

7、运算对象完全不起作用。因此，将文法中的终结符号看作运算符；非终结符号看作运算对象。算符优先分析技术：只在终结符号之间引进优先关系，并利用优先关系找出句柄（最左质短语）。第五章语法分析----自底向上分析技术5.2算符优先分析技术一、算符优先分析技术的引进二、算符文法定义5.1如果文法G中没有形如U∷=…VW…的规则，其中U、V、W∈VN，则该文法G称为算符文法，缩写为OG。第五章语法分析----自底向上分析技术5.2算符优先分析技术一、算符优先分析技术的引进二、算符文法三、算符优先关系与算符优先文法算符优先关系算符优先文法第五章语法分析----自底向上分析技术5.2简单优先分析技术5.2

8、.1算符优先分析技术的引进5.2.2算符文法算符优先关系算符优先文法第五章语法分析----自底向上分析技术定义5.2设文法G是一个算符文法，Tj与Ti是两个任意的终结符号，而U,V,W∈VN，定义算符优先关系如下：Tj=Ti当且仅当文法G中存在形如U∷=…TjTi…或U∷=…TjVTi…的规则；Tj＜Ti当且仅当文法G中存在形如U∷=…TjV…的规则，其中V=>Ti…或V=>WTi…；Tj＞Ti当且仅当文法G中存在形如U∷=…VTi…的规则，其中V=>…Tj或V=>…TjW。例设有文法G[Z]:Z∷=EE∷=T

9、E+TT∷=F

10、T*FF∷=(E)

11、i++++i+*()i>>>+<><<>

12、*<>><>(<<<<=)>>>5.2算符优先分析技术一、算符优先分析技术的引进二、算符文法三、算符优先关系与算符优先文法算符优先关系算符优先文法第五章语法分析----自底向上分析技术定义5.5设有算符文法G，如果在它的任意两个终结符号之间，算符优先关系=、＜与＞至多只有一种关系成立，则称该文法G为算符优先文法，缩写为OPG。例1文法G[Z]:Z∷=EE∷=T

13、E+TT∷=F

14、T*FF∷=(E)

15、i例2文法G[E]：E∷=E+E

16、E*E

17、(E)

18、i5.2简单优先分析技术5.2.1算符优先分析技术的引进5.2.2算符文法四、算符优先文法句型的识别质短语算符优先识别算法第五章语法分析----

19、自底向上分析技术定义5.6设有算符文法G[Z]，(句型的)质短语定义为这样一个短语：它至少包含一个终结符号，且除它自身外不再包含其他质短语。例1文法G[Z]:Z∷=EE∷=T

20、E+TT∷=F

21、T*FF∷=(E)

22、i（考虑句型T+T*F+i)定理5.3一个算符优先文法句型[N1]T1[N2]…[Nn]Tn[Nn+1]的最左质短语是满足条件：Tj－1Ti+1的最左子符号串[Ｎj]Tj[Nj+1]…[