原文链接 Geir Vattekar – QLALR Adventures – Using QLALR to generate a parser for a text adventure

QLALR是Qt所提供的应用程序之一，它是Qt解析程序生成器。过去它已经被用于Qt Script中，现在它还对QML的JavaScript和Qt中的XML流读取负责。很遗憾地是，因为它缺少文档，大多数Qt用户都不知道它。这篇文章就试图对这一问题进行补救。

QLALR可以根据一个按特有语法写成的文件生成与之匹配的C++代码。这个被接受的语法就是LALR，例如，一个前置口令。和yacc这样的解析程序生成器一样，QLALR对于处理联系和区别都很有帮助（例如变换/减少冲突）。在这里，我们不会讨论太深入的问题，只是来看看如何简单的使用QLALR来实现一个小型语言的解析器。

Plover（珩科鸟）

为了找到一个合适的示例语言，让我们回到上个世纪八十年代，那个时候文字探险（译者注：就是MUD了）还闪耀着光芒。文字探险就是一种玩家们通过输入命令进行交互的游戏。这些命令通常是比真实的人类语言简单得多的一种语言，通常情况下使用的是一种简化的伪英语。这种语法是典型的简单精确。因此我们发现它作为一个QLALR的实例非常合适。

我们将把我们的这种语言称作Plover（在那个用文字探险的时代，玩过的朋友都会眼前一亮的一个名字）。让我们来看几个Plover句子。

north
go north
eat the tasty apple
put orange peel in the trash bin

这里是BNF（巴科斯范式）格式的一个完整Plover语法：

Input ::= Sentence

Sentence ::= SingleVerbSentence
          |  OneNounSentence
          |  TwoNounSentence

SingleVerbSentence  ::= 'go' SingleVerb
                     |  SingleVerb

SingleVerb ::= 'north' | 'south' | 'west' | 'east'

OneNounSentence ::= OneNounVerb Noun

OneNounVerb ::= 'eat'

Noun ::= 'the' ObjectNameList
      | ObjectNameList

ObjectNameList ::= OBJECTNAME
                |  ObjectNameList OBJECTNAME

TwoNounSentence ::= TwoNounVerb Noun Preposition Noun

TwoNounVerb ::= 'put'

Preposition ::= 'in'

OBJECTNAME是一个可以为任意单词的口令，就像编程语言中的变量名一样。其它的口令大家通过拼写就知道意思了。

QLALR规范

QLALR的输入是一个包含语法、口令定义和产品完成时所执行的C++代码的文件（后缀为.g），可以用于构建一个符号栈并且保持对解析状态跟踪。另外，口令管理器必须单独实现，要么在这个.g文件中，要么在一个单独的C++源文件中。

让我们先来看看这么实现解析的类的定义。

class CommandInterpreter : public $table
{

public:
    CommandInterpreter();
    ~CommandInterpreter();

    Command parse();

    int nextToken();

    void setInput(const QString &input);

    inline void reallocateStack();

    inline QString &sym(int index)
    { return sym_stack [tos + index - 1]; }

private:
    int tos;
    QStringList tokens;
    QVector sym_stack;
    QVector state_stack;
    QString yylval;
};

这个类并不是生成的。我们用它来为Plover创建一个方便的前端。$table将会被QLALR所生成的类替代，其中包含了我们在parse()函数中所需要的常量、表和函数。

QLALR使用一个状态栈这样的有限的状态机实现了它的解析。我们自己保存这个栈，当然QLALR会告诉我们哪些状态需要推送到这个栈中和什么时候再次弹出这些状态。tos是用来指向这个状态栈的顶端。稍后会就这一点进一步解释。

sym_stack是一个符号栈，我们在这里保存了一些QString。sym()用来获取和当前产品相关的值。当遇到一个OBJECTNAME时，口令管理器就会设置yylval。我们用它来更新符号栈。

要开始一个命令（Command）的解析，我们需要设置输入（setInput()）并且调用parse()，它会在解析的时候为我们构建Command。为了完整起见，我们先展示一下Command的类定义（这一部分没有在.g文件中声明）。

