编译原理实验：递归下降语法分析实验报告

编译原理实验：递归下降语法分析实验报告

一. 实验目的

通过本次实验，了解递归下降语法分析的原理和实现方法，掌握递归下降语法分析程序的编写方法，加深对编译原理的理解。

二. 实验原理

1. 递归下降语法分析

递归下降语法分析是一种自顶向下的语法分析方法，它的基本思想是从语法的顶层开始，递归地分析语法规则，直到叶子节点为止，从而构建语法树。

递归下降语法分析程序一般由一个主函数和若干个子函数组成，每个子函数对应一条语法规则，主函数调用这些子函数递归地分析语法规则。

2. LL(1)文法

LL(1)文法是一种重要的上下文无关文法，它具有以下特点：

• 左公因子消除：对于任意两个产生式A->α1|α2，如果α1和α2有一个公共前缀β，就可以将其拆分为A->βA’，A’->α1’|α2’，其中α1’和α2’不以β开头。
• 左递归消除：对于任意非终结符A，如果存在产生式A->Aα1|Aα2|...|Aαn|β1|β2|...|βm，其中βi不能推出以A开头的符号串，就可以将其拆分为A->β1A’|β2A’|...|βmA’，A’->α1|α2|...|αnA’。
• First集和Follow集的计算：对于每个非终结符A，计算其First集和Follow集。
• LL(1)分析表的构造：对于每个非终结符A和终结符a，计算分析动作M[A,a]。

三. 实验内容

本次实验要求编写一个递归下降语法分析程序，对以下文法进行分析：

S->iEtS|a
E->b

其中，S表示语句，E表示表达式，i表示'if'语句，t表示表达式，a表示'assign'语句，b表示布尔表达式。

具体而言，要求实现以下功能：

1. 从文件中读入待分析的源程序，存储为一个字符串。
2. 对源程序进行词法分析，生成一个词法单元序列。
3. 对词法单元序列进行递归下降语法分析，生成语法树。
4. 输出语法树，以便于检查分析结果的正确性。

四. 实验步骤

1. 定义词法单元的数据结构，包括类型和值两个属性。
2. 实现词法分析程序，将源程序分解为词法单元序列。
3. 定义语法树的数据结构，包括节点类型和子节点列表两个属性。
4. 实现递归下降语法分析程序，根据文法规则生成语法树。
5. 输出语法树，以便于检查分析结果的正确性。

五. 实验结果

以下是一个示例源程序：

if b then a else if b then a else a

通过词法分析和递归下降语法分析，可以生成以下语法树：

可以看到，语法树正确地反映了源程序的结构，证明递归下降语法分析程序的正确性。

六. 实验总结

本次实验实现了一个递归下降语法分析程序，通过对源程序的词法分析和语法分析，生成了语法树，并输出了语法树以便于检查分析结果的正确性。递归下降语法分析是一种基本的语法分析方法，掌握其原理和实现方法对于进一步学习编译原理具有重要意义。