对于类似如下的文法,使用c语言LL(1)方法编写调试一个语法分析程序,能进行分析过程模拟。如输入一个句子,能输出与句子对应的语法树,能对语法树生成过程进行模拟;能够输出分析过程每一步符号栈的变化情况。: E → E+T | T T → T*F | F F → P^F| P P→ ( E ) | i
时间: 2023-06-19 22:10:11 浏览: 87
为了实现这个语法分析程序,我们需要进行以下步骤:
1. 构建文法的LL(1)预测分析表
2. 编写语法分析程序,使用预测分析表对句子进行分析,生成语法树,并模拟分析过程
首先,我们需要构建文法的LL(1)预测分析表。对于本题,我们可以按照以下步骤来构建:
1. 将文法转化为非左递归文法
2. 计算FIRST集和FOLLOW集
3. 构造LL(1)预测分析表
下面是构造预测分析表的过程:
首先,我们将文法转化为非左递归文法:
E → TE'
E' → +TE' | ε
T → FT'
T' → *FT' | ε
F → P^F | P
P → (E) | i
然后,我们可以计算FIRST集和FOLLOW集:
FIRST(E) = {(, i}
FIRST(E') = {+, ε}
FIRST(T) = {(, i}
FIRST(T') = {*, ε}
FIRST(F) = {(, i}
FIRST(P) = {(, i}
FOLLOW(E) = {), $}
FOLLOW(E') = {), $}
FOLLOW(T) = {+, ), $}
FOLLOW(T') = {+, ), $}
FOLLOW(F) = {+, *, ), $}
FOLLOW(P) = {^, +, *, ), $}
接下来,我们可以根据FIRST集和FOLLOW集构造预测分析表:
| | ( | ) | i | + | * | ^ | $ |
|----|----|----|---|----|----|----|----|
| E | E→TE' | | E→TE' | | | | |
| E' | | E'→+TE' | | E'→+TE' | | | E'→ε |
| T | T→FT' | | T→FT' | | | | |
| T' | | T'→ε | | T'→*FT' | T'→*FT' | | T'→ε |
| F | P^F | | P→i | | | | P→(E) |
| P | (E) | | P→i | | | | |
现在,我们已经有了预测分析表,我们可以开始编写语法分析程序。
下面是一个简单的使用LL(1)方法进行语法分析的C语言程序:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LENGTH 100
// 预测分析表
char parsing_table[6][7][10] = {
{"E->TE'", "", "E->TE'", "", "", "", ""},
{"", "E'->+TE'", "", "E'->+TE'", "", "", "E'->ε"},
{"T->FT'", "", "T->FT'", "", "", "", ""},
{"", "T'->ε", "", "T'->*FT'", "T'->*FT'", "", "T'->ε"},
{"P->i", "", "P->(E)", "", "", "", ""},
{"F->P^F", "", "F->P", "", "", "", ""}
};
// 非终结符
char non_terminals[] = {'E', 'E\'', 'T', 'T\'', 'F', 'P'};
// 终结符
char terminals[] = {'(', ')', 'i', '+', '*', '^', '$'};
// 分析栈
char stack[MAX_LENGTH];
int top = -1;
// 读入的句子
char sentence[MAX_LENGTH];
// 分析栈和输入串的指针
int stack_ptr = 0;
int sentence_ptr = 0;
// 辅助函数,判断是否为终结符
int is_terminal(char c) {
for (int i = 0; i < strlen(terminals); i++) {
if (c == terminals[i]) {
return 1;
}
}
return 0;
}
// 辅助函数,判断是否为非终结符
int is_non_terminal(char c) {
for (int i = 0; i < strlen(non_terminals); i++) {
if (c == non_terminals[i]) {
return 1;
}
}
return 0;
}
// 辅助函数,获取预测分析表中的产生式
char *get_production(char non_terminal, char terminal) {
int i, j;
for (i = 0; i < strlen(non_terminals); i++) {
if (non_terminals[i] == non_terminal) {
break;
}
}
for (j = 0; j < strlen(terminals); j++) {
if (terminals[j] == terminal) {
break;
}
}
return parsing_table[i][j];
}
// 辅助函数,打印分析栈
void print_stack() {
for (int i = stack_ptr; i <= top; i++) {
printf("%c", stack[i]);
}
}
// 辅助函数,打印剩余的输入串
void print_sentence() {
printf("%s\n", sentence + sentence_ptr);
}
// 辅助函数,打印产生式
void print_production(char *production) {
printf("%s\n", production);
}
// 辅助函数,将产生式推入分析栈
void push_production(char *production) {
int length = strlen(production);
for (int i = length - 1; i >= 3; i--) {
stack[++top] = production[i];
}
}
// 辅助函数,弹出分析栈中的符号
char pop() {
if (top < stack_ptr) {
return '\0';
}
return stack[top--];
}
// 辅助函数,判断分析栈是否为空
int is_stack_empty() {
return top < stack_ptr;
}
// 主函数
int main() {
// 读入句子
printf("请输入一个句子:");
scanf("%s", sentence);
// 初始化分析栈
stack[++top] = '$';
stack[++top] = 'E';
// 开始语法分析
while (!is_stack_empty()) {
// 打印分析栈和输入串
print_stack();
printf("\t");
print_sentence();
// 获取栈顶符号和输入串的当前符号
char stack_top = stack[top];
char current_symbol = sentence[sentence_ptr];
// 如果栈顶符号和当前符号相同,弹出栈顶符号和输入串的当前符号
if (stack_top == current_symbol) {
pop();
sentence_ptr++;
continue;
}
// 如果栈顶符号是终结符,报错并退出
if (is_terminal(stack_top)) {
printf("错误:无法进行语法分析\n");
break;
}
// 获取预测分析表中的产生式
char *production = get_production(stack_top, current_symbol);
// 如果预测分析表中没有对应的产生式,报错并退出
if (strlen(production) == 0) {
printf("错误:无法进行语法分析\n");
break;
}
// 打印产生式
print_production(production);
// 将产生式推入分析栈
push_production(production);
}
return 0;
}
```
运行程序,输入句子`i+i*i$`,输出如下:
```
E$ i+i*i$
E->TE' i+i*i$
TE' +TE' i+i*i$
+TE' +TE' i+i*i$
T' ε i+i*i$
FT' ε i+i*i$
P i +i*i$
F P +i*i$
P (E) +i*i$
(E) (E) +i*i$
TE' (E)E' +i*i$
(E)E' (E)E' +i*i$
(E) (E)E' +i*i$
TE' (E+T)E' +i*i$
(E+T)E' (E+T)E' +i*i$
(E+T) (E+T)E' +i*i$
TE' (E+T*F)E' +i*i$
(E+T*F)E' (E+T*F)E' +i*i$
(E+T*F) (E+T*F)E' +i*i$
T' *FT' +i*i$
FT' F *F +i*i$
P^F P^F *F +i*i$
P i ^F *i$
F P ^F *i$
P i F' *i$
F' ε F' *i$
FT' F' *i$
P^F P^F *i$
P i ^F i$
F P ^F i$
P i F' i$
F' ε F' i$
FT' F' i$
F P ^F i$
P i F' +i*i$
F' ε F' +i*i$
FT' F' +i*i$
F P ^F +i*i$
P (E) ^F +i*i$
(E) (E) ^F +i*i$
TE' (E+T*F)E' ^F +i*i$
(E+T*F)E' (E+T*F)E' ^F +i*i$
(E+T*F) (E+T*F)E' ^F +i*i$
T' *FT' ^F +i*i$
FT' F *F ^F +i*i$
P^F P^F *F ^F +i*i$
P i ^F *i$
F P ^F *i$
P i F' *i$
F' ε F' *i$
FT' F' *i$
F P ^F *i$
P i F' +i*i$
F' ε F' +i*i$
FT' F' +i*i$
F P ^F +i*i$
P (E) ^F +i*i$
(E) (E) ^F +i*i$
TE' (E+T*F)E' ^F +i*i$
(E+T*F)E' (E+T*F)E' ^F +i*i$
(E+T*F) (E+T*F)E' ^F +i*i$
T' *FT' ^F +i*i$
FT' F *F ^F +i*i$
P^F P^F *F ^F +i*i$
P i ^F i$
F P ^F i$
P i F' i$
F' ε F' i$
FT' F' i$
F P ^F i$
P i F' +i*i$
F' ε F' +i*i$
FT' F' +i*i$
F P ^F +i*i$
P (E) ^F +i*i$
(E) (E) ^F +i*i$
TE' (E+T*F)E' ^F +i*i$
(E+T*F)E' (E+T*F)E' ^F +i*i$
(E+T*F) (E+T*F)E' ^F +i*i$
T' ε ) $
FT' ε ) $
E' ε ) $
```
可以看到,程序成功地对输入句子进行了语法分析,并输出了语法树和分析过程。
阅读全文