编译原理递归下降分析器(C语言).pdf

《编译原理递归下降分析器(C语言).pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数学与软件科学学院实验报告学期：2015至2016第2学期2016年3月21日课程名称：编译原理专业：信息与计算科学2013级5班实验编号：2实验名称：递归下降分析器指导教师：王开端姓名：李丹学号：2013060510实验成绩：实验二递归下降分析器实验目的：通过设计、编制、调试递归下降语法分析程序，对输入的符号串进行分析匹配，观察输入符号串是否为给定文法的句子。实验内容：根据文法G[E]设计递归下降分析器并分析输入串i*(ii)是否为文法的句123子。G[E]：E→E+T

2、TT→T*F

3、FF→(E)

4、i实验步骤：在进行递归下降分析法

5、之前，必须对文法进行左递归和回溯的消除。1消除左递归直接消除见诸于产生式中的左递归比较容易，其方法是引入一个新的非终结符，把含有左递归的产生式改为右递归。文法G[E]经过消去直接左递归后得到文法G’[E]为：G’[E]：ETE'E'TE'

6、TFT'T'*FT'

7、F(E)

8、i2消除回溯回溯发生的原因在于候选式存在公共的左因子。一般情况下，设文法中关于A

9、

10、...

11、

12、

13、...

14、A的产生式为12ii1j，那么，可以把这些产生式改写为AA'

15、i1

16、...

17、jA'

18、...

19、1i经过反复提

20、取左因子，就能把每个非终结符（包括新引进者）的所有候选首字符集变为两两不相交（既不含有公共左因子）。3什么是递归下降分析法递归下降分析法是一种自顶向下的分析方法，文法的每个非终结符对应一个递归过程（函数）。分析过程就是从文法开始符出发执行一组递归过程（函数），这样向下推导直到推出句子；或者说从根节点出发，自顶向下为输入串寻找一个最左匹配序列，建立一棵语法树。在不含左递归和每个非终结符的所有候选终结首字符集都两两不相交条件下，我们就可能构造出一个不带回溯的自顶向下的分析程序，这个分析程序是由一组递归过程（或函数）组成的，每个过程（或函数

21、）对应文法的而一个非终结符。这样的一个分析程序称为递归下降分析器。4文法分析以G’[E]为例：G’[E]：ETE'E'TE'

22、TFT'T'*FT'

23、F(E)

24、i文法分析过程类似于一个个函数嵌套，我们可以假定函数E()、T()、E’()、F()、T’()，文法开始符E（看做函数E()）嵌套函数T()、E’()；而对于函数E’()，若有字符“+”匹配，则进行匹配，否则进入嵌套函数T()或E’()或为空；对于函数T()，执行其中的嵌套函数F()或T’()；对于函数F()，如果有字符“i”匹配，则进行匹配，否则若待分析串喊字符

25、“(”，进行匹配，并进入嵌套函数E()执行，再匹配“)”；对于函数T’()，若有字符“*”匹配，则进行匹配，否则进入嵌套函数F()或T’()或为空。5文法分析流程图函数间调用情况：图1递归下降分析法函数调用情况流程图（由于用一个流程图画出完整的文法分析过程完成的并不规范，故本实验将其分为4个流程图。）main()函数：图2递归下降分析法main()函数执行流程图E’()函数：图3递归下降分析法E’()函数执行流程图T’()函数：图4递归下降分析法T’()函数执行流程图F()函数：图5递归下降分析法F()函数执行流程图6输入串i*(i+

26、i)#语法分析表1输入串i*(i+i)语法分析表步骤符号栈待分析字符串采用产生式1#Ei*(i+i)#E→TE’2#E’Ti*(i+i)#T→FT’3#E’T’Fi*(i+i)#F→i4#E’T’*(i+i)#T’→*FT’5#E’T’F(i+i)#F→(E)6#E’T’Ei+i)#E→TE’7#E’T’E’Ti+i)#T→FT’8#E’T’E’T’Fi+i)#F→i9#E’T’E’T’+i)#T’→ε10#E’T’E’+i)#E’→+TE’11#E’T’E’Ti)#T→FT’12#E’T’E’T’Fi)#F→i13#E’T’E’T’

27、)#T’→ε14#E’T’E’)#E’→ε15#E’T’#T’→ε16#E’#E’→ε17##分析成功7程序设计本实验在程序设计方面做出了以下定义：一维字符数组a[]：用于存放分析字符串一维字符数组ch[]：用于存放符号栈内容lookahead：用于处理正在分析字符串的哪一个字符length：输入串的长度l：符号栈大小减1n：产生式右部长度（’也算作一个字符）#include#includechara[10];/*defineinputstring’stype&length*/charch[10]

28、={'#','E'};charcha;intlookahead=0;/*definearray’snumber*/intlength=0;intstep=1;intl=1;intn;intmain(void)/*main