利用C语言编制预测分析程序，并对简单语言进行语法分析。 1. 待分析的简单语言的语法 E → TE' E' → +TE' | -TE' | ε T → FT' T' → *FT' | /FT' | ε F → (E) | id 2. 实验要求说明 1) 构造文法的LL预测分析表； 2) 构造LL语法分析器的总控程序； 3) 输入文法：文法描述存储在文本文件中（编码格式ANSI），文件名作为命令行参数输入； 4) 输入待分析的符号串：符号串存储在文本文件中（编码格式ANSI），文件名作为命令行参数输入； 5) 输出文法的LL预测分析表到标准输出设备； 输出分析结果：输出待分析符号串是否为该文法正确句子的判断，并输出文本形式的分析过程。

### 实现LL(1)预测分析器的关键要素 为了实现一个完整的LL(1)预测分析器，需要以下几个核心模块： #### 1. **构造LL(1)分析表** 构建LL(1)分析表涉及计算FIRST集和FOLLOW集。这些集合用于决定文法中的每个非终结符在特定上下文中可能产生的第一个符号或跟随的符号。 通过以下步骤可以完成这一目标： - 计算每个非终结符的`FIRST`集[^2]。 - 计算每个非终结符的`FOLLOW`集[^2]。 - 使用`FIRST`和`FOLLOW`集填充LL(1)分析表。对于每条产生式A -> α，在`FIRST(α)`的所有终端符号位置填入该产生式的编号；如果`FIRST(α)`包含ε，则还需考虑`FOLLOW(A)`[^1]。 以下是计算`FIRST`和`FOLLOW`集的一个伪代码框架： ```c #include <stdio.h> #include <string.h> #define MAX_SYMBOLS 100 char firstSet[MAX_SYMBOLS][MAX_SYMBOLS]; char followSet[MAX_SYMBOLS][MAX_SYMBOLS]; // 初始化FIRST和FOLLOW集为空 void initializeSets() { memset(firstSet, '\0', sizeof(firstSet)); memset(followSet, '\0', sizeof(followSet)); } // 添加到某个集合中 void addToSet(char set[][MAX_SYMBOLS], char symbol, char toAdd) { int i; for (i = 0; set[symbol - 'A'][i]; ++i); if (!strchr(set[symbol - 'A'], toAdd)) { set[symbol - 'A'][i] = toAdd; } } ``` #### 2. **总控程序设计** 总控程序负责管理整个语法分析流程。其主要功能包括初始化栈、读取输入字符串、更新栈状态以及执行相应的动作（如移进或规约）。具体逻辑如下： - 初始状态下，将起始符号压入栈底，并设置当前输入指针指向输入串的第一个字符。 - 循环操作直到栈为空或者遇到错误为止。每次循环需比较栈顶元素与当前输入字符的关系，依据分析表采取相应行动[^1]。 下面展示了一个简单的总控程序模板： ```c typedef struct StackNode { char data; struct StackNode* next; } StackNode; StackNode* createNode(char value) { StackNode* newNode = malloc(sizeof(StackNode)); newNode->data = value; newNode->next = NULL; return newNode; } int isEmpty(StackNode* top) { return !top; } void push(StackNode** top_ref, char new_data) { StackNode* nn = createNode(new_data); nn->next = (*top_ref); (*top_ref) = nn; } char pop(StackNode** top_ref) { char res = (*top_ref)->data; StackNode* temp = *top_ref; (*top_ref) = (*top_ref)->next; free(temp); return res; } void controlProgram(StackNode* stackTop, const char input[], ...) { // 控制程序的具体实现... } ``` #### 3. **解析给定文法并验证输入符号串** 假设已知文法规则为 `E → TE'`, 需要按照上述方法逐步处理输入序列。每当发现匹配项时应用对应的产生式替换之，直至最终接受或拒绝输入串[^4]。 --- ### 示例代码片段 这里给出一段简化版的LL(1)分析器实现示例，仅适用于特定的小型文法定义： ```c #include <stdio.h> #include <stdlib.h> #include <ctype.h> const char table[5][5] = {{'#','#','T+E','$'},{'#','TE\'','#','$'},{'#','#','e','#'},{'#','#','id','#'}}; const char nonTerminals[] = {'E', 'E\'', 'T', 'T\''}; int main(){ printf("Simple LL(1) Parser Example\n"); // 假设输入为 id+id$ char inputStr[]="id+id$"; size_t len=strlen(inputStr); // 构建初始堆栈 StackNode* stk=createNode('$'); push(&stk,'E'); while(!isEmpty(stk)){ char top=pop(&stk); if(isupper(top)){ // 如果是非终结符查找对应规则 char currentInput=inputStr[0]; int row=-1,col=-1; for(int r=0;r<sizeof(nonTerminals)/sizeof(*nonTerminals);r++)if(nonTerminals[r]==top)row=r; for(int c=0;c<len && col==-1;c++)for(int k=0;k<strlen(table[row]);k++)if(currentInput==table[row][k])col=k; if(row!=-1&&col!=-1){ char production[]=table[row][col]; // 反向压回生产式右侧内容 for(int p=strlen(production)-1;p>=0;p--)push(&stk,production[p]); }else{ fprintf(stderr,"Error at parsing %c with top as %c.\n",currentInput,top); exit(EXIT_FAILURE); } }else{ // 终结符直接对比弹出 if(top!=inputStr[0]){ fprintf(stderr,"Mismatch error expected:%c but got:%c\n",top,inputStr[0]); exit(EXIT_FAILURE); } inputStr++; } } puts("Parsing Successful!"); return EXIT_SUCCESS; } ``` --- ### 输出样例说明 运行以上代码会模拟对指定输入串进行语法校验的过程，并输出成功与否的结果消息。 ---