编译实践系列将以lua的词法,语法和语意为标准,用C++实现lua的解释器,这其中也会参考lua解释器官方实现,但重点在于理清编译系统的基本框架和每个环节最基本的实现。
一般的编译系统结构:
本系列相应的源码在:https://github.com/pzhp/lua_interpretor
****************************************************************************
1 先看一道常见的面试题:把字符串转换为整数(即实现atoi),如果考虑到实现基本功能(不含溢出处理),这并不难:依次读入字符取得对应的数字再乘以权重累加即可,正负数也只是加个前置判断而已。
2 再给道题,判断一段字符串是否满足一下要求:只能以字母或下划线开始,其余部分数字、字母、下划线均可。我相信这个也不难,从头开始扫描字符串,if判断即可。
3 如果再告诉你一条规则,以 ‘“’ 开头直到遇到 ‘”’结尾,或者以 单引号开头和结尾可判定为字符串常量。
4 最后,增加判定是运算符(+ - * 、 % <= ...)和分隔符(; , ...)的规则,也就可以识别程序语言中的运算符和分割符了。只不过这里会用到一个小技巧,lua里存在 ".", "..", "..." 当字符判定为"."时,会继续预读入下一个字符再判定, 如果第二个字符是"." 则拿到该字符,结果为"..",继续这么处理第三个字符。可以将这个判断转化为查表。
当完成这几个函数,那么需要考虑什么时候选择解析成数字,什么时候解析成字符串...,其核心在于预先看一两个字符做预判,决定走那条路,这里的预测可以采用标准流的peek, get, putback等函数完成,其基本框架如下:
while (true){ // init a single token recognise state char ch = GetNextChar(); if (isdigit(ch)) { tk = ProcessNumberState(ch); } else if (std::isalpha(ch) || ch == '_') { tk = ProcessIndentifyState(ch); } else if (ch == '\'' || ch == '"') { tk = ProcessStringState(ch); } else if (ch == '-' && PeekNextChar() == '-') { HandleComemnt(ch); continue; } else if (m_dict.haveToken(std::string(1,ch))) { tk = ProcessOperatorAndDelim(ch); } else { m_currState = S_Fatal; m_strErrReason = "cannot find dispatch method"; }}
为了存放词法分析的结果,定义Token类,主要含有一下属性:token所在位置(文件,行,列),token类型(数字常量,字符串常量,标识符等),token的值(可以用解析出来字符串代表)。
具体源码请参考scanner.cpp
如果你要写针对特定语言的词法分析模块,上面描述就够了,那么为什么编译原理类的书会讲正则文法,有限状态自动机(DFA,NFA),搞的那么复杂呢?一方面为了形式化表述,另外方面也是为了自动化生成,满足可配置性。以lex generator:flex为例:
/* 规定DIGIT为0-9的数,如果规定[0-8],那么9将无法被判定到数字里面 */DIGIT ([0-9])HEX_DIGIT ([0-9a-fA-F])HEX_INTEGER (0[Xx]{HEX_DIGIT}+)INTEGER ({DIGIT}+)EXPONENT ([Ee][-+]?{INTEGER})DOUBLE ({INTEGER}"."{DIGIT}*{EXPONENT}?)BEG_STRING (\"[^"\n]*)STRING ({BEG_STRING}\")IDENTIFIER ([a-zA-Z][a-zA-Z_0-9]*)OPERATOR ([-+/*%=.,;!<>()[\]{}])BEG_COMMENT ("/*")END_COMMENT ("*/")SINGLE_COMMENT ("//"[^\n]*)/* -------------------- Constants ------------------------------ */"true"|"false" { yylval.boolConstant = (yytext[0] == 't'); return T_BoolConstant; }{INTEGER} { yylval.integerConstant = strtol(yytext, NULL, 10); return T_IntConstant; }{HEX_INTEGER} { yylval.integerConstant = strtol(yytext, NULL, 16); return T_IntConstant; }{DOUBLE} { yylval.doubleConstant = atof(yytext); return T_DoubleConstant; }{STRING} { yylval.stringConstant = _strdup(yytext); return T_StringConstant; }{BEG_STRING} { ReportError::UntermString(&yylloc, yytext); }/* -------------------- Identifiers --------------------------- */{IDENTIFIER} { if (strlen(yytext) > MaxIdentLen) ReportError::LongIdentifier(&yylloc, yytext); strncpy(yylval.identifier, yytext, MaxIdentLen); yylval.identifier[MaxIdentLen] = '\0'; return T_Identifier; }
我们提供正则表达式,generator其内部完成以下转换,从正则式转换到NFA再到DFA阶段,DFA还可以做优化精简,生成一个词法分析模块。每一步的转化都有相应的算法完成。比如NFA到DFA算法:采用子集构造算法,类似于广度优先搜索,将下一阶段有可能的状态集中到一个集合,遍历操作增加下一步,只有最终集合中存在可接受的状态,则视为成功。可以参考engineering a compiler:chapter2 和装配脑袋博客
联系客服