只须你正在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个成家，于是用’*’。用这种形式，咱们就师法了良多编程言语中对待一个变量名的条件，即条件变量名『必需』以字母下手，然而可能正在后续字符顶用数字。也便是说’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』节点正在状况转化图中始终也不行抵达不朽情缘官方网站Lex与YACC详解。这种环境的冲突容易管理(比如，重定名第一个夂箢为『delete all heater』，或者将『all』行动一个分裂的标识符)，但有时，(要管理冲突)却异常贫苦。 通过『--verbose』参数天生的y.output文献可能供应给你极大的帮帮。

　　GNU YACC(Bison)有一个异常棒的件，正在个中很好的纪录了YACC的语法。个中只提到了一次LEX，然而它照旧很棒的。你可能用Emacs中谁人异常好的『pinfo』器材阅读o文献。同时，正在Bison的主页上可能获取它：Bison手册。FLEX有一个不错的主页。借使你简陋剖析了FLEX所作所为，那将詈骂常有益的。FLEX的手册也可能联机获取。正在这些合于YACC和LEX的先容之后，你可以感觉你思必要更多的新闻。下面的竹帛咱们都还没有阅读，但他们听起来不错：