递归下降分析实验：LL(1)文法与计算器实现

"实验2-自顶向下语法分析1" 本次实验主要涉及编译原理中的自顶向下语法分析方法，特别是LL(1)分析法。实验的目标是让学生深入理解FIRST与FOLLOW集合的计算、LL(1)文法的判定和分析过程，并通过手工编程实现一个简单的计算器。 实验内容包括两部分：一是应用递归下降子程序分析算术表达式文法；二是设计并实现一个基于抽象语法树（AST）的计算器。 1. **算法思想**： - **递归下降分析**：这是一种自顶向下的语法分析方法，通过递归调用解析函数来模拟分析过程。在给定的文法中，每个非终结符对应一个解析函数，函数的调用顺序反映了文法产生式的右部。例如，文法G[E]表示E可以由TE^，E^可以由+TE^或$等推导而来。 - **模拟栈操作**：在分析过程中，使用递归调用来模拟栈操作，将产生式的右部逆序压栈，以E为例，调用E()函数时会先压入T，再压入E^。 2. **计算器的实现策略**： - **双栈处理**：为了处理算术表达式，使用了两个栈，一个存储运算符（算符栈），另一个存储数字（数字栈）。根据运算符的优先级，当遇到优先级高的运算符时，会弹出栈中所有优先级低于它的运算符，完成运算。 - **优先级规则**：在这个实验中，+的优先级高于*，这意味着遇到"+"时，会先处理所有已有的"*"运算。 3. **设计过程中的问题与对策**： - 原计划允许动态输入上下文无关文法（CFG），但由于技术限制和复杂性，改为固定文法在程序中。 - 计算器实现参考了网络资料，采用双栈避免了类型转换的复杂性。 4. **实验特色**： - 多次执行能力：用户可以反复使用这个计算器程序进行不同的计算。 - 高精度：计算器能够处理复杂的算术表达式，确保计算结果的准确性。 5. **具体实现**： - **主要变量**：可能包括表示栈的数组，当前字符的指针，以及其他用于状态跟踪的变量。 - **主要函数**：可能包括E()、T()、F()等解析函数，以及处理运算符和数字的辅助函数。 - **测试与运行情况**：通过输入样例数据，如"10+10*(10"，来验证程序的正确性和功能完整性。 通过这个实验，学生不仅掌握了递归下降分析的基本原理，还学会了如何将理论知识应用于实际编程，增强了对编译器工作原理的理解。