桂林电子科技大学编译原理实验手册：最左推导与最右推导

"桂林电子科技大学编译原理实验指导书，由唐敏编著，主要针对数学与计算科学学院的学生。本书旨在帮助读者深入理解编译原理，通过一系列实验来实践编译器的构造过程，特别关注如何为输入的符号串建立推导。实验内容包括根据给定的文法规则和符号串生成最左推导或最右推导，并能判断输入字符串是否为文法中的句子。实验要求程序具备交互性，允许用户选择推导方式，并能自动生成或交互式建立推导过程。书中提供了详细的输出样例，展示推导过程，帮助读者更好地理解和应用编译原理的基本概念。" 在编译原理中，实验一“建立推导”是一个关键环节，它涉及到以下几个重要的知识点： 1. 文法和重写规则：实验中提到了“给定文法的一组重写规则”，这通常指的是上下文无关文法（Context-Free Grammar，CFG），由非终结符、终结符、起始符号和一组产生式规则组成。重写规则是这些产生式的应用，允许我们从一个符号串推导出另一个符号串。 2. 最左推导和最右推导：这两种推导方式是分析语法结构的两种常见方法。最左推导是从文法的起始符号开始，每次选择最左边的非终结符进行替换，直至得到目标字符串。最右推导则是从目标字符串开始，逐步将最右边的非终结符替换为产生式右侧的符号串。 3. 交互式确定推导方式：实验要求程序允许用户选择推导方式，这有助于用户理解推导过程，因为最左推导和最右推导代表了不同的解析策略，分别对应于自顶向下和自底向上的解析。 4. 自动与交互式建立推导过程：自动建立推导意味着程序会根据输入的文法规则和符号串自动完成推导；而交互式建立则让用户参与到每一步的决策中，可以更直观地看到每个规则的应用。 5. 判断句子：在编译原理中，一个字符串如果能通过文法的推导过程推导到空串，则称其为该文法的句子。实验要求程序能判断输入符号串是否是句子，这是检查文法覆盖率和语义正确性的基本步骤。 通过这样的实验，学生不仅能学习到理论知识，还能亲手实践编译器的构造，增强对编译原理的理解，同时培养问题解决和编程能力。实验指导书中的输出样例提供了清晰的示例，便于学生对照学习和自我检验。