class Command
{

public:
    enum Verb { Eat, Go, Put, North, East, West, South };
    enum Preposition { In };
    enum State { Valid, Invalid };

    State state;
    QString errorMessage;

    Verb verb;
    QList nounNames; // First noun
    Preposition preposition;
    QList secondNames; // Second noun
};

让我们来继续看QLALR的输入文件：

%parser CommandParser
%merged_output commandparser.cpp
%start Input

%parser给出了由QLALR生成的类的名称。%merged_output规定了我们只想输出一个文件，它会同时包含.g文件中的C++的定义和实现代码。如果您想生成单独的头文件和实现文件，也可以使用%decl和%impl。%start规定了产品解析的开始位置。输出到声明部分的代码由/:和:/包含，实现部分由/.和./包含。

然后我们定义了这些口令：

-- The verbs

%token EAT "eat"
%token GO "go"
%token NORTH "north"
%token EAST "east"
%token SOUTH "south"
%token WEST "west"
%token PUT "put"

-- The preposition

%token IN "in"

-- Object names

%token THE "the"

%token OBJECTNAME "object"

口令由%token设定。它们将会变为生成的解析器的常量，并且会由口令管理器返回。注意这里给定的字符串只是用于错误处理，例如在解析自身的时候它们并不会被用到。

对于我们这个小语言，我们通过nextToken()函数实现了我们自己的口令管理器。因为我们是在解析期间自己调用的这个函数，如果需要的话，也可以使用任意的语法分析程序生成器，例如lex。

int CommandInterpreter::nextToken()
{
    if (tokens.isEmpty()) {
        return EOF_SYMBOL;
    }

    QString nextToken = tokens.takeFirst();

    nextToken = nextToken.toLower();

    if (nextToken == "eat") {
        return CommandParser::EAT;
    }

    ...

    if (nextToken == "the") {
        return CommandParser::THE;
    }

    yylval = nextToken;
    return CommandParser::OBJECTNAME;
}

tokens是一个QVector，包含了Plover语句的单词（例如[ 'put' 'gold' 'in' 'chest' ]）。正如您所见到的，当识别出认识的口令，就简单地返回口令常量。注意当遇到一个对象名称的时候，就保存这个口令的值。后面会用到它。

语法

在这一部分中，我们将会看看Plover语法的实现。也就是在这里，QLALR（或者其它做同样事情的解析程序生成器）的使用真正帮到我们了。

Input: Sentence ;

Sentence: GO SingleVerbSentence ;
Sentence: SingleVerbSentence ;
Sentence: OneNounSentence ;
Sentence: TwoNounSentence ;

产品的每一部分（或者是一个口令或者是另外一个产品）是由空格（whitespace）分隔的。如果这个产品有其它选择，它们会按照上面所显示的Sentence产品那样给出。

当一个产品完成时，我们可以插入代码：

ObjectName: OBJECTNAME ;
/.
    case $rule_number: {
        sym(1) = yylval;
    } break;
./

/.和./中间的代码会被插入到生成的解析器中，并且当解析器匹配到之前的产品时执行这一代码。$rule_number将会被这个语法中代表这个产品的数字所替代。

sym()函数会访问符号栈。它会获取和当前产品相关的值，例如sym(1)总是代表当前产品的第一个元素。我们的符号栈是由一组QString组成的。我们只保存OBJECTNAME的值，所以对于语法中的其它部分这个栈总是包含空字符串。

我们将不会查看所有的产品，因为我们已经用BNF格式展示了Plover语法。但在我们离开产品之前，让我们看看对象和句子是如何被解析的吧。

ObjectList: ObjectList ObjectName ;

Noun: THE ObjectList ;
Noun: ObjectList ;

ObjectList: ObjectName ;
/.
    case $rule_number: {
        command.nounNames.append(sym(1));
    } break;
./

...

TwoNounSentence: PUT Noun IN Second ;
/.
    case $rule_number: {
        command.verb = Command::Put;
        command.preposition = Command::In;
    } break;
