Vczh Library++ 语法分析器开发指南
陈梓瀚
前言
在日常的开发工作中我们总是时不时需要写一些语法分析器。语法分析器不一定指的是一门语言的编译器前端，也有可能仅仅是一个自己设计格式的配置文件的读写程序，或者是一门用来简化我们开发的DSL（领域专用语言）。我们可以选择使用XML，不过因为XML的噪音实在是太多，所以自己写语法分析器在有些情况下是必要的，特别是那种经常需要修改的文件，使用XML有时候会增加我们的负担，除非我们专门为此开发一个编辑器程序。
这篇文章将紧密结合一个带函数的四则运算计算器的例子（Documentation\Samples\ExpressionCalculator\ExpressionCalculator.sln）来说明如何使用Vczh Library++提供的工具来大幅度简化我们的语法分析器的开发，并最终给出一个可以编译的例子。虽然这个例子实在是老掉牙了，不过开发一个四则运算计算器可以覆盖大部分开发语法分析的过程中会遇到的问题，所以也不失为一个好的例子。
这个例子可以在Vczh Library++的代码里面找到。
制定语法
我们需要对带函数的四则运算计算器下一个定义，这样我们才可以有目的地完成这个任务。我们对四则运算式子是很熟悉的，一个四则运算式子包含加减乘除、括号和数字。我们还可以支持负号：-a，其实是(0-a)的简写形式。那么什么是支持函数呢？这里我们只考虑单参数函数的情况，譬如说三角函数和对数指数等等。譬如说下面的式子就是满足定义的带函数的四则运算式子：
sin(1+2) + cos(3*-4)
Vczh Library++使用语法的角度来对待一个字符串，因此我们可以把上面的定义转换成语法。一个语法用来表示字符串的一个子集。我们可以通过语法来表达什么样的字符串是满足规定的，什么样的字符串是不满足规定的。不过一个具有现实意义的语法总是会有一些局限性的，譬如说你很难用上下文无关的文法来表达一个字符串：a…ab…bc…c，其中三种字母的数量都相等。幸好在绝大多数情况下我们都不需要去面对这些高难度的问题，因此可以用一些简单的规则来处理：
RULE = EXPRESSION
RULE是这个规则的名字，而EXPRESSION是这个规则的定义。语法可以由一条规则组成，也可以由很多条规则组成。当所有的规则都列出来之后，那么每一个规则的名字都是一个字符串的集合。大部分情况下你需要指定一个“总入口”来代表整个语法。
举个例子，假设我们判断一个字符串是不是无符号整数。一个无符号整数只能由数字字符组成。于是我们可以先用一条规则来代表“数字字符”。这里我们可以使用“|”来代表“或”，那么下面的规则就表示DIGIT是’0’或’1’或…或’9’：
DIGIT = ‘0’ | ‘1’ | ‘2’ | ‘3’ | ‘4’ | ‘5’ | ‘6’ | ‘7’ | ‘8’ | ‘9’
那么，无符号整数就是“很多数字字符”：
INTEGER = DIGIT | INTEGER DIGIT
无符号整数INTEGER要么是一个数字字符，要么就是一个合法的无符号整数后面再加上一个数字字符。无符号整数加上一个数字字符仍然是一个无符号整数。
现在可以来检验一下。譬如说“1”是一个无符号整数，那么从INTEGER开始，分析“1”所走的路径就是
INTEGER
= DIGIT (INTEGER = DIGIT)
= ‘1’ (DIGIT = ‘1’)
字符串“123”显然也应该是一个无符号整数。“123”是一些数字字符组成的，因此走的路径跟单个字符稍微有些不同。这里将会交替使用INTEGER的两条路径来模拟循环：
INTEGER
= INTEGER DIGIT (INTEGER = INTEGER DIGIT)
= INTEGER DIGIT DIGIT (INTEGER = INTEGER DIGIT)
= DIGIT DIGIT DIGIT (INTEGER = DIGIT)
= ‘1’ DIGIT DIGIT (DIGIT = ‘1’)
= ‘1’ ‘2’ DIGIT (DIGIT = ‘2’)
= ‘1’ ‘2’ ‘3’ (DIGIT = ‘3’)
在使用INTEGER分析“123”的时候，我们可以交替使用INTEGER = DIGIT和INTEGER = INTEGER DIGIT这两条规则来将一个INTEGER替换成恰好三个DIGIT，然后再将DIGIT替换成’1’、’2’和’3’三个字符，从而确信“123”满足INTEGER的定义，因此“123”是一个无符号整数。
替换的过程并不是唯一的，我们完全可以使用另一种顺序来将INTEGER替换成“123”：
INTEGER
= INTEGER DIGIT (INTEGER = INTEGER DIGIT)
= INTEGER ‘3’ (DIGIT = ‘3’)
= INTEGER DIGIT ‘3’ (INTEGER = INTEGER DIGIT)
= INTEGER ‘2’ ‘3’ (DIGIT = ‘2’)
= DIGIT ‘2’ ‘3’ (INTEGER = DIGIT)
= ‘1’ ‘2’ ‘3’ (DIGIT = ‘1’)
这正是语法的一个特点：替换顺序与结果无关。
现在我们将这个例子再深入一点，如何用语法规则来描述一个逗号分隔的无符号整数列表呢？逗号分隔的无符号整数列表可以是一个整数“123”，也可以使多个整数“1,23,456”。这也是重复的一种，只是跟INTEGER的那种重复有所区别——多了一个逗号。根据上面的描述可以知道，逗号分隔的无符号整数列表有两种情况，第一种是单独的一个整数，第二种是一个已经完成的列表后面跟着一个逗号和一个整数。那么事情就变得简单了。假设我们使用LIST来代表这个列表，那么根据上面的描述我们可以用类似的技巧来描述它：
LIST = INTEGER | LIST ‘,’ INTEGER
用LIST来分析一个数字列表的过程与用INTEGER分析一个无符号整数是相似的。因为篇幅问题，这里只展示使用LIST处理“1,23,456”的其中一种方法：
LIST
= LIST ‘,’ INTEGER (LIST = LIST ‘,’ INTEGER)
= LIST ‘,’ INTEGER ‘,’ INTEGER (LIST = LIST ‘,’ INTEGER)
= INTEGER ‘,’ INTEGER ‘,’ INTEGER (LIST = INTEGER)
= DIGIT ‘,’ INTEGER ‘,’ INTEGER (INTEGER = DIGIT)
= ‘1’ ‘,’ INTEGER ‘,’ INTEGER (DIGIT = ‘1’)
= ‘1’ ‘,’ INTEGER DIGIT ‘,’ INTEGER (INTEGER = INTEGER DIGIT)
= ‘1’ ‘,’ DIGIT DIGIT ‘,’ INTEGER (INTEGER = DIGIT)
= ‘1’ ‘,’ ‘2’ DIGIT ‘,’ INTEGER (DIGIT = ‘2’)
= ‘1’ ‘,’ ‘2’ ‘3’ ‘,’ INTEGER (DIGIT = ‘3’)
= ‘1’ ‘,’ ‘2’ ‘3’ ‘,’ INTEGER DIGIT (INTEGER = INTEGER DIGIT)
= ‘1’ ‘,’ ‘2’ ‘3’ ‘,’ INTEGER DIGIT DIGIT (INTEGER = INTEGER DIGIT)
= ‘1’ ‘,’ ‘2’ ‘3’ ‘,’ DIGIT DIGIT DIGIT (INTEGER = DIGIT)
= ‘1’ ‘,’ ‘2’ ‘3’ ‘,’ ‘4’ DIGIT DIGIT (DIGIT = ‘4’)
= ‘1’ ‘,’ ‘2’ ‘3’ ‘,’ ‘4’ ‘5’ DIGIT (DIGIT = ‘5’)
= ‘1’ ‘,’ ‘2’ ‘3’ ‘,’ ‘4’ ‘5’ ‘6’ (DIGIT = ‘6’)
在开发实际的语法分析器的时候，我们总是需要考虑空格的问题。人们用空格让一个具有严格限制的字符串变得更加易读，譬如说将“1,23,456”变成“1, 23, 456”会让密密麻麻的一堆字符变得非常容易看懂。空格也不是乱加的，有些地方可以加空格，有些地方不能加空格。
在上面这个例子里面，如果要支持空格，那么空格除了不能插在INTEGER中间，应该可以放在任何的地方。这个时候就带来麻烦了，带空格的语法不是太好写。如果我们让LIST支持空格，那会把LIST变成下面这个样子：
SPACES = <EMPTY> | SPACES ‘ ’
LIST = SPACES INTEGER SPACES | LIST ‘,’ SPACES INTEGER SPACES
这里<EMPTY>代表空字符串，所以SPACES就是没有空格、一个空格或者很多空格了。因此我们必须在LIST里面所有可以加入空格的地方写空格，这会让我们的语法膨胀得很厉害。因此我们必须使用一种方法来让我们免除空格带来的困扰。
词法分析
引入词法分析的目的是让我们的语法更加简洁。我们可以将处理空格、注释和分割字符串的工作与语法分析完全分开，那么代码写起来就会更加容易，维护起来也会更加简单了。我们总是倾向于让我们的程序越来越容易理解和维护。
词法分析的目标是将输入的字符串适当分割并抛弃处理掉没有用的部分。“适当分割”一般来说没有一个明确的规则，应该根据具体情况而定，越方便越好。在大部分情况下我们仅把输入的字符串简单的划分为符号、数字、操作符、字符串、空格和注释等等的简单部分。这些划分一般代表“插入空格会改变意义”。比如说“1234”变成“12 34”之后，就从一个整数变成两个整数了。字符串的情况有点特别，虽然字符串中间插入一个空格还是一个字符串，但是插入空格后的字符串已经不是插入空格前的字符串了，因为内容已经发生了变化。与此同时，在一个整数列表里面，往逗号后面插入一个空格不会影响这个列表所要表达的意义，因此将字符串转换成“整数列表”的工作一般划分在语法分析而不是词法分析里。
处理词法分析的方法一般是使用正则表达式。Vczh Library++提供了一个使用正则表达式来开发词法分析器的类库。关于正则表达式的语法请参考Documentation\Chinese\Vczh Library++\Regex\Regex.htm#Grammar，关于这个词法分析器类的内容请参考Documentation\Chinese\Vczh Library++\Regex\Regex.htm#RegexToken。
在使用Vczh Library++进行词法分析的开发之前需要掌握正则表达式的简单用法。这里我们假设读者对正则表达式已经入门了。精通是没有必要的，因为词法分析使用到的正则表达式的内容十分简单。我们回到之前的“带函数的四则运算计算器”。经过简单的整理，我们知道一个带函数的四则运算计算器由数字、函数名、操作符和符号组成。
加号与减号的优先级一样，对于语法分析来说他们其实没有区别。乘号与除号也类似。当语法分析结束，语义分析开始的时候，加号与减号的区别才会出现。因此在词法分析里面我们可以把他们当成同样的东西来对待，因此有：
BLANK = \s+ ：空格
ADD = \+|- ：加减号
MUL = \*|/ ：乘除号
NUMBER = \d+(.\d+)? ：数字
ID = [a-zA-Z_]\w* ：函数名
OPEN = \( ：开括号
CLOSE = \) ：闭括号
我们把分类后的结果叫记号类型。一个字符串可以被分成很多记号，每一个记号属于一个记号类型。如果一个记号不属于任何记号类型的话（譬如问号“?”），那么遇到了词法分析的错误。这个时候我们需要报告错误了。
Vczh Library++有一个简单的方法让我们是用正则表达式表达记号类型，并使用他们来构造词法分析器：
List<WString> patterns;
const int BLANK = patterns.Add(L"/s+");
const int ADD = patterns.Add(L"/+|-");
const int MUL = patterns.Add(L"/*|//");
const int NUMBER = patterns.Add(L"/d+(./d+)?");
const int ID = patterns.Add(L"[a-zA-Z_]/w*");
const int OPEN = patterns.Add(L"/(");
const int CLOSE = patterns.Add(L"/)");
RegexLexer lexer(patterns.Wrap());
为了方便书写正则表达式，Vczh Library++同时支持两种转义符：“\”和“/”。因为C++使用了“\”作为字符串的转义符，所以在这里我们可以使用“/”，这样写起来会比较清晰。
构造词法分析器的方法很简单，我们将所有正则表达式放到一个字符串列表List<WString>，然后交给词法分析器RegexLexer，我们就得到了一个词法分析器了。在分析字符串的时候，每一个记号的类型其实就是该记号的正则表达式描述在字符串列表中的位置。如果发生错误的话，记号类型会变成-1。因为列表的Add函数返回添加的元素在列表中的位置，因此就可以使用上面的写法来简单地构造一个词法分析器了。
我们可以用一种简单的方法来使用这个词法分析器。RegexLexer输出的记号存放在RegexToken类型里面，我们可以使用任何容器来存放记号，在这里我们仍然使用RegexToken。
RegexToken的定义如下：
class RegexToken
{
public:
int start;
int length;
int token;
const wchar_t* reading;
int lineIndex;
int lineStart;
int codeIndex;
};
RegexToken记录了一个记号在输入的字符串中的位置、所在的行和在该行内的位置、记号类型和指向该位置的指针。这些信息可以用来做很多事情，譬如在产生错误信息的时候可以精确指定错误发生的位置。
在这里我们需要过滤空格，也就是过滤掉BLANK记号，因此我们需要写一个过滤函数：
bool IsNotBlank(RegexToken token)
{
return token.token!=0;
}
我们知道BLANK就是0，因此这里直接以0代替。有了这个函数之后，我们就可以将输入切割成记好了：
List<RegexToken> tokens;
CopyFrom(tokens.Wrap(), lexer.Parse(L"(1 + 2) * abs(-3 - 4)")>>Where(IsNotBlank));
执行了这段代码之后，我们就将字符串切割成记号了。这里只用了15行就完成了词法分析器的定义并使用词法分析器来分析一个字符串的任务了。