实验四 算符优先分析器的构造 1. 实验目的与任务 （1）理解自底向上的语法分析的基本思想。 （2）理解算符优先文法的概念。 （3）掌握算符分析表和优先函数的构造。 （4）掌握算符优先分析器的工作原理和工作流程。 2. 实验原理 算符优先分析法是一种简单、直观、广为使用的语法分析方法，这种方法特别适用于程序设计语言中的表达式的分析。算符优先分析法就是仿照算术表达式的运算过程而提出的一种自底向上的语法分析方法，它可以分析算符优先文法，分析的基本思想是：根据文法终结符之间的优先关系，通过比较相邻算符的优先次序来确定句型中的最左素短语，并进行归约。 所谓的算符优先文法是指：对算符文法中任意两个终结符对a、b之间至多有一种优先关系成立的文法，而算符文法G中的任何一个产生式中都不包含两个非终结符相邻的情况。对于满足这样条件的文法，我们就可以用算符优先分析法对其进行分析。 确定了符合要求的文法之后，自底向上的分析方法的关键就是如何在当前句型中寻找可归约的子串，算符优先分析法在归约过程中，通过终结符之间的优先关系确定当前的句型中的最左素短语，与非终结符无关，只需知道把当前句型中的最左素短语归约为一非终结符，不必知道该非终结符的名字是什么，这样也就去掉了单非终结符的归约，一旦找到最左素短语，就将它归约成一个非终结符。 在算符优先分析法分析过程中，可以设置一个栈S，用来存放归约或者待形成最左素短语的符号串，用一个工作单元a存放当前读入的输入字符，归约成功的标志是当读入的输入字符是句子的结束符号#时，栈S中只剩下#N。 3. 实验内容 给定一个上下文无关文法G： <常量说明部分>→const<常量定义>{，<常量定义>} <常量定义>→<标识符>＝<无符号整数> <无符号整数>→<数字>{<数字>} <变量说明部分>→{var}01 <标识符>{,<标识符>}:integer;∣{var}01 <标识符>{,<标识符>}:real;∣{var}01 <标识符>{,<标识符>}:boolean; <标识符>→<字母>{<字母>∣<数字>} <语句部分>→<语句>∣<复合语句> <复合语句>→begin <语句>{;begin<语句>end;} end. <语句>→<赋值语句>∣<条件语句>∣<循环语句> <赋值语句>→<标识符>:=<表达式> <表达式>→[+∣-]<项>∣<表达式>+<项>∣<表达式>-<项> <项>→<因子>∣<项>*<因子>∣<项>/<因子> <因子>→<标识符>∣<常量>∣（<表达式>） <常量>→<无符号整数> <条件语句>→if <条件> then <语句> else <语句> <条件>→<表达式><关系运算符><表达式>{(and∣or) <表达式><关系运算符><表达式>} <循环语句>→while (<条件>){(and∣or) (<条件>)} do <语句> <关系运算符>→=∣<∣>∣≤∣≥ <字母>→a∣b∣c∣…∣z ∣A∣B∣C∣…∣Z <数字>→0∣1∣2∣…∣9 编写程序，构造上述文法G的算符优先分析器，使其能实现如下功能： （1）扫描单词的内部表示形式，按语言的语法规则识别出语法单位（语句等）； （2）对各语法单位进行语法检查； （3）若发现单词的组成有错误时，输出有关的出错信息。 给出c语言的代码