./

注意产品的每一个部分都将会在符号栈中拥有一个单独的值。

parse()函数

在这个parse()函数中，我们使用了由QLALR所生成的表来进行真正的解析。QLALR还生成了一些帮助函数。

这个解析函数有三个部分：

• 找到一个产品
• 执行找到这个产品的代码（正如我们之前所看到的）
• 处理解析错误

Command CommandInterpreter::parse()
{
    Command command;

    const int INITIAL_STATE = 0;
    int yytoken = -1;

    tos = 0;
    state_stack[++tos] = INITIAL_STATE;

    while (true) {
        const int state = state_stack.at(tos);
        if (yytoken == -1 && - TERMINAL_COUNT != action_index [state] ) {
            yytoken = nextToken();
        }

        int act = t_action (state, yytoken);
        if (act == ACCEPT_STATE) {
            command.state = Command::Valid;
            return command;

        } else if (act > 0) {
            if (++tos == state_stack.size())
                reallocateStack();
            state_stack[tos] = act;
            yytoken = -1;
        } else if (act < 0) {

这部分看起来也许有一点可怕并且难以理解，但是不要怕，这部分代码通常对于解析器来说都是一样的。所以就把它们复制粘贴一下，然后就过去了。这里的要点是t_action()会从当前状态找到下一个状态。当它需要一个新的口令时，它会返回正值；当一个产品完成时，它会返回负值。零值意味着在语法中当前口令失败（也就是一个错误）。

这个while循环会一直运行，知道发生错误或者到达ACCEPT_STATE（例如，输入和语法匹配，并且我们找到了一个有效的命令）。

        } else if (act < 0) {
            int r = -act - 1;
            tos -= rhs[r];
            act = state_stack.at(tos++);

            switch(r) {
./

Input: Sentence ;

...

/.
            } // of the switch

            state_stack [tos] = nt_action (act, lhs [r] - TERMINAL_COUNT);
        } else {

在一个产品被找到并且相应的代码（如果有的话）执行之后，我们删除这个已经完成的产品所使用的状态，并且继续处理接下的产品。这是通过更新tos和调用nt_action()完成的，nt_action()会获取在新的tos位置的动作。再一次，简单地复制和粘贴这部分代码到您的解析器就可以了。

最后，我们来看看错误处理：

      } else {
         QString merrorMessage;
          int ers = state;
          int shifts = 0;
          int reduces = 0;
          int expectedtokens[3];
          for (int tk = 0; tk < TERMINALCOUNT; ++tk) {
              int k = taction(ers, tk);


          if (! k)
            continue;
          else if (k < 0)
            ++reduces;
          else if (spell[tk]) {
              if (shifts < 3)
                expected_tokens[shifts] = tk;
              ++shifts;
          }
      }


...

为了在特定状态的语法中检查哪些口令被确认了，我们对所拥有的全部口令调用t_action()，并且之后把接受的口令添加到一个数组中，使其可以用于错误信息。在这里我们不用再显示错误信息代码的部分。Plover的错误信息对于其它语言没有什么用处。例如“我不理解这句话”这样的消息对于C编译器输出来说时非常恼人的。我们为口令所指定的字符串已经被添加到一个数组spell中，数组的索引值和口令值一致。因此如果要获取一个口令的文本名称，可以写spell[PloverParser::TO]。

更进一步

如果想要一个更为复杂的实例，您可以看看Qt Script（通常发布在Qt 4的src/script/parser目录下）中的.g文件。您还可以在util/qlalr/examples目录下找到4个实例。如果您的目标是成为QLALR的专家，可以研究一下src/corelib/xml/qxmlstream.g。

源代码

本文中提到的实例的源代码可以在Qt Quarterly的网站下载：qq33-qlalr.zip。

关于作者

Geir Vattekar是Nokia, Qt的一名科技作者。在写作之余，他很喜欢交互科幻（文字探险）和函数编程。

译者注：大家还可以参考一下这篇文章 Kent Hansen - Developer Daze(tm) presents: A Closer Look at QLALR

0 comments