使用正则表达式时，词法分析器非常容易编写。今天，我想用Python编写一个简单的通用分析器，并提出了：

import re
import sys

class Token(object):
    """ A simple Token structure.
        Contains the token type, value and position. 
    """
    def __init__(self, type, val, pos):
        self.type = type
        self.val = val
        self.pos = pos

    def __str__(self):
        return '%s(%s) at %s' % (self.type, self.val, self.pos)

class LexerError(Exception):
    """ Lexer error exception.

        pos:
            Position in the input line where the error occurred.
    """
    def __init__(self, pos):
        self.pos = pos

class Lexer(object):
    """ A simple regex-based lexer/tokenizer.

        See below for an example of usage.
    """
    def __init__(self, rules, skip_whitespace=True):
        """ Create a lexer.

            rules:
                A list of rules. Each rule is a `regex, type`
                pair, where `regex` is the regular expression used
                to recognize the token and `type` is the type
                of the token to return when it's recognized.

            skip_whitespace:
                If True, whitespace (\s+) will be skipped and not
                reported by the lexer. Otherwise, you have to 
                specify your rules for whitespace, or it will be
                flagged as an error.
        """
        self.rules = []

        for regex, type in rules:
            self.rules.append((re.compile(regex), type))

        self.skip_whitespace = skip_whitespace
        self.re_ws_skip = re.compile('\S')

    def input(self, buf):
        """ Initialize the lexer with a buffer as input.
        """
        self.buf = buf
        self.pos = 0

    def token(self):
        """ Return the next token (a Token object) found in the 
            input buffer. None is returned if the end of the 
            buffer was reached. 
            In case of a lexing error (the current chunk of the
            buffer matches no rule), a LexerError is raised with
            the position of the error.
        """
        if self.pos >= len(self.buf):
            return None
        else:
            if self.skip_whitespace:
                m = self.re_ws_skip.search(self.buf[self.pos:])

                if m:
                    self.pos += m.start()
                else:
                    return None

            for token_regex, token_type in self.rules:
                m = token_regex.match(self.buf[self.pos:])

                if m:
                    value = self.buf[self.pos + m.start():self.pos + m.end()]
                    tok = Token(token_type, value, self.pos)
                    self.pos += m.end()
                    return tok

            # if we're here, no rule matched
            raise LexerError(self.pos)

    def tokens(self):
        """ Returns an iterator to the tokens found in the buffer.
        """
        while 1:
            tok = self.token()
            if tok is None: break
            yield tok

if __name__ == '__main__':
    rules = [
        ('\d+',             'NUMBER'),
        ('[a-zA-Z_]\w+',    'IDENTIFIER'),
        ('\+',              'PLUS'),
        ('\-',              'MINUS'),
        ('\*',              'MULTIPLY'),
        ('\/',              'DIVIDE'),
        ('\(',              'LP'),
        ('\)',              'RP'),
        ('=',               'EQUALS'),
    ]

    lx = Lexer(rules, skip_whitespace=True)
    lx.input('erw = _abc + 12*(R4-623902)  ')

    try:
        for tok in lx.tokens():
            print tok
    except LexerError, err:
        print 'LexerError at position', err.pos

它工作得很好，但是我有点担心它效率太低。是否有任何正则表达式技巧可以使我以更有效/更优雅的方式编写它？

具体来说，有没有一种方法可以避免线性地遍历所有正则表达式规则以找到合适的规则？

解决方案

re.match被锚定。我们可以给它一个位置参数：

pos = 0
end = len(text)
while pos < end:
    match = regexp.match(text, pos)
    # do something with your match
    pos = match.end()

看看pygments，它提供了很多词法分析器，用于语法突出显示，它们具有不同的实现方式，其中大多数基于正则表达式。

这并不是我们问题的直接答案，但我们可能需要看一下ANTLR。根据此文档，python代码生成目标应该是最新的。

至于正则表达式，如果我们坚持使用正则表达式，实际上有两种方法可以加快速度。第一种是按照在默认文本中找到它们的可能性的顺序对正则表达式进行排序。我们可能会想到在代码中添加一个简单的探查器，该探查器收集每种令牌类型的令牌计数，并在工作体上运行词法分析器。另一种解决方案是对正则表达式进行分类存储(因为键空间是一个字符，相对较小)，然后在对第一个字符进行一次辨别后使用数组或者字典来执行所需的正则表达式。

但是，我认为，如果我们要走这条路线，则应该真正尝试使用类似ANTLR的方法，该方法更易于维护，更快并且更不会出现错误。

我们可以使用" |"将所有正则表达式合并为一个运算符，然后让正则表达式库执行令牌之间的识别工作。应该注意确保令牌的优先级(例如，避免匹配关键字作为标识符)。

组合令牌正则表达式可能会起作用，但我们必须对其进行基准测试。就像是：

x = re.compile('(?P<NUMBER>[0-9]+)|(?P<VAR>[a-z]+)')
a = x.match('9999').groupdict() # => {'VAR': None, 'NUMBER': '9999'}
if a:
    token = [a for a in a.items() if a[1] != None][0]

筛选器是我们必须进行一些基准测试的地方...

更新：我对此进行了测试，似乎好像我们按所述方式组合了所有标记并编写了类似以下的函数：

def find_token(lst):
    for tok in lst:
        if tok[1] != None: return tok
    raise Exception

为此，我们将获得大致相同的速度(可能更快一些)。我相信加速必须在于匹配的调用数量上，但是令牌鉴别的循环仍然存在，这当然会杀死它。

这些不是那么简单，但是可能值得一看...

python模块pyparsing(pyparsing.wikispaces.com)允许先指定语法，然后使用它来解析文本。道格拉斯(Douglas)，感谢我们关于ANTLR的帖子，我还没有听说过。还有lex / yacc的PLY python2和python3兼容实现。

我自己先写了一个基于正则表达式的临时解析器，但后来意识到我可能会受益于使用一些成熟的解析工具和学习上下文无关语法的概念等。

使用语法进行解析的优点是，我们可以轻松地修改规则并针对要解析的内容形式化非常复杂的语法。

我建议使用re.Scanner类，它没有记录在标准库中，但值得使用。这是一个例子：

import re

scanner = re.Scanner([
    (r"-?[0-9]+\.[0-9]+([eE]-?[0-9]+)?", lambda scanner, token: float(token)),
    (r"-?[0-9]+", lambda scanner, token: int(token)),
    (r" +", lambda scanner, token: None),
])

>>> scanner.scan("0 -1 4.5 7.8e3")[0]
[0, -1, 4.5, 7800.0]