c代码转成中间代码（Flex和Bison）实践
2021-09-20 本文已影响0人
谭英智
流行编译架构
目前流行的编译框架一般分为Front-end和Back-end。
Front-end负责把代码转换成统一格式的中间代码
Back-end负责把中间代码进行优化和转成特定硬件平台的可执行代码。
Front-end针对各个程序的特点制定词法分析和语法分析，目前流行的有clang和llvm-gcc来作为来作为前端的制导工具
Back-end使用流行的llvm来做编译优化和生成机器代码
架构如下：
bison-overview
Flex/Bison
本文主要关注在前端的技术。
Flex是用来做词法分析的
Bison是用来做语法分析的
通过使用Flex和Bison，可以更好的理解编译的前端技术，而不是黑盒的使用clang这些框架
而且通过Flex和bison，可以按自己的想法，创建出自定义的计算机语言。
词法分析
通过分词和识别文法，把程序中的词都独立识别出来。例如识别出是变量还是常量等
识别技术
通过正则文法来识别
构造正则文法 -> NFA -> DFA -> Min DFA
- 正则文法是人类可以容易识别的语言
- NFA是把正则文法转化成一个有穷状态机
- NFA中的状态转换由于不是唯一的，导致程序来实现NFA时，需要回溯，而回溯往往会导致计算低效，因此需要有NFA转换未DFA的技术
- DFA可以避免回溯，但是一般有NFA转换来的DFA不一定是最简的，因此需要通过剪枝、合并等技术，最小化DFA，使得程序计算更加高效
语法分析
基于词法分析的结果，识别出特定模式的语法，并构造出语法树，便于输出中间代码和进一步分析语义。
识别技术
通过上下文无关文法，通过LL/LR/LR(1)/LR(N)技术，构造出语法树
- LL语法通过最左匹配，构造语法树。它不允许有左递归的文法，不允许下个token可以匹配两个不同状态的语法，它是自顶向下的上下文无关文法
- LR语法通过最右匹配，构造语法树，它不允许右递归的文法，不允许上个token可以匹配两个不同状态的语法，它是自底向上的上下文无关的文法
- LR(1)/LR(N)语法通过向右多看一个token，来实现更加松散的文法识别规则。这是由于LL/LR文法规定的太严格，导致代码语法都很难定义出来，而LR(1)文法没那么严格，实践表明，LR(1)文法可以满足现代的大部分的计算机高级语言的文法
正则文法与上下文无关文法的对比
为什么正则文法不能用来实现语法分析？
这是因为正则文法对token的计数问题束手无策。例如如果要识别一个有效的括号对。正则文法则无法实现，因为它没有栈的功能。而上下文无关的文法，则可以轻松的实现。
Flex实现c子集的词法分析
Flex工具，可以通过程序员指定正则文法，flex就可以进行词法分析
新建token.h
#ifndef TOKEN_H
#define TOKEN_H
typedef enum {
T_Le = 256, T_Ge, T_Eq, T_Ne, T_And, T_Or, T_IntConstant,
T_StringConstant, T_Identifier, T_Void, T_Int, T_While,
T_If, T_Else, T_Return, T_Break, T_Continue, T_Print,
T_ReadInt
} TokenType;
static void print_token(int token) {
static char* token_strs[] = {
"T_Le", "T_Ge", "T_Eq", "T_Ne", "T_And", "T_Or", "T_IntConstant",
"T_StringConstant", "T_Identifier", "T_Void", "T_Int", "T_While",
"T_If", "T_Else", "T_Return", "T_Break", "T_Continue", "T_Print",
"T_ReadInt"
};
if (token < 256) {
printf("%-20c", token);
} else {
printf("%-20s", token_strs[token-256]);
}
}
#endif
新建正则文法规则文件word-spliter.l
%{
#include "token.h"
int cur_line_num = 1;
void init_scanner();
void lex_error(char* msg, int line);
%}
/* Definitions, note: \042 is '"' */
INTEGER ([0-9]+)
UNTERM_STRING (\042[^\042\n]*)
STRING (\042[^\042\n]*\042)
IDENTIFIER ([_a-zA-Z][_a-zA-Z0-9]*)
OPERATOR ([+*-/%=,;!<>(){}])
SINGLE_COMMENT1 ("//"[^\n]*)
SINGLE_COMMENT2 ("#"[^\n]*)
%%
[\n] { cur_line_num++; }
[ \t\r\a]+ { /* ignore all spaces */ }
{SINGLE_COMMENT1} { /* skip for single line comment */ }
{SINGLE_COMMENT2} { /* skip for single line commnet */ }
{OPERATOR} { return yytext[0]; }
"<=" { return T_Le; }
">=" { return T_Ge; }
"==" { return T_Eq; }
"!=" { return T_Ne; }
"&&" { return T_And; }
"||" { return T_Or; }
"void" { return T_Void; }
"int" { return T_Int; }
"while" { return T_While; }
"if" { return T_If; }
"else" { return T_Else; }
"return" { return T_Return; }
"break" { return T_Break; }
"continue" { return T_Continue; }
"print" { return T_Print; }
"readint" { return T_ReadInt; }
{INTEGER} { return T_IntConstant; }
{STRING} { return T_StringConstant; }
{IDENTIFIER} { return T_Identifier; }
<<EOF>> { return 0; }
{UNTERM_STRING} { lex_error("Unterminated string constant", cur_line_num); }
. { lex_error("Unrecognized character", cur_line_num); }
%%
int main(int argc, char* argv[]) {
int token;
init_scanner();
while (token = yylex()) {
print_token(token);
puts(yytext);
}
return 0;
}
void init_scanner() {
printf("%-20s%s\n", "TOKEN-TYPE", "TOKEN-VALUE");
printf("-------------------------------------------------\n");
}
void lex_error(char* msg, int line) {
printf("\nError at line %-3d: %s\n\n", line, msg);
}
int yywrap(void) {
return 1;
}
新建makefile
run: word-spliter
./word-spliter < sample.c
word-spliter: lex.yy.c token.h
gcc -o $@ $<
lex.yy.c: word-spliter.l
flex $<
新建c语法测试文件sample.c
#include "for_gcc_build.hh" // only for gcc, TinyC will ignore it.
int main() {
int n;
n = 1;
print("The first 10 number of the fibonacci sequence:");
while (n <= 10) {
print("fib(%d)=%d", n, fib(n));
n = n + 1;
}
return 0;
}
int fib(int n) {
if (n <= 2) {
return 1;
}
return fib(n - 1) + fib(n - 2);
}
运行命令
make
结果：
bison-flex
Bison实现c语法分析，并构造中间代码
新建词法分析文件scanner.l
%{
#define YYSTYPE char *
#include "y.tab.h"
int cur_line = 1;
void yyerror(const char *msg);
void unrecognized_char(char c);
%}
LOGICOPER [>]
OPERATOR [-/+*()=;]
INTEGER [0-9]+
IDENTIFIER [_a-zA-Z][_a-zA-Z0-9]*
WHITESPACE [ \t]*
IF [i][f]
%%
{IF} { return T_if; }
{LOGICOPER} { return yytext[0]; }
{OPERATOR} { return yytext[0]; }
{INTEGER} { yylval = strdup(yytext); return T_IntConstant; }
{IDENTIFIER} { yylval = strdup(yytext); return T_Identifier; }
{WHITESPACE} { /* ignore every whitespcace */ }
\n { cur_line++; }
. { unrecognized_char(yytext[0]); }
%%
int yywrap(void) {
return 1;
}
void unrecognized_char(char c) {
char buf[32] = "Unrecognized character: ?";
buf[24] = c;
yyerror(buf);
}
void yyerror(const char *msg) {
printf("Error at line %d:\n\t%s\n", cur_line, msg);
exit(1);
}
新建语法分析文件parser.y
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <sstream>
using namespace std;
int yylex(void);
void yyerror(const char*);
#define YYSTYPE char *
int j = 0;
/*char* make_temp()
{
static int i=0;
i++;
char* p = malloc(128);
memset(p, 0, 128);
sprintf(p, "t%d", i);
return p;
}
char* new_p()
{
char* p = malloc(128);
memset(p, 0, 128);
return p;
}
*/
string make_temp()
{
static int i=0;
i++;
stringstream ss;
ss<< "%" << i;
return ss.str();
}
string get_last_line(const char* s) {
istringstream iss(s);
string last_line;
string temp;
while (getline(iss, temp, '\n')) {
if(temp != ""){
last_line = temp;
}
}
return last_line;
}
string getchildname(const char* exp)
{
string last_line = get_last_line(exp);
istringstream lineIss(last_line);
std::string tmp;
std::getline(lineIss, tmp, '=');
return tmp;
}
const char* getchildexp(const char* exp)
{
if(strstr(exp, "="))
{
return exp;
}
return "";
}
%}
%token T_IntConstant T_Identifier T_if
%left '+' '-'
%left '*' '/'
%right U_neg
%%
S : Stmt { cout << $1 ;}
| S Stmt { cout << $2 ;}
;
selection_statement: T_if '(' expression ')' Stmt {stringstream ss; ss << "cmp not " << $3 << " goto p" << j << "\n"<< $5 << "p" << j << ":\n"; j++; $$ = strdup(ss.str().c_str()); }
;
expression: Val '>' Val { stringstream ss; ss << $1 << ">" << $3; $$ = strdup(ss.str().c_str());}
;
Val: T_Identifier
| T_IntConstant
;
Stmt: T_Identifier '=' E ';' { stringstream ss; ss << getchildexp($3) << $1 << "=" << getchildname($3) << "\n"; $$ = strdup(ss.str().c_str()); }
| selection_statement { $$ = $1; }
;
E : E '+' E { string tempname = make_temp(); stringstream ss; ss << getchildexp($1) << getchildexp($3) << tempname << "=" << getchildname($1) << " + " << getchildname($3)<< "\n"; $$ = strdup(ss.str().c_str());}
| E '-' E { string tempname = make_temp(); stringstream ss; ss << getchildexp($1) << getchildexp($3) << tempname << "=" << getchildname($1) << " - " << getchildname($3)<< "\n"; $$ = strdup(ss.str().c_str());}
| E '*' E { string tempname = make_temp(); stringstream ss; ss << getchildexp($1) << getchildexp($3) << tempname << "=" << getchildname($1) << " * " << getchildname($3)<< "\n"; $$ = strdup(ss.str().c_str());}
| E '/' E { string tempname = make_temp(); stringstream ss; ss << getchildexp($1) << getchildexp($3) << tempname << "=" << getchildname($1) << " / " << getchildname($3)<< "\n"; $$ = strdup(ss.str().c_str());}
| T_IntConstant { $$ = $1; }
| T_Identifier { $$ = $1; }
;
%%
int main() {
return yyparse();
}
新建makefile
CC = g++
OUT = tcc
OBJ = lex.yy.o y.tab.o
SCANNER = scanner.l
PARSER = parser.y
build: $(OUT)
run: $(OUT)
./$(OUT) < test.c > test.asm
clean:
rm -f *.o lex.yy.c y.tab.c y.tab.h y.output $(OUT)
$(OUT): $(OBJ)
$(CC) -o $(OUT) $(OBJ)
lex.yy.c: $(SCANNER) y.tab.c
flex $<
y.tab.c: $(PARSER)
bison -vdty $<
新建测试文件test.c
a=c+b*10;
if(m>d)
c = a + 10;
m=a;
运行命令
make && ./tcc<test.c
得到结果
[root@localhost threeaddress]# make && ./tcc<test.c
bison -vdty parser.y
flex scanner.l
g++ -c -o lex.yy.o lex.yy.c
g++ -c -o y.tab.o y.tab.c
g++ -o tcc lex.yy.o y.tab.o
%1=b * 10
%2=c + %1
a=%2
cmp not m>d goto p0
%3=a + 10
c=%3
p0:
m=a
