编译原理递归下降实验报告

在编译原理中，递归下降分析是一种基于上下文无关文法（Context-Free Grammar, CFG）的解析技术，尤其适用于自顶向下的解析策略。在本次实验报告中，我们主要探讨了如何通过递归下降方法处理两个特定的文法：G[E] 和 G[S]，并实现了相应的C语言识别程序。 我们来看文法 G[E]： ``` E ::= E+T | T T ::= T*F | F F ::= (E) | i ``` 这个文法存在左递归，即E可以由自身加一个T构成（E+E）。为消除左递归，我们将其转换为等价的非左递归文法 G'[E]： ``` E ::= TE' E' ::= +TE' | ε T ::= FT' T' ::= *FT' | ε F ::= (E) | i ``` 在这个新文法中，E'表示E后面可能跟一个+和另一个E，而T'表示T后面可能跟一个*和另一个T。 接着，我们分析文法 G[S]： ``` S ::= S;T | T T ::= if e then S else S | if e then S | a ``` 同样，我们消除其左递归，得到等价的文法 G'[S]： ``` S ::= TS' S' ::= ;TS' | ε T ::= if e then ST' | a T' ::= else S | ε ``` 这里，S'表示S后面可能跟一个;和另一个T。 为了实现这两个文法的递归下降解析，我们使用C语言编写了两个程序。每个程序包含了多个函数，每个函数对应文法中的一个非终结符。例如，在G[E]的解析程序中，我们有E()、E1()、T()、T1()和F()函数。这些函数通过递归调用来匹配输入的字符串，直到找到一个有效的短语。 在程序中，我们使用GetSymbol()函数获取输入的字符，Error()函数用于处理解析错误。例如，当在预期的位置没有找到正确的符号时，Error()函数会被调用。 对于文法G[E]的程序，E()是主入口，它调用T()。T()调用F()，然后根据当前的输入符号进行不同的操作，如判断是否为'+'或'*'，或者是否为'i'或'('。F()函数会判断当前符号是否为'i'或'('，并进行相应的处理。整个过程形成一个递归结构，与文法结构相对应。 同样的逻辑也应用于文法G[S]的程序，只是处理的符号和规则有所不同，主要处理';'、'if'、'then'、'else'和'a'。 通过这两个实例，我们可以看到递归下降解析如何将文法规则转换为代码，从而解析输入的字符串。这种解析方式简单直观，但对文法有一定的限制，如不能处理所有的上下文无关文法，尤其是那些包含右递归和左递归的文法。不过，对于教学和理解编译原理，递归下降解析是一种很好的实践方法。