开发编程语言(六):语法分析

Linux 2016-09-29

起步

初步的可运行的已经在github上了:https://github.com/OriginUnion/origin,发现有bug可以留言,供学习而已,千万别用在项目上,应该也没人这么做吧。

什么是语法分析

上篇的词法分析已经把文本解析为一个个单词。上一步的输出就是这步的输入,语法分析就是定义语句的格式。诸如像if语句的定义:

if_statement
        : IF LP expression RP block
        | IF LP expression RP block ELSE block
        | IF LP expression RP block elseif_list
        | IF LP expression RP block elseif_list ELSE block

这就定义了if的形式为if(表达式){}或者if(表达式){}else{}等格式。blok的定义在其他地方。

block
        : LC statement_list RC
        | LC RC
        ;

通常情况下代码块是由{}组成的,里面有语句组成的列表,列表先后也决定了语句的执行顺序。

statement
        : expression SEMICOLON
        | global_statement
        | if_statement
        | while_statement
        | for_statement
        | return_statement
        | break_statement
        | continue_statement
        ;

语句里面也包含了if语句,层层嵌套,就像if里面允许写if一样。

创建语句

还是以if为例

if_statement
        : IF LP expression RP block
        {
            $$ = org_create_if_statement($3, $5, NULL, NULL);
        }
        | IF LP expression RP block ELSE block
        ...
        ;

通过yacc语法分析器当满足IF LP expression RP block就会执行{},创建if语句的函数则我们可以自己定义。$3, $5分别是IF LP expression RP block第三(expression)和第五个(block)。

//if语句
Statement *org_create_if_statement(Expression *condition, Block *then_block,
                                   Elseif *elseif_list, Block *else_block) {

    Statement *st;
    st = org_alloc_statement(IF_STATEMENT);
    st->u.if_s.condition = condition;
    st->u.if_s.then_block = then_block;
    st->u.if_s.elseif_list = elseif_list;
    st->u.if_s.else_block = else_block;
    return st;
}

后面返回了return st$$的作用是可以给其他诸如org_create_xxxx_statement(IF_STATEMENT *if_stat);使用。其实也就是创建block函数返回给$$一样,在下一层函数就可以直接得到这个Statement结构体了。$$是yacc里面的变量,可以存放任意数据。

再看一个函数创建的:

function_definition
        : FUNCTION IDENTIFIER LP parameter_list RP block
        {
            org_function_define($2, $4, $6);
        }
        | FUNCTION IDENTIFIER LP RP block
        {
            org_function_define($2, NULL, $5);
        }
        ;
//创建函数
void org_function_define(char *identifier, ParameterList *parameter_list, Block *block) {
    FunctionDefine *fun;
    ORG_Interpreter *inter;

    if (org_search_function(identifier)) {
        //如果函数名存在
        //org_compile_error(FUNCTION);
        return;
    }
    inter = org_get_current_interpreter();

    fun = org_malloc(sizeof(FunctionDefine));
    fun->name = identifier;
    fun->type = ORIGIN_FUNCTION_DEF;
    fun->u.origin_f.parameter = parameter_list;
    fun->u.origin_f.block = block;
    fun->next = inter->function_list;
    inter->function_list = fun;
}

创建函数的步骤会多一些检测,比方说检测函数是否已经定义过,函数的保存是在全局的环境还是局部环境,另外需要一个保存函数的列表。

后话

语法分析都没有提到LL(0),LR(1),LALR,因为我自己就被它搞得晕头转向了,更别提要总结写博客了,合并规约,合并规约冲突,规约规约冲突等等脑子都大了,全怪平常都打dota去了。

参考链接:lex和yacc教程


本文由 hongweipeng 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

如果对您有用,您的支持将鼓励我继续创作!