在之前的课程中，使用上下文无关文法（CFG）定义了非终结符，这些非终结符引用了终结符，但尚未定义终结符的结构。在本课中，将构建一个简单的正则表达式引擎，用于从输入字符串中匹配终结符。将不使用Microsoft的.NET正则表达式，因为那样会使结果更加复杂。然后，将创建一个小类，允许遍历输入字符串中的终结符。
首先，什么是终结符？简单来说，终结符是解析器识别的文本元素。它是基本元素，无法进一步解析。在语法中，终结符是+、*、(、)和int。终结符与非终结符组合在一起，形成解析树。终结符是叶子，而非终结符是节点。
将使用正则表达式定义终结符，但不会创建完整的正则表达式引擎。相反，将在代码中手动构建正则表达式。对于之前的语法，这相当直接。
E -> T E'
E' -> + T E'
E' ->
T -> F T'
T' -> * F T'
T' ->
F -> ( E )
F -> int
唯一不是简单字面量的终结符是int。在本练习中，将int视为一系列数字，类似于正则表达式[0-9]+。为了便于匹配表达式，将使用有向图来表示跳转表，将在遍历它们时使用这些有向图进行标记化。这比说起来容易，但会做到的。这背后的数学被称为有限自动机。
正在构建一个词法分析器作为正则表达式匹配器。它由几个正则表达式组成，每个终结符一个。每个表达式都有一个与之关联的终结符符号。
终结符是+、*、(、)和int。有向图需要看起来像这样：
这是一个状态机。气泡是状态，线条是转换。虚线转换不消耗任何输入。黑色线条在它们上面标记的输入上转换。双圆圈是接受状态，与之关联的终结符符号显示在气泡中。
在生产代码中，会在实际使用之前将这个"NFA"转换为"DFA"，因为结果是更快的，但为了保持简单，只是运行"NFA"。这个算法一旦知道如何优化，就很容易优化，并且当这样做时，它会生成最快的可能的词法分析代码，这是在这里选择它的原因之一，尽管在这个化身中它是慢的。它可以被构建和优化。
要使用它，反复将其运行在输入流的下一个位置。每次接受或每次不能接受并得到错误，报告它，然后重置机器回到q0。基本上，正在运行一个匹配，这会导致光标前进，再次运行匹配，这又会导致光标前进，等等，这就是如何通过文本移动。每次得到一个匹配或错误，都有一个与之关联的终结符符号，告诉匹配是什么，一个int，或者像(、+、*这样的其他终结符，或者在错误的情况下，#ERROR。
这些是最终将传递给解析器的，解析器将使用解析表构建这些"令牌"的树，因为它通过文本移动。还在吗？花一分钟。=)
这里的代码由几个部分组成：
首先，有FA。每个FA实例代表状态机中的一个状态，或图中的一个气泡。它们通过属性Transitions（实线）和EpsilonTransitions（虚线）相互连接。它还有一个静态构建器方法来创建基本表达式-Literal、Set、Concat、Or、Repeat和Optional，这些方法负责创建图中的线条。这些通常被组合起来创建类似正则表达式的东西。
以下是如何为这个项目创建词法分析器：
var lexer = new FA();
lexer.EpsilonTransitions.Add(FA.Literal("+", "+"));
lexer.EpsilonTransitions.Add(FA.Literal("*", "*"));
lexer.EpsilonTransitions.Add(FA.Literal("(", "("));
lexer.EpsilonTransitions.Add(FA.Literal(")", ")");
lexer.EpsilonTransitions.Add(FA.Repeat(FA.Set("0123456789"), "int"));
如果研究这个并查看上面的图表，应该看到它组合在一起。
这里的另一个非常重要的方法是FillMove，它接受当前所在的一组状态，并应用一个输入字符给它们，给在转换后最终状态，按照所有线条。标记器将使用这个来获取词素/标记。
接下来，需要实际处理刚刚创建的图表（lexer）。这就是标记器的用武之地。一个标记器将接受一个输入字符串和一个FA图，并从输入字符串中检索一系列标记/词素。这个项目的Tokenizer类使用.NET枚举器模式实现，所以可以使用foreach遍历它来获取标记。大部分繁重的工作由TokenEnumerator类完成，它实现了IEnumerator
在这个类中，大部分繁重的工作由_Lex方法完成。这是正则表达式处理器的核心和灵魂：
string _Lex()
{
string acc;
var states = _initialStates;
_buffer.Clear();
switch (_state)
{
case -1:
if (!_MoveNextInput())
{
_state = -2;
acc = _GetAcceptingSymbol(states);
if (null != acc)
return acc;
else
return "#ERROR";
}
_state = 0;
break;
case -2:
return "#EOS";
}
while (true)
{
var next = FA.FillMove(states, _input.Current);
if (0 == next.Count)
break;
_buffer.Append(_input.Current);
states = next;
if (!_MoveNextInput())
{
_state = -2;
acc = _GetAcceptingSymbol(states);
if (null != acc)
return acc;
else
return "#ERROR";
}
}
acc = _GetAcceptingSymbol(states);
if (null != acc)
return acc;
else
{
_buffer.Append(_input.Current);
if (!_MoveNextInput())
_state = -2;
return "#ERROR";
}
}
本质上，它只是在循环中调用FillMove，直到没有更多的状态返回，同时存储它找到的字符，对于输入结束和错误条件有一些特殊情况处理。其余的只是一些簿记工作。