一、 题目 编制LL1分析法的语法分析程序 二、目的 通过设计、编制、调试一个典型的语法分析程序能识别由加+、乘、括号、操作数所组成的算术表达式其文法如下： E→TE E→+TE∣ε T→FT T→FT∣ε F→E∣i 三、要求 1程序功能举例 输入：# i1 i2+i3# 输出：SUCCESS 输入：# i1 i2+i3# 输出：FOUND ERROR C语言

实现LL(1)分析法的语法分析程序。

2.程序能够正确识别由加+、乘*、括号（）、操作数所组成的算术表达式。

3.程序能够检测输入的算术表达式是否符合文法规定，若不符合则输出错误信息。

4.使用C语言编写程序。

四、思路

1.首先需要将文法转换为LL(1)文法。

2.根据LL(1)文法，构造预测分析表。

3.对输入的算术表达式进行语法分析，采用栈来存储符号串和状态。

4.判断输入的算术表达式是否符合文法规定。

五、代码实现

1.将文法转换为LL(1)文法：

E → T E' E' → + T E' | ε T → F T' T' → * F T' | ε F → ( E ) | i

2.构造预测分析表：

+      *      (      )      i      #

E NULL NULL E→TE' NULL E→TE' NULL E' +TE' NULL NULL ε ε ε T NULL NULL T→FT' NULL T→FT' NULL T' ε *FT' ε ε ε ε F NULL NULL (E) NULL i NULL

3.代码实现：

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 100

typedef struct { char nonTerm; // 非终结符 char term; // 终结符 char rule[10]; // 产生式 } Prediction;

Prediction table[5][6] = { {{NULL, NULL, NULL}, {NULL, NULL, NULL}, {'E', 'i', "E→TE'"}, {NULL, NULL, NULL}, {'E', 'i', "E→TE'"}, {NULL, NULL, NULL}}, {{'E', '+', "E'→+TE'"}, {NULL, NULL, NULL}, {NULL, NULL, NULL}, {'E', 'ε', "E'→ε"}, {NULL, NULL, NULL}, {'E', 'ε', "E'→ε"}}, {{NULL, NULL, NULL}, {NULL, NULL, NULL}, {'T', 'i', "T→FT'"}, {NULL, NULL, NULL}, {'T', 'i', "T→FT'"}, {NULL, NULL, NULL}}, {{'T', 'ε', "T'→ε"}, {'T', '', "T'→FT'"}, {NULL, NULL, NULL}, {'T', 'ε', "T'→ε"}, {NULL, NULL, NULL}, {'T', 'ε', "T'→ε"}}, {{NULL, NULL, NULL}, {NULL, NULL, NULL}, {'F', '(', "F→(E)"}, {NULL, NULL, NULL}, {'F', 'i', "F→i"}, {NULL, NULL, NULL}} };

int top = 0; // 栈顶指针 char stack[MAX] = {'#', 'E'}; // 栈 char input[MAX]; // 输入的算术表达式 int index = 0; // 输入串的指针

void push(char c) { // 入栈 stack[++top] = c; }

void pop() { // 出栈 top--; }

char getTop() { // 获取栈顶元素 return stack[top]; }

char getNextInput() { // 获取下一个输入字符 return input[index++]; }

void printStack() { // 输出栈中元素 for(int i = 0; i <= top; i++) { printf("%c", stack[i]); } printf("\n"); }

void printInput() { // 输出输入串 for(int i = index; i < strlen(input); i++) { printf("%c", input[i]); } printf("\n"); }

void error() { // 错误处理 printf("FOUND ERROR\n"); exit(0); }

int main() { printf("请输入算术表达式："); scanf("%s", input); push('#'); printf("步骤\t栈\t\t输入\t\t操作\n"); while(1) { char X = getTop(); // 获取栈顶符号 char a = getNextInput(); // 获取输入符号 if(X == a) { // 如果栈顶符号和输入符号相同，则出栈 if(X == '#') { // 如果栈顶符号为#，则语法分析成功 printf("SUCCESS\n"); exit(0); } pop(); } else if(X == 'ε') { // 如果栈顶符号为ε，则出栈 pop(); } else if(X >= 'A' && X <= 'Z') { // 如果栈顶符号为非终结符 int row = X - 'E' + 2; // 获取行 int col = a == '+' ? 0 : a == '*' ? 1 : a == '(' ? 2 : a == ')' ? 3 : a == 'i' ? 4 : 5; // 获取列 Prediction p = table[row][col]; // 获取预测分析表中的产生式 if(p.rule[0] == NULL) { // 如果预测分析表中没有产生式，则出错 error(); } printf("%d\t", index - 1); printStack(); printf("\t\t"); printInput(); printf("\t\t使用%s规约\n", p.rule); pop(); // 弹出栈顶符号 if(p.rule[2] != 'ε') { // 如果产生式不是ε，则将产生式的右侧符号压入栈中 for(int i = strlen(p.rule) - 1; i >= 2; i--) { push(p.rule[i]); } } } else { // 如果栈顶符号为终结符，则出错 error(); } } return 0;