创造新语言(2)——用Lex&Yacc构建简单的分析程序

技术分享
昨天我们开始设计了一门新语言,制定了基本的开发架构,今天我们就先来了解一下,两个非常好用的工具,编译器前端构建的神器——Lex&Yacc,这两个工具在linux下叫做flex和bison。

Lex是词法分析器构建工具,我们安装对应的词法规则书写,那么就能够为我们生成对应的词法分析器,自动帮我们分好token,而分词工作,一直是编译系统的基础任务。

我们今天,先来尝试编写一个BNF语法的解析器,将我们的BNF解析成代码可以识别的数据格式,BNF的格式大概是这样:

{{ do_init() }}

# 定义列表
<definelist> = <definelist> <define> | e ;
<define> = <constdef> | <vardef> | <functiondef> ;

# 变量和常量定义
<constdef> = "const" <const_def_run>  <vardef> {{ isconstdef = false }} ;
<vardef> = "int" <iddeflist> ";" ;
<iddeflist> = <iddeflist> "," <iddef> | <iddef> ;

这里就是我们的原始输入文件了,我们希望将其解析成为内存中的树结构,供我们的编译器使用,目前的任务就是,读入这样的文本,解析成树状结构。

这里我们可以发现,这种定义方式就是扩展BNF范式,而其中添加了语义动作的脚本{{ }},脚本也可以单独使用,用来做一些初始化工作等。

利用词法分析程序处理单词

我们先看一下基本的Lex扫描器如何编写:

/* scanner.l */
%{

#include <stdio.h>
#include "parser.hpp"

#define SAVE_TOKEN yylval.str = yytext
extern "C" int yywrap() { return 1; }

%}

/* show the line number */
%option yylineno

%%

"/*"([^\*]|(\*)*[^\*/])*(\*)*"*/" ; 

#[^\n]*\n               ; /* ignore line comment */ 

[ \t\v\n\f]             ; /* ignore blank token */

\"(\\.|[^\\"])*\"       SAVE_TOKEN; return STRING;

"{{"([^}]|\}[^}])*"}}"  SAVE_TOKEN; return SCRIPT;

"e"                     return ‘e‘;

":"                     return ‘:‘; 

"<"                     return ‘<‘; 

">"                     return ‘>‘; 

"["                     return ‘[‘;

"]"                     return ‘]‘;

"="                     return ‘=‘; 

"|"                     return ‘|‘;

";"                     return ‘;‘;

[a-zA-Z_][a-zA-Z0-9_]*  SAVE_TOKEN; return ID;

%%

这里的扫描器是根据多个正则式同时匹配的原理,注意,这里的条目是有顺序的,越靠上的元素优先级越高,假若第一个能匹配上,那么就不会匹配下面的,但存在更长的匹配时,取更长的。

这里用到了非常神奇的匹配:

"/*"([^\*]|(\*)*[^\*/])*(\*)*"*/"

能够匹配 /* comment */这样的注释。

\"(\\.|[^\\"])*\"

能够匹配C风格字符串。

"{{"([^}]|\}[^}])*"}}"

能够匹配类似{{ somefunction() }}这样的脚本。

如果您对这几个正则式不理解的话,希望先看一下我写的这篇文章,相信会对您有些帮助:
【Lex识别C风格字符串和注释 】

词法分析程序使用很多内置变量和函数,我再来介绍一下这几句话的意思:

extern "C" int yywrap() { return 1; }

yywrap是一个用来处理多文件的函数,它会在一个文件处理到结尾时被调用。假若你有多个文件,希望连续的被lex处理,那么你可以开一个文件列表,然后在这里依次将对应的文件接入到lex的输入流中,并且返回0,lex就认为还没处理结束,而yywrap一旦返回1时,表示所有的任务已经完成,可以结束了。

#define SAVE_TOKEN yylval.str = yytext

这个SAVE_TOKEN宏,用到了一个yacc中的内置变量yylval,这个变量是一个联合类型,一会儿你会在yacc的文件定义中发现一个%union的定义,就是它的类型定义。这部分的具体声明,可以在yacc生成的parser.hpp的头文件中找到。

%option yylineno

这是一个参数设置,启用了lex的报错机制,能够确定对应token的具体行号,虽然肯定会消耗一点资源,但debug也是十分重要的,使用时,只要在外部引用其中的yylineno变量,就能知道当前识别到的位置的行号:

