一、可配置的词法分析器
通用编译器是基于配置的,编译器本身不包含特定语言相关的信息。而语言相关的信息放到配置文件中。因此在整个编译器设计中,不仅仅是编译器要编译的文件需要词法分析,配置信息的读取也需要词法分析。
在可定制的词法分析部件完工之前,所有的词法分析都靠硬编码完成,即像这样:
if(_begin == end) throw EReachEndOfFile();
_pointer = _begin;
/*if(_literal_mode && (CppLex::IsBlank(*_pointer) || CppLex::IsEndLine(*_pointer)))
{
while(_pointer != end && _Lex::IsBlank(*_pointer)) ++_pointer;
}
else */if( _Lex::IsChar(*_pointer) )
{
bool isnumber = _Lex::IsDigit(*_pointer);
char_type ch = *_pointer;
while(_pointer != end && (_Lex::IsChar(ch) || (ch=='.' && isnumber)))
{
//_str.push_back(*_pointer);
//if(isnumber && !_Lex::IsDigit(ch) && !_Lex::IsNumSuffix(ch)) break;
ch = *(++_pointer);
//if(isnumber && _Lex::IsNumSuffix(ch)) {ch = *(++_pointer); break;}
}
/*if( *this == _T("0") && _Lex::IsNumHexPrefix(ch) && _pointer != end ) // hex numbers
{
do
{
ch = *(++_pointer);
}
while(_Lex::IsHexDigit(ch) && _pointer != end);
}
else if( isnumber && ch == '.' && _pointer != end ) // floating points
{
do
{
ch = *(++_pointer);
if(!_Lex::IsDigit(ch) && !_Lex::IsNumSuffix(ch)) break;
if(ch == 'f' || ch == 'F') {ch = *(++_pointer); break;}
}
while( (_Lex::IsDigit(ch) || _Lex::IsNumSuffix(ch)) && _pointer != end );
}
else // exponent
{
char_type prev = *(_pointer-1);
if( isnumber && (_Lex::IsDigit(ch) || ch == '-') && (prev == 'e' || prev == 'E') && _pointer != end )
{
do
{
prev = ch;
ch = *(++_pointer);
}
while((_Lex::IsDigit(ch) || _Lex::IsNumSuffix(ch)) && !_Lex::IsNumSuffix(prev) && _pointer != end);
}
}*/
}
else if( _Lex::IsSign(*_pointer) )
{
char_type ch = *_pointer, ch2 = 0;
if(ch == '/n') _line_no++; // line no increases
if(_pointer != end)
{
//_str.push_back(*_pointer);
++_pointer;
// check duplicated charactors such as ==, ++, -- etc.
if(_Lex::CanDuplicated(ch) && _pointer != end && ch == *_pointer)
{ ch2 = ch; ch = *_pointer; /*_str.push_back(ch);*/ ++_pointer; }
// check composite operator such as +=, <<=, ||= etc.
if(_pointer != end && _Lex::CanCombine(ch, *_pointer))
{
ch2 = ch;
ch = *_pointer;
//_str.push_back(ch);
++_pointer;
}
if(ch2 != 0 && _pointer != end && _Lex::CanCombine(ch2, ch, *_pointer))
{
ch = *_pointer;
++_pointer;
}
if( _Lex::IsQuoteOn(ch) )
{
while(_pointer != end)
{
if (_Lex::IsQuoteOff(*_pointer, ch))
{
break;
}
int escs = _Lex::EscapeChars(*_pointer);
++_pointer;
while (escs > 0)
{
++_pointer;
escs--;
}
}
if(_pointer != end) ++_pointer;
}
}
//int txtid;
// check _T("/ xxx")
if( ch == '//' )
{
// skip _T("//") + _T("/n") and read next Token.
Token<_Iter,_Lex> tk(*this);
tk.ReadToken(_pointer, end);
if(tk.IsEmpty() || tk == _T("/n"))
{
// skip _T("/ /n") and _T("/ feof")
tk.ReadToken(tk.end(), end);
Copy(tk);
}
// merge _T("//")+_T("xNNN")
/*else
{
char_type ch = *_pointer;
if(_Lex::IsNumHexPrefix(ch))
{
do
{
ch = *(++_pointer);
}
while(_Lex::IsHexDigit(ch));
}
else if(_Lex::IsDigit(ch))
{
do
{
ch = *(++_pointer);
}
while(_Lex::IsDigit(ch));
}
}*/
}
//else if( text && (txtid=_Lex::IsTextOn(*this)) > 0 ) // check text-literal
//{
// // read 'text' or _T("text")
// Token<_Iter,_Lex> tk(*this);
// tk.ReadToken(_pointer, end);
// while( !tk.IsEmpty() && !_Lex::IsTextOff(tk, txtid) )
// {
// if(tk == '/n')
// _line_no++; // line number increases
// tk.ReadToken(tk.end(), end, false, false);
// }
// Merge(tk);
//}
else if(skipComment)
{
int commentid;
// skip comments
if(_Lex::IsLineComment(*this))
{
// skip _T("/ //comment /n")
do
{
if(_begin == end) break;
++_begin;
}
while(*_begin != '/n');
_pointer = _begin;
/* /n should be preserved */
if(_pointer != end)
{
_line_no++;
++_pointer;
}
//Token<_Iter,_Lex> tk(*this);
//tk.ReadToken(_pointer, end);
//while( !tk.IsEmpty() && tk != '/n' ) tk.ReadToken(tk.end(), end, /*text,*/ false);
///* /n should be preserved so the following line should be omitted. */
////tk.ReadToken(tk.End(), end);
//Copy(tk);
////_line_no++; // line number increases
}
else if( (commentid=_Lex::IsCommentOn(*this)) > 0 )
{
// skip _T("/ /*comment*/ /n")
do
{
if(_pointer == end) break;
if(*_pointer == '/n') _line_no++;
++_pointer;
}
while(!_Lex::IsCommentOff(*this, commentid));
ReadToken(_pointer, end);
//Token<_Iter,_Lex> tk(*this);
//tk.ReadToken(_pointer, end);
//while( !tk.IsEmpty() && !_Lex::IsCommentOff(tk, commentid) )
//{
// if(tk == '/n')
// _line_no++; // line number increases
// tk.ReadToken(tk.end(), end, /*text,*/ false);
//}
//tk.ReadToken(tk.end(), end);
//Copy(tk);
}
}
}
else ++_pointer;
return _pointer;
}
这种硬编码的词法分析器非常笨拙。这段长达100多行的代码融入和各种词法元素的分析,难于维护。但是又不得不写。因为没有这个词法分析器就不可能完成配置文件的分析,因为这是一个先有鸡还是先有蛋的问题,就好象我写C++编译器,还先得找个可用的C++编译器来使用。(不同点在于自己的设计是不断精炼的,而不管如何精炼,可能都无法超越已有的。但至少整体设计是新颖的。)
一种构造词法分析器的方法是使用Lex程序生成一个。Lex和Yacc都是基于代码替换的。它们将正则表达式(词法定义)和产生式(文法定义)分析为状态动作表,然后通过动作表生成代码框架,定义文件中每一条定义对应的动作代码就嵌入到框架的相应位置,从而产生完整的词法分析和文法分析代码。
我采用的方法是不再生成分析器的源代码,而是直接根据动作表进行翻译。这样做的好处是可以保证接口的一致性,缺点是速度偏慢(词法分析的速度很快,文法分析的速度较慢)。
二、动作表的生成
现在的问题有三个:1.词法如何定义?2.动作表长着什么样?3.如何通过定义生成动作表。
词法和文法在计算理论中其实是一码事,都属于字符串识别的问题。针对这类问题便有了乔姆斯基的文法分类(具体细节去看教科书《形式语义与自动机》)。按照该分类,编译器一般用的是最弱的两类文法:II型文法(上下文无关文法)和III型文法(正则文法)。III型文法是II型文法的特例,也是定义最强,表达能力最弱的文法。这两种文法的区别是:II型文法允许中部递归(A->aAa|b,识别b aba aabaa aaabaaa等),而III型只允许左右递归(A->aA|b相当于a*b,A->Aa|b相当于ba*)。
词法一般由正则文法表达即可。正则文法与NFA、DFA都是等价的概念。因此动作表实际上就是DFA图的某种表示形式。生成动作表的方法其实就是正则文法转换为DFA的问题。
但是我使用了上下文无关文法来定义词法。这样做的好处是:保持词法和文法定义的书写一致性,同时相关的格式化代码也可以共用,另外C++标准中的词法也是用类似BNF来表示的,可以直接复制出来使用,而且换一种语言的话,如果能够给出正则表达式,那么写出等效的上下文无关文法也易如反掌。
因此要得到词法分析器可用的DFA动作表,步骤是这样的:1.将上下文无关文法降级为正则文法并转换为NFA;2.NFA转换为对应的DFA;3.将DFA最小化。
上下文无关文法转换为NFA并不是等效转换,而是一种降级转换,许多上下文无关文法可识别的串,NFA无法识别,例如a...ab...b中要求a和b的数目一致才能识别,这属于上下文无关文法,而正则文法无法表达。有人会说:那干脆直接用上下文无关文法的分析法来进行词法分析好了。这样做是可行的,而且我也将之前做的可配置的语法分析器LRParser修改了一下,兼容词法分析。结果是速度比硬编码慢5倍,而DFA的词法分析器速度比硬编码的快2倍。
我们用大写字母来表示非终结符,小写字母来表示终结符,希腊字母表示终结符或非终结符,FIRST代表FIRST集合函数,F代表结束状态集函数,#代表任意其他终结符。用类似LR动作表构造方法中给产生式右部加点的方法来表示翻译状态。上下文无关文法的降级过程如下:
1、划分状态集:
若A-> .α B属于状态集 i,则A->. β C也属于状态集 i;
若A-> α . B属于状态集 i,则 B-> . β 也属于状态集 i;
2、生成NFA:
对于 A-> . a B 的所在状态集 i, 添加NFA动作:(i, a)-> j,其中 j 为
A->a . B 所在状态集,并添加状态集 j 到 A 的递归集合 R 中;
* 对于形如 A->a . B c 或 A-> . B c 的所在状态集 i ,添加NFA动作:(i, ε)-> j,其中 j 为 B-> . β 所在状态集,并设置F(B-> β) := F(A->a B c);
对于形如 A-> . A a 的所在状态集 i,忽略对应动作,因为对应动作(i, ε)-> i 没有意义。
**对于形如 A->a . A 的所在状态集 i,添加所有符合如下条件的NFA动作:(i, α) -> r,其中α属于FIRST(A)中任意终结符,r为A的递归集合 R 中任意状态集。
* 对于形如 A->a B c . 的所在状态集 i,
如果F(A->aBc) = 空,则添加NFA归约:(i, #) = "A" ,否则,如果 i != F(A->a B c) 添加NFA动作:(i, ε)-> F(A->a B c)
3、由NFA生成DFA:
这个就直接采用教科书上的经典算法即可。基本思想是将ε-closure(i)作为DFA状态,对于 i 相关的每一个动作都添加到 ε-closure 的对应动作表中,如果重复添加,则产生冲突。算法可以保证不会出现转移冲突;也不可能出现转移/归约冲突,因为归约符号#代表所有其他不在表中的终结符。因此只能出现归约/归约冲突。这个时候得依靠用户输入优先级了。例如identifier的优先级永远是最低的,因为关键字通常也是标识符,因此出现归约关键字和归约标识符的冲突,那么就优先归约关键字。
4、DFA最小化。
这个最简单,只需搜索所有DFA状态集簇对应的动作,如果两个状态集簇的动作表一致,则可以合并,并修改相关状态集簇的标号。知道所有能合并的状态集簇都被合并了,则为最小DFA。
生成NFA算法中带 * 的第二条和第五条规则是针对归约的。F(产生式)函数只是该产生式的一条临时记录,在该产生式的所有后续动作全部解析完后,这条临时记录就可以被删除了。等到下次再递归到这儿的时候F()的值已经变化了。举个简单例子说明这一情况:
假设有如下文法:
id -> first-char id-char
first-char -> '_' | letters
id-char -> '_' | letters | digits
现在要识别id,那么对于first-char -> '_' | letters 和 id-char -> '_' | letters | digits 这5个产生式来说,其A->a B c .不存在归约,因为词法分析不像文法分析那样需要对每个产生式进行归约,只需要对要识别的初始项目进行归约即可。因此这5个产生式的F(...) = F(id -> first-char id-char),他们都是由第一个产生式按照算法第二条引申出来的。
生成NFA算法中带**的第四条规则是针对右递归的。举个例子:
假设有如下文法:
S -> A B
A -> a A | c A | a | c
B -> b B | b
这就相当于正则表达式 [a,c]+b+。假设A->A a属于状态集i,则 i 一定已经在递归集合 R 中了,且后续输入可能有a和b。而只有对FIRST(A)中的终结符a,c 有 (i, a) -> r、(i, c) -> r,对于b,需要依靠 (S -> A . B, b) 的转移实现,这是第二条规则的内容。
上下文无关文法转正则文法的算法依靠带 * 号的那两条规则除去了对词法来讲繁复无用的中间归约步骤,只保留了最终归约。换句话说,扔掉了上下文无关文法的树状层次关系,而将输入字符串展平了。
三、词法分析器
词法分析器就是一个确定性有限状态自动机。状态机维护一个状态数,可以看作是动作表数组的下标。初始状态为0,对每一个输入查表并执行操作。只有两种操作:
形如(i, a) -> j 的转移操作,即如果输入字符为 a ,则从状态 i 转移到状态 j
形如(i, #) = "A" 的归约操作,即如果输入字符为 a,而 i 的动作表中没有 a 对应的操作,则将已输入的字符串归约为A。
词法分析器就是从状态0开始执行到一个归约操作为止。注意:归约操作时遇到的输入字符 a 并不从输入序列中删除,而是下一个记号的起始。
四、效率
使用DFA重新设计的词法分析器比之前的硬编码分析器更灵活,而分析器本身的代码更简单,速度也更快(提高了近1倍)。
五、使用
C:/Users/xx/Desktop/lex>lextable cpp.lexi
type ? for help.
COMMAND :format
optional node is found in [exponent-part]
optional node is found in [exponent-part]
optional node is found in [floating-literal]
optional node is found in [floating-literal]
optional node is found in [floating-literal]
optional node is found in [floating-literal]
optional node is found in [fractional-constant]
optional node is found in [integer-literal]
optional node is found in [integer-literal]
optional node is found in [integer-literal]
optional node is found in [integer-suffix]
optional node is found in [integer-suffix]
optional node is found in [string-literal]
optional node is found in [string-literal]
0 ms
COMMAND :nfa token
nfa has built successfully.
40935 ms
COMMAND :dfam
terminations collision detected:
0 identifier; 1 operator;
Please select a termination : 1
terminations collision detected:
0 identifier; 1 boolean-literal;
Please select a termination : 1
0 items left.
dfa has built successfully.
minimizing...
dfa table has been minimized.
29484 ms
COMMAND :saveb cpp.dfa
0 ms
COMMAND :exit
C:/Users/xx/Desktop/lex>lex cpp.lexi cpp.dfa test.c
loading syntax file and action file complete.
{ /r/n | (0,0) | skip}
{ int | (1,0) | identifier}
{ SP | (1,3) | skip}
{ main | (1,4) | identifier}
{ SP | (1,8) | skip}
{ ( | (1,9) | operator}
{ int | (1,10) | identifier}
{ SP | (1,13) | skip}
{ argc | (1,14) | identifier}
{ , | (1,18) | operator}
{ SP | (1,19) | skip}
{ const | (1,20) | identifier}
{ SP | (1,25) | skip}
{ char | (1,26) | identifier}
{ SP | (1,30) | skip}
{ * | (1,31) | operator}
{ argv | (1,32) | identifier}
{ [ | (1,36) | operator}
{ ] | (1,37) | operator}
{ ) | (1,38) | operator}
{ /r/n | (1,39) | skip}
{ { | (2,0) | punctuator}
{ /r/n/t | (2,1) | skip}
{ int | (3,1) | identifier}
{ SP | (3,4) | skip}
{ a | (3,5) | identifier}
{ SP | (3,6) | skip}
{ = | (3,7) | operator}
{ SP | (3,8) | skip}
{ 1 | (3,9) | integer-literal}
{ ; | (3,10) | punctuator}
{ /r/n/t | (3,11) | skip}
{ int | (4,1) | identifier}
{ SP | (4,4) | skip}
{ b | (4,5) | identifier}
{ SP | (4,6) | skip}
{ = | (4,7) | operator}
{ SP | (4,8) | skip}
{ 2 | (4,9) | integer-literal}
{ ; | (4,10) | punctuator}
{ /r/n/t | (4,11) | skip}
{ return | (5,1) | identifier}
{ SP | (5,7) | skip}
{ a | (5,8) | identifier}
{ SP | (5,9) | skip}
{ + | (5,10) | operator}
{ SP | (5,11) | skip}
{ b | (5,12) | identifier}
{ ; | (5,13) | punctuator}
{ /r/n | (5,14) | skip}
421ms
COMMAND :