一、實驗目的
學生運用編譯原理的知識在實驗技能和方法自行設計實驗方案并加以實作。
二、使用儀器、器材
計算機一台
作業系統：Windows10
程式設計軟體：Intellij IDEA
三、實驗内容及原理
1．實驗内容：
輸入任意一個正确的文法G[S]，都能分析，并得出一個等價的LL(1)文法G[E]，求出FIRST集和FOLLOW集，并求出LL(1)分析表。對輸入串進行文法分析，判斷其是否符合文法G[E]。
2．要求：
（1）輸入任意一個正确的文法G[S]，都能分析，并得出一個等價的LL(1)文法G[E];
（2）根據該LL(1)文法G[E]的文法規則建立LL(1)分析表；
（3）輸出輸入串分析過程。
3. 原理：
3.1 FIRST集構造原理：
3.2 FOLLOW集構造原理：
這裡FOLLOW集的表述難以了解，可以轉換成如下表述：
1.首先判斷非終結符A是否是文法開始符，如果是，則 # ∈ FOLLOW(A)
2.檢視A在哪幾個産生式的右部出現
3.檢視A是否位于産生式右部某候選式的最右端，
若是，則選用第三條規則
若否，則選用第二條規則且好看該候選項中A之後的符号串能否推導為空串，若能，則再次選用第三條規則
3.3 分析表構造原理：
一、主程式示意圖
二、掃描子程式算法思想
1.構造FIRST集：
周遊每一個産生式
{
if(産生式右部第一個字元a為終結符）
{
// S➡a...
a 加入FIRST(S)
}
else
{
// S➡A1...
求FIRST(A1)
FIRST(A1)\{ε}加入FIRST(S)
// S➡A1A2...An
如果FIRST(A1)包含空串，則檢查A2...An，将FIRST(Ai)\\{ε}加入FIRST(S)，直到其中一個不包含空串
如果A1到An的FIRST都包含空串，則空串加入FIRST(A1)
}
}
2.構造FOLLOW集：
周遊每一個産生式右部包含S的産生式
{
if(S在産生式最右部）
{
// E → ...S，使用規則三
// FOLLOW(E) ∈ FOLLOW(S)
将FOLLOW(E)加入到FOLLOW(S)
}
else
{
// E → αSβ，使用規則二
// 将FIRST(β)\{ε}加入FOLLOW，如果FIRST(β)包含ε，則對β使用規則三
if(β 屬于 Vt)
{
// FIRST(β) = {β}
直接将β加入FOLLOW(E)
}
else
{
FIRST(β)\{ε}加入FOLLOW(E)
if(FIRST(β)包含ε）
{
FOLLOW(β)加入FOLLOW(E)
}
}
}
}
3.構造分析表：
for(非終結符A:非終結符集)
{
擷取FIRST(A)
對于FIRST集的每一個元素
找到對應産生式，加入分析表
如果FIRST集包含空串，則對于任意b（b∈vt）屬于FOLLOW(A)，A->空串加入到M[A,b]
}
4.文法分析程式：
四、實驗過程原始記錄
1.目錄結構
2.類說明
該程式包含兩個核心類，GrammarProcessUtil和MyGrammarProcessor。GrammarProcessUtil：處理FIRST、FOLLOW和分析表
MyGrammarProcessor：進行文法分析，判斷某個句子是否符合文法
3.主要屬性說明
/**
* 儲存非終結符在 vnList中的位置
*/
private Map<String,Integer> vnMap = new HashMap<>();
/**
* 儲存終結符在 vtList 中的位置
*/
private Map<String,Integer> vtMap = new HashMap<>();
/**
* 非終結符集
*/
private List<String> vnList = new ArrayList<>();
/**
* 終結符集
*/
private List<String> vtList = new ArrayList<>();
/**
* 分析表
*/
private String[][] table = null;
/**
* 儲存非終結符的産生式
*/
private Map<String,List<String>> productionMap = new HashMap<>();
/**
* 産生式的分隔符
*/
private final String SEPARATOR = "→";
/**
* 候選式的分隔符
*/
private final String CANDIDATE_SEPARATOR = "|";
/**
* 空串
*/
private final String BLANK_STRING = "ε";
/**
* FIRST集
*/
private Map<String,Set<String>> first = new HashMap<>();
/**
* FOLLOW集
*/
private Map<String,Set<String>> follow = new HashMap<>();
-
vnMap、vnList和vtMap、vtList是用來儲存終結符與非終結符資訊的。
其中Map用來儲存字元存儲在List的下标，List用來儲存字元。
- table是一個二維數組，用來儲存分析表，下标可根據Map來獲得。
- productionMap用來儲存每個非終結符對應的産生式的候選式（如S→a|Ba|C）則 productionMap中的資料為 鍵“S”對應的值為[“a”,“Ba”,“C”]
- first和follow分别為FIRST集與FOLLOW集
4.函數說明
紅框内的函數是主要函數，都是私有函數：
- initFirst()：初始化FIRST集
- getFirst(): 擷取某個非終結符的FIRST集
- initFollow()：初始化FOLLOW集
- getFollow()：擷取某個非終結符的FOLLOW集
- getTable(): 初始化分析表
-
printXXX(): 列印
綠框内的函數是公開函數，提供給外部使用：
- get()：根據終結符與非終結符傳回分析表中的内容
-
getGrammarStart(): 傳回文法開始符
其他函數是私有函數，則是起到一些輔助功能，具體可以檢視代碼中的注釋
5.程式清單
/**
* 文法分析器工具類，處理FIRST集、FOLLOW集和分析表
* @Author DELL
* @create 2020/12/4 15:26
*/
public class GrammarProcessorUtil {
/**
* 儲存非終結符在 vnList中的位置
*/
private Map<String,Integer> vnMap = new HashMap<>();
/**
* 儲存終結符在 vtList 中的位置
*/
private Map<String,Integer> vtMap = new HashMap<>();
/**
* 非終結符集
*/
private List<String> vnList = new ArrayList<>();
/**
* 終結符集
*/
private List<String> vtList = new ArrayList<>();
/**
* 分析表
*/
private String[][] table = null;
/**
* 儲存非終結符的産生式
*/
private Map<String,List<String>> productionMap = new HashMap<>();
/**
* 産生式的分隔符
*/
private final String SEPARATOR = "→";
/**
* 候選式的分隔符
*/
private final String CANDIDATE_SEPARATOR = "|";
/**
* 空串
*/
private final String BLANK_STRING = "ε";
/**
* FIRST集
*/
private Map<String,Set<String>> first = new HashMap<>();
/**
* FOLLOW集
*/
private Map<String,Set<String>> follow = new HashMap<>();
/**
* 将路徑拼接為類路徑
* @param path
* @return
*/
private String getClasspath(String path) {
return Thread.currentThread().getContextClassLoader().getResource(path).getPath();
}
/**
* 将産生式按照候選式的分隔符進行分割
* 例：str:"E'a|ε" => ["E'a","ε"]
* str:“E'a" => ["E'a"]
* @param str
* @return
*/
private List<String> splitBySeparator(String str) {
List<String> ans = new ArrayList<>();
if(!str.contains(CANDIDATE_SEPARATOR)) {
// 不包含分隔符，不可分割
ans.add(str);
return ans;
} else {
// 包含分隔符，進行分割
String[] split = str.split("\\|");
Collections.addAll(ans,split);
return ans;
}
}
/**
* 将字元串分割成一個個字元
* 注：主要是處理帶單引号的字元
* 例：str:"E'aT" => ["E'","a","T"]
* @param str
* @return
*/
private List<String> getCharacter(String str) {
List<String> ans = new ArrayList<>();
int end = str.length();
for(int start = str.length()-1;start >= 0;start--) {
if(str.charAt(start) == '\'') {
continue;
} else {
String substring = str.substring(start, end);
ans.add(substring);
end = start;
}
}
return ans;
}
/**
* 判斷字元串str是否完全包含 regex，傳回下标
* 例：str:"aEb",regex="E" => 1
* str:"aE'b",regex="E" => -1
* str:"aE'b",regex="E'" => 1
* @param str
* @param regex
* @return
*/
private int contains(String str,String regex) {
char[] ch = str.toCharArray();
if(regex.length() == 2) {
for (int i = 0; i < ch.length - 1; i++) {
if (ch[i] == regex.charAt(0) && ch[i + 1] == regex.charAt(1)) {
return i;
}
}
} else if(regex.length() == 1) {
for (int i = 0; i < ch.length; i++) {
if ((i == ch.length-1 && ch[i] == regex.charAt(0))
|| (ch[i] == regex.charAt(0) && ch[i + 1] != '\'')) {
return i;
}
}
} else {
throw new UnsupportedOperationException("int contains(String str,String regex):regex長度隻支援1或2");
}
return -1;
}
public GrammarProcessorUtil(String path) throws IOException {
// 讀取檔案，儲存資料
BufferedReader reader = new BufferedReader(new FileReader(getClasspath(path)));
String curLine = null;
while((curLine = reader.readLine()) != null) {
// 産生式左部 split[0]，右部：split[1]
String[] split = curLine.split(SEPARATOR);
String left = split[0];
String right = split[1];
// 處理産生式左部,儲存産生式右部
vnMap.put(left,vnList.size());
vnList.add(left);
productionMap.put(left,splitBySeparator(right));
}
reader.close();
// 擷取非終結符集
for(String vn:vnList) {
// 擷取非終結符産生式的右部的候選式
List<String> vnRight = productionMap.get(vn);
for(String right:vnRight) {
// 将一個個候選式拆分成字元（處理類似 E → S'a的情況）
List<String> characters = getCharacter(right);
for(String c:characters) {
// 不是非終結符 且 未曾加入到過 終結符集
if(!vnMap.containsKey(c) && !vtMap.containsKey(c)
&& !CANDIDATE_SEPARATOR.equals(c)) {
vtMap.put(c,vtList.size());
vtList.add(c);
}
}
}
}
// 列印終結符集 與 非終結符集
printVtAndVn();
// 擷取FIRST集
initFirst();
// 列印FIRST集
printFirst();
// 擷取FOLLOW集
initFollow();
// 列印FOLLOW集
printFollow();
// 擷取分析表
getTable();
// 列印分析表
printTable();
}
/**
* 初始化FIRST集
*/
private void initFirst() {
for(String vn:vnList) {
getFirst(vn);
}
}
/**
* 擷取FIRTS集
* @param vn
* @return
*/
private Set<String> getFirst(String vn) {
if(first.containsKey(vn)) return first.get(vn);
Set<String> set = new HashSet<>();
// 周遊産生式的右部的候選式
List<String> vnRight = productionMap.get(vn);
for(String right:vnRight) {
int index = 0;
// 候選式的第一個字元
String firstCharacter = String.valueOf(right.charAt(index++));
if (vtMap.containsKey(firstCharacter)) {
// 滿足 E→a...,a加入FIRST集
set.add(firstCharacter);
} else if (vnMap.containsKey(firstCharacter)) {
// 滿足 E→S...，S∈vt,FIRST(S)\{ε}加入FIRST(E)
Set<String> s = getFirst(firstCharacter);
// FIRST(S)是否包含空串
boolean hasBlankString = false;
for(String str:s) {
if(!BLANK_STRING.equals(str)) {
set.add(str);
} else {
hasBlankString = true;
}
}
// 記錄該産生式空串個數
int blankStringNumber = hasBlankString ? 1 : 0;
// E→S1S2S3... FIRST(S1)包含空串,則檢查下一個字元
while(hasBlankString && index < right.length()
&& vnMap.containsKey(String.valueOf(right.charAt(index)))) {
Set<String> nextFirst = getFirst(String.valueOf(right.charAt(index)));
for(String str:nextFirst) {
if(!BLANK_STRING.equals(str)) {
set.add(str);
} else {
blankStringNumber++;
hasBlankString = true;
}
}
index++;
}
// E→S1S2...Sn中的每個字元都可以推導出空串，空串加入FIRST集
if(blankStringNumber == right.length()) {
set.add(BLANK_STRING);
}
}
}
first.put(vn,set);
return set;
}
/**
* 初始化FOLLOW集
*/
private void initFollow() {
for(String vn:vnList) {
getFollow(vn);
}
}
/**
* 擷取FOLLOW集
* @param vn
* @return
*/
private Set<String> getFollow(String vn) {
// FOLLOW(vn)已經存在，直接傳回
if(follow.containsKey(vn) && !follow.get(vn).isEmpty()) return follow.get(vn);
Set<String> set = new HashSet<>();
// 文法開始符，#加入FOLLOW集
if(vnList.get(0).equals(vn)) {
set.add("#");
}
// 檢視vn在哪條産生式的右部出現過
for(String left:vnList) {
// 自己的FOLLOW集不用管
if(left.equals(vn)) {
continue;
}
// 擷取vn對應的産生式
List<String> vnRight = productionMap.get(left);
for(String item:vnRight) {
int index = contains(item,vn);
// 在産生式右部出現過
if(index != -1) {
// 這樣做是為了識别 E'
if(index + vn.length() == item.length()) {
// left→...S S出現在産生式最右部，使用規則三，将FOLLOW(left)加入FOLLOW(S)
Set<String> itemFollow = getFollow(left);
set.addAll(itemFollow);
} else {
// 否則使用規則二
// 擷取next，這裡要處理E'
String next = null;
int e1 = index + vn.length();
if(e1 + 1< item.length() && item.charAt(e1+1) == '\'') {
// SE',下一個字元帶單引号
next = item.substring(e1,e1+2);
} else {
// SE,下一個字元不帶單引号
next = item.substring(e1,e1+1);
}
if(vtMap.containsKey(next)) {
// 如果next是終結符，則FIRST(next) = {next}，直接加入
set.add(next);
} else {
// FIRST(next)\{ε}加入FOLLOW(vn)
Set<String> first = getFirst(next);
boolean hasBlankString = first.contains(BLANK_STRING);
for(String s:first) {
if(!BLANK_STRING.equals(s)) {
set.add(s);
}
}
// FIRST(next)含有ε，使用規則三
if(hasBlankString && !next.equals(vn)) {
Set<String> follow = getFollow(next);
set.addAll(follow);
}
}
}
}
}
}
follow.put(vn,set);
return set;
}
/**
* 将vn與vt對應的産生式存入分析表
* @param vn
* @param vt
* @param production
*/
private void fillTable(String vn,String vt,String production) {
if(table == null) {
throw new IllegalStateException("調用fillTable前請確定table已初始化！");
}
// 擷取vn與vt分别在vnList與vtList的下标
int vnIndex = vnMap.getOrDefault(vn,-1);
int vtIndex = -1;
if("#".equals(vt)) {
vtIndex = table[0].length - 1;
} else {
vtIndex = vtMap.getOrDefault(vt, -1);
}
if(vnIndex == -1 || vtIndex == -1) {
throw new IllegalArgumentException("fillTable(vn="+vn+",vt="+vt+",production="+production+")不合法");
}
// 拼接産生式
String trueProduction = vn+SEPARATOR+production;
// 存入分析表
table[vnIndex][vtIndex] = trueProduction;
}
/**
* 傳回vn對應的産生式，且産生式中包含vt
* 例：E→iESS'|a,vn:E,vt:i => iESS'
* @param vn
* @param vt
* @return
*/
private String findProduction(String vn,String vt) {
List<String> list = productionMap.get(vn);
for(String p:list) {
if(p.startsWith(vt)) {
return p;
}
}
return null;
}
/**
* 擷取分析表
* 前提：FIRST集與FOLLOW集已構造完成
* @return
*/
private String[][] getTable() {
if(table != null) return table;
table = new String[vnList.size()][vtList.size()+1];
// 周遊非終結符
for(String vn:vnList) {
// 擷取對應非終結符的FIRST集
Set<String> vnFirst = first.get(vn);
// 對于FIRST集的每一個元素，找到對應産生式，加入分析表
for(String vt:vnFirst) {
if(!BLANK_STRING.equals(vt)) {
String production = null;
if (productionMap.get(vn).size() == 1) {
production = productionMap.get(vn).get(0);
} else {
production = findProduction(vn, vt);
}
fillTable(vn, vt, production);
}
}
// FIRST集包含空串，則
if(vnFirst.contains(BLANK_STRING)) {
Set<String> vnFollow = follow.get(vn);
for(String vt:vnFollow) {
fillTable(vn, vt, BLANK_STRING);
}
}
}
return table;
}
/**
* 根據非終結符與終結符擷取分析表中的産生式
* @param vn
* @param vt
* @return
*/
public String get(String vn,String vt) {
if(table == null) {
throw new IllegalStateException("調用fillTable前請確定table已初始化！");
}
int vnIndex = vnMap.getOrDefault(vn,-1);
int vtIndex = -1;
if("#".equals(vt)) {
vtIndex = table[0].length - 1;
} else {
vtIndex = vtMap.getOrDefault(vt, -1);
}
if(vnIndex == -1 || vtIndex == -1) {
return null;
}
return table[vnIndex][vtIndex];
}
/**
* 擷取文法開始符
* @return
*/
public String getGrammarStart() {
return vnList.get(0);
}
/**
* 檢查vt是否為終結符
* @param vt
* @return
*/
public boolean containsVt(String vt) {
if("#".equals(vt)) return false;
return vtMap.containsKey(vt);
}
private void printVtAndVn() {
System.out.println("終結符：");
for(String vt:vtList) {
System.out.println(vt);
}
System.out.println("非終結符：");
for(String vn:vnList) {
System.out.println(vn);
}
}
private void printFirst() {
for(String vn:vnList) {
Set<String> strings = first.get(vn);
StringBuilder sb = new StringBuilder();
sb.append("FIRST(");
sb.append(vn);
sb.append(") = {");
for(String s:strings) {
sb.append(s).append(",");
}
sb.deleteCharAt(sb.length()-1);
sb.append("}");
System.out.println(sb.toString());
}
}
private void printFollow() {
for(String vn:vnList) {
Set<String> strings = follow.get(vn);
StringBuilder sb = new StringBuilder();
sb.append("FOLLOW(");
sb.append(vn);
sb.append(") = {");
for(String s:strings) {
sb.append(s).append(",");
}
sb.deleteCharAt(sb.length()-1);
sb.append("}");
System.out.println(sb.toString());
}
}
private void printTable() {
int blankIndex = vtMap.getOrDefault(BLANK_STRING,-1);
for(int i = 0;i < vtList.size();i++) {
if(i != blankIndex) {
System.out.print("\t" + vtList.get(i));
}
}
System.out.println("\t#");
for(int i = 0;i < table.length;i++) {
System.out.print(vnList.get(i)+"\t");
int j = 0;
for(j = 0;j < table[0].length - 1;j++) {
if(j != blankIndex) {
System.out.print("\t" + table[i][j]);
}
}
System.out.println("\t"+table[i][j]);
}
}
}
/**
* 定義文法分析器的行為
* @Author DELL
* @create 2020/12/4 15:17
*/
public interface GrammarProcessor {
boolean check(String str);
}
/**
* @Author DELL
* @create 2020/12/4 15:23
*/
public class MyGrammarProcessor implements GrammarProcessor {
private GrammarProcessorUtil util;
public MyGrammarProcessor(String path) throws IOException {
util = new GrammarProcessorUtil(path);
}
/**
* 根據一個非終結符與終結符擷取産生式
* @param vn
* @param vt
* @return
*/
public String get(String vn,String vt) {
//vt = vt.toUpperCase();
return util.get(vn,vt);
}
/**
* 檢查某個串是否符合 i+i 的文法
* @param str
* @return
*/
@Override
public boolean check(String str) {
printTitle(str);
// 初始時 # 與 文法開始符壓棧
Deque<String> stack = new LinkedList<>();
stack.push("#");
stack.push(util.getGrammarStart());
// 輸入串的下一個位置
int i = 0;
// 輸入串目前指向的字元
String cur = String.valueOf(str.charAt(i++));
// 棧頂符号
String top = null;
do{
// 列印
print(stack,str,i,cur);
top = stack.pop();
if(top.equals("#") && cur.equals("#")) break;
// 棧頂符号 ∈ Vt，判斷棧頂與輸入串目前字元是否相等
if(util.containsVt(top)) {
// x == a != "#"，則字元串指針移動
if(top.equalsIgnoreCase(cur)) {
if(!"#".equals(cur)) {
cur = "#";
System.out.println();
if(i < str.length()) {
cur = String.valueOf(str.charAt(i));
i++;
}
}
}
else {
return false;
}
} else {
// 根據棧頂查表
String t = get(top,cur);
// 找不到，識别失敗
if(t == null) {
return false;
}
// 輸出産生式
System.out.println(padWhitespaceRight(t,8));
// 擷取産生式的右部
String sentence = t.split("→")[1];
// 将産生式的右部逆序壓棧
int end = sentence.length();
for(int start = sentence.length()-1;start >= 0;start--) {
if(sentence.charAt(start) == '\'') {
continue;
} else {
String substring = sentence.substring(start, end);
// ε不壓棧
if(!"ε".equals(substring)) {
stack.push(substring);
end = start;
}
}
}
}
} while(!"#".equals(top));
System.out.println();
return true;
}
private void printTitle(String str) {
System.out.println(str+"解析流程：");
int len = str.length() + 3;
String[] titles = new String[] {"符号棧","目前輸入符号","輸入串","所用産生式"};
for(String s:titles) {
System.out.print(padWhitespaceRight(s,len));
}
System.out.println();
}
private void print(Deque<String> stack, String str, int i, String cur) {
int len = str.length() + 5;
StringBuilder sb = new StringBuilder();
// 拼接棧内的符号
Iterator<String> iterator = stack.descendingIterator();
while(iterator.hasNext()) {
sb.append(iterator.next());
}
// 輸出棧
System.out.print(padWhitespaceRight(sb.toString(),len));
// 輸出目前輸入符号
System.out.print(padWhitespaceRight(cur,len));
// 輸出輸入串
if(i < str.length()) {
System.out.print(padWhitespaceRight(str.substring(i-1),len));
} else {
System.out.print(padWhitespaceRight("#",len));
}
}
public static String padWhitespaceLeft(String s, int len) {
return String.format("%1$" + len + "s", s);
}
public static String padWhitespaceRight(String s, int len) {
return String.format("%1$-" + len + "s", s);
}
}
/**
* @Author DELL
* @create 2020/12/4 16:13
*/
public class GrammarTest {
@Test
public void test01() throws IOException {
MyGrammarProcessor grammarProcessor = new MyGrammarProcessor("grammar.txt");
List<String> tests = new ArrayList<>();
tests.add("i+i*i#");
tests.add("i+i#");
tests.add("i*i#");
tests.add("(i+i)*i#");
tests.add("(i*i)+(i)#");
for(String test:tests) {
System.out.println(grammarProcessor.check(test));
System.out.println();
}
List<String> err = new ArrayList<>();
err.add("i&i#");
err.add("i/(i*i)#");
for(String test:err) {
System.out.println(grammarProcessor.check(test));
System.out.println();
}
}
@Test
public void test02() throws IOException {
MyGrammarProcessor grammarProcessor = new MyGrammarProcessor("grammar02.txt");
System.out.println(grammarProcessor.check("i=e#"));
System.out.println();
System.out.println(grammarProcessor.check("i:i=e#"));
System.out.println();
System.out.println(grammarProcessor.check("i-i=e#"));
System.out.println();
}
}
五、實驗結果與分析
1.第一組文法：
其對應的輸出的終結符、非終結符、FIRST、FOLLOW、分析表如下：
2.第二組文法：
其對應的輸出的終結符、非終結符、FIRST、FOLLOW、分析表如下：
六、實驗分析及心得
分析：根據實驗結果顯示，對于檔案中的一個LL(1)文法，該程式能夠正常識别出終結符與非終結符，并且推出FIRST集、FOLLOW集，并使用FIRST、FOLLOW求得分析表，最終能夠實作對于給定的句子判斷是否符合文法，其中解析時能夠正确輸出符号棧、目前輸入符号、輸入串和所使用的産生式，達到了預期的目的。同時對于文法中的帶單引号的字元（E→TE’），該程式也做了一定識别。
心得：
1.通過實驗，将LL(1)文法的一系列流程通過程式實作出來，使得我對LL(1)文法的了解更加深刻，同時也鍛煉了自己的程式設計能力。
2.在對編譯原理的認知方面，我覺得對于編譯原理中給定的方法，如果我們能夠從程式的角度來看問題的話，會容易了解一些。例如FIRST集和FOLLOW集的構造方法中就會涉及到一些遞歸操作。
3.帶單引号的字元的文法的識别，無論是在構造分析表還是在識别句子的過程中，這一點都帶來了一定的困難，但最終都通過一定的方法克服了。
代碼已上傳至 gitee