学生运用编译原理的知识在实验技能和方法自行设计实验方案并加以实现。
计算机一台
操作系统：Windows10
编程软件：Intellij IDEA
输入任意一个正确的文法G[S]，都能分析，并得出一个等价的LL(1)文法G[E]，求出FIRST集和FOLLOW集，并求出LL(1)分析表。对输入串进行语法分析，判断其是否符合文法G[E]。
（1）输入任意一个正确的文法G[S]，都能分析，并得出一个等价的LL(1)文法G[E];
（2）根据该LL(1)文法G[E]的文法规则建立LL(1)分析表；
（3）输出输入串分析过程。
这里FOLLOW集的表述难以理解，可以转换成如下表述：
1.首先判断非终结符A是否是文法开始符，如果是，则 # ∈ FOLLOW(A)
2.查看A在哪几个产生式的右部出现
3.查看A是否位于产生式右部某候选式的最右端，
若是，则选用第三条规则
若否，则选用第二条规则且好看该候选项中A之后的符号串能否推导为空串，若能，则再次选用第三条规则
遍历每一个产生式
{
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)
}
}
遍历每一个产生式右部包含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)
}
}
}
}
for(非终结符A:非终结符集)
{
获取FIRST(A)
对于FIRST集的每一个元素
找到对应产生式，加入分析表
如果FIRST集包含空串，则对于任意b（b∈vt）属于FOLLOW(A)，A->空串加入到M[A,b]
}
4.语法分析程序：
该程序包含两个核心类，GrammarProcessUtil和MyGrammarProcessor。GrammarProcessUtil：处理FIRST、FOLLOW和分析表
MyGrammarProcessor：进行语法分析，判断某个句子是否符合语法
/**
* 保存非终结符在 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<>();
红框内的函数是主要函数，都是私有函数：
/**
* 语法分析器工具类，处理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();
}
}
其对应的输出的终结符、非终结符、FIRST、FOLLOW、分析表如下：
其对应的输出的终结符、非终结符、FIRST、FOLLOW、分析表如下：
分析：根据实验结果显示，对于文件中的一个LL(1)文法，该程序能够正常识别出终结符与非终结符，并且推出FIRST集、FOLLOW集，并使用FIRST、FOLLOW求得分析表，最终能够实现对于给定的句子判断是否符合文法，其中解析时能够正确输出符号栈、当前输入符号、输入串和所使用的产生式，达到了预期的目的。同时对于文法中的带单引号的字符（E→TE’），该程序也做了一定识别。
心得：
1.通过实验，将LL(1)文法的一系列流程通过程序实现出来，使得我对LL(1)文法的理解更加深刻，同时也锻炼了自己的编程能力。
2.在对编译原理的认知方面，我觉得对于编译原理中给定的方法，如果我们能够从程序的角度来看问题的话，会容易理解一些。例如FIRST集和FOLLOW集的构造方法中就会涉及到一些递归操作。
3.带单引号的字符的文法的识别，无论是在构造分析表还是在识别句子的过程中，这一点都带来了一定的困难，但最终都通过一定的方法克服了。
代码已上传至 gitee