该实验项目实现了一个通用的正则词法分析器和LALR(1)语法分析器。词法分析器通过扩展正则语法（支持字符类、方括号等）构建DFA，采用最长匹配算法生成Token序列。语法分析器基于LALR(1)自动机，通过闭包计算和向前看符号传播算法生成规约序列。系统定义了.myl词法文件格式（正则规则）和.myy语法文件格式（产生式规则），支持增量分析模式。项目包含龙书例题和C语言子集的完整测试用例，实现了从字符流到语法树的完整解析流程，验证了Thompson算法、子集构造、LR状态机构建等核心编译原理技术。
由Azure AI部署的DeepSeek-R1模型推理
这是一个编译原理课的大作业，我自己实现了一个正则语法分析器（从输入字符流到Token序列）和LALR(1)语法分析器（Token序列到规约产生式序列）。以下是说明文档。
项目是放在一个repo的子文件夹里的，目录是：https://github.com/ddadaal/Homework/tree/master/Compiler/CompilerLab
实现一个能解析正则表达式和一些扩展语法的通用词法分析器，和使用LALR(1)进行语法分析的语法分析器，并定义一个能够以上提到的分析器所解析的词法定义文件（.myl）和语法定义文件（.myy）的格式，并能够做到通过在系统指定的可用Token集合上，从用户给定的词法定义文件和语法定义文件，实现从输入文件到产生式规约序列的全过程。
本实验提供了以下内容：
一个Intellij IDEA格式的Java项目，包含了目标中提到的词法分析器、语法分析器以及对应分析器的一些测例。
能被分析器所解析的词法定义文件（.myl）和语法定义文件（.myy）的格式描述
以龙书上例题4.31为依据的输入文件、输出文件、myl词法定义文件和myy语法定义文件，并提供了对应的测例
一个C语言子集的输入文件、输出文件、myl词法定义文件和myy语法定义文件。同时还提供了与其中myl和myy等价的flex/bison定义文件以及对应的一些工具程序。提供的词法定义和语法定义已经经过flex和bison测试可以完整无错误的解析提供的输入文件。
一个myl包含数个以下格式的词法定义，每个定义之间可接受任意个数的空行。
第一行：正则表达式的字符串
第二行：对应的TokenType的字符串
其中，正则表达式支持以下元素：
扩展支持：
方括号内部出现的元素之间会通过并集|连接，可与字符类配套使用。
例如：[ac\n]等价于(a|c|\n)
在ASCII表中，-前面的符号和后面的符号之间的所有符号会通过并集|连接。
例如：[a-d]等价于(a|b|c|d)
例如：[\n\ba-d_]等价于(\n|\b|(a|b|c|d)|_)
示例：
\+
PLUS （定义一个正则表达式为\+，对应到PLUS类型的Token的匹配规则，）
\*
STAR（定义一个正则表达式为\*，对应到STAR类型的token的匹配规则）
\(
LEFT_PARENTHESIS
\)
RIGHT_PARENTHESIS
[a-zA-Z]([0-9a-zA-Z_])*
IDENTIFIER （定义一个正则表达式为[a-zA-Z]([0-9a-zA-Z_])*（即以字母开头，后面跟任意个数的数字、字母或下划线），对应到IDENTIFIER类型的token转换规则）
[\ \n\r]
IGNORED （定义空格、空行或\r字符都被匹配到IGNORED类型的token的转换规则）
一个myy文件以一个字符串（代表此产生式列表的开始符，这个开始符可多次出现在产生式的左边）占一行开始，接下来由数个以下格式的语法定义组成，每个语法定义代表一系列具有相同左侧符号的产生式的集合，每个定义之间可接受任意个数的空行。
第一行：一个字符串，代表本产生式集合左边的符号
第二行开始：每一行代表一个产生式的右侧的符号列表。每个符号之间用任意个数的空格隔开。若一行为空，则代表这是一个epsilon产生式。若一个符号包含在TokenType列表里，则这个符号会被认为是一个终结符
本集合最后一个产生式后一行：符号"%"
示例：
E （代表这个产生式列表的开始符为E）
E （定义这个产生式集合的左侧符号为E）
E PLUS T （定义一个E -> E PLUS T的产生式，PLUS是一个类型为PLUS的终结符）
T （定义一个E -> T的产生式）
% （以E为左侧的产生式集合定义完毕）
T （定义这个产生式集合的左侧符号为T）
T STAR F （定义一个F -> T STAR F的产生式，STAR是一个类型为STAR的终结符）
F （定义一个T -> F的产生式）
% （以T为左侧的产生式集合定义完毕）
F （定义这个产生式集合的左侧符号为F）
LEFT_PARENTHESIS E RIGHT_PARENTHESIS （定义一个F -> LEFT_PARENTHESIS E RIGHT_PARENTHESIS的产生式，LEFT_PARENTHESIS和RIGHT_PARENTHESIS是终结符）
IDENTIFIER （定义一个F -> IDENTIFIER的产生式）
（定义一个F -> epsilon的epsilon产生式）
% （以F为左侧的产生式集合定义完毕）
词法定义 --> 词法DFA
语法定义 --> 语法LALR(1) DFA
输入文件 --词法DFA--> Token序列 --语法LALR(1) DFA--> 规约产生式列表
其中，词法分析器每读取一个到一个Token即暂停对输入字符的读取，转发给语法分析器进行语法分析；当语法分析器需要更多Token的时候，词法分析才继续对输入字符的读取，并不是首先生成所有的Token，再一次性交给语法LRDFA进行语法分析。
项目中假设只会用到以下类型的Token。若需要更多类型的Token，可在lex.internal.token.TokenType枚举类型下增加更多的Token类型。
注意，在产生式中出现Token类型列表所包含的字符串，将被认为是对应类型的终结符。字面量仅用于调试和错误报告中。
| Token类型 | 字面量 | 备注 |
|---|---|---|
| VOID | void | |
| INT | int | |
| RETURN | return | |
| WHILE | while | |
| IF | if | |
| ELSE | else | |
| ELLIPSIS | ... | |
| EQUAL | == | |
| ASSIGN | = | |
| SEMICOLON | ; | |
| STAR | * | |
| OR_OR | ||
| LEFT_BRACE | { | |
| RIGHT_BRACE | } | |
| LEFT_PARENTHESIS | ) | |
| RIGHT_PARENTHESIS | ) | |
| COMMA | , | |
| PLUS | + | |
| MINUS | - | |
| DIV | / | |
| INC | ++ | |
| LT | < | |
| LE | <= | |
| IDENTIFIER | id | |
| INT_CONST | int_const | |
| STR_CONST | str_const | |
| IGNORED | IGNORED类型的token将不会传送给语法分析器 | |
| DOLLAR_R | $R | 当词法分析器结束了所有的读取时，语法分析器无法获得下一个Token，则语法分析器会认为下一个Token是$R |
| UNKNOWN | # | 若词法分析器分析到UNKNOWN类型的Token，将会抛出LexicalParseException |
| EOF | $eof | 词法分析器结束了所有的读取时，将会返回$eof类型的Token |
词法分析器设计到的数据结构有DFA, DFANode, NFA, NFANode, Regex, RegexNode和Rule。
Regex顾名思义代表一个正则表达式，一个Regex是由一个RegexNode的列表所组成的。
一个RegexNode代表一个正则表达式的符号，其中正则表达式的符号即为正则表达式标准定义中的集几种组成元素，包括以下几种类型：
每个RegexNode都存储了这个RegexNode的类型和它的字面量值，以及其对应的优先级。优先级仅用于连接和并集的优先级选择上，其中连接的连接的优先级高于闭包。这个优先级将会在正则表达式中缀转后缀的过程中起作用。
RegexNode通过lombok生成了equals和hashCode方法，以方便比较两个RegexNode的相等性。两个RegexNode相等当且仅当两个Regex具有相同的类型且具有相同的字面量值。
NFA顾名思义代表一个对于一个正则表达式的NFA。本系统里的NFA是根据Thompson算法做出来的，而通过Thompson算法做出的对于一个正则表达式的NFA只有一个结束状态，故本系统中一个NFA是由代表开始状态的NFANode和一个代表结束状态的NFANode组成的。
NFANode代表一个NFA中的节点，或者说一个NFA的状态。一个NFANode是由一个以自己为出发边的边的集合和对应的正则表达式所对应的token类型所组成的。
前者（以自己为出发边的边的集合）在Java中的表示形式为Map<Character, List<NFANode>>，其key代表边上的字符，value代表通过key字符能够达到的状态的集合。
后者（对应的正则表达式所对应的token类型）对应在词法定义文件中，满足此正则表达式的字符串应该被语法分析及其后续过程认为的Token的类型。
NFA的边集没有单独保存，而是通过每个NFANode的以自己为出发边的边的集合表示。
DFA顾名思义代表一个对于一份词法定义文件的DFA，由一个标志开始状态的DFANode和这个DFA所有的接受状态的列表组成。本系统里DFA是以下算法得到的：
DFANode代表一个DFA中的节点，或者说一个DFA的状态。一个DFANode是由它所对应的NFA状态的集合、以自己为出发边的边的集合和自己所对应的所有可能的token类型的集合所组成的。
第一项（所对应的NFA状态的集合）即在子集构造算法中，构成这个DFA状态的NFANode的集合。
第二项（以自己的为出发边的边的集合）在Java中的表示形式为Map<Character, List<NFANode>>，其key代表边上的字符，value代表通过key字符能够达到的状态的集合。
第三项（自己所对应的所有可能的token类型的集合）即这个DFA状态对应的NFANode所对应的正则表达式所对应的token类型的并集。“这个DFA所对应的NFA状态的集合中包括至少一个结束状态的NFANode”是“DFANode所对应的所有可能的token类型的集合非空”的充要条件。通过保存这个集合能够减少词法分析的时间。
DFA的边集没有单独保存，而是通过每个DFANode的以自己为出发边的边的集合表示。
DFANode重写了equals方法。两个DFANode相等当且仅当两个DFANode具有相同的自己所对应的所有可能的token类型的集合。虽然NFANode并没有重写equals方法，但是在算法过程中保证了没有新的NFANode产生，保证了两个NFANode相等当且仅当它们是同一个对象。
一个Rule代表词法定义文件中定义的转换规则，由一个正则表达式的字符串和对应的Token类型组成。它仅被用于表示用户的词法定义。
语法分析器用到的数据结构有Symbol, Production, ProductionList, LRItem, LRDFA, LRDFANode。
Symbol（符号）是语法分析过程的基本单位，有两个属性组成：代表非终结符名称的ntName和代表终结符Token类型的tokenType。一个符号要么是一个非终结符（nt != null && tokenType == null），要么是一个终结符（nt == null && tokenType != null）。通过调用Symbol.terminal(TokenType)或者Symbol.nonterminal(String)可以分别产生一个终结符或者非终结符实例。
Symbol实现了equals和hashCode方法，两个Symbol相等当且仅当（两个Symbol都是非终结符 && 两个Symbol的非终结符名称相同） || (两个Symbol都是终结符 && 两个Symbol的终结符Token类型相同)。实现hashCode方法允许了将其作为HashMap的Key值，简化了后续的编程。这两个方法都是由lombok实现的。
Production代表一个产生式，由**产生式左边的符号(left)和产生式右边的符号列表(right)**组成。当产生式右边的符号列表为空的时候，代表这是一个epsilon产生式。
Production实现了equals和hashCode方法。两个Production相等当且仅当两个产生式具有相同的产生式左边的符号和产生式右边的符号列表（包括顺序）。实现hashCode方法允许了将其作为HashMap的Key值，简化了后续的编程。这两个方法都是由lombok实现的。
一个ProductionList代表一个产生式列表，一个ProductionList只允许有一个左边是开始符的产生式。所以，一个产生式列表由产生式的列表，初始产生式(startProduction），即左边是开始符的唯一的产生式和**开始符（startSymbol）**组成。
为了简化编程，一个ProductionList还提供了计算函数First(Symbol)以计算一个符号的First函数值，和canDeriveToEpsilon(Symbol)以判断一个符号是否能推出epsilon表达式。为了减少计算时间，这两个函数将会在计算出一个Symbol的结果后，将其结果记录到一个Map中（firstMemo和canDeriveToEpsilonMemo），下次再进行相同的符号的时候，函数将直接从对应的map中直接取值。
一个LRItem代表一个LR项，由对应产生式(production)、**点的位置(dotPosition)和向前看符号(lookaheadSymbol)**组成。根据向前看符号是否为null，一个LRItem可能是一个LR(0)项（lookaheadSymbol == null），也可能是一个LALR(1)项（lookaheadSymbol != null）。
LRItem实现了equals和hashCode方法。两个LRItem相等当且仅当两个LRItem具有相同的对应产生式，点的位置和向前看符号。实现hashCode方法允许了将其作为HashMap的Key值，简化了后续的编程。这两个方法都是由lombok实现的。
LRDFANode代表一个LR自动机中的一个状态，由代表这个状态的内核(kernel)的LR项（LRItem）的集合、组成整个状态的LR项的集合和以自己为出发边的边的集合组成。其中，以自己为出发边的边的集合在Java中的表示形式为Map<Character, List<LRDFANode>>，其key代表边上的字符，value代表通过key字符能够达到的状态的集合。根据组成其的LR项的类型（LR(0)项或者LALR(1)项），这个LRDFANode可能是LR(0)自动机或者LALR(1)自动机的一个状态。
LRDFANode重写了equals和hashCode方法。两个LRDFANode相等当且仅当它们具有相同的内核。实现hashCode方法允许了将其作为HashMap的Key值，简化了后续的编程。
一个LRDFA代表一个LR确定自动机，由开始状态(startState)、**结束状态列表(endStates)和所有状态列表(allNodes)**组成。根据其中包含的状态的类型（LR(0)或者LALR(1)），这个自动机可能是LR(0)自动机或者LALR(1)自动机。
对应的方法：lex.MylexReader.read
首先去掉忽略所有空格行，读到非空格行第一行认为是正则表达式，第二行认为是Token，调用TokenType.valueOf将字符串转换为TokenType。循环这个过程直到输入结束。
对应的方法：lex.internal.NFA.constructNFA
此过程分为4个子过程：正则表达式字符串预处理，加入点符号，中缀正则表达式转后缀和后缀正则表达式转NFA。
对应的方法：lex.internal.Regex.preprocess
预处理过程会将中括号和字符类的符号转换为只包含字符、*、|和()的标准正则表达式，并将字符串转换为RegexNode的列表。具体转换规则如下：
对应的方法：lex.internal.Regex.addConcatenation
遍历预处理后的RegexNode列表，在满足以下条件的两个符号之间加入点符号，表示这是两个正则表达式相连接的而构成的。
对应的方法：lex.internal.Regex.toPostfix
将加入点符号的RegexNode列表转换为后缀表达式，其中
对应的方法：lex.internal.NFA.constructNFA
使用Thompson算法，将一个后缀正则表达式转换为一个NFA。其中，每个后缀正则表达式的结束状态的对应的正则表达式所对应的token类型被设置为对应转换规则所规定的Token类型，非结束状态的状态的对应的正则表达式所对应的token类型为null。
对应的方法：lex.LexicalAnalyzer.constructDFA，43-53
得到所有转换规则的正则表达式的NFA后，新增一个开始状态，将这个开始状态用epsilon边连接到所有NFA的开始状态，得到一个lNFA。
对应的方法：lex.internal.DFA.constructDFA
使用子集构造算法（龙书图3-29，算法3.20），将lNFA转换为对应的DFA。其中每个DFA状态（DFANode）自己所对应的所有可能的token类型的集合包含组成这个DFANode的NFANode的对应的正则表达式所对应的token类型的并集。构建出来的DFA被称作词法DFA，是后续进行词法分析的核心组件。
子集构造算法中使用的epsilon闭包的计算算法为龙书图3-30。
对应的方法：syntax.MyYaccReader.read
首先忽略带开头的所有空行，读到第一个字符串被认为是整个产生式列表的开始符。继续往后读，重复一下步骤直到没有进一步的输入：
最后，调用ProductionList.fromUnaugmentedList方法，给整个产生式列表加入一个新的开始符S'和新的初始产生式S' -> {原开始符}。
对应的方法：syntax.constructLR0DFA
对应的方法：syntax.internal.LRDFA.closure
采用书上图4-32所采用的CLOSURE的计算方法。为了提高效率，会使用一个栈来保存还没有进行状态内扩展的项。在函数刚进入的时候，内核的所有项将会入栈；在每次执行算法的时候，会弹出栈顶，在这个过程中新产生的LR项将会入栈；当栈为空的时候，说明没有可以继续进行状态内扩展的LR项，表明闭包构建完成。
注意，在闭包构建过程中会产生新的LRItem对象。由于LRItem对象重写了equals方法，所以这些新产生的LRItem对象和之前可能已经存在LRItem对象无异。
注意，若输入的LR项存在向前看符号（即为LALR(1)项），设为(A -> a.Bc, d)_，则将会计算First(cd)，并将这些向前看符号加入到LRItem对象中。
对应的方法：syntax.constructLR0DFA
对应算法：syntax.addLookaheadSymbol
在这个算法中需要用到First函数，以及判断一个符号是否能够推出epsilon。由于它们仅依赖产生式列表，为了方便代码的维护以及设计缓存增加计算效率，所以这两个方法都写在ProductionList作为它们的实例方法。
判断一个符号是否能推出epsilon：syntax.internal.ProductionList.canDeriveToEpsilon
First算法：syntax.internal.ProductionList.first
使用书上算法4.47（自生成-传播算法），将LR(0)自动机中的所有状态中的所有LR项加上向前看符号（lookahead symbol），构建LALR(1)自动机。
对应算法：syntax.addLookaheadSymbol
首先定义一个新的数据结构StateSpecificLRItem，保存一个LRDFANode项和LRItem项，用于记录一个LRItem项及其它所属的LRDFANode。
<StateSpecificLRItem, List<StateSpecificLRItem>>，用于记录向前看符号的传播路径。在这个Map中，Key所拥有的向前看符号都会最终传播给它的Value中的所有LR项。Map<StateSpecificLRItem, List<Symbol>>，用于记录每对一个LR项，它通过自生成或者传播所得到的所有向前看符号的集合。对应方法：lex.LexicalAnalyzer.next
这个过程实现了最长匹配。在这个过程中，一旦返回Token，词法分析暂停，等待语法分析程序需要更多的Token时再继续分析。
在分析之前，已经通过输入的词法定义文件获得了对应的DFA。
对应方法：syntax.SyntaxAnalyzer.getProductionSequence
这个过程通过输入Token序列流，能够返回所有使用到的规约产生式序列。
这个过程没有像书上一样采用LALR(1)分析表实现，而是直接通过使用LALR(1) DFA来进行分析，其核心理念是相同的（移入-规约），核心算法几乎一致（书上算法4.30），而且LALR(1)分析表也是通过LALR(1) DFA获得的。直接使用LALR(1)方便编程。
CompilerLab要运行这个测试，请运行test/java/IntegrationTest::testExample431。这个测例将读取main/java/resources/example4.31下预先提供的输入文件、词法定义文件和语法分析文件，将输入文件进行词法和语法分析，得到规约序列，并与测试中写好的预期序列进行比较，得出测试结果。示例（以及确保正确的）的输出结果位于main/java/resources/example4.31/output中。
这个C语言子集提供了flex/bison项目以及基于等价myl, myy定义文件的运行方式。
flex/bison项目中包含了这个C语言子集对应的.l和.y定义文件。要运行flex/bison项目，请参考CSubsetFlexBison目录下的说明文档。
与flex/bison项目中提到的C语言子集等价的词法定义文件和语法定义文件，以及和flex/bison项目中示例文件test.c完全相同的示例输入文件均位于main/java/resources/bigtest下。测试用例test/java/IntegrationTest::bigTest将读取输入文件、词法定义文件和语法分析文件，将输入文件进行词法和语法分析，输出规约序列。注意此“测试”由于比较复杂（规约序列中包含200余条产生式），故只提供了程序的输出信息(main/java/resources/bigtest/output文件)，并没有进行正确性验证。
在开发过程中，单元测试起到了测试一个功能点正确性的作用。本项目中test/java/LexTest和test/java/SyntaxTest包含了编写词法和语法分析器过程中所用到的单元测试，若有兴趣，可自行运行。
仅举几个例子。
使用公式递归计算First函数的时候，容易遇到类似First(A) = First(A) U First(B)...的无限递归的情况。根据集合方程的特性，在这种情况下可以直接忽略右侧的First(A)，这样即可避免无穷递归的问题，成功算出函数值。
在程序运行过程中，有很多地方可能会产生与老对象有同样的值的新的对象（例如计算一个LR DFA状态的closure的过程中，会产生一些新的状态）。为了让这些新的对象能够在程序中表现得和原来的老对象一致，所以程序中重写了equals方法，这样就可以让有相同内容的新的对象和老的对象在程序中被认为是相等的，简化了判断。
另一方面，程序中有很多地方看起来需要修改现有对象（例如加入向前看符号，移点操作等），但是由于很多对象在一次计算过程中是共享的，若直接修改输入对象的内容，可能会造成不可预知的后果。所以，这些方法都实际被做成了产生新的状态（而不是直接修改现有的对象），由于这些对象都重写了equals方法，它们将会在接下来的算法中，和目前有的对象被认为是同一个对象，不会影响程序的实现。
我当时考虑过建立LALR(1)分析表，但是这样会引入很多的类，以及类似Map<State, Map<State, Action>>这样比较拗口的类型用来表示一个二维表。后来为了简化编程，所以直接采用LALR(1) DFA状态机的形式进行分析。
词法分析和语法分析是编译器最早的两个步骤，通过自己实现通用词法分析器和同于语法分析器，我更加深入地理解了正则表达式到NFA到DFA过程和从CFG到LR(0) DFA到LALR(1) DFA的全过程，也更加深入的理解了从输入文件到Token序列到产生式规约序列的全过程，对我理解词法分析和语法分析过程起到了至关重要的作用。
该实验项目实现了一个通用的正则词法分析器和LALR(1)语法分析器。词法分析器通过扩展正则语法（支持字符类、方括号等）构建DFA，采用最长匹配算法生成Token序列。语法分析器基于LALR(1)自动机，通过闭包计算和向前看符号传播算法生成规约序列。系统定义了.myl词法文件格式（正则规则）和.myy语法文件格式（产生式规则），支持增量分析模式。项目包含龙书例题和C语言子集的完整测试用例，实现了从字符流到语法树的完整解析流程，验证了Thompson算法、子集构造、LR状态机构建等核心编译原理技术。
由Azure AI部署的DeepSeek-R1模型推理
这是一个编译原理课的大作业，我自己实现了一个正则语法分析器（从输入字符流到Token序列）和LALR(1)语法分析器（Token序列到规约产生式序列）。以下是说明文档。
项目是放在一个repo的子文件夹里的，目录是：https://github.com/ddadaal/Homework/tree/master/Compiler/CompilerLab
实现一个能解析正则表达式和一些扩展语法的通用词法分析器，和使用LALR(1)进行语法分析的语法分析器，并定义一个能够以上提到的分析器所解析的词法定义文件（.myl）和语法定义文件（.myy）的格式，并能够做到通过在系统指定的可用Token集合上，从用户给定的词法定义文件和语法定义文件，实现从输入文件到产生式规约序列的全过程。
本实验提供了以下内容：
一个Intellij IDEA格式的Java项目，包含了目标中提到的词法分析器、语法分析器以及对应分析器的一些测例。
能被分析器所解析的词法定义文件（.myl）和语法定义文件（.myy）的格式描述
以龙书上例题4.31为依据的输入文件、输出文件、myl词法定义文件和myy语法定义文件，并提供了对应的测例
一个C语言子集的输入文件、输出文件、myl词法定义文件和myy语法定义文件。同时还提供了与其中myl和myy等价的flex/bison定义文件以及对应的一些工具程序。提供的词法定义和语法定义已经经过flex和bison测试可以完整无错误的解析提供的输入文件。
一个myl包含数个以下格式的词法定义，每个定义之间可接受任意个数的空行。
第一行：正则表达式的字符串
第二行：对应的TokenType的字符串
其中，正则表达式支持以下元素：
扩展支持：
方括号内部出现的元素之间会通过并集|连接，可与字符类配套使用。
例如：[ac\n]等价于(a|c|\n)
在ASCII表中，-前面的符号和后面的符号之间的所有符号会通过并集|连接。
例如：[a-d]等价于(a|b|c|d)
例如：[\n\ba-d_]等价于(\n|\b|(a|b|c|d)|_)
示例：
\+
PLUS （定义一个正则表达式为\+，对应到PLUS类型的Token的匹配规则，）
\*
STAR（定义一个正则表达式为\*，对应到STAR类型的token的匹配规则）
\(
LEFT_PARENTHESIS
\)
RIGHT_PARENTHESIS
[a-zA-Z]([0-9a-zA-Z_])*
IDENTIFIER （定义一个正则表达式为[a-zA-Z]([0-9a-zA-Z_])*（即以字母开头，后面跟任意个数的数字、字母或下划线），对应到IDENTIFIER类型的token转换规则）
[\ \n\r]
IGNORED （定义空格、空行或\r字符都被匹配到IGNORED类型的token的转换规则）
一个myy文件以一个字符串（代表此产生式列表的开始符，这个开始符可多次出现在产生式的左边）占一行开始，接下来由数个以下格式的语法定义组成，每个语法定义代表一系列具有相同左侧符号的产生式的集合，每个定义之间可接受任意个数的空行。
第一行：一个字符串，代表本产生式集合左边的符号
第二行开始：每一行代表一个产生式的右侧的符号列表。每个符号之间用任意个数的空格隔开。若一行为空，则代表这是一个epsilon产生式。若一个符号包含在TokenType列表里，则这个符号会被认为是一个终结符
本集合最后一个产生式后一行：符号"%"
示例：
E （代表这个产生式列表的开始符为E）
E （定义这个产生式集合的左侧符号为E）
E PLUS T （定义一个E -> E PLUS T的产生式，PLUS是一个类型为PLUS的终结符）
T （定义一个E -> T的产生式）
% （以E为左侧的产生式集合定义完毕）
T （定义这个产生式集合的左侧符号为T）
T STAR F （定义一个F -> T STAR F的产生式，STAR是一个类型为STAR的终结符）
F （定义一个T -> F的产生式）
% （以T为左侧的产生式集合定义完毕）
F （定义这个产生式集合的左侧符号为F）
LEFT_PARENTHESIS E RIGHT_PARENTHESIS （定义一个F -> LEFT_PARENTHESIS E RIGHT_PARENTHESIS的产生式，LEFT_PARENTHESIS和RIGHT_PARENTHESIS是终结符）
IDENTIFIER （定义一个F -> IDENTIFIER的产生式）
（定义一个F -> epsilon的epsilon产生式）
% （以F为左侧的产生式集合定义完毕）
词法定义 --> 词法DFA
语法定义 --> 语法LALR(1) DFA
输入文件 --词法DFA--> Token序列 --语法LALR(1) DFA--> 规约产生式列表
其中，词法分析器每读取一个到一个Token即暂停对输入字符的读取，转发给语法分析器进行语法分析；当语法分析器需要更多Token的时候，词法分析才继续对输入字符的读取，并不是首先生成所有的Token，再一次性交给语法LRDFA进行语法分析。
项目中假设只会用到以下类型的Token。若需要更多类型的Token，可在lex.internal.token.TokenType枚举类型下增加更多的Token类型。
注意，在产生式中出现Token类型列表所包含的字符串，将被认为是对应类型的终结符。字面量仅用于调试和错误报告中。
| Token类型 | 字面量 | 备注 |
|---|---|---|
| VOID | void | |
| INT | int | |
| RETURN | return | |
| WHILE | while | |
| IF | if | |
| ELSE | else | |
| ELLIPSIS | ... | |
| EQUAL | == | |
| ASSIGN | = | |
| SEMICOLON | ; | |
| STAR | * | |
| OR_OR | ||
| LEFT_BRACE | { | |
| RIGHT_BRACE | } | |
| LEFT_PARENTHESIS | ) | |
| RIGHT_PARENTHESIS | ) | |
| COMMA | , | |
| PLUS | + | |
| MINUS | - | |
| DIV | / | |
| INC | ++ | |
| LT | < | |
| LE | <= | |
| IDENTIFIER | id | |
| INT_CONST | int_const | |
| STR_CONST | str_const | |
| IGNORED | IGNORED类型的token将不会传送给语法分析器 | |
| DOLLAR_R | $R | 当词法分析器结束了所有的读取时，语法分析器无法获得下一个Token，则语法分析器会认为下一个Token是$R |
| UNKNOWN | # | 若词法分析器分析到UNKNOWN类型的Token，将会抛出LexicalParseException |
| EOF | $eof | 词法分析器结束了所有的读取时，将会返回$eof类型的Token |
词法分析器设计到的数据结构有DFA, DFANode, NFA, NFANode, Regex, RegexNode和Rule。
Regex顾名思义代表一个正则表达式，一个Regex是由一个RegexNode的列表所组成的。
一个RegexNode代表一个正则表达式的符号，其中正则表达式的符号即为正则表达式标准定义中的集几种组成元素，包括以下几种类型：
每个RegexNode都存储了这个RegexNode的类型和它的字面量值，以及其对应的优先级。优先级仅用于连接和并集的优先级选择上，其中连接的连接的优先级高于闭包。这个优先级将会在正则表达式中缀转后缀的过程中起作用。
RegexNode通过lombok生成了equals和hashCode方法，以方便比较两个RegexNode的相等性。两个RegexNode相等当且仅当两个Regex具有相同的类型且具有相同的字面量值。
NFA顾名思义代表一个对于一个正则表达式的NFA。本系统里的NFA是根据Thompson算法做出来的，而通过Thompson算法做出的对于一个正则表达式的NFA只有一个结束状态，故本系统中一个NFA是由代表开始状态的NFANode和一个代表结束状态的NFANode组成的。
NFANode代表一个NFA中的节点，或者说一个NFA的状态。一个NFANode是由一个以自己为出发边的边的集合和对应的正则表达式所对应的token类型所组成的。
前者（以自己为出发边的边的集合）在Java中的表示形式为Map<Character, List<NFANode>>，其key代表边上的字符，value代表通过key字符能够达到的状态的集合。
后者（对应的正则表达式所对应的token类型）对应在词法定义文件中，满足此正则表达式的字符串应该被语法分析及其后续过程认为的Token的类型。
NFA的边集没有单独保存，而是通过每个NFANode的以自己为出发边的边的集合表示。
DFA顾名思义代表一个对于一份词法定义文件的DFA，由一个标志开始状态的DFANode和这个DFA所有的接受状态的列表组成。本系统里DFA是以下算法得到的：
DFANode代表一个DFA中的节点，或者说一个DFA的状态。一个DFANode是由它所对应的NFA状态的集合、以自己为出发边的边的集合和自己所对应的所有可能的token类型的集合所组成的。
第一项（所对应的NFA状态的集合）即在子集构造算法中，构成这个DFA状态的NFANode的集合。
第二项（以自己的为出发边的边的集合）在Java中的表示形式为Map<Character, List<NFANode>>，其key代表边上的字符，value代表通过key字符能够达到的状态的集合。
第三项（自己所对应的所有可能的token类型的集合）即这个DFA状态对应的NFANode所对应的正则表达式所对应的token类型的并集。“这个DFA所对应的NFA状态的集合中包括至少一个结束状态的NFANode”是“DFANode所对应的所有可能的token类型的集合非空”的充要条件。通过保存这个集合能够减少词法分析的时间。
DFA的边集没有单独保存，而是通过每个DFANode的以自己为出发边的边的集合表示。
DFANode重写了equals方法。两个DFANode相等当且仅当两个DFANode具有相同的自己所对应的所有可能的token类型的集合。虽然NFANode并没有重写equals方法，但是在算法过程中保证了没有新的NFANode产生，保证了两个NFANode相等当且仅当它们是同一个对象。
一个Rule代表词法定义文件中定义的转换规则，由一个正则表达式的字符串和对应的Token类型组成。它仅被用于表示用户的词法定义。
语法分析器用到的数据结构有Symbol, Production, ProductionList, LRItem, LRDFA, LRDFANode。
Symbol（符号）是语法分析过程的基本单位，有两个属性组成：代表非终结符名称的ntName和代表终结符Token类型的tokenType。一个符号要么是一个非终结符（nt != null && tokenType == null），要么是一个终结符（nt == null && tokenType != null）。通过调用Symbol.terminal(TokenType)或者Symbol.nonterminal(String)可以分别产生一个终结符或者非终结符实例。
Symbol实现了equals和hashCode方法，两个Symbol相等当且仅当（两个Symbol都是非终结符 && 两个Symbol的非终结符名称相同） || (两个Symbol都是终结符 && 两个Symbol的终结符Token类型相同)。实现hashCode方法允许了将其作为HashMap的Key值，简化了后续的编程。这两个方法都是由lombok实现的。
Production代表一个产生式，由**产生式左边的符号(left)和产生式右边的符号列表(right)**组成。当产生式右边的符号列表为空的时候，代表这是一个epsilon产生式。
Production实现了equals和hashCode方法。两个Production相等当且仅当两个产生式具有相同的产生式左边的符号和产生式右边的符号列表（包括顺序）。实现hashCode方法允许了将其作为HashMap的Key值，简化了后续的编程。这两个方法都是由lombok实现的。
一个ProductionList代表一个产生式列表，一个ProductionList只允许有一个左边是开始符的产生式。所以，一个产生式列表由产生式的列表，初始产生式(startProduction），即左边是开始符的唯一的产生式和**开始符（startSymbol）**组成。
为了简化编程，一个ProductionList还提供了计算函数First(Symbol)以计算一个符号的First函数值，和canDeriveToEpsilon(Symbol)以判断一个符号是否能推出epsilon表达式。为了减少计算时间，这两个函数将会在计算出一个Symbol的结果后，将其结果记录到一个Map中（firstMemo和canDeriveToEpsilonMemo），下次再进行相同的符号的时候，函数将直接从对应的map中直接取值。
一个LRItem代表一个LR项，由对应产生式(production)、**点的位置(dotPosition)和向前看符号(lookaheadSymbol)**组成。根据向前看符号是否为null，一个LRItem可能是一个LR(0)项（lookaheadSymbol == null），也可能是一个LALR(1)项（lookaheadSymbol != null）。
LRItem实现了equals和hashCode方法。两个LRItem相等当且仅当两个LRItem具有相同的对应产生式，点的位置和向前看符号。实现hashCode方法允许了将其作为HashMap的Key值，简化了后续的编程。这两个方法都是由lombok实现的。
LRDFANode代表一个LR自动机中的一个状态，由代表这个状态的内核(kernel)的LR项（LRItem）的集合、组成整个状态的LR项的集合和以自己为出发边的边的集合组成。其中，以自己为出发边的边的集合在Java中的表示形式为Map<Character, List<LRDFANode>>，其key代表边上的字符，value代表通过key字符能够达到的状态的集合。根据组成其的LR项的类型（LR(0)项或者LALR(1)项），这个LRDFANode可能是LR(0)自动机或者LALR(1)自动机的一个状态。
LRDFANode重写了equals和hashCode方法。两个LRDFANode相等当且仅当它们具有相同的内核。实现hashCode方法允许了将其作为HashMap的Key值，简化了后续的编程。
一个LRDFA代表一个LR确定自动机，由开始状态(startState)、**结束状态列表(endStates)和所有状态列表(allNodes)**组成。根据其中包含的状态的类型（LR(0)或者LALR(1)），这个自动机可能是LR(0)自动机或者LALR(1)自动机。
对应的方法：lex.MylexReader.read
首先去掉忽略所有空格行，读到非空格行第一行认为是正则表达式，第二行认为是Token，调用TokenType.valueOf将字符串转换为TokenType。循环这个过程直到输入结束。
对应的方法：lex.internal.NFA.constructNFA
此过程分为4个子过程：正则表达式字符串预处理，加入点符号，中缀正则表达式转后缀和后缀正则表达式转NFA。
对应的方法：lex.internal.Regex.preprocess
预处理过程会将中括号和字符类的符号转换为只包含字符、*、|和()的标准正则表达式，并将字符串转换为RegexNode的列表。具体转换规则如下：
对应的方法：lex.internal.Regex.addConcatenation
遍历预处理后的RegexNode列表，在满足以下条件的两个符号之间加入点符号，表示这是两个正则表达式相连接的而构成的。
对应的方法：lex.internal.Regex.toPostfix
将加入点符号的RegexNode列表转换为后缀表达式，其中
对应的方法：lex.internal.NFA.constructNFA
使用Thompson算法，将一个后缀正则表达式转换为一个NFA。其中，每个后缀正则表达式的结束状态的对应的正则表达式所对应的token类型被设置为对应转换规则所规定的Token类型，非结束状态的状态的对应的正则表达式所对应的token类型为null。
对应的方法：lex.LexicalAnalyzer.constructDFA，43-53
得到所有转换规则的正则表达式的NFA后，新增一个开始状态，将这个开始状态用epsilon边连接到所有NFA的开始状态，得到一个lNFA。
对应的方法：lex.internal.DFA.constructDFA
使用子集构造算法（龙书图3-29，算法3.20），将lNFA转换为对应的DFA。其中每个DFA状态（DFANode）自己所对应的所有可能的token类型的集合包含组成这个DFANode的NFANode的对应的正则表达式所对应的token类型的并集。构建出来的DFA被称作词法DFA，是后续进行词法分析的核心组件。
子集构造算法中使用的epsilon闭包的计算算法为龙书图3-30。
对应的方法：syntax.MyYaccReader.read
首先忽略带开头的所有空行，读到第一个字符串被认为是整个产生式列表的开始符。继续往后读，重复一下步骤直到没有进一步的输入：
最后，调用ProductionList.fromUnaugmentedList方法，给整个产生式列表加入一个新的开始符S'和新的初始产生式S' -> {原开始符}。
对应的方法：syntax.constructLR0DFA
对应的方法：syntax.internal.LRDFA.closure
采用书上图4-32所采用的CLOSURE的计算方法。为了提高效率，会使用一个栈来保存还没有进行状态内扩展的项。在函数刚进入的时候，内核的所有项将会入栈；在每次执行算法的时候，会弹出栈顶，在这个过程中新产生的LR项将会入栈；当栈为空的时候，说明没有可以继续进行状态内扩展的LR项，表明闭包构建完成。
注意，在闭包构建过程中会产生新的LRItem对象。由于LRItem对象重写了equals方法，所以这些新产生的LRItem对象和之前可能已经存在LRItem对象无异。
注意，若输入的LR项存在向前看符号（即为LALR(1)项），设为(A -> a.Bc, d)_，则将会计算First(cd)，并将这些向前看符号加入到LRItem对象中。
对应的方法：syntax.constructLR0DFA
对应算法：syntax.addLookaheadSymbol
在这个算法中需要用到First函数，以及判断一个符号是否能够推出epsilon。由于它们仅依赖产生式列表，为了方便代码的维护以及设计缓存增加计算效率，所以这两个方法都写在ProductionList作为它们的实例方法。
判断一个符号是否能推出epsilon：syntax.internal.ProductionList.canDeriveToEpsilon
First算法：syntax.internal.ProductionList.first
使用书上算法4.47（自生成-传播算法），将LR(0)自动机中的所有状态中的所有LR项加上向前看符号（lookahead symbol），构建LALR(1)自动机。
对应算法：syntax.addLookaheadSymbol
首先定义一个新的数据结构StateSpecificLRItem，保存一个LRDFANode项和LRItem项，用于记录一个LRItem项及其它所属的LRDFANode。
<StateSpecificLRItem, List<StateSpecificLRItem>>，用于记录向前看符号的传播路径。在这个Map中，Key所拥有的向前看符号都会最终传播给它的Value中的所有LR项。Map<StateSpecificLRItem, List<Symbol>>，用于记录每对一个LR项，它通过自生成或者传播所得到的所有向前看符号的集合。对应方法：lex.LexicalAnalyzer.next
这个过程实现了最长匹配。在这个过程中，一旦返回Token，词法分析暂停，等待语法分析程序需要更多的Token时再继续分析。
在分析之前，已经通过输入的词法定义文件获得了对应的DFA。
对应方法：syntax.SyntaxAnalyzer.getProductionSequence
这个过程通过输入Token序列流，能够返回所有使用到的规约产生式序列。
这个过程没有像书上一样采用LALR(1)分析表实现，而是直接通过使用LALR(1) DFA来进行分析，其核心理念是相同的（移入-规约），核心算法几乎一致（书上算法4.30），而且LALR(1)分析表也是通过LALR(1) DFA获得的。直接使用LALR(1)方便编程。
CompilerLab要运行这个测试，请运行test/java/IntegrationTest::testExample431。这个测例将读取main/java/resources/example4.31下预先提供的输入文件、词法定义文件和语法分析文件，将输入文件进行词法和语法分析，得到规约序列，并与测试中写好的预期序列进行比较，得出测试结果。示例（以及确保正确的）的输出结果位于main/java/resources/example4.31/output中。
这个C语言子集提供了flex/bison项目以及基于等价myl, myy定义文件的运行方式。
flex/bison项目中包含了这个C语言子集对应的.l和.y定义文件。要运行flex/bison项目，请参考CSubsetFlexBison目录下的说明文档。
与flex/bison项目中提到的C语言子集等价的词法定义文件和语法定义文件，以及和flex/bison项目中示例文件test.c完全相同的示例输入文件均位于main/java/resources/bigtest下。测试用例test/java/IntegrationTest::bigTest将读取输入文件、词法定义文件和语法分析文件，将输入文件进行词法和语法分析，输出规约序列。注意此“测试”由于比较复杂（规约序列中包含200余条产生式），故只提供了程序的输出信息(main/java/resources/bigtest/output文件)，并没有进行正确性验证。
在开发过程中，单元测试起到了测试一个功能点正确性的作用。本项目中test/java/LexTest和test/java/SyntaxTest包含了编写词法和语法分析器过程中所用到的单元测试，若有兴趣，可自行运行。
仅举几个例子。
使用公式递归计算First函数的时候，容易遇到类似First(A) = First(A) U First(B)...的无限递归的情况。根据集合方程的特性，在这种情况下可以直接忽略右侧的First(A)，这样即可避免无穷递归的问题，成功算出函数值。
在程序运行过程中，有很多地方可能会产生与老对象有同样的值的新的对象（例如计算一个LR DFA状态的closure的过程中，会产生一些新的状态）。为了让这些新的对象能够在程序中表现得和原来的老对象一致，所以程序中重写了equals方法，这样就可以让有相同内容的新的对象和老的对象在程序中被认为是相等的，简化了判断。
另一方面，程序中有很多地方看起来需要修改现有对象（例如加入向前看符号，移点操作等），但是由于很多对象在一次计算过程中是共享的，若直接修改输入对象的内容，可能会造成不可预知的后果。所以，这些方法都实际被做成了产生新的状态（而不是直接修改现有的对象），由于这些对象都重写了equals方法，它们将会在接下来的算法中，和目前有的对象被认为是同一个对象，不会影响程序的实现。
我当时考虑过建立LALR(1)分析表，但是这样会引入很多的类，以及类似Map<State, Map<State, Action>>这样比较拗口的类型用来表示一个二维表。后来为了简化编程，所以直接采用LALR(1) DFA状态机的形式进行分析。
词法分析和语法分析是编译器最早的两个步骤，通过自己实现通用词法分析器和同于语法分析器，我更加深入地理解了正则表达式到NFA到DFA过程和从CFG到LR(0) DFA到LALR(1) DFA的全过程，也更加深入的理解了从输入文件到Token序列到产生式规约序列的全过程，对我理解词法分析和语法分析过程起到了至关重要的作用。