编译原理实验三：语法分析程序
目录
编译原理第三个实验：语法分析程序，在词法分析的基础上，将单词序列组合成各类语法短语，如程序、语句、表达式等，并判断源程序在结构上是否正确。 语法分析程序通过使用上下文无关文法，按照源语言的语法规则，从词法分析的结果中识别出相应的语法范畴，同时进行语法检查。
1 需求分析
1.1 输入需求
① 从文本文件中读取给定的文法规则，并将文法规则存储在适当的数据结构中。
② 如果文法是LL（1）文法，需要用户输入四则混合运算的句子，程序需要对句子进行分析
1.2 文法定义需求
在进行语法分析之前需要先定义四则混合运算的语法规则，如下图，该语法规则可实现四则混合运算，包括+、-、*、/以及括号内的运算。
1.3 符号分类
① 程序需要将文法中的符号分为非终结符和终结符，并区分开始符号。
② 将非终结符和终结符存入VN、VT集合中。
1.4 判断LL(1)文法
程序需要检查文法是否为LL(1)文法，检查有多条产生式的SELECT集合的交集是否为空，如果所有SELECT集合的交集都为空，则文法是LL(1)的。。
1.5 构建预测分析表
如果文法为LL（1）文法，则须根据文法每一条产生式的SELECT集合构建预测分析表。
1.6 分析输入的单词串
如果文法为LL（1）文法，使用预测分析表对用户输入的四则混合运算的句子进行分析，如果语法正确，输出正确且返回结果值；否则，输出错误且输出错误位置。
2 功能分析
2.1 读取文件
程序可以从指定路径的文件中一行一行的读入文法文法规则，并将每一行保存在一个result数组中，最后将数组返回。
2.2 符号分类
① 从终结符集合中选取第一个符号作为文法的开始符号。
② 遍历list数组中的每个文法规则，对每个规则使用"→"将每条文法规则分割为左右两部分，左侧是非终结符，右侧是产生式。
③ 将左侧的非终结符加入到非终结符集合（VN）。遍历右侧的字符，将右侧的字符过滤掉非终结符后就是终结符，将所有的终结符添加到终结符集合（VT）中，和产生式集合（mapValue）。
④ 对于每个文法规则，将其右侧的产生式（right）添加到MAP中，MAP的键是非终结符，值是对应的产生式列表。
⑤ 如果当前字符后面跟着一个撇号（‘），将当前字符和撇号合并为一个新字符（如E’），并将这个新字符添加到right后面。
以下为符号分类的程序流程图：
2.3 消除左递归
① 创建一个迭代器it，用于遍历所有的非终结符，这是消除左递归的第一步。
② 使用迭代器it检查是否已经遍历完所有的非终结符。如果未迭代完，继续处理；如果已迭代完，结束迭代。
③ 对于每个非终结符，检查其对应的MAP中的右侧产生式部分是否被修改。这涉及到检查文法规则是否已经过左递归处理。
④ 遍历当前非终结符的所有产生式，对于每一项产生式，检查是否存在左递归的情况，即产生式的右侧是否以左侧的非终结符开始。如果存在左递归，需要对产生式进行处理，将其转换为等价的非左递归形式，并更新newRightCell，同时设置左递归标志flag为true。
⑤ 如果处理了左递归，需要更新文法，将修改后的产生式重新加入到MAP中，替换原有的左递归产生式。
消除左递归流程图如图3.2.3。
2.4 计算FIRST集合
1)程序遍历非终结符集合，根据非终结符集合中的非终结符获取MAP集合对应的value，也就是该非终结符对应的产生式列表。
2)遍历列表中的每一项，按照FIRST集合的计算规则计算出每一个非终结符的FIRST结合，并将它们存入FIRST集合中。
3)FIRST集合计算规则：
① 如果列表只有一项并且这一项是终结符或则是ε，即A->b 或者A->ε，那么FIRST(A)={b} 或 FIRST(A)={ε}
② 其他情况：以产生式 A->αβ为例
1.如果α是终结符，那么将该终结符加入FIRST(A)集合中；
2.如果α是非终结符:检查β
① β是终结符，将FIRST(α)加到FIRST(A)中
② β是非终结符，将FIRST(α)+FIRST(β)加到FIRST(A)中
③ 如果α可以推导出ε，那么需要按上面的步骤递归继续检查β
计算FIRST集合如图3.2.4：
2.5 计算FOLLOW集合
1)计算规则：以产生式A→αBβ为例
① 如果β不是ε或者不能够导出空串，那么将FIRST(β)中的所有元素（除了ε）添加到FOLLOW(B)中；
② 如果β能够导出空串，或者β以ε开始，那么将FOLLOW(A)中的所有元素添加到FOLLOW(B)中。
2)对于每个非终结符B，递归地计算其FOLLOW集合，直到没有新的元素可以添加到FOLLOW(B)中。
计算FOLLOW集合流程图如图3.2.5：
2.6 计算SELECT集合
计算SELECT集合：对于每个产生式A→α，计算SELECT(A→α)：将FIRST(α)中的所有元素添加到SELECT(A→α)中；如果α能够导出空串，或者α以ε开始，将FOLLOW(A)中的所有元素添加到SELECT(A→α)中。
计算SELECT集合流程图如图3.2.6：
2.7 LL(1)文法判断
程序对每个非终结符收集所有以该非终结符为左侧的产生式，形成产生式列表。检查每个非终结符的产生式列表，对于有多个产生式的非终结符，计算每对产生式的SELECT集合的交集。如果SELECT集合的交集为空，则文法是LL(1)文法；如果存在至少一对产生式的SELECT集合的交集不为空，则该文法不是LL(1)文法，因为这意味着在解析过程中可能会对选择哪个产生式产生歧义。
LL（1）文法判断流程图如图3.2.7：
2.8 构建预测分析表
1)初始化预测分析表
① 创建表结构：使用VN（非终结符集合）和VT（终结符集合，除去空串"ε"）的大小来初始化二维数组FORM。FORM的第一行用于存放终结符，第一列用于存放非终结符，其余部分用于存放预测分析表的具体内容。
② 填充第一行和第一列：遍历VT和VN，将终结符填充到FORM的第一行，将非终结符填充到FORM的第一列。
2)根据FIRST集合填表
① 遍历表：对于FORM中的每个单元格，如果单元格位于第一行（除了第一列），则根据FORM的第一列（非终结符）和第一行（终结符）构建键oneLeftKey，形式为A$a，其中A是非终结符，a是终结符。
② 查找FIRST集合：使用oneLeftKey作为键，在oneLeftFirst映射中查找对应的FIRST集合，并将结果填充到FORM的相应单元格中。
3)处理ε产生式
① 检查ε产生式：对于每个非终结符A，检查是否存在A→ε的产生式。如果存在，需要根据A的FOLLOW集合来进一步填表。
② 填充FOLLOW集合：对于A的FOLLOW集合中的每个终结符b，如果FORM中存在以A为起始的行和以b为起始的列，那么将A→ε的产生式添加到对应的单元格中。
3 测试结果
(1）文法输入
pic_center
(2)消除左递归
对于文法中存在左递归的情况，程序可以处理文法中的左递归。
(3)计算FIRST集合
程序可以根据FIRST集合的计算规则计算文法的FIRST集合。
(4)计算FOLLOW集合
程序可以根据FOLLOW集合的计算规则计算文法的FOLLOW集合
(5)计算SELECT集合
程序可以根据SELECT集合的计算规则计算文法的SELECT集合
(6)判断LL（1）文法
程序可以根据SELECT集合有无交集判断该文法是否为LL(1)文法
(7)输出预测分析表
(8)输出分析过程
程序能够输出四则混合运算的分析过程：
4 主要功能函数
(1)消除左递归函数
private static void reformMap() {
boolean isReForm = false;// MAP是否被修改
Set<String> keys = new HashSet<>(MAP.keySet());
Iterator<String> it = keys.iterator();
ArrayList<String> nullSign = new ArrayList<>();
nullSign.add("ε");
while (it.hasNext()) {
String left = it.next();
boolean flag = false;// 是否有左递归
ArrayList<ArrayList<String>> rightList = MAP.get(left);//[[T], [E, +, T], [E, -, T]]
ArrayList<String> oldRightCell = new ArrayList<>(); // 旧产生的右边
ArrayList<ArrayList<String>> newLeftNew = new ArrayList<>();// 存放新的左边和新的右边
// 消除直接左递归
for (ArrayList<String> strings : rightList) {//遍历每一个右边 [T], [E, +, T], [E, -, T]
ArrayList<String> newRightCell = new ArrayList<>(); // 新产生式的右边
if (strings.get(0).equals(left)) {//左递归
for (int j = 1; j < strings.size(); j++) {
newRightCell.add(strings.get(j));
}
flag = true;
newRightCell.add(left + "\'");
newLeftNew.add(newRightCell);
} else {
oldRightCell.addAll(strings);//T
oldRightCell.add(left + "\'");//E'
}
}
if (flag) {// 如果有左递归，则更新MAP
isReForm = true;
newLeftNew.add(nullSign);
MAP.put(left + "\'", newLeftNew);//newLeftNew:[[+, T, E'], [-, T, E'], [ε]]
VN.add(left + "\'"); // 加入新的VN
VT.add("ε"); // 加入ε到VT
ArrayList<ArrayList<String>> newLeftOld = new ArrayList<>();// 存放原先，但是产生新的右边
newLeftOld.add(oldRightCell);//TE'
MAP.put(left, newLeftOld);
}
}
// 如果文法被修改，则输出修改后的文法
if (isReForm) {
System.out.println("消除文法的左递归:");
Set<String> kSet = new HashSet<>(MAP.keySet());
for (String k : kSet) {
ArrayList<ArrayList<String>> leftList = MAP.get(k);
System.out.print("\t" + k + "→");
for (int i = 0; i < leftList.size(); i++) {
System.out.print(String.join("", leftList.get(i).toArray(new String[leftList.get(i).size()])));
if (i + 1 < leftList.size())
System.out.print("|");
}
System.out.println();
}
}
MAP.toString();
}
(2)求FIRST几何函数
private static void findFirst() {
System.out.println("\nFIRST集合:");
for (String s : VN) {
HashSet<String> firstCell = new HashSet<>();// 存放单个非终结符号的FIRST
ArrayList<ArrayList<String>> list = MAP.get(s);//[[+, T, E'], [-, T, E'], [ε]] FT'
// 遍历单个产生式的左边
// listCell为“|”分割出来
for (ArrayList<String> listCell : list) {//[+, T, E']
HashSet<String> firstCellOne = new HashSet<>();// 产生式左边用“ | ”分割的单个式子的First(弃用)
String oneLeft = String.join("", listCell.toArray(new String[listCell.size()]));//+TE'
if (VT.contains(listCell.get(0))) {//第一个字符就是终结符
firstCell.add(listCell.get(0));
firstCellOne.add(listCell.get(0));
oneLeftFirst.put(s + "$" + listCell.get(0), s + "→" + oneLeft);
} else {
boolean[] isVn = new boolean[listCell.size()];// 标记是否有定义为空,如果有则检查下一个字符
isVn[0] = true;// 第一个为非终结符号
int p = 0;
while (isVn[p]) {//第一个字符为非终结符
// System.out.println(p+" "+listCell.size());
if (VT.contains(listCell.get(p))) {
firstCell.add(listCell.get(p));
firstCellOne.add(listCell.get(p));
oneLeftFirst.put(s + "$" + listCell.get(p), s + "→" + oneLeft);
break;
}
String vnGo = listCell.get(p);//
Stack<String> stack = new Stack<>();
stack.push(vnGo);//非终结符入栈
while (!stack.isEmpty()) {
ArrayList<ArrayList<String>> listGo = MAP.get(stack.pop());//获取栈顶元素对应的产生式列表
for (ArrayList<String> listGoCell : listGo) {//遍历列表 F→(E)|D
if (VT.contains(listGoCell.get(0))) { // 如果第一个字符是终结符号
if (listGoCell.get(0).equals("ε")) {//第一个字符是ε
if (!s.equals(START)) { // 开始符号不能推出空
firstCell.add(listGoCell.get(0));
firstCellOne.add(listGoCell.get(0));
oneLeftFirst.put(s + "$" + listGoCell.get(0), s + "→" + oneLeft);
}
if (p + 1 < isVn.length) {// 如果为空，可以查询下一个字符
isVn[p + 1] = true;
}
} else { // 非空的终结符号加入对应的FIRST集合
firstCell.add(listGoCell.get(0));
firstCellOne.add(listGoCell.get(0));
oneLeftFirst.put(s + "$" + listGoCell.get(0), s + "→" + oneLeft);
}
} else {// 不是终结符号，入栈
stack.push(listGoCell.get(0));
}
}
}
p++;
if (p > isVn.length - 1)
break;
}
}
FIRST.put(s + "→" + oneLeft, firstCellOne);
// System.out.println("\tFIRST(" + s +"→"+oneLeft+ ")={" + String.join("、", firstCellOne.toArray(new String[firstCellOne.size()])) + "}");
}
FIRST.put(s, firstCell);
// 输出key的FIRST集合
System.out.println("\tFIRST(" + s + ")={" + String.join("、", firstCell.toArray(new String[firstCell.size()])) + "}");
}
}
(3)求FOLLOW几何函数
private static void findFollow() {
System.out.println("\nFOLLOW集合:");
Iterator<String> it = VN.iterator();
HashMap<String, HashSet<String>> keyFollow = new HashMap<>();
ArrayList<HashMap<String, String>> vn_VnList = new ArrayList<>();// 用于存放/A->...B 或者 A->...Bε的组合
HashSet<String> vn_VnListLeft = new HashSet<>();// 存放vn_VnList的左边和右边
HashSet<String> vn_VnListRight = new HashSet<>();
// 开始符号加入#
keyFollow.put(START, new HashSet<>() {
@Serial
private static final long serialVersionUID = 1L;
{
add("#");
}
});
while (it.hasNext()) {
String key = it.next();
ArrayList<ArrayList<String>> list = MAP.get(key);
ArrayList<String> listCell;
// 先把每个VN作为keyFollow的key，之后在查找添加其FOLLOW元素
if (!keyFollow.containsKey(key)) {
keyFollow.put(key, new HashSet<>());
}
keyFollow.toString();
for (ArrayList<String> strings : list) {
listCell = strings;
// (1)直接找非总结符号后面跟着终结符号
for (int j = 1; j < listCell.size(); j++) {
HashSet<String> set = new HashSet<>();
if (VT.contains(listCell.get(j))) {
// System.out.println(listCell.get(j - 1) + ":" + listCell.get(j));
set.add(listCell.get(j));
if (keyFollow.containsKey(listCell.get(j - 1)))
set.addAll(keyFollow.get(listCell.get(j - 1)));
keyFollow.put(listCell.get(j - 1), set);
}
}
// (2)找...VnVn...组合
for (int j = 0; j < listCell.size() - 1; j++) {
HashSet<String> set = new HashSet<>();
if (VN.contains(listCell.get(j)) && VN.contains(listCell.get(j + 1))) {
set.addAll(FIRST.get(listCell.get(j + 1)));
set.remove("ε");
if (keyFollow.containsKey(listCell.get(j)))
set.addAll(keyFollow.get(listCell.get(j)));
keyFollow.put(listCell.get(j), set);
}
}
// (3)A->...B 或者 A->...Bε(可以有n个ε)的组合存起来
for (int j = 0; j < listCell.size(); j++) {
HashMap<String, String> vn_Vn;
if (VN.contains(listCell.get(j)) && !listCell.get(j).equals(key)) {// 是VN且A不等于B
boolean isAllNull = false;// 标记VN后是否为空
if (j + 1 < listCell.size())// 即A->...Bε(可以有n个ε)
for (int k = j + 1; k < listCell.size(); k++) {
if ((FIRST.containsKey(listCell.get(k)) && FIRST.get(listCell.get(k)).contains("ε"))) {// 如果其后面的都是VN且其FIRST中包含ε
isAllNull = true;
} else {
isAllNull = false;
break;
}
}
// 如果是最后一个为VN,即A->...B
if (j == listCell.size() - 1) {
isAllNull = true;
}
if (isAllNull) {
vn_VnListLeft.add(key);
vn_VnListRight.add(listCell.get(j));
// 往vn_VnList中添加，分存在和不存在两种情况
boolean isHaveAdd = false;
for (int x = 0; x < vn_VnList.size(); x++) {
HashMap<String, String> vn_VnListCell = vn_VnList.get(x);
if (!vn_VnListCell.containsKey(key)) {
vn_VnListCell.put(key, listCell.get(j));
vn_VnList.set(x, vn_VnListCell);
isHaveAdd = true;
break;
} else {
// 去重
if (vn_VnListCell.get(key).equals(listCell.get(j))) {
isHaveAdd = true;
break;
}
continue;
}
}
if (!isHaveAdd) {// 如果没有添加，表示是新的组合
vn_Vn = new HashMap<>();
vn_Vn.put(key, listCell.get(j));
vn_VnList.add(vn_Vn);
}
}
}
}
}
}
keyFollow.toString();
// (4)vn_VnListLeft减去vn_VnListRight,剩下的就是入口产生式，
vn_VnListLeft.removeAll(vn_VnListRight);
// 用栈或者队列都行
Queue<String> keyQueue = new LinkedList<>(vn_VnListLeft);
while (!keyQueue.isEmpty()) {
String keyLeft = keyQueue.poll();
for (int t = 0; t < vn_VnList.size(); t++) {
HashMap<String, String> vn_VnListCell = vn_VnList.get(t);
if (vn_VnListCell.containsKey(keyLeft)) {
HashSet<String> set = new HashSet<>();
// 原来的FOLLOW加上左边的FOLLOW
if (keyFollow.containsKey(keyLeft))
set.addAll(keyFollow.get(keyLeft));
if (keyFollow.containsKey(vn_VnListCell.get(keyLeft)))
set.addAll(keyFollow.get(vn_VnListCell.get(keyLeft)));
keyFollow.put(vn_VnListCell.get(keyLeft), set);
keyQueue.add(vn_VnListCell.get(keyLeft));
// 移除已处理的组合
vn_VnListCell.remove(keyLeft);
vn_VnList.set(t, vn_VnListCell);
}
}
}
// 此时keyFollow为完整的FOLLOW集
FOLLOW = keyFollow;
// 打印FOLLOW集合
for (String key : keyFollow.keySet()) {
HashSet<String> f = keyFollow.get(key);
System.out.println("\tFOLLOW(" + key + ")={" + String.join("、", f.toArray(new String[f.size()])) + "}");
}
}
(4)构建预测分析表函数
private static void preForm() {
HashSet<String> set = new HashSet<>(VT);
set.remove("ε");
FORM = new String[VN.size() + 1][set.size() + 2];
Iterator<String> itVn = VN.iterator();
Iterator<String> itVt = set.iterator();
// (1)初始化FORM,并根据oneLeftFirst(VN$VT,产生式)填表
for (int i = 0; i < FORM.length; i++)
for (int j = 0; j < FORM[0].length; j++) {
if (i == 0 && j > 0) {// 第一行为Vt
if (itVt.hasNext()) {
FORM[i][j] = itVt.next();
}
if (j == FORM[0].length - 1)// 最后一列加入#
FORM[i][j] = "#";
}
if (j == 0 && i > 0) {// 第一列为Vn
if (itVn.hasNext())
FORM[i][j] = itVn.next();
}
if (i > 0 && j > 0) {// 其他情况先根据oneLeftFirst填表
String oneLeftKey = FORM[i][0] + "$" + FORM[0][j];// 作为key查找其First集合
FORM[i][j] = oneLeftFirst.get(oneLeftKey);
}
}
// (2)如果有推出了ε，则根据FOLLOW填表
for (int i = 1; i < FORM.length; i++) {
String oneLeftKey = FORM[i][0] + "$ε";
if (oneLeftFirst.containsKey(oneLeftKey)) {
HashSet<String> followCell = FOLLOW.get(FORM[i][0]);
for (String vt : followCell) {
for (int j = 1; j < FORM.length; j++)
for (int k = 1; k < FORM[0].length; k++) {
if (FORM[j][0].equals(FORM[i][0]) && FORM[0][k].equals(vt))
FORM[j][k] = oneLeftFirst.get(oneLeftKey);
}
}
}
}
// 打印预测表
printForm();
//存于Map的数据结构中用于快速查找
buildPreMap();
}
5 源代码
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
18
0- 0
已为社区贡献2条内容
所有评论(0)