flex&bison完成C-语言编译器前端（三）

发表于 | 分类于 ， | 阅读数

写在前面

因为自己在学习使用flex&bison编写编译器时，困难很大，网上的资料很老很陈旧，很多示例代码都无法运行。幸而自己最终找到一份07年的博客，所以想对其整理一下。一来加深自己的理解，为学弟学妹提供一份参考资料，二来也能防止原博客丢失。

flex是lex的加强版，同样bison也是yacc的加强版，lex和yacc的语法适用于flex和bison，之后的博客内容将不区分flex和lex，bison和yacc。

本文所有的代码都在kali2019运行测试过，没有linux基础的读者可以安装Ubuntu系列linux，推荐ubuntu16和ubuntu18。

原博客指路

文章代码示例

示例

我们在以前的基础上，深入一步，设计一个简单的计算器，包含+,-,*,/四项操作，且支持()运算符，其中对值可以进行变量保存，并打印出内部的分析信息。

lex文件内容（lexya_b.l）

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
%{

#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;

}

Yacc文件全内容（lexya_b.y）

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
%{

#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");

 /*

 for(i=0;i<=iX;i++)

  printf("%s \n",sBuff[i]);

 */

 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)全内容
ps:该input一定要在linux中编写或使用我写好的。Windows换行符和Linux不一致会导致无法完成词法分析。

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

命令行依次输入下列命令

1
2
3
4
bison -d lexya_b.y
lex lexya_b.l
gcc -g -o parser lex.yy.c lexya_b.tab.c
./parser < input

运行截图

test

文中成功了使用了变量，并且操作符运算优先级也没有问题。其实细看过flex&bison完成C-语言编译器前端（二）一文后，理解上面的例子就很轻松了。这里只是做了一些扩充变化：
1.增加了全局数组sMem来存放变量，不过变量名有限制，只支持单字符。
2.增加了全局数组sBuff存放分析过的语句
3.增加debuginfo打印堆栈信息
4.增加printinfo打印目前的分析语句
要进行内部分析，就需要剖析生成的c文件，对程序(parser)进行跟踪调试。(注：Lex编译时加上d参数，会在程序解释时输出详细的调试信息。如：lex -d lexya_b.l)
通过本示例再加上实际对lexya_b.tab.c的分析理解，会对lex，yacc理论有更进一步的理解。

增加支持的变量字符数

上面的例子只支持单字符的变量，想支持多字符，需要定义一全局变量如：

1
2
3
4
struct varIndex {
  int iValue;
  char sMark[10];
};

同时打印信息加入对变量的显示，下面列出全部文件内容，比较简单，不再附加说明。

userdef.h

1
2
3
4
5
6
7
typedef struct
{
    int iValue;
    char sMark[10];
} varIndex;

varIndex strMem[256];

example2.l

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
%{
  #include <stdlib.h>
  #include <string.h>
  #include "userdef.h"
  #include "example.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;
}

example2.y

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 %{
  #include <stdlib.h>
  #include <stdio.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");
   /*
   for(i=0;i<=iBuffX;i++)
    printf("%s \n",sBuff[i]);
   */

   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;
}

最后

这个系列打算就记载到这里了，剩余的内容读者可以访问原博客。