16

正規表現がある場合、字句アナライザーは非常に簡単に記述できます。今日、私は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

それは問題なく動作しますが、非効率的すぎるのではないかと少し心配しています。より効率的でエレガントな方法でそれを書くことを可能にする正規表現のトリックはありますか?

具体的には、すべての正規表現ルールを直線的にループして、適切なものを見つけることを回避する方法はありますか?

4

6 に答える 6

12

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]
于 2010-11-09T16:59:03.160 に答える
7

「|」を使用して、すべての正規表現を1つにマージできます。演算子を使用して、正規表現ライブラリにトークンを識別する作業を実行させます。トークンの優先度を確保するために、ある程度の注意を払う必要があります(たとえば、キーワードを識別子として一致させないようにするため)。

于 2008-09-25T15:54:53.540 に答える
7

これはpythonドキュメントで見つけました。シンプルでエレガントです。

import collections
import re

Token = collections.namedtuple('Token', ['typ', 'value', 'line', 'column'])

def tokenize(s):
    keywords = {'IF', 'THEN', 'ENDIF', 'FOR', 'NEXT', 'GOSUB', 'RETURN'}
    token_specification = [
        ('NUMBER',  r'\d+(\.\d*)?'), # Integer or decimal number
        ('ASSIGN',  r':='),          # Assignment operator
        ('END',     r';'),           # Statement terminator
        ('ID',      r'[A-Za-z]+'),   # Identifiers
        ('OP',      r'[+*\/\-]'),    # Arithmetic operators
        ('NEWLINE', r'\n'),          # Line endings
        ('SKIP',    r'[ \t]'),       # Skip over spaces and tabs
    ]
    tok_regex = '|'.join('(?P<%s>%s)' % pair for pair in token_specification)
    get_token = re.compile(tok_regex).match
    line = 1
    pos = line_start = 0
    mo = get_token(s)
    while mo is not None:
        typ = mo.lastgroup
        if typ == 'NEWLINE':
            line_start = pos
            line += 1
        elif typ != 'SKIP':
            val = mo.group(typ)
            if typ == 'ID' and val in keywords:
                typ = val
            yield Token(typ, val, line, mo.start()-line_start)
        pos = mo.end()
        mo = get_token(s, pos)
    if pos != len(s):
        raise RuntimeError('Unexpected character %r on line %d' %(s[pos], line))

statements = '''
    IF quantity THEN
        total := total + price * quantity;
        tax := price * 0.05;
    ENDIF;
'''

for token in tokenize(statements):
    print(token)

ここでのトリックは次の行です。

tok_regex = '|'.join('(?P<%s>%s)' % pair for pair in token_specification)

ここで(?P<ID>PATTERN)は、一致した結果を で指定された名前でマークしますID

于 2013-02-17T08:51:33.957 に答える
3

re.match固定されています。位置引数を与えることができます:

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

ほとんどが正規表現に基づいた、さまざまな実装で構文を強調表示する目的で大量のレクサーを出荷する pygments を探してください。

于 2008-09-25T15:38:49.430 に答える
3

トークンの正規表現を組み合わせて機能する可能性はありますが、ベンチマークする必要があります。何かのようなもの:

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

これにより、ほぼ同じ速度(おそらく10代の速度)が得られます。スピードアップは一致する呼び出しの数にあるに違いないと思いますが、トークン識別のループは依然として存在し、もちろんそれを殺します。

于 2008-09-25T19:24:13.210 に答える
1

これはあなたの質問に対する直接的な回答ではありませんが、 ANTLRを見たいと思うかもしれません。このドキュメントによると、python コード生成ターゲットは最新である必要があります。

正規表現に関しては、正規表現に固執している場合、速度を上げるには実際には2つの方法があります。1 つ目は、正規表現をデフォルトのテキストで見つける確率の順に並べることです。各トークン タイプのトークン カウントを収集するコードに単純なプロファイラーを追加し、一連の作業でレクサーを実行することを考えることができます。もう1つの解決策は、正規表現をバケットソートし(文字であるキースペースが比較的小さいため)、配列または辞書を使用して、最初の文字で単一の識別を実行した後、必要な正規表現を実行することです。

ただし、この方法を使用する場合は、メンテナンスが容易で、高速で、バグが発生しにくいANTLRのようなものを実際に試してみてください。

于 2008-09-25T15:40:47.287 に答える