Эффективное сопоставление нескольких регулярных выражений в Python
https://stackoverflow.com/questions/133886
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Лексические анализаторы довольно легко писать, когда у вас есть регулярные выражения.Сегодня я хотел написать простой общий анализатор на 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.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]
Я нашел это в документе 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.
re.match стоит на якоре.Вы можете привести к этому аргумент позиции:
pos = 0
end = len(text)
while pos < end:
match = regexp.match(text, pos)
# do something with your match
pos = match.end()
Поищите pygments, который поставляет кучу лексеров для подсветки синтаксиса с различными реализациями, большинство из которых основаны на регулярных выражениях.
Возможно, что объединение регулярных выражений токенов сработает, но вам придется сравнить его.Что -то вроде:
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
Для этого вы получите примерно такую же скорость (может быть, чуть быстрее).Я считаю, что ускорение должно заключаться в количестве совпадающих вызовов, но цикл для распознавания токенов все еще существует, что, конечно, убивает его.
Это не совсем прямой ответ на ваш вопрос, но вы, возможно, захотите взглянуть на ANTLR.Согласно это документируйте, что цель генерации кода python должна быть актуальной.
Что касается ваших регулярных выражений, то на самом деле есть два способа ускорить процесс, если вы придерживаетесь регулярных выражений.Первым было бы упорядочить ваши регулярные выражения в порядке вероятности их нахождения в тексте по умолчанию.Вы могли бы подумать о добавлении простого профилировщика к коду, который собирает количество токенов для каждого типа токенов, и запуске лексера для выполнения всего объема работы.Другим решением было бы выполнить сортировку ваших регулярных выражений (поскольку ваше ключевое пространство, являющееся символом, относительно невелико), а затем использовать массив или словарь для выполнения необходимых регулярных выражений после выполнения единственного распознавания первого символа.
Тем не менее, я думаю, что если вы собираетесь пойти по этому пути, вам действительно следует попробовать что-то вроде ANTLR который будет проще в обслуживании, быстрее и с меньшей вероятностью появления ошибок.
