只消你正在Unix境遇中写进轨范，你一定会相逢奥密的Lex&YACC，就如GNU/Linux用户所熟知的Flex&Bison，这里的Flex便是由Vern Paxon告竣的一个Lex，Bison则是GNU版本的YACC。正在此咱们将联合称谓这些轨范为Lex和YACC。新版本的轨范是向上兼容的(译注：即兼容老版本)，以是你能够用Flex和Bison来测验下咱们的实例。这些轨范适用性极广，但好像你的C编译器相通，正在其主页上并没有刻画它们，也没相闭于奈何行使的新闻。当和Lex勾结行使时，YACC实正在是棒极了，不过Bison的主页上并没有刻画Bison怎么跟Lex勾结行使以天生代码的相应阐发。

　　即使行使适当，这些轨范(指LEX&YACC)能够让你容易的解析繁复的说话，当你需求读取一个设备文献时，或者你需求编写一个你我方行使的说话的编译器时，这对付你来说是莫大的裨益。本文档能供应给你少许帮帮，你将出现你再也无须手工写解析器了，Lex & YACC便是为你量身打造的利器。

　　Lex会天生一个叫做『词法领会器』的轨范。这是一个函数，它带有一个字符散布入参数，词法领会器函数看到一组字符就会去成家一个闭头字(key)，选用相应手腕。一个尽头方便的例子(example1)如下:

　　第一个别，位于%{和%}对之间直接包括了输出轨范(stdio.h)。咱们需求这个轨范，由于行使了printf函数，它正在stdio.h中界说。第二个别用’%%’割据开来，以是第二行开始于’stop’，一朝正在输入参数中碰到了’stop’，接下来的那一行(printf()挪用)将被实践。除此除表，尚有’start’，其跟stop的手脚差不多。咱们再次用’%%’终止代码段。为了编译上面的例子，只需务实践以下敕令：

　　属意：即使你用flex，则就将lex敕令用flex代庖，还需求将’-ll’选项改成’-lfl’。正在RedHat 6.x以及SuSe中需求云云做。云云，Lex将天生’example1’这个文献。运转该文献爱赢体育，它将守候你输入少许数据。每次你输入少许不行家的敕令(非’stop’和’start’)，它会将你输入的字符再次输出。你若输入’stop’，它将输出’Stop command received’。用一个EOF(^D)来终止轨范。也许你念大白，它是何如运转的，由于咱们并没有界说main()函数。这个函数(指main())曾经正在lib1(liblex)中界说好了，正在此咱们选用了编译选项’-ll’

　　老破例达式是一种行使元说话的形式刻画。表达式由符号构成。符号普通是字符和数字，尚有少许拥有迥殊寄义的其他记号，如下表：

　　这个实例(example2)自己并没什么用途，下一个实例也不会提及正则表达式。但这里它呈现了怎么正在Lex中行使正则表达式，这正在后面将尽头有效。

　　该Lex文献刻画了两种token成家：WORDs和NUMBERs。正则表达式尽头恐惧，不过只需求稍花力气便能够加以领会。此中NUMBER成家“[0123456789]+”能够写成“[0-9]+”。WORD成家就有点繁复：[a-zA-Z][a-zA-Z0-9]*第一个别仅仅成家一个’a’到’z’或’A’到’Z’之间的字符，也即一个字母。接着该字母后面需求连上0个或多个字符，这些字符能够是字母，也能够是数字。这里为何用’*’? ’+’吐露起码1次的成家。一个WORD只要一个字符也能够很好的成家，正在第一个别咱们曾经成家到了一个字符，以是第二个别能够是0个成家，以是用’*’。用这种形式，咱们就仿照了许多编程说话中对付一个变量名的哀求，即哀求变量名『务必』以字母开始，不过能够正在后续字符顶用数字爱赢体育Lex与YACC详解。也便是说’temperature1’是一个无误的定名，不过’1temperature’就不是。像example1相通编译example2，并输入少许文本，如下：

