lex(flex)&yacc(bison)

唐宇定

2023-12-01

初始配置

文法分析用Flex(Lex):将数据分隔成一个个的标记token (标示符identifiers，关键字keywords，数字numbers, 中括号brackets, 大括号braces, 等等etc.)
语法分析用Bison(Yacc): 在分析标记的时候生成抽象语法树. Bison 将会做掉几乎所有的这些工作, 我们定义好我们的抽象语法树就OK了.
组装用LLVM: 这里我们将遍历我们的抽象语法树，并未每一个节点生成字节/机器码。这听起来似乎很疯狂，但是这几乎就是最简单的一步了.
sudo apt-get install flex bison
flex -h && bison -h 进行测试
cd ~/shellscript/bin
gedit lexya
将执行后面每一个例子时一连串的命令放进去
chmod u+x lexya 就像下面这样
～/shellscript/bin/lexya 针对草木鱼（四五六七）和汇编版本的一个脚本

flex&yacc 相关知识

flex&yacc IBM1
yacc 基本用法－矮油

flex

所使用的语法是普通而古老的正则表达式语法。有一些扩展。其中一个扩展是，您可以为通用的模式命名。
您可以在 lex 程序的第一部分中第一个 %% 之前为其中的一部分定义名称：

DIGIT [0-9]
ALPHA [a-zA-Z]
ALNUM [0-9a-zA-Z]
IDENT [0-9a-zA-Z_]
然后，您可以在规则部分将其名称放置在大括号内来反向引用它们：
({ALPHA}|_){IDENT}* { return IDENTIFIER; }

yacc

有关　union 标志（token）绑定到YYSTYPE的某个域 nonassoc

yacc 基本用法－矮油

union 标志（token）绑定到YYSTYPE的某个域

对于操作符，可以定义%left和%right：%left表示左相关（left-associative），%right表示右相关（right-associative）。可以定义多组%left或%right，在后面定义的组有更高的优先级。如：

%left ‘+’ ‘-‘
%left ‘*’ ‘/’
上面定义的乘法和除法比加法和减法有更高的优先级。

改变YYSTYPE的类型。如这样定义TTSTYPE：

%union
{
     int iValue; /* integer value */
     char sIndex; /* symbol table index */
     nodeType *nPtr; /* node pointer */
};

则生成的头文件中的内容是：

typedef union
{
     int iValue;      /* integer value */
     char sIndex;    /* symbol table index */
     nodeType *nPtr; /* node pointer */
} YYSTYPE;
extern YYSTYPE yylval;

可以把标志（token）绑定到YYSTYPE的某个域。如：

%token <iValue> INTEGER
%type <nPtr> expr

把expr绑定到nPtr，把INTEGER绑定到iValue。yacc处理时会做转换。如：

expr: INTEGER { $$ = con($1); }
转换结果为：
yylval.nPtr = con(yyvsp[0].iValue);
其中yyvsp[0]是值栈（value stack）当前的头部。

Bison中默认将所有的语义值都定义为int类型，可以通过定义宏YYSTYPE来改变值的类型。如果有多个值类型，则需要通过在Bison声明中使用%union列举出所有的类型
，然后为每个符号定义相对的类型，终结符使用%token，非终结符使用%type来定义。

nonassoc

定义一元减号符有更高的优先级的方法：

%left GE LE EQ NE '>' '<'
%left '+' '-'
%left '*'
%nonassoc UMINUS

%nonassoc的含义是没有结合性。它一般与%prec结合使用表示该操作有同样的优先级。如：
expr: ‘-’ expr %prec UMINUS { $$ = node(UMINUS, 1, $2); }
表示该操作的优先级与UMINUS相同，在上面的定义中，UMINUS的优先级高于其他操作符，所以该操作的优先级也高于其他操作符计算。

.c和 .h 的关系

点击 .c与.h联系区别
因为 #include “xx.h” 这个宏其实际意思就是把当前这一行删掉，把 xx.h 中的内容原封不动的插入在当前行的位置。
由于想写这些函数声明的地方非常多（每一个调用 xx.c 中函数的地方，都要在使用前声明一下子），所以用 #include “xx.h”
这个宏就简化了许多行代码——让预处理器自己替换好了。也就是说，xx.h 其实只是让需要写 xx.c 中函数声明的地方调用（可以少写几行字），
至于 include 这个 .h 文件是谁，是 .h 还是 .c，还是与这个 .h 同名的 .c，都没有任何必然关系。
编译器不会自动把 .h 文件里面的东西跟同名的.c文件绑定在一起
在编译阶段只是生成各自的.o文件.这个阶段不和其它的文件发生任何的关系. 而include这个预处理指令发生在预处理阶段(早先编译阶段,只是编译器的一个前驱处理程序).

