前言

它是如何工作的？下面一一分析。

概要

文件列表

total 167
-rw-r--r-- 1 lij25 1049089 28536 11月  8 19:24 calc
-rw-r--r-- 1 lij25 1049089   433 11月  8 19:10 calc.l
-rw-r--r-- 1 lij25 1049089   707 11月  8 18:33 calc.y
-rw-r--r-- 1 lij25 1049089 45039 11月  8 19:24 lex.yy.c
-rw-r--r-- 1 lij25 1049089 25224 11月  8 19:24 lex.yy.o
-rw-r--r-- 1 lij25 1049089   419 11月  8 19:24 makefile
-rw-r--r-- 1 lij25 1049089  3393 11月  8 19:24 y.output
-rw-r--r-- 1 lij25 1049089 44845 11月  8 19:24 y.tab.c
-rw-r--r-- 1 lij25 1049089  2282 11月  8 19:24 y.tab.h
-rw-r--r-- 1 lij25 1049089 11688 11月  8 19:24 y.tab.o

calc:计算器应用程序
calc.l:计算器词法分析规则
calc.y:计算器语法分析规则
lex.yy.c:计算器语法分析源码
lex.yy.o:计算器语法分析object
makefile:编译规则
y.output: 计算器语法分析输出
y.tab.c: 计算器语法分析源码
y.tab.h:计算器语法分析源码引入文件
y.tab.o:计算器语法分析object

编译命令

bison -vdty calc.y
gcc -c y.tab.c
flex calc.l
gcc -c lex.yy.c
gcc -o calc y.tab.o lex.yy.o -lfl

bison -vdty calc.y
根据语法规则生成文件：y.output，y.tab.c和y.tab.h
gcc -c y.tab.c
将y.tab.c编译成y.tab.o目标文件
flex calc.l
根据词法规则生成文件：lex.yy.c（词法分析器）
gcc -c lex.yy.c
将lex.yy.c编译成lex.yy.o目标文件
gcc -o calc y.tab.o lex.yy.o -lfl
将y.tab.o和lex.yy.o编译成calc应用程序

calc.y（词法分析）

%{
#include <stdio.h>
int yyerror(char *s);
int yylex();
%}

%define api.value.type {int}

%token NUM 256
%token ADD 257
%token SUB 258
%token MUL 259
%token DIV 260
%token LP 261
%token RP 262
%token EOL 263

%%
cmd:
    | cmd expr EOL {printf("=%d\n>",$2);}

expr: term
    | expr ADD term {$$ = $1 + $3;}
    | expr SUB term {$$ = $1 - $3;}
    ;

term: factor {$$ = $1;}
    | term MUL factor {$$ = $1 * $3;}
    | term DIV factor {$$ = $1 / $3;}
    ;

factor: NUM {$$ = $1;}
    | LP expr RP {$$ = $2;}
    ;
%%

int main(){
    printf("> ");
    yyparse();
    return 0;
}

int yyerror(char *s){
    fprintf(stderr ,"parser error:%s\n",s);
    return 0;
}

%{
#include <stdio.h>
int yyerror(char *s);
int yylex();
%}

这个是头定义，就是C语言的头定义

%define api.value.type {int}
%token NUM 256
%token ADD 257
%token SUB 258
%token MUL 259
%token DIV 260
%token LP 261
%token RP 262
%token EOL 263

常量定义

%token 标示定义枚举值C语言转化

/* Token type.  */
#ifndef YYTOKENTYPE
# define YYTOKENTYPE
  enum yytokentype
  {
    NUM = 256,
    ADD = 257,
    SUB = 258,
    MUL = 259,
    DIV = 260,
    LP = 261,
    RP = 262,
    EOL = 263
  };
#endif
/* Tokens.  */
#define NUM 256
#define ADD 257
#define SUB 258
#define MUL 259
#define DIV 260
#define LP 261
#define RP 262
#define EOL 263

这一些常量定义是给词法解析器来解析文本输入转化为token输出。

声明：用途

