sun编译原理第4章语法分析(第8-18讲) (2).ppt

《sun编译原理第4章语法分析(第8-18讲) (2).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、语法分析程序的功能是以词法分析器生成的单词符号序列作为输入，根据语言的语法规则（文法），识别出各种语法成分，并在分析过程中进行语法检查，检查所给单词符号序列是否是该语言的文法的一个句子。若是，则以该句子的某种形式的语法树作为输出；若不是，则表明有错误，并指出错误的性质和位置。4.1语法分析程序的功能语法分析程序的输入是单词符号序列；输出是语法树。8/14/20211信息学院孙丽云递归下降法LL(1)分析法回溯分析方法（不确定的分析法）预测分析方法(确定的分析法)LR(0)parsingSLR(1)parsingL

2、R(1)parsingLALR(1)parsing自顶向下分析方法从根结点出发构造语法树自底向上分析方法从叶结点出发构造语法树语法分析方法L:由左向右的处理输入L:为输入串构造最左推导L:由左向右的处理输入R:为输入串构造最右推导8/14/20212信息学院孙丽云■自顶向下的分析例：设有文法G：S→cAd;A→ab;A→a;识别串w=cabd是否是该文法的句子。ScAd■自底向上的分析ScAdabcdabcdabAcdabAS8/14/20213信息学院孙丽云例：已知符号串S=cad文法G[Z]:Z→cAdA→a

3、b

4、a求解SL(G[Z])分析过程是设法建立一棵语法树,使语法树的末端结点与给定符号串相匹配.1.开始:令Z为根结点Z2.用Z的右部,符号串去匹配输入串·ZcAd完成一步推导ZcAd检查c-c匹配A是非终结符,将匹配任务交给A回溯分析法4.2自上而下分析法8/14/20214信息学院孙丽云3.选用A的右部符号串匹配输入串A有两个右部,选第一个·cAdabZ完成进一步推导Aab检查,a-a匹配,b-d不匹配(失败)但是还不能冒然宣布SL(G[Z])4.回溯即砍掉A的子树改选A的第二右部·ZcAdaAa检查

5、a-a匹配d-d匹配建立语法树,末端结点为cad与输入cad相匹配,建立了推导序列EcAdcad∴cadL(G(E))S=cadG[Z]:Z→cAdA→ab

6、a分析工作要部分地或全部地退回去重做叫回溯回溯分析法分析效率低，代价高，实际不常用。8/14/20215信息学院孙丽云■文法左递归的消除4.2自上而下分析法左递归导致无限递归循环；解决无限递归循环的方法：消除左递归。（1）左递归改成右递归——简单直接左递归的消除A→Aα

7、βA→βA’A’→αA’

8、ε解：exp→termexp’exp’→addopter

9、mexp’

10、ε例：将文法G：exp→expaddopterm

11、term消除左递归。左递归的消除不改变语言，但是改变了文法和分析树。确定的自上而下分析法对文法要求：(1)无左递归；(2)无回溯8/14/20216信息学院孙丽云A→Aα1

12、Aα2

13、…

14、Aαn

15、β1

16、β2

17、…

18、βmA→β1A’

19、β2A’

20、…

21、βmA’A’→α1A’

22、α2A’

23、…

24、αnA’

25、ε●Example将文法G：exp→exp+term

26、exp-term

27、term消除左递归。解：exp→termexp’exp’→+termexp’

28、-termexp

29、’

30、ε(1)左递归改成右递归——普通的直接左递归的消除练习：对文法G:E→T*F

31、T/F

32、FT→F

33、T*F

34、T/F消除左递归8/14/20217信息学院孙丽云（2）采用扩充BNF表示法改写含直接左递归的规则使用花括号{a}表示符号串a的出现可0次或多次，即表示a*。例：if-stmtif(exp)statement

35、if(exp)statementelsestatementif-stmtif(exp)statement[elsestatement]expexpaddopterm

36、termexpterm{a

37、ddopterm}使用方括号[a]表示a的出现可有可无，它用来表示可供选择的符号串。使用圆括号可在规则中提取因子。例：Axa1

38、xa2

39、…

40、xanAx(a1

41、a2

42、…

43、an)8/14/20218信息学院孙丽云■回溯的消除引起回溯的情况：（1）相同左部的规则，其右部左端第一个符号相同而引起回溯。例：Z→cAdA→ab

44、a（2）相同左部的规则，其中某一右部能推出ε串。例：ABxBx

45、ε■LL(1)文法LL(1)中的第一个L表示从左到右扫描输入串，第二个L表明分析过程中使用最左推导，1表示分析时每一步只需向前看

46、一个符号即可决定所选用的规则，而且这种选择是准确无误的。P618/14/20219信息学院孙丽云First集合和Follow集合■First集合定义：FIRST(α)={a

47、α=>*aβ，aT,α,β(TN)*}若α=>*ε，则规定εFIRST(α)该集合称为α的头符号集合8/14/202110信息学院孙丽云1.若X,则FIRST(X)={X}2.若XN,且