ART - Smali 文件分析 词法分析（二）

上次简单地介绍了一些词法分析

.class public Lcom/F8LEFT;
           

可以被分割为三个Token “.class” “public” “Lcom/F8LEFT;”

像这一类Token都可以按照其作用分为多种Token

比如，public private static等可以划分为flag的Token

分析器可以接收这一类Token，并且按照预定的规则进行分析。

那么，对于程序来说应该怎么去把这种字符串分析为相应的Token呢？

有一种比较简单的方法，就是利用正则表达式

比如，flag的正则为

public | private | static

通过定义多个正则可以准确地划分字符串为合适的Token。

然而，考虑到效率，是不建议对每一个Token进行比较，扫描的。因此，有必要寻求一种更高效的方法对字符串进行扫描。

举例来说，假如要区分IF ID,用c++可以这样实现

if(strcmp(src, "IF") == )
    return TOK_IF;
else if(strcmp(src, "ID") == )
    return TOK_ID;
return TOK_ERROR;
           

然而，这种对于每一个字符串都进行一次比较的做法，虽然编程上易于实现，但是效率实在是太低。

实际上，仔细观察，IF ID开头字母都是一样的，因此可以进行合并

const char* p = src;
if(*p == 'I') {
    p++;
    if(*p == 'F')
        return TOK_IF;
    else if(*p == 'D')
        return TOK_ID;
}
return TOK_ERROR:
           

这样则可以在保证效果一样的前提下提高了效率。当要判断的字符串前部相似的地方越多，则效率提升越高。这种每一次只取一个字符进行判断，然后切换判断流程的称为自动机。

上图显示了自动机以及有限自动机的合并。

这样，通过对多个自动机的合并，则可以完成一个比较高效的分析器。

当然，这种操作写起来比较麻烦，所以ART中使用了flex来完成词法分析。

下一节，将会讲解ART中的Lex模块

ART项目地址：

https://github.com/F8LEFT/ART