%define api.value.type {类型}：指定所有符号的语义值类型
%define api.pure full：生成可重入的解析器
%union 名字 {成员声明}：声明一个联合类型，不指定名字则YYSTYPE
%require "版本"：若bison版本低于指定版本则报错退出
%token 符号：声明一个终结符，可后接有双引号形式的字面标记
%token <类型> 符号：在栈类型为联合时，声明一个有给定语义值类型的终结符，可后接有双引号形式的字面标记
%left 符号…：声明一些左结合符号
%left <类型> 符号…：在栈类型为联合时，声明一个有给定语义值类型的左结合符号
%right 符号…：声明一些右结合符号
%right <类型> 符号…：在栈类型为联合时，声明一个有给定语义值类型的右结合符号
%nonassoc 符号…：声明一些不结合符号
%nonassoc <类型> 符号…：在栈类型为联合时，声明一个有给定语义值类型的不结合符号
%precedence 符号…：声明一些有相同优先级的符号，较后的声明对应较高的优先级
%precedence <类型> 符号…：在栈类型为联合时，声明一个有给定语义值类型的有相同优先级的符号，较后的声明对应较高的优先级
%type <类型> 非终结符…：在栈类型为联合时，声明一些有特定语义值类型的非终结符
%initial-action { C代码 }：在开始解析前运行指定的C代码，其中可用$$和@$引用向前看符号的初始值和位置。
%destructor { C代码 } 符号…：在不再需要指定符号（或语义值类型）的语义值时运行指定的C代码。其中$$和@$分别引用有关语义值和其位置。
%printer { C代码 } 符号…：在调试模式中报告指定符号时运行指定代码，其中yyoutput、$$和@$分别引用输出流、有关语义值和其位置。
%expect N：预期有N个移入-归约冲突而没有归约-归约冲突，不用警告。
%expect-rr N：预期有N个归约-归约冲突（用GLR解析器），不用警告。
%start 符号：指定开始符号
%code {代码}：把给定代码原样复制到解析器
%code 位置 {代码}：把给定代码原样复制到解析器中指定位置（requires（包含头文件的位置）、provides（头文件中）、top（包含头文件的位置与解析器之间）、imports）
%file-prefix "前缀"：指定输出文件名对应输入文件名前缀.y
%output "文件"：指定输出文件
%language "语言"：指定生成解析器的语言（C/C++/Java）
%name-prefix "前缀"：为外部可用名字加给定前缀而非yy
%skeleton "文件"：指定基于的骨架
%verbose：生成更多信息

语法规则

%%
cmd:
    | cmd expr EOL {printf("=%d\n>",$2);}

expr: term
    | expr ADD term {$$ = $1 + $3;}
    | expr SUB term {$$ = $1 - $3;}
    ;

term: factor {$$ = $1;}
    | term MUL factor {$$ = $1 * $3;}
    | term DIV factor {$$ = $1 / $3;}
    ;

factor: NUM {$$ = $1;}
    | LP expr RP {$$ = $2;}
    ;
%%

这个是实现 1 + 1 +5 * 6 等复杂语法的重中之重，语法分析也分为自顶向下和自底向上两种，文本输入就像是一条从左向右的一条绳子，左边是顶，右边是底，分析它是一个非常复杂的过程，涉及的算法很多，我就不献丑说明了，分析语法就像是句子断句例如如下

1 + 1
one plus one
一加一
1 + 1 - 2
one plus one and then minus two
一加一再减二
计算机的表示其实是对现实的表示，上面的语法规则就是对句子的描述和定义，分析结果如下
factor：表示的成分类型有NUM或（ expr ）两种，例如1或(1)或(1+1)或(1+1-2)等等类似的成分，这个是最高优先级，为啥，因为在最下面
term：是表示factor或term MUL factor或term DIV factor 乘除，例如1 * 3或2/2 或者(2+3)/3等等，这个是次优先级
expr：是表示expr或expr MUL term或expr DIV term乘除，例如1 + 3或2 - 2 或者(2*3) - 3等等，这个是再次优先级
cmd：只是一个循环根据EOL断句，就像每个句子以。结尾

C语言代码

int main(){
    printf("> ");
    yyparse();
    return 0;
}

int yyerror(char *s){
    fprintf(stderr ,"parser error:%s\n",s);
    return 0;
}

代码只是定义运行启动主函数和错误处理，没有其他特别。

calc.l（词法分析）

%{
#include "y.tab.h"
int lexerror(char *s);
%}
%%
"+"         {return ADD;}
"-"         {return SUB;}
"*"         {return MUL;}
"/"         {return DIV;}
"("         {return LP;}
")"         {return RP;}
[0-9]+      {yylval = atoi(yytext);return NUM;}
\n          {return EOL;}
[ \t]       {}
.           {lexerror(yytext);}
%%

int lexerror(char *s){
    fprintf(stderr ,"lexical error:%s\n",s);
    return 0;
}

这个之前分析过，将文本输入切割成token,然后交给语法分析器来分析处理。