编译原理语法3(自顶向下语法分析：递归下降)

《编译原理语法3(自顶向下语法分析：递归下降)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6讲编译原理西北农林科技大学本科教程主讲教师：赵建邦第三章语法分析3.1文法和语言3.2推导与语法树3.3自顶向下的语法分析3.4自底向上的语法分析3.5规范规约的自底向上语法分析方法第三章《语法分析》3.3自顶向下的语法分析递归下降分析法LL(1)分析法（下一讲内容）重点掌握消除左递归消除回溯构建递归下降子程序本讲目标3.3自顶向下的语法分析算法思想：从文法的开始符号出发，向下推导，如果推导出的句子恰好为输入符号串，则输入符号串为符合该文法的句子；或者：开始符号作为根节点，向下生长出一棵语法树，其叶子节点组成的句子恰好为输入符号串。这里的每一步“生长”对应一次直接推导。自顶向下分析方

2、法:1、不确定的自顶向下分析2、确定的自顶向下分析递归下降分析法LL(1)分析法1、不确定的自顶向下分析方法假定文法G[S]为S→xAyA→ab

3、a若输入串为xay，则其分析过程如下：(1)建立根节点S；(2)关于S的产生式只有一个，则生长语法树,匹配语法树的第一个终结符x；(3)A → ab

4、a有两个候选式，选择第一个,并且匹配语法树的第二个叶子节点a；(4)输入串xay期待匹配y,而语法树中的b与之匹配失败；SAyabx3.3自顶向下的语法分析1、不确定的自顶向下分析方法假定文法G[S]为S → xAyA → ab

5、a若输入串为xay，则其分析过程如下：(5)撤销匹配a，注销A所生成

6、的子树，回溯；(6)选择产生式A→a，重新匹配a；(7)匹配输入串的字符y；而语法树的最后一个叶子节点也是y,因此语法树和输入串xay匹配成功。SAyabxa3.3自顶向下的语法分析小结：关于不确定的自顶向下分析方法这种自顶向下的分析是一个不断试探的过程；即，在分析过程中，如果出现多个产生式(即候选式)可供选择，则逐一试探每一候选式进行匹配，每当一次试探失败，就选取下一候选式再进行试探；此时，必须回溯到这一次试探的初始现场，包括注销已生长的子树及将匹配指针调回到失败前的状态。这种带回溯的自顶向下分析方法实际上是一种穷举的试探方法，其分析效率极低，在实用的编译程序中很少使用。3.3自顶向下

7、的语法分析2、确定的自顶向下分析方法确定的自顶向下分析要求文法满足两个条件：(1)文法不含左递归：即不存在这样的非终结符号A：有A→A…存在或者有；原因：左递归的文法使自顶向下分析工作陷入无限循环E→E+T3.3自顶向下的语法分析(2)无回溯，对文法的任一非终结符号，当其产生式右部有多个候选式可供选择时，各候选式所推出的终结符号串的首字符集合要两两不相交原因：会导致先前做的一大堆语法工作和语义工作(指中间代码产生工作和各种表格的簿记工作)推倒重来3、消除左递归方法：引入一个新的非终结符，把含有左递归的产生式改写为右递归。设关于非终结符A的直接左递归的产生式形如A → Aα

8、β其中，α、β

9、是任意的符号串且β不以A开头。该产生式所能推导的句子如下：…3.3自顶向下的语法分析再看下面不含A的直接左递归的产生式：A → βA'A'→ αA'

10、ε这两个产生式所能推导的句子如下：可见，两种产生式所推导的结果相同：都能描述正规表达式βα*3.3自顶向下的语法分析3、消除左递归规则：将产生式A → Aα

11、β改写为：A → βA‘A’→ αA‘

12、ε其中，A’是新引入的非终结符。ε不可缺少，否则推导过程无法结束。3.3自顶向下的语法分析例如，含有直接左递归的表达式文法G[E]为G[E]:E → E+T

13、TT → T*F

14、FF → (E)

15、iE → TE'E' → +TE'

16、ε(3.2)

17、经过消去直接左递归后得到文法G'[E]为T → FT'T' → *FT'

18、εG'[E]:F → (E)

19、i3.3自顶向下的语法分析3、消除左递归一般情况下，设文法中关于A的产生式为A → Aα1

20、Aα2

21、…

22、Aαm

23、β1

24、β2

25、…

26、βn其中，每个α都不等于ε且每个β都不以A开头，则消除A的直接左递归性就是将其改为：例如，对产生式E→E+T

27、E-T

28、T，消除直接左递归后为3.3自顶向下的语法分析R=(β1

29、β2

30、…

31、βn)(α1

32、α2

33、…

34、αm)*E→TE'E'→+TE'

35、-TE'

36、ε3、消除间接左递归注意：也有些文法是含有间接左递归的，如下述文法G[S]:G[S]:S → Qc

37、cQ→ 

38、Rb

39、bR→ Sa

40、a(3.3)中的S、Q、R都具有间接左递归3.3自顶向下的语法分析3、消除间接左递归如何消除一个文法的一切左递归呢？如果一个文法不含回路(形如A=>A的推导)，且产生式的右部也不含ε的候选式，那么，下述算法将消除文法的左递归：(1)将文法G[S]的所有非终结符按一给定的顺序排列：A1、A2、…、An；+3.3自顶向下的语法分析(2)执行下述循环语句将消除所有左递归for(i=1;i<=n;i++){for(j=