extern int yylineno;

利用Yacc识别语法

为了正确的识别整个BNF语法,并且结构化的解析他们,我们写了如下的一个yacc程序:

/* parser.y */
%{

#include <stdio.h>

extern int yylex();

extern int yylineno;
extern char* yytext;
void yyerror(const char *s);

%}


%union {

    char *str = NULL;

}


%token <str> ID STRING SCRIPT


%start list

%%
/* 总的混合bnf和脚本的列表 */
list : item 
     | list item 
     ;

/* 可以是bnf或脚本 */
item : bnf_item
     | SCRIPT
     ;

/* 一行bnf的定义 */
bnf_item : symbol ‘=‘ bnf_list ‘;‘
         ;

/* bnf后面的部分 */
bnf_list : symbol_list
         | bnf_list ‘|‘ symbol_list
         ;

/* 一条bnf项的列表 */
symbol_list : symbol
            | symbol_list symbol
            ;

/* 可用的bnf符号 */
symbol : ‘<‘ name ‘>‘ 
       | ‘[‘ name ‘]‘
       | ‘e‘
       | STRING
       | SCRIPT
       ;

/* 名字,并且可以定义实例名 */
name : ID
     | ID ‘:‘ ID
     ;
%%

void yyerror(const char* s){
    fprintf(stderr, "%s \n", s);    
    fprintf(stderr, "line %d: ", yylineno);
    fprintf(stderr, "error %s \n", yytext);
}

这段程序就是在定义整个BNF语法的结构,以及按照什么样的规则规约他们,这里我们并没有添加语义动作,我们会在接下来的时间里将其添加成为一个可用的分析器。

添加主处理函数

我们的yacc和lex写的源文件可以被翻译为C++代码,但仅仅拥有一个基本的处理函数,要想处理文件,那就有自己编写文件的打开部分并将该文件重定向到yyin输入流中。


#include <stdio.h>
#include "parser.hpp"
#include "help_message.h"

extern FILE* yyin;
FILE* file_in;

int main(int argc,const char *argv[])
{
    printf("Welcome to use the XScript!\n");
    if (argc <= 1) printf(help_message);
    else {
        /* open the file and change the yyin stream. */
        const char *file_in_name = argv[1];
        if ((file_in=fopen(file_in_name,"r"))==NULL) {
            printf("error on open %s file!",file_in_name);
            getchar();
            return 1;
        }
        yyin = file_in;
        yyparse();

        /* you should close the file. */
        fclose(file_in);
    }
    return 0;
}

恩,主函数都写完了,我也想给这个项目起个名字,就先叫做XScript吧,意为多变的脚本,希望能成为一门自定义语法的翻译语言。

然后大家应该问,既然都写完了,那么如何编译构建呢?这里我们使用cmake构建整个工程,现在cmake也比较方便,能够支持直接调用lex和yacc的linux版,我们只需要增加两个cmake模块就可以实现项目的构建:

cmake_minimum_required(VERSION 2.8)

project(scanner)
SET(CMAKE_CXX_COMPILER_ENV_VAR "CXX")
SET(CMAKE_CXX_FLAGS "-std=c++11")
include_directories(include build src)

# bison and flex
find_package(BISON)
find_package(FLEX)
flex_target(SCANNER src/scanner.l  ${CMAKE_CURRENT_BINARY_DIR}/scanner.cpp)
bison_target(PARSER src/parser.y  ${CMAKE_CURRENT_BINARY_DIR}/parser.cpp)
ADD_FLEX_BISON_DEPENDENCY(SCANNER PARSER)

# src files and make exe
file(GLOB_RECURSE source_files "${CMAKE_CURRENT_SOURCE_DIR}/src/*.cpp")
add_executable(scanner
    ${source_files}
    ${BISON_PARSER_OUTPUTS}
    ${FLEX_SCANNER_OUTPUTS})

项目的文件组织目前是这样的:

LR_Scanner
    | ---- build
    | ---- src
            | ---- main.cpp
            | ---- help_message.h
            | ---- parser.y 
            | ---- scanner.l
    | ---- CMakeLists.txt

好的,在build路径下:

cmake ..
make

就搞能编译通过了,但运行并没有什么效果,这只是因为语义动作并没有执行,等我们添加好语义动作后,效果就不一样了,而且目前的解析器,只要你给的语法不对,他就会在对应的位置报错,还是很方便的。

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。