Лексические анализаторы довольно легко писать, когда у вас есть регулярные выражения. Сегодня я хотел написать простой общий анализатор в 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 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, который отправляет shitload lexers для целей подсветки синтаксиса с различными реализациями, большинство из которых основано на регулярных выражениях.
Возможно, что объединение выражений с токеном будет работать, но вам нужно будет сравнить его. Что-то вроде:
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, которое будет легче поддерживать, быстрее и с меньшей вероятностью иметь ошибки.
это не так просто, но, возможно, стоит посмотреть...
python module pyparsing (pyparsing.wikispaces.com) позволяет указать грамматику, а затем использовать ее для анализа текста. Дуглас, спасибо за сообщение о ANTLR Я не слышал об этом. Также существует PLY - python2 и совместимая с python3 реализация lex/yacc.
Я сначала написал собственный синтаксический анализатор, основанный на регулярном выражении, но позже понял, что мне может пригодиться использование какого-то зрелого инструмента синтаксического анализа и концепций обучения контекстно-зависимой грамматики и т.д.
Преимущество использования грамматики для синтаксического анализа заключается в том, что вы можете легко модифицировать правила и формализовать довольно сложный синтаксис для того, что вы анализируете.