yacc语法分析器

Yacc（Yet Another Compiler Compiler）是一个语法分析器，它能够接受词法分析器Lex的输入并将一系列Token解析为抽象语法树（AST）。阅读本文前，需要先阅读Lex章节的内容。本文将介绍一些关于Yacc的简单使用。和Lex、Flex的关系类似，Yacc的现代GNU版叫做Bison，两者基本用法相同，因此后文所说的Yacc都指Bison程序。

安装Bison

如果我们的操作系统没有预装Bison，直接从软件源中安装即可。此外，我们也可以查看Bison工具的帮助手册，了解其中的命令选项。

man bison

Yacc的使用

和学习Lex一样，我们直接从一个简单的例子入手。

英语中，单词词性有：NOUN（名词），PRONOUN（代词），VERB（动词），ADVERB（副词），ADJECTIVE（形容词），PREPOSITION（介词），CONJUNCTION（连词）。我们编写一个程序，识别一个序列是不是一个英文句子。我们的序列用固定的几个字符串组合表示，例如：adj noun adv verb adj noun根据英语语法，这个序列表示一个句子。

如何判定一个序列是一个句子呢？根据英语语法，我们简单的定义如下文法产生式：

sentence->simple_sentence|compound_sentence

simple_sentence->subject verb object|subject verb object prep_phrase

compound_sentence->simple_sentence CONJUNCTION simple_sentence|compound_sentence CONJUNCTION simple_sentence

subject->NOUN|PRONOUN|ADJECTIVE subject

verb->VERB|ADVERB VERB|verb VERB

object->NOUN|ADJECTIVE object

prep_phrase->PREPOSITION NOUN

注：上面的产生式中，大写单词表示Lex识别的Token（终结符），小写的单词都是中间推导的过程（非终结符）。

理解了上面的规则其实就好办了，我们只要按照Yacc的文件格式编写.y文件就行了。当然除此之外，我们还需要一个.l文件供Lex使用。

english.l

%{
#include <stdio.h>
#include "y.tab.h"
%}
%%
verb {
    printf("VERB TOKEN\n");
    return VERB;
}
adj {
    printf("ADJECTIVE TOKEN\n");
    return ADJECTIVE;
}
adv {
    printf("ADVERB TOKEN\n");
    return ADVERB;
}
noun {
    printf("NOUN TOKEN\n");
    return NOUN;
}
prep {
    printf("PREPOSITION TOKEN\n");
    return PREPOSITION;
}
pron {
    printf("PRONOUN TOKEN\n");
    return PRONOUN;
}
conj {
    printf("CONJUCTION TOKEN\n");
    return CONJUNCTION;
}
[ \t]+ {}
%%
int yywrap(void)
{
    return 1;
}

english.y

%{
#include <stdio.h>
%}
%token NOUN PRONOUN VERB ADVERB ADJECTIVE PREPOSITION CONJUNCTION
%%
sentence: simple_sentence {
    printf("parsed simple sentence\n");
    }
    | compound_sentence {
        printf("parsed compound sentence\n");
    }
    ;

simple_sentence: subject verb object
    | subject verb object prep_phrase
    ;

compound_sentence: simple_sentence CONJUNCTION simple_sentence
    | compound_sentence CONJUNCTION simple_sentence
    ;

subject: NOUN
    | PRONOUN
    | ADJECTIVE subject
    ;

verb: VERB
    | ADVERB VERB
    | verb VERB
    ;

object: NOUN
    | ADJECTIVE object
    ;

prep_phrase: PREPOSITION NOUN
    ;

%%

extern FILE *yyin;

int main(void)
{
    yyparse();
}

void yyerror(char *s)
{
    fprintf(stderr, "%s\n", s);
}

下面我们分别解释一下这两个文件。

Lex结合Yacc

和上一篇使用Lex的方式不同，这里我们结合使用了Yacc和Lex，我们注意Lex文件的写法：

#include "y.tab.h"：Yacc在编译.y文件时，会对声明的Token进行宏定义，其结果存储在y.tab.h中，Lex文件需要引用这个头文件才能使用这些Token宏定义。
注意每个匹配动作的return语句，返回值是一个Token（的宏定义），这些Token我们在.y文件中编写。

Yacc文件格式

Yacc文件格式和Lex很像，它在设计时就为了让用户方便，设计成了和Lex一样的格式。

首先{%和%}内放置了一些C语言代码，这和Lex文件是一样的，我们在这里使用了include语句。

接下来的%token定义了一系列Token。实际上我们可以打开y.tab.h看看，这些定义的Token会被Yacc编译成宏定义的数字。

之后，%%表示当前区块结束，进入规则区块。规则区块中，我们发现，其实编写的内容和上文我们写的“文法产生式”基本是一样的，Yacc其实就是这样使用的，我们定义一系列符合BNF的产生式，Yacc能够生成能够自动推导的代码。这部分的写法遵循上面的例子就好了，没什么多解释的。

最后，又出现了%%表示下一部分是用户代码区块，这和Lex文件一样。我们在这一部分，编写了我们的main函数，函数中调用了yyparse()，注意这个函数是Yacc提供的不是Lex的。总之，调用yyparse()，整个程序就能按照我们的预期，由Lex进行词法分析并输出Token序列，接着Yacc按照我们定义的产生式进行推导。

注意yyerror()，这个函数是语法分析器遇到错误语法时的默认回调函数，我们实际上是覆盖了默认的yyerror()函数（默认的yyerror()通过宏进行定义，如果我们覆盖了yyerror，就会使用我们定义的yyerror）。

测试上面的程序

我们现在编写好了Yacc + Lex程序，这里我们测试一下，执行以下命令编译代码。

lex english.l && yacc -d english.y && gcc lex.yy.c y.tab.c

我们先测试一个错的情况：

注意：syntax error其实就是由yyerror输出的，语法分析器遇到错误语法默认就会输出这条信息。

一个简单英文句子：

一个复杂英文句子：

注意：Linux控制台下，请使用ctrl+D向标准输入发送EOF结束输入。

一些其他的Yacc用法

上面的例子比较简单，覆盖的内容不是很全面，例如如何从Lex向Yacc传递识别的数据、如何定义Token类型、如何构建语法树等。在后一篇笔记中，我们将介绍一个Lex和Yacc结合使用的另一个例子：类似SQL语法的解析。

作者：Gacfox