编译原理之lex,yacc学习
写在前⾯的⼏句废话
最近在项⽬的过程中接触了lex 和 yacc，他们可以帮助我们来实现⾃⼰的领域语⾔。最典型的应⽤就是可以帮助我们来实现⾃定义测试脚本的执⾏器。但是，这⾥也有⼀个限制，就是测试脚本要做的基本事情必须有现成的C语⾔库来实现，否则就做不到了；如果基本的操作是⽤java来做的，那么还可以⽤Antlr，这⾥不对Antlr做详细介绍。
lex是什么？
教科书上把lex的作⽤的作⽤叫做“词法分析 lexical analysis ”，这个中⽂叫法⾮常让⼈看不明⽩（叫做“符号提取”更合适），其实从它的英⽂单词lexical上来看他的意思其实是⾮常清楚的。
lexical，在webster上的解释是：of or relating to words or the vocabulary of a language as distinguished from its grammar and construction。
指的是：⼀种语⾔中关于词汇、单词的，与之相对的是这种语⾔的语法和组织
这么来看的话 lexical analysis 的作⽤就应该是语⾔中的词汇和单词分析。事实上他的作⽤就是从语⾔中提取单词。放到编程语⾔中来说，他要做的事情其实就是提取编程语⾔占⽤的各种保留字、操作符等等语⾔的元素。
所以他的另外⼀个名字scanner其实更形象⼀些，就是扫描⼀个⽂本中的单词。
lex把每个扫⾯出来的单词叫统统叫做token，token可以有很多类。对⽐⾃然语⾔的话，英语中的每个单词都是token，token有很多类，⽐如non(名词)就是⼀个类token，apple就是属于这个类型的⼀个具体token。对于某个编程语⾔来说，token的个数是很有限的，不像英语这种⾃然语⾔中有⼏⼗万个单词。
lex⼯具会帮我们⽣成⼀个yylex函数，yacc通过调⽤这个函数来得知拿到的token是什么类型的，但是token的类型是在yacc中定义的。
lex的输⼊⽂件⼀般会被命名成 .l⽂件，通过lex XX.l 我们得到输出的⽂件是
yacc是什么呢？
刚才说完lex了，那么yacc呢，教科书上把yacc做的⼯作叫做syntactic analysis。这次我们翻译没有直译做句法分析，⽽是叫语法分析，这个翻译能好⼀点，意思也基本上⽐较清楚。
其实我们最开始学习英语的时候⽼师都会告诉我们英语其实就是“单词+语法”，这个观点放到编程语⾔中很合适，lex提取了单词，那么是剩下的部分就是如何表达语法。那么yacc做的事情就是这⼀部分（实际应该说是BNF来做的）。
yacc会帮我们⽣成⼀个yyparse函数，这个函数会不断调⽤上⾯的yylex函数来得到token的类型。
yacc的输⼊⽂件⼀般会被命名成 .y⽂件，通过yacc -d XX.y我们得到的输出⽂件是y.tab.h y.tab.c，前者包含了lex需要的token类型定义，需要被include进 .l⽂件中
lex和yacc的输⼊⽂件格式
Definition section
正则匹配原理
%%
Rules section
%%
C code section
.l和.y的⽂件格式都是分成三段，⽤%%来分割，三个section的含义是：
Definition Section
这块可以放C语⾔的各种各种include，define等声明语句，但是要⽤%{ %}括起来。
如果是.l⽂件，可以放预定义的正则表达式：minus "-" 还要放token的定义，⽅法是：代号正则表达式。然后到了，Rules
Section就可以通过{符号} 来引⽤正则表达式
如果是.y⽂件，可以放token的定义，如：%token INTEGER PLUS ，这⾥的定⼀个的每个token都可以在y.tab.h中看到
Rules section
.l⽂件在这⾥放置的rules就是每个正则表达式要对应的动作，⼀般是返回⼀个token
.y⽂件在这⾥放置的rules就是满⾜⼀个语法描述时要执⾏的动作
不论是.l⽂件还是.y⽂件这⾥的动作都是⽤{}扩起来的，⽤C语⾔来描述，这些代码可以做你任何想要做的事情
C code Section
main函数，yyerror函数等的定义
lex和yacc能帮我们做什么？
⼀句话：解释执⾏⾃定义语⾔。有⼏点要注意：
1. ⾃定义语⾔的要做的事情必须可以能通过C语⾔来实现。其实任何计算机能做的事情都可以⽤C语⾔来实现，lex和yacc存在的意义在
于简化语⾔，让使⽤者能够以⼀种⽤⽐较简单的语⾔来实现复杂的操作。⽐如：对于数据库的查询肯定有现成的库可以来完成，但是使⽤起来⽐较⿇烦，要⾃⼰写成语调⽤API，编译才⾏。如果我们想实⾃定义⼀个简单的语⾔（⽐如SQL）来实现操作，这个时候就可以⽤lex和yacc。
2. lex和yacc 做的事情只是：⽤C语⾔来实现另外⼀种语⾔。所以，他没办法实现C语⾔⾃⼰，但是可以实现java、python等。当然你可
以通过Antlr来实现C语⾔的解析和执⾏，如果你这么做的话，C语⾔程序⾸先是通过java来执⾏，然后java⼜变成了本地语⾔（C语⾔）来执⾏，谁叫我们的操作系统都是C语⾔实现的呢。
使⽤lex和yacc我们要做那⼏件事情？
1. 定义各种token类型。他们在.y中定义，这些token既会被lex使⽤到，也会被.y⽂件中的BNF使⽤到。
2. 写词汇分析代码。这部分代码在.l⽂件（就是lex的输⼊⽂件）中。这块的定义⽅式是：正则表达式-->对应操作。如果和yacc⼀起来使
⽤的话，对应的操作通常是返回⼀个token类型，这个token的类型要在yacc中提前定义好。
3. 写BNF。这些东西定义了语⾔的规约⽅式。
关于BNF
是⼀种，请参考：摘录：
<symbol> ::= __expression__
1. <> is a
2. consists of one or more sequences of symbols
3. more sequences are separated by the , '|'
4. Symbols that never appear on a left side are . On the other hand
5. symbols that appear on a left side are and are always enclosed between the pair <>.
在yacc中定义的⽅式其实是：
<symbol> : __expression__ {operation}
| __expression__ {operation}
operation 是满⾜语法时要执⾏的C语⾔代码，这⾥的C语⾔代码可以使⽤⼀些变量，他们是：$$ $1 $2等等。$$代表规约的结果，就是表达式__expression__的值，$1代表的是前⾯ __expression__ 中出现的各个word。举个例⼦：
expr2:
expr3 { $$ == $1; }
| expr2 PLUS expr3 { $$ = plus($1, $3); }
| expr2 MINUS expr3 { $$ = minus($1, $3); }
;
来⾃：
1. expr2 expr3都是BNF中定义的non-terminal
2. PLUS和MINUS都是.y中定义的token类
3. plus和minus 是事先定义好的C语⾔函数
关于yacc中BNF的推导过程引⽤后⾯的《lex和yacc简明教程》做⼀下说明：
1. yacc 在内部维护着两个堆栈；⼀个分析栈和⼀个内容栈。分析栈中保存着终结符和⾮终结符，并且代表当前剖析状态。内容栈是⼀个
YYSTYPE 元素的数组，对于分析栈中的每⼀个元素都保存着⼀个对应的值。例如，当yylex 返回⼀个INTEGER标记时，y acc 把这个标记移⼊分析栈。同时，相应的yylval 值将会被移⼊内容栈中。分析栈和内容栈的内容总是同步的，因此从栈中到对应于⼀个标记的值是很容易实现的。
2. 对expr: expr '+' expr { $$ = $1 + $3; }来说，在分析栈中我们其实⽤左式替代了右式。在本例中，我们弹出“expr '+' expr” 然后压
⼊“expr”。我们通过弹出三个成员，压⼊⼀个成员缩⼩的堆栈。在我们的C 代码中可以⽤通过相对地址访问内容栈中的值，“ $1”代表右式中的第⼀个成员，“ $2”代表第⼆个，后⾯的以此类推。“ $$ ”表⽰缩⼩后的堆栈的顶部。在上⾯的动作中，把对应两个表达式的值相加，弹出内容栈中的三个成员，然后把造得到的和压⼊堆栈中。这样，分析栈和内容栈中的内容依然是同步的。
来看⼀个⽤lex和yacc实现计算器的例⼦
参考了下⾯链接的lex和yacc⽂件：
cal.y
%{
#include <stdio.h>
#include ""
#define YYSTYPE int
int yyparse(void);
%}
%token INTEGER PLUS MINUS TIMES DIVIDE LP RP
%%
command : exp {printf("%d/n",$1);}
exp: exp PLUS term {$$ = $1 + $3;}
|exp MINUS term {$$ = $1 - $3;}
|term {$$ = $1;}
;
term : term TIMES factor {$$ = $1 * $3;}
|term DIVIDE factor {$$ = $1/$3;}
|factor {$$ = $1;}
;
factor : INTEGER {$$ = $1;}
| LP exp RP {$$ = $2;}
;
%%
int main()
{
return yyparse();
}
void yyerror(char* s)
{
fprintf(stderr,"%s",s);
}
int yywrap()
{
return 1;
}
cal.l
%{
#include<string.h>
#include "y.tab.h"
extern int yylval;
%}
numbers ([0-9])+
plus "+"
minus "-"
times "*"
divide "/"
lp "("
rp ")"
delim [ /n/t]
ws {delim}*
%%
{numbers} {sscanf(yytext, "%d", &yylval); return INTEGER;}
{plus} {return PLUS;}
{minus} {return MINUS;}
{times} {return TIMES;}
{divide} {return DIVIDE;}
{lp} {return LP;}
{rp} {return RP;}
{ws} ;
. {printf("Error");exit(1);}
%%
使⽤⽅式：
yacc -d cal.y
lex cal.l
g++ -o cal y.tab.c
运⾏./cal 然后输⼊3+4 ctrl+D就可以看到结果了
关于lex和yacc中⼀些预定义的东西
yyin
FILE* 类型。它指向 lexer 正在解析的当前⽂件。
yyout
FILE* 类型。它指向记录 lexer 输出的位置。缺省情况下，yyin 和 yyout 都指向标准输⼊和输出。yytext
匹配模式的⽂本存储在这⼀变量中（char*）。
yyleng
给出匹配模式的长度。
yylineno
提供当前的⾏数信息。（lexer不⼀定⽀持。）
yylex()
这⼀函数开始分析。它由 Lex ⾃动⽣成。
yywrap()
这⼀函数在⽂件（或输⼊）的末尾调⽤。如果函数的返回值是1，就停⽌解析。因此它可以⽤来解析多个⽂件。代码可以写在第三段，这就能够解析多个⽂件。⽅法是使⽤ yyin ⽂件指针（见上表）指向不同的⽂件，直到所有的⽂件都被解析。最后，yywrap() 可以返回 1 来表⽰解析的结束。
yyless(int n)
这⼀函数可以⽤来送回除了前�n? 个字符外的所有读出标记。
yymore()
这⼀函数告诉 Lexer 将下⼀个标记附加到当前标记后。
参考资料：
⾸先推荐《lex and yacc tutorial》
上⾯pdf的中⽂版《lex和yacc简明教程》在在：
⼀个⽼外写的上⼿教程
这两个⽤ lex 和 yacc实现了 c语⾔解释器

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。