服装外贸公司大量订单外发_东莞短视频制作公司_最有效的推广学校的方式_百度网盘24小时人工电话

一、实验目的

二、实验内容及步骤

三、程序分析

1. 需求分析

2. 功能分析

1. LL(1)文法功能分析

2. 算符优先文法功能分析

3. 信创分析-主要针对能力提升中国产操作系统上开发内容。

四、源代码

1. LL(1)文法代码

2. 算符优先文法

五、测试结果

1. LL(1)文法：

2. 算符优先文法：

一、实验目的

（1）通过完成LL(1)和SLR(1)(或者算符优先分析法)语法分析程序，了解自顶向下

和自底向上语法分析的过程。

（2）掌握两种语法分析程序的设计和实现过程。

二、实验内容及步骤

（1）根据实验二的结果，至少使用以上语法分析中的一种完成语法分析。

（2）实现一个 LL(1)和SLR(1)(或者算符优先分析法)语法分析程序，可以对用户输入的符号串进行分析。

（3）以上内容2选1完成，要求输出分析过程及分析结果。

能力提升：在国产操作系统上开发功能模块。

三、程序分析

1. 需求分析

本次实验需要实现 LL(1)语法分析程序和算符优先分析程序，要实现这两个程序，首先要了解这两个文法的分析原理，而程序的需求也就是将文法分析的各个步骤与过程实现出来。下面分别介绍两个文法的分析过程与原理：

（1）LL(1)语法分析程序需求分析：

LL(1)语法分析程序的分析步骤为：

①判断是否是有左递归和左公共因子：

LL(1)文法没有左递归与左公共因子，拿到一个文法首先开始检查有无左递归和左公因子，若有则需要改造该文法才能继续进行分析，若无则直接开始第四步的分析。

②消除左递归：

左递归包括直接左递归与间接左递归，直接左递归是可以直接推导出由自身作为开头的产生式，如A->A...，间接左递归是间接地推导出由自身作为开头的产生式，如A->B..., B->A...。

若是直接左递归，则按图3-1的方法直接消除，若是间接左递归，则先将其转换为直接左递归，再按直接左递归的方法进行消除，方法也如图3-1所示：

图3-1 消除左递归方法

③提取左公共因子：

形如A->abb..,A->acc...的规则即含有左公共因子，提取方法是保留公共因子，将剩下的其余部分换成一个新非终结符，再由该新非终结符推导出非公共因子的其余部分，具体过程如图3-2所示：

图3-2 提取左公因子方法

④求所有非终结符的FIRST集合：

FIRST集合即产生式右部的首终结符字符的集合。求非终结符x的FIRST集合，需要找产生式的左部为x的。例如规则A->aBb，若a为终结符，则FIRST(A)={a}；若a为非终结符，当a不为空串，则FIRST(A)=FIRST(a)-{ε}，若a为空串，则将空串代入，规则变为A->Bb，循环上述过程，FIRST(A)=FIRST(B)。

图3-3 求FIRST集合方法

⑤求所有非终结符的FOLLOW集合：

FOLLOW集合即产生式右部的尾终结符字符的集合。求非终结符x的FOLLOW集合，需要找产生式的右部出现了x的。

规则1：begin->#...#，即FOLLOW(begin) = { #, ...}

规则2：A->aB（B后为空），则FOLLOW(B) = FOLLOW(A)

规则3：A->aBc（B后不为空）

规则3.1：c是终结符，则FOLLOW(B) = {a}

规则3.2：c是非终结符，且c不为空串，则FOLLOW(B)=FIRST(B)-{ε}

规则3.3：c是非终结符，但c为空串，则代入空串到原式，继续判断上述规则。

图3-4 求FOLLOW集合方法

⑥求所有产生式的SELECT集合：

SELECT集合即是输入符号集（即当前读取的符号）与该产生式的右侧符号串能产生的符号的交集。求产生式的SELECT集合有两种情况：

规则1：A->a，a不为空串ε，则SELECT(A->a)=FIRST(a)

规则2：A->a，a为空串ε，则SELECT(A->a)=FOLLOW(A)

图3-5 求FOLLOW集合方法

⑦求相同左部的所有产生式的SELECT集合的交集：

SELECT集合即是输入符号集（即当前读取的符号）与该产生式的右侧符号串能产生的符号的交集，求相同左部的所有产生式的SELECT集合的交集可以判断当前文法是否是LL(1)文法。若所有相同左部的产生式的SELECT集合的交集都为空，则是LL(1)文法，否则不是LL(1)文法。

⑧根据SELECT集合构造预测分析表：

LL(1)的预测分析表由行-终结符，列-非终结符构成，若非终结符x的SELECT集合中包括哪些终结符，则将该产生式的右部写入表格中。

（2）算符优先分析程序需求分析：

算符优先语法分析程序的分析步骤为：

①判断是否是有相邻的非终结符：

算符优先文法没有相邻的非终结符，拿到一个文法首先开始检查有无相邻的非终结符，若有则该文法不是算符优先文法，若无则可以继续第二步分析。

②求所有非终结符的FIRSTVT和LASTVT集合：

非终结符x的FIRSTVT集合即x从左到右，经过1步或n步能推导出的所有第一个终结符的集合，例如B->b...，B->Cb...。

非终结符x的FIRSTVT集合即从x从右到左，经过1步或n步能推导出的所有最后一个终结符的集合，例如B->...b，B->...bC。

③求算符优先关系：

算符共有三种关系，分别为算符等于，算符大于和算符小于，需要注意的是，所有算符关系都不能调换顺序。

关系1：算符等于 a=b，即A->...ab... 或 A->aBb

关系2：算符大于 a>b，即A->...Bb...且B->...a或B->...aC，即a∈LASTVT(B)

关系3：算符大于 a<b，即A->...aB...且B->b...或B->Cb...，即b∈FIRSTVT(B)

④根据算符优先关系构造算符优先分析表：

算符优先分析表由行-终结符，列-终结符构成。

情况1：终结符a = 终结符b，则将 = 写入表格的a行b列中

情况2：终结符a > 终结符b，则将 > 写入表格的a行b列中

情况3：终结符a < 终结符b，则将 < 写入表格的a行b列中

2. 功能分析

1. LL(1)文法功能分析

系统的整体结构设计与需求分析中的一致，首先从grammer.txt中读取要分析的文法，接着程序通过main函数按顺序调用各种分析函数，处理后再提示用户输入要分析的字符串，并构造输入字符串分析表打印到控制台。具体的各类主要函数功能如表3-2-1所示：

表3-2-1 LL(1)文法系统主要函数功能表

