数学与软件科学院实验报告
学期： 2015年至2016年第二学期2016年3月21日
课程名称：编译原理专业：信息与计算科学2013班5
实验编号： 2实验名称：递归下降分析器指导教师： ttdsy
名字：帅小白菜学号： 2013060510实验成绩：
实验2递归下降分析器
实验目的：
通过设计、创建和调试递归下降语法分析程序来分析输入的符号串
是的，观察输入符号串是否是给定语法的句子。
实验内容：
基于语法G[E]设计递归下降分析器，分析输入串I*[II]123是否为语法句子
孩子。
G[E]:EE T|T
TT*F|F
f(e )|i
实验步骤：
在进行递归下降分析法之前，必须对语法进行左递归和回溯消除。
1消除左递归
直接排除生成式中出现的左递归相对容易，其方法是引入新的非终结
将包含左递归的生成表达式更改为右递归。
删除语法G[E]直接左递归后得到的语法g’[ e ]如下。
g’[ e ] :
ete '
e'te'|
tft '
T'*FT'|
f(e )|i
2消除回溯
发生回溯的原因是候选公式中存在共同的左因子。 一般来说，在语法上
A|.||||.||
的生成式为1 2 i i1 j，可以将这些生成式改写为
a'||.|
I1j
a'|.|1I
通过反复提取左因子，将各非终端符号(包括新导入者)的所有候选开头字符
集将不会交叉成两个。 不包含共同的左因子。
3什么是递归下降分析法
递归下降分析法是自上而下的分析法，每个语法非终结符号对应一个
递归过程。 分析过程是指从语法的起始符开始执行一系列递归过程(函数)，
这样往下引直到把句子挤出来； 或者从根节点，自上而下地查找输入列之一
将序列匹配到最左侧，并创建语法树。
所有不包含左递归和每个非终结符的候选终结符字符集都有两个非交叉条件
中，可以构建无回溯的自上而下分析程序。 这个分析程序
由一组递归过程(或函数)组成，每个过程(或函数)对应于结尾而不是语法结尾
票。 这种分析程序称为递归下降分析器。
4语法分析
以g’[ e ]为例，g’[ e ] :
ete '
e'te'|
tft '
T'*FT'|
f(e )|i
语法分析过程就像一个个函数嵌套在一起，函数e ()、t ()、e () )、
f ()、t () )、语法起始符e ) )函数e )、e ) )； 对于函数e’() )，
如果字符“”匹配，则匹配。 如果不匹配，则进入嵌套函数t ()或e () )或为空。 对于函数
t ) )，其中的嵌套函数f ()或t ) )； 对于函数f ()，在字符" I "一致情况下
行匹配，否则，解析字符串并喊「()”后进行匹配，进入嵌套函数e ) )执行，重新匹配
加上「()”； 函数t’) )，则进入字符“*”匹配时匹配，不匹配时嵌套函数f ) )
或t’()或空。
5语法分析流程图
对于函数间调用：
图1是递归下降分析法函数调用时的流程图
(因为在一个流程中描绘完整的语法分析过程是不规范的，所以在本实验中
这分为四个流程图。 ）
main ) )函数：
图2递归下降量