自动机、正则文法、正则表达式的相互转化.ppt

《自动机、正则文法、正则表达式的相互转化.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、自动机、正则文法、正则表达式的相互转化正则文法NFA正则表达式123456DFA最小化复习第四章语法分析4.1自顶向下分析法4.1.1自顶向下分析的思想4.1.2左递归和回溯性质4.1.3递归子程序法（递归下降分析法）4.1.4LL(1)分析法4.2自底向上分析法4.2.1自底向上分析法概述4.2.2LR分析法的概念4.2.3LR(0)项目族的构造4.2.4SLR分析法4.2.5LALR分析法4.2.6二义性文法的应用编译程序的功能和组织结构表处理词法分析源程序目标程序错误处理语法分析语义分析目标代码生成前端后端中间代码优化中间代码生成44功能

2、：根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查。基本任务：识别符号串S是否为某语法成分两大类分析方法：自顶向下分析自底向上分析语法分析概述5若ZS则SL(G[Z])否则SL(G[Z])+G[Z]存在主要问题:左递归问题回溯问题主要方法:递归子程序法LL分析法自顶向下分析算法的基本思想为：若ZS则SL(G[Z])否则SL(G[Z])+G[Z]自底向上分析算法的基本思想为：存在主要问题:句柄的识别问题主要方法:算法优先分析法LR分析法自顶向下分析664.1.1自顶向下分析的思想4.1.2自顶向下分析存在的问题及解决方法

3、4.1.3递归子程序法（递归下降分析法）4.1.4LL(1)分析法4.1.1自顶向下分析的思想77我们可以通过一例子来说明语法分析过程给定符号串S，若预测是某一语法成分，那么可根据该语法成分的文法,设法为S构造一棵语法树.若成功,则S最终被识别为某一语法成分,即SL(G[Z])其中G[Z]为某语言成分的文法.若不成功,则SL(G[Z])88例：已知符号串S=cad文法G[Z]:Z→cAdA→ab

4、a求解SL(G[Z])分析过程是设法建立一棵语法树,使语法树的末端结点与给定符号串相匹配.1.开始:令Z为根结点Z2.用Z的右部,符号串去匹配输入

5、串·ZcAd完成一步推导ZcAd检查c-c匹配A是非终结符,将匹配任务交给A993.选用A的右部符号串匹配输入串A有两个右部,选第一个·cAdabZ完成进一步推导Aab检查,a-a匹配,b-d不匹配(失败)但是还不能冒然宣布SL(G[Z])4.回溯即砍掉A的子树改选A的第二右部·ZcAdaAa检查a-a匹配d-d匹配建立语法树,末端结点为cad与输入cad相匹配,建立了推导序列ZcAdcad∴cadL(G(Z))S=cadG[Z]:Z→cAdA→ab

6、a分析工作要部分地或全部地退回去重做叫回溯自顶向下分析方法特点1.分析过程是带有预

7、测的，对输入符号串要预测属于什么语法成分，然后根据该语法成分的文法建立语法树。2.分析过程是一种试探过程，是尽一切办法(选用不同规则)设法建立语法树的过程，由于是试探过程，故难免有失败，所以分析过程需进行回溯，因此我们也称这种方法是带回溯的自顶向下分析方法。4.1.2自顶向下分析存在的问题及解决方法自顶向下分析方法的基本缺点：不能处理具有左递归性的文法自顶向下分析为什么不能处理左递归文法？文法G，存在U∈Vn，ifU==>U…,则G为左递归文法+1．左递归文法：左递归文法回溯问题1212在采用最左推导的自顶向下分析中，左递归的存在是十分有害的，例

8、如，考虑文法G[S]：SSa

9、b，分析输入串baaa是否为文法的合法句子。按照自顶向下分析法，对输入串baaa的当前输入符b从开始符号S开始进行最左推导，若首次使用SSa则可能得到：SSaSaaSaaaSaaaa如果文法具有间接左递归，则也将发生上述问题，只不过环的圈子兜的更大。要实行自顶向下分析，必须要消除文法的左递归，下面我们将介绍直接左递归的消除方法，在此基础上再介绍一般左递归的消除方法。自顶向下分析为什么不能处理左递归文法？1313将左递归规则改为右递归规则若：P→P

10、则可改写为：P→P’P’→P’

11、ε证明的关键步

12、骤：P->Pα

13、βP->β

14、βα

15、βαα

16、βααα

17、……P->β(ε

18、α

19、αα

20、ααα

21、……)P->βP’,P’->ε

22、α

23、αα

24、ααα

25、……P->βP’,P’->ε

26、αP’①消除直接左递归:1414文法E->E+T

27、TT->T*F

28、FF->(E)

29、i例2已知G[E]：E->T*F

30、T/F

31、FT->F

32、T*F

33、T/F解：左递归改为右递归得：E->T*F

34、T/F

35、FT->FT’T’->*FT’

36、/FT’

37、ε消除左递归后：E->TE’,E’->+TE’

38、εT->FT’,T’->*FT’

39、εF->(E)

40、i1515②消除一般左递归基本思想先用代入法把间

41、接左递归变成直接左递归，再消除直接左递归，最后去掉多余规则以化简文法。算法说明要求文法不能含有回路(即形如P+P的推导)，并且不含作