　　你也许会思疑，整个的输出中的空格是从哪来的？缘故很方便：从输入而来，咱们不正在空格上成家任何实质，以是它们又输出来了。Flex主页上有正则表达式的周详文档。许多人感应perl正则表达式主页的阐发尽头有效，不过Flex并不告竣perl所告竣的整个东西。你只需求确保不写少许形如’[0-9]*’的空成家即可，你的词法领会器(由Flex天生)将不明就里的发端持续的成家空字符。

　　YACC能够解析输入流中的标识符(token)，这就明了的刻画了YACC和LEX的相闭，YACC并不大白『输入流』为何物，它需求事先就将输入流预加工成标识符，固然你能够我方手工写一个Tokenizer，但咱们将这些处事留给LEX来做。YACC用来为编译器解析输入数据，即轨范代码。这些用编程说话写成的轨范代码一点也不含糊其词——它们只要一个旨趣。正由于如许，YACC才不会去对于那些有歧义的语法，而且会怨言shift/reduce或者reduce/reduce冲突。更多的闭于混沌性和YACC『题目』能够正在『冲突』一章中找到。

　　假定咱们有一个温度计恒温器，咱们要用一种方便的说话来独揽它。闭于此的一个会话、如下：

　　有两个中心需求属意：第一，咱们包括了『y.tab.h』；第二，咱们不再打印输出了，咱们返回标识符的名字。之所云云做是由于咱们将这些返回传送给了YACC，而它对付咱们屏幕上的输出并不伤风。 『y.tab.h』中界说了这些标识符。不过y.tab.h从哪里来？它由YACC从咱们编写的语法文献中天生，语法文献尽头方便，如下：

　　第一个别，咱们称之为根(root)。它告诉咱们有一个『commands』，而且这些『commands』由单个的『command』构成。正如你所见到的那样，这是一个准则的递归构造，由于它又再次包括了『commands』。这意味着该轨范能够一个个的递减一系列的敕令。参见『LEX和YACC内部处事道理』一章，阅读更多的递归细节。第二个章程界说了『command』的实质。咱们只假定两种敕令。一个heat_switch由HEAT标识符构成，它后面随着一个状况，该状况正在LEX中界说，为『on』或『off』。target_set稍微有点繁复，它由TARGET标识符、TEMPERATURE以及一个数字构成。前面的谁人例子只要YACC文献的语法个别，开始正在YACC文献中尚有其它实质，完善的YACC文献如下：

　　函数yyerror()正在YACC出现一个毛病的时分被挪用，咱们只是方便的输出毛病新闻，但实在还能够做少许更美丽的事宜，参见文档尾的『进阶阅读』个别。yywrap()函数用于持续的从一个文献中读取数据，当碰到EOF时，你能够再输入一个文献，然后返回0，你也能够使得其返回1，暗意着输入终止。更多细节，参见『YACC和LEX内部怎么处事的？』一章。接着，这里有一个main()函数，它根本什么也不做，只是挪用少许函数。结尾一行方便的界说了我将行使的标识符，即使挪用YACC时，行使『-d』选项，那么它们会输出到y.tab.h中。编译并运转恒温独揽器：

　　正在此，景况有所厘革，咱们现正在挪用YACC来编译咱们的轨范，它创筑了y.tab.c和y.tab.h. 我接着再挪用LEX。 编译时，咱们去除了『-ll』编译选项，由于此时咱们有了我方的main()函数，并不需求libl来供应。属意：即使正在编译进程中报错说找不到『yylval』，那么正在example4.l的#include y.tab.h下面加上：

