設計要求：對于任意輸入的一個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;
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 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("****分析失敗了****");
}
}
}
運作結果如下圖所示
運作結果
![LL1文法JAVA文法輸入_表達式電腦（LL1文法）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)