美文网首页
c代码转成中间代码(Flex和Bison)实践

c代码转成中间代码(Flex和Bison)实践

作者: 谭英智 | 来源:发表于2021-09-20 16:35 被阅读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
    

    相关文章

      网友评论

          本文标题:c代码转成中间代码(Flex和Bison)实践

          本文链接:https://www.haomeiwen.com/subject/ryxvgltx.html