　　咱们曾经能够无误的解析温度计敕令了，而且能对少许毛病做记号。但也许少许奸诈的人会嫌疑说，该解析器并不大白你应当做什么，也没有执掌少许你输入的数值。让咱们来增加能读取新的温度参数的效力。为到达此目标，咱们得大白LEX中的NUMBER成家要转化成一个数值，然后本事为YACC所摄取.每当LEX成家到了一个主意字串，它就将该成家文本赋值给『yytext』，YACC则按次正在『yylval』中来查找一个值，正在example5中，咱们能够取得一个分明的计划：

　　如你所见，咱们正在yytext顶用了atoi()，并将结果存储正在yylval中，使得YACC能够『瞥见』它。 同理，咱们再执掌STATE成家，将其与『on』斗劲，若念等，则将yylval筑树为1。接下来，咱们就得窥察YACC怎么来应对。咱们来看看新的temperature target章程筑树：

　　为取得章程中第三个另表值(NUMBER)，咱们用『$3』来吐露，每次yylex()返回时，yylval的值便倚赖到了终结符上，其值能够通过『$-常数』来获取。为更进一步加深领会，咱们来看『heat_switch』章程：

　　之前咱们曾经将LEX文献写好了，接下来只需求编写YACC语法文献，而且对词法领会器做少许窜改，使得其能够返回少许值给YACC。example6中的词法领会器如下：

　　留神的话，你会出现yylval曾经厘革了！咱们不再以为它是一个整数，而是假定为一个char*类型数据。为保留方便性，咱们挪用strdup并所以糟塌了许多内存。但这并不影响你解析这个文献。咱们需求存储字符串的值，正在此咱们执掌的都是少许定名，文献名以及区域命。鄙人一章，咱们将注解怎么对于少许繁复类型的数据。为告诉YACC闭于yylval的新类型，咱们正在YACC的语法文献中增加一行：

　　下面是完善的YACC文献，语法斗劲繁复，提倡勾结代码画AST树来帮帮领会（原文这里的代码有不少题目，下面是校正后的代码，对语法也简化了一点点）：

　　固然LEX和YACC的史乘要早于C++，不过仍旧能够用它们来天生一个C++解析器。但咱们用LEX来天生C++的词法领会器，YACC并不大白怎么直接来执掌这些，以是咱们造止备这么做。我以为斗劲好的做法是，要做一个C++解析器，就需求LEX天生一个C文献，而且让YACC来天生C++代码。但当你这么做的时分，正在这个进程中你将会碰到题目，由于C++代码默认景况下并不行找到C的函数，除非你将那些函数界说为extern “C”。为达此目标，咱们正在YACC代码中编写一个C开始：

　　这是由于C++中的一个闭于界说的章程，即不应许yydebug的多处界说。你还也许出现，你需求正在你的LEX文献中反复#define YYSTYPE，这是因为C++中苛苛的类型反省(机造)酿成的。遵照如下形式来编译：

　　因为-o选项的存正在，y.tab.h现正在形成example_cpp.hpp，记住这点。总结： 不要自寻不快的正在C++中编译你的词法领会器，让它呆正在C的领地里。正在C++中编写解析器时，(也得)确保向编译器注释明了，即你的C函数都有一个extern “C”声明。

　　正在YACC文献中，你界说了你我方的main()函数，它正在某个点上挪用了yyparse()。YACC会创筑你的yyparse()函数，并正在y.tab.c中终止该函数。yyparse()函数读取一个『标识符/值对』(token/value pairs)流，这些流需求事先就供应，这些流能够是你我方手写的代码供应的，也能够是LEX天生的。正在咱们的示例中，咱们把这个处事丢给了LEX。LEX天生的yylex()函数从文献参数FILE *file中读取字符(文献名为yyin)。即使不筑树成yyin，则默以为准则输入，它会输出到yyout中，即使不加筑树，便是stdout爱赢体育。你能够正在yywrap()函数中窜改位于文献尾的yyin.yywrap()函数。这些窜改使得你能够掀开另少许文献，并一连解析。即使是这种景况，那么就让yywrap()返回0，即使你念正在该文献上终止解析，就让它返回1。每次yylex()挪用城市返回一个整数值，该值代表了一个标识符类型(token type)。它告诉YACC，曾经读取了这种标识符。该标识符能够有一个值，它应当存放正在yylval变量中。yylval的默认类型为int，不过你能够窜改其类型，通过正在YACC文献中#define YYSTYPE。词法领会器需求也许访候yylval，为到达此功效，(yylval)务必正在词法领会器(lexer)中被声明为一个表部变量(extern variable)。原本的YACC粗心了这点，并没有为你干这项处事，以是，你务必增加以下代码到你的词法领会器中，就正在#include y.tab.h下面：

