LL1文法_预测分析法_语法分析器

设计要求:对于任意输入的一个LL(1)文法,构造其预测分析表,并对指定输入串分析其是否为该文法的句子。
思路:首先实现集合FIRST(X)构造算法和集合FOLLOW(A)构造算法,再根据FIRST和FOLLOW集合构造出预测分析表,并对指定的句子打印出分析栈的分析过程,判断是否为该文法的句子。

  1. 求FIRST集的算法思想
    如果产生式右部第一个字符为终结符,则将其计入左部first集
    如果产生式右部第一个字符为非终结符
    ->求该非终结符的first集
    ->将该非终结符的非$first集计入左部的first集
    ->若存在$,则将指向产生式的指针右移
    ->若不存在$,则停止遍历该产生式,进入下一个产生式
    ->若已经到达产生式的最右部的非终结符,则将$加入左部的first集
    处理数组中重复的first集中的终结符
  2. 求FOLLOW集的算法思想
    对于文法G中每个非终结符A构造FOLLOW(A)的办法是,连续使用下面的规则,直到每个FOLLOW不在增大为止.
    (1) 对于文法的开始符号S,置#于FOLLOW(S)中;
    (2) 若A->aBb是一个产生式,则把FIRST(b){ε}加至FOLLOW(B)中;
    (3) 若A->aB是一个产生式,或A->aBb是一个产生式而b=>ε(即ε∈FIRST(b))则把FOLLOW(A)加至FOLLOW(B)中

  3. 生成预测分析表的算法思想
    构造分析表M的算法是:
    (1) 对文法G的每个产生式A->a执行第二步和第三步;
    (2) 对每个终结符a∈FIRST(a),把A->a加至M[A,a]中;
    (3) 若ε∈FIRST(a),则把任何b∈FOLLOW(A)把A->a加至M[A,b]中;
    (4) 把所有无定义的M[A,a]标上出错标志.

  4. 对符号串的分析过程
    预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号行事的,对于任何(X,a),总控程序
    每次都执行下述三种可能的动作之一;
    (1) 若X=a=”#”,则宣布分析成功,停止分析过程.
    (2) 若X=a≠”#”,则把X从STACK栈顶逐出,让a指向下一个输入符号.
    (3) 若X是一个非终结符,则查看分析表M,若M[A,a]中存放着关于X的一个产生式,那么,首先把X逐出STACK栈顶,然后
    把产生式的右部符号串按反序一一推进STACK栈(若右部符号为ε,则意味着不推什么东西进栈).在把产生式的右部
    符号推进栈的同时应做这个产生式相应得语义动作,若M[A,a]中存放着”出错标志”,则调用出错诊察程序ERROR.
    句子采用i\i+i*
    文法采用课本P69消除左递归后的4.2文法:

    1
    2
    3
    4
    5
    E->TE'
    E'->+TE'|ε
    T->FT'
    T'->*FT'|ε
    F->(E)|i

