题目描述 已知文法 G (E): E→TE' E'→+TE' | ε T→FT' T'→*FT' | ε F→(E) | i 试编写一个预测分析程序，判断文法 G 所能接受的串。 输入 输入多行由终止符构成的算术表达式。输入 EOF 结束 输出 判断每行输入的算术表达式是否为合法的语法单位，如果算术表达式在语法结构上合法，输出 "syntax correct"；否则输出："syntax error"。 样例输入 i+i*(i+i)# ii*ii# 样例输出 syntax correct syntax error 根据给出的输入输出设计相应的C

### 实现LL(1)预测分析器 为了编写一个基于给定文法 \( G(E) \) 的 C 语言程序来解析输入字符串并验证其语法正确性，可以按照以下方法设计 LL(1) 预测分析表，并通过栈模拟分析过程。 #### 文法回顾 已知文法如下： - \( E \to TE' \)[^1] - \( E' \to +TE' \mid \epsilon \)[^1] - \( T \to FT' \) - \( T' \to *FT' \mid \epsilon \)[^1] - \( F \to (E) \mid i \)[^1] #### 构建 FIRST 和 FOLLOW 集合 FIRST 和 FOLLOW 是构建 LL(1) 分析表的基础。以下是这些集合的内容： - **FIRST集**[^2]: - \( FIRST(E) = FIRST(T) = FIRST(F) = \{i, (\} \) - \( FIRST(E') = \{+, \epsilon\} \) - \( FIRST(T') = \{*, \epsilon\} \) - **FOLLOW集**[^3]: - \( FOLLOW(E) = \{\$, )\} \) - \( FOLLOW(E') = \{\$, )\} \) - \( FOLLOW(T) = \{+, \$, )\} \) - \( FOLLOW(T') = \{+, \$, )\} \) - \( FOLLOW(F) = \{*, +, \$, )\} \) #### 构建 LL(1) 分析表 根据上述 FIRST 和 FOLLOW 集合，可得到 LL(1) 分析表。例如，在表格中填入对应的产生式规则。 | | $ i $ | $ ($ | $ ) $ | $ + $ | $ * $ | $ \$ $ | |-------|--------|---------|---------|---------|---------|----------| | $ E $ | $ TE' $ | $ TE' $ | | | | | | $ E' $ | | | $ \epsilon $ | $ +TE' $ | | $ \epsilon $ | | $ T $ | $ FT' $ | $ FT' $ | | | | | | $ T' $ | | | $ \epsilon $ | | $ *FT' $ | $ \epsilon $ | | $ F $ | $ i $ | $ (E) $ | | | | | #### 设计 C 程序逻辑 下面是一个完整的 C 程序框架，用于实现该 LL(1) 解析器的功能。 ```c #include <stdio.h> #include <string.h> #define MAX_STACK_SIZE 100 #define MAX_INPUT_LENGTH 100 char stack[MAX_STACK_SIZE]; int top = -1; void push(char symbol) { if (top >= MAX_STACK_SIZE - 1) { printf("Stack overflow\n"); return; } stack[++top] = symbol; } char pop() { if (top < 0) { printf("Stack underflow\n"); return '\0'; } return stack[top--]; } // Function to simulate the parser using a stack and input string. int parse(char input[]) { int i = 0; char current_input_symbol, current_stack_top; // Initialize stack with start symbol 'E$' push('$'); push('E'); while (top != -1) { current_stack_top = stack[top]; current_input_symbol = input[i]; if (current_stack_top == '$' && current_input_symbol == '$') { break; // Successful parsing } if (current_stack_top == current_input_symbol) { // Match terminal symbols pop(); i++; } else if (current_stack_top == 'E') { // Apply production rules based on analysis table if (current_input_symbol == 'i' || current_input_symbol == '(') { pop(); // Remove 'E' from stack push('E'); // Push reverse of 'TE'' push('T'); } else { printf("Error at position %d: Invalid rule for non-terminal E.\n", i); return 0; } } else if (current_stack_top == 'E\'') { if (current_input_symbol == '+') { pop(); // Remove 'E'' from stack push('E'); // Push reverse of '+TE'' push('T'); push('+'); } else if (current_input_symbol == ')' || current_input_symbol == '$') { pop(); // Replace 'E'' by epsilon } else { printf("Error at position %d: Invalid rule for non-terminal E'.\n", i); return 0; } } else if (current_stack_top == 'T') { if (current_input_symbol == 'i' || current_input_symbol == '(') { pop(); // Remove 'T' from stack push('T'); // Push reverse of 'FT'' push('F'); } else { printf("Error at position %d: Invalid rule for non-terminal T.\n", i); return 0; } } else if (current_stack_top == 'T\'') { if (current_input_symbol == '*') { pop(); // Remove 'T'' from stack push('T'); // Push reverse of '*FT'' push('F'); push('*'); } else if (current_input_symbol == '+' || current_input_symbol == ')' || current_input_symbol == '$') { pop(); // Replace 'T'' by epsilon } else { printf("Error at position %d: Invalid rule for non-terminal T'.\n", i); return 0; } } else if (current_stack_top == 'F') { if (current_input_symbol == 'i') { pop(); // Replace 'F' by 'i' push('i'); } else if (current_input_symbol == '(') { pop(); // Replace 'F' by '(E)' push(')'); push('E'); push('('); } else { printf("Error at position %d: Invalid rule for non-terminal F.\n", i); return 0; } } else { printf("Unexpected error encountered during parsing.\n"); return 0; } } if (top == -1 && input[i] == '$') { printf("Input is syntactically correct.\n"); return 1; } else { printf("Parsing failed due to syntax errors.\n"); return 0; } } int main() { char input[MAX_INPUT_LENGTH], temp[MAX_INPUT_LENGTH]; printf("Enter an arithmetic expression ending with '$': "); scanf("%s", input); strcpy(temp, input); // Preserve original input for output purposes strcat(input, "$"); // Append end-of-input marker if (parse(input)) { printf("The expression '%s' follows the given grammar rules.\n", temp); } else { printf("The expression '%s' does not follow the given grammar rules.\n", temp); } return 0; } ``` 此代码实现了基于给定文法的 LL(1) 预测分析器功能。 --- ###