# expression_calculator **Repository Path**: haze347/expression_calculator ## Basic Information - **Project Name**: expression_calculator - **Description**: 编译原理作业 - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2023-04-26 - **Last Updated**: 2023-06-04 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # lab2 我建议来我的笔记里看，链接如下：[https://www.wolai.com/gFzZAPpYUGUQKHReb4vP4T](https://www.wolai.com/gFzZAPpYUGUQKHReb4vP4T) ## 目录 - [引言](#引言) - [开发过程](#开发过程) - [任务分配表](#任务分配表) - [实验要求](#实验要求) - [讨论语法定义的二义性](#讨论语法定义的二义性) - [设计并实现词法分析程序](#设计并实现词法分析程序) - [构造算符优先关系表](#构造算符优先关系表) - [设计并实现语法分析和语义处理程序](#设计并实现语法分析和语义处理程序) - [测试你的实验结果](#测试你的实验结果) - [实验内容](#实验内容) - [设计模式](#设计模式) - [词法分析](#词法分析) - [MyScanner 接口与 token 定义](#MyScanner-接口与-token-定义) - [SimpleFactory.makeScannerFA()——构造自动机](#SimpleFactorymakeScannerFA构造自动机) - [SimpleScanner.scan](#SimpleScannerscan) - [语法分析（1）——生成语法分析表](#语法分析1生成语法分析表) - [Grammar接口——文法](#Grammar接口文法) - [SimpleGrammar 类](#SimpleGrammar-类) - [ParserFA接口——自动机](#ParserFA接口自动机) - [SimpleItem类](#SimpleItem类) - [SimpleStatus 类](#SimpleStatus-类) - [SimpleParserFA类](#SimpleParserFA类) - [ParserTable接口——转移表](#ParserTable接口转移表) - [SimpleParserTable类（简化版）](#SimpleParserTable类简化版) - [阶段测试](#阶段测试) - [TestPFAFactory——测试工厂](#TestPFAFactory测试工厂) - [测试结果1——普通文法](#测试结果1普通文法) - [测试结果2——直接左递归文法](#测试结果2直接左递归文法) - [测试结果3——间接左递归文法](#测试结果3间接左递归文法) - [语法分析（2）——真·语法分析](#语法分析2真语法分析) - [OperatorTable运算符优先级表](#OperatorTable运算符优先级表) - [SimpleParserTable.putInAction](#SimpleParserTableputInAction) - [R-R冲突](#R-R冲突) - [S-R冲突](#S-R冲突) - [SimpleFactory.makeGrammar()](#SimpleFactorymakeGrammar) - [MyParser接口](#MyParser接口) - [SimpleParser.parser（简化版）](#SimpleParserparser简化版) - [语义分析](#语义分析) - [SimpleParser.semanticAnalysis（语义分析）](#SimpleParsersemanticAnalysis语义分析) - [SimpleParser.exitWithException（异常处理）](#SimpleParserexitWithException异常处理) - [回归测试](#回归测试) - [personal.abandon包（附录）](#personalabandon包附录) - [从正则表达式生成DFA](#从正则表达式生成DFA) - [ExREToStREConverter——扩展型正则表达式转标准型正则表达式](#ExREToStREConverter扩展型正则表达式转标准型正则表达式) - [StREToNFAConverter——标准型正则表达式转 NFA](#StREToNFAConverter标准型正则表达式转-NFA) - [NFAToDFAConverter——NFA转DFA](#NFAToDFAConverterNFA转DFA) - [DFAMinimizer——DFA最小化](#DFAMinimizerDFA最小化) - [personal.TestDrive](#personalTestDrive) 姓名：陈渤林 学号：20337175 班级：计算机科学与技术2班 *** # 引言 无语…… 做语义分析的时候，我使用了如下字符串作分割符，用于split与merge ```java public class SemanticAnalyzer { private final String delimiter = "$delimiter$"; } ``` 然后出bug了…… 我跑了一个测试程序： ```java public static void main(String[] args) { String tmp = "1$delimiter$1"; System.out.println(tmp.split("$delimiter$").length); System.out.println(tmp.split("$delimiter$")[0]); } ``` 然后输出如下： ```纯文本 1 1$delimiter$1 ``` 我人都麻了??? 然后chat了一下： ![](image/image_RpL_ejWpgQ.png) 所以说， - 我随便写了个字符串， - 内容恰好和变量名一样， - 嫌内容和变量名重复不是好的方案，所以在首尾随便加了个字符， - 又恰好使用了双引号， 然后触发了我不知道的java机制，导致了项目bug…… 至于为什么我会去问gpt这个问题，我只能说是：离谱事儿见多了…… # 开发过程 > 我真的是当做项目开发了，太恐怖了 #### 任务分配表 | 任务内容 | 状态 | 开始日期 | 备注 | 预计时间 | | ------------------------------------------------------------------------------------------------------------------- | --- | ---------- | --------------------------- | ---- | | [建立实验报告框架，划分任务](https://www.wolai.com/wXF3igvVfaWxzkXc4SFauV "建立实验报告框架，划分任务") | 已完成 | 2023/04/26 | | 1天 | | [阅读实验要求，构建项目文件](https://www.wolai.com/jXeUGRRx9c7fFMNsde4bbd "阅读实验要求，构建项目文件") | 已完成 | 2023/04/26 | | 1天 | | [生成词法分析自动机](https://www.wolai.com/3HBFUEfuu1yf49g5zjnDPT "生成词法分析自动机") | 已完成 | 2023/05/06 | | 2天 | | [scan](https://www.wolai.com/a94z5t5hgx4yvrDv4kJhgD "scan") | 已完成 | 2023/05/09 | | 1天 | | [parser](https://www.wolai.com/2vTbmADo3k2NdHUEAszKax "parser") | 进行中 | | | | | [scanner](https://www.wolai.com/nrdPHiLCAyjcSi5yHeKbae "scanner") | 已完成 | | | | | [基本数据结构：文法，写入文法](https://www.wolai.com/d8ZZaYpdbJnbDuEAqgXGhE "基本数据结构：文法，写入文法") | 已完成 | 2023/05/10 | | 1天 | | [由文法生成自动机](https://www.wolai.com/kBht8m6odG36Kd5CX1LGW2 "由文法生成自动机") | 已完成 | 2023/05/11 | | 2天 | | [规定运算符优先级：直接从自动机上解决冲突](https://www.wolai.com/tKogtbx4AoL8N7F5KMeSDB "规定运算符优先级：直接从自动机上解决冲突") | 未完成 | | 废弃，不可能解决 | | | [重构scanner，以生成更具体的token，减轻语法分析的负担](https://www.wolai.com/tYo2PLS8GC4EZCTinEuMBF "重构scanner，以生成更具体的token，减轻语法分析的负担") | 已完成 | 2023/05/13 | | 1天 | | [first 集，ll(1) item，fa](https://www.wolai.com/u2udSYtenTUcj8pkR9fsST "first 集，ll(1) item，fa") | 已完成 | 2023/05/15 | | 1天 | | [ll(1) table简化版](https://www.wolai.com/8nZ1rt8kqqu4vuqd5WDeNz "ll(1) table简化版") | 已完成 | 2023/05/16 | | 1天 | | [ll(1) table 解决冲突](https://www.wolai.com/pB8wtn2JTnPA3LLHirU3FW "ll(1) table 解决冲突") | 已完成 | 2023/05/17 | 因为没有重写hashCode，我de了6h bug…… | 1天 | | [ll(1)归约过程，抛异常，语义](https://www.wolai.com/tRxSficn3LeS3GWaAB1REh "ll(1)归约过程，抛异常，语义") | 已完成 | 2023/05/18 | | 1天 | | [回归测试](https://www.wolai.com/6omzzNpQhyZAvpLqCe3xZA "回归测试") | 未完成 | 2023/05/19 | 准确度尚可，部分测试没有通过 | 1天 | # 实验要求 本实验要求使用 Java 语言设计并实现一个实际可用的计算器，其规格说明参阅本文档第 2 部分的详细描述。你必须按照软件工程的规范要求，编写本实验中设计与实现相关的文档；此外，你还必须在实验报告中撰写以下相关内容。 ## 讨论语法定义的二义性 本文档第 2 部分以 BNF 描述了可接收的输入表达式的形式化语法定义。请问这一语法定义是否存在二义性？如果你回答不存在，请说明理由；如果你回答存在，请证明之，并说明如何解析表达式中的二义性。上述 BNF 二义性的讨论有助于你更好地理解所处理的表达式语言。 存在。当输入为：1+2+3时，我们显然能获得两颗语法树。 ```mermaid flowchart TD n1(Expr) n2(ArithExpr) n3(ArithExpr) n4(+) n5(ArithExpr) n6(ArithExpr) n7(+) n8(ArithExpr) n9(1) n10(2) n11(3) n1-->n2 n2-->n3 n2-->n4 n2-->n5 --> n11 n3-->n6 --> n9 n3-->n7 n3-->n8 --> n10 ``` ```mermaid flowchart TD n1(Expr) n2(ArithExpr) n3(ArithExpr) n4(+) n5(ArithExpr) n11(1) n6(ArithExpr) n7(+) n8(ArithExpr) n9(2) n10(3) n1-->n2 n2-->n3 n2-->n4 n2-->n5 --> n11 n3-->n6 --> n9 n3-->n7 n3-->n8 --> n10 ``` 要想解释文法的二义性，我们需要为每一个运算符注册优先级和结合性 ## 设计并实现词法分析程序 在 EXPR-Eval 中，输入表达式支持布尔类型常量、数值类型常量（其中包括科学记数法）、各种算术运算、关系运算、逻辑运算、以及预定义函数等，请从本文档中提取支持的表达式语言的词法规则，并绘制识别其中所有合法单词的有限自动机（状态转换图），并以此作为程序蓝图编写你的词法分析程序。建议你的词法分析程序的主类命名为 Scanner。为便于在此基础上开发语法分析和语义处理程序，建议你采用嵌入式测试（Embedded Testing）对你自己开发的词法扫描程序进行较为完善的测试。 在你的实验报告中，词法分析部分的重点是描述你在实验中： 如何对单词进行分类，譬如算术运算符或关系运算符是分别作为一类单词，还是每一个运算符就是一类单词；如何处理对预定义函数名和布尔常量的识别，注意它们都属于标识符一类；如何处理科学记数法表示的数值常量；如何处理字符串的边界；等等。 我们选择将单词分成10类，即产生10种token。（词法分析一节） 另外，我们会在词法分析阶段区分减号和负号。（词法分析一节） 有关科学计数法的部分，我们使用自动机来解决。（附录一节） ## 构造算符优先关系表 本实验要求采用 OPP 作为语法分析技术，因而语法分析的核心问题是算符优先关系表的构造。请仔细构造你的算符优关系表，并在实验报告中说明你在表中如何处理一些较为敏感的关系；所谓敏感的关系，意指可能比较容易搞错的两个运算符之间的关系，譬如一元取负运算符和二元减法运算符之间的关系、三元运算符与其他运算符之间的关系、预定义函数与其他运算符之间的关系等。注意！请特别声明你是如何处理表达式中两个重载（Overloading）的运算符：一元取负运算符“−”和二元减法运算符“−”，例如 2−3 \*−4。 由于我们在词法分析阶段就区分了减号和负号，所以算符优先关系表是非常简单的。（语法分析2一节） ## 设计并实现语法分析和语义处理程序 以上述算符优先关系表为基础，编写 的语法分析程序和语义处理程序。建议你将语法分析程序的两个核心动作单独放在两个独立的子程序 shift()和 reduce()中，这符合结构化程序设计中每一子程序完成一个相对独立功能的基本原则。你的语义处理程序重点是完成类型推导与类型兼容性检查的工作；实际上，这些语义处理代码与语法分析代码通常是混合在一起的。在语法分析和语义处理过程中发现任何错误，均以异常（Exception）的形式对外报告；本实验的实验软装置已预定义了各种出错情况对应的异常类型，详见本文档第 3 部分。建议你的语法分析和语义处理程序的主类命名为 Parser。为便于对语法分析和语义处理程序进行调试，你既可以采用嵌入式测试，也可以使用实验软装置中提供的测试工具。在你的实验报告中，语法分析与语义处理部分的重点是描述你在实验中：如何实现 OPP 的核心控制程序，请以伪码或 Java 代码给出核心的算法；如何实现各种运算符的归约（Reduce）动作；如何对语义进行处理，主要是类型的兼容性检查与类型的推导；等等。 （语法分析2一节） ## 测试你的实验结果 请使用本实验的实验软装置中提供的测试用例对自己的实验结果进行测试。实验软装置提供了 simple 和 standard 两个级别的测试；如果时间许可，请在通过了所有 standard 测试用例后，再提交你的最终实验结果。注意，任课教师在评价你的实验结果时，会使用比 standard 测试多出数倍的测试用例来测试你的实验结果。因而，如果时间许可，你应该编写比 standard 测试更多的测试用例，以减少自己实验结果中可能存在的设计错误或实现错误。本文档第 3 部分介绍了如何以 XML 文档书写自己设计的测试用例，这些测试用例可借助实验软装置自动完成回归测试（RegressionTesting）。 （语义分析一节，回归测试一节） # 实验内容 > 我已经修改了 build.bat 文件，请按照我的文件构建项目 ![](image/image_V2cYzJrv0T.png) ![](image/image_hE1IhhxCrJ.png) ## 设计模式 强调一下： - 我们严格遵守“依赖倒置原则”，将接口与实现分离开。 - 通过工厂模式构造相关的类，选择哪一版底层实现交由工厂负责，而不是调用者。 综上，我们新建 personal 包，负责构建相关的自动机、转移表、提供底层数据结构等，具体如下： - scanner包：提供底层数据结构，Factory调用相关类， - perser包：提供底层数据结构，Factory调用相关类， - util包：一些基本的辅助函数 - Factory接口：外界只应该使用这个类进行构造，其具体工作交给SimpleFactory类来做 - TestDrive类：测试类，调用 scanner 包和 perser 包，生成有关的dfa、转移表，以供我们修改 > 项目早期的实现方案已被废弃，我将其放置在abandoned包中 ## 词法分析 ### MyScanner 接口与 token 定义 MyScanner 接口负责提供 scan 接口，定义 token 类 - Token - OperandToken：运算数 - DecimalToken：整数、浮点数 decimal - BooleanToken：布尔数 true、false - OperatorToken：运算符 - ArithmeticOperatorToken：算术运算符 + - \* / ^ ? : - ArithmeticOperator1DToken：单目算术运算符 - - ArithmeticOperator2DToken：双目算术运算符 + - \* / ^ - ArithmeticOperator3DToken：三目算术运算符 ? : - LogicalOperatorToken：逻辑运算符 < > = >= <= <> ! & | - CompareOperatorToken：比较运算符 < > = >= <= <> - LogicalOperator1DToken：单目逻辑运算符 ! - LogicalOperator2DToken：双目逻辑运算符 & | - DelimiterOperatorToken：分隔符 , ( ) - FunctionToken：保留函数 sin cos min max 这是根据运算结果给出的继承关系。 因为三元运算的结果一定是数值，所以将其放在ArithmeticOperator的子类中。 ![](image/image_n7NntD7qqh.png) 类图如下： ```mermaid classDiagram Token <|-- OperandToken Token <|-- OperatorToken Token <|-- FunctionToken OperandToken <|-- DecimalToken OperandToken <|-- BooleanToken OperatorToken <|-- ArithmeticOperatorToken OperatorToken <|-- LogicalOperatorToken OperatorToken <|-- DelimiterOperatorToken ArithmeticOperatorToken <|-- ArithmeticOperator1DToken ArithmeticOperatorToken <|-- ArithmeticOperator2DToken ArithmeticOperatorToken <|-- ArithmeticOperator3DToken LogicalOperatorToken <|-- CompareOperatorToken LogicalOperatorToken <|-- LogicalOperator1DToken LogicalOperatorToken <|-- LogicalOperator2DToken ``` 自然，我们只允许最底层的类是可以被构造的。一共 10 种 token，分别是： 1. DecimalToken 2. BooleanToken 3. ArithmeticOperator1DToken 4. ArithmeticOperator2DToken 5. ArithmeticOperator3DToken 6. CompareOperatorToken 7. LogicalOperator1DToken 8. LogicalOperator2DToken 9. DelimiterOperatorToken 10. FunctionToken ### SimpleFactory.makeScannerFA()——构造自动机 > 构造的过程在 personal.Maker 中进行 自动机如下： ```mermaid flowchart LR n01{"01"} n02(("02")) n03{"03"} n04(("04")) n05{"05"} n06(("06")) n07{"07"} n08{"08"} n09{"09"} n10{"10"} n11(("11")) n12{"12"} n13{"13"} n14{"14"} n15(("15")) n16(("16")) n17(("17")) n18(("18")) n19(("19")) n20(("20")) n21(("21")) n22{"22"} n23{"23"} n24(("24")) n25{"25"} n26{"26"} n27{"27"} n28{"28"} n01--"0 1 2 3 4 \n5 6 7 8 9 \n"-->n02 n02--"0 1 2 3 4 \n5 6 7 8 9 \n"-->n02 n02--"E e "-->n03 n02--". "-->n05 n05--"0 1 2 3 4 \n5 6 7 8 9 \n"-->n06 n06--"0 1 2 3 4 \n5 6 7 8 9 \n"-->n06 n06--"E e "-->n03 n03--"0 1 2 3 4 \n5 6 7 8 9 \n"-->n04 n03--"+ - "-->n07 n07--"0 1 2 3 4 \n5 6 7 8 9 \n"-->n04 n04--"0 1 2 3 4 \n5 6 7 8 9 \n"-->n04 n01--"t "-->n08 n08--"r "-->n09 n09--"u "-->n10 n10--"e "-->n11 n01--"f "-->n12 n12--"a "-->n13 n13--"l "-->n14 n14--"s "-->n10 n01--"* : + - ^ \n/ ? "-->n15 n01--"> "-->n16 n16--"= "-->n17 n01--"< "-->n18 n18--"= > "-->n17 n01--"= "-->n19 n01--"! & | "-->n20 n01--"( ) , "-->n21 n01--"s "-->n22 n22--"i "-->n23 n23--"n "-->n24 n01--"m "-->n25 n25--"i "-->n23 n25--"a "-->n26 n26--"x "-->n24 n01--"c "-->n27 n27--"o "-->n28 n28--"s "-->n24 ``` 我们为节点注册一些默认异常，以供 scan 时减少 if-else 数量。 构造时，部分代码如下： ```java public ScannerDFA makeScannerDFA() { SimpleScannerDFA dfa = new SimpleScannerDFA(1, " ", "01 02 0 1 2 3 4 5 6 7 8 9", "02 02 0 1 2 3 4 5 6 7 8 9", "02 03 E e", "02 05 .", "05 06 0 1 2 3 4 5 6 7 8 9", "06 06 0 1 2 3 4 5 6 7 8 9", "06 03 E e", "03 04 0 1 2 3 4 5 6 7 8 9", "03 07 + -", "07 04 0 1 2 3 4 5 6 7 8 9", "04 04 0 1 2 3 4 5 6 7 8 9", "01 08 t", "08 09 r", "09 10 u", "10 11 e", "01 12 f", "12 13 a", "13 14 l", "14 10 s", "01 15 + - * / ^ ? :", "01 16 >", "16 17 =", "01 18 <", "18 17 = >", "01 19 =", "01 20 ! & |", "01 21 ( ) ,", "01 22 s", "22 23 i", "23 24 n", "01 25 m", "25 23 i", "25 26 a", "26 24 x", "01 27 c", "27 28 o", "28 24 s" ); dfa.registerAcceptableNode(2, MyScanner.DecimalToken.class); dfa.registerAcceptableNode(4, MyScanner.DecimalToken.class); dfa.registerAcceptableNode(6, MyScanner.DecimalToken.class); dfa.registerAcceptableNode(11, MyScanner.BooleanToken.class); dfa.registerAcceptableNode(15, MyScanner.ArithmeticOperatorToken.class); dfa.registerAcceptableNode(16, MyScanner.CompareOperatorToken.class); dfa.registerAcceptableNode(17, MyScanner.CompareOperatorToken.class); dfa.registerAcceptableNode(18, MyScanner.CompareOperatorToken.class); dfa.registerAcceptableNode(19, MyScanner.CompareOperatorToken.class); dfa.registerAcceptableNode(20, MyScanner.LogicalOperatorToken.class); dfa.registerAcceptableNode(21, MyScanner.DelimiterOperatorToken.class); dfa.registerAcceptableNode(24, MyScanner.FunctionToken.class); dfa.registerDefaultException(1, IllegalIdentifierException.class); // 开头就错，说明是非法字符 // 错误的运算数字 dfa.registerDefaultException(3, IllegalDecimalException.class); dfa.registerDefaultException(5, IllegalDecimalException.class); dfa.registerDefaultException(7, IllegalDecimalException.class); dfa.registerDefaultException(8, IllegalDecimalException.class); dfa.registerDefaultException(9, IllegalDecimalException.class); dfa.registerDefaultException(10, IllegalDecimalException.class); dfa.registerDefaultException(12, IllegalDecimalException.class); dfa.registerDefaultException(13, IllegalDecimalException.class); dfa.registerDefaultException(14, IllegalDecimalException.class); // 错误的标识符 dfa.registerDefaultException(22, IllegalIdentifierException.class); dfa.registerDefaultException(23, IllegalIdentifierException.class); dfa.registerDefaultException(25, IllegalIdentifierException.class); dfa.registerDefaultException(26, IllegalIdentifierException.class); dfa.registerDefaultException(27, IllegalIdentifierException.class); dfa.registerDefaultException(28, IllegalIdentifierException.class); return dfa; } ``` ### SimpleScanner.scan > 这部分在 parser.MyScanner 类中实现 现在，我们根据上述自动机进行词法分析 MyScanner 类包含如下成员： - input：String，输入的表达式 - lookahead：int，下一个字符 - input buffer：输入内容的临时缓冲区， - accept buffer：接受值的临时缓冲区，用于实现最长匹配 MyScanner 类包含如下方法： - isIllegalTransit：是否是非法转移，即转移不在转移表中，或转移到了非法节点 - isLongestMatch：是否发生最长匹配，即当前节点是接受节点，且当前发生非法转移 - longestMatchHandle：发生最长匹配时的处理函数， - exit：异常处理函数，通过if-else 抛出精确的异常 - scan：词法分析主过程 scan 的处理过程需要注意以下问题： - 特判 lookahead 是空格时的情景 - 按顺序处理以下情况：最长匹配，非法转移，合法转移 部分代码如下： ```java public List scan(String input) throws IllegalSymbolException, IllegalDecimalException, IllegalIdentifierException { List tokenList = new ArrayList<>(); int ptr = 0; // 读取指针 int u = MyScanner.DFA.getStartId(); // 当前节点 while (ptr < input.length()) { MyScanner.lookahead = (int) input.charAt(ptr); // 记录当前输入 if (MyScanner.DFA.isAcceptable(u)) this.acceptBuffer.add(u); // 如果当前节点是接受节点，那么放入 buffer // 开始处理 if (MyScanner.lookahead == ' ') { // 表达式发生显示分隔 this.longestMatchHandle(tokenList); // 可能发生最长匹配 u = MyScanner.DFA.getStartId(); // 回到开始节点 ++ptr; // 跳转到下一个字符 continue; } if (this.isLongestMatch(u)) { // 发生最长匹配 this.longestMatchHandle(tokenList); // 处理栈顶 u = MyScanner.DFA.getStartId(); // 回到开始节点 continue; } else if (this.isIllegalTransit(u)) { // 出现非法转移 this.exit(u); // 抛出异常 throw new UnknownError(); } // 只是普通的转移 this.inputBuffer.append((char) (int) MyScanner.lookahead); // 将 lookahead 放入 buffer u = MyScanner.DFA.transitionTable[u][MyScanner.lookahead]; // 跳转到下一个字符 ++ptr; // 读取指针后移 } if (MyScanner.DFA.isAcceptable(u)) { // 读取结束时，也可能发生最长匹配 this.acceptBuffer.add(u); this.longestMatchHandle(tokenList); } return tokenList; } ``` ## 语法分析（1）——生成语法分析表 > 生成语法分析表的过程中，我们用了无数次BF算法求闭包…… 我们要做以下事情： - 定义文法 - 生成该文法的 LR(0) 项集族：闭包 - 生成该文法的 LR(1) 项集族：first 集，lookahead - 生成自动机：加上转移边 - 生成parser表：略 ### Grammar接口——文法 数据结构包括： - 静态内部类：Symbol，拥有一个 String - 静态内部类：TerminalSymbol，继承自Symbol - 静态内部类：NonTerminalSymbol，继承自Symbol - 静态内部类：Production，拥有一个 NonTerminalSymbol左部，一个 Symbol List 右部 方法包括： - 返回开始符号 - 返回终结符集合 - 返回非终结符集合 - 返回产生式列表 - 返回具有指定表达式的符号 - 返回指定可变参数列表的 first 集 ### SimpleGrammar 类 这个类是 Grammar 接口的底层实现。 我们说一下构造函数，构造文法时，我们需要传入以字符串形式给出的： - 开始符号 - 非终结符集合 - 终结符集合 - 产生式的分隔符：用于 split - 产生式：是可变参数列表 ```java /** * 构造函数，传入以字符串形式给出的：开始符号，非终结符集合、终结符集合、产生式、以及产生式的分隔符 * * @param startSymbolExpression 开始符号 * @param nonTerminalSymbolExpressions 非终结符集合 * @param terminalSymbolExpressions 终结符集合 * @param delimiterExpression 分隔符，理解成对字符串形式的产生式调用 String.split * @param productionExpressions 产生式列表 */ public SimpleGrammar(String startSymbolExpression, List nonTerminalSymbolExpressions, List terminalSymbolExpressions, String delimiterExpression, String... productionExpressions) { // 初始化 this.nonTerminals = new HashSet<>(); this.terminals = new HashSet<>(); this.productions = new ArrayList<>(); this.symbolsByExpression = new HashMap<>(); this.firstOfSymbol = new HashMap<>(); // 初始化非终结符集合、终结符集合，并检查冲突 for (String expression : nonTerminalSymbolExpressions) { // 非终结符 NonTerminal symbol = new NonTerminal(expression); if (this.symbolsByExpression.putIfAbsent(expression, symbol) != null) // 不是第一次出现 throw new IllegalArgumentException("符号冲突：" + expression); this.nonTerminals.add(symbol); } for (String expression : terminalSymbolExpressions) { // 终结符 Terminal symbol = new Terminal(expression); if (this.symbolsByExpression.putIfAbsent(expression, symbol) != null) // 不是第一次出现 throw new IllegalArgumentException("符号冲突：" + expression); this.terminals.add(symbol); } this.startSymbol = this.getSymbol(startSymbolExpression); // 初始化产生式 for (String productionExpression : productionExpressions) { // 遍历产生式 // split String[] expressionList = productionExpression.split(delimiterExpression); if (expressionList.length < 2) { // 保证有一个左部，一个右部 throw new IllegalArgumentException(String.format("产生式 %s 长度过短", productionExpression)); } // 检查左部 Symbol leftSide = this.getSymbol(expressionList[0]); if (leftSide == null) { throw new IllegalArgumentException(String.format("产生式 %s 的左部是未知符号", productionExpression)); } if (!(leftSide instanceof NonTerminal)) { throw new IllegalArgumentException(String.format("产生式 %s 的左部不是非终结符", productionExpression)); } // 检查右部 List rightSide = new ArrayList<>(); for (int i = 1; i < expressionList.length; ++i) { Symbol rightSideSymbol = this.getSymbol(expressionList[i]); if (rightSideSymbol == null) { throw new IllegalArgumentException(String.format("产生式 %s 的右部出现未知符号 %s", productionExpression, expressionList[i])); } rightSide.add(rightSideSymbol); } // 创建产生式 this.productions.add(new Production((NonTerminal) leftSide, rightSide)); } // 初始化单符号的 first 集 this.initFirstBySymbol(); } ``` 有关 first 集的计算，我们交给如下一套函数去做： - fist()：外界的接口，处理一些异常信息，并使用内部的getFirstBySymbol方法拼接返回内容。 - getFirstBySymbol()：内部使用的辅助函数，能提供单符号的 first 集。本质上在使用 map，但是对调用者屏蔽内部细节。 - initFirstBySymbol()：构造函数调用之，初始化getFirstBySymbol() 函数的记忆化信息。本质上使用了类贝尔曼福德算法求解转移闭包。 > 因为文法是优质的，没有产生式转移到空串，所以我们能减少很多工作量 代码如下： ```java @Override public Set fist(Symbol... symbols) { if (Arrays.stream(symbols).anyMatch(this::isIllegalSymbol)) throw new UnknownError("非法符号"); // for (Symbol symbol : symbols) if (this.isIllegalSymbol(symbol)) throw new UnknownError("非法符号"); if (symbols.length == 1) return this.getFirstBySymbol(symbols[0]); // 单个符号：FIRST(X) Set ret = new HashSet<>(); for (Symbol symbol : symbols) { if (symbol == Grammar.EMPTY) continue; ret.addAll(this.getFirstBySymbol(symbol)); // 显然是没有 ε 的 break; // 直接退出即可 } return ret; } /** * 单符号的 first 集 */ private final Map> firstOfSymbol; private Set getFirstBySymbol(Symbol symbol) { return this.firstOfSymbol.get(symbol); } /** * 初始化单符号的 first 集 */ private void initFirstBySymbol() { if (this.getTerminals().contains(Grammar.EMPTY)) throw new IllegalArgumentException("禁止出现空串"); // 先处理终结符的 first 集 for (Terminal terminal : this.getTerminals()) { this.firstOfSymbol.putIfAbsent(terminal, new HashSet<>(List.of(terminal))); } // 再处理非终结符的 first 集 // 转移影响，右部的非终结符将影响左部 Map> bucket = new HashMap<>(); for (Production production : this.getProductions()) { try { NonTerminal right = (NonTerminal) production.rightSide().get(0); bucket.putIfAbsent(right, new HashSet<>()); bucket.get(right).add(production.leftSide()); } catch (ClassCastException ignored) { } } // 先将各非终结符的 first 集初始化为空集 for (NonTerminal nonTerminal : this.getNonTerminals()) { this.firstOfSymbol.putIfAbsent(nonTerminal, new HashSet<>()); } // 循环流程 Queue qeBuffer = new LinkedList<>(this.getNonTerminals()); // 更新队列 // 初始化更新队列，先处理右部是终结符开头的 for (Production production : this.getProductions()) { try { Terminal right = (Terminal) production.rightSide().get(0); this.firstOfSymbol.get(production.leftSide()).add(right); qeBuffer.add(production.leftSide()); // 放入更新队列 } catch (ClassCastException ignored) { } } while (!qeBuffer.isEmpty()) { NonTerminal u = qeBuffer.poll(); // 当前非终结符 try { for (NonTerminal v : bucket.get(u)) { if (this.firstOfSymbol.get(v).addAll(this.firstOfSymbol.get(u))) { // first 集发生改变 qeBuffer.add(v); } } } catch (NullPointerException ignored) { // 说明这个非终结符并不影响任何其它的 } } } ``` ### ParserFA接口——自动机 包括： - 内部接口：Item，提供 Production、描述当前位置、lookahead等信息 - 内部接口：Status，提供相关的信息：所有相关转移、是否可归约、是否具有移入-归约冲突、归约-归约冲突 方法包括： - 自动机节点数量 - 获得指定编号的节点 - 获得指定编号的转移符号 - 获得指定节点的编号 - 获得指定转移符号的编号 - 给出指定节点指定转移的结果 ### SimpleItem类 SimpleItem类实现 Item 接口，并提供了更多的方法，以减轻构建表的负担。这包括： - 返回当前符号右侧的表达式 - 当前位置向后移动一位，形成新的 SimpleItem - 合并 lookahead 代码如下： ```java class SimpleItem implements ParserFA.Item { /** * @return 返回当前符号右侧的表达式，用于求 first 以求 lookahead */ public List getFollowSymbols() { if (this.point == this.production().rightSide().size()) throw new UnknownError("对可归约项调用 getFollowSymbols"); if (this.point + 1 == this.production().rightSide().size()) return new ArrayList<>(List.of(Grammar.EMPTY)); List ret = new ArrayList<>(); for (int i = this.point + 1; i < this.production().rightSide().size(); ++i) { ret.add(this.production().rightSide().get(i)); } return ret; } /** * @return 当前位置向后移动一位 */ public SimpleItem getNextItem() { return new SimpleItem(this.production, this.point + 1, this.lookahead); } /** * 合并 lookahead * * @param o 另一个产生式 * @throws IllegalArgumentException 产生式或当前符号不同，无法合并 */ public void merged(SimpleItem o) { if (this.production != o.production || this.point != o.point) throw new IllegalArgumentException("产生式或当前符号不同，无法合并"); this.lookahead.addAll(o.lookahead); } /** * 构造函数，创建一个指定产生式从头开始的 item * * @param production 指定产生式 * @param lookahead lookahead */ public SimpleItem(Grammar.Production production, Set lookahead) { this(production, 0, lookahead); } /** * 完全的构造函数，供内部使用 * * @param production 指定产生式 * @param point 当前位置 * @param lookahead lookahead */ private SimpleItem(Grammar.Production production, int point, Set lookahead) { this.production = production; this.point = point; this.lookahead = lookahead; } } ``` > 注意，我们的 public 构造函数是不允许指定`当前位置`的，因为逻辑上没有使用需求 ### SimpleStatus 类 SimpleStatus 类继承 LinkedHashSet 类，实现 Status 接口。 ```java public class SimpleStatus extends LinkedHashSet implements ParserFA.Status { /** * 对自己求闭包 * * @return 自己 */ public SimpleStatus toClosure(Grammar grammar) { Queue qeBuffer = new LinkedList<>(this); while (!qeBuffer.isEmpty()) { // BF 算法求闭包 SimpleItem itemU = qeBuffer.poll(); for (SimpleItem itemV : this.transfer(grammar, itemU)) { if (this.add(itemV)) qeBuffer.add(itemV); // 放入新的 itemV } } // 合并 lookahead Map2D bucket = new Map2D<>(); // 用产生式、当前位置作 key for (SimpleItem item : this) { SimpleItem preItem = bucket.putIfAbsent(item.production(), item.point(), item); if (preItem != null) preItem.merged(item); } this.clear(); this.addAll(bucket.values()); return this; } /** * @param grammar 指定文法 * @param itemU 指定 item * @return 指定文法中，由指定 item 推导出的 item 集合 */ private List transfer(Grammar grammar, SimpleItem itemU) { List ret = new ArrayList<>(); try { Grammar.NonTerminal current = (Grammar.NonTerminal) itemU.getCurrent(); // 当前符号 List productions = grammar.getProductions().stream().filter(i -> i.leftSide().equals(current)).toList(); // 取出文法中，左部是当前符号的产生式 for (Grammar.Production production : productions) { // 遍历左部是当前符号的产生式 // 生成 lookahead Set lookahead = new HashSet<>(); for (Grammar.Terminal terminal : itemU.lookahead()) { // 遍历 itemU 的 lookahead 集合， List buffer = itemU.getFollowSymbols(); buffer.add(terminal); lookahead.addAll(grammar.fist(buffer.toArray(new Grammar.Symbol[0]))); // 将对应的 first 集合并到 lookahead } ret.add(new SimpleItem(production, lookahead)); // 放入 } } catch (IndexOutOfBoundsException ignored) { // 到达产生式结尾 } catch (ClassCastException ignored) { // 当前符号不是非终结符 } return ret; } } ``` ### SimpleParserFA类 > ParserFA 的底层实现 parser 的自动机长这个样子 ![](image/image_r-OLxsaDiJ.png) SimpleParserFA 包含以下几点： - 私有方法transitForEachSymbol：遍历并处理指定节点的所有转移 - 私有方法transitBySymbol：求指定节点进行转移后的节点 - 构造函数：从文法生成自动机，还是BF算法求闭包 生成过程如下： ```java public class SimpleParserFA implements ParserFA { /** * 构造函数，传入对应的文法 * * @param grammar 对应的文法 */ public SimpleParserFA(Grammar grammar) { // 初始化数据结构 this.nodeIdAllocter = new IdAllocter<>(1); this.symbolIdAllocter = new IdAllocter<>(1); this.grammar = grammar; this.adj = new Map2D<>(); // 初始化自动机 SimpleStatus StartNode = new SimpleStatus(); StartNode.add(new SimpleItem(this.grammar.getProductions().get(0), new HashSet<>(List.of((Grammar.Terminal) this.grammar.getSymbol("$"))))); this.indexOf(StartNode.toClosure(this.grammar)); // 为第一个节点编号 // 开始转移 Queue qe = new LinkedList<>(); this.nodeIdAllocter.pollAllTo(qe); while (!qe.isEmpty()) { SimpleStatus node = qe.poll(); node.initTag(); // 初始化 tag this.transitForEachSymbol(node); this.nodeIdAllocter.pollAllTo(qe); } } /** * 遍历并处理指定节点的所有转移 * * @param nodeU 指定节点 */ private void transitForEachSymbol(SimpleStatus nodeU) { for (Grammar.Symbol transit : nodeU.getCurrents()) { SimpleStatus nodeV = this.transitBySymbol(nodeU, transit); int idU = this.indexOf(nodeU), idV = this.indexOf(nodeV), idW = this.indexOf(transit); if (!this.addEdge(idU, idV, idW)) throw new UnknownError("转移节点时，发生未知错误"); } } /** * 求指定节点进行转移后的节点 * * @param init 指定节点 * @param symbol 转移符号 * @return 转移后的节点 */ private SimpleStatus transitBySymbol(SimpleStatus init, Grammar.Symbol symbol) { SimpleStatus ret = new SimpleStatus(); List items = init.stream().filter(i -> symbol.equals(i.getCurrentOrNull())).toList(); // 取出当前符号是 symbol 的产生式 for (SimpleItem item : items) { // 遍历 Status 中的 item ret.add(item.getNextItem()); } return ret.toClosure(this.grammar); } } ``` ### ParserTable接口——转移表 包括： - 静态内部类：Action，描述动作 - 静态内部类：ShiftAction，继承自Action，表示移入动作 - 静态内部类：ReduceAction，继承自Action，表示归约动作 - 静态内部类：AcceptAction，继承自Action，表示接受动作 ### SimpleParserTable类（简化版） 转移表长这个样子： ![](image/image_0v8GPaNVqK.png) 继承 LL(1)的自动机，我们尝试生成转移表。规则如下： ![](image/image_DKffLoGGSU.png) 遵守上述规则，代码如下： ```java public class SimpleParserTable implements ParserTable { public SimpleParserTable(Grammar grammar) { // 初始化数据结构 this.grammar = grammar; this.fa = new SimpleParserFA(grammar); this.actionTable = new Map2D<>(); this.gotoTable = new Map2D<>(); // 开始填表 for (int u = 1; u <= this.size(); ++u) { // 遍历各个状态 ParserFA.Status nodeU = fa.getStatus(u); for (ParserFA.Item item : nodeU.Items()) { // 遍历各个 item // 如果是终结符，那么填入 ACTION 表 try { // 移入，即未到达产生式结尾 Grammar.Terminal current = (Grammar.Terminal) item.getCurrentSymbol(); // 取出当前位置 this.putInAction(u, current, new ShiftAction(fa.transitTo(u, current))); // 那么 Action[u, symbol] = Sift, goto(u, symbol) } catch (IndexOutOfBoundsException ex) { // 归约，即已经到达产生式末尾， if (item.production().equals(grammar.getProductions().get(0))) { // 如果是第 0 条产生式， this.putInAction(u, grammar.getSymbol("$"), new AcceptAction()); // 那么 Action[u, $] = accept } else { // 否则，是普通的产生式 ReduceAction reduceAction = new ReduceAction(grammar.getProductions().indexOf(item.production())); for (Grammar.Symbol terminalSymbol : item.lookahead()) { // 对于任意 lookahead， Action[u, lookahead] = Reduce indexOfProduction this.putInAction(u, terminalSymbol, reduceAction); } } } catch (ClassCastException ignored) { // 非终结符，那么填入 GOTO 表 Grammar.NonTerminal nonTerminal = (Grammar.NonTerminal) item.getCurrentSymbol(); try { // Goto[u, A] = v if (this.gotoTable.putIfAbsent(u, nonTerminal, fa.transitTo(u, nonTerminal)) != null) throw new UnknownError("构建 goto 表时，同一位置填入多个项"); } catch (NullPointerException ex) { throw new UnknownError("填入 goto 表时，不存在相关转移"); } } } } } /** * @param u * @param symbol * @param action */ private void putInAction(int u, Grammar.Symbol symbol, Action action) { Action preAction = this.actionTable.putIfAbsent(u, symbol, action); if (preAction == null) return; else throw new UnsupportedOperationException("暂时未实现解决冲突的逻辑"); } } ``` > 注意：我们暂时没有处理动作冲突，这部分留在下一部分做 ## 阶段测试 由于原文法过于庞大，我们使用小样例进行测试。 ### TestPFAFactory——测试工厂 我们使用测试工厂进行测试，外界只需要修改工厂即可。 测试工厂代码： ```java public class TestPFAFactory implements Factory { @Override public ScannerDFA makeScannerDFA() { throw new UnsupportedOperationException(); } @Override public Grammar makeGrammar() { // todo } @Override public ParserTable makeParserTable() { throw new UnsupportedOperationException(); } } ``` ### 测试结果1——普通文法 普通文法： ![](image/image_LDE2PIjS3e.png) ```java @Override public Grammar makeGrammar() { List nonTerminalSymbolExpressions = List.of("S`", "S", "X"); List terminalSymbolExpressions = List.of("a", "b", "$"); SimpleGrammar grammar = new SimpleGrammar("S`", nonTerminalSymbolExpressions, terminalSymbolExpressions, " ", "S` S", "S X X", "X a X", "X b" ); return grammar; } ``` 测试结果如下： ```mermaid flowchart LR n1["n1 S` --> • S [$] S --> • X X [$] X --> • a X [a, b] X --> • b [a, b] "] n2["n2 X --> a • X [a, b] X --> • a X [a, b] X --> • b [a, b] "] n3["n3 X --> b • [a, b] "] n4["n4 S` --> S • [$] "] n5["n5 S --> X • X [$] X --> • a X [$] X --> • b [$] "] n6["n6 X --> a X • [a, b] "] n7["n7 X --> a • X [$] X --> • a X [$] X --> • b [$] "] n8["n8 X --> b • [$] "] n9["n9 S --> X X • [$] "] n10["n10 X --> a X • [$] "] n1--"a"-->n2 n1--"b"-->n3 n1--"S"-->n4 n1--"X"-->n5 n2--"a"-->n2 n2--"b"-->n3 n2--"X"-->n6 n5--"a"-->n7 n5--"b"-->n8 n5--"X"-->n9 n7--"a"-->n7 n7--"b"-->n8 n7--"X"-->n10 ``` 转移表如下： ```纯文本 a, b, $, S, X, S`, 1: Shift 2, Shift 3, null, 4, 5, null, 2: Shift 2, Shift 3, null, null, 6, null, 3: Reduce 3, Reduce 3, null, null, null, null, 4: null, null, Accept, null, null, null, 5: Shift 7, Shift 8, null, null, 9, null, 6: Reduce 2, Reduce 2, null, null, null, null, 7: Shift 7, Shift 8, null, null, 10, null, 8: null, null, Reduce 3, null, null, null, 9: null, null, Reduce 1, null, null, null, 10: null, null, Reduce 2, null, null, null, ``` ### 测试结果2——直接左递归文法 左递归文法： ```java @Override public Grammar makeGrammar() { List nonTerminalSymbolExpressions = List.of("S`", "S", "X"); List terminalSymbolExpressions = List.of("a", "b", "$"); SimpleGrammar grammar = new SimpleGrammar("S", nonTerminalSymbolExpressions, terminalSymbolExpressions, " ", "S` S", "S S a S", "S b" ); return grammar; } ``` 测试结果： ```mermaid flowchart LR n1["n1 S` --> • S [$] S --> • S a S [a, $] S --> • b [a, $] "] n2["n2 S --> b • [a, $] "] n3["n3 S` --> S • [$] S --> S • a S [a, $] "] n4["n4 S --> S a • S [a, $] S --> • S a S [a, $] S --> • b [a, $] "] n5["n5 S --> S a S • [a, $] S --> S • a S [a, $] "] n1--"b"-->n2 n1--"S"-->n3 n3--"a"-->n4 n4--"b"-->n2 n4--"S"-->n5 n5--"a"-->n4 ``` Action 表发生冲突！ ### 测试结果3——间接左递归文法 间接左递归文法： ```java @Override public Grammar makeGrammar() { List nonTerminalSymbolExpressions = List.of("S`", "S", "X"); List terminalSymbolExpressions = List.of("a", "b", "$"); SimpleGrammar grammar = new SimpleGrammar("S", nonTerminalSymbolExpressions, terminalSymbolExpressions, " ", "S` S", "S X a S", "S b", "X S" ); return grammar; } ``` 测试结果： ```mermaid flowchart LR n1["n1 S` --> • S [$] S --> • X a S [a, $] S --> • b [a, $] X --> • S [a] "] n2["n2 S --> b • [a, $] "] n3["n3 S` --> S • [$] X --> S • [a] "] n4["n4 S --> X • a S [a, $] "] n5["n5 S --> X a • S [a, $] S --> • X a S [a, $] S --> • b [a, $] X --> • S [a] "] n6["n6 S --> X a S • [a, $] X --> S • [a] "] n1--"b"-->n2 n1--"S"-->n3 n1--"X"-->n4 n4--"a"-->n5 n5--"b"-->n2 n5--"S"-->n6 n5--"X"-->n4 ``` Action 表发生冲突！ ## 语法分析（2）——真·语法分析 文法如下： ![](image/image_b-QMWnCceO.png) 运算符优先级如下： ![](image/image_EFClxxhzof.png) ### OperatorTable运算符优先级表 只是一个表，代码如下： ```java /** * 运算符表 */ public class OperatorTable extends LinkedHashMap> { /** * 结合性 */ public enum Associative { LEFT, RIGHT } /** * 构造函数，由指定形式的字符串表意运算符内容、优先级、结合性。 * * @param grammar 文法，注册的运算符来自这个文法 * @param delimiter 分割符，用于划分字符串 * @param expressions 表达式列表，每个元素形如：op int LEFT */ public OperatorTable(Grammar grammar, String delimiter, String... expressions) { for (String expression : expressions) { String[] tokens = expression.split(delimiter); if (tokens.length != 3) throw new IllegalArgumentException("形式化字符串格式不对"); try { Grammar.Terminal terminal = (Grammar.Terminal) grammar.getSymbol(tokens[0]); int level = Integer.parseInt(tokens[1]); Associative associative; if (tokens[2].equals("LEFT")) associative = Associative.LEFT; else if (tokens[2].equals("RIGHT")) associative = Associative.RIGHT; else throw new IllegalArgumentException("结合性书写错误"); this.register(terminal, level, associative); } catch (NumberFormatException ex) { throw new IllegalArgumentException("优先级书写异常"); } catch (ClassCastException ex) { throw new IllegalArgumentException("运算符书写异常"); } } } /** * 注册运算符 * * @param terminal 运算符 * @param level 优先级 * @param associative 结合性 * @return 是否成功注册 */ public boolean register(Grammar.Terminal terminal, int level, Associative associative) { return this.putIfAbsent(terminal, new Pair<>(level, associative)) == null; } /** * @param terminal 指定运算符 * @return 指定运算符的优先级 */ public int levelOf(Grammar.Terminal terminal) { return this.get(terminal).getFirst(); } /** * @param terminal 指定运算符 * @return 指定运算符的结合性 */ public Associative associativeOf(Grammar.Terminal terminal) { return this.get(terminal).getSecond(); } } ``` ### SimpleParserTable.putInAction 之前我们填写 Action 表的时候，调用了如下函数，现在我们继续将其完成。 ```java private void putInAction(int u, Grammar.Symbol symbol, Action newAction) { Action preAction = this.actionTable.putIfAbsent(u, symbol, newAction); if (preAction == null) return; if (this.operatorTable == null) throw new UnsupportedOperationException("暂时未实现解决冲突的逻辑"); // todo } ``` 我们枚举所有可能性 - 如果新的动作是 acc，那么填入新的动作 - 如果新的动作是移入，旧的动作是移入，那么什么也不做 - 如果新的动作是归约，旧的动作是归约， - 如果一个动作是归约，一个动作是移入 #### R-R冲突 现在我们使用如下测试代码，检查 R-R 冲突的情形： ```java private void putInAction(int u, Grammar.Symbol symbol, Action newAction) { Action preAction = this.actionTable.putIfAbsent(u, symbol, newAction); if (preAction == null) return; // if (this.operatorTable == null) throw new UnsupportedOperationException("暂时未实现解决冲突的逻辑"); // todo if (newAction instanceof AcceptAction) this.actionTable.put(u, symbol, newAction); // 如果新的动作是 acc，那么填入新的动作 if (newAction instanceof ShiftAction && preAction instanceof ShiftAction) return; // 如果新的动作是移入，旧的动作是移入 if (newAction instanceof ReduceAction && preAction instanceof ReduceAction) { // 如果新的动作是归约，旧的动作是归约 System.out.println(List.of(fa.getStatus(u), preAction, newAction)); } } ``` 发现没有任何输出，那么发生这种情况，我们将不处理这个冲突，直接抛异常即可。抛异常的目的是为了避免其它文法被错误地处理。 #### S-R冲突 现在我们使用如下测试代码，检查 S-R 冲突的情形： ```java private void putInAction(int u, Grammar.Symbol symbol, Action newAction) { Action preAction = this.actionTable.putIfAbsent(u, symbol, newAction); if (preAction == null) return; // if (this.operatorTable == null) throw new UnsupportedOperationException("暂时未实现解决冲突的逻辑"); // todo if (newAction instanceof AcceptAction) this.actionTable.put(u, symbol, newAction); // 如果新的动作是 acc，那么填入新的动作 if (newAction instanceof ShiftAction && preAction instanceof ShiftAction) return; // 如果新的动作是移入，旧的动作是移入 if (newAction instanceof ReduceAction && preAction instanceof ReduceAction) { // 如果新的动作是归约，旧的动作是归约 throw new UnsupportedOperationException("我们假设没有归约-归约冲突"); // System.out.println("暂时未实现解决冲突的逻辑"); } // 是移入归约冲突 debugMap.putIfAbsent(u, new StringBuilder()); // debug debugMap.get(u).append(String.format("%s, %s\n", preAction, newAction)); // debug // System.out.println(List.of(fa.getStatus(u), preAction, newAction)); } ``` 输出中，有这么一些冲突现象： ```纯文本 [ArithExpr --> ArithExpr + ArithExpr • [<=, <>, $, *, +, <, -, =, ^, >, /, >=] ArithExpr --> ArithExpr • + ArithExpr [<=, <>, $, *, +, <, -, =, ^, >, /, >=] ArithExpr --> ArithExpr • - ArithExpr [<=, <>, $, *, +, <, -, =, ^, >, /, >=] ArithExpr --> ArithExpr • * ArithExpr [<=, <>, $, *, +, <, -, =, ^, >, /, >=] ArithExpr --> ArithExpr • / ArithExpr [<=, <>, $, *, +, <, -, =, ^, >, /, >=] ArithExpr --> ArithExpr • ^ ArithExpr [<=, <>, $, *, +, <, -, =, ^, >, /, >=] BoolExpr --> ArithExpr • > ArithExpr [&, |, ?] BoolExpr --> ArithExpr • >= ArithExpr [&, |, ?] BoolExpr --> ArithExpr • < ArithExpr [&, |, ?] BoolExpr --> ArithExpr • <= ArithExpr [&, |, ?] BoolExpr --> ArithExpr • = ArithExpr [&, |, ?] BoolExpr --> ArithExpr • <> ArithExpr [&, |, ?] , Shift 16, Reduce 3 Shift 17, Reduce 3 Shift 18, Reduce 3 Shift 19, Reduce 3 Shift 21, Reduce 3 Shift 24, Reduce 3 Reduce 3, Shift 22 Reduce 3, Shift 26 Reduce 3, Shift 20 Reduce 3, Shift 23 Reduce 3, Shift 25 ][BoolExpr --> ! Bool [ArithExpr --> neg ArithExpr • [<=, <>, $, *, +, <, -, =, ^, >, /, >=] ArithExpr --> ArithExpr • + ArithExpr [<=, <>, $, *, +, <, -, =, ^, >, /, >=] ArithExpr --> ArithExpr • - ArithExpr [<=, <>, $, *, +, <, -, =, ^, >, /, >=] ArithExpr --> ArithExpr • * ArithExpr [<=, <>, $, *, +, <, -, =, ^, >, /, >=] ArithExpr --> ArithExpr • / ArithExpr [<=, <>, $, *, +, <, -, =, ^, >, /, >=] ArithExpr --> ArithExpr • ^ ArithExpr [<=, <>, $, *, +, <, -, =, ^, >, /, >=] BoolExpr --> ArithExpr • > ArithExpr [&, |, ?] BoolExpr --> ArithExpr • >= ArithExpr [&, |, ?] BoolExpr --> ArithExpr • < ArithExpr [&, |, ?] BoolExpr --> ArithExpr • <= ArithExpr [&, |, ?] BoolExpr --> ArithExpr • = ArithExpr [&, |, ?] BoolExpr --> ArithExpr • <> ArithExpr [&, |, ?] , Shift 16, Reduce 8 Shift 17, Reduce 8 Shift 18, Reduce 8 Shift 19, Reduce 8 Shift 21, Reduce 8 Shift 22, Reduce 8 Shift 24, Reduce 8 Shift 26, Reduce 8 Reduce 8, Shift 20 Reduce 8, Shift 23 Reduce 8, Shift 25 ] [ArithExpr --> BoolExpr ? ArithExpr : ArithExpr • [<=, <>, ), *, +, ,, -, /, <, =, ^, >, >=] ArithExpr --> ArithExpr • + ArithExpr [<=, <>, ), *, +, ,, -, /, <, =, ^, >, >=] ArithExpr --> ArithExpr • - ArithExpr [<=, <>, ), *, +, ,, -, /, <, =, ^, >, >=] ArithExpr --> ArithExpr • * ArithExpr [<=, <>, ), *, +, ,, -, /, <, =, ^, >, >=] ArithExpr --> ArithExpr • / ArithExpr [<=, <>, ), *, +, ,, -, /, <, =, ^, >, >=] ArithExpr --> ArithExpr • ^ ArithExpr [<=, <>, ), *, +, ,, -, /, <, =, ^, >, >=] BoolExpr --> ArithExpr • > ArithExpr [&, |, ?] BoolExpr --> ArithExpr • >= ArithExpr [&, |, ?] BoolExpr --> ArithExpr • < ArithExpr [&, |, ?] BoolExpr --> ArithExpr • <= ArithExpr [&, |, ?] BoolExpr --> ArithExpr • = ArithExpr [&, |, ?] BoolExpr --> ArithExpr • <> ArithExpr [&, |, ?] , Shift 16, Reduce 9 Shift 17, Reduce 9 Shift 313, Reduce 9 Shift 314, Reduce 9 Shift 316, Reduce 9 Shift 22, Reduce 9 Shift 317, Reduce 9 Shift 24, Reduce 9 Shift 26, Reduce 9 Reduce 9, Shift 20 Reduce 9, Shift 318 ] [BoolExpr --> BoolExpr & BoolExpr • [&, |, ?] BoolExpr --> BoolExpr • & BoolExpr [&, |, ?] BoolExpr --> BoolExpr • | BoolExpr [&, |, ?] ArithExpr --> BoolExpr • ? ArithExpr : ArithExpr [<=, <>, *, +, <, =, -, >, ^, >=, /] , Shift 28, Reduce 27 Reduce 27, Shift 27 Reduce 27, Shift 99 ] [BoolExpr --> ! BoolExpr • [&, ), |, ?] BoolExpr --> BoolExpr • & BoolExpr [&, ), |, ?] BoolExpr --> BoolExpr • | BoolExpr [&, ), |, ?] ArithExpr --> BoolExpr • ? ArithExpr : ArithExpr [<=, <>, *, +, <, =, -, >, ^, >=, /] , Reduce 29, Shift 133 Reduce 29, Shift 135 Reduce 29, Shift 99 ] ``` 我们考虑记录Action表动作是由哪个Item触发的。 如果原来Item的运算符优先级更高，那么什么都不做 如果现在Item的运算符优先级更高，那么更换Item 如果原来Item的运算符优先级相同，那么考虑结合性。左结合使用归约，右结合使用移入 最终代码如下： ```java /** * 填入 Action 表，并根据运算符表处理冲突 * * @param u 状态编号 * @param symbol 终结符 * @param newAction 动作 * @param item 导致这次动作的 item */ private void putInAction(int u, Grammar.Symbol symbol, Action newAction, ParserFA.Item item) { Action preAction = this.actionTable.putIfAbsent(u, symbol, newAction); this.actionCause.putIfAbsent(u, symbol, item); if (preAction == null) return; // if (this.operatorTable == null) throw new UnsupportedOperationException("暂时未实现解决冲突的逻辑"); // todo if (newAction instanceof AcceptAction) { // 如果新的动作是 acc，那么填入新的动作 this.actionTable.put(u, symbol, newAction); this.actionCause.put(u, symbol, item); return; } if (newAction instanceof ReduceAction && preAction instanceof ReduceAction) { // 如果新的动作是归约，旧的动作是归约 throw new UnsupportedOperationException("我们假设没有归约-归约冲突，暂时未实现解决冲突的逻辑"); } // 是移入归约冲突 Grammar.Terminal preOp = this.getOperatorOf(this.actionCause.get(u, symbol)), nowOp = this.getOperatorOf(item); int preLevel = this.operatorTable.levelOf(preOp), nowLevel = this.operatorTable.levelOf((nowOp)); // 优先级不相等 if (preLevel > nowLevel) return; if (preLevel < nowLevel) { this.actionTable.put(u, symbol, newAction); this.actionCause.put(u, symbol, item); return; } // 优先级相等，判断结合性。左结合使用归约，右结合使用移入 OperatorTable.Associative associative = this.operatorTable.associativeOf(preOp); if (associative.equals(OperatorTable.Associative.RIGHT) && preAction instanceof ShiftAction) return; if (associative.equals(OperatorTable.Associative.LEFT) && preAction instanceof ReduceAction) return; this.actionTable.put(u, symbol, newAction); this.actionCause.put(u, symbol, item); } /** * 获得 item 的产生式的右部的运算符。判断为运算符的依据是是否在运算符表中注册。 * * @param item * @return item 的产生式的右部的运算符 */ private Grammar.Terminal getOperatorOf(ParserFA.Item item) { // 初始化 set List ret = new ArrayList<>(); for (Grammar.Symbol symbol : item.production().rightSide()) { try { Grammar.Terminal terminal = (Grammar.Terminal) symbol; if (this.operatorTable.containsKey(terminal)) ret.add(terminal); } catch (ClassCastException ignored) { } } // 先处理多个运算符的情况 if (ret.contains((Grammar.Terminal) this.grammar.getSymbol("("))) { // ( ) sin cos max min return (Grammar.Terminal) this.grammar.getSymbol("("); } if (ret.contains((Grammar.Terminal) this.grammar.getSymbol("?"))) { // ? : return (Grammar.Terminal) this.grammar.getSymbol("?"); } // 处理异常情况 if (ret.size() > 1) throw new UnknownError("产生式右部不应该出现多个运算符"); return ret.get(0); } ``` ### SimpleFactory.makeGrammar() 现在，代码如下： ```java public class SimpleFactory implements Factory { @Override public Grammar makeGrammar() { List nonTerminalSymbolExpressions = List.of("Expr", "ArithExpr", "BoolExpr", "UnaryFunc", "VariablFunc", "ArithExprList"); List terminalSymbolExpressions = List.of( "decimal", "true", "false", "+", "-", "*", "/", "^", "neg", "?", ":", "(", ")", ",", "sin", "cos", "max", "min", ">", ">=", "<", "<=", "=", "<>", "&", "|", "!", "$" ); SimpleGrammar grammar = new SimpleGrammar("Expr", nonTerminalSymbolExpressions, terminalSymbolExpressions, " ", "Expr ArithExpr", "ArithExpr decimal", "ArithExpr ( ArithExpr )", "ArithExpr ArithExpr + ArithExpr", "ArithExpr ArithExpr - ArithExpr", "ArithExpr ArithExpr * ArithExpr", "ArithExpr ArithExpr / ArithExpr", "ArithExpr ArithExpr ^ ArithExpr", "ArithExpr neg ArithExpr", "ArithExpr BoolExpr ? ArithExpr : ArithExpr", "ArithExpr UnaryFunc", "ArithExpr VariablFunc", "UnaryFunc sin ( ArithExpr )", "UnaryFunc cos ( ArithExpr )", "VariablFunc max ( ArithExpr , ArithExprList )", "VariablFunc min ( ArithExpr , ArithExprList )", "ArithExprList ArithExpr", "ArithExprList ArithExpr , ArithExprList", "BoolExpr true", "BoolExpr false", "BoolExpr ( BoolExpr )", "BoolExpr ArithExpr > ArithExpr", "BoolExpr ArithExpr >= ArithExpr", "BoolExpr ArithExpr < ArithExpr", "BoolExpr ArithExpr <= ArithExpr", "BoolExpr ArithExpr = ArithExpr", "BoolExpr ArithExpr <> ArithExpr", "BoolExpr BoolExpr & BoolExpr", "BoolExpr BoolExpr | BoolExpr", "BoolExpr ! BoolExpr" ); return grammar; } @Override public ParserTable makeParserTable() { Grammar grammar = this.makeGrammar(); OperatorTable operatorTable = new OperatorTable(grammar, " ", "( 1 LEFT", ") 1 LEFT", "sin 2 LEFT", "cos 2 LEFT", "max 2 LEFT", "min 2 LEFT", "neg 3 RIGHT", "^ 4 RIGHT", "* 5 LEFT", "/ 5 LEFT", "+ 6 LEFT", "- 6 LEFT", "> 7 LEFT", ">= 7 LEFT", "< 7 LEFT", "<= 7 LEFT", "= 7 LEFT", "<> 7 LEFT", "! 8 RIGHT", "& 9 LEFT", "| 10 LEFT", "? 11 RIGHT", ": 11 RIGHT" ); // System.out.println(operatorTable); return new SimpleParserTable(grammar, operatorTable); } } ``` 因为我们在词法分析多做了点事儿，所以我们把文法中的符号改为了 neg，以区别运算符重载。 ```纯文本 开始符号：Expr Production[leftSide=Expr, rightSide=[ArithExpr]] Production[leftSide=ArithExpr, rightSide=[decimal]] Production[leftSide=ArithExpr, rightSide=[(, ArithExpr, )]] Production[leftSide=ArithExpr, rightSide=[ArithExpr, +, ArithExpr]] Production[leftSide=ArithExpr, rightSide=[ArithExpr, -, ArithExpr]] Production[leftSide=ArithExpr, rightSide=[ArithExpr, *, ArithExpr]] Production[leftSide=ArithExpr, rightSide=[ArithExpr, /, ArithExpr]] Production[leftSide=ArithExpr, rightSide=[ArithExpr, ^, ArithExpr]] Production[leftSide=ArithExpr, rightSide=[neg, ArithExpr]] Production[leftSide=ArithExpr, rightSide=[BoolExpr, ?, ArithExpr, :, ArithExpr]] Production[leftSide=ArithExpr, rightSide=[UnaryFunc]] Production[leftSide=ArithExpr, rightSide=[VariablFunc]] Production[leftSide=UnaryFunc, rightSide=[sin, (, ArithExpr, )]] Production[leftSide=UnaryFunc, rightSide=[cos, (, ArithExpr, )]] Production[leftSide=VariablFunc, rightSide=[max, (, ArithExpr, ,, ArithExprList, )]] Production[leftSide=VariablFunc, rightSide=[min, (, ArithExpr, ,, ArithExprList, )]] Production[leftSide=ArithExprList, rightSide=[ArithExpr]] Production[leftSide=ArithExprList, rightSide=[ArithExpr, ,, ArithExprList]] Production[leftSide=BoolExpr, rightSide=[true]] Production[leftSide=BoolExpr, rightSide=[false]] Production[leftSide=BoolExpr, rightSide=[(, BoolExpr, )]] Production[leftSide=BoolExpr, rightSide=[ArithExpr, >, ArithExpr]] Production[leftSide=BoolExpr, rightSide=[ArithExpr, >=, ArithExpr]] Production[leftSide=BoolExpr, rightSide=[ArithExpr, <, ArithExpr]] Production[leftSide=BoolExpr, rightSide=[ArithExpr, <=, ArithExpr]] Production[leftSide=BoolExpr, rightSide=[ArithExpr, =, ArithExpr]] Production[leftSide=BoolExpr, rightSide=[ArithExpr, <>, ArithExpr]] Production[leftSide=BoolExpr, rightSide=[BoolExpr, &, BoolExpr]] Production[leftSide=BoolExpr, rightSide=[BoolExpr, |, BoolExpr]] Production[leftSide=BoolExpr, rightSide=[!, BoolExpr]] 终结符：[<=, <>, cos, neg, min, sin, ^, !, $, max, &, false, (, ), *, +, ,, -, /, true, :, decimal, <, |, =, >, ?, >=] 非终结符：[ArithExpr, BoolExpr, Expr, ArithExprList, UnaryFunc, VariablFunc] ``` ### MyParser接口 代码如下： ```java public interface MyParser { String parser(List tokens); } ``` ### SimpleParser.parser（简化版） 流程如下： ![](image/image_rfFja2gp-Y.png) 在开始之前，我们先考虑一些问题： - 部分token和terminal的表达式并不等价 - neg与ArithmeticOperator1DToken的特殊处理 - decimal与DecimalToken的特殊处理 - 结尾的\$如何处理 我们将上述功能放在update函数中，代码如下： ```java private void update() { // 到达结尾 if (this.lookaheadPtr == this.tokens.size()) { this.lookaheadTerminal = (Grammar.Terminal) this.grammar.getSymbol("$"); this.lookaheadToken = null; return; } // 取出并特殊处理 this.lookaheadToken = this.tokens.get(this.lookaheadPtr++); if (this.lookaheadToken instanceof MyScanner.DecimalToken) { // 数字 this.lookaheadTerminal = (Grammar.Terminal) this.grammar.getSymbol("decimal"); } else if (this.lookaheadToken instanceof MyScanner.ArithmeticOperator1DToken) { // 负号 this.lookaheadTerminal = (Grammar.Terminal) this.grammar.getSymbol("neg"); } else { // 其它 8 种： Boolean、ArithmeticOp2D、ArithmeticOp3D、CompareOp、LogicalOp1D、LogicalOp2D、DelimiterOp、Function this.lookaheadTerminal = (Grammar.Terminal) this.grammar.getSymbol(this.lookaheadToken.getExpression()); } } ``` 最终代码如下： ```java public class SimpleParser implements MyParser { @Override public String parser(List tokens) throws SyntacticException { // 初始化数据结构 Lookahead lookahead = new Lookahead(tokens, this.parserTable.getGrammar()); final List statuses = new ArrayList<>(); // 状态栈 final List symbols = new ArrayList<>(); // 符号栈 final Deque reduceBuffer = new LinkedList<>(); // 归约项缓冲区，由 parser 函数负责放入，语义分析函数负责拿出 statuses.add(1); symbols.add(this.parserTable.getGrammar().getSymbol("$")); // 开始归约 int deadline = tokens.size() * this.parserTable.size() * this.parserTable.size(); for (; deadline > 0; --deadline) { ParserTable.Action action = this.parserTable.getAction(statuses.get(statuses.size() - 1), lookahead.terminal()); // 根据状态栈顶、lookahead，查找 Action 表， if (action == null) this.exitWithException(symbols, lookahead.terminal()); // 如果是空。那么抛出异常 if (action instanceof ParserTable.AcceptAction) break; // 如果是接受 if (action instanceof ParserTable.ShiftAction) { // 如果是移入， symbols.add(lookahead.terminal()); // 那么移入 statuses.add(action.getId()); // 压入新的状态 lookahead.update(); // 更新 lookahead continue; } if (!(action instanceof ParserTable.ReduceAction)) throw new UnknownError("动作不是接受、移入、归约"); // 是归约 Grammar.Production production = this.parserTable.getGrammar().getProductions().get(action.getId()); // 找到归约项 for (int i = 0; i < production.rightSide().size(); ++i) { // 设归约项长度为 rSize，栈均弹出 rSize 个元素， reduceBuffer.addFirst(symbols.get(symbols.size() - 1)); // 放入 reduceBuffer 中 symbols.remove(symbols.size() - 1); statuses.remove(statuses.size() - 1); } symbols.add(production.leftSide()); // 将归约结果放入符号栈顶， statuses.add(this.parserTable.getGoto(statuses.get(statuses.size() - 1), production.leftSide())); // 根据状态栈顶、符号栈顶查找 Goto 表，并将跳转状态放入状态栈顶 } if (deadline == 0) throw new UnknownError("归约过程超时"); return null; } /** * 负责根据现状抛出异常 */ private void exitWithException(final List symbols, Grammar.Terminal lookahead) throws SyntacticException { throw new SyntacticException(); } private static class Lookahead { public void update() { } } } ``` - 内部类 Lookahead：集成之前的 update() 的功能，负责提供 lookahead 及其到 terminal的解码 - exitWithException()：负责判断异常类型，并抛出。我们将其放在语义分析一节讲述。 ## 语义分析 我们在语法分析的过程中，做语义分析。 ### SimpleParser.semanticAnalysis（语义分析） 我们对每一个产生式进行特殊处理即可 ```java "Expr ArithExpr", "ArithExpr decimal", "ArithExpr ( ArithExpr )", "ArithExpr ArithExpr + ArithExpr", "ArithExpr ArithExpr - ArithExpr", "ArithExpr ArithExpr * ArithExpr", "ArithExpr ArithExpr / ArithExpr", "ArithExpr ArithExpr ^ ArithExpr", "ArithExpr neg ArithExpr", "ArithExpr BoolExpr ? ArithExpr : ArithExpr", "ArithExpr UnaryFunc", "ArithExpr VariablFunc", "UnaryFunc sin ( ArithExpr )", "UnaryFunc cos ( ArithExpr )", "VariablFunc max ( ArithExpr , ArithExprList )", "VariablFunc min ( ArithExpr , ArithExprList )", "ArithExprList ArithExpr", "ArithExprList ArithExpr , ArithExprList", "BoolExpr true", "BoolExpr false", "BoolExpr ( BoolExpr )", "BoolExpr ArithExpr > ArithExpr", "BoolExpr ArithExpr >= ArithExpr", "BoolExpr ArithExpr < ArithExpr", "BoolExpr ArithExpr <= ArithExpr", "BoolExpr ArithExpr = ArithExpr", "BoolExpr ArithExpr <> ArithExpr", "BoolExpr BoolExpr & BoolExpr", "BoolExpr BoolExpr | BoolExpr", "BoolExpr ! BoolExpr" ``` 代码如下： ```java public class SemanticAnalyzer { public void analysis(final List codes, final Grammar.Production production) { // 先弹出归约项长度的中间代码，放入 buffer 中 LinkedList buffer = new LinkedList<>(); for (int i = 0; i < production.rightSide().size(); ++i) { buffer.addFirst(codes.remove(codes.size() - 1)); } // 处理各条产生式 double ArithExprL, ArithExprR; boolean BoolExprL, BoolExprR; int pid = this.grammar.getProductions().indexOf(production); // 产生式编号 switch (pid) { case 0: // "Expr ArithExpr" case 1: // "ArithExpr decimal" case 10: // "ArithExpr UnaryFunc" case 11:// "ArithExpr VariablFunc" case 16: // "ArithExprList ArithExpr" case 18: // "BoolExpr true" case 19: // "BoolExpr false" codes.add(buffer.getFirst()); break; case 2: // "ArithExpr ( ArithExpr )" case 20: // "BoolExpr ( BoolExpr )" codes.add(buffer.get(1)); break; case 3: // "ArithExpr ArithExpr + ArithExpr" case 4: // "ArithExpr ArithExpr - ArithExpr" case 5: // "ArithExpr ArithExpr * ArithExpr" case 7: // "ArithExpr ArithExpr ^ ArithExpr" ArithExprL = Double.parseDouble(buffer.get(0)); ArithExprR = Double.parseDouble(buffer.get(2)); switch (buffer.get(1)) { case "+" -> codes.add(Double.toString(ArithExprL + ArithExprR)); case "-" -> codes.add(Double.toString(ArithExprL - ArithExprR)); case "*" -> codes.add(Double.toString(ArithExprL * ArithExprR)); case "^" -> codes.add(Double.toString(Math.pow(ArithExprL, ArithExprR))); default -> throw new UnknownError("不是+-*/^"); } break; case 6: // "ArithExpr ArithExpr / ArithExpr" ArithExprL = Double.parseDouble(buffer.get(0)); ArithExprR = Double.parseDouble(buffer.get(2)); if (ArithExprR == 0) throw new DividedByZeroException(); codes.add(Double.toString(ArithExprL / ArithExprR)); break; case 8: // "ArithExpr neg ArithExpr" ArithExprR = Double.parseDouble(buffer.get(1)); codes.add(Double.toString(-ArithExprR)); break; case 9: // "ArithExpr BoolExpr ? ArithExpr : ArithExpr" BoolExprL = Boolean.parseBoolean(buffer.get(0)); ArithExprL = Double.parseDouble(buffer.get(2)); ArithExprR = Double.parseDouble(buffer.get(4)); if (BoolExprL) codes.add(Double.toString(ArithExprL)); else codes.add(Double.toString(ArithExprR)); break; case 12: // "UnaryFunc sin ( ArithExpr )" ArithExprL = Double.parseDouble(buffer.get(2)); codes.add(Double.toString(Math.sin(ArithExprL))); break; case 13: // "UnaryFunc cos ( ArithExpr )" ArithExprL = Double.parseDouble(buffer.get(2)); codes.add(Double.toString(Math.cos(ArithExprL))); break; case 14: // "VariablFunc max ( ArithExpr , ArithExprList )" case 15: // "VariablFunc min ( ArithExpr , ArithExprList )" ArithExprL = Double.parseDouble(buffer.get(2)); // System.out.println(buffer.get(4)); // debug // System.out.println(buffer.get(4).split(this.delimiter).length); // debug for (String expr : buffer.get(4).split(this.delimiter)) { // System.out.println("debug:" + expr + ":debug"); // debug switch (buffer.get(0)) { case "min" -> ArithExprL = Math.min(ArithExprL, Double.parseDouble(expr)); case "max" -> ArithExprL = Math.max(ArithExprL, Double.parseDouble(expr)); default -> throw new UnknownError("不是min、max"); } } codes.add(Double.toString(ArithExprL)); break; case 17: // "ArithExprList ArithExpr , ArithExprList" codes.add(buffer.get(0) + this.delimiter + buffer.get(2)); // todo break; case 21: // "BoolExpr ArithExpr > ArithExpr" case 22: // "BoolExpr ArithExpr >= ArithExpr" case 23: // "BoolExpr ArithExpr < ArithExpr" case 24: // "BoolExpr ArithExpr <= ArithExpr" case 25: // "BoolExpr ArithExpr = ArithExpr" case 26: // "BoolExpr ArithExpr <> ArithExpr" ArithExprL = Double.parseDouble(buffer.get(0)); ArithExprR = Double.parseDouble(buffer.get(2)); switch (buffer.get(1)) { case ">" -> codes.add(Boolean.toString(ArithExprL > ArithExprR)); case ">=" -> codes.add(Boolean.toString(ArithExprL >= ArithExprR)); case "<" -> codes.add(Boolean.toString(ArithExprL < ArithExprR)); case "<=" -> codes.add(Boolean.toString(ArithExprL <= ArithExprR)); case "=" -> codes.add(Boolean.toString(ArithExprL == ArithExprR)); case "<>" -> codes.add(Boolean.toString(ArithExprL != ArithExprR)); default -> throw new UnknownError("<=>"); } break; case 27: // "BoolExpr BoolExpr & BoolExpr" BoolExprL = Boolean.parseBoolean(buffer.get(0)); BoolExprR = Boolean.parseBoolean(buffer.get(2)); codes.add(Boolean.toString(BoolExprL & BoolExprR)); break; case 28: // "BoolExpr BoolExpr | BoolExpr" BoolExprL = Boolean.parseBoolean(buffer.get(0)); BoolExprR = Boolean.parseBoolean(buffer.get(2)); codes.add(Boolean.toString(BoolExprL | BoolExprR)); break; case 29: // "BoolExpr ! BoolExpr" BoolExprL = Boolean.parseBoolean(buffer.get(1)); codes.add(Boolean.toString(!BoolExprL)); break; } } } ``` > 我们顺便处理了DividedByZeroException异常 ### SimpleParser.exitWithException（异常处理） ![](image/image_amcUufkhci.png) 又来了……我们进行一个面向需求编程。简单来说就是跑样例，然后根据出现异常时，symbol栈的状态进行特殊处理。通过老师给出的16个测试样例之后，代码如下： ```java public class SimpleParser implements MyParser { /** * 预处理，并抛出部分异常 * * @param input token 列表 * @throws MissingLeftParenthesisException 缺少左括号 * @throws MissingRightParenthesisException 缺少右括号 * @throws TrinaryOperationException 三元运算符使用错误 */ private void checkBraceAnd3D(final List input) throws MissingLeftParenthesisException, MissingRightParenthesisException, TrinaryOperationException { int cntBrace = 0, cnt3D = 0; // 括号计数，三元运算符计数 for (MyScanner.Token token : input) { switch (token.getExpression()) { case "(" -> --cntBrace; case ")" -> ++cntBrace; case "?" -> --cnt3D; case ":" -> ++cnt3D; } if (cntBrace > 0) throw new MissingLeftParenthesisException(); if (cnt3D > 0) throw new TrinaryOperationException(); } if (cntBrace > 0) throw new MissingLeftParenthesisException(); if (cntBrace < 0) throw new MissingRightParenthesisException(); if (cnt3D != 0) throw new TrinaryOperationException(); } /** * 归约路径记录 */ private StringBuilder reducePath; /** * 负责根据现状抛出异常 * * @param symbols 符号 * @param lookahead 下一位 * @throws SyntacticException */ private void exitWithException(final LinkedList symbols, Grammar.Terminal lookahead) throws SyntacticException, TypeMismatchedException { if (this.detectArithExpr(symbols)) { // [$, ArithExpr, ^, (, ArithExpr, )], decimal switch (lookahead.getExpression()) { case "decimal" -> throw new MissingOperatorException(); // MissingOperatorException } } if (this.detectArithOp(symbols)) { // [$, ArithExpr, ^, (, ArithExpr, -], ) switch (lookahead.getExpression()) { case ")" -> throw new MissingOperandException(); // MissingOperandException } } if (this.detectBoolExpr(symbols)) { // [$, (, BoolExpr, )], + switch (lookahead.getExpression()) { case "+", "-", "*", "/", "^" -> throw new TypeMismatchedException(); // TypeMismatchedException } } if (this.detectMaxAndMinFunction(symbols)) { // [$, ArithExpr, +, max, (, ArithExpr, +, decimal], ) // [$, min, (, decimal], ) switch (lookahead.getExpression()) { case ")" -> throw new MissingOperandException(); // MissingOperandException } } if (this.detectSinAndCosFunction(symbols)) { // [$, sin, (, ArithExpr, +, decimal], , // [$, sin, (, decimal], , switch (lookahead.getExpression()) { case "," -> throw new FunctionCallException(); // FunctionCallException } } System.out.println(reducePath); // debug throw new SyntacticException(); } /** * 判断符号栈的结尾是否是算术表达式，这包括：ArithExpr、 ( ArithExpr ) * * @param symbols 符号栈 * @return 是否是算术表达式 */ private boolean detectArithExpr(LinkedList symbols) { if (symbols.getLast().getExpression().equals("ArithExpr")) return true; else if (symbols.getLast().getExpression().equals(")")) { String[] tmp = new String[]{symbols.get(symbols.size() - 3).getExpression(), symbols.get(symbols.size() - 2).getExpression(), symbols.get(symbols.size() - 1).getExpression()}; return tmp[0].equals("(") && tmp[1].equals("ArithExpr") && tmp[2].equals(")"); } return false; } /** * 判断符号栈的结尾是否是算术运算符，这包括：+ - * / ^ * * @param symbols 符号栈 * @return 是否是算术运算符 */ private boolean detectArithOp(LinkedList symbols) { switch (symbols.getLast().getExpression()) { case "+", "-", "*", "/", "^": return true; default: return false; } } /** * 判断符号栈的结尾是否是布尔表达式，这包括：BoolExpr、 ( BoolExpr ) * * @param symbols 符号栈 * @return 是否是布尔表达式 */ private boolean detectBoolExpr(LinkedList symbols) { if (symbols.getLast().getExpression().equals("BoolExpr")) return true; else if (symbols.getLast().getExpression().equals(")")) { String[] tmp = new String[]{symbols.get(symbols.size() - 3).getExpression(), symbols.get(symbols.size() - 2).getExpression(), symbols.get(symbols.size() - 1).getExpression()}; return tmp[0].equals("(") && tmp[1].equals("BoolExpr") && tmp[2].equals(")"); } return false; } /** * 判断符号栈的结尾是否是最值函数的一半，这包括：max ( ArithExpr + decimal、 min ( decimal * * @param symbols 符号栈 * @return 是否是最值函数的一半 */ private boolean detectMaxAndMinFunction(LinkedList symbols) { List buffer; if (symbols.size() < 3) return false; buffer = symbols.subList(symbols.size() - 3, symbols.size()).stream().map(Grammar.Symbol::getExpression).toList(); if (buffer.equals(List.of("max", "(", "decimal"))) return true; if (buffer.equals(List.of("min", "(", "decimal"))) return true; if (symbols.size() < 5) return false; buffer = symbols.subList(symbols.size() - 5, symbols.size()).stream().map(Grammar.Symbol::getExpression).toList(); if (buffer.equals(List.of("max", "(", "ArithExpr", "+", "decimal"))) return true; if (buffer.equals(List.of("min", "(", "ArithExpr", "+", "decimal"))) return true; return false; } /** * 判断符号栈的结尾是否是三角函数的一半，这包括：sin ( ArithExpr + decimal、 cos ( decimal * * @param symbols 符号栈 * @return 三角函数的一半 */ private boolean detectSinAndCosFunction(LinkedList symbols) { List buffer; if (symbols.size() < 3) return false; buffer = symbols.subList(symbols.size() - 3, symbols.size()).stream().map(Grammar.Symbol::getExpression).toList(); if (buffer.equals(List.of("cos", "(", "decimal"))) return true; if (buffer.equals(List.of("sin", "(", "decimal"))) return true; if (symbols.size() < 5) return false; buffer = symbols.subList(symbols.size() - 5, symbols.size()).stream().map(Grammar.Symbol::getExpression).toList(); if (buffer.equals(List.of("cos", "(", "ArithExpr", "+", "decimal"))) return true; if (buffer.equals(List.of("sin", "(", "ArithExpr", "+", "decimal"))) return true; return false; } } ``` ## 回归测试 由于助教没有提供pdf中的所有测试样例，所以我们写了个python辅助一下： ```python test_template = """ PDF%03d %s %s """ infomation = [ "3.e3 + 1", "IllegalDecimalException", "4 + 10.E+5 + 1", "IllegalDecimalException", "3.3e3.3 + 1", "IllegalDecimalException", "1 + 3.3E.3 + 2", "IllegalDecimalException", "1 + 3.3E-(3 + 2)", "IllegalDecimalException", "min(4., 7)", "IllegalDecimalException", "12.3Emax(4, 5, 6)", "IllegalDecimalException", "5 / v4 + 1/", "IllegalIdentifierException", "4 + mix(5, 2) + 1", "IllegalIdentifierException", " (5 @ 4) ? 7 : 8", "IllegalSymbolException", "(1 + 2) (3 - 4) - 5", "MissingOperatorException", "(1 + 2) ^ (3 - 4) 5", "MissingOperatorException", "cos(0.5)12.3E+4", "MissingOperatorException", "(1 + 2) ^ (3 - ) + 5", "MissingOperandException", "3 > 2.5 * 1.5 ? 9 :", "MissingOperandException", "3.14 * 2 >= 2.5 * 3 ? (6 : 7) + 8", "MissingOperandException", "7 > 0 ? 7 <= 0 ? : 6 : 5", "MissingOperandException", "sin()", "MissingOperandException", "min()", "MissingOperandException", "min(2.5)", "MissingOperandException", "min(, 1.8)", "MissingOperandException", "max(3.14, )", "MissingOperandException", "max(17, , 87)", "MissingOperandException", "max(3.14 + 2, )", "MissingOperandException", "max((5 < 6 ? 1 : 0), )", "MissingOperandException", "true ? : 5", "MissingOperandException", "2 + ( ? 4 : 5)", "MissingOperandException", "(2 + 3) ^ 3) - ((1 + 1)", "MissingLeftParenthesisException", "((2 + 3) ^ ((3 - 1) + 1)", "MissingRightParenthesisException", "sin(2, 1)", "FunctionCallException", "max5, 6, 8)", "FunctionCallException", "cos(3.14, )", "FunctionCallException", " false ? 9 : true ? 1 : 3 : 5", "TrinaryOperationException", "4 / (12 - 3 * 4) + 1", "DividedByZeroException", "(13 < 2 * 5) + 12", "TypeMismatchedException", "(13 < 2 * 5) + 12", "TypeMismatchedException", "12 ? 34 : 56", "TypeMismatchedException", "true ? 42.5 > 5 * 8 : 15", "TypeMismatchedException", "4 ^ (32.5 > 65)", "TypeMismatchedException", "sin(32.5 > 65)", "TypeMismatchedException", "32.5 | 65", "TypeMismatchedException", ] with open("./tmp", "w") as fout: for i in range(0, len(infomation), 2): fout.write(test_template%(i // 2 + 1, infomation[i + 1], infomation[i], infomation[i + 1])) ``` 最终得到了所有的测试样例。测试结果如下： ```纯文本 -------------------------------------------------------- Statistics Report (65 test cases): Passed case(s): 52 (80.0%) Warning case(s): 13 (20.0%) Failed case(s): 0 (0.0%) ======================================================== Press any key to continue . . . ``` 成功率还行。但是因为我们只进行到根据样例做相关的报错分类，所以错误类型仍然是有欠缺的。要是想完全控制异常抛出，一个可行的方法是写一张异常表： - 行是文法的所有的 item 集 - 列是所有的终结符 我们只要在指定位置填上对应的异常即可。 > 由于我无法在有效时间内完成这个工作，所以这里只是提一个方案 # personal.abandon包（附录） > 这部分是废案，之前用来生成词法分析自动机。与本项目关系不大，但是姑且放在这儿了 ## 从正则表达式生成DFA 我们的目的是生成能区分以下正则表达式的自动机，类似算法上的多重模式匹配问题。 ![](image/image_Vbm7NpNLCv.png) 设计的工作流程如下： - 遵守扩展型正则表达式的语法，写出正则表达式的字符串 - 扩展型正则表达式转标准型正则表达式：通过NFA匹配 - 从标准型正则表达式中获得转移表 - 正则表达式转NFA：汤普森构造法 - NFA转DFA：子集构造法 - 最小化DFA：子集划分法 我们将上述工作放在 personal.scanner 包中实现，另外 personal.scanner.util 包中是一些辅助类 > 看代码的时候，你可能会发现里面包含了处理泛用性和优先级的代码。这是因为早期立项目的时候希望程序生成的自动机能自行处理异常，但从结果来看，难度很大。故我暂且保持了代码的可扩展性。 ### ExREToStREConverter——扩展型正则表达式转标准型正则表达式 先说明“标准正则表达式”：int\[] - 使用 -int('e') 表示空串。 - 只有() \*|运算，其值是对应原生字符的负值。 - 其余正数值一律为原生字符。 我们定义“扩展正则表达式”：string - \e 表示空串。 - 将 () \*|- 视为运算符。 - 反而，上述运算符的原生字符需要通过转义给出，例如：\ \*。 我们的目的是，扩展型正则表达式是便于书写的，标准型正则表达式是便于处理的。 为了便于处理，我们手搓一个小自动机： ![](image/image_WUoAYJXODP.png) ```mermaid flowchart LR 开始--开始-->n1{n1} n1((n1))--"[^()*|-]"-->n1 n1--"()*|"-->n4((n4))--ε-->n1 n1--"\"-->n2{n2}--"e"-->n3((n3))--ε-->n1 n2--"[()*|-\]"-->n1 n1--"-"-->n5{n5}--"任意字符"-->n6((n6))--ε-->n1 ``` ### StREToNFAConverter——标准型正则表达式转 NFA 递归处理表达式，并通过改良版的汤普森构造法构造。 以下列出构造范例： a|b：标准的汤普森构造 ```mermaid flowchart LR 1 --ε--> 2 --a--> 3 --ε--> 4 1 --ε--> 5 --b--> 6 --ε--> 4 ``` a(bc)a：括号两侧会留下 ε ```mermaid flowchart LR 1 --a--> 2 --ε--> 3 --b--> 4 --c--> 5 --ε--> 6 --a--> 7 ``` ab\*a：闭包会直接在原地连接空串 ```mermaid flowchart LR 2 --ε--> 3 --ε--> 2 1 --a--> 2 --b--> 3 --a--> 4 ``` a(bc)\*a：闭包会直接在原地连接空串，但是括号两侧留有 ε，所以不会出现问题 ```mermaid flowchart LR 3 --ε--> 5 --ε--> 3 1 --a--> 2 --ε--> 3 --b--> 4 --c--> 5 --ε--> 6 --a--> 7 ``` 由于逻辑有一些复杂，所以在此讲解一下。 先列出各个函数： ```java /** * 正则表达式转 NFA，我们禁止正则表达式中出现*|() * * @author 陈渤林 */ public class StREToNFAConverter { /** * 找出与指定的左括号匹配的右括号 * * @param left_pos 指定的左括号的下标 * @return 匹配的右括号的下标 */ private int findMatchedRightIndex(int left_pos) throws IllegalArgumentException { } /** * 将 re[l, r] 沿 | 分割。注意，我们将 () 子区间视为一个整体，其不会被划分开 * * @param l 指定区间左端点 * @param r 指定区间右端点 * @return 分割后的区间，以 list 返回，list 中每两个元素视为一个二元组 */ private List divideByUnion(int l, int r) { } /** * 处理 re[l, r] 中的 | 运算，子图节点编号范围是 [s, t]。按指定区间逐个递归处理，再将处理结果合并， * * @param s 初始编号， * @param intervals 给出的指定区间，每两个元素视为一个二元组 * @return 结束编号 t， */ private int convertByUnion(int s, final List intervals) { } /** * 处理 re[l, r]，子图节点编号范围是 [s, t] * * @param l 区间左端点 * @param r 区间右端点 * @param s 初始编号， * @return 结束编号 t， */ private int convert(int l, int r, int s) { } /** * 将指定的正则表达式转换成 NFA，我们认为你的正则表达式有足够多的括号 * * @param re 指定的正则表达式 * @param transitions 字母表 * @param startId 自动机开始编号 * @param acceptId 接受值 * @return 转换后的 NFA */ public FiniteAutomata convert(final String re, int startId, int acceptId) { } } ``` - divideByUnion 函数负责检测指定的子表达式是否是**多个子表达式的并**，即是否具有：(……) | (……) 形式。 - convert 函数会先调用divideByUnion， - 如果具有上述形式，那么交由 convertByUnion 函数处理， - 否则，只需要处理 () 子表达式、闭包、连接，交给 if-else 即可 - convertByUnion函数负责沿 divideByUnion 函数划分的子区间递归调用 convert 函数进行处理，最后合并结果 ### NFAToDFAConverter——NFA转DFA 子集构造法 transition： $\operatorname{move}(T, a)=\{t \mid s \in T, s \stackrel{a}{\rightarrow} t\}$：T集合中的状态s，通过a能转移到的状态t的集合 $\varepsilon-closure (T)=move(T, \varepsilon)$：T集合中的状态s，通过空串能转移到的状态t的集合 禁止空串转移： - 构造NFA中，每一个节点u的空串转移集合 $I_u$ - 构造上述每一个集合I 的转移表（集合通过转移能到达的集合） - 此时转移表即是DFA - 如果表项对应的集合中存在NFA的接受节点，那么该DFA节点是可接受节点 例子： ![](image/image_EF_ZSqHwxK.png) ### DFAMinimizer——DFA最小化 集合划分法 ![](image/image_wPQdp75HWw.png) 详细说明一下构造新划分的过程 考虑有限自动机中的一个点集S，字母表集合T， **无法分辨**：出边相同：$\forall t \in T, \forall i, j \in S, \operatorname{Move}(i, t)=\operatorname{Move}(j, t)$ **可分辨**：出边不同：$\exist t \in T, \exist i, j \in S, \operatorname{Move}(i, t) \not=\operatorname{Move}(j, t)$ ### personal.TestDrive 在 personal.TestDrive 中，我们按照之前定义的扩展型正则表达式的语法，写出各个词素的正则表达式 数值类型的正则表达式： ![](image/image_Vbm7NpNLCv.png) ```java String digit = "0-9"; String integral = String.format("(%s)(%s)*", digit, digit); // 整数 String fraction = String.format(".(%s)", integral); // 小数 String exponent = String.format("(E|e)(+|\\-|\\e)(%s)", integral); // 指数 String decimal = String.format("(%s)((%s)|\\e)((%s)|\\e)", integral, fraction, exponent); // 浮点数 String numericTypeRE = String.format("(%s)|(%s)", integral, decimal); // 数值类型 ``` 自动机： ```mermaid flowchart LR 开始-->n1 n1{"1"} --"0 1 2 3 4 \n5 6 7 8 9 \n"--> n7(("7")) n2{"2"} --"0 1 2 3 4 \n5 6 7 8 9 \n"--> n6(("6")) n3{"3"} --"0 1 2 3 4 \n5 6 7 8 9 \n"--> n5(("5")) n4{"4"} --"+ - "--> n3{"3"} n4{"4"} --"0 1 2 3 4 \n5 6 7 8 9 \n"--> n5(("5")) n5(("5")) --"0 1 2 3 4 \n5 6 7 8 9 \n"--> n5(("5")) n6(("6")) --"E e "--> n4{"4"} n6(("6")) --"0 1 2 3 4 \n5 6 7 8 9 \n"--> n6(("6")) n7(("7")) --". "--> n2{"2"} n7(("7")) --"E e "--> n4{"4"} n7(("7")) --"0 1 2 3 4 \n5 6 7 8 9 \n"--> n7(("7")) ``` 布尔类型： ```mermaid flowchart LR 开始-->n1 n1{"1"} --"t "--> n6{"6"} n1{"1"} --"f "--> n7{"7"} n2{"2"} --"l "--> n5{"5"} n3{"3"} --"e "--> n8(("8")) n4{"4"} --"u "--> n3{"3"} n5{"5"} --"s "--> n3{"3"} n6{"6"} --"r "--> n4{"4"} n7{"7"} --"a "--> n2{"2"} ``` 运算符类型： ```java String arithmeticOperator = String.format("(%s)|(%s)|(%s)|(%s)|(%s)", "+", "\\-", "\\*", "/", "^"); // 算术运算符 String comparisonOperator = String.format("(%s)|(%s)|(%s)|(%s)|(%s)|(%s)", ">", "<", "=", ">=", "<=", "<>"); // 比较运算符 String relationalOperator = String.format("(%s)|(%s)|(%s)", "&", "\\|", "!"); // 关系运算符 String booleanOperator = String.format("(%s)|(%s)", comparisonOperator, relationalOperator); // 布尔运算符 String otherOperator = String.format("(%s)|(%s)|(%s)|(%s)|(%s)", "?", ":", ",", "\\(", "\\)"); // 三目运算符、逗号运算符、括号运算符 String operatorTypeRE = String.format("(%s)|(%s)|(%s)", arithmeticOperator, booleanOperator, otherOperator);// 上述三种运算符 ``` 自动机： ```mermaid flowchart LR 开始-->n1 n1{"1"} --"! & ( ) * \n+ , - / : \n| = ^ ? "--> n2(("2")) n1{"1"} --"< "--> n3(("3")) n1{"1"} --"> "--> n4(("4")) n3(("3")) --"= > "--> n2(("2")) n4(("4")) --"= "--> n2(("2")) ``` 预定函数： ```mermaid flowchart LR 开始-->n1 n1{"1"} --"c "--> n2{"2"} n1{"1"} --"s "--> n4{"4"} n1{"1"} --"m "--> n7{"7"} n2{"2"} --"o "--> n6{"6"} n3{"3"} --"n "--> n8(("8")) n4{"4"} --"i "--> n3{"3"} n5{"5"} --"x "--> n8(("8")) n6{"6"} --"s "--> n8(("8")) n7{"7"} --"i "--> n3{"3"} n7{"7"} --"a "--> n5{"5"} ``` 接下来只需要将这些自动机拼接起来即可