编译原理：词法分析器 & Flex工具的使用（简单易懂）

词法分析器 & Flex工具的使用背景：编译器和解释器概念区别编译器的实现

词法分析器(Lexer)工具(Flex)安装Flex目标程序：verilog代码Flex程序格式DeclarationsDefinitionsRulesUser subroutines==如何通过flex读入文件？==

完整程序编译&运行

进阶：Flex生成Coolc的词法分析器DefinitionsNested CommentsInline CommentsStringOperatorKeywordAll Others

补充：正则表达式补充：有限状态机

词法分析器 & Flex工具的使用

背景：编译器和解释器

概念

编译器是一个程序（常见为C/C++程序），它阅读某种语言（源语言）编写的程序，并将其翻译为一种等价的、用另一种语言（目标语言）编写的程序

解释器是常见的另一种语言处理器，但是它并不同编译器一样翻译生成目标程序，而是直接利用用户提供的输入执行源程序指定的操作

例子：C和C++编译产生中间代码，如汇编代码和可重定位文件等，因此是编译型语言；Java和Python不产生中间代码，通过虚拟机直接运行源程序，因此是解释型语言

区别

通常来讲，编译器产生的程序比解释器运行速度快地多；然而，解释器的错误诊断效果通常更好，因为它的编译和执行是同时进行的。

编译器的实现

回顾一下编译器实现的几个阶段：

词法分析（lex analysis）解析（parse）语法分析（syntax analysis）代码优化（code optimization）代码生成（code gen）

我们暂且只关注词法分析的部分，来看看编译器完成的第一个工作是什么

词法分析器(Lexer)

来看一个简单的例子：This is a sentence

这是一串英文文本，人在解读它时，人就类似于编译器，请想一想人解读文本的第一步是什么？

为了解读文本，事实上人们总是需要先识别出单词的划分，尽管这是如此自然以致于你很可能会忽略这一步。然而，对于机器，这可能比你想象中更为复杂

如上的例子会被如此划分：

“This” - 代词(Pronoun)“is” - 动词(Verb)“a” - 冠词(Article)“sentence” - 名词(Noun)

思考：那么对一段程序情况如何呢？

if (i==j)

z=0;

else

z=1;

我们先直接陈述结论：词法分析器为了后续的解析所作的工作是，从【空格】【换行】【制表】等符号（统称whitespace）的间隔中区分出单词，常见的词性有六种。

whitespace-空白符identifiers-标识符keywords-关键字numbers-数字string-字符串operator-操作符/运算符

结果（标注所用首字母与上文对应）

工具(Flex)

Flex是一个用于生成词法分析器（lexer）的工具。

根据所输入的正则表达式，Flex能够直接生成需要的词法分析器的C++代码。

安装Flex

在旧版flex环境下进行实验

sudo apt install flex-old

flex --version

# should print flex 2.5.35(In Unbuntu 22.04LTS)

目标程序：verilog代码

我们考虑一段简单的verilog代码，并通过flex工具自动化生成可用的词法分析器程序

module My_not(A, Y)

input A;

output Y;

pmos(Y, VCC, A);

nmos(Y, GND, A);

endmodule

Flex程序格式

Declarations //包括头文件、枚举、宏名、函数申明等

Definitions //定义正则表达式和状态

Rules //定义匹配动作

User subroutines//用户定义的程序

Declarations

首先，定义程序需要用到的词性如下

enum TokenType {

KEYWORD = 1, //关键字

USER_DEF, //用户定义的标识符

SYMBOL, //符号

NUMBER, //数字

NONE //异常（空）

};

定义我们返回Token需要的函数

Token make_token(const std::string& text, int type) {

return std::make_pair(text, type);

}

定义行数：

int curLine

Definitions

因为没有特别复杂的正则表达式，因此在Definitions段我们就不声明特殊的正则表达式了，如果你需要声明，格式如下

USER_DEF [a-zA-Z_][a-zA-Z0-9_]* //星号(*)表示0个或多个,加号(+)表示1个或多个

DIGIT [0-9]+ //数字0到9

SYMPOL [,\.\(\);:\[\]] //中括号表示从所有字符中匹配其中一个

WHITESPACE [ \t\n\r\v]

Rules

此处定义匹配正则表达式的动作

module|input|output|wire|pmos|nmos|endmodule {

current_token = make_token(yytext, KEYWORD);

return current_token.second;

}

[a-zA-Z_][a-zA-Z0-9_]* {

current_token = make_token(yytext, USER_DEF);

return current_token.second;

}

[0-9]+ {

current_token = make_token(yytext, NUMBER);

return current_token.second;

}

[,\.\(\);:\[\]] {

current_token = make_token(yytext, SYMBOL);

return current_token.second;

}

[ \t\n\r\v] {

if (*yytext == '\n')

++curLine;

}

. { //"."表示匹配除了"\n"外的所有字符

std::cerr << "Unrecognized token: " << yytext << " at line " << curLine << std::endl; }

