编译原理实验二 海南大学

掌握递归下降语法程序的分析、设计与实现的基本技术与一般方法。 编写识别由下列文法G[E]所定义的表达式的递归下降语法分析器。 EE+T | E-T | T TT*F | T/F |F F(E) | i 输入：含有十进制数或十六进制数的表达式，如：75+(1ah-3*2)+68/2#。 输出：语法正确或语法错误信息。 ### 编译原理实验二——递归下降语法分析器 #### 实验背景及目标 本实验基于海南大学计算机科学与技术学院的课程“编译原理”，旨在帮助学生深入理解并掌握递归下降语法分析的基本技术和方法。通过实验，学生能够熟悉如何编写用于识别特定文法所定义表达式的递归下降语法分析器。 #### 实验任务概述 实验任务是设计并实现一个递归下降语法分析器，该分析器能够识别由以下文法`G[E]`定义的表达式： - **E** → E + T | E − T | T - **T** → T * F | T / F | F - **F** → (E) | i 这里的`i`代表数字（可以是十进制或十六进制），并且允许输入包含这些数字的表达式。例如，输入`75+(1ah-3*2)+68/2#`，输出应该是关于该表达式语法是否正确的信息。 #### 文法解析与转换 为了确保递归下降分析器的正确性，首先需要将给定的文法转换为LL(1)文法形式。LL(1)文法是一种特殊的上下文无关文法，可以通过简单的递归下降算法来处理，这在编写递归下降分析器时非常重要。 对于本实验中的文法，我们注意到它已经符合LL(1)文法的要求，因此无需进一步转换。 #### 分析器设计 递归下降语法分析器的设计主要分为以下几个步骤： 1. **词法分析**：首先对输入的字符串进行词法分析，将它们转换为有意义的符号（token）。在这个实验中，词法分析的任务包括识别数字、操作符等基本元素。 2. **语法分析**：完成词法分析后，接下来的任务是根据给定的文法规则检查这些符号是否构成合法的表达式。这里采用的是递归下降分析的方法。 #### 词法分析实现 实验中的词法分析部分使用了C语言实现，具体代码如下所示： ```c #define _CRT_SECURE_NO_WARNINGS #include #include int isDigitOrChar(char ch){ enum type { digit, space, Hh, AF, letter, end }; if (ch >= '0' && ch <= '9') return digit; else if (ch == ' ') return space; else if (ch == 'H' || ch == 'h') return Hh; else if ((ch >= 'A' && ch <= 'F') || (ch >= 'a' && ch <= 'f')) return AF; else if ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z')) return letter; else if (ch == '#') return end; } int wordanalyse(char words[]){ words[strlen(words)] = '#'; char* q = NULL; char word[20] = ""; int state = 0; int i = 0; q = words; while (*q){ switch (state){ case 0: switch (isDigitOrChar(*q)){ case digit: word[i++] = *q; state = 2; break; case Hh: case AF: case letter: word[i++] = *q; state = 1; break; case space: state = 0; break; default:; } break; case 1: switch (isDigitOrChar(*q)){ case digit: case Hh: case AF: case letter: word[i++] = *q; state = 1; break; case space: if (word[0] != '\0'){ printf("%s 是一个标识符\n", word); return -1; } memset(word, 0, sizeof(word)); i = 0; state = 0; break; case end: printf("%s 是一个标识符\n", word); break; default: word[i++] = *q; state = 5; } break; case 2: switch (isDigitOrChar(*q)){ case digit: word[i++] = *q; state = 2; break; case Hh: word[i++] = *q; state = 3; break; case AF: word[i++] = *q; state = 4; break; case letter: word[i++] = *q; state = 5; break; } break; // 其他状态... } q++; } } ``` 此代码实现了词法分析器的基本功能，它通过检查每个字符来识别数字、字母等，并将它们分类为相应的符号类型。 #### 语法分析实现 语法分析部分的实现同样重要，它依赖于递归下降分析方法。具体的递归下降函数会根据上述文法规则递归地调用自身或其他函数来匹配输入序列。这部分的具体实现细节没有给出，但通常会涉及到定义一系列函数，比如`E()`、`T()`、`F()`等，这些函数将根据文法规则逐层分解输入。 #### 总结 通过上述实验，学生不仅能够学习到如何构建递归下降语法分析器的基本知识，还能深入了解词法分析和语法分析的过程。此外，通过实际编程实践，学生还能够增强解决实际问题的能力，这对于未来的软件开发工作非常有帮助。