lex(flex)yacc(bison)

news/2024/11/24 22:29:12/

初始配置

  • 文法分析用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]);elseprintf("$%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]);elseprintf("%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]);elseprintf("%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） 同出（规约）


http://www.ppmy.cn/news/221518.html

相关文章

Windows下安装lex(flex)与yacc(bison)

Windows下安装lex(flex)与yacc(bison)

上完第一节编译原理&#xff0c;Mr李要求这周自己探索一下lex和yacc这两个工具。 查了一下lex与yacc是两个在Unix下的分别作词法分析和语法分析的工具&#xff0c;都说很强大。而他俩在linux下又有对应的东西叫flex与bison。虽然硬盘上装了ubuntu但是不怎么用&#xff0c;linu…
阅读更多...
ElasticSearch7.X和ElasticSearch8.X学习记录

ElasticSearch7.X和ElasticSearch8.X学习记录

ElasticSearch7 倒排索引 数据写入时&#xff0c;建立关键字和主键的映射&#xff0c;查询时–>关键字–>主键–>对应文章 分片 因为ES是以检索为主的产物&#xff0c;为了便于查询&#xff0c;会将数据进行分片&#xff0c;例如:根据性别分片&#xff0c;当查询女…
阅读更多...
【ESXi 7.x内部升级】ESXi 升级 —— 小版本升级（7.X或8.X版本内升级）

【ESXi 7.x内部升级】ESXi 升级 —— 小版本升级（7.X或8.X版本内升级）

目录 4. 小版本升级&#xff08;7.X或8.X版本内升级&#xff09;4.1 示例 — 使用 vSphere Lifecycle Manager升级 ESXi目标&#xff1a;将 VMware ESXi 7.0 U2e 升级为 7.0 U3f&#xff08;1&#xff09;在vSphere Client 中查看需要升级的 ESXi 版本&#xff08;2&#xff09…
阅读更多...
如何使用lex

如何使用lex

第一次在blog上粘代码时觉得很郁闷&#xff0c;缩进变得很短&#xff0c;关键字也没有颜色变化&#xff08;当然这么简单的用复制粘贴也只能是这种效果&#xff09;后来自己用c#做了个小程序&#xff0c;用来在代码里贴上html标签。折腾里一个晚上&#xff0c;费了不少劲。第二…
阅读更多...
yylex使用

yylex使用

%{#include <stdio.h>#include <stdlib.h>int num_num 0;int num_id 0; %} INTEGER [-]?[1-9][0-9]* ID [a-zA-Z][a-zA-Z_0-9]* SPACE [ \n\t] %% {INTEGER} { num_num;printf("(num %d)\n", atoi(yytext));/*打印数字值*//*数字数加一*/ }{ID} { nu…
阅读更多...
【ESXi 7.x 升 8.x】ESXi 升级 —— 使用 ESXCLI 升级 ESXi（Offline Bundle ZIP）

【ESXi 7.x 升 8.x】ESXi 升级 —— 使用 ESXCLI 升级 ESXi（Offline Bundle ZIP）

目录 3. 大版本升级 6.X 升级至 7.X3.1 示例 — 使用 ESXCLI 升级 ESXi&#xff08;Offline Bundle ZIP&#xff09;【目标&#xff1a;将 ESXi 6.5 U2 GA 升级为 7.0 U3f】&#xff08;1&#xff09;下载离线升级ZIP包&#xff08;2&#xff09;升级 ESXi① 查看离线包② 升级…
阅读更多...
Lex 入门

Lex 入门

Lex 入门 First! lex程序的结构是这样的&#xff01; 定义 %% 规则 %% 用户代码 一个 Lex 程序分为三个段&#xff1a;第一段是 C 和 Lex 的全局声明&#xff0c;第二段包括模式&#xff08;C 代码&#xff09;&#xff0c;第三段是补充的 C 函数。 这些段以%%来分界。 下面是一…
阅读更多...
LEX 教程

LEX 教程

LEX简介 LEX是LEXical compiler 的缩写&#xff0c;是UNIX环境下非常著名的工具软件&#xff0c;其主要功能是根据LEX源程序生成一个用C语言描述的词法分析程序(scanner)。 LEX源程序是词法分析程序的规格说明文件&#xff0c;文件名约定为lex.l&#xff0c;经过LEX编译程序的…
阅读更多...
最新文章

Copyright @ 2022~2023