User subroutines

这部分可以执行的操作和C语言一模一样，你可以定义函数，变量和main函数

while ((token = yylex())) {

// Processing code

std::cout <<"#"<< curLine <<" "<< TokenTypeToString(current_token.second) << " " << current_token.first << std::endl;

}

我们在main函数中通过flex提供的yylex()接口不断获取文件中的下一个token，并打印在标准输出上

如何通过flex读入文件？

flex标准的输入YY_INPUT默认为FILE*形式，无法读入C++的std::iftream，因此我们呢需要在Declarations段声明其使用C++的标准输入，这样我们通过file.open打开的文件就成为了flex的输入

/* Define YY_INPUT to read from the std::ifstream object */

#undef YY_INPUT

#define YY_INPUT(buf, result, max_size) \

if (!file.eof() && file.readsome(buf, max_size) > 0) \

result = file.gcount(); \

else \

result = YY_NULL;

//在main函数中

file.open(argv[1]);

完整程序

//lexer.l

#include

enum TokenType {

KEYWORD = 1,

USER_DEF,

SYMBOL,

NUMBER,

NONE

};

using Token = std::pair;

std::ifstream file;

int curLine = 1;

Token current_token;

Token make_token(const std::string& text, int type) {

return std::make_pair(text, type);

}

#define YY_DECL int yylex()

int yylex();

void yyerror(const char* msg);

/* Define YY_INPUT to read from the std::ifstream object */

#undef YY_INPUT

#define YY_INPUT(buf, result, max_size) \

if (!file.eof() && file.readsome(buf, max_size) > 0) \

result = file.gcount(); \

else \

result = YY_NULL;

%option noyywrap

module|input|output|wire|pmos|nmos|endmodule { current_token = make_token(yytext, KEYWORD); return current_token.second; }

[a-zA-Z_][a-zA-Z0-9_]* { current_token = make_token(yytext, USER_DEF); return current_token.second; }

[0-9]+ { current_token = make_token(yytext, NUMBER); return current_token.second; }

[,\.\(\);:\[\]] { current_token = make_token(yytext, SYMBOL); return current_token.second; }

[ \t\n\r\v] {

if (*yytext == '\n') ++curLine;

}

. { std::cerr << "Unrecognized token: " << yytext << " at line " << curLine << std::endl; }

