實驗二、文法設計——基于LL(1)文法的預測分析表法
一、實驗目的
通過實驗教學，加深學生對所學的關于編譯的理論知識的了解，增強學生對所學知識的綜合應用能力，并通過實踐達到對所學的知識進行驗證。通過對基于LL(1)文法的預測分析表法DFA模拟程式實驗，使學生掌握确定的自上而下的文法分析的實作技術，及具體實作方法。通過本實驗加深對語詞法分析程式的功能及實作方法的了解 。
二、實驗環境
供Windows系統的PC機，可用C++/C#/Java等程式設計工具編寫
三、實驗内容
1、自己定義一個LL(1)文法
示例如(僅供參考) G[E]：E →TE' E' → +TE' | ε
T →FT' T' → *FT' | ε F → i | ( E )
2、構造其預測分析表，如
3、LL(1)文法的預測分析表的模型示意圖
4、預測分析控制程式的算法流程
5、運作結果，示例如下
四、實驗方式與要求
1、設計的下推自動機具有通用性，上機程式設計實作；
2、實驗報告格式要求書寫要點：概要設計(總體設計思想)；詳細設計(程式主流程、自動機的存儲格式、關鍵函數的流程圖)；結果分析(輸入與輸出結果、存在問題及有待改進善的地方、實驗心得)；
3、實驗報告限4頁内。
設計思路：我就講解一下核心部分代碼，首先，進棧函數在 298 行處左右，我們用 ArrayList 去定義一個動态數組 analyzeProduces ，我們定義了一個棧 analyzeStatck ，而這個棧在我們在定義 Analyzer 類中初始化化過了，是以在建立 analyzeStatck 中首先會進行初始化操作， push 了一個 # ，是以analyzeStatck 棧中會存在 # 這個字元(以這個 # 作為标記)，然後 302 行，我們向 analyzeStack 中推入開始符号，也就是我們在主函數設定的字元 E ，然後列印出開始符号以及一些格式要求(步驟，符号棧，輸入串，産生式等等)，設定 index 的值來記錄走過的步驟次數 。
從 308 行開始，我們開始對棧進行分析。我們設定一個判斷棧 analyzeStatck 是否為空，由前面可知，棧中存在 #E 兩個字元，顯然字元是非空的，通過 index++ 記錄目前的步數，然後我們去通過 peek 函數去彈出目前棧頂元素的第一個字元，通過和剩餘輸入串 str 的第一個字元進行比對。
如果棧頂元素與目前輸入串的第一個字元不可以比對，我們就去分析表 TextUtil 中利用函數 findUseExp 去找到這個産生式，而 findUseExp 函數我們通過去定義了一個哈希表去存儲查找出來的棧頂元素，用一個集合 keySet 去存儲哈希表的所有鍵值，通過 for 循環，利用定義一個紅黑樹 treeSet 去存取表達式，然後去進行比對，如果在紅黑樹中包含了目前查找的字元，我們就傳回目前從哈希表中所擷取到的表達式。将目前所找到的産生式存入到 nowUseExpStr 中，列印出此時所進行到的步驟值，符号棧，輸入棧，産生式。316 行，我們建立一個分析棧 produce 去記錄上一步的值(位置，符号棧，輸入串)，判斷目前的産生式是否為空，如果不為空，設定下目前分析棧的産生式，将整個分析棧加入到動态數組 analyzeProduces 中，再将之前的分析棧中的棧頂彈出，如果目前的表達式不為空且第一個字元不是空字元，我們再将需要用到的表達式進行反序入棧。
如果棧頂元素與目前輸入串的第一個字元可以比對，分析棧出棧，串去掉一位，建立一個新的分析棧 produce ，記錄上一步的值(位置，符号棧，輸入串)，設定目前産生式為目前輸入串的第一個字元可以比對，将整個分析棧加入到動态數組 analyzeProduces 中，再将之前的分析棧中的棧頂彈出，将剩餘的字元串記錄在 str 字元串中。
注：produce 相當于是一個持久化存儲中間參數的一個分析棧
實驗代碼如下：
package python;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Stack;
class TextUtil {
public static boolean containsbA(TreeSet nvSet, String itemCharStr, Character a,
HashMap> expressionMap) {
String aStr = a.toString();
String lastStr = itemCharStr.substring(itemCharStr.length() - 1);
if (lastStr.equals(aStr)) {
return true;
}
return false;
}
public static boolean containsbAbIsNull(TreeSet nvSet, String itemCharStr, Character a,
HashMap> expressionMap) {
String aStr = a.toString();
if (containsAB(nvSet, itemCharStr, a)) {
Character alastChar = getAlastChar(itemCharStr, a);
System.out.println("----------------+++++++++++++++++++--" + expressionMap.toString());
ArrayList arrayList = expressionMap.get(alastChar);
if (arrayList.contains("ε")) {
System.out.println(alastChar + " contains('ε')" + aStr);
return true;
}
}
return false;
}
public static boolean containsAb(TreeSet ntSet, String itemCharStr, Character a) {
String aStr = a.toString();
if (itemCharStr.contains(aStr)) {
int aIndex = itemCharStr.indexOf(aStr);
String findStr;
try {
findStr = itemCharStr.substring(aIndex + 1, aIndex + 2);
} catch (Exception e) {
return false;
}
if (ntSet.contains(findStr.charAt(0))) {
return true;
} else {
return false;
}
} else {
return false;
}
}
public static boolean containsAB(TreeSet nvSet, String itemCharStr, Character a) {
String aStr = a.toString();
if (itemCharStr.contains(aStr)) {
int aIndex = itemCharStr.indexOf(aStr);
String findStr;
try {
findStr = itemCharStr.substring(aIndex + 1, aIndex + 2);
} catch (Exception e) {
return false;
}
if (nvSet.contains(findStr.charAt(0))) {
return true;
} else {
return false;
}
} else {
return false;
}
}
public static Character getAlastChar(String itemCharStr, Character a) {
String aStr = a.toString();
if (itemCharStr.contains(aStr)) {
int aIndex = itemCharStr.indexOf(aStr);
String findStr = "";
try {
findStr = itemCharStr.substring(aIndex + 1, aIndex + 2);
} catch (Exception e) {
return null;
}
return findStr.charAt(0);
}
return null;
}
public static boolean isEmptyStart(String selectExp) {
char charAt = selectExp.charAt(0);
if (charAt == 'ε') {
return true;
}
return false;
}
public static boolean isNtStart(TreeSet ntSet, String selectExp) {
char charAt = selectExp.charAt(0);
if (ntSet.contains(charAt)) {
return true;
}
return false;
}
public static boolean isNvStart(TreeSet nvSet, String selectExp) {
char charAt = selectExp.charAt(0);
if (nvSet.contains(charAt)) {
return true;
}
return false;
}
public static String findUseExp(TreeMap>> selectMap, Character peek,
char charAt) {
try {
HashMap> hashMap = selectMap.get(peek);
Set keySet = hashMap.keySet();
for (String useExp : keySet) {
TreeSet treeSet = hashMap.get(useExp);
if (treeSet.contains(charAt)) {
return useExp;
}
}
} catch (Exception e) {
return null;
}
return null;
}
}
class Analyzer {
public Analyzer() {
super();
analyzeStatck = new Stack();
// 結束符進棧
analyzeStatck.push('#');
}
private ArrayList analyzeProduces;
private Gs ll1Gs;
public Gs getLl1Gs() {
return ll1Gs;
}
public void setLl1Gs(Gs ll1Gs) {
this.ll1Gs = ll1Gs;
}
private Character startChar;
private Stack analyzeStatck;
private String str;
private String useExp;
public ArrayList getAnalyzeProduces() {
return analyzeProduces;
}
public void setAnalyzeProduces(ArrayList analyzeProduces) {
this.analyzeProduces = analyzeProduces;
}
public Character getStartChar() {
return startChar;
}
public void setStartChar(Character startChar) {
this.startChar = startChar;
}
public Stack getAnalyzeStatck() {
return analyzeStatck;
}
public void setAnalyzeStatck(Stack analyzeStatck) {
this.analyzeStatck = analyzeStatck;
}
public String getStr() {
return str;
}
public void setStr(String str) {
this.str = str;
}
public String getUseExp() {
return useExp;
}
public void setUseExp(String useExp) {
this.useExp = useExp;
}
//進棧 flag is here
public void analyze() {
analyzeProduces = new ArrayList();
// 開始符進棧
analyzeStatck.push(startChar);
System.out.println("開始符:" + startChar);
System.out.println("步驟\t\t\t " + "符号棧\t\t " + "\t輸入串 \t\t\t" + "所用産生式 ");
int index = 0;
// 開始分析
// while (analyzeStatck.peek() != '#' && str.charAt(0) != '#') {
while (!analyzeStatck.empty()) {
index++;
//傳回棧頂元素
if (analyzeStatck.peek() != str.charAt(0)) {
// 到分析表中找到這個産生式
String nowUseExpStr = TextUtil.findUseExp(ll1Gs.getSelectMap(), analyzeStatck.peek(), str.charAt(0));
System.out.println(index + "\t\t\t" + analyzeStatck.toString() + "\t\t\t" + str + "\t\t\t"
+ analyzeStatck.peek() + "->" + nowUseExpStr);
AnalyzeProduce produce = new AnalyzeProduce();
produce.setIndex(index);
produce.setAnalyzeStackStr(analyzeStatck.toString());
produce.setStr(str);
if (null == nowUseExpStr) {
produce.setUseExpStr("無法比對!");
} else {
produce.setUseExpStr(analyzeStatck.peek() + "->" + nowUseExpStr);
}
analyzeProduces.add(produce);
// 将之前的分析棧中的棧頂出棧
analyzeStatck.pop();
// 将要用到的表達式入棧,反序入棧
if (null != nowUseExpStr && nowUseExpStr.charAt(0) != 'ε') {
for (int j = nowUseExpStr.length() - 1; j >= 0; j--) {
char currentChar = nowUseExpStr.charAt(j);
analyzeStatck.push(currentChar);
}
}
continue;
}
// 如果可以比對,分析棧出棧，串去掉一位
if (analyzeStatck.peek() == str.charAt(0)) {
System.out.println(index + "\t\t\t" + analyzeStatck.toString() + "\t\t\t" + str + "\t\t\t" + "“"
+ str.charAt(0) + "”比對");
AnalyzeProduce produce = new AnalyzeProduce();
produce.setIndex(index);
produce.setAnalyzeStackStr(analyzeStatck.toString());
produce.setStr(str);
produce.setUseExpStr("“" + str.charAt(0) + "”比對");
analyzeProduces.add(produce);
analyzeStatck.pop();
str = str.substring(1);
continue;
}
}
}
}
class AnalyzeProduce implements Serializable{
private static final long serialVersionUID = 10L;
private Integer index;
private String analyzeStackStr;
private String str;
private String useExpStr;
public Integer getIndex() {
return index;
}
public void setIndex(Integer index) {
this.index = index;
}
public String getAnalyzeStackStr() {
return analyzeStackStr;
}
public void setAnalyzeStackStr(String analyzeStackStr) {
this.analyzeStackStr = analyzeStackStr;
}
public String getStr() {
return str;
}
public void setStr(String str) {
this.str = str;
}
public String getUseExpStr() {
return useExpStr;
}
public void setUseExpStr(String useExpStr) {
this.useExpStr = useExpStr;
}
}
class Gs implements Serializable {
private static final long serialVersionUID = 1L;
public Gs() {
super();
gsArray = new ArrayList();
nvSet = new TreeSet();
ntSet = new TreeSet();
firstMap = new HashMap>();
followMap = new HashMap>();
selectMap = new TreeMap>>();
}
private String[][] analyzeTable;
private TreeMap>> selectMap;
private ArrayList gsArray;
private HashMap> expressionMap;
private Character s;
private TreeSet nvSet;
private TreeSet ntSet;
private HashMap> firstMap;
private HashMap> followMap;
public String[][] getAnalyzeTable() {
return analyzeTable;
}
public void setAnalyzeTable(String[][] analyzeTable) {
this.analyzeTable = analyzeTable;
}
public TreeMap>> getSelectMap() {
return selectMap;
}
public void setSelectMap(TreeMap>> selectMap) {
this.selectMap = selectMap;
}
public HashMap> getFirstMap() {
return firstMap;
}
public void setFirstMap(HashMap> firstMap) {
this.firstMap = firstMap;
}
public HashMap> getFollowMap() {
return followMap;
}
public void setFollowMap(HashMap> followMap) {
this.followMap = followMap;
}
public HashMap> getExpressionMap() {
return expressionMap;
}
public void setExpressionMap(HashMap> expressionMap) {
this.expressionMap = expressionMap;
}
public ArrayList getGsArray() {
return gsArray;
}
public void setGsArray(ArrayList gsArray) {
this.gsArray = gsArray;
}
public Character getS() {
return s;
}
public void setS(Character s) {
this.s = s;
}
public TreeSet getNvSet() {
return nvSet;
}
public void setNvSet(TreeSet nvSet) {
this.nvSet = nvSet;
}
public TreeSet getNtSet() {
return ntSet;
}
public void setNtSet(TreeSet ntSet) {
this.ntSet = ntSet;
}
public void getNvNt() {
for (String gsItem : gsArray) {
String[] nvNtItem = gsItem.split("->");
String charItemStr = nvNtItem[0];
char charItem = charItemStr.charAt(0);
// nv在左邊
nvSet.add(charItem);
}
for (String gsItem : gsArray) {
String[] nvNtItem = gsItem.split("->");
// nt在右邊
String nvItemStr = nvNtItem[1];
// 周遊每一個字
for (int i = 0; i < nvItemStr.length(); i++) {
char charItem = nvItemStr.charAt(i);
if (!nvSet.contains(charItem)) {
ntSet.add(charItem);
}
}
}
}
public void initExpressionMaps() {
expressionMap = new HashMap>();
for (String gsItem : gsArray) {
String[] nvNtItem = gsItem.split("->");
String charItemStr = nvNtItem[0];
String charItemRightStr = nvNtItem[1];
char charItem = charItemStr.charAt(0);
if (!expressionMap.containsKey(charItem)) {
ArrayList expArr = new ArrayList();
expArr.add(charItemRightStr);
expressionMap.put(charItem, expArr);
} else {
ArrayList expArr = expressionMap.get(charItem);
expArr.add(charItemRightStr);
expressionMap.put(charItem, expArr);
}
}
}
public void getFirst() {
// 周遊所有Nv,求出它們的First集合
Iterator iterator = nvSet.iterator();
while (iterator.hasNext()) {
Character charItem = iterator.next();
ArrayList arrayList = expressionMap.get(charItem);
for (String itemStr : arrayList) {
boolean shouldBreak = false;
// Y1Y2Y3...Yk
for (int i = 0; i < itemStr.length(); i++) {
char itemitemChar = itemStr.charAt(i);
TreeSet itemSet = firstMap.get(charItem);
if (null == itemSet) {
itemSet = new TreeSet();
}
shouldBreak = calcFirst(itemSet, charItem, itemitemChar);
if (shouldBreak) {
break;
}
}
}
}
}
private boolean calcFirst(TreeSet itemSet, Character charItem, char itemitemChar) {
// get ago
// TreeSet itemSet = new TreeSet();
// 将它的每一位和Nt判斷下
// 是終結符或空串,就停止，并将它加到FirstMap中
if (itemitemChar == 'ε' || ntSet.contains(itemitemChar)) {
itemSet.add(itemitemChar);
firstMap.put(charItem, itemSet);
// break;
return true;
} else if (nvSet.contains(itemitemChar)) {// 這一位是一個非終結符
ArrayList arrayList = expressionMap.get(itemitemChar);
for (int i = 0; i < arrayList.size(); i++) {
String string = arrayList.get(i);
char tempChar = string.charAt(0);
calcFirst(itemSet, charItem, tempChar);
}
}
return true;
}
public void getFollow() {
for (Character tempKey : nvSet) {
TreeSet tempSet = new TreeSet();
followMap.put(tempKey, tempSet);
}
// 周遊所有Nv,求出它們的First集合
Iterator iterator = nvSet.descendingIterator();
// nvSet.descendingIterator();
while (iterator.hasNext()) {
Character charItem = iterator.next();
System.out.println("charItem:" + charItem);
Set keySet = expressionMap.keySet();
for (Character keyCharItem : keySet) {
ArrayList charItemArray = expressionMap.get(keyCharItem);
for (String itemCharStr : charItemArray) {
System.out.println(keyCharItem + "->" + itemCharStr);
TreeSet itemSet = followMap.get(charItem);
calcFollow(charItem, charItem, keyCharItem, itemCharStr, itemSet);
}
}
}
}
private void calcFollow(Character putCharItem, Character charItem, Character keyCharItem, String itemCharStr,
TreeSet itemSet) {
///
// (1)A是S(開始符)，加入#
if (charItem.equals(s)) {
itemSet.add('#');
System.out.println("---------------find S:" + charItem + " ={#}+Follow(E)");
followMap.put(putCharItem, itemSet);
// return;
}
// (2)Ab,=First(b)-ε,直接添加終結符
if (TextUtil.containsAb(ntSet, itemCharStr, charItem)) {
Character alastChar = TextUtil.getAlastChar(itemCharStr, charItem);
System.out.println("---------------find Ab:" + itemCharStr + " " + charItem + " =" + alastChar);
itemSet.add(alastChar);
followMap.put(putCharItem, itemSet);
// return;
}
// (2).2AB,=First(B)-ε,=First(B)-ε，添加first集合
if (TextUtil.containsAB(nvSet, itemCharStr, charItem)) {
Character alastChar = TextUtil.getAlastChar(itemCharStr, charItem);
System.out.println(
"---------------find AB:" + itemCharStr + " " + charItem + " =First(" + alastChar + ")");
TreeSet treeSet = firstMap.get(alastChar);
itemSet.addAll(treeSet);
if (treeSet.contains('ε')) {
itemSet.add('#');
}
itemSet.remove('ε');
followMap.put(putCharItem, itemSet);
///
if (TextUtil.containsbAbIsNull(nvSet, itemCharStr, charItem, expressionMap)) {
char tempChar = TextUtil.getAlastChar(itemCharStr, charItem);
System.out.println("tempChar:" + tempChar + " key" + keyCharItem);
if (!keyCharItem.equals(charItem)) {
System.out.println("---------------find tempChar bA: " + "tempChar:" + tempChar + keyCharItem
+ " " + itemCharStr + " " + charItem + " =Follow(" + keyCharItem + ")");
Set keySet = expressionMap.keySet();
for (Character keyCharItems : keySet) {
ArrayList charItemArray = expressionMap.get(keyCharItems);
for (String itemCharStrs : charItemArray) {
calcFollow(putCharItem, keyCharItem, keyCharItems, itemCharStrs, itemSet);
}
}
}
}
}
// (3)B->aA,=Follow(B),添加followB
if (TextUtil.containsbA(nvSet, itemCharStr, charItem, expressionMap)) {
if (!keyCharItem.equals(charItem)) {
System.out.println("---------------find bA: " + keyCharItem + " " + itemCharStr + " " + charItem
+ " =Follow(" + keyCharItem + ")");
Set keySet = expressionMap.keySet();
for (Character keyCharItems : keySet) {
ArrayList charItemArray = expressionMap.get(keyCharItems);
for (String itemCharStrs : charItemArray) {
calcFollow(putCharItem, keyCharItem, keyCharItems, itemCharStrs, itemSet);
}
}
}
}
}
public void getSelect() {
// 周遊每一個表達式
// HashMap>>
Set keySet = expressionMap.keySet();
for (Character selectKey : keySet) {
ArrayList arrayList = expressionMap.get(selectKey);
// 每一個表達式
HashMap> selectItemMap = new HashMap>();
for (String selectExp : arrayList) {
TreeSet selectSet = new TreeSet();
// set裡存放的資料分3種情況,由selectExp決定
// 1.A->ε,=follow(A)
if (TextUtil.isEmptyStart(selectExp)) {
selectSet = followMap.get(selectKey);
selectSet.remove('ε');
selectItemMap.put(selectExp, selectSet);
}
// 2.Nt開始,=Nt
//
終結符開始
if (TextUtil.isNtStart(ntSet, selectExp)) {
selectSet.add(selectExp.charAt(0));
selectSet.remove('ε');
selectItemMap.put(selectExp, selectSet);
}
// 3.Nv開始，=first(Nv)
if (TextUtil.isNvStart(nvSet, selectExp)) {
selectSet = firstMap.get(selectKey);
selectSet.remove('ε');
selectItemMap.put(selectExp, selectSet);
}
selectMap.put(selectKey, selectItemMap);
}
}
}
public void genAnalyzeTable() throws Exception {
Object[] ntArray = ntSet.toArray();
Object[] nvArray = nvSet.toArray();
// 預測分析表初始化
analyzeTable = new String[nvArray.length + 1][ntArray.length + 1];
// 輸出一個占位符
System.out.print("Nv/Nt" + "\t\t");
analyzeTable[0][0] = "Nv/Nt";
// 初始化首行
for (int i = 0; i < ntArray.length; i++) {
if (ntArray[i].equals('ε')) {
ntArray[i] = '#';
}
System.out.print(ntArray[i] + "\t\t");
analyzeTable[0][i + 1] = ntArray[i] + "";
}
System.out.println("");
for (int i = 0; i < nvArray.length; i++) {
// 首列初始化
System.out.print(nvArray[i] + "\t\t");
analyzeTable[i + 1][0] = nvArray[i] + "";
for (int j = 0; j < ntArray.length; j++) {
String findUseExp = TextUtil.findUseExp(selectMap, Character.valueOf((Character) nvArray[i]),
Character.valueOf((Character) ntArray[j]));
if (null == findUseExp) {
System.out.print("\t\t");
analyzeTable[i + 1][j + 1] = "";
} else {
System.out.print(nvArray[i] + "->" + findUseExp + "\t\t");
analyzeTable[i + 1][j + 1] = nvArray[i] + "->" + findUseExp;
}
}
System.out.println();
}
}
}
public class LL1_modify {
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
// // LL(1)文法産生集合
ArrayList gsArray = new ArrayList();
// // Vn非終結符集合
// TreeSet nvSet = new TreeSet();
// // Vt終結符集合
// TreeSet ntSet = new TreeSet();
Gs gs = new Gs();
initGs(gsArray);
gs.setGsArray(gsArray);
// getNvNt(gsArray, gs.getNvSet(), gs.getNtSet());
gs.getNvNt();
gs.initExpressionMaps();
gs.getFirst();
// 設定開始符
gs.setS('E');
gs.getFollow();
gs.getSelect();
// 建立一個分析器
Analyzer analyzer = new Analyzer();
analyzer.setStartChar('E');
analyzer.setLl1Gs(gs);
analyzer.setStr("i+i*i#");
analyzer.analyze();
gs.genAnalyzeTable();
System.out.println("");
}
private static void getNvNt(ArrayList gsArray, TreeSet nvSet, TreeSet ntSet) {
for (String gsItem : gsArray) {
String[] nvNtItem = gsItem.split("->");
String charItemStr = nvNtItem[0];
char charItem = charItemStr.charAt(0);
// nv在左邊
nvSet.add(charItem);
}
for (String gsItem : gsArray) {
String[] nvNtItem = gsItem.split("->");
// nt在右邊
String nvItemStr = nvNtItem[1];
// 周遊每一個字
for (int i = 0; i < nvItemStr.length(); i++) {
char charItem = nvItemStr.charAt(i);
if (!nvSet.contains(charItem)) {
ntSet.add(charItem);
}
}
}
}
private static void initGs(ArrayList gsArray) {
// Z相當于E',Y相當于T'
gsArray.add("E->TZ");
gsArray.add("Z->+TZ");
gsArray.add("Z->ε");
gsArray.add("Z->+TZ");
gsArray.add("T->FY");
gsArray.add("Z->+TZ");
gsArray.add("Y->*FY");
gsArray.add("Y->ε");
gsArray.add("F->i");
gsArray.add("F->(E)");
}
}
測試結果如下：