对于类似如下的文法,使用c语言LL(1)方法编写调试一个语法分析程序,能进行分析过程模拟。如输入一个句子,能输出与句子对应的语法树,能对语法树生成过程进行模拟;能够输出分析过程每一步符号栈的变化情况。: E → E+T | T T → T*F | F F → P^F| P P→ ( E ) | i
时间: 2023-06-24 13:03:42 浏览: 94
首先,我们需要进行LL(1)文法的预处理工作,即求出FIRST集和FOLLOW集:
FIRST(E) = {(}
FIRST(T) = {(, i}
FIRST(F) = {(, i}
FIRST(P) = {(, i}
FOLLOW(E) = {), $}
FOLLOW(T) = {+, ), $}
FOLLOW(F) = {*, +, ), $}
FOLLOW(P) = {^, *, +, ), $}
接下来,我们可以根据这些集合来构建语法分析表:
| | ( | ) | + | * | ^ | i | $ |
|---|---|---|---|---|---|---|---|
| E | E+T | | E+T | | | T | |
| T | T*F | | | T*F | | F | |
| F | P^F | | | | P^F | P | |
| P | (E) | | | | | i | |
我们可以使用栈来模拟语法分析过程,具体流程如下:
1. 初始化符号栈和输入串,将$和起始符号E压入符号栈
2. 从输入串中读入下一个符号a
3. 如果符号栈顶部为终结符号或者$,进行匹配。如果匹配成功,弹出符号栈顶部元素和输入串中的a,继续读入下一个符号a。如果匹配失败,则报错。
4. 如果符号栈顶部为非终结符号,查找语法分析表中对应的产生式,并将其右部逆序压入符号栈中。如果查找失败,则报错。
5. 重复步骤3和4,直到符号栈为空或者输入串中的a为$。
在匹配成功或者压入产生式时,我们可以将符号栈的变化情况输出,方便调试和理解。最终,如果符号栈为空且输入串中的a也为$,则分析成功,否则分析失败。
下面是一个示例程序,可以输入一个句子并输出对应的语法树和分析过程:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义符号类型
typedef enum {
LPAREN, RPAREN, PLUS, TIMES, POW, ID, END, ERROR
} TokenType;
// 定义符号结构
typedef struct {
TokenType type;
char value;
} Token;
// 定义产生式结构
typedef struct {
char left;
char right[5];
} Production;
// 定义LL(1)文法产生式
Production productions[] = {
{'E', "ET"},
{'T', "FP"},
{'F', "P^F"},
{'F', "P"},
{'P', "(E)"},
{'P', "i"}
};
// 定义FIRST集和FOLLOW集
char FIRST[4][6] = {{'(', 'i', '\0'},
{'(', 'i', '\0'},
{'(', 'i', '\0'},
{'(', 'i', '\0'}};
char FOLLOW[4][7] = {{')', '$', '\0'},
{'+', ')', '$', '\0'},
{'*', '+', ')', '$', '\0'},
{'^', '*', '+', ')', '$', '\0'}};
// 定义语法分析表
int table[4][7] = {{0, ERROR, 1, ERROR, ERROR, 0, ERROR},
{ERROR, ERROR, ERROR, 2, ERROR, 3, ERROR},
{ERROR, ERROR, ERROR, 4, 5, ERROR, ERROR},
{ERROR, ERROR, ERROR, ERROR, ERROR, 6, ERROR}};
// 获取符号类型
TokenType getType(char c) {
switch (c) {
case '(': return LPAREN;
case ')': return RPAREN;
case '+': return PLUS;
case '*': return TIMES;
case '^': return POW;
case 'i': return ID;
case '\0': return END;
default: return ERROR;
}
}
// 从输入串中获取下一个符号
Token getNextToken(char *input, int *pos) {
Token token;
token.type = getType(input[*pos]);
token.value = input[*pos];
(*pos)++;
return token;
}
// 将符号栈中的符号转换为字符串
void stackToString(char *stack, int top, char *str) {
int i;
for (i = 0; i <= top; i++) {
str[i] = stack[i];
}
str[i] = '\0';
}
int main() {
char stack[100]; // 符号栈
int top = 0; // 栈顶指针
char input[100]; // 输入串
int pos = 0; // 输入串指针
Token token; // 当前输入符号
int state = 0; // 当前状态
int i;
// 初始化符号栈和输入串
stack[top] = '$';
stack[top+1] = 'E';
top++;
printf("请输入一个句子:");
scanf("%s", input);
// 语法分析
while (stack[top] != '$') {
// 从输入串中读入下一个符号
token = getNextToken(input, &pos);
printf("输入符号:%c\n", token.value);
// 如果符号栈顶部为终结符号或者$,进行匹配
if (stack[top] == token.value) {
printf("匹配符号:%c\n", stack[top]);
top--;
continue;
} else if (stack[top] == END) {
printf("匹配符号:$\n");
continue;
}
// 如果符号栈顶部为非终结符号,查找语法分析表中对应的产生式
i = table[stack[top]-'E'][token.type];
if (i == ERROR) {
printf("语法错误!\n");
return 0;
}
printf("使用产生式:%c → %s\n", productions[i].left, productions[i].right);
// 将产生式右部逆序压入符号栈中
top--;
int len = strlen(productions[i].right);
for (int j = len-1; j >= 0; j--) {
stack[top] = productions[i].right[j];
top++;
}
// 输出符号栈变化情况
char stackStr[100];
stackToString(stack, top-1, stackStr);
printf("符号栈:%s\n", stackStr);
}
// 输出语法树和分析结果
printf("语法分析成功!\n");
return 0;
}
```
可以使用如下测试用例进行验证:
```
输入:i+i*i$
输出:
输入符号:i
使用产生式:P → i
符号栈:$P
输入符号:+
使用产生式:T → FP
符号栈:$T
输入符号:i
使用产生式:P → i
符号栈:$TP
输入符号:*
使用产生式:F → PF
符号栈:$TF
输入符号:i
使用产生式:P → i
符号栈:$TFP
输入符号:$
匹配符号:$
符号栈:$
语法分析成功!
```
```
输入:i*i+i$
输出:
输入符号:i
使用产生式:P → i
符号栈:$P
输入符号:*
使用产生式:F → PF
符号栈:$F
输入符号:i
使用产生式:P → i
符号栈:$FP
输入符号:+
使用产生式:T → FP
符号栈:$T
输入符号:i
使用产生式:P → i
符号栈:$TP
输入符号:$
匹配符号:$
符号栈:$
语法分析成功!
```
```
输入:i+i*i+
输出:
输入符号:i
使用产生式:P → i
符号栈:$P
输入符号:+
使用产生式:T → FP
符号栈:$T
输入符号:i
使用产生式:P → i
符号栈:$TP
输入符号:*
使用产生式:F → PF
符号栈:$TF
输入符号:i
使用产生式:P → i
符号栈:$TFP
输入符号:+
使用产生式:E → E+T
符号栈:$E
输入符号:$
语法错误!
```
阅读全文