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

数学与软件科学学院 实验报告 学 期： 2015 至 2016 第 2 学期 2016 年 3 月 21 日 课程名称： 编译原理 专 业： 信息与计算科学 2013 级 5 班 实验编号： 2 实验名称： 递归下降分析器 指导教师： 王开端 姓 名： 李丹 学 号： 2013060510 实验成绩： 实验二 递归下降分析器 实验目的： 通过设计、编制、调试递归下降语法分析程序，对输入的符号串进行分析匹 配，观察输入符号串是否为给定文法的句子。 实验内容： 根据文法 G[E]设计递归下降分析器并分析输入串 1 *(i i ) i ? 是否为文法的句 2 3 子。 G[E]：E→E+T|T T→T*F|F F→(E)|i 实验步骤： 在进行递归下降分析法之前，必须对文法进行左递归和回溯的消除。 1 消除左递归 直接消除见诸于产生式中的左递归比较容易，其方法是引入一个新的非终结 符，把含有左递归的产生式改为右递归。 文法 G[E]经过消去直接左递归后得到文法 G’[E]为： G’[E]： E ? TE E? ?TE|? T ? FT T? *FT|? F ? (E) | i 2 消除回溯 回溯发生的原因在于候选式存在公共的左因子。一般情况下，设文法中关于 A ? ?? |?? |...|?? | ? | ...| ? A 的产生式为 i i j 1 2 ?1 ，那么，可以把这些产生式改写为 ? ? ? ? A A| | ...| i?1 ? ? A? ? | ...| ? 1 i ? j 经过反复提取左因子，就能把每个非终结符（包括新引进者）的所有候选首字符 集变为两两不相交（既不含有公共左因子）。 3 什么是递归下降分析法 递归下降分析法是一种自顶向下的分析方法，文法的每个非终结符对应一个 递归过程（函数）。分析过程就是从文法开始符出发执行一组递归过程（函数）， 这样向下推导直到推出句子；或者说从根节点出发，自顶向下为输入串寻找一个 最左匹配序列，建立一棵语法树。 在不含左递归和每个非终结符的所有候选终结首字符集都两两不相交条件 下，我们就可能构造出一个不带回溯的自顶向下的分析程序，这个分析程序是由 一组递归过程（或函数）组成的，每个过程（或函数）对应文法的而一个非终结 符。这样的一个分析程序称为递归下降分析器。 4 文法分析 以 G’[E]为例：G’[E]： E ? TE E? ?TE|? T ? FT T? *FT|? F ? (E) | i 文法分析过程类似于一个个函数嵌套，我们可以假定函数 E()、T()、E’()、 F()、T’()，文法开始符 E（看做函数 E()）嵌套函数 T()、E’()；而对于函数 E’()， 若有字符“+”匹配，则进行匹配，否则进入嵌套函数 T()或 E’()或为空；对于函数 T()，执行其中的嵌套函数 F()或 T’()；对于函数 F()，如果有字符“i”匹配，则进 行匹配，否则若待分析串喊字符“(”，进行匹配，并进入嵌套函数 E()执行，再匹 配“)”；对于函数 T’()，若有字符“*”匹配，则进行匹配，否则进入嵌套函数 F() 或 T’()或为空。 5 文法分析流程图 函数间调用情况： 图 1 递归下降分析法函数调用情况流程图 （由于用一个流程图画出完整的文法分析过程完成的并不规范，故本实验将 其分为 4 个流程图。） main()函数： 图 2 递归下降分析法 main()函数执行流程图 E’()函数： 图 3 递归下降分析法 E’()函数执行流程图 T’()函数： 图 4 递归下降分析法 T’()函数执行流程图 F()函数： 图 5 递归下降分析法 F()函数执行流程图 6 输入串 i*(i+i)#语法分析 表 1 输入串 i*(i+i)语法分析表 步骤 符号栈 待分析字符串 采用产生式 1 #E i*(i+i)# E→TE’ 2 #E’T i*(i+i)# T→FT’ 3 #E’T’F i*(i+i)# F→i 4 #E’T’ *(i+i)# T’→*FT’ 5 #E’T’F (i+i)# F→(E) 6 #E’T’E i+i)# E→TE’ 7 #E’T’E’T i+i)# T→FT’ 8 #E’T’E’T’F i+i)# F→i 9 #E’T’E’T’ +i)# T’→ε 10 #E’T’E’ +i)# E’→+TE’ 11 #E’T’E’T i)# T→FT’ 12 #E’T’E’T’F i)# F→i 13 #E’T’E’T’ )# T’→ε 14 #E’T’E’ )# E’→ε 15 #E’T’ # T’→ε 16 #E’ # E’→ε 17 # # 分析成功 7 程序设计 本实验在程序设计方面做出了以下定义： 一维字符数组 a[]：用于存放分析字符串 一维字符数组 ch