Skip to content

Flex 和 Bison 配合实现Python风格语法解析

Jump to bottom
西风逍遥游 edited this page Dec 9, 2021 · 3 revisions

Python风格语法是很受欢迎的一种基于缩进写法的语法，可以减少各种括号的使用，表示代码块只需使用缩进对其就可以了。 其中有两个难点，其一是Flex需要识别缩进，并确定block的位置。其二是，缩进在某些情况下应当被忽略，比如一行没有写完的代码。

def work(name):
    for i in range(1, 30)
        print(i)
	
	a = a + b + c + 
		q + parse(1, 2) # 这里的缩进就必须被忽略
        print(q)

代码缩进识别不是很困难，这点在这篇问答中已经被解决了： https://stackoverflow.com/questions/1413204/how-to-use-indentation-as-block-delimiters-with-bison-and-flex

我们可以在lexer中设立两个不同的start condition，INITIAL作为默认，用来识别缩进；而NORMAL模式用来识别缩进后面的正常词法。同时我们记录两个变量，一个是当前的缩进量，一个在前一个有效行的缩进量。注意，有些行比如没有内容的空行，注释等，我们不认为是有效行。

那么我们判断如果当前的缩进量比上一行加4，那么就输出一个特殊的token INDENT，用来表示类似左括号的意义 如果比上一行小，那么每4个空格，就输出一个token DEDENT，用表示类似右括号 这样一对INDENT和DEDENT包围下的内容就是一个代码块。

" "      {  current_line_indent++; }
"\t"     {  current_line_indent = (current_line_indent + 4) & ~3; }
"\n"     {  current_line_indent = 0; }
.        {
                    unput(*yytext);
                    if (current_line_indent > indent_level) {
                        if (current_line_indent == indent_level + 4) {
                            indent_level = current_line_indent;
                            BEGIN(NORMAL);
                            return INDENT;
                        } 
                    } else if (current_line_indent < indent_level) {
                        indent_level -= 4;
                        return DEDENT;
                    } else {
                        BEGIN(NORMAL);
                    }
                }

注意，tab的处理这里进行了一下计算，把一个tab当做了 ( indent+4 & (~3) ), 这个式子实际上是在计算如果tab前面有没对齐的空格，那么tab具体应该当做几个空格。在一般的设定tab=4空格的编辑器中，这个式子可以让你任意混用tab和空格，只要最后显示对齐，那么就可以正确识别。

处理没有结束的行

这个解析器最难的地方就是如何确保没有结束的行能够忽略缩进的影响，让用户可以任意换行写完这个语句，这就需要用到之前optional semicolon 一文中的方法了。我们知道，如果一个语句还没有结束，那么在换行符处进行检测，用分号测试自动机能否继续运转来确定此处是否能插入一个分号。这时只需要换成用INDENT和DEDENT进行测试即可。发现可以插入一个这种token时，就修改flex的start condition即可。

要想在bison里修改flex的start condition需要一点技巧，因为一般写在flex中的BEGIN(INITIAL)这种写法是一个宏，无法在生成的lexer.c外被使用，那么就需要在flex的第三个自定义函数区添加一个函数，那这里写好调整状态的代码，然后在bison中调用。同时，由于我们需要在遇到\n后，调整回INITIAL状态让flex进行处理，我们还需要unput这个换行符，让其不要被我们当前的token读取消耗掉。

void myunput(char c) { unput(c); }
void beginIndent() { BEGIN(INITIAL); }

于是，在结合上判断句尾的分号后，我们可以在yyfilter中实现如下效果，在每次遇到换行符时进行3次判断，是否需要一个分号，需要的话则输出一个分号。同时将unput换行符，这样相当于没有读入这个token。这样当不需要分号了之后，就去判断是否需要INDENT和DEDENT两个符号。 如果都不需要的时候，那么就去跳过当前的换行，直到下一个不是换行符。

int yyfilter(int yychar, int yyn, int yystate, yy_state_t *yyssp) {
    if (yychar == '\n' || yychar == YYEOF) {
        /* do we need a ';' ? */
        int r = try_symbol(yychar, yyn, yystate, yyssp, ';');
        if (r != -1) { printf("unput \\n"); myunput('\n'); return r; }
        
        /* do we need a INDENT or DEDENT ? */
        r = try_symbol(yychar, yyn, yystate, yyssp, INDENT);
        if (r != -1) { printf("unput \\n"); myunput('\n'); beginIndent(); return yylex(); }

        r = try_symbol(yychar, yyn, yystate, yyssp, DEDENT);
        if (r != -1) { printf("unput \\n"); myunput('\n'); beginIndent(); return yylex(); }

        do { yychar = yylex(); } while (yychar == '\n'); 
        printf("jump to next: %d\n", yychar);
        return yychar;

    }
    return yychar;
}

要注意，yyfilter是在optional semicolon一文中提到的自定义函数，需要用到自定义的skeleton。

完整代码 https://github.com/sunxfancy/flex-bison-examples/tree/master/python-like-indentation

Clone this wiki locally