python3 - python string expresiones regulares

Combina eficientemente múltiples expresiones regulares en Python

Question

Los analizadores léxicos son bastante fáciles de escribir cuando tienes expresiones regulares. Hoy quería escribir un analizador general simple en Python, y se me ocurrió:

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

Funciona bien, pero estoy un poco preocupado de que sea demasiado ineficiente. ¿Hay algún truco de expresiones regulares que me permita escribirlo de una manera más eficiente / elegante?

Específicamente, ¿hay alguna forma de evitar el bucle sobre todas las reglas de expresión regular de forma lineal para encontrar una que encaje?

Answer 1

Encontré esto en el documento de Python. Es simple y 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)

El truco aquí es la línea:

tok_regex = ''|''.join(''(?P<%s>%s)'' % pair for pair in token_specification)

Aquí (?P<ID>PATTERN) marcará el resultado coincidente con un nombre especificado por ID .

Answer 2

Esta no es exactamente una respuesta directa a su pregunta, pero es posible que desee ver ANTLR . De acuerdo con este documento, el objetivo de generación de código python debería estar actualizado.

En cuanto a tus expresiones regulares, en realidad hay dos maneras de acelerar el proceso si te limitas a las expresiones regulares. La primera sería ordenar sus expresiones regulares en el orden de la probabilidad de encontrarlas en un texto predeterminado. Podría figurar agregar un generador de perfiles simple al código que recopila los recuentos de tokens para cada tipo de token y ejecutar el lexer en un cuerpo de trabajo. La otra solución sería agrupar las expresiones regulares (ya que su espacio clave, que es un carácter, es relativamente pequeño) y luego usar una matriz o diccionario para realizar las expresiones regulares necesarias después de realizar una única discriminación en el primer carácter.

Sin embargo, creo que si vas a seguir esta ruta, deberías probar algo como ANTLR, que será más fácil de mantener, más rápido y con menos probabilidades de tener errores.

Answer 3

Puede fusionar todas sus expresiones regulares en una utilizando el "|" operador y deje que la biblioteca de expresiones regulares haga el trabajo de discernir entre tokens. Se debe tener cuidado para garantizar la preferencia de los tokens (por ejemplo, para evitar que coincida una palabra clave como un identificador).

Answer 4

re.match está anclado. Puedes darle un argumento de posición:

pos = 0
end = len(text)
while pos < end:
    match = regexp.match(text, pos)
    # do something with your match
    pos = match.end()

Busque pygments que envíe una gran cantidad de lexers para resaltar la sintaxis con diferentes implementaciones, la mayoría basadas en expresiones regulares.

Answer 5

Es posible que la combinación de las expresiones regulares token funcione, pero tendría que compararla. 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]

El filtro es donde tendrás que hacer una evaluación comparativa ...

Actualización: Probé esto, y parece que si combinas todos los tokens como se indica y escribes una función como:

def find_token(lst):
    for tok in lst:
        if tok[1] != None: return tok
    raise Exception

Obtendrá aproximadamente la misma velocidad (tal vez un poco más rápido) para esto. Creo que la aceleración debe estar en el número de llamadas para que coincida, pero el ciclo para la discriminación de token todavía está allí, lo que por supuesto lo mata.

Answer 6

estos no son tan simples, pero puede valer la pena mirar ...

Python module pyparsing (pyparsing.wikispaces.com) permite especificar la gramática y luego usarla para analizar el texto. Douglas, gracias por el post sobre ANTLR. No he oído hablar de él. También existe la implementación de lex / yacc compatible con PLY - python2 y python3.

Primero escribí un analizador basado en expresiones regulares ad-hoc, pero más tarde me di cuenta de que podría beneficiarme del uso de una herramienta de análisis madura y de aprender conceptos de gramática independiente del contexto, etc.

La ventaja de utilizar la gramática para el análisis es que puede modificar fácilmente las reglas y formalizar una sintaxis bastante compleja para lo que sea que esté analizando.

Answer 7

Sugiero usar la clase re.Scanner, no está documentada en la biblioteca estándar, pero vale la pena usarla. Aquí hay un ejemplo:

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]