编译原理 Part4语法分析.ppt

《编译原理 Part4语法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Part4语法分析授课：胡静语法分析器的作用以语法分析器为核心的编译器模型语法分析器词法分析器中间代码生成器语义分析器一部分中间代码输入字符串程序入口初始化工作语法分析器所处的位置语法分析的例子语法分析的类比针对自然语言的语法分析：识别一个句子是不是符合语法规范&识别每一个成分的功能。语法分析器的作用接收词法分析器提供的记号串检查记号串是否能由源程序语言的文法产生用易于理解的方式提示语法错误信息，并能从常见的错误中恢复过来语法分析器词法分析器符号表前端的其余部分源程序记号取下一个记号语法树中间表示语法分析器工作原理语言的结构是用上下文无关文法描述的，

2、因此，语法分析器的工作本质上就是按照文法的产生式，识别输入符号串是否为一个句子。语法分析器是从左向右的扫描输入字符串，每次读入一个符号，并判断，看是否能从文法的开始符号出发推导出这个输入串。或者，从概念上讲，就是要建立一棵与输入串匹配的语法分析树。语法分析器分类通用的语法分析方法，用来分析任何文法，生成编译器时效率太低编译器使用的语法分析方法—处理文法的一些子类自顶向下（建立分析树）—LL文法，其分析器常用手工实现自底向上（建立分析树）—LR文法，其分析器常利用自动生成工具构造自顶向下分析面临的困难自顶向下分析面临的困难自顶向下分析的主旨是，对任何输

3、入串，试图用一切可能的办法，从文法的开始符号（根结）出发，自顶向下的为输入串建立一棵语法树。这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。自顶向下分析的一般方法是带“回溯”的。自顶向下分析的简单例子假定文法G[S]，以及输入串x*y（记为α）。S→xAyA→**

4、*初始化：第一步扩展Sx*yIPSx*yIPyAx自顶向下分析的简单例子假定文法G[S]，以及输入串x*y（记为α）。S→xAyA→**

5、*第二步扩展：回溯x*yIPSx*yIPyAx**SyAx*自顶向下分析方法的特点困难我们希望通过读取下一个符号就确定要使用

6、哪一个产生式。S→E+S

7、EE→num

8、(S)这样做很难，这个文法不能够通过向前看一个符号的自顶向下分析方法来进行语法分析LL(1)分析法自顶向下分析存在的问题及解决方法左递归文法消除直接左递归消除直接左递归-提取左因子消除直接左递归——改写成右递归直接左递归的消除P→Pα

9、βP→βP’P’→αP’

10、εE→E+T

11、TT→T*F

12、FF→(E)

13、iE→TE’E’→+TE’

14、εT→FT’T’→*FT’

15、εF→(E)

16、i消除左递归的算法如果一个文法不含回路（形如P=>+P的推导），也不含以ε为右部的产生式，那么执行下述算法将保证消除左递归（但改写后的文法可能

17、含有ε为右部的产生式）。消除左递归的算法消除左递归的例子R→Sa

18、aQ→Rb

19、bS→Qc

20、cR→Sa

21、aQ→Sab

22、ab

23、bS→Sabc

24、abc

25、bc

26、cS→abcS’

27、bcS’

28、cS’S’→abcS’

29、εR→Sa

30、aQ→Sab

31、ab

32、bS→abcS’

33、bcS’

34、cS’S’→abcS’

35、εS→Qc

36、cQ→Rb

37、bR→bcaR’

38、caR’

39、aR’R’→bcaR’

40、ε回溯问题消除回溯的途径消除回溯、提取左因子令Ｇ是一个不含左递归的文法，对G的所有非终结符的每个候选α定义它的终结首符集FIRST(α)为：FIRST(α)={a

41、α=>*a…,a∈VT}若α

42、=>*ε，则规定ε∈FIRST(α)FIRST(α)是α的所有可能推导的开头终结符或可能的ε如果非终结符Ａ的所有候选首符集两两不相交，即Ａ的任何两个不同候选αi和αｊFIRST(αi)∩FIRST(αj)=Φ那么当要求Ａ匹配输入串时，Ａ就能根据它所面临的第一个输入符号ａ，准确的指派某一个候选前去执行任务。这个候选就是那个终结首符集含ａ的α。消除回溯、提取左因子提取左因子的方法假定Ａ的规则是：Ａ→δβ1

43、δβ2

44、…

45、δβn

46、γ1

47、γ2

48、…

49、γm（其中，每个γ不以δ开头）那么这些规则可以改写为：A→δA’

50、γ1

51、γ2

52、…

53、γmA’→β1

54、β2

55、…

56、βn经

57、过反复提取左因子，就能够把每个非终结符（包括新引进者）的所有候选首符集便成为两两不相交。我们为此要付出的代价是大量引进新的非终结符和ε产生式。消除回溯的方法二文法的两个条件扩充的巴科斯范式前面的巴科斯范式只用到了两个元符号“→”和“

58、”扩充几个元语言符号：用花括号{α}表示闭包运算α*。用{α}n0表示α可任意重复0次至n次。{α}00={α}0=ε.用方括号[α]表示{α}10，即表示α的出现可有可无（等价于α

59、ε）。例如，通常的“实数”可定义为：decimal→[sign]integer.{digit}[exponent]exponent→E[s

60、ign]integerinteger→digit[digit]sign→+

61、-递归下降分析程序的构造当文法满