一远豺、 實(shí)驗(yàn)?zāi)康?/h2>
通過完成預(yù)測(cè)分析法的語法分析程序，了解預(yù)測(cè)分析法和遞歸子程序法的區(qū)別和聯(lián)系坞嘀。使學(xué)生了解語法分析的功能躯护，掌握語法分析程序設(shè)計(jì)的原理和構(gòu)造方法，訓(xùn)練學(xué)生掌握開發(fā)應(yīng)用程序的基本方法丽涩。有利于提高學(xué)生的專業(yè)素質(zhì)棺滞，為培養(yǎng)適應(yīng)社會(huì)多方面需要的能力。
二矢渊、 實(shí)驗(yàn)內(nèi)容
根據(jù)某一文法編制調(diào)試 LL(1)分析程序继准，以便對(duì)任意輸入的符號(hào)串進(jìn)行分析。
構(gòu)造預(yù)測(cè)分析表矮男，并利用分析表和一個(gè)棧來實(shí)現(xiàn)對(duì)上述程序設(shè)計(jì)語言的分析程序移必。
分析法的功能是利用LL(1)控制程序根據(jù)顯示棧棧頂內(nèi)容、向前看符號(hào)以及LL(1)分析表昂灵，對(duì)輸入符號(hào)串自上而下的分析過程避凝。
三舞萄、 LL（1）分析法實(shí)驗(yàn)設(shè)計(jì)思想及算法
對(duì)文法的句子進(jìn)行不含回溯的自上向下語法分析的充分必要條件是：
（1）文法不含左遞歸眨补；
（2）對(duì)于文法中的每一個(gè)非終結(jié)符的各個(gè)產(chǎn)生式的候選首符集兩兩不相交管削，即，若
則
（3）對(duì)于文法中的每一個(gè)非終結(jié)符
將滿足上述條件的文法稱為L(zhǎng)L(1)文法。
一個(gè)LL(1)文法一定不是左遞歸的甘晤。因此要進(jìn)行自下而上的LL(1)分析含潘，那么首先要消除文法的左遞歸性。如果一個(gè)文法不含回路（is not cyclic线婚，即不含有形如
消除左遞歸的算法：
（1）把文法
（3）化簡(jiǎn)由（2）所得的文法游沿，即去除那些從開始符號(hào)出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則饰抒。
同時(shí)，自上而下的LL(1)分析要求文法中的每一個(gè)非終結(jié)符的各個(gè)產(chǎn)生式的候選首符集兩兩不相交诀黍。當(dāng)兩者相交時(shí)袋坑，需要提取左公因子。算法如下：
提取左公因子算法：
對(duì)文法的每一個(gè)非終結(jié)符眯勾，執(zhí)行下面的算法枣宫，直到文法中的每一個(gè)非終結(jié)符的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。
假定關(guān)于某個(gè)非終結(jié)符
將其改寫成
First集合構(gòu)造：
對(duì)每一文法符號(hào)
- 若
歇拆，則
。
- 若
范咨，且有產(chǎn)生式
故觅，則把
加入到
中；若
也是一條產(chǎn)生式渠啊，則把
也加到
- 若
是一個(gè)產(chǎn)生式，且
替蛉，則把
中的所有非ε-元素都加到
是一個(gè)產(chǎn)生式拄氯，
都是非終結(jié)符，而且它浅，對(duì)于任何
,
译柏，
都含有
)，則把
，則把
現(xiàn)在胯府，我們能夠?qū)ξ姆?img class="math-inline" src="https://math.jianshu.com/math?formula=G" alt="G" mathimg="1">的任何符號(hào)串構(gòu)造集合
。首先恨胚，置
沦寂；若對(duì)于任何
俐末，則把
加至
试幽，則把
Follow集合構(gòu)造：
對(duì)于文法的每個(gè)非終結(jié)符
構(gòu)造
的算法是匿值，連續(xù)使用下面的規(guī)則灿巧，直至每個(gè)
不再增大為止：
- 對(duì)于文法的開始符號(hào)
，置#于
中僚碎；
- 若
是一個(gè)產(chǎn)生式猴娩，則把
加至
中；
- 若
(即
)卷中，則把
加至
預(yù)測(cè)分析表構(gòu)造：
對(duì)于文法渊抽，構(gòu)造分析表
的算法是：
1.對(duì)文法執(zhí)行2和3蟆豫；
2.對(duì)于每個(gè)終結(jié)符，把
中懒闷；
3.若十减，則對(duì)于任何的
把
中；
4.把所有無定義的
一個(gè)文法
四玩焰、 詳細(xì)的算法描述
- First集合構(gòu)造
對(duì)于規(guī)則3由驹，具有以下規(guī)律：
規(guī)則3的三條規(guī)則(3-1, 3-2, 3-3)的成立條件是以前一條規(guī)則成立為基礎(chǔ)的。對(duì)于規(guī)則3-2昔园，若規(guī)則3-1不成立蔓榄，也就是并炮，
不是非終結(jié)符，顯然
甥郑，
不會(huì)是非終結(jié)符逃魄，也就是3-2不成立。對(duì)于規(guī)則3-2內(nèi)部壹若，若
嗅钻，若
不是非終結(jié)符皂冰，那么對(duì)于
來說店展，前面的符號(hào)都不是非終結(jié)符，也就是規(guī)則3-2不成立秃流。同理可得赂蕴，規(guī)則3-2是規(guī)則3-3的前提條件。
以下是上述算法的略微形式化的描述：
/* 規(guī)則1 */
1. for-each 文法的終結(jié)符X
將First(X)置為{X}
/* 規(guī)則2 */
2. for-each文法的非終結(jié)符X
如果X含有X->a舶胀，a為非終結(jié)符概说，那么將a加入到First(X)。
/* 連續(xù)使用規(guī)則3嚣伐，直至每個(gè)文法符號(hào)的First集不再增大為止 */
3. 設(shè)置標(biāo)記modified糖赔，查看是否上一次First集有增大。
4. while modified do
還原modified
for-each 文法的非終結(jié)符X：
Lable1:
for-each文法的產(chǎn)生式：
/* 規(guī)則3-1 */
if 文法的產(chǎn)生式首位不是非終結(jié)符 continue
else 文法產(chǎn)生式為X->Y…轩端，將First(Y)的非ε元素加到Fisrt(X)中放典，并檢查First(X)的長(zhǎng)度是否有變化，有變化基茵，置位modified
/* 規(guī)則3-2 */
for-each 產(chǎn)生式右部的文法符號(hào)Y：
if Y不是非終結(jié)符 continue Lable1
else 將First(Y)的非ε元素加到Fisrt(X)中奋构，并檢查First(X)的長(zhǎng)度是否有變化，有變化拱层，置位modified
/* 規(guī)則3-3 */
將ε加到Fisrt(X)中弥臼，并檢查First(X)的長(zhǎng)度是否有變化，有變化根灯，置位modified
5. 算法結(jié)束
- 將一個(gè)普通的文法轉(zhuǎn)換為一個(gè)LL(1)文法
大致分為兩大部分径缅，第一大部分是消除左遞歸，第二大部分是提取左公因子烙肺。下面給出這個(gè)方法的略微形式化的描述：
1. 將非終結(jié)符進(jìn)行排序纳猪，儲(chǔ)存在tempVn中
2. for-each P_i in tempVn:
for-each j in range(1, i-1):
for-each P_i的產(chǎn)生式Pro:
if Pro以P_j開頭
把P_j的所有規(guī)則帶入到P_i->P_jγ中，并更新產(chǎn)生式Pro
改寫P->Pα_1|Pα_2|…|α_m|β_1|β_2|…|β_n為P->β_1P'|β_2P'|...|β_nP'茬高，P'->α_1P'|α_2P'|…|α_mP'|ε兆旬。
3. 2中得到的文法可能含有多余的式子。下面通過新的Vn來替換未達(dá)到的文法怎栽。
do
置修改表示flag為false
for-each 2中得到的產(chǎn)生式：
將產(chǎn)生式中的所有非終結(jié)符加入到新的Vn中
若Vn大小發(fā)生變化丽猬，置flag為true
while flag
將Vn中的每個(gè)出現(xiàn)過的非終結(jié)符對(duì)應(yīng)的產(chǎn)生式加入到新的產(chǎn)生式集合中
/* 以上步驟已經(jīng)消除左遞歸宿饱，下面進(jìn)行提左因子 */
4.
do
置左因子標(biāo)志flag為false
for-each 文法的非終結(jié)符；
for-each 非終結(jié)符為左部的產(chǎn)生式：
以產(chǎn)生式右部的第一字母為鍵脚祟，計(jì)算以該字母為第一字母的產(chǎn)生式有多少個(gè)
根據(jù)結(jié)果置位flag
if 以該字母為第一字母的產(chǎn)生式不只有他自己：
/* 有左因子 */
將A->δβ_1|δβ_2|…|δβ_n|γ_1|γ_2|…|γ_m谬以，改寫為A->δA'|γ_1|γ_2|…|γ_m，A'->β_1|β_2|…|β_n由桌。
while flag
5. 判斷得到的文法的預(yù)測(cè)分析表是否含有多重入口來判斷是否為L(zhǎng)L(1)文法为黎，從而得到結(jié)果。
- 預(yù)測(cè)分析的總控程序
begin
把#行您，文法的開始符號(hào)推入棧S
把第一個(gè)輸入符號(hào)讀進(jìn)a
標(biāo)志flag置為true
while true do
begin
把棧S的棧頂符號(hào)推出去放到X中
if X為非終結(jié)符
if X == a 把下一個(gè)輸入符號(hào)讀進(jìn)a
else error
else if X是#
if X == a 置flag為false
else error
else if M[A, a] = {X->產(chǎn)生式右部}
if 產(chǎn)生式右部不是ε
將產(chǎn)生式右部逆序推入棧S
else error
end of while
stop
end
五铭乾、 源代碼
僅給出核心部分
(1) GrammerSymbol.java
package exp2.grammer.symbol;
import exp2.grammer.exception.GrammerException;
import java.util.Objects;
import static java.lang.Character.isUpperCase;
/**
* 文法符號(hào)
*
* @version 2020-06-01
*/
public final class GrammerSymbol implements Comparable<GrammerSymbol> {
/* 文法符號(hào)儲(chǔ)存在String中，可能的長(zhǎng)度為1或者2 */
private final String symbol;
/* 空字對(duì)應(yīng)的符號(hào) */
public final static GrammerSymbol GS_EPSILON = new GrammerSymbol("\u03b5");
/**
* 從字符構(gòu)造文法符號(hào)
*
* @param symbol 文法符號(hào)對(duì)應(yīng)的字符
*/
public GrammerSymbol(char symbol) {
this.symbol = String.valueOf(symbol);
}
/**
* 從字符串構(gòu)造文法符號(hào)
*
* @param symbol 文法符號(hào)對(duì)應(yīng)的字符串
*/
public GrammerSymbol(String symbol) {
if (symbol == null) throw new NullPointerException();
if (symbol.length() > 2) throw new GrammerException("文法符的長(zhǎng)度最大為2娃循，而實(shí)際為" + symbol.length());
if (symbol.length() == 2 && (!isUpperCase(symbol.charAt(0)) || symbol.charAt(1) != '\''))
throw new GrammerException("非終結(jié)符必須是大寫字母炕檩，或者是帶有'的大寫字母，而實(shí)際為" + symbol);
this.symbol = symbol;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || GrammerSymbol.class != o.getClass()) return false;
GrammerSymbol that = (GrammerSymbol) o;
return Objects.equals(symbol, that.symbol);
}
@Override
public int hashCode() {
return Objects.hash(symbol);
}
@Override
public String toString() {
return symbol;
}
@Override
public int compareTo(GrammerSymbol o) {
return this.symbol.compareTo(o.symbol);
}
/**
* 判斷一個(gè)文法符號(hào)是不是非終結(jié)符捌斧，非終結(jié)符必須為大寫字母笛质，或者是帶有'的大寫字母
*
* @param gs 文法符號(hào)
* @return 若是非終結(jié)符，返回true捞蚂，否則返回false
*/
public static boolean isNonterminal(GrammerSymbol gs) {
return isUpperCase(gs.symbol.charAt(0));
}
/**
* 判斷一個(gè)文法符號(hào)是不是終結(jié)符妇押，終結(jié)符應(yīng)該為終結(jié)符是除大寫字母和大寫字母聯(lián)合'外的其他非空可見字符
*
* @param gs 文法符號(hào)
* @return 若是非終結(jié)符，返回true姓迅，否則返回false
*/
public static boolean isTerminal(GrammerSymbol gs) {
return !isNonterminal(gs);
}
}
(2) GrammerSymbols.java
package exp2.grammer.symbol;
import java.util.*;
import static java.lang.Character.isUpperCase;
/**
* 文法符號(hào)序列
*
* @version 2020-06-01
*/
public final class GrammerSymbols implements Comparable<GrammerSymbols>, Iterable<GrammerSymbol> {
/* 儲(chǔ)存文法符號(hào)序列 */
private final List<GrammerSymbol> value;
/* 文法符號(hào)序列對(duì)應(yīng)的字符串 */
private final String valueString;
/**
* 從文法符號(hào)數(shù)組構(gòu)造文法符號(hào)序列
*
* @param value 文法符號(hào)數(shù)組
*/
public GrammerSymbols(GrammerSymbol[] value) {
this.value = Collections.unmodifiableList(Arrays.asList(value));
StringBuilder sb = new StringBuilder();
for (GrammerSymbol gs : this.value)
sb.append(gs.toString());
this.valueString = sb.toString();
}
/**
* 從文法符號(hào)列表構(gòu)造文法符號(hào)序列
*
* @param value 文法符號(hào)列表
*/
public GrammerSymbols(List<GrammerSymbol> value) {
this.value = Collections.unmodifiableList(value);
StringBuilder sb = new StringBuilder();
for (GrammerSymbol gs : this.value)
sb.append(gs.toString());
this.valueString = sb.toString();
}
/**
* 從文法符號(hào)序列字符串構(gòu)造文法序列
*
* @param string 文法符號(hào)序列字符串
*/
public GrammerSymbols(String string) {
List<GrammerSymbol> value = new ArrayList<>();
int last = string.length() - 1;
for (int i = 0; i < last; ++i) {
char c = string.charAt(i);
if (isUpperCase(c)) {
if (string.charAt(i + 1) == '\'') {
value.add(new GrammerSymbol(c + "'"));
i += 1;
continue;
}
}
value.add(new GrammerSymbol(c));
}
if (string.charAt(last) != '\'') value.add(new GrammerSymbol(string.charAt(last)));
this.value = Collections.unmodifiableList(value);
this.valueString = string;
}
/**
* 返回序列的長(zhǎng)度
*
* @return 序列的長(zhǎng)度
*/
public int length() {
return value.size();
}
/**
* 取索引為index的文法符號(hào)
*
* @param index 索引
* @return 對(duì)應(yīng)的文法符號(hào)
*/
public GrammerSymbol get(int index) {
try{
return value.get(index);
} catch (IndexOutOfBoundsException e) {
return null;
}
}
/**
* 根據(jù)給定的文法符號(hào)敲霍，匹配對(duì)應(yīng)的索引
*
* @param gs 文法符號(hào)
* @return 如果找到，返回index队贱，否則返回-1
*/
public int indexOf(GrammerSymbol gs) {
return value.indexOf(gs);
}
/**
* 根據(jù)給定的文法符號(hào)序列色冀，匹配對(duì)應(yīng)的索引首
*
* @param gs 文法符號(hào)序列
* @return 如果找到，返回index柱嫌，否則返回-1
*/
public int indexOf(GrammerSymbols gs) {
return indexOf(value, value.size(),
gs.value, gs.value.size(), 0);
}
/**
* 根據(jù)給定的文法符號(hào)序列锋恬，匹配指定索引及以后的對(duì)應(yīng)索引首
*
* @param gs 文法符號(hào)序列
* @param fromIndex 指定的開始索引
* @return 如果找到，返回index编丘，否則返回-1
*/
public int indexOf(GrammerSymbols gs, int fromIndex) {
return indexOf(value, value.size(),
gs.value, gs.value.size(), fromIndex);
}
/**
* 根據(jù)給定的兩個(gè)文法符號(hào)序列与学，匹配指定索引及以后的對(duì)應(yīng)索引首
*
* @param source 原序列
* @param sourceCount 原序列的長(zhǎng)度
* @param target 目標(biāo)序列
* @param targetCount 目標(biāo)序列的長(zhǎng)度
* @param fromIndex 指定的開始索引
* @return 如果找到，返回index嘉抓，否則返回-1
*/
static int indexOf(List<GrammerSymbol> source, int sourceCount,
List<GrammerSymbol> target, int targetCount,
int fromIndex) {
if (fromIndex >= sourceCount)
return (targetCount == 0 ? sourceCount : -1);
if (fromIndex < 0)
fromIndex = 0;
if (targetCount == 0)
return fromIndex;
GrammerSymbol first = target.get(0);
int max = (sourceCount - targetCount);
for (int i = fromIndex; i <= max; i++) {
/* 找到第一個(gè)文法符號(hào)匹配 */
if (!source.get(i).equals(first))
while (++i <= max && !source.get(i).equals(first));
/* 找到了第一個(gè)匹配索守，進(jìn)行查看后面是否匹配 */
if (i <= max) {
int j = i + 1;
int end = j + targetCount - 1;
for (int k = 1; j < end && source.get(j).equals(target.get(k)); j++, k++);
if (j == end)
/* 整個(gè)字符串匹配 */
return i;
}
}
return -1;
}
/**
* 根據(jù)給定的索引，返回對(duì)應(yīng)的子序列
*
* @param start 索引首
* @return sequence[start:]
*/
public GrammerSymbols subSequence(int start) {
return subSequence(start, value.size());
}
/**
* 根據(jù)給定的索引抑片，返回對(duì)應(yīng)的子序列
*
* @param start 索引首
* @param end 索引尾
* @return sequence[start:end)
*/
public GrammerSymbols subSequence(int start, int end) {
return new GrammerSymbols(value.subList(start, end));
}
@Override
public String toString() {
return valueString;
}
/**
* 返回序列中的所有非終結(jié)符號(hào)
*
* @return 所有非終結(jié)符號(hào)的集合
*/
public Set<GrammerSymbol> getVns() {
Set<GrammerSymbol> set = new TreeSet<>();
for (GrammerSymbol gs : value)
if (GrammerSymbol.isNonterminal(gs))
set.add(gs);
return set;
}
/**
* 返回序列中的所有終結(jié)符號(hào)
*
* @return 所有終結(jié)符號(hào)的集合
*/
public Set<GrammerSymbol> getVts() {
Set<GrammerSymbol> set = new TreeSet<>();
for (GrammerSymbol gs : value)
if (GrammerSymbol.isTerminal(gs))
set.add(gs);
return set;
}
@Override
public int compareTo(GrammerSymbols o) {
int lencmp = Integer.compare(this.value.size(), o.value.size());
if (lencmp != 0) return -lencmp;
return this.valueString.compareTo(o.valueString);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
GrammerSymbols that = (GrammerSymbols) o;
return Objects.equals(valueString, that.valueString);
}
@Override
public int hashCode() {
return Objects.hash(valueString);
}
@Override
public Iterator<GrammerSymbol> iterator() {
return value.listIterator();
}
}
(3) Grammer.java
package exp2.grammer;
import exp2.grammer.exception.GrammerException;
import exp2.grammer.symbol.GrammerSymbol;
import exp2.grammer.symbol.GrammerSymbols;
import java.util.*;
import static exp2.grammer.symbol.GrammerSymbol.GS_EPSILON;
/**
* 文法
*
* @version 2020-06-01
*/
public class Grammer {
/* 終結(jié)符集合卵佛，在這里，我們假定終結(jié)符是除大寫字母和大寫字母聯(lián)合'外的其他非空可見字符 */
final Set<GrammerSymbol> Vt;
/* 非終結(jié)符集合，在這里截汪，我們假定非終結(jié)符是大寫字母疾牲，或者是大寫字母帶有'字符 */
final Set<GrammerSymbol> Vn;
/* 文法的開始符號(hào)，一般來說為S或者S' */
final GrammerSymbol S;
/* 文法的產(chǎn)生式 */
final Map<GrammerSymbol, Set<GrammerSymbols>> Productions;
/**
* 從文法產(chǎn)生式輸入構(gòu)造一個(gè)文法
*
* @param src 文法輸入
*/
public Grammer(String src) {
this(src.split("(\r\n)|(\n)|(\r)"));
}
/**
* 從文法產(chǎn)生式字符串?dāng)?shù)組構(gòu)造一個(gè)文法
*
* @param srcs 文法字符串?dāng)?shù)組
*/
public Grammer(String[] srcs) {
if (srcs.length <= 0)
throw new GrammerException("文法構(gòu)造時(shí)出錯(cuò)衙解，輸入的文法不應(yīng)為空阳柔。");
this.S = new GrammerSymbol(srcs[0].split("->")[0]);
Set<GrammerSymbol> Vt = new TreeSet<>();
Set<GrammerSymbol> Vn = new TreeSet<>();
Map<GrammerSymbol, Set<GrammerSymbols>> Productions = new TreeMap<>();
for (String src : srcs) {
String[] items = src.split("->");
if (items.length != 2)
throw new GrammerException("文法構(gòu)造時(shí)出錯(cuò)，輸入的產(chǎn)生式不可能含有多個(gè)或不含有->蚓峦。");
String left = items[0];
String right = items[1];
if ((left.length() > 2) || (left.length() == 0) || (left.length() == 2 && !left.endsWith("'")) || !(left.toUpperCase().equals(left)))
throw new GrammerException("文法構(gòu)造時(shí)出錯(cuò)舌剂，輸入的非終結(jié)符應(yīng)當(dāng)是大寫字母，或者是帶有'的大寫字母暑椰。");
GrammerSymbol nonTerminal = new GrammerSymbol(left);
Vn.add(nonTerminal);
Set<GrammerSymbols> rights;
if (Productions.containsKey(nonTerminal))
rights = Productions.get(nonTerminal);
else {
rights = new TreeSet<>();
Productions.put(nonTerminal, rights);
}
for (String item : right.split("\\|")) {
String s = item.replaceAll("\\s*", "");
GrammerSymbols gss = new GrammerSymbols(s);
if (!s.equals(""))
rights.add(gss);
Vt.addAll(gss.getVts());
Vn.addAll(gss.getVns());
}
}
for (GrammerSymbol gs : Productions.keySet())
Productions.replace(gs, Collections.unmodifiableSet(Productions.get(gs)));
Vt.add(GS_EPSILON);
Vn.add(this.S);
this.Productions = Collections.unmodifiableMap(Productions);
this.Vt = Collections.unmodifiableSet(Vt);
this.Vn = Collections.unmodifiableSet(Vn);
}
/**
* 根據(jù)一個(gè)已經(jīng)存在的文法構(gòu)造一個(gè)副本
*
* @param grammer 已經(jīng)存在的文法
*/
public Grammer(Grammer grammer) {
this.Productions = grammer.Productions;
this.S = grammer.S;
this.Vn = grammer.Vn;
this.Vt = grammer.Vt;
}
/**
* 從開始符號(hào)和產(chǎn)生式集合構(gòu)造文法
*
* @param S 開始符號(hào)
* @param Productions 產(chǎn)生式集合
*/
public Grammer(GrammerSymbol S, Map<GrammerSymbol, Set<GrammerSymbols>> Productions) {
this.Productions = Collections.unmodifiableMap(Productions);
this.S = S;
Set<GrammerSymbol> Vt = new TreeSet<>();
Set<GrammerSymbol> Vn = new TreeSet<>();
for (GrammerSymbol gs : this.Productions.keySet()) {
Set<GrammerSymbols> set = this.Productions.get(gs);
for (GrammerSymbols gss : set) {
Vt.addAll(gss.getVts());
Vn.addAll(gss.getVns());
}
}
Vn.add(this.S);
Vt.add(GS_EPSILON);
this.Vt = Collections.unmodifiableSet(Vt);
this.Vn = Collections.unmodifiableSet(Vn);
}
public Set<GrammerSymbol> getVt() {
return Vt;
}
public Set<GrammerSymbol> getVn() {
return Vn;
}
public GrammerSymbol getS() {
return S;
}
public Map<GrammerSymbol, Set<GrammerSymbols>> getProductions() {
return Productions;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Grammer grammer = (Grammer) o;
return Objects.equals(Vt, grammer.Vt) &&
Objects.equals(Vn, grammer.Vn) &&
Objects.equals(S, grammer.S) &&
Objects.equals(Productions, grammer.Productions);
}
@Override
public int hashCode() {
return Objects.hash(Vt, Vn, S, Productions);
}
@Override
public String toString() {
return "Grammer{" + "Vt=" + Vt +
", Vn=" + Vn +
", S=" + S +
", Productions=" + Productions +
'}';
}
}
(4) LL1Grammer.java
package exp2.grammer;
import exp2.grammer.exception.GrammerException;
import exp2.grammer.symbol.GrammerSymbol;
import exp2.grammer.symbol.GrammerSymbols;
import exp2.util.Pair;
import java.util.*;
import static exp2.grammer.symbol.GrammerSymbol.GS_EPSILON;
import static exp2.grammer.symbol.GrammerSymbol.isNonterminal;
/**
* LL(1)文法
*
* @version 2020-06-01
*/
public class LL1Grammer extends Grammer {
/* 文法的Fisrt集合 */
final Map<GrammerSymbol, Set<GrammerSymbol>> FirstSets;
/* 文法的Follow集合 */
final Map<GrammerSymbol, Set<GrammerSymbol>> FollowSets;
/* LL(1)文法的預(yù)測(cè)分析表 */
final Map<GrammerSymbol, Map<GrammerSymbol, GrammerSymbols>> PATable;
/**
* 從一個(gè)已經(jīng)存在的文法構(gòu)造成LL(1)文法
*
* @param grammer 已經(jīng)存在的文法
*/
public LL1Grammer(Grammer grammer) {
super(grammer);
Map<GrammerSymbol, Set<GrammerSymbol>> FirstSets = generateFirstSets();
for (GrammerSymbol gs : FirstSets.keySet())
FirstSets.replace(gs, Collections.unmodifiableSet(FirstSets.get(gs)));
this.FirstSets = Collections.unmodifiableMap(FirstSets);
Map<GrammerSymbol, Set<GrammerSymbol>> FollowSets = generateFollowSets();
for (GrammerSymbol gs : FollowSets.keySet())
FollowSets.replace(gs, Collections.unmodifiableSet(FollowSets.get(gs)));
this.FollowSets = Collections.unmodifiableMap(FollowSets);
Map<Pair<GrammerSymbol, GrammerSymbol>, Set<GrammerSymbols>> PATable = generatePATable();
boolean isNotLL1 = false;
Map<GrammerSymbol, Map<GrammerSymbol, GrammerSymbols>> LL1PATable = new TreeMap<>();
for (Pair<GrammerSymbol, GrammerSymbol> pair : PATable.keySet()) {
Set<GrammerSymbols> set = PATable.get(pair);
isNotLL1 |= (set.size() > 1);
Iterator<GrammerSymbols> iter = PATable.get(pair).iterator();
GrammerSymbols grammerSymbols = iter.hasNext()?iter.next():null;
if (LL1PATable.containsKey(pair.value1))
LL1PATable.get(pair.value1).put(pair.value2, grammerSymbols);
else {
Map<GrammerSymbol, GrammerSymbols> map = new TreeMap<>();
map.put(pair.value2, grammerSymbols);
LL1PATable.put(pair.value1, map);
}
}
if (isNotLL1) throw new GrammerException("該文法的預(yù)測(cè)分析表含有多重入口霍转，不是LL(1)的。");
for (GrammerSymbol gs : LL1PATable.keySet())
LL1PATable.replace(gs, Collections.unmodifiableMap(LL1PATable.get(gs)));
this.PATable = Collections.unmodifiableMap(LL1PATable);
}
/**
* 構(gòu)造一個(gè)LL(1)文法干茉，并生成它的First谴忧，F(xiàn)ollow集合以及預(yù)測(cè)分析表
*
* @param src 文法輸入
*/
public LL1Grammer(String src) {
this(src.split("(\r\n)|(\n)|(\r)"));
}
/**
* 構(gòu)造一個(gè)LL(1)文法很泊，并生成它的First角虫，F(xiàn)ollow集合以及預(yù)測(cè)分析表
*
* @param srcs 文法字符串?dāng)?shù)組
*/
public LL1Grammer(String[] srcs) {
super(srcs);
Map<GrammerSymbol, Set<GrammerSymbol>> FirstSets = generateFirstSets();
for (GrammerSymbol gs : FirstSets.keySet())
FirstSets.replace(gs, Collections.unmodifiableSet(FirstSets.get(gs)));
this.FirstSets = Collections.unmodifiableMap(FirstSets);
Map<GrammerSymbol, Set<GrammerSymbol>> FollowSets = generateFollowSets();
for (GrammerSymbol gs : FollowSets.keySet())
FollowSets.replace(gs, Collections.unmodifiableSet(FollowSets.get(gs)));
this.FollowSets = Collections.unmodifiableMap(FollowSets);
Map<Pair<GrammerSymbol, GrammerSymbol>, Set<GrammerSymbols>> PATable = generatePATable();
boolean isNotLL1 = false;
Map<GrammerSymbol, Map<GrammerSymbol, GrammerSymbols>> LL1PATable = new TreeMap<>();
for (Pair<GrammerSymbol, GrammerSymbol> pair : PATable.keySet()) {
Set<GrammerSymbols> set = PATable.get(pair);
isNotLL1 |= (set.size() > 1);
Iterator<GrammerSymbols> iter = PATable.get(pair).iterator();
GrammerSymbols grammerSymbols = iter.hasNext()?iter.next():null;
if (LL1PATable.containsKey(pair.value1))
LL1PATable.get(pair.value1).put(pair.value2, grammerSymbols);
else {
Map<GrammerSymbol, GrammerSymbols> map = new TreeMap<>();
map.put(pair.value2, grammerSymbols);
LL1PATable.put(pair.value1, map);
}
}
if (isNotLL1) throw new GrammerException("該文法的預(yù)測(cè)分析表含有多重入口，不是LL(1)的委造。");
for (GrammerSymbol gs : LL1PATable.keySet())
LL1PATable.replace(gs, Collections.unmodifiableMap(LL1PATable.get(gs)));
this.PATable = Collections.unmodifiableMap(LL1PATable);
}
/**
* 產(chǎn)生文法的所有終結(jié)符和非終結(jié)符的First集合
*
* @return 由文法符號(hào)作為鍵戳鹅，文法符號(hào)對(duì)應(yīng)的First集合作為值的鍵值對(duì)構(gòu)成的映射
*/
private Map<GrammerSymbol, Set<GrammerSymbol>> generateFirstSets() {
Map<GrammerSymbol, Set<GrammerSymbol>> FirstSets = new TreeMap<>();
Set<GrammerSymbol> firstX;
/* 規(guī)則1 若X∈Vt, 則First(X) = {X}*/
for (GrammerSymbol X : this.Vt) {
firstX = new TreeSet<>();
firstX.add(X);
FirstSets.put(X, firstX);
}
/* 規(guī)則2 若X∈Vn, 且有產(chǎn)生式X->a...，則把a(bǔ)加入到First(X)中 */
for (GrammerSymbol X : this.Vn) {
firstX = new TreeSet<>();
FirstSets.put(X, firstX);
Set<GrammerSymbols> Productions = this.Productions.get(X);
if (Productions == null) continue;
for (GrammerSymbols production : Productions) {
GrammerSymbol a = production.get(0);
if (GrammerSymbol.isTerminal(a))
firstX.add(a);
}
}
/* 連續(xù)使用規(guī)則3昏兆，直至每個(gè)文法符號(hào)的First集不再增大為止.
規(guī)則3-1 若X->Y...是一個(gè)產(chǎn)生式枫虏，且Y∈Vn，則把Fisrt(Y)中的所有非ε-元素都加到FIRST(X)中爬虱；
規(guī)則3-2 若X->Y_1Y_2...Y_k是一個(gè)產(chǎn)生式隶债，Y_1,?,Y_(i-1)都是非終結(jié)符，而且跑筝，
對(duì)于任何j死讹，1≤j≤i-1，F(xiàn)irst(Y_j)都含有ε(即Y_1Y_2...Y_(i-1)=*=>ε)曲梗，則把First(Y_j )中的所有非ε-元素都加到First(X)中赞警；
規(guī)則3-3 特別是，若所有的First(Y_j)均含有ε,j=1,2,?,k虏两，則把ε加到First(X)中愧旦。
*/
boolean modified = true;
while (modified) {
modified = false;
for (GrammerSymbol X : this.Productions.keySet()) {
firstX = FirstSets.get(X);
Set<GrammerSymbols> Productions = this.Productions.get(X);
Label1:
for (GrammerSymbols production : Productions) {
/* 規(guī)則3-1 */
GrammerSymbol Y = production.get(0);
if (GrammerSymbol.isTerminal(Y)) continue;
Set<GrammerSymbol> firstY = new TreeSet<>(FirstSets.get(Y));
firstY.remove(GS_EPSILON);
int fslen = firstX.size();
firstX.addAll(firstY);
modified |= (fslen != firstX.size());
if (!FirstSets.get(Y).contains(GS_EPSILON)) continue;
/* 規(guī)則3-2 */
for (int i = 1; i < production.length(); ++i) {
Y = production.get(i);
if (GrammerSymbol.isTerminal(Y)) continue Label1;
firstY = new TreeSet<>(FirstSets.get(Y));
firstY.remove(GS_EPSILON);
fslen = firstX.size();
firstX.addAll(firstY);
modified |= (fslen != firstX.size());
if (!FirstSets.get(Y).contains(GS_EPSILON)) continue Label1;
}
/* 規(guī)則3-3 */
fslen = firstX.size();
firstX.add(GS_EPSILON);
modified |= (fslen != firstX.size());
}
}
}
return FirstSets;
}
/**
* 產(chǎn)生文法的所有非終結(jié)符的Follow集合
*
* @return 由文法符號(hào)作為鍵，文法中非終結(jié)符對(duì)應(yīng)的Follow集合作為值的鍵值對(duì)構(gòu)成的映射
*/
private Map<GrammerSymbol, Set<GrammerSymbol>> generateFollowSets() {
Map<GrammerSymbol, Set<GrammerSymbol>> FollowSets = new TreeMap<>();
Set<GrammerSymbol> FollowSet;
for (GrammerSymbol gs : this.Vn) {
FollowSet = new TreeSet<>();
FollowSets.put(gs, FollowSet);
}
/* 規(guī)則1 對(duì)于文法的開始符號(hào)S定罢，置#于FOLLOW(S)中笤虫； */
FollowSets.get(this.S).add(new GrammerSymbol("#"));
boolean modified = true;
/* 連續(xù)使用規(guī)則2和3，直至每個(gè)Follow集不再增大為止. */
while (modified) {
modified = false;
for (GrammerSymbol A : Productions.keySet()) {
Set<GrammerSymbols> Productions = this.Productions.get(A);
for (GrammerSymbols production : Productions) {
GrammerSymbol B;
Set<GrammerSymbol> followB;
int fslen;
for (int i = 0; i < production.length() - 1; ++i) {
/* 規(guī)則2 若A→αBβ是一個(gè)產(chǎn)生式，則把FIRST(β)\{ε}加至FOLLOW(B)中琼蚯； */
B = production.get(i);
if (GrammerSymbol.isTerminal(B)) continue;
followB = FollowSets.get(B);
GrammerSymbols beta = production.subSequence(i + 1, production.length());
Set<GrammerSymbol> fisrtSetBeta = this.FirstSet(beta);
boolean firstSetBetaHasEpsilon = fisrtSetBeta.contains(GS_EPSILON);
fisrtSetBeta.remove(GS_EPSILON);
fslen = followB.size();
followB.addAll(fisrtSetBeta);
modified |= (fslen != followB.size());
/* 規(guī)則3-1 若A→αBβ是一個(gè)產(chǎn)生式而β→ε (即ε?First(β))境蜕，則把Follow(A)加至Follow(B)中。 */
if (firstSetBetaHasEpsilon) {
fslen = followB.size();
followB.addAll(FollowSets.get(A));
modified |= (fslen != followB.size());
}
}
/* 規(guī)則3-2 若A→αB是一個(gè)產(chǎn)生式凌停，則把Follow(A)加至Follow(B)中粱年。 */
B = production.get(production.length() - 1);
if (GrammerSymbol.isTerminal(B)) continue;
followB = FollowSets.get(B);
fslen = followB.size();
followB.addAll(FollowSets.get(A));
modified |= (fslen != followB.size());
}
}
}
return FollowSets;
}
/**
* 返回對(duì)應(yīng)文法字符串的First集合
*
* @param production 文法字符串
* @return 文法字符串production對(duì)應(yīng)的First集合
*/
public Set<GrammerSymbol> FirstSet(GrammerSymbols production) {
/* 構(gòu)造文法的一個(gè)任何符號(hào)串α的First集合 */
/* 規(guī)則1 置First(α)=First(X_1)\{ε}； */
GrammerSymbol gsY = production.get(0);
Set<GrammerSymbol> result = new TreeSet<>(this.FirstSets.get(gsY));
Set<GrammerSymbol> fsgsY;
result.remove(GS_EPSILON);
if (!FirstSets.get(gsY).contains(GS_EPSILON)) return result;
/* 規(guī)則2 若對(duì)于任何1≤j≤i-1,ε∈FIRST(X_j)罚拟，則把FIRST(X_i)\{ε}加至FIRST(α)中台诗； */
for (int i = 1; i < production.length(); ++i) {
gsY = production.get(i);
fsgsY = new TreeSet<>(FirstSets.get(gsY));
fsgsY.remove(GS_EPSILON);
result.addAll(fsgsY);
if (!FirstSets.get(gsY).contains(GS_EPSILON)) return result;
}
/* 規(guī)則3 特別是，若所有的First(Y_j)均含有ε,1≤j≤n赐俗，則把ε加到First(α)中拉队。 */
result.add(GS_EPSILON);
return result;
}
/**
* 返回對(duì)應(yīng)文法符號(hào)的First集合
*
* @param s 文法符號(hào)
* @return 文法符號(hào)s對(duì)應(yīng)的Fisrt集合
*/
public Set<GrammerSymbol> FirstSet(GrammerSymbol s) {
return this.FirstSets.get(s);
}
/**
* 產(chǎn)生文法的預(yù)測(cè)分析表
*
* @return 文法的預(yù)測(cè)分析表M
*/
private Map<Pair<GrammerSymbol, GrammerSymbol>, Set<GrammerSymbols>> generatePATable() {
Map<Pair<GrammerSymbol, GrammerSymbol>, Set<GrammerSymbols>> PATable = new TreeMap<>();
Set<GrammerSymbol> Vt = new TreeSet<>(this.Vt);
Vt.remove(GS_EPSILON);
Vt.add(new GrammerSymbol("#"));
for (GrammerSymbol gsn : this.Vn)
for (GrammerSymbol gst : Vt)
PATable.put(new Pair<>(gsn, gst), new TreeSet<>());
/* 對(duì)文法G的每個(gè)產(chǎn)生式A->α */
for (GrammerSymbol A : this.Productions.keySet()) {
Set<GrammerSymbols> productions = this.Productions.get(A);
for (GrammerSymbols alpha : productions) {
Set<GrammerSymbol> firstSet = this.FirstSet(alpha);
for (GrammerSymbol a : firstSet)
/* 若ε∈FIRST(α)，則對(duì)于任何的b∈FOLLOW(A)把A->α加至M[A,b]中 */
if (a.equals(GS_EPSILON)) {
Set<GrammerSymbol> followSet = this.FollowSet(A);
for (GrammerSymbol b : followSet)
PATable.get(new Pair<>(A, b)).add(alpha);
/* 對(duì)于每個(gè)終結(jié)符a∈FIRST(α)阻逮，把A->α加至M[A,a]中 */
} else PATable.get(new Pair<>(A, a)).add(alpha);
}
}
return PATable;
}
/**
* 返回對(duì)應(yīng)文法符號(hào)的Follow集合
* @param s 文法符號(hào)
* @return 文法符號(hào)s對(duì)應(yīng)的Follow集合
*/
public Set<GrammerSymbol> FollowSet(GrammerSymbol s) {
return this.FollowSets.get(s);
}
@Override
public Set<GrammerSymbol> getVn() {
return super.getVn();
}
@Override
public GrammerSymbol getS() {
return super.getS();
}
@Override
public Set<GrammerSymbol> getVt() {
return super.getVt();
}
@Override
public Map<GrammerSymbol, Set<GrammerSymbols>> getProductions() {
return super.getProductions();
}
public Map<GrammerSymbol, Set<GrammerSymbol>> getFirstSets() {
return FirstSets;
}
public Map<GrammerSymbol, Set<GrammerSymbol>> getFollowSets() {
return FollowSets;
}
public Map<GrammerSymbol, Map<GrammerSymbol, GrammerSymbols>> getLL1PATable() {
return this.PATable;
}
/**
* 判斷一個(gè)文法是不是LL(1)的
* @param grammer 要判斷的文法
* @return 如果文法是LL1的粱快，返回true，否則返回false
*/
public static boolean isLL1Grammer(Grammer grammer) {
try {
LL1Grammer ll1Grammer = new LL1Grammer(grammer);
} catch (GrammerException e) {
return false;
}
return true;
}
/**
* 嘗試將一個(gè)非LL(1)的文法轉(zhuǎn)換為一個(gè)LL(1)文法
*
* @param grammer 一個(gè)普通的文法
* @return 是否能成功轉(zhuǎn)換為L(zhǎng)L(1)文法叔扼，如果是事哭，那么返回轉(zhuǎn)換后的文法，否則返回null
*/
public static LL1Grammer convertFrom(Grammer grammer) {
List<GrammerSymbol> tempVn = new ArrayList<>(grammer.getVn());
Set<GrammerSymbol> newVn = new TreeSet<>(tempVn);
Map<GrammerSymbol, Set<GrammerSymbols>> newMap = new TreeMap<>(grammer.Productions);
/* 對(duì)于每一個(gè)非終結(jié)符P_i */
for (int i = 0; i < tempVn.size(); ++i) {
GrammerSymbol P_i = tempVn.get(i);
Set<GrammerSymbols> newSet = new TreeSet<>();
/* 對(duì)于P_i的每一條規(guī)則 */
Set<GrammerSymbols> productions = newMap.get(P_i);
Set<GrammerSymbols> newProductions = new TreeSet<>(productions);
for (int j = 0; j < i; ++j) {
GrammerSymbol P_j = tempVn.get(j);
Set<GrammerSymbols> tempProductions = new TreeSet<>(newProductions);
for (GrammerSymbols production : tempProductions) {
/* 如果規(guī)則形如P_i->P_jγ */
if (production.indexOf(P_j) == 0) {
/* 把P_j的規(guī)則帶入到P_i->P_jγ中 */
newProductions.remove(production);
String gammaString = production.subSequence(1).toString();
Set<GrammerSymbols> jProductions = newMap.get(P_j);
for (GrammerSymbols jProduction : jProductions)
newProductions.add(new GrammerSymbols(jProduction + gammaString));
}
}
}
/* 消除P_i的新規(guī)則中的所有左遞歸 */
Set<GrammerSymbols> newProductionHasLR = new TreeSet<>();
Set<GrammerSymbols> newProductionHasNoLR = new TreeSet<>();
for (GrammerSymbols newProduction : newProductions)
if (newProduction.indexOf(P_i) == 0)
newProductionHasLR.add(newProduction.subSequence(1));
else newProductionHasNoLR.add(newProduction);
if (newProductionHasLR.size() != 0) {
GrammerSymbol newSymbol = findNextNontermialinContext(P_i, newVn);
/* 所有的P->β_1P'|β_2P'|...|β_nP' */
for (GrammerSymbols beta : newProductionHasNoLR)
newSet.add(new GrammerSymbols(beta + newSymbol.toString()));
Set<GrammerSymbols> newSymbolSet = new TreeSet<>();
newMap.put(newSymbol, newSymbolSet);
for (GrammerSymbols alpha : newProductionHasLR)
newSymbolSet.add(new GrammerSymbols(alpha + newSymbol.toString()));
newSymbolSet.add(new GrammerSymbols(Collections.singletonList(GS_EPSILON)));
newVn.add(newSymbol);
}
/* 如果規(guī)則都不含左遞歸 */
else
newSet.addAll(newProductions);
newMap.replace(P_i, newSet);
}
/* 化簡(jiǎn)現(xiàn)在的文法 */
newVn = new TreeSet<>();
newVn.add(grammer.S);
boolean flag;
do {
flag = false;
for (GrammerSymbol Vn : newVn) {
Set<GrammerSymbols> set = newMap.get(Vn);
for (GrammerSymbols p : set) {
for (GrammerSymbol c : p) {
if (isNonterminal(c)) {
int fslen = newVn.size();
newVn.add(c);
flag |= (fslen != newVn.size());
}
}
}
}
} while (flag);
Map<GrammerSymbol, Set<GrammerSymbols>> tempMap = new TreeMap<>();
for (GrammerSymbol gs : newVn)
tempMap.put(gs, newMap.get(gs));
/* 以上步驟已經(jīng)消除左遞歸瓜富，下面進(jìn)行提左因子 */
/* 提左因子鳍咱，直到?jīng)]有左因子停止 */
do {
/* 假設(shè)沒有左因子 */
flag = false;
Set<GrammerSymbol> curVn = new TreeSet<>(newVn);
for (GrammerSymbol gs : newVn) {
Set<GrammerSymbols> productions = tempMap.get(gs);
Map<GrammerSymbol, Set<GrammerSymbols>> counter = new TreeMap<>();
for (GrammerSymbols production : productions) {
GrammerSymbol first = production.get(0);
if (counter.containsKey(first))
counter.get(first).add(production);
else {
counter.put(first, new TreeSet<>());
counter.get(first).add(production);
}
}
Map<GrammerSymbol, Set<GrammerSymbols>> counterfilter = new TreeMap<>();
for (GrammerSymbol key : counter.keySet()) {
if (counter.get(key).size() > 1) {
counterfilter.put(key, counter.get(key));
}
}
/* 看看是否真的沒有左因子 */
flag |= (counterfilter.size() > 0);
/* 如果有左因子，將A->δβ_1|δβ_2|...|δβ_n|γ_1|γ_2|...|γ_m
* 改寫為A->δA'|γ_1|γ_2|...|γ_m
* A'->β_1|β_2|...|β_n
*/
if (counterfilter.size() > 0) {
for (GrammerSymbol delta : counterfilter.keySet()) {
GrammerSymbol A_ = findNextNontermialinContext(gs, curVn);
curVn.add(A_);
Set<GrammerSymbols> set = counterfilter.get(delta);
productions.removeAll(set);
productions.add(new GrammerSymbols(delta + A_.toString()));
Set<GrammerSymbols> secondSet = new TreeSet<>();
for (GrammerSymbols gss : set)
secondSet.add(gss.subSequence(1));
tempMap.put(A_, secondSet);
}
}
}
newVn.addAll(curVn);
} while (flag);
LL1Grammer ll1Grammer;
try {
Grammer temp = new Grammer(grammer.S, tempMap);
ll1Grammer = new LL1Grammer(temp);
} catch (GrammerException e) {
return null;
}
return ll1Grammer;
}
private static GrammerSymbol findNextNontermialinContext(GrammerSymbol prev, Set<GrammerSymbol> set) {
GrammerSymbol newSymbol;
/* 如果當(dāng)前符號(hào)帶'与柑，或者加上'后在set中谤辜，尋找一個(gè)不帶'的大寫字母代替 */
if (prev.toString().length() == 2) {
newSymbol = findNextNontermialNotinSet(set);
}
else {
newSymbol = new GrammerSymbol(prev.toString() + '\'');
if (set.contains(newSymbol)) {
newSymbol = findNextNontermialNotinSet(set);
}
}
return newSymbol;
}
private static GrammerSymbol findNextNontermialNotinSet(Set<GrammerSymbol> set) {
GrammerSymbol cur;
for (char c = 'A'; c <= 'Z'; ++c) {
cur = new GrammerSymbol(c);
if (!set.contains(cur))
return cur;
}
for (char c = 'A'; c <= 'Z'; ++c) {
cur = new GrammerSymbol(c + "'");
if (!set.contains(cur))
return cur;
}
throw new GrammerException("達(dá)到最大非終結(jié)符個(gè)數(shù)，無法產(chǎn)生新的非終結(jié)符价捧。");
}
@Override
public String toString() {
return "LL1Grammer{" + "FirstSets=" + FirstSets +
", FollowSets=" + FollowSets +
", PATable=" + PATable +
", Vt=" + Vt +
", Vn=" + Vn +
", S=" + S +
", Productions=" + Productions +
'}';
}
}
(5) LL1Parser.java
package exp2.parser;
import exp2.grammer.Grammer;
import exp2.grammer.LL1Grammer;
import exp2.grammer.exception.GrammerException;
import exp2.grammer.symbol.GrammerSymbol;
import exp2.grammer.symbol.GrammerSymbols;
import exp2.util.*;
import java.util.*;
/**
* LL(1)預(yù)測(cè)分析器
*
* @version 2020-06-04
*/
public class LL1Parser {
/* 某個(gè)LL(1)文法 */
final LL1Grammer grammer;
/**
* 從某個(gè)一個(gè)存在的LL(1)文法構(gòu)造LL(1)預(yù)測(cè)分析程序
*
* @param grammer 已經(jīng)存在的LL(1)文法
*/
public LL1Parser(LL1Grammer grammer) {
this.grammer = grammer;
}
/**
* 從某個(gè)一個(gè)存在的文法構(gòu)造LL(1)預(yù)測(cè)分析程序
*
* @param grammer 已經(jīng)存在的文法
* @throws GrammerException 如果這個(gè)文法不是LL(1)的
*/
public LL1Parser(Grammer grammer) { this.grammer = new LL1Grammer(grammer); }
/**
* 采用給定的LL(1)文法{@link #grammer}分析字符串
*
* @param string 要分析的字符串
* @return 分析結(jié)果
*/
public List<Quartet<String, String, String, String>> parseString(String string) {
return parseGrammerSymbols(new GrammerSymbols(string));
}
/**
* 采用給定的LL(1)文法{@link #grammer}分析輸入的文法符號(hào)序列
*
* @param input 要分析的文法符號(hào)序列
* @return 分析結(jié)果
*/
public List<Quartet<String, String, String, String>> parseGrammerSymbols(GrammerSymbols input) {
/* 符號(hào)棧, 剩余輸入串, 所用產(chǎn)生式, 動(dòng)作 */
List<Quartet<String, String, String, String>> snap = new LinkedList<>();
String inputString = input.toString();
String usedProduction = "";
Stack<GrammerSymbol> stack = new Stack<>();
StringBuilder action;
GrammerSymbol EOI = new GrammerSymbol("#");
GrammerSymbols Epsilon = new GrammerSymbols(Collections.singletonList(GrammerSymbol.GS_EPSILON));
/* 把#和文法開始符號(hào)推入棧中 */
stack.add(EOI);
stack.add(this.grammer.getS());
snap.add(new Quartet<>(stack.toString(), inputString, usedProduction, "INIT"));
int index = -1;
/* 把第一個(gè)輸入符號(hào)讀入a中 */
GrammerSymbol a = input.get(++index);
boolean flag = true;
while (flag) {
usedProduction = "";
/* 把棧頂符號(hào)托出去并放在X中 */
GrammerSymbol X = stack.pop();
action = new StringBuilder("POP");
/* 如果X在終結(jié)符且X==a丑念，那么a指向下一個(gè)符號(hào)，否則出錯(cuò) */
if (this.grammer.getVt().contains(X))
if (X.equals(a)) {
a = input.get(++index);
action.append(", GETNEXT");
}
else {
flag = false;
action.append(", ERROR");
}
/* 如果X==#并且a==#结蟋，程序分析結(jié)束脯倚，否則出錯(cuò) */
else if (X.equals(EOI))
if (X.equals(a)) {
flag = false;
action.append(", SUCCESS");
}
else {
flag = false;
action.append(", ERROR");
}
else {
if (this.grammer.getLL1PATable().containsKey(X)) {
GrammerSymbols grammerSymbols = this.grammer.getLL1PATable().get(X).get(a);
/* 如果M[A,a]==null，表示出錯(cuò) */
if (grammerSymbols == null) {
flag = false;
action.append(", ERROR");
}
/* 如果M[A,a]有產(chǎn)生式（不是Error）椎眯，把產(chǎn)生式倒序推入棧 */
else {
usedProduction = X + "->" + grammerSymbols;
if (!grammerSymbols.equals(Epsilon)) {
action.append(", PUSH(");
for (int i = grammerSymbols.length() - 1; i >= 0; --i) {
GrammerSymbol g = grammerSymbols.get(i);
stack.add(g);
action.append(g.toString());
}
action.append(")");
}
}
}
/* 棧頂符號(hào)如果不是這幾種其一挠将，發(fā)生錯(cuò)誤 */
else {
flag = false;
action.append(", ERROR");
}
}
/* 記錄結(jié)果 */
snap.add(new Quartet<>(stack.toString(), inputString.substring(index), usedProduction, action.toString()));
}
return snap;
}
public LL1Grammer getGrammer() {
return grammer;
}
}
}
