Faites correspondre efficacement plusieurs expressions rationnelles en Python
https://stackoverflow.com/questions/133886
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Les analyseurs lexicaux sont assez faciles à écrire lorsque vous avez des regex. Aujourd'hui, je voulais écrire un analyseur général simple en Python et j'ai proposé:
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
Cela fonctionne très bien, mais je crains un peu que ce soit trop inefficace. Existe-t-il des astuces regex qui me permettent de l'écrire de manière plus efficace / élégante?
Plus précisément, y a-t-il un moyen d'éviter de faire une boucle sur toutes les règles de regex de manière linéaire pour en trouver une qui convient?
La solution
Vous pouvez fusionner toutes vos expressions rationnelles en une seule à l'aide de " | | " opérateur et laissez la bibliothèque regex faire le travail de discernement entre les jetons. Il convient de veiller à privilégier les jetons (par exemple, pour éviter de faire correspondre un mot clé à un identifiant).
Autres conseils
Je suggère d'utiliser la classe re.Scanner, elle n'est pas documentée dans la bibliothèque standard, mais vaut la peine d'être utilisée. Voici un exemple:
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]
J'ai trouvé this dans un document python. C'est simple et élégant.
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)
Le truc ici est la ligne:
tok_regex = '|'.join('(?P<%s>%s)' % pair for pair in token_specification)
Ici (?P<ID>PATTERN) marquera le résultat correspondant avec un nom spécifié par ID.
re.match est ancré. Vous pouvez lui donner un argument de position:
pos = 0
end = len(text)
while pos < end:
match = regexp.match(text, pos)
# do something with your match
pos = match.end()
Jetez un œil à pygments qui fournit une multitude de lexers à des fins de mise en évidence de la syntaxe avec différentes implémentations, la plupart basées sur des expressions régulières.
Il est possible que la combinaison des expressions rationnelles de jetons fonctionne, mais vous devrez le comparer. Quelque chose comme:
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]
Le filtre est l'endroit où vous devrez effectuer des analyses comparatives ...
Mise à jour: j'ai testé cela. Il semble que vous combiniez tous les jetons comme indiqué et que vous écriviez une fonction telle que:
def find_token(lst):
for tok in lst:
if tok[1] != None: return tok
raise Exception
Vous obtiendrez à peu près la même vitesse (peut-être un peu plus vite) pour cela. Je crois que l'accélération doit être dans le nombre d'appels à faire correspondre, mais la boucle pour la discrimination de jeton est toujours là, ce qui le tue bien sûr.
Ce n’est pas une réponse directe à votre question, mais vous pouvez également consulter ANTLR . Selon le ce document, la cible de génération de code python devrait être active à ce jour.
En ce qui concerne vos expressions rationnelles, il existe vraiment deux façons de l’accélérer si vous vous en tenez à des expressions rationnelles. La première serait de classer vos expressions rationnelles dans l'ordre de la probabilité de les trouver dans un texte par défaut. Vous pouvez imaginer l'ajout d'un profileur simple au code qui recueille le nombre de jetons pour chaque type de jeton et l'exécution du lexer sur un corps de travail. L’autre solution consisterait à trier vos expressions rationnelles (votre espace clé étant un caractère relativement petit), puis à utiliser un tableau ou un dictionnaire pour effectuer les expressions rationnelles nécessaires après avoir effectué une discrimination unique sur le premier caractère.
Cependant, je pense que si vous choisissez cette voie, vous devriez vraiment essayer quelque chose comme ANTLR qui sera plus facile à entretenir, plus rapide et moins susceptible d’avoir des bugs.
