编译原理 递归下降子程序的编写

1．给定文法： S→（T）|a+S|a T→T，S|S 改写文法，使其可以使用递归下降子程序方法进行分析，编写递归下降子程序，判断句子：（（（a+a+a），a+a），a）是否符合该文法。 输入：（（（a+a+a），a+a），a） 输出：结构正确或结构错误 **编译原理 - 递归下降子程序的编写** 在编译原理中，递归下降解析是一种基于上下文无关文法的自顶向下解析方法。它通过一系列的递归函数来解析输入的符号串，每个函数对应文法的一个非终结符。在本实验中，我们需要对给定的文法进行改写，以便使用递归下降子程序进行分析。 **给定文法：** ```markdown S → (T) | a + S | a T → T, S | S ``` 这个文法表示一个简单的表达式，其中`S`是非终结符，代表一个表达式，`T`是非终结符，代表一个逗号分隔的表达式列表。我们需要改写这个文法，使得它可以被递归下降子程序解析。 **改写后的文法：** 由于原始文法已经适合递归下降解析，我们不需要做大的改动。不过，为了清晰起见，我们可以将文法稍微调整一下，明确终止符和非终结符的边界： ```markdown S → expr expr → (expr) | a + expr | a expr_list → expr_list, expr | ε ``` 这里，`expr`表示表达式，`expr_list`表示逗号分隔的表达式列表，`ε`表示空串。 **递归下降子程序的编写：** 根据改写后的文法，我们可以编写如下的C++递归下降子程序： 1. `match(char t)`：匹配当前的输入字符与期望的字符`t`，如果匹配成功，移动输入指针。 2. `S()`：解析`S`规则，即解析整个表达式。 3. `expr()`：解析`expr`规则，处理括号、加法和单个字母。 4. `expr_list()`：解析`expr_list`规则，处理逗号分隔的表达式列表。 **程序源代码片段：** ```cpp void match(char t); void S(); void expr(); void expr_list(); // ... 其他函数定义 void match(char t){ if(lookahead == t) lookahead = a[++j]; else error(); } void S(){ expr(); } void expr(){ if(lookahead == '('){ match('('); expr(); match(')'); } else if(lookahead == 'a'){ match('a'); expr_list(); } else if(lookahead == '+'){ match('+'); expr(); } else { error(); } } void expr_list(){ if(lookahead == ','){ match(','); expr(); expr_list(); } } // ... 其他函数和主函数 ``` **实验程序执行与结果：** 程序接收一个以`@`结尾的表达式，如`(((a+a+a),a+a),a)`，然后尝试使用递归下降子程序解析。如果输入的表达式符合文法，程序输出“匹配”，否则输出“不匹配”。 **优点和特色：** 1. 输入通过文件读取，简化了用户交互。 2. 递归下降子程序具有较好的健壮性，可以准确指出错误位置。 3. 使用C语言编写，易于理解和实现。 **问题与解决方案：** 在实验过程中，可能出现输入繁琐和错误定位不准确的问题。通过文件读写优化输入，并通过增强的`error`函数改进错误处理，以提高程序的健壮性。 **总结与体会：** 本次实验加深了对递归下降预测分析的理解，包括其工作原理、可能遇到的回溯问题及其解决方案。通过编写递归下降子程序，明确了这种方法的优缺点，比如简洁性、易于理解，但可能会遇到回溯问题。通过实践，我们为学习其他预测分析方法打下了坚实的基础。