创造新语言(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
就搞能编译通过了,但运行并没有什么效果,这只是因为语义动作并没有执行,等我们添加好语义动作后,效果就不一样了,而且目前的解析器,只要你给的语法不对,他就会在对应的位置报错,还是很方便的。
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。