[toc]
词法、LR(1)语法分析器生成器,这只是一个玩具,学编译原理的时候写的。用的C++17,如果无法编译,可以点击这里下载编译好的exe,双击运行里面的demo就好。./demo
文件夹里的3个demo,都可以直接运行,注意运行的时候cwd
是./demo
,而不是项目根目录。
这三个demo从./testcase
文件夹中读取词法、文法、AST的定义,将生成的程序写入到./generated
文件夹中。在./testcase
文件夹中同样有这三个语言的样例程序,这三个demo同时会把这三个程序的分析结果写入到./output
文件夹中。
更详细的使用方法见后面的介绍。
PS:生成Parser的算法复杂度好高QAQ,一个C语言结构体的文法大概要4秒生成
MyLexer
:词法分析程序生成器,生成基于表格的词法分析器。支持的正则表达式包括形如这样的:
()
、[]
、[^abc]
、[a-zA-Z]
、.*?+|
和转义\.\*\+\?\|\(\)\[\]
,目前暂不支持{}
、^
、$
、预查、元字符,不支持UnicodeMyParser
:LR(1)语法分析程序生成器,生成基于表格的语法分析器。它不依赖于MyLexer
,而是只依赖于commons/token.hpp
中的Token
类。项目结构:
demo
:示例程序jsonxx
:JSON和fifo_map
依赖src
commons
:lexer和parser的公共依赖lexer/lexercc.hpp
:词法分析生成器parser/parsercc.hpp
:语法分析生成器gen_lexer_and_parser.hpp
:一个生成词法和语法分析代码的函数,使用方法见后lexer_main.cpp
:包含一个main函数,请编译后在命令行中输入参数运行,使用方法见后parser_main.cpp
:包含一个main函数,请编译后在命令行中输入参数运行,使用方法见后lexer_demo.cpp
:一个简单的Lexer的demotestcase
:测试用例,包括词法定义、文法定义、AST定义和一个待分析代码词法定义是一个普通的JSON文件,Key-Value
表示Token-Regex
,越先出现的token优先级越高,例如在下面的例子中,INT
和DOUBLE
的优先级高于ID
的优先级,这样保证了关键字优先:
// lexeme.json
{
"INT": "int",
"DOUBLE": "double",
"PLUS": "+",
"INT_VAL": "0|[1-9][0-9]*",
"DOUBLE_VAL": "[0-9]*\\.[0-9]*",
"ID": "[a-zA-Z_][a-zA-Z0-9_]*",
"STRING": "\"([^\"]|\\\\[btnfr\\\\\"])*\"",
"CHARACTER": "'[^']'"
}
语法定义是一个CSV文件(为什么不也用JSON,因为懒QAQ,以后再补了它叭),有2列,第一列是产生式名字,第二列是产生式,单词之间用空格分割,需要用扩展文法,区分大小写:
GS , exp_elem
exp_elem , add_exp
add_exp , mul_exp
add_exp , mul_exp PLUS add_exp
add_exp , mul_exp MINUS add_exp
mul_exp , VAL
mul_exp , VAL TIMES mul_exp
mul_exp , VAL DIV mul_exp
mul_exp , VAL PERCENT mul_exp
这个可有可无,其实就是个语法制导翻译,参考了一下Charles N.Fischer等人的《编译器构造》,使用JSON定义。详细定义见src/AST_schema.json
,包含4种操作
parseTreeToASTRules
的数组中重命名,需要注意的是,只有一个孩子的节点会被压缩,如果不想压缩掉,可以在compressExclusions
中写terminalNamesMapping
的数组中重命名childToFields
中写,终结符默认都会放进去,如果不想放,参考第6点childToSiblings
中写mergeChilds
里写ignoredTerminals
中写编译后命令行中运行lexer_main.exe
,接收两个参数,一个是用json格式定义的词法文件路径,一个是输出的词法分析程序的路径。
例如,使用testcase/midl_lex.json
中定义的词法,可以通过以下的方式在./output
文件夹中找到输出的程序
./build> lexer_main.exe ./testcase/midl/midl_lex.json ./output/
编译后命令行中运行parser_main.exe
,接收3~4个参数,含义如下:
例如,使用testcase/midl_syntax.txt
中定义的文法,可以通过下面的方式在./output
文件夹中找到输出的程序和分析表
./build> parser_main.exe ./testcase/midl/midl.json ./testcase/midl/midl_syntax ./output/ ./output/parse_table.csv
如下面的例子
在my_lexer.hpp
中包含核心的MyLexer
类,它提供2种方法:
addRegex
:添加一个正则表达式,priority
的值越小代表优先级越高lex
:对输入字符串进行词法分析,支持从std::istream
输入,也有一个从string
输入的包装版在lexercc.hpp
中包含2个工厂方法:
buildLexer
:从文件流读取词法文件,并建立词法分析器writeLexer
:将生成的词法分析器写入到指定路径的文件中只需要用以上两个文件就好了,从JSON文件读取输入的详细示例见lexer_main.cpp
。下面是一个从字符串读取输入的简单的例子:
#include "./src/lexercc.hpp"
using namespace std;
int main(){
MyLexer lexer;
lexer.addRegex("int", "INT", 0);
lexer.addRegex("double", "DOUBLE", 0);
lexer.addRegex("0|[1-9][0-9]*", "INT_NUM", 0);
lexer.addRegex("[0-9]*\\.[0-9]*", "DOUBLE_NUM", 0);
lexer.addRegex("[a-zA-Z_][a-zA-Z0-9_]*", "ID", 1);
lexer.addRegex("\"([^\"]|\\\\[btnfr\\\\\"])*\"", "STRING", 1);
vector<Token> tokens = lexer.lex("double foo 1.2 int intt 1 \"abc#$+\\n\\t\"");
for (auto i : tokens) {
cout << i.tokenName << ": " << i.word << endl;
}
writeLexer(lexer, "./output/", "./src/lexer", true);
}
在my_parser.hpp
中包含核心的MyParser
类,它只依赖于commons/Token.hpp
中的Token
类作为输入,不依赖于MyLexer
。它提供4个方法:
buildParserFromSyntaxDef
:工厂方法,从CSV格式的文法定义中建立语法分析器buildParserFromCsvParseTable
:工厂方法,从CSV格式的LR(1)分析表中建立语法分析器parse
:从vector<Token>
中读取输入,返回分析树指针 shared_ptr<MyParser::ParseTreeNode>
printParseTable
:打印分析表到指定的输出流中printParseTree
:打印分析树到指定的输出流中在parsercc.hpp
中包含一个方法:
writeParser
:将生成的语法分析器写入到指定路径的文件中在generate_lexer_and_parser.hpp
中包含一个方法:
generateLexerAndParser
:使用方法和前面的parser_main.exe
的使用相同:传送门
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。