- 文法分析用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;
char sIndex;
nodeType *nPtr;
};
则生成的头文件中的内容是：
typedef union
{
int iValue;
char sIndex;
nodeType *nPtr;
} 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 执行 文件
小结
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。
简单计算器
%{
#include <stdlib.h>
void yyerror(char *);
#include "lexya_a.tab.h"
%}
%%
[0-9]+ { yylval = atoi(yytext); return INTEGER; }
[-+*/\n] return *yytext;
[/t] ;
. yyerror("无效字符");
%%
int yywrap(void) {
return 1;
}
%{
#include <stdlib.h>
include <stdio.h>
int yylex(void);
void yyerror(char *);
%}
%token INTEGER
%left ‘+’ ‘-‘
%left ‘*’ ‘/’
%%
program:
program expr ‘\n’ { printf(“%d\n”, $2); }
|
;
expr:
INTEGER {
</span> = <span class="hljs-variable">$1</span>; }
| expr <span class="hljs-string">'*'</span> expr { <span class="hljs-variable">
=
$1; }
| expr
'*' expr {
</span> = <span class="hljs-variable">1</span>∗<spanclass="hljs−variable"> *
3</span>; }
| expr <span class="hljs-string">'/'</span> expr { <span class="hljs-variable"></span> = <span class="hljs-variable">$1</span> / <span class="hljs-variable">$3</span>; }
| expr <span class="hljs-string">'+'</span> expr { <span class="hljs-variable">
=
$1 /
$3; }
| expr
'+' expr {
</span> = <span class="hljs-variable">1</span>+<spanclass="hljs−variable"> +
3</span>; }
| expr <span class="hljs-string">'-'</span> expr { <span class="hljs-variable">$$ =
1</span>−<spanclass="hljs−variable"> -
3; }
;
%%
void yyerror(char
*s) {
printf(
“%s\n”, s);
}
int main(void) {
yyparse();
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 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
包含+,-,*,/四项操作，且支持()运算符，其中对值可以进行变量保存，并打印出内部的分析信息。
%{
#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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
%{
#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[$<span class="hljs-number">1</span>]=$3; }
| statement '\n' { printf("--------------------------------\n\n"); }
;
expr:
INT { debuginfo("INT",yyvsp,"0"); $$ = $<span class="hljs-number">1</span>; }
| VAR { debuginfo(<span class="hljs-string">"VAR"</span>,yyvsp,<span class="hljs-string">"1"</span>); $$ = sMem[$<span class="hljs-number">1</span>]; }
| expr <span class="hljs-string">'*'</span> expr { debuginfo(<span class="hljs-string">"*"</span>,yyvsp,<span class="hljs-string">"010"</span>); $$ = $<span class="hljs-number">1</span> * $<span class="hljs-number">3</span>; }
| expr <span class="hljs-string">'/'</span> expr { debuginfo(<span class="hljs-string">"/"</span>,yyvsp,<span class="hljs-string">"010"</span>); $$ = $<span class="hljs-number">1</span> / $<span class="hljs-number">3</span>; }
| expr <span class="hljs-string">'+'</span> expr { debuginfo(<span class="hljs-string">"+"</span>,yyvsp,<span class="hljs-string">"010"</span>); $$ = $<span class="hljs-number">1</span> + $<span class="hljs-number">3</span>; }
| expr <span class="hljs-string">'-'</span> expr { debuginfo(<span class="hljs-string">"-"</span>,yyvsp,<span class="hljs-string">"010"</span>); $$ = $<span class="hljs-number">1</span> - $<span class="hljs-number">3</span>; }
| <span class="hljs-string">'('</span> expr <span class="hljs-string">')'</span> { debuginfo(<span class="hljs-string">"()"</span>,yyvsp,<span class="hljs-string">"101"</span>); $$ = $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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
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理论有更进一步的理解。
增加支持的变量字符数
typedef struct {
int iValue;
char sMark[10];
} varIndex;
varIndex strMem[256];
%{
#include <stdlib.h>
#include "userdef.h"
#include "lexya_c.tab.h"
void yyerror(char *);
void add_buff(char *);
void add_var(char *);
extern char sBuff[10][20];
extern int iBuffX;
extern int iBuffY;
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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
%{
#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[$<span class="hljs-number">1</span>].iValue=$3; }
| statement '\n' { printf("--------------------------------\n\n"); }
;
expr:
INT { debug_info("INT",yyvsp,"0"); $$ = $<span class="hljs-number">1</span>; }
| VAR { debug_info(<span class="hljs-string">"VAR"</span>,yyvsp,<span class="hljs-string">"2"</span>); $$ = strMem[$<span class="hljs-number">1</span>].iValue; }
| expr <span class="hljs-string">'*'</span> expr { debug_info(<span class="hljs-string">"*"</span>,yyvsp,<span class="hljs-string">"010"</span>); $$ = $<span class="hljs-number">1</span> * $<span class="hljs-number">3</span>; }
| expr <span class="hljs-string">'/'</span> expr { debug_info(<span class="hljs-string">"/"</span>,yyvsp,<span class="hljs-string">"010"</span>); $$ = $<span class="hljs-number">1</span> / $<span class="hljs-number">3</span>; }
| expr <span class="hljs-string">'+'</span> expr { debug_info(<span class="hljs-string">"+"</span>,yyvsp,<span class="hljs-string">"010"</span>); $$ = $<span class="hljs-number">1</span> + $<span class="hljs-number">3</span>; }
| expr <span class="hljs-string">'-'</span> expr { debug_info(<span class="hljs-string">"-"</span>,yyvsp,<span class="hljs-string">"010"</span>); $$ = $<span class="hljs-number">1</span> - $<span class="hljs-number">3</span>; }
| <span class="hljs-string">'('</span> expr <span class="hljs-string">')'</span> { debug_info(<span class="hljs-string">"()"</span>,yyvsp,<span class="hljs-string">"101"</span>); $$ = $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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
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） 同出（规约）