函数名称	形参含义	功能详解
int main() 主函数	无	程序入口，按分析顺序调用各个函数。调用函数对数据进行初始化，打开输入文件并调用函数进行分割与分析等。分析结束后提示用户输入要分析的字符串，并构造输入字符串分析表打印到控制台。
init() 初始化函数	无	对程序所需要的各个集合，如非终结符VN和终结符VT进行初始化。
identifyVnVt (ArrayList<String> list) 识别终结符与非终结符	文法的产生式集合	1. 识别开始符号：第一个产生式的左部 2. 识别非终结符：左部与右部通过[->]进行分割获取，每个产生式的左部即为该文法的非终结符。 3. 识别终结符：相同左部的不同产生式通过[\|]进行分割获取，每一个产生式的每一个右部元素去除掉第二步中识别出的非终结符，即为该文法的终结符。
reformMap() 消除左递归和提取左公共因子	无	1. 产生式右部不为左递归：保持左部不变，右部的最后面添加一个[左部+[']]的字符。 2. 产生式右部为左递归：左递归标志设为true，左部替换为[左部+[']]的字符，右部保留除了第一个字符的剩下元素，再添加[左部+[']]的字符。 3. 左递归标志为true：更新产生式的键值对map，添加[左部+[']]作为新的非终结符VN。右部不递归的产生式右部元素再添加一个空串ε。 4. 提取左公共因子：左部保持不变，右部保留公共因子，在右部剩余部分删除，再添加为[左部+[']]。添加新产生式左部为[左部+[']]，右部为刚刚删除的非公共部分的其余部分。
getFirst() 求FIRST集合	无	1. 产生式第一个符号是终结符：加入FIRST集合 2. 产生式第一个符号是非终结符：递归查找该非终结符的 FIRST 集合，直到找到终结符或空串ϵ。
getFollow() 求FOLLOW集合	无	1. 开始符号start的FOLLOW集合：直接加入[#] 2. 非终结符后直接跟一个终结符: 该终结符加入非终结符的FOLLOW集合。 3. ...非终结符1非终结符2...：则FOLLOW(非终结符1) = FIRST(非终结符2) 4. 非终结符1->...非终结符2：则FOLLOW(非终结符2) = FOLLOW(非终结符1)

图3-2-1 LL(1)文法系统功能流程图

图3-2-2 识别VNVT函数功能流程图

图3-2-3 消除左递归函数功能流程图

图3-2-4 求FIRST集合函数功能流程图

2. 算符优先文法功能分析

表3-2-1 算符优先文法系统主要函数功能表

函数名称	形参含义	功能详解
int main() 主函数	无	程序入口，按分析顺序调用各个函数。调用函数获取终结符与非终结符，分割产生式等。分析结束后提示用户输入要分析的字符串，并构造输入字符串分析表打印到控制台。
getFirstVT(Character s, Set<Character> fvt) 计算FIRSTVT集合	当前要分析的左部文法符号	1. P->a...，产生式以终结符开头：终结符加入FIRSTVT集合。 2. P->Qa...，即先以非终结符开头，紧跟终结符：终结符加入FIRSTVT集合。 3. P->Q...，即以非终结符开头：该非终结符的FIRSTVT集合加入P的FIRSTVT集合。
getLastVT(Character s, Set<Character> lvt) 计算LASTVT集合	当前要分析的左部文法符号	1. P->....aW，即先以非终结符结尾，倒数第二位是终结符：终结符入LASTVT集合。 2. P->aQ \|，即先以非终结符结尾，前面是终结符，后面有分隔符：终结符入LASTVT集合，递归调用计算函数。 3. P->....Q，即以非终结符结尾：该非终结符LASTVT集合加入P的LASTVT集合。 4. P->....Q \|，即以非终结符结尾，后面有分隔符：非终结符LASTVT集合加入P的LASTVT集合，递归调用计算函数。
constructMatrix() 构造算符优先矩阵	无	1. P->...ab...，即当前字符后面有一个终结符字符，并且不是竖线（'\|'）: 将当前字符和后面的字符作为键，算符等于号（'='）作为值，存入matrix中。 2. P->....aBc，即当前字符后面有两个字符，并且第二个字符也是终结符，并且不是竖线（'\|'）：将当前字符和第二个字符作为键，将算符等于号（'='）作为值，存入matrix中。 3. P-> +T, 即当前字符后面有一个非终结符：该字符的FIRSTVT集合中的每个元素与当前字符作为键，将小于号（'<'）作为值，存入matrix中。 4. P->E+，即当前字符前面为非终结符，且不是起始符号：该字符的lastVt集合中的每个元素与当前字符作为键，将大于号（'>'）作为值，存入matrix中。

图3-2-5 算符优先文法系统功能流程图

图3-2-6 求FIRSTVT集合功能流程图

图3-2-7 求LASTVT集合功能流程图

3. 信创分析-主要针对能力提升中国产操作系统上开发内容。

1. 国产操作系统：

名称：麒麟操作系统

系统版本：20.03 (LTS-SP3)

内核： Linux 4.19.90

CPU：ARM 架构的 Kunpeng 920 处理器

桌面环境：UKUI

当前用户：root

2. 编译器：

名称：IntelliJ IDEA

版本：Community Edition 2018.3.6

图3-2-1 编译器配置

3. 开发步骤：

（1）安装idea

①在JetBrains官方网站下载IntelliJ IDEA，选择linux版本。

由于该操作系统的java版本太低，因此安装太高级的idea会无法使用，要安装较低版本的如2018.3.6。

②提取下载的压缩文件，输入命令：tar -zxvf ideaIC-2018.3.6.tar.gz

这里的[ideaIC-2018.3.6]应该换成自己下载的版本。

③给脚本执行权限，输入命令：

cd idea-IC-183.6156.11

sudo chmod a=+rx bin/idea.sh

bin/idea.sh

这里的[idea-IC-183.6156.11]依然应该换成自己下载的版本。

④安装idea，一直next就可以。

（2）打开idea

①打开解压出来的文件

②在该文件目录下打开终端

③在终端输入命令：bin/idea.sh

④成功打开idea

（3）在idea中运行程序

在国产操作系统上运行程序的结果和Windows上是一样的，这里就不演示了。

4. 开发中遇到的问题：

（1）无法安装vscode

原本开发消除注释的程序是用c++语言的写的，因此在国产操作系统上安装vscode。但由于该国产操作系统与其他操作系统的命令有部分不一样，例如apt-get命令不知为何使用不了，导致在诸如ubuntu操作系统上的安装流程，在麒麟操作系统上并不适用，无法成功安装。因此我将c++代码改为了java代码，并成功安装了idea进行编译。

（2）无法安装高版本的idea

一开始我直接安装了最高版本的idea，但在解压后安装idea时发现无法安装。

经查阅资料，发现是由于操作系统本身的java环境太低，与高版本的idea不适配，因为不同版本的idea有对应支持的java范围。因此我通过试验了几个版本的idea，找到2018版本的idea可以在操作系统上成功运行。

四、源代码

1. LL(1)文法代码

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.*;public class TetsLab3LL1 {// 文法定义文件public static final String PATH = "grammer.txt";// 从文件中读取得到的产生式集合public static ArrayList<String> produceList;// 文法开始符号private static String START;// 非终结符集合 终结符集合private static HashSet<String> VN, VT;// 产生式集合 key:产生式左边 value:产生式右边(含多条)private static HashMap<String, ArrayList<ArrayList<String>>> MAP;// "|" 分开的单条产生式对应的FIRST集合,用于构建LL1分析表private static HashMap<String, String> oneLeftFirst;// 总体的FIRST、FOLLOW集合private static HashMap<String, HashSet<String>> FIRST, FOLLOW;// LL1分析表的数组，用于输出private static String[][] FOCAST_TABLE;// LL1分析表的map，用于快速查找private static HashMap<String, String> preMap;public static void main(String[] args) {// 1. 初始化init();// 2. 将文件中的符号分类,并以key-value形式存于MAP中/* readFile(): 读取文件的内容，把文件的每一行存为一个字符串，放入ArrayList<String>中类似["S -> A B | C D","A -> a | ε","B -> b"]*/produceList = readFile(new File(PATH));identifyVnVt(produceList);// 3. 消除左递归reformMap();// 4. 求FIRST集合getFirst();// 5. 求FOLLOW集合getFollow();if (isLL1()) {// 6. 构建预测分析表preForm();System.out.println("请输入要分析的单词串:");Scanner in = new Scanner(System.in);printAutoPre(in.nextLine());in.close();}}// 1. 初始化集合private static void init() {VN = new HashSet<>(); // 非终结符VT = new HashSet<>(); // 终结符MAP = new HashMap<>(); // 产生式集合，内含多条产生式FIRST = new HashMap<>(); // FIRST集合FOLLOW = new HashMap<>(); // FOLLOW集合oneLeftFirst = new HashMap<>(); // 单条产生式的FIRST集合preMap = new HashMap<>(); // 预测分析表的map}// 2. 将语法的字符进行分类，分为开始符号（非终结符）和终结符等/*该方法接受一个语法列表，识别出非终结符（VN）和终结符（VT），将它们分别存储在集合VN和VT中，同时构建产生式的映射MAP*/private static void identifyVnVt(ArrayList<String> list) { // 传入文法的产生式集合START = String.valueOf(list.get(0).charAt(0)); // 文法的开始符号：文法中的第一个产生式的第一个字符for (String oneline : list) { // 处理文法list中的每个产生式oneline// 1. 分割该非终结符的产生式的左部和右部// 用 "→" 分割产生式 vnvt[0]是文法的左边（非终结符） vnvt[1]是文法的右边（终结符）String[] vnvt = oneline.split("→");// 2. 处理产生式左部String left = vnvt[0].trim(); // 产生式的左边 并消除左右空格VN.add(left); // 将产生式的左边添加到非终结符集合// 3. 处理产生式各个右部// 每个左部对应一个mapValue// 例如[//      [“A”，"a"], 代表A->Aa//      ["b"] 代表A->b//     ]ArrayList<ArrayList<String>> mapValue = new ArrayList<>();ArrayList<String> right = new ArrayList<>(); // 存储当前左部的其中一个右部，需要用[|]分割出来存入rightfor (int j = 0; j < vnvt[1].length(); j++) { // 遍历产生式的右部的每一个字符if (vnvt[1].charAt(j) == '|') { // 用 “|” 分割产生式的右部// 把每个右部传入VT终结符集合，把某个左部对应的所有右部集合加入mapValue// （这次移入会把终结符和非终结符一起移入，非终结符会在后续删掉）addRightToVTAndMapValue(right, mapValue);right = new ArrayList<>(); // 清空rightcontinue;}// 如果产生式某字符的左边含有中文或英文的单引号，则视为一个整体常量// 如果当前字符后面紧跟一个单引号（' 或 ’），则将这两个字符视为一个整体，并将它们添加到 right 中。// 如果不是，则只添加当前字符。
//                if (j + 1 < vnvt[1].length() && (vnvt[1].charAt(j + 1) == '\'' || vnvt[1].charAt(j + 1) == '’')) {
//                    right.add(new StringBuilder().append(vnvt[1].charAt(j)).append(vnvt[1].charAt(j + 1)).toString());
//                    j++;
//                }else { // 如果没有遇到分割符[|]right.add(String.valueOf(vnvt[1].charAt(j))); // 将字符添加到right}}addRightToVTAndMapValue(right, mapValue); // 最后一次遍历不会遇到[|]，再add一次// 4. 把处理好的左部及对应的各个右部添加到MAP// 以左部非终结符left作为键，以各个右部形成的列表作为值// 例如A->Aa|b，最终map里就是key-A，value-[["A","a"],["b"]]MAP.put(left, mapValue);}VT.removeAll(VN); // 循环结束后，找到所有的非终结符了，再从终结符集合中移除非终结符// 打印Vn非终结符、Vt终结符System.out.println("\n非终结符集:\t{" + String.join("、", VN) + "}");System.out.println("终结符集:\t{" + String.join("、", VT) + "}\n");}// 2.1 从文法文件中读取语法，并将文法的每一行存放到list集合中public static ArrayList<String> readFile(File file) {System.out.println("分析的文法为：");ArrayList<String> result = new ArrayList<>(); // 要返回的存储了文件每一行的string集合try {BufferedReader br = new BufferedReader(new FileReader(file)); // 保存文件内容到缓存区String s; // 当前读取的一行while ((s = br.readLine()) != null) { // 逐行读入文件每行System.out.println("\t" + s);result.add(s.trim()); // 把当前行消除空格并存入result}br.close();}catch (Exception e) {System.out.println(e.getMessage());}return result;}// 2.2 添加 终结符VT 和 映射值mapValueprivate static void addRightToVTAndMapValue(ArrayList<String> right, ArrayList<ArrayList<String>> mapValue) {VT.addAll(right); // VT终结符集合 加入right右部集合中的每个元素（这次移入会把终结符和非终结符一起移入，非终结符会在后续删掉）mapValue.add(new ArrayList<>(right)); // mapVlue列表加入right集合 并且这个集合是新new的 修改right集合不会影响mapVaue列表}// 3. 消除左递归private static void reformMap() {boolean isEditMap = false; // 标志MAP是否被修改Set<String> keys = new HashSet<>(MAP.keySet()); // 保存MAP中所有去重的key【即非终结符】Iterator<String> it = keys.iterator(); // keys的迭代器ArrayList<String> nullRight = new ArrayList<>(); // 空串右部nullRight.add("ε"); // ε是空串while (it.hasNext()) { // 还有下一个非终结符String left = it.next(); // 当前产生式的左部非终结符1boolean isReflag = false; // 标志是否有左递归ArrayList<ArrayList<String>> rightList = MAP.get(left); // 产生式原本的右部列表，例如[ ["S","a","c"], ["b"] ]，用来遍历ArrayList<String> noReRightElement = new ArrayList<>(); // 不递归的产生式的右部元素ArrayList<ArrayList<String>> yesReRightList = new ArrayList<>(); // 递归的产生式的右部列表// 消除直接左递归for (ArrayList<String> strings : rightList) { // 遍历当前产生式的所有右部列表，strings例如["S","a","c","b"]ArrayList<String> yesReRightElement = new ArrayList<>(); // 递归的产生式的右部元素if (strings.get(0).equals(left)) { // 该右部是左递归的：右部的第一个字符是左部，例如["S","a","c"]中的"S"isReflag = true; // 设置左递归标志为truefor (int j = 1; j < strings.size(); j++) { // 继续遍历剩下的右部yesReRightElement.add(strings.get(j)); // 递归的产生式的右部元素：加入除了左部（第一个符）的所有右部，如["a","c"]}yesReRightElement.add(left + "'"); // 递归的产生式的右部元素：继续加入产生式左部的[']版。如["a","c","S'"]yesReRightList.add(yesReRightElement); // 递归的产生式的右部列表：放入递归的产生式的新右部[["a","c","S'"]]}else { // 该右部不是左递归的noReRightElement.addAll(strings); // 不递归的产生式的右部元素：加入原产生式的右部例如["b"]noReRightElement.add(left + "'"); // 不递归的产生式的右部元素：继续加入左部的[']版，例如["b","S'"]}}if (isReflag) { // 如果存在左递归，则更新MAPisEditMap = true; // 更新MAP的标志为trueyesReRightList.add(nullRight); // 递归的产生式的右部列表：继续加入空串右部元素["ε"], 例如[["a","c","S'"]，["ε"]]MAP.put(left + "'", yesReRightList); // 加入递归的产生式，左部是原左部加[']，右边是递归的产生式的右部列表 map如S'->acS'| εVN.add(left + "'"); // 加入新的非终结符到VN集合VT.add("ε"); // 加入新的[ε]空串到VT集合ArrayList<ArrayList<String>> newLeftOld = new ArrayList<>(); // 存放不递归的新产生式 如S->bS'newLeftOld.add(noReRightElement); // 存放旧的产生式MAP.put(left, newLeftOld); // 更新原产生式}}// 如果文法被修改，则输出修改后的文法if (isEditMap) {System.out.println("消除左递归后的文法：");Set<String> kSet = new HashSet<>(MAP.keySet()); // 找到文法的所有非终结符for (String k : kSet) { // 遍历该文法每个非终结符ArrayList<ArrayList<String>> rightList = MAP.get(k); // 找到该非终结符对应的右部列表 如[["a","c","S'"]，["ε"]]System.out.print("\t" + k + "→");for (int i = 0; i < rightList.size(); i++) { // 遍历右部列表 如[["a","c","S'"]，["ε"]]System.out.print(String.join("", // 把该右部列表的第i个右部元素拼接为一个字符串 如["a","c","S'"]拼接为["acS'"]rightList.get(i).toArray(new String[rightList.get(i).size()])));if (i + 1 < rightList.size()) { // 该右部列表还有下一个右部元素System.out.print("|"); // 用[|]分隔}}System.out.println();}}//        MAP.toString(); // 输出新MAP}// 5. 求FIRST集合/*遇到终结符：加入FIRST集合遇到非终结符：递归，求该非终结符的FIRST集合，即为该终结符的FIRST集合*/private static void getFirst() {System.out.println("\n该文法的FIRST集合：");for (String vn : VN) { // 遍历每个非终结符HashSet<String> FIRST_List = new HashSet<>(); // 当前非终结符vn的FIRST集合，包括该vn的各个产生式各自的FIRST集合ArrayList<ArrayList<String>> rightList = MAP.get(vn); // 当前非终结符vn对应的右部列表 如[["a","c","S'"], ["ε"]]// System.out.println(key+":");for (ArrayList<String> rightListElement : rightList) { // 遍历每个右部列表的每个右部元素（产生式） 如["a","c","S'"]// 当前非终结符的当前产生式的FIRST集合 即组成当前非终结符vn的FIRST集合的一部分HashSet<String> FIRST_List_One = new HashSet<>();// 将右部列表中的单个元素拼接成字符串 如["a","c","S'"]拼接为"acS"String oneRightElement = String.join("",rightListElement.toArray(new String[rightListElement.size()]));// System.out.println("oneLeft: "+oneLeft);if (VT.contains(rightListElement.get(0))) { // 如果产生式第一个符号是终结符 则该符号是FIRST集合的符号FIRST_List.add(rightListElement.get(0)); // 将该符号加入该产生式的FIRST集合FIRST_List_One.add(rightListElement.get(0));oneLeftFirst.put(vn + "$" + rightListElement.get(0), vn + "→" + oneRightElement); // 添加到预测分析表中}else { // 如果产生式第一个符号是非终结符// 标记产生式中的符号是否为非终结符，是则检查下一个字符boolean[] isVn = new boolean[rightListElement.size()];isVn[0] = true; // 第一个为非终结符int p = 0;while (isVn[p]) { // 循环检查产生式中的每个符号 直到找到终结符或者空串（ε）。if (VT.contains(rightListElement.get(p))) { // 1. 如果遇到终结符FIRST_List.add(rightListElement.get(p)); // 则把该终结符加入当前非终结符的FIRST集合中FIRST_List_One.add(rightListElement.get(p)); // 把该终结符加入当前产生式的FIRST集合中oneLeftFirst.put(vn + "$" + rightListElement.get(p), vn + "→" + oneRightElement); // 添加到预测分析表中break; // 找到终结符了，退出循环}// 2. 如果不是终结符String vnGo = rightListElement.get(p); // 当前符号是非终结符，转换为找该非终结符的FIRST集合Stack<String> stack = new Stack<>();stack.push(vnGo); // 将当前非终结符放入栈中while (!stack.isEmpty()) { // 如果栈不为空：是非终结符 转换为找该终结符的FIRST集合ArrayList<ArrayList<String>> listGo = MAP.get(stack.pop()); // 获取该非终结符vnGo的右部for (ArrayList<String> listGoCell : listGo) { // 遍历该非终结符vnGo的右部的每个元素if (VT.contains(listGoCell.get(0))) { // 如果第一个字符是终结符 可能1：空 可能2：终结符if (listGoCell.get(0).equals("ε")) { // 可能1：空 可以查询下一个字符if (!vn.equals(START)) { // 如果当前的终结符不是开始符号（开始符号不能推出空）FIRST_List.add(listGoCell.get(0)); // 把空串加入FIRST集合FIRST_List_One.add(listGoCell.get(0));oneLeftFirst.put(vn + "$" + listGoCell.get(0), vn + "→" + oneRightElement); // 添加到预测分析表中}if (p + 1 < isVn.length) { // 继续处理下一个字符isVn[p + 1] = true;}}else { // 可能2：终结符 加入对应的FIRST集合FIRST_List.add(listGoCell.get(0));FIRST_List_One.add(listGoCell.get(0));oneLeftFirst.put(vn + "$" + listGoCell.get(0), vn + "→" + oneRightElement); // 添加到预测分析表中}}else { // 不是终结符号，入栈，再转换为找该非终结符的FIRST集合 以此递归stack.push(listGoCell.get(0));}}}p++;if (p > isVn.length - 1)break;}}// 保存当前非终结符vn的产生式oneRightElement的FIRST元素到总FIRST集合中// key为当前产生式 如A->acS value为当前产生式的FIRST集合FIRST.put(vn + "→" + oneRightElement, FIRST_List_One);}FIRST.put(vn, FIRST_List); // 添加到总的FIRST集合中// 输出key的FIRST集合System.out.println("\tFIRST(" + vn + ")={" + String.join("、",FIRST_List.toArray(new String[FIRST_List.size()])) + "}");}}// 求FOLLOW集合private static void getFollow() {System.out.println("\n该文法的FOLLOW集合：");// 遍历非终结符集合的迭代器Iterator<String> it = VN.iterator();// 创建一个HashMap keyFollow 用于存储每个非终结符的FOLLOW集合HashMap<String, HashSet<String>> keyFollow = new HashMap<>();// 存放特殊组合 如A->...B 或者 A->...Bε（结尾是非终结符/结尾是空串）ArrayList<HashMap<String, String>> vn_VnList = new ArrayList<>();// 存放vn_VnList的左边和右边HashSet<String> vn_VnListLeft = new HashSet<>();HashSet<String> vn_VnListRight = new HashSet<>();// 开始符号加入#，初始化keyFollowkeyFollow.put(START, new HashSet() {private static final long serialVersionUID = 1L;{add("#");}});// 遍历非终结符集合while (it.hasNext()) { // 还有非终结符String currentVN = it.next(); // key为当前的非终结符ArrayList<ArrayList<String>> rightList = MAP.get(currentVN); // rightList为当前非终结符的右部 如[["a","c","S'"], ["ε"]]ArrayList<String> rightListOne; // rightListOne为当前非终结符的右部的其中一个右部元素 如["a","c","S'"]// 如果key的FOLLOW集合不存在，则初始化if (!keyFollow.containsKey(currentVN)) {keyFollow.put(currentVN, new HashSet<>());}
//            keyFollow.toString();// 遍历该非终结符的所有产生式for (ArrayList<String> strings : rightList) {rightListOne = strings; // rightListOne为当前非终结符的右部的其中一个右部元素 如["a","c","S'"]// (1) 如果非终结符号的后面找到了一个终结符for (int j = 1; j < rightListOne.size(); j++) {HashSet<String> set = new HashSet<>(); // 当前产生式的FOLLOW集合if (VT.contains(rightListOne.get(j))) { // 如果找到一个终结符set.add(rightListOne.get(j)); // 把该终结符加入到当前产生式的FOLLOW集合if (keyFollow.containsKey(rightListOne.get(j - 1)))set.addAll(keyFollow.get(rightListOne.get(j - 1))); // 把上一个非终结符的FOLLOW集合加入当前的FOLLOW集合keyFollow.put(rightListOne.get(j - 1), set); // 把当前产生式的FOLLOW集合加入到前一个非终结符的FOLLOW集合}}// (2) 找...非终结符1非终结符2...组合// 则FOLLOW(非终结符1) = FIRST(非终结符2)for (int j = 0; j < rightListOne.size() - 1; j++) {HashSet<String> set = new HashSet<>();if (VN.contains(rightListOne.get(j)) && VN.contains(rightListOne.get(j + 1))) {set.addAll(FIRST.get(rightListOne.get(j + 1)));set.remove("ε");if (keyFollow.containsKey(rightListOne.get(j)))set.addAll(keyFollow.get(rightListOne.get(j)));keyFollow.put(rightListOne.get(j), set);}}// (3) A->...B 或者 A->...Bε(可以有n个ε)的组合存起来for (int j = 0; j < rightListOne.size(); j++) {HashMap<String, String> vn_Vn;if (VN.contains(rightListOne.get(j)) && !rightListOne.get(j).equals(currentVN)) {// 是VN且A不等于Bboolean isAllNull = false;// 标记VN后是否为空if (j + 1 < rightListOne.size())// 即A->...Bε(可以有n个ε)for (int k = j + 1; k < rightListOne.size(); k++) {if ((FIRST.containsKey(rightListOne.get(k)) && FIRST.get(rightListOne.get(k)).contains("ε"))) {// 如果其后面的都是VN且其FIRST中包含εisAllNull = true;} else {isAllNull = false;break;}}// 如果是最后一个为VN,即A->...Bif (j == rightListOne.size() - 1) {isAllNull = true;}if (isAllNull) {vn_VnListLeft.add(currentVN);vn_VnListRight.add(rightListOne.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(currentVN)) {vn_VnListCell.put(currentVN, rightListOne.get(j));vn_VnList.set(x, vn_VnListCell);isHaveAdd = true;break;} else {// 去重if (vn_VnListCell.get(currentVN).equals(rightListOne.get(j))) {isHaveAdd = true;break;}continue;}}if (!isHaveAdd) {// 如果没有添加，表示是新的组合vn_Vn = new HashMap<>();vn_Vn.put(currentVN, rightListOne.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);// 处理 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加上左边的FOLLOWif (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()])) + "}");}}/*判断是不是LL(1)文法1. 无左递归：文法不能直接或间接地包含左递归。2. SELECT集合的交集为空：对于某个非终结符 A，如果 A 有两个产生式 A -> α 和 A -> β，那么必须满足：（1）如果 α 和 β 都能推导出空串（即包含 ε），则 FIRST(α) 与 FOLLOW(A) 必须没有交集。（2）如果 α 和 β 不都能推导出空串，则 FIRST(α) 和 FIRST(β) 必须没有交集。*/private static boolean isLL1() {System.out.println("\n判断是否是LL(1)文法：");boolean flag = true; // 是否是LL(1)文法的标志for (String key : VN) { // 遍历非终结符ArrayList<ArrayList<String>> list = MAP.get(key);// 对于每一个非终结符 key，获取其产生式列表 listif (list.size() > 1) { // 如果该终结符的产生式有两个以上，则判断SELECT集合的交集for (int i = 0; i < list.size(); i++) {String a = String.join("", list.get(i));for (int j = i + 1; j < list.size(); j++) {String b = String.join("", list.get(j));// 对于每一对产生式，如果其中一个是空产生式（ε），则要求该非终结符对应的 FIRST 集合和 FOLLOW 集合的交集为空if (a.equals("ε") || b.equals("ε")) {// (1)若a＝ε,则判断FOLLOW(A) ∩ FIRST(b) = φ 相当于FOLLOW(Key) ∩ FIRST(b) = φ// (2)若b＝ε, 则判断FIRST(a) ∩ FOLLOW(B)=φ 相当于FIRST(a) ∩ FOLLOW(Key) = φSet<String> retainSet = new HashSet<>(FIRST.get(key));if (FOLLOW.get(key) != null) {retainSet.retainAll(FOLLOW.get(key)); // 求A的FOLLOW集合与FIRST集合的交集}if (!retainSet.isEmpty()) { // 如果交集不为空，说明存在冲突flag = false;// 不是LL(1)文法，输出FIRST(a)FOLLOW(a)的交集printIntersectionSet("\tFIRST(" + key + ") ∩ FOLLOW(" + key + ")", retainSet);break;} else {System.out.println("\tFIRST(" + key + ") ∩ FOLLOW(" + key + ") = φ");}//如果交集不为空，说明存在冲突，输出交集并将标志 flag 设置为 false}else { // (2)如果a和b都不为空 则要FIRST(a) ∩ FIRST(b) = φSet<String> retainSet = new HashSet<>(FIRST.get(key + "→" + a));retainSet.retainAll(FIRST.get(key + "→" + b));if (!retainSet.isEmpty()) { // 1. 如果FIRST(a)和FIRST(b)的交集不为空flag = false;// 不是LL(1)文法，输出FIRST(a)FIRST(b)的交集printIntersectionSet("\tFIRST(" + a + ") ∩ FIRST(" + b + ")", retainSet);break;}else { // 2. 如果FIRST(a)和FIRST(b)的交集为空System.out.println("\tFIRST(" + a + ") ∩ FIRST(" + b + ") = φ");}}}}}}if (flag)System.out.println("\t是LL(1)文法,继续分析!");elseSystem.out.println("\t不是LL(1)文法,退出分析!");return flag;}/*输出*/private static void printIntersectionSet(String prefix, Set<String> set) {System.out.println(prefix + " = {" + String.join("、", set) + "}");}/*构建预测分析表FORM遍历非终结符和终结符集合，利用 oneLeftFirst 和 FOLLOW 集合填充预测分析表*/private static void preForm() {HashSet<String> setVT = new HashSet<>(VT); // 终结符集setVTsetVT.remove("ε"); // 去除空串 "ε"FOCAST_TABLE = new String[VN.size() + 1][setVT.size() + 2]; // 预测分析表：行是非终结符，列是终结符的二维数组Iterator<String> itVn = VN.iterator(); // 非终结符集VN的迭代器Iterator<String> itVt = setVT.iterator(); // 终结符集VT的迭代器// （1）第一个循环遍历 FORM，根据迭代器填充第一行和第一列// 同时填充不是空串的，即FIRST集合for (int i = 0; i < FOCAST_TABLE.length; i++) {for (int j = 0; j < FOCAST_TABLE[0].length; j++) {if (i == 0 && j > 0) { // 第一行 填充终结符VTif (itVt.hasNext()) {FOCAST_TABLE[i][j] = itVt.next();}if (j == FOCAST_TABLE[0].length - 1) // 最后一列 加入 [#]FOCAST_TABLE[i][j] = "#";}if (j == 0 && i > 0) { // 第一列 填充非终结符VNif (itVn.hasNext())FOCAST_TABLE[i][j] = itVn.next();}if (i > 0 && j > 0) { // 不是第一行和第一列，且不是空串（则填充FIRST集合）String oneLeftKey = FOCAST_TABLE[i][0] + "$" + FOCAST_TABLE[0][j];// 作为key查找其First集合FOCAST_TABLE[i][j] = oneLeftFirst.get(oneLeftKey);}}}// （2）第二个循环 处理空串的情况 填充 FOLLOW 集合for (int i = 1; i < FOCAST_TABLE.length; i++) {String oneLeftKey = FOCAST_TABLE[i][0] + "$ε"; // 非终结符+"$ε"if (oneLeftFirst.containsKey(oneLeftKey)) { // 如果有空产生式 则填充FOLLOW集合HashSet<String> follows = FOLLOW.get(FOCAST_TABLE[i][0]); // 获取空产生式的FOLLOW集合for (String vt : follows) { // 遍历FOLLOW集合中的元素（终结符）for (int j = 1; j < FOCAST_TABLE.length; j++)for (int k = 1; k < FOCAST_TABLE[0].length; k++) {if (FOCAST_TABLE[j][0].equals(FOCAST_TABLE[i][0]) && FOCAST_TABLE[0][k].equals(vt)) { // 找到要填充的行、列FOCAST_TABLE[j][k] = oneLeftFirst.get(oneLeftKey); // 对应位置填写当前key的产生式}}}}}// 打印预测表printForm();//将预测分析表的数据存储到Map中，以便于快速查找buildPreMap();}// 打印预测表private static void printForm() {System.out.println("\n该文法的预测分析表为：");for (String[] line : FOCAST_TABLE) {for (String column : line) {System.out.print((column != null ? column : " ") + "\t"); // 若不为空则输出当前行所在的列的内容}System.out.println();}System.out.println();}// 根据FROM建立Mapprivate static void buildPreMap() {for (int i = 1; i < FOCAST_TABLE.length; i++) {for (int j = 1; j < FOCAST_TABLE[0].length; j++) {if (FOCAST_TABLE[i][j] != null) {String[] tmp = FOCAST_TABLE[i][j].split("→");preMap.put(FOCAST_TABLE[i][0] + FOCAST_TABLE[0][j], tmp[1]);}}}}// 根据LL(1)分析表来分析输入串public static void printAutoPre(String str) {System.out.println(str + "的分析过程:");Deque<String> queue = new LinkedList<>(); // 队列queue 用于存储单词串的分割for (int i = 0; i < str.length(); i++) {StringBuilder t = new StringBuilder().append(str.charAt(i));if (i + 1 < str.length() && (str.charAt(i + 1) == '\'' || str.charAt(i + 1) == '’')) {t.append(str.charAt(i + 1)); // 将输入的单词串按照一定规则分割成单个符号，并存储在队列中，同时在符号后面的字符是 ' 或 ’ 时，将其合并。i++;}queue.offer(t.toString());}queue.offer("#"); // 将结束符 # 加入队列末尾。// 分析栈Deque<String> stack = new LinkedList<>();stack.push("#"); // "#"开始stack.push(START); // 初态为开始符号boolean isSuccess = false; // 分析成功的标志int step = 1; // 步骤数初始为1while (!stack.isEmpty()) { // 进行循环分析，直到分析栈为空String left = stack.peek();String right = queue.peek(); // 检查分析栈栈顶 left 和队列头部 right// （1）分析成功if (left.equals(right) && right.equals("#")) { // 栈和输入串相等，且输入串为#isSuccess = true;System.out.println((step++) + "\t#\t#\t" + "分析成功");break; // 结束循环}// （2）规约if (left.equals(right)) { // 栈顶和当前符号匹配，均为终结符System.out.println((step++) + "\t" + toString(stack) + "\t" + toString(queue) + "\t\"" + left + "\"\t匹配");stack.pop(); // 出栈queue.poll(); // 出队列continue; // 继续}// （3）产生式推导if (preMap.containsKey(left + right)) {System.out.println((step++) + "\t" + toString(stack) + "\t" + toString(queue) + "\t产生式" + left + "→"+ preMap.get(left + right));stack.pop();String tmp = preMap.get(left + right); // 从预测分析表 preMap 中查找对应产生式，输出相应信息，将产生式逆序入栈for (int i = tmp.length() - 1; i >= 0; i--) { // 逆序进栈StringBuilder t = new StringBuilder();if (tmp.charAt(i) == '\'' || tmp.charAt(i) == '’') {t.append(tmp.charAt(i-1)).append(tmp.charAt(i));i--;}else {t.append(tmp.charAt(i));}if (!t.toString().equals("ε")) { // 不为空串则入栈stack.push(t.toString());}}continue;}//（4）其他情况：不规约，无推导，不成功，则直接退出break;}if (!isSuccess) { // 如果没有成功就中途退出System.out.println((step++) + "\t#\t#\t" + "分析失败");}}// 将集合的转化为字符串private static String toString(Collection<String> collection) {return String.join("", collection.toArray(new String[0]));}
}

2. 算符优先文法

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.*;
import java.util.stream.Collectors;public class TestLab3SFYX {//FIRSTVT集合private static Map<Character, Set<Character>> firstVt = new HashMap<>();//LASTVT集合private static Map<Character, Set<Character>> lastVt = new HashMap<>();//输入的文法private static List<String> input = new ArrayList<>();//终结符private static Set<Character> End = new LinkedHashSet<>();//非终结符private static Set<Character> NoEnd = new LinkedHashSet<>();//算符矩阵private static Map<String, Character> matrix = new HashMap<>();//输入流private static Scanner in = new Scanner(System.in);//文法的左右分割一一对应private static Map<Character, List<String>> produce = new HashMap<>();// TODO 主方法public static void main(String[] args) {String path = "grammer2.txt";int flag = 1;while (flag != 0) {input = readFile(new File(path));if (isOperator()) {System.out.println("此文法是算符文法!");flag = 0;} else {System.out.println("此文法不是算符文法!请重新输入:");input.clear();}}//获取终结符getVT();//获取非终结符getVN();//分离文法getProduce();//计算并显示FirstVT、LastVT集合DisplayFirstVT_LastVT();//构造算符优先矩阵并打印constructMatrix();//分析句子过程analysisProcess();}//TODO 读取文法文件public static ArrayList<String> readFile(File file) {System.out.println("从文件读入的文法为:");// 输出读取的文法内容ArrayList<String> result = new ArrayList<>();try {BufferedReader br = new BufferedReader(new FileReader(file));String s;while ((s = br.readLine()) != null) {System.out.println("\t" + s);result.add(s.trim());}br.close();} catch (Exception e) {System.out.println(e.getMessage());// 如果发生异常，输出错误信息}return result;}// TODO 判断是否是算符文法/*** 判断其是不是算符文法* 遍历每个产生式，检查是否有连续的非终结符相连，如果有，则不是算符文法* 如果没有连个连续非终结符号相连的就是算符优先文法,返回判断结果*/private static boolean isOperator() {int i;for (i = 0; i < input.size(); i++) {for (int j = 0; j < input.get(i).length() - 1; j++) {String str = input.get(i);if (str.charAt(j) >= 65 && str.charAt(j) <= 90) {if ((str.charAt(j + 1) >= 65 && str.charAt(j + 1) <= 90)) {return false;}}}}return true;}// TODO 求终结符/*** 获取文法中的终结符* 遍历每个产生式，将终结符添加到End集合中*/private static void getVT() {for (String temp : input) {for (int j = 2; j < temp.length(); j++) {if (temp.charAt(j) < 65 || temp.charAt(j) > 90 && temp.charAt(j) != '|') {End.add(temp.charAt(j));}}}End.add('#');}// TODO 求非终结符/*** 获取文法中的非终结符* 遍历每个产生式，将非终结符添加到NoEnd集合中*/private static void getVN() {for (String temp : input) {for (int j = 2; j < temp.length(); j++) {if (temp.charAt(j) >= 65 && temp.charAt(j) <= 90) {NoEnd.add(temp.charAt(j));}}}}//TODO 分离文法/*** 分离文法，将每一行的文法分离成左右两部分* 将左部分作为键，右部分作为值存入produce集合中* 将每一行的文法分离,如E->E+T|T分离成E和E+T,T*/private static void getProduce() {for (String s : input) {List<String> list = new ArrayList<>();String str = s;StringBuffer a = new StringBuffer();for (int j = 2; j < str.length(); j++) {if (str.charAt(j) != '|') {a.append(str.charAt(j));} else {list.add(a.toString());a.delete(0, a.length());//清空a}}list.add(a.toString());produce.put(str.charAt(0), list);}}// TODO 计算firstVt集合/***  遍历文法，根据文法规则计算FirstVT集合,结果存储在fvt参数中* 获得firstVt集合*/private static void getFirstVT(Character s, Set<Character> fvt) {String str = null;int i = 0;for (i = 0; i < input.size(); i++) {if (input.get(i).charAt(0) == s) {str = input.get(i);}}if (str == null)return;//logger.info("求firstVt集合：" + str);boolean flag = true;for (i = 2; i < str.length(); i++){if (str.charAt(i) < 65 || str.charAt(i) > 90){//P->a.....，即以终结符开头，该终结符入Firstvtif ((String.valueOf(str.charAt(i - 1)).equals("→")) || str.charAt(i - 1) == '|') {fvt.add(str.charAt(i));flag = false;}}if (str.charAt(i) == '|')flag = true;//P->Qa....，即先以非终结符开头，紧跟终结符，则终结符入Firstvtif (str.charAt(i) >= 65 && str.charAt(i) <= 90){int index = i + 1;if (index < str.length()){if ((str.charAt(index) < 65 || str.charAt(index) > 90)&& End.contains(str.charAt(index)) && flag){fvt.add(str.charAt(index));}}}//若有P->Q.....，即以非终结符开头，该非终结符的Firstvt加入P的Firstvtif ((str.charAt(i - 1) == '|' || String.valueOf(str.charAt(i-1)).equals("→"))&& str.charAt(i) >= 65 && str.charAt(i) <= 90) {//E->Eif (str.charAt(i) == str.charAt(0)) {continue;}//递归//E->P//logger.info("firstVt集合进入递归");getFirstVT(str.charAt(i), fvt);}}}// TODO 计算lastVt集合/*** 遍历文法，根据文法规则计算LastVT集合,结果存储在lvt参数中* 获得lastVt集合*/private static void getLastVT(Character s, Set<Character> lvt) {String str = null;int i;for (i = 0; i < input.size(); i++) {if (input.get(i).charAt(0) == s) {str = input.get(i);}}if (str == null)return;for (i = 2; i < str.length(); i++) {if (str.charAt(i) < 65 || str.charAt(i) > 90) {//P->....aW，即先以非终结符结尾，前面是终结符，则终结符入Lastvt,Q处于产生式最后一位的情况if (i == str.length() - 1 ||(i == str.length() - 2 &&str.charAt(i + 1) >= 65 && str.charAt(i + 1) <= 90 &&str.charAt(i) != '|' && !String.valueOf(str.charAt(i)).equals("→"))) {lvt.add(str.charAt(i));}if (i < str.length() - 2) {//P->aQ | ，即先以非终结符结尾，前面是终结符，则终结符入Lastvtif (str.charAt(i + 1) == '|' ||(str.charAt(i + 2) == '|' && str.charAt(i + 1) >= 65 && str.charAt(i + 1) <= 90)) {lvt.add(str.charAt(i));}}} else {//P->....Q，即以非终结符结尾，该非终结符的Lastvt入P的Lastvtif (i == str.length() - 1) {if (str.charAt(i) == str.charAt(0)) {continue;}getLastVT(str.charAt(i), lvt);} else if (str.charAt(i + 1) == '|') {if (str.charAt(i) == str.charAt(0)) {continue;}//P->....Q，即以非终结符结尾，该非终结符的Lastvt入P的LastvtgetLastVT(str.charAt(i), lvt);}}}}/*** 显示FirstVT集合和LastVT集合* 遍历文法，计算并显示每个非终结符的FirstVT和LastVT集合*///TODO 显示firstVt集合和lastVt集合----一次优化private static void DisplayFirstVT_LastVT() {for (String value : input) {Set<Character> fvt = new HashSet<>();getFirstVT(value.charAt(0), fvt);firstVt.put(value.charAt(0), fvt);Set<Character> lvt = new HashSet<>();getLastVT(value.charAt(0), lvt);lastVt.put(value.charAt(0), lvt);}displaySet("firstVt", firstVt);displaySet("lastVt", lastVt);}//输出private static void displaySet(String setName, Map<Character, Set<Character>> set) {System.out.printf("%s集合如下:\n", setName);for (Map.Entry<Character, Set<Character>> entry : set.entrySet()) {String valueString = String.join(",", entry.getValue().stream().map(String::valueOf).collect(Collectors.toList()));System.out.printf("%s(%s): {%s}\n", setName, entry.getKey(), valueString);}}/*** 错误*/public static void partError() {matrix.put(")(", 'b');matrix.put("((", 'b');matrix.put("(#", 'a');}//TODO 构造算符优先矩阵并打印/*** 构造算符优先矩阵并打印* 用Map<String,Character>存,String中存优先变得行值和列值,* Character表示String中所存行列的大小关系如"++"表示行为'+',列为'+'的时候,关系为Character中的值* 遍历文法，根据文法规则构造算符优先矩阵* 结果存储在matrix集合中*/private static void constructMatrix() {for (int i = 0; i < input.size(); i++) {String str = input.get(i);for (int j = 2; j < input.get(i).length(); j++) {//每个产生式的字符，判断是否为终结符并且不是竖线（'|'）if ((str.charAt(j) < 65 || str.charAt(j) > 90) && (str.charAt(j) != '|')) {//当前字符后面有一个字符，并且该字符也是终结符,并且不是竖线（'|'），将当前字符和后面的字符作为键，// 将等于号（'='）作为值，存入matrix中。P->...ab....if (j < str.length() - 1&& (str.charAt(j + 1) < 65 || str.charAt(j + 1) > 90)&& (str.charAt(j + 1) != '|')) {String temp = str.charAt(j) + "" + str.charAt(j + 1);matrix.put(temp, '=');} else {//当前字符后面有两个字符，并且第二个字符也是非终结符，并且不是竖线（'|'），将当前字符和第二个字符作为键，//将等于号（'='）作为值，存入matrix中。//如 P->....aBcif (j < str.length() - 2&& (str.charAt(j + 2) < 65 || str.charAt(j + 2) > 90)&& (str.charAt(j + 2) != '|')) {matrix.put(str.charAt(j) + "" + str.charAt(j + 2), '=');}}//当前字符后面有一个字符，并且该字符是非终结符，将该字符的firstVt集合中的每个元素与当前字符作为键，// 将小于号（'<'）作为值，存入matrix中。  如 +T 则有 + < FirstV(T)if (j < str.length() - 1 && str.charAt(j + 1) >= 65 && str.charAt(j + 1) <= 90) {Set<Character> coll = firstVt.get(str.charAt(j + 1));for (Character value : coll) {//logger.info("创建矩阵测试2："+str.charAt(j+1) + ":" + value);matrix.put(str.charAt(j) + "" + value, '<');}}//当前字符前面不是产生式的起始符号，并且当前字符前面的字符是非终结符，将该字符的lastVt集合中的每个元素与当前字符作为键，// 将大于号（'>'）作为值，存入matrix中。  如 E+ 则有 LastV(E) > +if (j - 1 != 1 && str.charAt(j - 1) >= 65 && str.charAt(j - 1) <= 90) {Set<Character> coll = lastVt.get(str.charAt(j - 1));for (Character value : coll) {matrix.put(value + "" + str.charAt(j), '>');}}}}}//起始符号的firstVt集合中的每个元素与'#'作为键，将小于号（'<'）作为值，存入matrix中。Set<Character> coll = firstVt.get(input.get(0).charAt(0));for (Character value : coll) {matrix.put('#' + "" + value, '<');}//起始符号的lastVt集合中的每个元素与'#'作为键，将大于号（'>'）作为值，存入matrix中。Set<Character> coll1 = lastVt.get(input.get(0).charAt(0));for (Character value : coll1) {matrix.put(value + "" + '#', '>');}//处理部分错误情况partError();//遍历所有的终结符，并在matrix中找到对应的优先关系。//如果没有找到对应的关系，则将键值对存入matrix中，其中值为' '。for (Character value : End) {for (Character value1 : End) {matrix.putIfAbsent(value + "" + value1, ' ');}}//将"##"作为键，将等于号（'='）作为值，存入matrix中。matrix.put("##", '=');getVT();//打印构造的算符优先矩阵printMatrix();}/*** 打印算符优先矩阵* 遍历终结符，输出构造的算符优先矩阵*/private static void printMatrix(){System.out.println("\n构造的算符优先关系表如下:");int kong = 0;for (Character value : End) {if (kong == 0) {System.out.print("   ");}kong++;System.out.print(value);if (kong != End.size()) {System.out.print("  ");}}System.out.println();for (Character value : End) {System.out.print(value);for (Character value1 : End) {Character ch = matrix.get(value + "" + value1);if (ch != null) {System.out.print("  " + ch);} else {System.out.print("  " + " ");}}System.out.println();}}/*** 判断其是不是终结符*/private static boolean isEnd(Character ch) {for (Character value : End) {if (value.equals(ch)) {return true;}}return false;}/*** 判断其是不是非终结符*/private static boolean isNoEnd(Character ch) {for (Character value : NoEnd) {if (value.equals(ch)) {return true;}}return false;}/*** 根据产生式右部分返回左边*/private static char retLeft(String str) {char ch;// 遍历文法的产生式for (Map.Entry<Character, List<String>> map : produce.entrySet()) {ch = map.getKey();// 遍历每个产生式的右部for (String value : map.getValue()) {// 检查右部的长度是否与给定的字符串相同if (value.length() != str.length()) {continue;}int i;for (i = 0; i < str.length(); i++) {// 比较每个字符if (str.charAt(i) >= 65 && str.charAt(i) <= 90) {// 如果是非终结符if (value.charAt(i) >= 65 && value.charAt(i) <= 90) {// 都是非终结符，继续比较} else {break;// 产生式与给定字符串不匹配，跳出循环}} else {// 如果是终结符，直接比较字符if (value.charAt(i) != str.charAt(i)) {break; // 产生式与给定字符串不匹配，跳出循环}}}if (i == str.length()) {return ch;// 如果遍历完成，说明匹配成功，返回左部非终结符}}}return 0;// 没有匹配的产生式，返回0}//TODO 将字符数组转换成字符串/*** 将字符数组转换成字符串* @param list  字符列表* @return      对应的字符串*/public static String replaceToString(List<Character> list) {StringBuffer a = new StringBuffer();for (Character value : list) {if (value != ',' && value != '[' && value != ']') {a.append(value);}}return a.toString();}//TODO 分析过程/*** 算符优先分析过程* 使用一个符号栈，用它寄存终结符和非终结符,k代表符号栈的深度* 在正常情况下，算法工作完毕时，符号栈S应呈现:#N*/public static void analysisProcess() {int status = 0;// 操作类型标志，0表示移进，1表示规约int count = 0;// 计数器，记录分析步骤int k = 0;//符号栈深度的指针，用于标记在符号栈中的当前位置int j = 0;// 回溯指针，用于在规约过程中找到前一个终结符int step = 0;//计步器，用于记录当前处理到句子的哪个字符String gui = null;//字符串，用于存储规约时的显示信息System.out.println("请输入要分析的句子");//输入的句子，需要被分析的字符串String analyze;analyze = in.nextLine();if (analyze.charAt(analyze.length() - 1) != '#') {analyze = analyze + "#";}/* 符号栈的初始化，符号栈用于存储待处理的符号，初始时栈底为'#' *///符号栈，用于存储待处理的符号。它是一个字符的列表，可以存储输入字符串中的字符和非终结符。List<Character> listStack = new ArrayList<>();//格式化字符串"%-8s%-20s%-8s%-10s%-8s\n"中的每个%-Ns表示一个左对齐的字符串，其中N是该字符串的最小宽度System.out.printf("%-8s%-20s%-8s%-10s%-8s\n", "步骤", "栈", "a读入", "剩余串", "操作");//栈底 #listStack.add('#');//当前正在处理的字符char a = analyze.charAt(step++);/* 分析过程主体 */do {if (status == 0) {if (count != 0) {System.out.printf("%-8s\n%-8d %-20s %-8c %-10s", "移进", count,replaceToString(listStack), a, analyze.substring(step));} else {System.out.printf("%-8d %-20s %-8c %-10s", count,replaceToString(listStack), a, analyze.substring(step));}} else {System.out.printf("%-8s\n%-8d %-20s %-8c %-10s", gui, count,replaceToString(listStack), a, analyze.substring(step));}char ch = listStack.get(k);if (isEnd(ch)) {j = k;} else if (j >= 1) {j = k - 1;}char temp;if (matrix.get(listStack.get(j) + "" + a) != null) {//规约//检查符号栈顶的字符和当前输入字符之间的优先关系。如果栈顶的符号优先级高，那么执行规约操作while (matrix.get(listStack.get(j) + "" + a).equals('>')) {if (listStack.size() == 2 && a == '#') {//#E这种情况break;}StringBuffer judge = new StringBuffer();do {temp = listStack.get(j);if (isEnd(listStack.get(j - 1))) {j = j - 1;} else {j = j - 2;}} while (!matrix.get(listStack.get(j) + "" + temp).equals('<'));for (int i = j + 1; i < listStack.size(); i++) {judge.append(listStack.get(i));}int te = listStack.size();for (int t = j + 1; t < te; t++) {listStack.remove(j + 1);}//将符号栈中的一些字符替换为一个非终结符char res = retLeft(judge.toString());if (res != 0) {count++;k = j + 1;listStack.add(res);status = 1;gui = "用" + res + "->" + judge + "规约";if (status == 0) {System.out.printf("%-8s\n%-8d %-20s %-8c %-10s", "移进", count,replaceToString(listStack), a, analyze.substring(step));} else {System.out.printf("%-8s\n%-8d %-20s %-8c %-10s", gui, count,replaceToString(listStack), a, analyze.substring(step));}}}}//移进---将当前输入字符'a'添加到符号栈中。if (matrix.get(listStack.get(j) + "" + a).equals('<')|| matrix.get(listStack.get(j) + "" + a).equals('=')) {count++;k++;status = 0;listStack.add(a);}else{//输入字符'a'和符号栈顶的字符不能形成有效的优先关系，那么输出错误信息并退出程序。switch (matrix.get(listStack.get(j) + "" + a)){case 'a':System.out.print("非法左括号! ");return;case 'b':System.out.print("缺少运算符! ");return;case 'c':System.out.print("缺少表达式! ");return;default:break;}}if (listStack.size() == 2 && a == '#') {break;}if (step < analyze.length()) {a = analyze.charAt(step++);} else {break;}} while (listStack.size() != 2 || a != '#');System.out.printf("%-8s\n", "分析成功");}
}

五、测试结果

1. LL(1)文法：

（1）输入文件：

图5-1-1 LL(1)文法的输入文件

（2）分析结果：

图5-1-2 LL(1)文法的分析结果

2. 算符优先文法：

（1）输入文件：

图5-1-4 算符优先文法的输入文件

（2）分析结果：

图5-1-5 算符优先文法的分析结果

服装外贸公司大量订单外发_东莞短视频制作公司_最有效的推广学校的方式_百度网盘24小时人工电话

一、实验目的

二、实验内容及步骤