【手写编译器】手写带图像界面GUI的简单编译器 C# C++混合编码项目介绍（DFA词法分析器+LR1语法分析

最终实现效果看这里

设计目标：

任务 1：创建一个词法分析程序，该程序支持分析常规单词。
任务 2：创建一个使用 LL(1) 方法或 LR(1) 方法的语法分析程序。

最终实现：

实验环境：Win10
IDE: VScode 、Visual Studio2019
编程语言：C++、C# 混合编程 (DLL)

一、简述

1.1 任务一：词法分析器

创建一个词法分析程序，它支持对正规文法的分析。必须使用DFA（确定性有限自动机）或NFA（非确定性有限自动机）来实现这一项目。该程序的输入是一个文本文件，包括一组由该正规文法产生的产生式以及待识别源代码字符串。该程序的输出是一个符号表（二元式），它由5种类型符号：关键词，识别符，常量，界符和操作符。

1.2 任务二：语法分析器

创建一个语法分析程序，它采用LL（1）方法或LR（1）方法。该程序的输入是一个文本文档，包括一组2型文法（上下文无关文法）的产生式和任务1程序输出的符号表。任务2的输出是一个YES或NO，即源代码字符串是否符合本2型文法。

二、原理介绍

DFA的构建：

词法分析器读取有字符串组成的输入流，并产生包含单词的输出流，每个单词都标记了其语法范畴（syntactic category）或类型，等效于英文单词的词类。为了完成这种聚集和分类操作，词法分析器会应用一组描述输入程序设计语言的词法结构（也称微语法，microsyntax）的规则。程序设计语言的微语法规定了如何将字符组合为单词，以及反过来如何分开混合在一起的各个单词。
通过正则表达式来快速定义字符串集合，并且可以通过算法快速检测一个字符串是否属于正则表达式所表达的字符集合。为了正则表达式匹配，引入有限状态自动机。自动机可以对一个输入序列表现出两种状态：接受和拒绝。有了自动机的存在，便可以实现正则表达式的快速匹配。接受状态只出现在匹配终止且最终状态在接受状态上的情况。拒绝状态是有某个输入使得自动机没有进行状态转移或者最终状态不在接受状态上。
有限状态自动机分为dfa和nfa，分别是确定有限状态自动机和不确定有限自动机。dfa是对于每个状态，对于一个输入，只有最多一种状态转移，且没有0输入就进行状态转移的情况，简称ε moves。nfa是对于一个输入，可以有多种状态转移，且可以存在ε moves的自动机。可以通过正则表达式简单地构造nfa，再有NFA转为DFA。
NFA的好处是构造难度很低，并且空间复杂度较低，但是时间复杂度很高。
DFA的好处是时间复杂度较低，但是空间复杂度较高，且构造比较难。

LR(1)状态机构建:

LR(1)分析从外部看起来，每次接受一个字符，最后接收程序终结符时，内部刚好形成一颗语法树。
在内部，每当我们接受一个Symbol之后，我们就需要做一个决定：是把新的Symbol跟原有的Symbol立即合并成更高级的Symbol，还是把新的Symbol暂放。
在LR(1)中，有两个术语：reduce(归约)和shift(移入)。规约就是把已经读入的低级Symbol组合成高级Symbol，如Integer “x” Integer 可以reduce成MultipleExpression。
为了正确处理以上的问题，我们要构建一个状态机来指导LR(1)运算，何时reduce，何时shift。
由BNF我们可以得到的语法规则，以四则运算为例，最终我们想要的是一个Expression，即我们的语法树最终根节点是Expression 。
我们认为输入的token序列最终会形成一个Expression，那么考虑一个问题，状态机的最初状态0，能够接受哪些Symbol的shift呢？
第一个考虑到，状态机可以接受Expression这个Symbol,这将导致我们进入最终状态。
此外因为有语法规则Expression ::= AdditiveExpression，状态0还能接受AdditiveExpression又因为有语法规则AdditiveExpression ::= MultipleExpression “+” MultipleExpression , MultipleExpression “-” MultipleExpression , MultipleExpression
状态0还能接受MultipleExpression
……
从这个分析过程不难看出，状态0可以接受所有Expression，以及所有能生成Expression的规则的第一个Symbol，并按此规则递归。
接下来需要关心迁移问题了，毫无疑问接受Expression这个Symbol以后，直接进入最终状态，然而对于其它情况，如接受了一个MultipleExpression ，则会产生更多可能性，我们把AdditiveExpression ::= MultipleExpression “+” MultipleExpression , MultipleExpression “-” MultipleExpression , MultipleExpression看成3条规则，把所有的规则全都拆分出来。
每一条规则都将会形成若干状态迁移规则：

Expression ::= AdditiveExpression
● AdditiveExpression
AdditiveExpression ●

AdditiveExpression ::= AdditiveExpression “+” MultipleExpression , AdditiveExpression “-” MultipleExpression , MultipleExpression
…略
显而易见，我们可以总结出下面两条规律：
1、所有以●结尾的状态，操作就是规约,其它状态操作就是移入。
2、假如当前状态● 后是一个非终结符X，那么所有能规约到X的规则中以●开头的状态迁移规则也适用于当前状态。
我们现在可以认为● Expression是初始状态，Expression ● 是结束状态。要想得到完整地状态机，还要对所有后续状态递归地应用规则2。这将可能产生无限循环，为了避免这种情况，我们应该对每个状态做hash,然后把循环的情况直接指向之前的结果。

做完这些之后，我们就得到了一个完整的LR(1)状态机。