Match Effizientes mehrere reguläre Ausdrücke in Python
https://stackoverflow.com/questions/133886
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Die lexikalischen Analysatoren sind recht einfach zu schreiben, wenn Sie reguläre Ausdrücke haben. Heute wollte ich einen einfachen allgemeinen Analysator in Python schreiben, und kam mit:
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
Es funktioniert ganz gut, aber ich bin ein bisschen besorgt, dass es zu ineffizient ist. Gibt es regex Tricks, die mir erlauben, es in einer effizienteren / elegante Art und Weise zu schreiben?
Insbesondere ist es eine Möglichkeit, Schleifen über alle regex Regeln zu vermeiden linear zu finden, das passt?
Lösung
Sie können alle Ihre regulären Ausdrücke zu einer Einheit verschmelzen mit dem „|“ Betreiber und lassen Sie die regex Bibliothek die Arbeit der anspruchsvollen zwischen Token. Einige sollte darauf geachtet werden, die Bevorzugung von Tokens, um sicherzustellen, (zum Beispiel ein Schlüsselwort als Bezeichner zu vermeiden Anpassung).
Andere Tipps
Ich schlage vor, die re.Scanner-Klasse, es ist nicht in der Standard-Bibliothek dokumentiert, aber es lohnt sich verwenden. Hier ein Beispiel:
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]
Ich fand dieser in Python-Dokument. Es ist nur einfach und elegant.
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)
Der Trick hier ist die Zeile:
tok_regex = '|'.join('(?P<%s>%s)' % pair for pair in token_specification)
Hier (?P<ID>PATTERN) das verglichenen Ergebnis mit einem Namen von ID angegeben markieren.
re.match verankert ist. Sie können eine Position Argument geben:
pos = 0
end = len(text)
while pos < end:
match = regexp.match(text, pos)
# do something with your match
pos = match.end()
Haben Sie einen Blick für pygments die Schiffe eine Unmenge von lexers für Syntax-Hervorhebung Zwecke mit unterschiedlichen Implementierungen, die meisten basieren auf regulären Ausdrücken.
Es ist möglich, dass der Token Regexes Kombination funktioniert, aber man würde es Benchmark hat. So etwas wie:
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]
Der Filter ist, wo Sie müssen einige Benchmarking tun ...
Update: Getestet habe ich diese, und es scheint, als ob, wenn Sie alle Token kombinieren, wie eine Funktion wie angegeben und schreiben:
def find_token(lst):
for tok in lst:
if tok[1] != None: return tok
raise Exception
Sie werden in etwa die gleiche Geschwindigkeit bekommen (vielleicht ein teensy schneller) für diese. Ich glaube, die Beschleunigung in der Anzahl der Anrufe werden müssen übereinstimmen, aber die Schleife für Token Diskriminierung ist immer noch da, was natürlich tötet es.
Dies ist nicht gerade eine direkte Antwort auf Ihre Frage, aber Sie könnten aussehen wollen unter ANTLR . Nach diesem Dokument des Python Code-Generierung Ziel soll bis sein aktuell sind.
In Bezug auf Ihre regulären Ausdrücke gibt es wirklich zwei Möglichkeiten, es zu beschleunigen zu gehen, wenn Sie reguläre Ausdrücke sind kleben. Die erste wäre Ihre reguläre Ausdrücke in der Reihenfolge der Wahrscheinlichkeit bestellen von ihnen in einem Standardtext zu finden. Sie könnten Figur, die einen einfachen Profiler, um den Code hinzufügen, die für jeden Token-Typ Tokenzählungen gesammelt und den Betrieb der Lexer auf einem Körper der Arbeit. Die andere Lösung wäre, um Ihre reguläre Ausdrücke Bucketsort (da Ihren Schlüsselraum, ist ein Zeichen, relativ klein ist) und dann einen Array oder ein Wörterbuch verwenden, um die benötigten Regexes durchführen, nachdem eine einzelne Diskriminierung auf dem ersten Zeichen durchgeführt wird.
Aber ich denke, dass, wenn Sie diesen Weg gehen gehst, du wirklich etwas versuchen sollten, wie ANTLR was leichter zu pflegen, schneller und weniger wahrscheinlich, Fehler zu haben.
