设计要求：对于任意输入的一个LL(1)文法，构造其预测分析表，并对指定输入串分析其是否为该文法的句子。
思路：首先实现集合FIRST(X)构造算法和集合FOLLOW(A)构造算法，再根据FIRST和FOLLOW集合构造出预测分析表，并对指定的句子打印出分析栈的分析过程，判断是否为该文法的句子。
求FIRST集的算法思想
如果产生式右部第一个字符为终结符，则将其计入左部first集
如果产生式右部第一个字符为非终结符
->求该非终结符的first集
->将该非终结符的非$first集计入左部的first集
->若存在$，则将指向产生式的指针右移
->若不存在$，则停止遍历该产生式，进入下一个产生式
->若已经到达产生式的最右部的非终结符，则将$加入左部的first集
处理数组中重复的first集中的终结符求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)中生成预测分析表的算法思想
构造分析表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]标上出错标志.对符号串的分析过程
预测分析程序的总控程序在任何时候都是按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文法：
E->TE'
E'->+TE'|ε
T->FT'
T'->*FT'|ε
F->(E)|i
LL1_Deque.java源码如下：
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("****分析失败了****");
}
}
}
运行结果如下图所示
