Eficientemente combinar múltiplas expressões regulares em Python
https://stackoverflow.com/questions/133886
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
analisadores lexicais são bastante fáceis de escrever quando você tem expressões regulares. Hoje eu queria escrever um analisador geral simples em Python, e veio com:
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
Ele funciona muito bem, mas estou um pouco preocupado que é muito ineficiente. Há algum truques regex que permita-me a escrevê-lo de uma forma mais eficiente / elegante?
Especificamente, há uma maneira de evitar um loop sobre todas as regras regex linearmente para encontrar um que se encaixa?
Solução
Você pode mesclar todas as suas expressões regulares em um usando o "|" operador e deixar a biblioteca regex fazer o trabalho de discernir entre tokens. Alguns cuidados devem ser tomados para garantir a preferência de tokens (por exemplo, para evitar que combinam com uma palavra-chave como um identificador).
Outras dicas
Eu sugiro usar a classe re.Scanner, não é documentado na biblioteca padrão, mas vale bem a pena usar. Aqui está um exemplo:
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]
este no documento python. É apenas simples e elegante.
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)
O truque aqui é a linha:
tok_regex = '|'.join('(?P<%s>%s)' % pair for pair in token_specification)
Aqui (?P<ID>PATTERN) marcará o resultado combinado com um nome especificado pelo ID.
re.match está ancorado. Você pode dar-lhe um argumento posição:
pos = 0
end = len(text)
while pos < end:
match = regexp.match(text, pos)
# do something with your match
pos = match.end()
Tenha um olhar para pygments que vem uma porrada de lexers para sintaxe fins com diferentes implementações destacando, a maioria com base em expressões regulares.
É possível que a combinação dos regexes simbólicos irá funcionar, mas você teria que benchmark. Algo como:
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]
O filtro é onde você vai ter que fazer alguma análise comparativa ...
Update: Eu testei isso, e parece que se você combinar todas as fichas como indicado e escrever uma função como:
def find_token(lst):
for tok in lst:
if tok[1] != None: return tok
raise Exception
Você terá aproximadamente a mesma velocidade (talvez um teensy mais rápido) para isso. Eu acredito que a aceleração deve estar no número de chamadas para jogo, mas o loop para a discriminação sinal ainda está lá, o que naturalmente mata-lo.
Esta não é exatamente uma resposta directa à sua pergunta, mas você pode querer olhar para ANTLR . De acordo com a este documento o alvo python geração de código deve ser para cima à data.
Quanto à sua expressões regulares, há realmente duas maneiras de ir sobre a acelerar se você está aderindo a expressões regulares. A primeira seria a de ordenar suas expressões regulares na ordem da probabilidade de encontrá-los em um texto padrão. Você poderia imaginar a adição de um profiler simples para o código que recolheu as contagens de token para cada tipo de token e executando o lexer em um corpo de trabalho. A outra solução seria balde tipo suas expressões regulares (uma vez que o seu espaço de chave, sendo um personagem, é relativamente pequeno) e, em seguida, usar uma matriz ou dicionário para executar as expressões regulares necessárias após a realização de um único discriminação com o primeiro caractere.
No entanto, penso que, se você estiver indo para percorrer este caminho, você deve realmente tentar algo como ANTLR que será mais fácil de manter, mais rápido e menos propensos a ter bugs.
