《编译原理》实验报告——语法分析1

《编译原理》实验报告的主题聚焦于语法分析的LR(1)方法，主要涉及了编译器设计中从文法到分析表的构建过程。在本实验中，使用Java编程语言实现了一个C语言子集文法的语法分析器，其核心步骤如下： 1. **初始化数据结构**：根据给定的文法G，需要初始化一些关键的数据结构。这包括终结符集（Terminal Set）、非终结符集（Non-Terminal Set）以及非终结符的first集。first集是用于构建LR(1)分析表中的预测符，它表示非终结符可以开始的符号序列。 2. **构造LR(1)状态机**：接下来，根据文法G，生成LR(1)状态机，也就是项目集。LR(1)分析是基于项目的，每个项目包含一个产生式和一个点，表示分析过程的当前位置。 3. **生成分析表**：从状态机出发，生成分析表的两个部分：GOTO部分和ACTION部分。GOTO部分指示在当前状态下遇到某个非终结符时应转移到哪个状态，ACTION部分则表示在当前状态下遇到某个终结符时应该执行的操作，如移进或规约。 4. **分析输入字符串**：使用生成的LR(1)分析表，对来自词法分析器的token序列进行分析，自底向上地确定其是否符合文法规则。 5. **错误处理与提示**：在分析过程中，如果遇到文法二义性或输入字符串不符合文法的情况，程序会提供错误提示。 实验中，一些关键数据结构如下： - **产生式（Production）**：由一个非终结符（Left）和一个右侧元素序列（ArrayList<String>）组成，表示一种转换规则。 - **LR(1)分析式**：包含一个产生式d和一个LR(1)分析式右端的终结符lr，以及点的位置index，指示分析过程的状态。 - **DFA中的状态（State）**：每个状态有唯一的编号Id，以及包含所有LR(1)分析式的集合set。 核心算法包括： - **计算first集**：这是一个递归过程，遍历文法符号，将非终结符的first集通过其产生的产生式推导得到，同时处理左递归以避免无限递归。 - **构建DFA**：也是一个递归过程，通过遍历LR(1)分析式中点右边的文法符号产生式，不断扩展状态，并通过路径获取下一个状态。 构建语法分析表是将上述信息整合，形成一个指导分析过程的表格，它包含了如何根据当前状态和输入符号进行下一步操作的规则。这个表是LR分析器的核心，使得编译器能够判断输入的token序列是否符合文法，并指导如何进行下一步的解析动作。