Eficientemente combinar múltiplas expressões regulares em Python
-
02-07-2019 - |
Pergunta
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.