　　正在前面我曾经说过，yylex()需求返回它碰到了一个什么标识符类型，并将其值存储正在yylval中。当这些标识符正在%token敕令中界说时，它们就被付与了少许数字ID，从256发端。因为这个原形，(咱们)能够将整个的ascii字符看成标识符。假定你要写一个估量器，到现正在为止，咱们也许曾经云云写了其词法领会器：

　　没有需要弄这么繁复。用字符动作速记法来动作标识符的数字ID，咱们能够云云来重写咱们的词法领会器：

　　结尾一行成家任何的单个字符，不然便是不行家字符。而YACC的语法文献则是云云:

　　云云特别简短而直观，你就不必正在文献头用%token来界说那些ascii字符了。另一方面，云云构造尚有少许好处，它能够成家整个丢给它的东西，而避免了将那些不行家的输入输出到准则输出的默认手脚。即使用户正在暂时估量器上输入一个’^’字符，将会导致一个解析毛病，而不是将其输出到准则输出中。

　　递归是YACC一个极其紧要的性情。没有递归的话，你就确定一个文献是由一系列独立的敕令构成仍旧由语句构成。因为YACC本身的性情，它只对第一个章程或谁人你将其计划为『开始章程』的章程感风趣。开始章程用’%start’符号记号爱赢体育。YACC中的递归以两种景象呈现，左递归和右递归。左递归是你应当时常行使的，它们看起来如下：

　　这是正在说，一个command要么为空，要么它包括了更多的commands，后面再跟一个command。YACC的这种处事形式意味着它现正在能够容易的剔除单个的command群并一步步简化(执掌)。拿上面的例子和下面的右递归做斗劲：

　　不过云云做开销有点大，即使(commands)是%start章程(即开始章程)，那么YACC会将整个的commands存储正在你的栈数据中(file on the stack)，这将糟塌豪爽内存。以是，正在解析长的语句时，务必行使左递归，比方一切文献。但有时难以避免右递归，可是，即使你的语句并不太长，你就没有需要越轨行使左递归。即使你有少许东西来终结(所以而割据)你的commands，右递归就尽头适合了，但开销仍旧有点大:

　　本文档的早期版本毛病的行使了右递归。Markus Triska友谊的提示咱们这点(毛病)。

　　现正在，咱们需求界说yylval的类型。不过这并不连续恰如其当。咱们也许会多次云云做，由于需求执掌多种数据类型。回到咱们假定的谁人恒温器，也许你念挑选独揽一个加热器，比方：

　　云云的话，就哀求yylval是一个union，它能够存储字符串，也能够存储整数，但并不是同时存储。追思之前咱们讲过，咱们提前告诉YACC哪种yylval类型会要执掌是通过界说YYSTYPE来告竣。同样，咱们能够界说YYSTYPE为一个union，YACC中有一种轻省的要领来告竣，即%union语句。正在example4根柢上，我编写example7的YACC语法：

　　咱们界说了union，它只包括一个整数和一个字符串。接着行使了一个扩展的%token语法，咱们向YACC注释了应当获取union哪个个另表标识符。正在本例中，咱们让STATE标识符用一个整数(来吐露)，这跟之前相通。NUMBER同理，咱们之前用来读取温度。不过WORD有所厘革，它声明为需求一个字符串。词法解析器文献有所厘革：