安装

sudo apt-get install flex bison LLVM

yacc & flex

yacc，flex快速入门
 点击　一系列　yacc, flex

flex 的使用

点击 Lex和Yacc应用方法(一).初识Lex
exfirst.l 存 flex 型的文件

%{
#include "stdio.h"
%}
%%
[\n]                  ;
[0-9]+                printf("Int     : %s\n",yytext);
[0-9]*\.[0-9]+        printf("Float   : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]*  printf("Var     : %s\n",yytext);
[\+\-\*\/\%]          printf("Op      : %s\n",yytext);
.                     printf("Unknown : %c\n",yytext[0]);
%%

在命令行下执行命令flex解析，会自动生成lex.yy.c文件：

flex exfirst.l
或
flex -o a.c exfirst.l
进行编译生成parser可执行程序：
cc -o parser lex.yy.c -ll
或
cc lex.yy.c -o parser -ll
或
$ gcc -o a a.c -ll
[注意：如果不加-ll链结选项，cc编译时会出现错误。当编译时不带-ll选项时，是必须加入main函数和yywrap]

file.txt 存自己的定义的语言程序

title
i=1+3.9;
a3=909/6
bcd=4%9-333

用 a 执行文件

$ ./a < file.txt

小结
1.定义Lex描述文件
2.通过lex，flex工具解析成lex.yy.c文件（a.c）
3.使用cc编译lex.yy.c(a.c)生成可执行程序a

yacc 的使用

点击 Lex和Yacc应用方法(二).再识

“移进-归约”冲突(shift-reduce conflict) ,在yacc中产生这种冲突时，会继续移进。
“归约-归约”冲突
YYSTYPE 定义了用来将值从 lexer 拷贝到解析器或者 Yacc 的 yylval （另一个 Yacc 变量）的类型。默认的类型是 int。

简单计算器　

lexya_a.l

%{　　　　　　　//C 和 Lex 的全局声明
#include <stdlib.h>
void yyerror(char *);
#include "lexya_a.tab.h"
%}
%%       //标记声明, 包括模式（C 代码）
[0-9]+       { yylval = atoi(yytext); return INTEGER; }
[-+*/\n]     return *yytext;
/*向yacc的分析栈返回运算符标记，系统保留的0-255此时便有了作用，内容栈为空。*/
[/t]         ;/* 去除空格 */
.            yyerror("无效字符");
%%       //补充的Ｃ函数
int yywrap(void) {
  return 1;
}

lexya_a.y

%{  //定义段，引用，C 与 Yacc 的声明
#include <stdlib.h>
#include <stdio.h>
int yylex(void);　　//yylex的返回值类型是整型，可以用于返回标记。
void yyerror(char *);
%}      //预定义，
%token INTEGER　　　//终结符（中的一种－命名标记: 这些由 %token 标识符来定义）
%left '+' '-'
%left '*' '/'    //最后列出的定义拥有最高的优先权
%%
program:
program expr '\n' { printf("%d\n", $2); }
|
; /* 先理解expr，再递归理解program。首先program可以为空，也可以用单单的expr加下“/n”回车符组成，结合起来看program定义的就是多个表达式组成的文件内容 */
expr:
INTEGER { $$ = $1; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr { $$ = $1 / $3; }
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
; /* 可以由单个INTEGER值组成，也可以有多个INTERGER和运算符组合组成。以表达式“1+4/2*3-0”为例，1 4 2 3 都是expr，就是expr+expr/expr*expr-expr说到底最后还是个expr。递归思想正好与之相反，逆推下去会发现expr这个规则标记能表示所有的数值运算表达式 */
%%
void yyerror(char *s) {
  printf("%s\n", s);
}
int main(void) {
  yyparse();
  return 0;
}

bison -d lexya_a.y 参数 -d 将头文件和.c文件分离
lex lexya_a.l
cc -o parser *.c
./parser 输入计算式，回车会显示运行结果
bison -d lexya_a.y 编译后会产生 lexya_a.tab.c lexya_a.tab.h
lex文件lexya_a.l中头声明已包括了 lexya_a.tab.h。这两个文件是典型的互相协作的示例
详细分析见草木瓜系列的第二篇

计算器升级版 ()运算符变量保存 lex && yacc

包含+,-,*,/四项操作，且支持()运算符，其中对值可以进行变量保存，并打印出内部的分析信息。

lexya_b.l

%{
#include <stdlib.h>
#include "lexya_b.tab.h"
void yyerror(char *);
void add_buff(char *);
extern char sBuff[10][20];
extern int iX;
extern int iY;
%}
%%
[a-z]         { yylval = *yytext; add_buff(yytext); return VAR; }
[0-9]+        { yylval = atoi(yytext); add_buff(yytext); return INT; }
[-+()=*/]     { yylval = *yytext; add_buff(yytext); return *yytext; }
[\n]          { yylval = *yytext; iY=0;iX++; return *yytext; }
[\t]          ;
.             yyerror("无效字符");
%%
void add_buff(char * buff) {
    sBuff[iX][iY]=*buff; iY++;
}
int yywrap(void) {
    return 1;
}

lexya_b.y

%{
#include <stdlib.h>
int yylex(void);
void yyerror(char *);
void debuginfo(char *, int *, char *);      //打印堆栈信息
void printinfo();   //打印目前的分析语句
int sMem[256];       //来存放变量
char sBuff[10][20]={0};     //存放分析过的语句
int iX=0;
int iY=0;
%}
%token INT VAR
%left '+' '-'
%left '*' '/'
%%
program:
program statement
|
;
statement:
expr { printf("%d\n",$1); }
| VAR '=' expr { debuginfo("=",yyvsp,"110"); sMem[$1]=$3; }
| statement '\n' { printf("--------------------------------\n\n"); }
;
expr:
INT { debuginfo("INT",yyvsp,"0"); $$ = $1; }
| VAR { debuginfo("VAR",yyvsp,"1"); $$ = sMem[$1]; }
| expr '*' expr { debuginfo("*",yyvsp,"010"); $$ = $1 * $3; }
| expr '/' expr { debuginfo("/",yyvsp,"010"); $$ = $1 / $3; }
| expr '+' expr { debuginfo("+",yyvsp,"010"); $$ = $1 + $3; }
| expr '-' expr { debuginfo("-",yyvsp,"010"); $$ = $1 - $3; }
| '(' expr ')'   { debuginfo("()",yyvsp,"101"); $$ = $2; }
;
%%
void debuginfo(char * info,int * vsp, char * mark) {
    printf("--RULE: %s \n", info);
    int i=0;
    int ilen=strlen(mark);
    for(i=0;i>=1-ilen;i--) {
    if(mark[ilen+i-1]=='1')
        printf("$%d %d %c \n", i+ilen, vsp[i], vsp[i]);
    else
        printf("$%d %d \n", i+ilen, vsp[i]);
    }
    printinfo();
}
void printinfo() {
    int i=0;
    printf("--STATEMENT: \n");

    if(iY==0)
        printf("%s \n",sBuff[iX-1]);
    else
        printf("%s \n",sBuff[iX]);
    printf("\n");
}
void yyerror(char *s) {
    printf("%s\n", s);
}
int main(void) {
    yyparse();
    return 0;
}

input

a=4+2*(3-2-1)+6
b=1-10/(6+4)+8
c=a-b
a
b
c

这里只是做了一些扩充变化：
1.增加了全局数组sMem来存放变量，不过变量名有限制，只支持单字符。
2.增加了全局数组sBuff存放分析过的语句
3.增加debuginfo打印堆栈信息
4.增加printinfo打印目前的分析语句
要进行内部分析，就需要剖析生成的c文件，对程序(parser)进行跟踪调试。
(注：Lex编译时加上d参数，会在程序解释时输出详细的调试信息。如：lex -d lexya_$1.l)
通过本示例再加上实际对lexya_b.tab.c的分析理解，会对lex，yacc理论有更进一步的理解。

增加支持的变量字符数

userdef.h

typedef struct {
    int iValue;  //存数值
    char sMark[10];　　//存代表的字符，如aa ,bb
} varIndex;
varIndex strMem[256];　　//字符数组

lexya_c.l

%{
#include <stdlib.h>
#include "userdef.h"
#include "lexya_c.tab.h"

void yyerror(char *);
void add_buff(char *);　　//加入　lex 存放分析过的源代码　
void add_var(char *);

extern char sBuff[10][20];　　　//lex 存放分析过的源代码
extern int iBuffX;  //lex　目前分析到的行数
extern int iBuffY;　　//lex　目前分析到的某行第几个

extern varIndex strMem[256];
extern int iMaxIndex;　　//当前所有ＶＡＲ的个数
extern int iCurIndex;   //目前字符指针（值）
%}
%%
[a-zA-Z][a-zA-Z0-9]*         { add_var(yytext); yylval = iCurIndex; add_buff(yytext);   return VAR; }
[0-9]+        { yylval = atoi(yytext); add_buff(yytext); return INT;   }
[-+()=*/]     { yylval = *yytext; add_buff(yytext); return *yytext; }
[\n]          { yylval = *yytext; iBuffY=0;iBuffX++; return *yytext; }
[\t]          ;
.             yyerror("无效字符");
%%
void add_buff(char * buff) {
    strcat(sBuff[iBuffX],buff);
    iBuffY+=strlen(buff);
}
void add_var(char *mark) {
    if(iMaxIndex==0){
        strcpy(strMem[0].sMark,mark);
        iMaxIndex++;
        iCurIndex=0;
        return;
    }
    int i;
    for(i=0;i<=iMaxIndex-1;i++) {
        if(strcmp(strMem[i].sMark,mark)==0) {
            iCurIndex=i;
            return;
        }
    }
    strcpy(strMem[iMaxIndex].sMark,mark);
    iCurIndex=iMaxIndex;
    iMaxIndex++;
}
int yywrap(void) {
    return 1;
}

lexya_c.y

%{
#include <stdlib.h>
#include "userdef.h"
int yylex(void);
void yyerror(char *);
void debug_info(char *, int *, char *);
void stm_info();

extern varIndex strMem[256];

int iMaxIndex=0;
int iCurIndex=0;

char sBuff[10][20]={0};
int iBuffX=0;
int iBuffY=0;

%}
%token INT VAR
%left '+' '-'
%left '*' '/'
%%
program:
program statement
|
;
statement:
expr { printf("%d\n",$1); }
| VAR '=' expr { debug_info("=",yyvsp,"210"); strMem[$1].iValue=$3;   }
| statement '\n' { printf("--------------------------------\n\n"); }
;
expr:
INT { debug_info("INT",yyvsp,"0"); $$ = $1;   }
| VAR { debug_info("VAR",yyvsp,"2"); $$ =   strMem[$1].iValue; }
| expr '*' expr { debug_info("*",yyvsp,"010"); $$ = $1 * $3; }
| expr '/' expr { debug_info("/",yyvsp,"010"); $$ = $1 / $3; }
| expr '+' expr { debug_info("+",yyvsp,"010"); $$ = $1 + $3; }
| expr '-' expr { debug_info("-",yyvsp,"010"); $$ = $1 - $3; }
| '(' expr ')'   { debug_info("()",yyvsp,"101"); $$ = $2;      }
;
%%
void debug_info(char * info,int * vsp, char * mark) {
    printf("--RULE: %s \n", info);
    int i=0;
    int ilen=strlen(mark);
    for(i=0;i>=1-ilen;i--) {
        switch(mark[ilen+i-1]){
            case '1':
                printf("$%d %d %c \n", i+ilen, vsp[i], vsp[i]);
                break;
            case '0':
                printf("$%d %d \n", i+ilen, vsp[i]);
                break;
            case '2':
                printf("$%d %s %d\n", i+ilen, strMem[vsp[i]].sMark, strMem[vsp[i]].iValue);
                break;
        }
    }
    stm_info();
}
void stm_info() {
    int i=0;
    printf("--STATEMENT: \n");
    if(iBuffY==0)
        printf("%s \n",sBuff[iBuffX-1]);
    else
        printf("%s \n",sBuff[iBuffX]);
    printf("\n");
}
void yyerror(char *s) {
    printf("%s\n", s);
}
int main(void) {
    yyparse();
    return 0;
}

input

aa=4+2*(3-2-1)+6
bb=1-10/(6+4)+8
cd=aa-bb
aa
bb
cd

bison -d lexya_c.y
lex lexya_c.l
gcc -g -o parser lex.yy.c lexya_c.tab.c 参数-g是调试选项
./parser < input

yyvsp　从内容栈中弹出的东西
yylval　对应内容栈
VAR INT + 之类的对应分析栈
内容栈　分析栈　同进（lex到yacc）同出（规约）

lex(flex)&yacc(bison)

初始配置

flex&yacc 相关知识

flex

yacc

有关　union 标志（token）绑定到YYSTYPE的某个域 nonassoc

union 标志（token）绑定到YYSTYPE的某个域

nonassoc

.c和 .h 的关系

安装

yacc & flex

flex 的使用

yacc 的使用

简单计算器

计算器升级版 ()运算符变量保存 lex && yacc

增加支持的变量字符数

相关阅读

相关文章

相关问答

相关文档

lex(flex)&yacc(bison)

初始配置

flex&yacc 相关知识

flex

yacc

有关 union 标志（token）绑定到YYSTYPE的某个域 nonassoc

union 标志（token）绑定到YYSTYPE的某个域

nonassoc

.c和 .h 的关系

安装

yacc & flex

flex 的使用

yacc 的使用

简单计算器

计算器升级版 ()运算符 变量保存 lex && yacc

增加支持的变量字符数

相关阅读

相关文章

相关问答

相关文档

有关　union 标志（token）绑定到YYSTYPE的某个域 nonassoc

简单计算器　

计算器升级版 ()运算符变量保存 lex && yacc