用c根据某一文法编制调试LL(1)分析程序,以便对任意输入的符号串进行分析。
时间: 2024-06-08 19:12:23 浏览: 126
LL(1)语法分析 任意输入一个文法符号串,并判断它是否为文法的一个句子
5星 · 资源好评率100%
LL(1)分析器的编写需要以下步骤:
1. 设计文法并计算FIRST和FOLLOW集合。
2. 构造LL(1)预测分析表。
3. 编写程序实现LL(1)分析器。
以下是一个例子,假设我们有一个文法:
```
S → aAc
A → b | ε
```
计算FIRST和FOLLOW集合:
```
FIRST(S) = {a}
FIRST(A) = {b, ε}
FOLLOW(S) = {$}
FOLLOW(A) = {c}
```
构造LL(1)预测分析表:
| | a | b | c | $ |
| ---- | ---- | ---- | ---- | ---- |
| S | S → aAc | | | |
| A | | A → b | | A → ε |
编写LL(1)分析器程序:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_LEN 100
typedef enum {
A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z,
EPSILON, END, ERROR
} token_type;
typedef struct {
token_type type;
char value[MAX_LEN];
} token;
token_type table[5][4] = {
/* a b c $ */
/* S */ { A, ERROR, ERROR, ERROR },
/* A */ { ERROR, B, ERROR, EPSILON },
/* B */ { EPSILON, EPSILON, EPSILON, EPSILON },
/* C */ { ERROR, ERROR, D, ERROR },
/* D */ { ERROR, ERROR, ERROR, EPSILON }
};
token_type get_type(char c) {
switch (c) {
case 'a': return A;
case 'b': return B;
case 'c': return C;
case '$': return END;
default: return ERROR;
}
}
token get_token(char* str) {
token t;
int i = 0;
while (islower(str[i])) {
t.value[i] = str[i];
i++;
}
t.value[i] = '\0';
t.type = get_type(str[i]);
return t;
}
void parse(token_type stack[], int top, token t) {
token_type x = stack[top];
if (x == END) {
printf("Accepted.\n");
return;
}
if (x == EPSILON) {
top--;
x = stack[top];
}
if (x == t.type) {
top--;
parse(stack, top, t);
} else if (table[x][t.type] == ERROR) {
printf("Error: unexpected token %s\n", t.value);
return;
} else {
int i;
token_type row = x;
token_type col = t.type;
token_type* prod = &table[row][col];
for (i = 0; i < top; i++) {
printf("%c", stack[i] + 'A');
}
printf("\t %s \t %c\n", t.value, *prod + 'A');
top--;
for (i = strlen(t.value) - 1; i >= 0; i--) {
stack[++top] = get_type(t.value[i]);
}
for (i = 3; i >= 0; i--) {
if (table[*prod][i] != EPSILON) {
stack[++top] = table[*prod][i];
}
}
parse(stack, top, t);
}
}
int main() {
char input[MAX_LEN];
printf("Enter input string: ");
scanf("%s", input);
int i, top = 0;
token_type stack[MAX_LEN];
stack[top++] = END;
stack[top++] = S;
for (i = strlen(input) - 1; i >= 0; i--) {
stack[top++] = get_type(input[i]);
}
parse(stack, top, (token){END, "$"});
return 0;
}
```
运行程序,输入符号串,程序会输出分析过程并判断是否被接受。
阅读全文