### 算符优先分析器的构造方法 算符优先分析器是一种用于语法分析的技术，其核心在于通过构建优先关系表来判断输入串是否可以由给定文法推导出来。以下是实现的关键部分： #### 扫描单词功能 扫描单词的功能主要是将输入源程序分解为一系列基本单元（即单词）。这些单词可能包括关键字、标识符、运算符、分隔符和常量等[^1]。 ```c #include <stdio.h> #include <string.h> #define MAX_LEN 100 char zhongjianq[MAX_LEN]; int syn; void scaner(char input[]) { int i = 0; while (input[i] != '\0') { switch (input[i]) { case '+': zhongjianq[strlen(zhongjianq)] = '+'; break; case '-': zhongjianq[strlen(zhongjianq)] = '-'; break; case '*': zhongjianq[strlen(zhongjianq)] = '*'; break; case '/': zhongjianq[strlen(zhongjianq)] = '/'; break; case '(': zhongjianq[strlen(zhongjianq)] = '('; break; case ')': zhongjianq[strlen(zhongjianq)] = ')'; break; default: if (isdigit(input[i])) { char num_str[10] = {0}; int j = 0; while (isdigit(input[i])) { num_str[j++] = input[i++]; } i--; // 回退一位 strcat(zhongjianq, num_str); } else { printf("非法字符：%c\n", input[i]); syn = -1; return; } } i++; } } ``` #### 语法单位识别 语法单位识别的核心是对终结符和非终结符进行分类，并根据文法规则定义 `FirstVT` 和 `LastVT` 集合[^2]。这一步骤通常涉及对文法的深入解析。 ```c typedef struct { char firstvt_set[50]; char lastvt_set[50]; } GrammarSymbol; GrammarSymbol symbols[50]; void initialize_symbols() { strcpy(symbols['+'].firstvt_set, "+"); strcpy(symbols['-'].firstvt_set, "-"); strcpy(symbols['*'].lastvt_set, "*"); strcpy(symbols['/'].lastvt_set, "/"); } // 判断某个符号是否属于 FirstVT 或 LastVT int is_in_firstvt(char symbol, char vt) { return strchr(symbols[symbol].firstvt_set, vt) != NULL; } int is_in_lastvt(char symbol, char vt) { return strchr(symbols[symbol].lastvt_set, vt) != NULL; } ``` #### 语法检查 语法检查的主要工作是利用优先关系矩阵验证输入序列的有效性。如果当前符号之间的优先级满足条件，则继续匹配；否则报错退出[^3]。 ```c #include <stdbool.h> bool analyse_stack(char stack[], char input[], int *sp, int ip) { if (*sp >= 0 && ((is_in_firstvt(stack[*sp], input[ip]) || is_in_lastvt(stack[*sp], input[ip]))) { return true; } return false; } void analyse(char input[]) { char optr_stack[MAX_LEN]; // 运算符栈 char opnd_stack[MAX_LEN]; // 操作数栈 int sp_optr = -1; // 运算符栈指针 int sp_opnd = -1; // 操作数栈指针 int ip = 0; // 输入指针 optr_stack[++sp_optr] = '#'; // 初始化栈底符号 while (true) { if (optr_stack[sp_optr] == '#' && input[ip] == '#') { printf("字符串可被文法识别。\n"); break; } if (!analyse_stack(optr_stack, input, &sp_optr, ip)) { printf("错误：无法匹配 %c 和 %c 的优先级。\n", optr_stack[sp_optr], input[ip]); return; } if (optr_stack[sp_optr] == '(' && input[ip] == ')') { --sp_optr; ++ip; } else if (strchr("+-*%", optr_stack[sp_optr]) && !strchr("(#", optr_stack[sp_optr])) { double b = opnd_stack[sp_opnd--]; double a = opnd_stack[sp_opnd--]; char operator_ = optr_stack[sp_optr--]; double result = 0; switch (operator_) { case '+': result = a + b; break; case '-': result = a - b; break; case '*': result = a * b; break; case '%': result = a / b; break; } opnd_stack[++sp_opnd] = result; } else { if (isdigit(input[ip])) { opnd_stack[++sp_opnd] = input[ip] - '0'; ++ip; } else { optr_stack[++sp_optr] = input[ip]; ++ip; } } } } ``` --- ### 完整流程示例 以下是一个完整的调用过程，展示如何使用上述模块完成整个分析任务。 ```c int main() { char input_expression[] = "3+4*(7-2)#"; scaner(input_expression); if (syn == 0) { analyse(zhongjianq); } else { printf("输入存在错误，无法继续分析。\n"); } return 0; } ``` --- ### 总结 以上代码展示了如何用C语言实现一个简单的算符优先分析器，涵盖了从单词扫描到语义分析的过程。需要注意的是，在实际应用中还需要进一步优化性能和增强鲁棒性。