IBM社区对于lex和Yacc的快速入门，附带例子
简书：初识flex
简书：初识bison
bison %code使用
bison声明细则
我们使用的词法分析器为flex，语法分析器为bison。
词法分析器会将输入序列与定义的常规表达式匹配，匹配往往会返回标记。
语法分析器在查看到某个标记序列时，可能会触发某些动作，这便是语法。
bas.y通过yacc生成y.tab.h包含了语法规则需要的词法声明（终结符声明）。
bas.l和y.tab.h通过lex生成了lex.yy.c，用来定义y.tab.c里语标记序列的语法规则中每个标记的语法定义规则。（终结符匹配规则）
bas.y通过yacc和lex.yy.c，会生成y.tab.c，包含了标记序列的语法规则。
（PS:终结符和我们自定义的“标记”等同。）
接下来我们会用两个例子来演示一下flex和bison的配合。
第一个例子：输入name=age时触发，输出name is age years old !!
第二个例子：输入带有括号的满足乘法加法的表达式，输出运算后的值。
当我们输入 tom=10 的输入序列后，输入序列会被flex的scanner获取。
flex对scanner中的字符一一解析匹配，name和age被存储到类型为char*的yytext中再返回，eq则会直接返回一个终结符给语法分析器。
Name.lex
//声明部分 %{%}之内的内容会被复制到Name.tab.c中
%{
#include "Name.tab.h"
#include <stdio.h>
#include <string.h>
%}
char [A-Za-z]
num [0-9]
eq [=]
name {char}+
age {num}+
//规则部分 输入序列与常规表达式的匹配，可能会触发标记返回。
//yylval Yacc的变量，默认为int类型，可以被重定义为char*
//yytext 匹配模式的文本存储在这一变量中（char*）。
%%
{name} {yylval=strdup(yytext);return NAME;} //匹配到名字，返回NAME
{eq} {return EQ;} //匹配到=,返回EQ
{age} {yylval=strdup(yytext);return AGE;} //匹配到年龄，返回AGE
%%
//C代码部分
int yywrap() //返回为1时代表分析结束。
{
return 1;
}
当scanner中的字符都被词法分析器解析完，并将终结符返回给了语法分析器之后，接着语法分析。
我们递归地读取记录，当NAME EQ AGE这个终结符序列被匹配时，我们触发打印 name is age years old！！
Name.y
%{
#include <stdio.h>
typedef char *string;
#define YYSTYPE string
%}
%token NAME EQ AGE //词法分析得到的结果，用于传入语法分析器进行分析
%%
file:record file|record;
record:NAME EQ AGE {printf("%s is %s years old!!!\n",$1,$3);}; //某个标记序列，触发动作
%%
int main()
{
yyparse(); //语法分析
return 0;
}
int yyerror(char *msg)
{
printf("Error encountered: %s\n",msg);
}
Name.tab.h
包含了语法规则需要的词法声明，即Name.y第一部分的声明内容。
extern int yydebug;
#endif
/* Token type. */
#ifndef YYTOKENTYPE
# define YYTOKENTYPE
enum yytokentype
{
NAME = 258,
EQ = 259,
AGE = 260
};
#endif
/* Value type. */
#if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED
typedef char * YYSTYPE;
# define YYSTYPE_IS_TRIVIAL 1
# define YYSTYPE_IS_DECLARED 1
#endif
extern YYSTYPE yylval;
int yyparse (void);
build.sh
bison -d Name.y # bison -d 由.y文件产生.tab.c .tab.h
sed -i 's/typedef int YYSTYPE/typedef char * YYSTYPE/g' Name.tab.h #sed -i 's/原字符串/新字符串/' /home/1.txt
flex Name.lex #flex 由.lex文件产生.yy.c文件
cc -o test2 lex.yy.c Name.tab.c #cc为gcc
运行结果
我们从需求由顶向下分析，从main开始：
实际上是main得到输入序列->放到getAST，先被拷贝进scanner，经过自定义的yyparse解析获得expression表达式->evaluate中解析得到值。
int yyparse(SExpression **expression,yyscan_t scanner);
SExpresion *getAST(const char *expr)
{
SExpression *expression;
yyscan_t scanner;
YY_BUFFER_STATE state;
//如果初始化失败则返回
if(yylex_init(&scanner)) return NULL;
//将输入序列复制进语法分析器的扫描器中
state=yy_scan_string(expr,scanner);
//如果解析失败则返回
if(yyparse(&expression,scanner)) return NULL;
//将scanner分配的buffer清除
yy_delete_buffer(state,scanner);
yylex_destroy(scanner);
return expression;
}
int evaluate(SExpression *e)
{
switch (e->type)
{
case eVALUE:
return e->value;
case eMULTIPLY:
return evaluate(e->left)*evaluate(e->right);
case ePLUS:
return evaluate(e->left)+evaluate(e->right);
default:
return 0;
}
}
int main(void)
{
SExpression *e=NULL;
char test[]=" 4 + 2 *10 + 3 * (5 + 1 )";
int result=0;
//将输入序列放到getAST中，经过抽象树处理生成expression
e=getAST(test);
//由评估函数将expression的值得出
result=evaluate(e);
printf("Result of '%s' is %d\n",test,result);
deleteExpression(e);
return 0;
}
expression的定义：
//表达式的操作符类型
typedef enum tagEOperationType
{
eVALUE,
eMULTIPLY,
ePLUS
}EOperationType;
//多么令人熟悉的二叉树
typedef struct tagSExpression
{
EOperationType type;
int value;
struct tagSExpression *left;
struct tagSExpression *right;
}SExpression;
//该表达式节点就一个值
SExpression *createNumber(int value);
//该表达式节点还有左右操作符
SExpression *createOperation(EOperationType type,SExpression *left,SExpression *right);
void deleteExpression(SExpression *b);
现在让我们进入真正进行yyparse的Parser.y
我们希望从词法分析器获得这些终结符：
左圆括号、右圆括号、加号、乘号、数字。
我们希望将这些终结符定义为可左结合：
加号、乘号。
我们将expr定义为非终结符。
我们希望定义这样的语法规则：
%{
#include "Expression.h"
#include "Parser.h"
#include "Lexer.h"
int yyerror(SExpression **Expression,yyscan_t scanner,const char *msg){}
%}
//会被放到defines,output中定义YYSTYPE、YYLTYPE之前
%code requires{
#ifndef YY_TYPEDEF_YY_SCANNER_T
#define YY_TYPEDEF_YY_SCANNER_T
typedef void* yyscan_t;
#endif
}
//将原本的.tab.c / .tab.h改成.c / .h
%output "Parser.c"
%defines "Parser.h"
//将指定所有符号的语义类型
%define api.pure
//lex parse要用到的一些参数
%lex-param {yyscan_t scanner}
%parse-param {SExpression **expression}
%parse-param {yyscan_t scanner}
//指定一个联合类型,不指定名字则是YYSTYPE
%union{
int value;
SExpression *expression;
}
//声明 左结合 的符号类型
%left '+' TOKEN_PLUS
%left '*' TOKEN_MULTIPLY
//声明终结符
%token TOKEN_LPAREN
%token TOKEN_RPAREN
%token TOKEN_PLUS
%token TOKEN_MULTIPLY
//栈类型为联合时，指定有语义值类型的终结符
%token <value> TOKEN_NUMBER
//栈类型为联合时，有语义值类型的非终结符
%type <expression> expr
%%
//yyparse
input:expr {*expression=$1};
expr
// 表达式+表达式
:expr TOKEN_PLUS expr {$$=createOperation(ePLUS,$1,$3);}
//表达式*表达式
|expr TPKON_MULTIPLAY expr {$$=createOperation(eMULTIPLY,$1,$3);}
//（表达式）
|TOKEN_LPAREN expr TOKEN_RPAREN {$$=$2;}
//值
|TOKEN_NUMBER{$$=createNumber($1);}
;
%%
有了语法规则，需要对终结符的词法规则进行定义，进入Lexer.l
我们将左圆括号、右圆括号、加号、乘号、数字分别进行匹配定义。（注意空白我们也有进行匹配定义，只不过在词法规则中无需返回）
我们在匹配左圆括号、右圆括号、加号、乘号、数字、空白时，加入了触发动作，大多是直接返回，但数字还需要被存储到yytext中，空白无需返回。
%{
#include "Expression.h"
#include "Parser.h"
#include <stdio.h>
%}
%option outfile="Lexer.c" header-file="Lexer.h"
%option warn nodefault
%option reentrant noyywrap never-interactive nounistd
%option bison-bridge
LPAREN "("
RPAPEN ")"
PLUS "+"
MULTIPLY "*"
NUMBER [0-9]+
WS [ \r\n\y]*
%%
{WS} {}
{NUMBER} {sscanf(yytext,"%d",&yylval->value);return TOKEN_NUMBER;}
{MULTIPLY} {return TOKEN_MULTIPLY;}
{PLUS} {return TOKEN_PLUS;}
{LPAREN} {return TOKEN_LPAREN;}
{RPAPEN} {return TOKEN_RPAREN;}
. {}
%%
int yyerror(const char *msg){
fprintf(stderr,"Error:%s\n",msg);return 0;
}
Expression.c main.c是由我们写的。
Lexer.l（Parser.h）通过flex生成Lexer.c。
Parser.y （Lexer.c）通过bison生成Parser.c。
最后Lexer.c Parser.c Expression.c main.c生成test。
#Makefile
#宏定义
FILES = Lexer.c Parser.c Expression.c main.c
CC = g++
CFLAGS = -g -ansi
#待生成文件：需要什么文件\
#生成方式
test: $(FILES)
$(CC) $(CFLAGS) $(FILES) -o test
Lexer.c: Lexer.l
flex Lexer.l
Parser.c: Parser.y Lexer.c
bison Parser.y
clean:
rm -f *.o *~ Lexer.c Lexer.h Parser.c Parser.h test
运行结果