LL1_Deque.java源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
package com.LL1;
import java.util.ArrayDeque;
import java.util.Deque;
/**
* LL1文法分析器,已经构建好预测分析表,采用Deque实现
* Created by HongWeiPC on 2017/5/12.
*/
public class LL1_Deque {
//预测分析表
private String[][] analysisTable = new String[][]{
{"TE'", "", "", "TE'", "", ""},
{"", "+TE'", "", "", "ε", "ε"},
{"FT'", "", "", "FT'", "", ""},
{"", "ε", "*FT'", "", "ε", "ε"},
{"i", "", "", "(E)", "", ""}
};
//终结符
private String[] VT = new String[]{"i", "+", "*", "(", ")", "#"};
//非终结符
private String[] VN = new String[]{"E", "E'", "T", "T'", "F"};
//输入串strToken
private StringBuilder strToken = new StringBuilder("i*i+i");
//分析栈stack
private Deque<String> stack = new ArrayDeque<>();
//shuru1保存从输入串中读取的一个输入符号,当前符号
private String shuru1 = null;
//X中保存stack栈顶符号
private String X = null;
//flag标志预测分析是否成功
private boolean flag = true;
//记录输入串中当前字符的位置
private int cur = 0;
//记录步数
private int count = 0;
public static void main(String[] args) {
LL1_Deque ll1 = new LL1_Deque();
ll1.init();
ll1.totalControlProgram();
ll1.printf();
}
//初始化
private void init() {
strToken.append("#");
stack.push("#");
System.out.printf("%-8s %-18s %-17s %s\n", "步骤 ", "符号栈 ", "输入串 ", "所用产生式 ");
stack.push("E");
curCharacter();
System.out.printf("%-10d %-20s %-20s\n", count, stack.toString(), strToken.substring(cur, strToken.length()));
}
//读取当前栈顶符号
private void stackPeek() {
X = stack.peekFirst();
}
//返回输入串中当前位置的字母
private String curCharacter() {
shuru1 = String.valueOf(strToken.charAt(cur));
return shuru1;
}
//判断X是否是终结符
private boolean XisVT() {
for (int i = 0; i < (VT.length - 1); i++) {
if (VT[i].equals(X)) {
return true;
}
}
return false;
}
//查找X在非终结符中分析表中的横坐标
private String VNTI() {
int Ni = 0, Tj = 0;
for (int i = 0; i < VN.length; i++) {
if (VN[i].equals(X)) {
Ni = i;
}
}
for (int j = 0; j < VT.length; j++) {
if (VT[j].equals(shuru1)) {
Tj = j;
}
}
return analysisTable[Ni][Tj];
}
//判断M[A,a]={X->X1X2...Xk}
//把X1X2...Xk推进栈
//X1X2...Xk=ε,不推什么进栈
private boolean productionType() {
return VNTI() != "";
}
//推进stack栈
private void pushStack() {
stack.pop();
String M = VNTI();
String ch;
//处理TE' FT' *FT'特殊情况
switch (M) {
case "TE'":
stack.push("E'");
stack.push("T");
break;
case "FT'":
stack.push("T'");
stack.push("F");
break;
case "*FT'":
stack.push("T'");
stack.push("F");
stack.push("*");
break;
case "+TE'":
stack.push("E'");
stack.push("T");
stack.push("+");
break;
default:
for (int i = (M.length() - 1); i >= 0; i--) {
ch = String.valueOf(M.charAt(i));
stack.push(ch);
}
break;
}
System.out.printf("%-10d %-20s %-20s %s->%s\n", (++count), stack.toString(), strToken.substring(cur, strToken.length()), X, M);
}
//总控程序
private void totalControlProgram() {
while (flag) {
stackPeek(); //读取当前栈顶符号 令X=栈顶符号
if (XisVT()) {
if (X.equals(shuru1)) {
cur++;
shuru1 = curCharacter();
stack.pop();
System.out.printf("%-10d %-20s %-20s \n", (++count), stack.toString(), strToken.substring(cur, strToken.length()));
} else {
ERROR();
}
} else if (X.equals("#")) {
if (X.equals(shuru1)) {
flag = false;
} else {
ERROR();
}
} else if (productionType()) {
if (VNTI().equals("")) {
ERROR();
} else if (VNTI().equals("ε")) {
stack.pop();
System.out.printf("%-10d %-20s %-20s %s->%s\n", (++count), stack.toString(), strToken.substring(cur, strToken.length()), X, VNTI());
} else {
pushStack();
}
} else {
ERROR();
}
}
}
//出现错误
private void ERROR() {
System.out.println("输入串出现错误,无法进行分析");
System.exit(0);
}
//打印存储分析表
private void printf() {
if (!flag) {
System.out.println("****分析成功啦!****");
} else {
System.out.println("****分析失败了****");
}
}
}

运行结果如下图所示
运行结果

Hongwei wechat
欢迎大家关注微信公众号:ghw1996