　　正如你所见，咱们不再直接访候yylval，咱们增加了一个后缀来阐发咱们要访候谁人个别。咱们不再需求正在YACC语法文献中来干这个处事，YACC正在这里耍了下妖术：

　　因为上面的%token声明，YACC自愿挑选了union中的’string’成员。属意这里$2中存储的一份拷贝，正在后面它会告诉用户发送死令到哪个heater（需求正在C文献头界说char *heater）：

　　许多景况下，咱们不肯望从准则输入解析，而愿望解析给定的字符串。告竣要领是自界说告竣YY_INPUT，整体做法如下：

　　YACC中有很多调试反应新闻。这些调试新闻的价格有点高，以是你需求供应少许开闭来掀开它。当调试你的语法时，正在YACC敕令行中增加—debug和—verbose选项，正在你的C文献头中增加以下语句：

　　这将天生一个y.output文献，此中阐发了所创筑的谁人状况机。当你运转谁人天生的二进造文献，它将输出许多运转时新闻。内部包括暂时所运转的状况机以及读取到的少许标识符。Peter Jinks写了一篇闭于调试的作品，他正在此中讲述了少许常见得毛病以及怎么校正这些毛病。

　　YACC解析器正在内部运转的是一个『状况机』，该状况性能够有多种转台。接着有多个章程来管造状况间的彼此转化。任何实质都是从『root』章程发端。正在example7的y.output文献中：

　　默认情况下，这个状况机从『commands』章程发端递减演化，这也是咱们之前的谁人递归章程，它界说了『commands』并从单个的『command』举办构造，后面随着一个分号，然后也许再随着更多的『commands』。这个状况机持续递减演化，直到它碰到某些它能领会的东西，正在本例中，为一个ZONETOK，也即单词『zone』。然后转化到状况1，正在此，进一步执掌一个zone command:

　　第一行中有一个『.』，它用来阐发咱们所处的名望：即方才识别到了一个ZONETOK，目前正正在寻找一个『quotedname』。明晰，一个『quotedname』会以QUOTE发端，它将咱们转化到状况4。为进一步跟踪，用正在『调试』章节中提到的标识来编译example7。

　　一朝YACC警戒你呈现了冲突，那么你的困难来了。要办理这些题目显得是一种方法景象，它会教会许多闭于你的说话的东西。比你念大白的要多的多的实质。题目缭绕于怎么来翻译一系列标识符。假定咱们界说了一种说话，它需求继承一下两种敕令：

　　也许你曾经嗅到了困难的滋味。状况机从读取单词『word』发端，接着它遵照下一个标识符感应转换到何种状况。接下来的标识符能够是『mode』，它指定了怎么来删除heater，或者是将要删除的heater。然而这里的困难是爱赢体育，对付这两个敕令，下一个标识符都将是一个WORD。YACC所以也无法定夺下一步该干嘛。这回导致一个『reduce/reduce』警戒，而下一个警戒便是『delete_a_heater』节点正在状况转化图中长久也不行到达恒温器。这种景况的冲突容易办理(比方，重定名第一个敕令为『delete all heater』，或者将『all』动作一个离开的标识符)，但有时，(要办理冲突)却尽头穷困。 通过『--verbose』参数天生的y.output文献能够供应给你极大的帮帮。

　　GNU YACC(Bison)有一个尽头棒的件，正在此中很好的记载了YACC的语法。此中只提到了一次LEX，然而它仍旧很棒的。你能够用Emacs中谁人尽头好的『pinfo』用具阅读o文献。同时，正在Bison的主页上能够得到它：Bison手册。FLEX有一个不错的主页。即使你简略清晰了FLEX所作所为，那将诟谇常有益的。FLEX的手册也能够联机获取。正在这些闭于YACC和LEX的先容之后，你也许感应你念需求更多的新闻。下面的书本咱们都还没有阅读，但他们听起来不错：