std::string TokenTypeToString(int tt) {

switch (tt) {

case KEYWORD:

return "KEYWORD ";

case USER_DEF:

return "USER_DEF";

case SYMBOL:

return "SYMBOL ";

case NUMBER:

return "NUMBER ";

case NONE:

return "NONE ";

default:

return "UNKNOWN ";

}

int main(int argc, char** argv) {

if (argc < 2) {

std::cerr << "Usage: " << argv[0] << " " << std::endl;

return 1;

}

file.open(argv[1]);

if (!file.is_open()) {

std::cerr << "Failed to open file: " << argv[1] << std::endl;

return 1;

}

int token;

while ((token = yylex())) {

// Processing code

std::cout <<"#"<< curLine <<" "<< TokenTypeToString(current_token.second) << " " << current_token.first << std::endl;

}

file.close();

return 0;

}

void yyerror(const char* msg) {

std::cerr << "Error: " << msg << std::endl;

}

编译&运行

编译命令：

# 自动生成cpp文件

flex -o lexer.cpp lexer.l

# 编译cpp成为可执行文件

g++ -std=c++14 -o lexer lexer.cpp -lfl # 通过-fl链接flex库

运行命令

./lexer not.v

输出格式

进阶：Flex生成Coolc的词法分析器

这是CS143课程的一个课程pj，接下来的实现来自skyzluo大佬，作为深度了解高级语言词法分析器的关键一步

注意：请参考代码框中的注释理解分词逻辑

Definitions

重点：通过%符号定义有限状态机的状态，此处只需要有个印象即可

DARROW =>

DIGIT [0-9]

%Start COMMENTS //注释

%Start INLINE_COMMENTS //单行注释

%Start STRING //字符串

Nested Comments

"(*" { //遇到(*时增加注释层次，并进入注释状态

comment_layer++;

BEGIN COMMENTS;

}

[^\n(*]* { } //跳过\n,(,*之外的所有连续字符

[()*] { } //跳过(,*,)的单个字符

"*)" { //匹配到*)时减少注释层次，到0时退出注释状态

comment_layer--;

if(comment_layer==0){

BEGIN 0;

}

<> { //注释中遇到EOF进行报错

yylval.error_msg = "EOF in comment";

BEGIN 0;

return ERROR;

}

"*)" { //未在注释状态遇到*)时报错

yylval.error_msg = "Unmatched *)";

return ERROR;

}

Inline Comments

"--" { BEGIN INLINE_COMMENTS; }//遇到特殊字符--开始单行注释

[^\n]* { } //跳过除\n外的所有字符

"\n" { //遇到换行符\n结束注释。

curr_lineno++;

BEGIN 0;

}

String

(\") {

BEGIN STRING;

yymore();

}

[^\\\"\n]* { yymore(); } //除了反斜杠,影号和换行符

\\[^\n] { yymore(); } //反斜杠转义字符

/* 转义的换行符

* char *str = "This is a long string \

* that spans multiple lines \

* using escaped newline characters.";

\\\n {

curr_lineno++;

yymore();

}

<> {

yylval.error_msg = "EOF in string constant";

BEGIN 0;

yyrestart(yyin);

return ERROR;

}

\n {

yylval.error_msg = "Unterminated string constant";

BEGIN 0;

curr_lineno++;

return ERROR;

}

\" {

std::string input(yytext,yyleng);

input = input.substr(1, input.length() - 2);

std::string output = "";

std::string::size_type pos;

//检查是否包含空字符

if (input.find_first_of('\0') != std::string::npos) {

yylval.error_msg = "String contains null character";

BEGIN 0;

return ERROR;

}

//添加转义字符

while ((pos = input.find_first_of("\\")) != std::string::npos) {

output += input.substr(0, pos);

switch (input[pos + 1]) {

case 'b':

output += "\b";

break;

case 't':

output += "\t";

break;

case 'n':

output += "\n";

break;

case 'f':

output += "\f";

break;

default:

output += input[pos + 1];

break;

}

input = input.substr(pos + 2, input.length() - 2);

}

output += input;

//检查字符串是否过长

if (output.length() > 1024) {

yylval.error_msg = "String constant too long";

BEGIN 0;

return ERROR;

}

//添加到字符表

cool_yylval.symbol = stringtable.add_string((char*)output.c_str());

BEGIN 0;

return STR_CONST;

}

Operator

"<-" { return ASSIGN; }

"<=" { return LE; }

"=>" { return DARROW; }

"+" { return int('+'); }

"-" { return int('-'); }

"*" { return int('*'); }

"/" { return int('/'); }

"<" { return int('<'); }

"=" { return int('='); }

"." { return int('.'); }

";" { return int(';'); }

"~" { return int('~'); }

"{" { return int('{'); }

"}" { return int('}'); }

"(" { return int('('); }

")" { return int(')'); }

":" { return int(':'); }

"@" { return int('@'); }

"," { return int(','); }

Keyword

(?i:class) { return CLASS; }

(?i:else) { return ELSE; }

(?i:fi) { return FI; }

(?i:if) { return IF; }

(?i:in) { return IN; }

(?i:inherits) { return INHERITS; }

(?i:let) { return LET; }

(?i:loop) { return LOOP; }

(?i:pool) { return POOL; }

(?i:then) { return THEN; }

(?i:while) { return WHILE; }

(?i:case) { return CASE; }

(?i:esac) { return ESAC; }

(?i:of) { return OF; }

(?i:new) { return NEW; }

(?i:isvoid) { return ISVOID; }

(?i:not) { return NOT; }

All Others

/* INT_CONST */

{DIGIT}+ {

cool_yylval.symbol = inttable.add_string(yytext);

return INT_CONST;

}

/* BOOL_CONST */

t(?i:rue) {

cool_yylval.boolean = 1;

return BOOL_CONST;

}

f(?i:alse) {

cool_yylval.boolean = 0;

return BOOL_CONST;

}

/* White Space */

[ \f\r\t\v]+ { }

/* TYPEID */

[A-Z][A-Za-z0-9_]* {

cool_yylval.symbol = idtable.add_string(yytext);

return TYPEID;

}

/* OBJECTID */

[a-z][A-Za-z0-9_]* {

cool_yylval.symbol = idtable.add_string(yytext);

return OBJECTID;

}

"\n" {

curr_lineno++;

}

/* error */

[^\n] {

yylval.error_msg = yytext;

return ERROR;

}

补充：正则表达式

基础：

空字符串

\epsilon

单字符集R

并连R+R

串连RR

自连R*

特殊：

A+ == AA*（A至少有一个）A? == A +

\epsilon

ϵ（A是可选的）[a-zA-Z] == ‘a’+‘b’+…A|B == A+B[a-z]的补 == [^a-z]

补充：有限状态机

有兴趣可了解确定性自动机(DFA) & 不确定性自动机(NFA)。

正则表达式如何通过有限状态机(FSM)表达？NFA如何转换到DFA？

友情链接

相关推荐

怎样领取手机积分怎么做积分兑换商城

婴儿缺氧多久会脑损伤

破解36个聚合直播平台：技术、风险与行业震荡

合作伙伴

编译原理：词法分析器 & Flex工具的使用（简单易懂）

相关推荐

怎样领取手机积分 怎么做积分兑换商城

婴儿缺氧多久会脑损伤

破解36个聚合直播平台：技术、风险与行业震荡

合作伙伴

怎样领取手机积分怎么做积分兑换商城