编译原理实验指导：求非终结符推导空字符与FIRST集合

"该资源包含了两个编译原理实验的题目，分别是求能推出空字符的非终结符和求所有文法符号的FIRST集合。这两个实验旨在加深学生对编译过程的理解，提高编程能力，为未来的工作做准备。" 实验一详解： 实验名称：求出能推出空字符的非终结符 实验目的：该实验通过编程实现，帮助学生更好地理解和应用算法，增强程序设计能力，并理解编译器进行语法分析的各个阶段。 实验要求：学生需使用C语言编写一个函数，处理给定的上下文无关文法，找出能推导出空字符的非终结符。实验过程中，学生需要独立完成程序，对代码有清晰的解释。 实验步骤： 1. 需要掌握C语言编程基础。 2. 设计算法流程图。 3. 实现算法，其中包括扫描文法、更新非终结符标记等步骤。 4. 对程序进行调试，确保正确性。 5. 编写实验报告，记录实验过程和结果。 算法描述： - 初始化所有非终结符标记为“未定”。 - 扫描产生式，处理两种情况：(A) 删除含有终结符的产生式，若导致所有以特定非终结符为左部的产生式被删除，将其标记为“否”。(B) 若发现能推出空字符的产生式，更新非终结符标记为“是”，并删除相应产生式。 - 接着扫描产生式右部，根据非终结符的标记进行处理：(A) 如果标记为“是”，则删除非终结符，若使产生式右部变空，更新左部非终结符标记为“是”并删除其产生式；(B) 如果标记为“否”，则删除整个产生式，检查是否影响其他产生式，必要时更新非终结符标记。 - 重复第三步，直至不再改变标记。 实验二详解： 实验名称：求出所有文法符号的FIRST集合 实验目的：通过编程实现，深化对FIRST集合概念的理解，理解自上而下的语法分析，提升编程技能，为未来的职业生涯奠定基础。 实验要求：利用C语言编写函数，计算给定文法的每个符号的FIRST集合。实验假设非终结符是否能推出空字符已在实验一中给出。 实验步骤： 1. 学生需具备C语言基础。 2. 设计算法框图。 3. 编写程序，依据附录中的算法执行。 4. 进行调试，验证程序的正确性。 5. 编写实验报告，记录实验过程。 算法描述： - 对于终结符X，它的FIRST集合为{X}。 - 对于非终结符X，如果有产生式X→a，那么a属于FIRST(X)。 - 如果非终结符X有产生式X→ε，那么ε属于FIRST(X)。 - 对于非终结符X，如果有多条产生式，需要遍历所有可能的情况，结合实验一的结果，更新FIRST集合。 这两个实验都强调了实际操作和理论知识的结合，通过编程解决编译原理中的问题，有助于学生系统地掌握编译器设计的核心概念。