Los analizadores son programas que ayudan a procesar el texto. Los compiladores e intérpretes usan analizadores para analizar programas antes de procesarlos más, y analizadores para formatos como JSON y YAML procesan texto en las estructuras de datos nativas del lenguaje de programación.
En este artículo, vamos a ver cómo construir "analizadores de descenso recursivos". Los analizadores descendentes recursivos son una forma simple pero poderosa de crear analizadores:para cada "entidad" en el texto que desea procesar, define una función.
Primero, vamos a ver algunas de las teorías subyacentes al análisis. Luego, usando Python, vamos a construir una calculadora y un analizador JSON que admita comentarios, comas finales y cadenas sin comillas. Finalmente, discutiremos cómo puede crear analizadores para otros tipos de lenguajes que se comporten de manera diferente a los ejemplos mencionados anteriormente.
Si ya está familiarizado con la teoría, puede pasar directamente a las partes donde construimos el analizador.
Contenido
- 1 ¿Cómo funciona el análisis?
- 2 Escribir reglas de producción
- 3 consideraciones al construir analizadores
- 3.1 Manejo de precedencia en gramáticas
- 3.2 Evitar la recursividad por la izquierda
- 3.3 Evitar el retroceso
- 4 Construyendo una base para el analizador de descenso recursivo en Python
- 4.1 La clase de excepción
- 4.2 La clase de analizador base
- 4.3 Procesamiento de rangos de caracteres
- 4.4 Extraer caracteres del texto
- 4.5 Extracción de palabras clave y símbolos
- 4.6 Un ayudante para emparejar múltiples producciones
- 4.7 Mirando hacia el futuro:funciones auxiliares
- 5 Primer ejemplo de analizador:una calculadora
- 5.1 Reglas de producción para la gramática de la calculadora
- 5.2 Implementando el analizador
- 5.3 Reconocer números
- 5.4 Una interfaz para nuestro analizador
- 6 Segundo ejemplo de analizador:un analizador JSON "extendido"
- 6.1 Reglas de producción para la gramática JSON
- 6.2 Implementando el analizador y manejando comentarios
- 6.3 Análisis de listas y mapas
- 6.4 Reconocimiento de valores nulos y booleanos
- 6.5 Reconocimiento de cadenas y números sin comillas
- 6.6 Reconocimiento de cadenas entrecomilladas
- 6.7 Una interfaz para nuestro analizador JSON
- 7 Construcción de otros tipos de analizadores
- 7.1 Idiomas sensibles a los espacios en blanco
- 7.2 Sangría basada en espacios en blanco
¿Cómo funciona el análisis?
Para procesar un fragmento de texto, un programa realiza tres tareas. En un proceso llamado "lexing" o "tokenización", el programa revisa los caracteres del texto y extrae grupos lógicos llamados "tokens". Por ejemplo, en una expresión como “3 + 5 – 10”, un programa para procesar expresiones aritméticas podría extraer los siguientes tokens:
[{ "Type": "Number" , "Text": "3" },
{ "Type": "Operator", "Text": "+" },
{ "Type": "Number" , "Text": "5" },
{ "Type": "Operator", "Text": "-" },
{ "Type": "Number" , "Text": "10" }] Luego, el programa usa reglas para identificar secuencias significativas de tokens, y esto se denomina "análisis". Las reglas que se usan para hacer que esto suceda se llaman "gramáticas", de la misma manera que las palabras de un idioma natural como el inglés se unen en secuencias significativas usando la gramática inglesa. Las reglas individuales de una gramática se denominan “producciones”.
Imagina que estamos construyendo un programa para procesar expresiones matemáticas y solo nos interesan las sumas y restas. Una expresión debe tener un número (como "3"), seguido de cualquier número de operadores y números (como "+ 5"). La regla de análisis se puede visualizar así:
El indica que el grupo puede repetir cualquier número de veces (incluyendo cero).
Finalmente, el programa toma un conjunto de acciones para una regla gramatical. Por ejemplo, después del análisis, nuestro programa matemático necesitaría calcular el valor de la expresión.
Aunque los hemos descrito como pasos separados, un programa puede realizarlos todos a la vez. Hacer todos los pasos a la vez tiene algunas ventajas, y este es el enfoque que vamos a adoptar en este artículo.
Escribir reglas de producción
En el resto de este artículo, usaremos reglas de producción para visualizar gramáticas. Por lo tanto, hemos explicado cómo escribimos las reglas de producción a lo largo de este artículo. Si ha leído previamente un libro de texto sobre análisis, la notación que hemos usado aquí es un poco diferente.
Anteriormente, hemos visto un ejemplo de una producción simple. Cuando la regla gramatical contiene el nombre de un token y el token es bastante simple, es común escribir el texto del token en la gramática. Si consideramos el ejemplo anterior, arroja un + o un - , por lo que podríamos reescribir la regla así:
También hemos visto cómo podemos usar para indicar que algo se repite cualquier número de veces. De manera similar, a indica que algo se repite, pero debe ocurrir al menos una vez. A indica algo que es opcional.
Como ejemplo, supongamos que estamos construyendo un analizador para procesar una lista de condiciones, como "x> 10 e y> 30". Suponga que el and es opcional, por lo que podríamos reescribir esta condición como “x> 10 y> 30”. Podrías diseñar una gramática para lo anterior así:
Cuando hay múltiples alternativas, el orden de las alternativas importa. Para una regla como , deberíamos intentar hacer coincidir primero un "+" y luego un "-". Aunque en este ejemplo trivial puede parecer que el orden no importa, veremos ejemplos más adelante donde el orden se vuelve importante.
Finalmente, una regla de producción solo se enfoca en tokens y otros símbolos gramaticales, ignora los espacios en blanco y los comentarios.
Consideraciones al construir analizadores
Anteriormente, hemos visto algunas gramáticas simples. Sin embargo, al intentar analizar algo más complejo, pueden surgir varios problemas. Vamos a discutirlos aquí.
Manejo de precedencia en gramáticas
Previamente, vimos una gramática que puede manejar una expresión matemática que consta de sumas y restas. Desafortunadamente, no puede extender la misma gramática para multiplicaciones (y divisiones), ya que esas operaciones tienen mayor precedencia que las sumas (y restas).
Para manejar este escenario, debemos diseñar nuestra gramática de modo que el analizador difiera cualquier suma, pero realice multiplicaciones tan pronto como las encuentre. Para lograr esto, dividimos la gramática en dos reglas separadas, como se muestra a continuación:
Tomemos una expresión (como “3 + 2 * 5”) para asegurarnos de que esto realmente funciona. Asumiremos que una vez que nuestro analizador haya terminado de hacer coincidir una regla gramatical, automáticamente calcula la expresión. También usaremos texto subrayado para indicar lo que está buscando el analizador. Además, también hemos omitido las comillas para mayor claridad.
Cuando 2 * 5 se analiza, el analizador devuelve inmediatamente el resultado de 10. Este resultado se recibe en el paso y la suma se realiza al final, dando como resultado 13.
En resumen, debe organizar sus reglas para que los operadores con la precedencia más baja estén en la parte superior, mientras que los que tienen la precedencia más alta estén en la parte inferior.
Evitar la recursión a la izquierda
Anteriormente, mencionamos que un analizador descendente recursivo consta de funciones que procesan "entidades" en el texto. Ahora que conocemos los tokens y las reglas de producción, redefinamos esto un poco más formalmente:cada función en el analizador extrae un token o implementa la lógica de una regla de producción.
Tomemos una gramática simple, como para ver lo que esto realmente significa. Si escribiera el pseudocódigo para esta gramática, se vería así:
def expression():
first_number = number()
read('+')
second_number = number()
# process these two numbers, e.g. adding them
A continuación, considere una gramática que analiza una lista de números separados por comas. Generalmente lo escribirías como:
Ahora, imagina que por alguna razón quisieras evitar el comodín y reescribirlo así:
Esta gramática es teóricamente correcta:elige un solo número del texto o se expande a una lista con un número al final. La segunda lista, a su vez, puede expandirse a otro número o una lista, hasta que el analizador termine de leer el texto.
Sin embargo, hay un problema con este enfoque:¡ingresarías una recursividad infinita! Si intentas llamar al list() función una vez, termina llamándola de nuevo, y así sucesivamente. Podrías pensar que reescribir la gramática podría ayudar. Sin embargo, si intentara escribir una función, leería un solo número y dejaría de analizar. El número que lees puede ser parte de una lista como "2, 4, 6" y no podrás leer los otros números.
Cuando se trata de análisis sintáctico, esto se llama recursión izquierda. El caso que vimos anteriormente implica "recursión izquierda directa", pero también hay "recursión izquierda indirecta", donde A llama a B, B llama a A y así sucesivamente. En cualquier caso, debe reescribir la gramática de otra forma para evitar este problema.
Evitar el retroceso
Suponga que está tratando de construir un analizador que analice una operación de dos números, como "2 + 4", y escribió una gramática de esta manera:
Esta gramática es correcta y también se comportará de la manera esperada y producirá resultados correctos. Sin embargo, esta gramática no es lo que querrías usar.
Para ver por qué este es el caso, considere la cadena de entrada "5 - 2". Primero aplicaremos la regla de suma y analizaremos un número. Entonces, esperaríamos un "+", pero al leer la cadena, obtendremos un "-", lo que significa que tenemos que retroceder y aplicar la regla de resta. Al hacerlo, hemos perdido tiempo y ciclos de CPU analizando un número, solo para descartarlo y analizarlo nuevamente como parte de la regla de resta.
Además, cuando se construyen analizadores que funcionan directamente a partir de flujos de datos, como un socket de red, rebobinar el flujo a menudo no es una opción. En este artículo, solo trataremos con analizadores que tienen todo el texto en la memoria. Sin embargo, es una buena práctica evitar retroceder y, para hacerlo, debe factorizar las partes comunes de la izquierda. Así quedaría nuestra regla después de la factorización:
El paso de factorización está completo y evitará retroceder. Sin embargo, por razones estéticas, simplemente lo escribiremos como:
Construyendo una base para el analizador de descenso recursivo en Python
Ahora que hemos discutido las diversas consideraciones para el análisis, construiremos la calculadora y el analizador JSON. Sin embargo, antes de hacerlo, escribiremos una clase base "Análisis" que tenga algunos métodos para funciones comunes, como reconocer caracteres y manejar errores.
Esta sección puede parecer demasiado larga, pero vale la pena la paciencia. Una vez que complete esta sección, tendrá todas las herramientas para crear analizadores complejos con muy poco código requerido para reconocer tokens e implementar reglas de producción.
La clase de excepción
Dado que esta es la tarea más fácil con diferencia, la abordaremos primero. Definiremos nuestra propia clase de excepción llamada ParseError así:
class ParseError(Exception):
def __init__(self, pos, msg, *args):
self.pos = pos
self.msg = msg
self.args = args
def __str__(self):
return '%s at position %s' % (self.msg % self.args, self.pos)
La clase acepta la posición del texto donde ocurrió el error, un mensaje de error (como una cadena de formato) y los argumentos de la cadena de formato. Veamos cómo puede usar este tipo de excepción:
e = ParseError(13, 'Expected "{" but found "%s"', "[") Cuando intente imprimir la excepción, obtendrá un mensaje con formato como este:
Expected "{" but found "[" at position 13
Tenga en cuenta que no hemos usado un % símbolo dentro de la cadena de formato y sus argumentos (como '"Expected "{" but found "%s"' % "[" ). Esto se maneja en el __str__ método de la clase, donde hemos formateado self.msg con elementos en self.pos .
Ahora, puede preguntarse, ¿por qué queremos formatearlo en el __str__ método, en lugar de escribirlo con un % ? Resulta que usando el % operador para dar formato a una cadena lleva bastante tiempo. Al analizar una cadena, se generarán muchas excepciones cuando el analizador intente aplicar varias reglas. Por lo tanto, hemos diferido el formato de la cadena para cuando sea realmente necesario.
La clase de analizador base
Ahora que tenemos una clase de error en su lugar, el siguiente paso es escribir la clase de analizador. Lo definiremos de la siguiente manera:
class Parser:
def __init__(self):
self.cache = {}
def parse(self, text):
self.text = text
self.pos = -1
self.len = len(text) - 1
rv = self.start()
self.assert_end()
return rv
Aquí verás un cache miembro en el __init__ método:volveremos a explicar por qué es necesario cuando hablemos sobre el reconocimiento de caracteres.
El parse El método es bastante simple:primero, almacena la cadena. Como aún no hemos escaneado ninguna parte de la cadena, estableceremos la posición en -1. Además, almacenaremos el índice máximo de la cadena en self.len . (El índice máximo siempre es uno menos que la longitud de la cadena).
A continuación, comenzaremos a analizar la cadena y comprobaremos si hemos llegado al final de la cadena. Esto es para garantizar que nuestro analizador pueda procesar todo el texto sin que quede nada al final. Después de esto, devolvemos el resultado.
El assert_end El método es simple:verificaremos si la posición actual es menor que el índice máximo. Tenga en cuenta que estos métodos están dentro de la clase, aunque hemos omitido la sangría por simplicidad.
def assert_end(self):
if self.pos < self.len:
raise ParseError(
self.pos + 1,
'Expected end of string but got %s',
self.text[self.pos + 1]
)
A lo largo de nuestro analizador, veremos el carácter que es uno más que el índice actual (self.pos ). Para ver por qué este es el caso, considere que comenzamos con self.pos = -1 , por lo que estaríamos mirando el índice 0. Una vez que hayamos reconocido un carácter con éxito, self.pos va a 0 y miraríamos el carácter en el índice 1, y así sucesivamente. Esta es la razón por la cual el error usa self.pos + 1 .
Con la mayoría de los idiomas, los espacios en blanco entre tokens se pueden descartar de forma segura. Por lo tanto, parece lógico incluir un método que compruebe si el siguiente carácter es un carácter de espacio en blanco y, de ser así, lo “descarte” avanzando a la siguiente posición.
def eat_whitespace(self):
while self.pos < self.len and self.text[self.pos + 1] in " fvrtn":
self.pos += 1
Procesamiento de rangos de caracteres
Ahora, escribiremos una función que nos ayude a reconocer caracteres en el texto. Sin embargo, antes de hacer eso, consideraremos nuestra función desde la perspectiva de un usuario:le daremos un conjunto de caracteres para que coincida con el texto. Por ejemplo, si quisiera reconocer un alfabeto o un guión bajo, podría escribir algo como:
self.char('A-Za-z_')
Le daremos el char método que contiene una lista de caracteres o rangos (como A-Z en el ejemplo anterior). Los rangos se denotan mediante dos caracteres separados por un - . El primer carácter tiene un valor numérico más pequeño que el de la derecha.
Ahora, si el carácter en self.text[self.pos + 1] coincide con algo en el argumento de self.char , lo devolveremos. De lo contrario, generaremos una excepción.
Internamente, procesaremos la cadena en algo que sea más fácil de manejar:una lista con caracteres separados o rangos como ['A-Z', 'a-z', '_'] . Entonces, escribiremos una función para dividir los rangos:
def split_char_ranges(self, chars):
try:
return self.cache[chars]
except KeyError:
pass
rv = []
index = 0
length = len(chars)
while index < length:
if index + 2 < length and chars[index + 1] == '-':
if chars[index] >= chars[index + 2]:
raise ValueError('Bad character range')
rv.append(chars[index:index + 3])
index += 3
else:
rv.append(chars[index])
index += 1
self.cache[chars] = rv
return rv
Aquí, recorremos el chars cadena, buscando un - seguido de otro personaje. Si esta condición coincide y el primer carácter es más pequeño que el último, agregamos el rango completo (como A-Z ) a la lista rv . De lo contrario, agregamos el carácter en chars[index] a rv .
Luego, agregamos la lista en rv al caché. Si vemos esta cadena por segunda vez, la devolveremos desde el caché usando el try ... except KeyError: ... bloque en la parte superior.
Es cierto que podríamos haber proporcionado una lista como ['A-Z', 'a-z', '_'] al char método. Sin embargo, en nuestra opinión, hacerlo de esta manera genera llamadas a char() lucir un poco más limpio.
Extracción de caracteres del texto
Ahora que tenemos un método que da una lista que contiene rangos y caracteres, podemos escribir nuestra función para extraer un carácter del texto. Aquí está el código para el char método:
def char(self, chars=None):
if self.pos >= self.len:
raise ParseError(
self.pos + 1,
'Expected %s but got end of string',
'character' if chars is None else '[%s]' % chars
)
next_char = self.text[self.pos + 1]
if chars == None:
self.pos += 1
return next_char
for char_range in self.split_char_ranges(chars):
if len(char_range) == 1:
if next_char == char_range:
self.pos += 1
return next_char
elif char_range[0] <= next_char <= char_range[2]:
self.pos += 1
return next_char
raise ParseError(
self.pos + 1,
'Expected %s but got %s',
'character' if chars is None else '[%s]' % chars,
next_char
)
Centrémonos primero en el argumento chars=None . Esto le permite llamar al self.char() sin darle un conjunto de caracteres. Esto es útil cuando desea simplemente extraer un carácter sin restringirlo a un conjunto específico. De lo contrario, puede llamarlo con un rango de caracteres, como hemos visto en la sección anterior.
Esta función es bastante sencilla:primero, verificamos si nos hemos quedado sin texto. Luego, elegimos el siguiente carácter y verificamos si chars es None , en cuyo caso podemos incrementar la posición y devolver el carácter inmediatamente.
Sin embargo, si hay un conjunto de caracteres en chars , lo dividimos en una lista de caracteres y rangos individuales, como ['A-Z', 'a-z', '_'] . En esta lista, una cadena de longitud 1 es un carácter y cualquier otra cosa es un rango. Comprueba si el siguiente carácter coincide con el carácter o el rango, y si es así, lo devolvemos. Si no logramos compararlo con nada, sale del ciclo que genera ParseError , indicando que no pudimos obtener el carácter esperado.
El 'character' if chars is None else '[%s]' % chars es solo una forma de proporcionar una excepción más legible. Si chars es None , el mensaje de la excepción sería Expected character but got ... , pero si char se configuró en algo como A-Za-z_ , obtendríamos Expected [A-Za-z_] but got ... .
Más adelante, veremos cómo usar esta función para reconocer tokens.
Extracción de palabras clave y símbolos
Además de extraer caracteres individuales, el reconocimiento de palabras clave es una tarea común al crear un analizador. Estamos usando "palabras clave" para referirnos vagamente a cualquier cadena contigua que sea su "propia entidad", y puede tener espacios en blanco antes y después. Por ejemplo, en JSON { podría ser una palabra clave, y en un lenguaje de programación if , else podría ser una palabra clave, y así sucesivamente.
Este es el código para reconocer palabras clave:
def keyword(self, *keywords):
self.eat_whitespace()
if self.pos >= self.len:
raise ParseError(
self.pos + 1,
'Expected %s but got end of string',
','.join(keywords)
)
for keyword in keywords:
low = self.pos + 1
high = low + len(keyword)
if self.text[low:high] == keyword:
self.pos += len(keyword)
self.eat_whitespace()
return keyword
raise ParseError(
self.pos + 1,
'Expected %s but got %s',
','.join(keywords),
self.text[self.pos + 1],
)
Este método toma palabras clave, como self.keyword('if', 'and', 'or') . El método elimina los espacios en blanco y luego verifica si nos quedamos sin texto para analizar. Luego itera a través de cada palabra clave, verificando si la palabra clave existe en el texto. Si encuentra algo, eliminaremos el espacio en blanco que sigue a la palabra clave y luego devolveremos la palabra clave.
Sin embargo, si no encuentra algo, sale del ciclo que genera ParseError , indicando que no se pudieron encontrar las palabras clave.
Un ayudante para emparejar múltiples producciones
En las secciones anteriores, notó que usamos excepciones para informar errores. También sabemos que para escribir un analizador de descenso recursivo, debe escribir funciones que reconozcan un token o una regla de producción. Ahora, imagina que quisieras analizar un texto simple, donde esperas un número o una palabra. La regla de producción podría verse así:
También supondremos que el texto contiene una palabra. Cuando el analizador intenta buscar un dígito (quizás usando char() ), no lo encontrará y esto hace que genere una excepción. Además, debe eliminar los espacios en blanco antes y después de hacer coincidir una regla de producción. Entonces, el código para item() podría verse así:
def item(self): self.eat_whitespace() try: rv = self.number() except ParseError: rv = self.word() self.eat_whitespace() return rv
¡Esto ya parece mucho para implementar una regla simple! Imagine cómo sería implementar una regla compleja:tendría que usar try...except bloques por todas partes.
Entonces, escribiremos un match() función que eliminará los espacios en blanco e intentará hacer coincidir varias reglas. La función es la siguiente:
def match(self, *rules):
self.eat_whitespace()
last_error_pos = -1
last_exception = None
last_error_rules = []
for rule in rules:
initial_pos = self.pos
try:
rv = getattr(self, rule)()
self.eat_whitespace()
return rv
except ParseError as e:
self.pos = initial_pos
if e.pos > last_error_pos:
last_exception = e
last_error_pos = e.pos
last_error_rules.clear()
last_error_rules.append(rule)
elif e.pos == last_error_pos:
last_error_rules.append(rule)
if len(last_error_rules) == 1:
raise last_exception
else:
raise ParseError(
last_error_pos,
'Expected %s but got %s',
','.join(last_error_rules),
self.text[last_error_pos]
)
Antes de discutir cómo funciona, veamos lo simple que es reescribir nuestro ejemplo anterior usando match() :
def item(self):
return self.match('number', 'word')
Entonces, ¿cómo funciona eso? match() toma un nombre de método para ejecutar (como number o word en el ejemplo anterior). Primero, se deshace del espacio en blanco al principio. Luego, itera sobre todos los nombres de métodos y obtiene cada método usando su nombre a través de getattr() . Luego intenta invocar el método y, si todo va bien, también eliminará los espacios en blanco después del texto. Finalmente, devuelve el valor que recibió llamando al método
Sin embargo, si hay un error, reinicia self.pos al valor que estaba allí antes de intentar hacer coincidir una regla. Luego, intenta seleccionar un buen mensaje de error usando las siguientes reglas:
- Al hacer coincidir varias reglas, muchas de ellas pueden generar un error. El error que se generó después de analizar la mayor parte del texto es probablemente el mensaje de error que queremos.
Para ver por qué este es el caso, considere la cadena "abc1". Intentando llamar a number() fallaría en la posición 0, mientras que word() fallaría en la posición 2. Mirando la cadena, es bastante probable que el usuario quisiera ingresar una palabra, pero cometió un error tipográfico.
- Si dos o más reglas con errores terminan en un "empate", preferimos informar al usuario sobre todas las reglas que fallaron.
El last_error_pos y last_exception realiza un seguimiento de la posición del último error y la excepción, respectivamente. Además, mantenemos una lista last_error_rules para que, en caso de empate, podamos informar al usuario sobre todas las reglas que intentamos hacer coincidir.
En el except ParseError bloque, comparamos la posición del último error y el error actual. Si el error actual es igual, lo consideramos un empate y lo agregamos a la lista. De lo contrario, actualizamos la posición del error, la excepción y la lista de reglas con errores.
Al final, comprobamos cuántas reglas fallaron. Si solo hay uno, last_exception tendría el mejor mensaje de error. De lo contrario, es un empate y se lo haremos saber al usuario con un mensaje como Expected number,word but found ... .
Mirando hacia el futuro:funciones auxiliares
En este punto, tenemos todas las cosas necesarias en nuestro analizador y todas las fallas arrojan excepciones. Sin embargo, a veces queremos hacer coincidir solo un carácter, palabra clave o regla si está allí, sin el inconveniente de manejar excepciones.
Presentaremos tres pequeños ayudantes para hacer precisamente eso. En el caso de una excepción al buscar cosas, estas devolverán None :
def maybe_char(self, chars=None):
try:
return self.char(chars)
except ParseError:
return None
def maybe_match(self, *rules):
try:
return self.match(*rules)
except ParseError:
return None
def maybe_keyword(self, *keywords):
try:
return self.keyword(*keywords)
except ParseError:
return None
El uso de estas funciones es fácil. Así es como podría usarlos:
operator = self.maybe_keyword('+', '-'):
if operator == '+':
# add two numbers
elif operator == '-':
# subtract two numbers
else: # operator is None
# do something else
Primer ejemplo de analizador:una calculadora
Ahora que hemos construido la base para escribir un analizador, construiremos nuestro primer analizador. Podrá analizar expresiones matemáticas con sumas, restas, multiplicaciones, divisiones y también manejar expresiones entre paréntesis como "(2 + 3) * 5".
Comenzaremos visualizando la gramática en forma de reglas de producción.
Reglas de producción para la gramática de la calculadora
Anteriormente hemos visto una gramática para manejar todo excepto las expresiones entre paréntesis:
Ahora, pensemos en cómo encajan las expresiones entre paréntesis en esta gramática. Al evaluar “(2 + 3) * 5”, tendríamos que calcular “(2 + 3)” y reducirlo a un número. Lo que significa que en la gramática anterior, el término "Número" puede referirse a una expresión entre paréntesis o algo que en realidad es un número, como "5".
Por lo tanto, ajustaremos nuestras reglas para acomodar ambos. En la regla para "Término", reemplazaremos "Número" por un término más apropiado como "Factor". "Factor" puede referirse a una expresión entre paréntesis o a un "Número". La gramática modificada se ve así:
Con eso fuera del camino, ¡implementemos las reglas de producción!
Implementación del analizador
Implementaremos nuestro analizador Calculator extendiendo la clase Parser base. Comenzamos definiendo la clase así:
class CalcParser(Parser):
def start(self):
return self.expression()
Anteriormente, al implementar la clase de analizador base, teníamos un start() método para comenzar a analizar. Simplemente llamaremos al expression() método aquí, que definiremos a continuación:
def expression(self):
rv = self.match('term')
while True:
op = self.maybe_keyword('+', '-')
if op is None:
break
term = self.match('term')
if op == '+':
rv += term
else:
rv -= term
return rv
La regla gramatical para . Entonces, comenzamos leyendo un término del texto. Luego configuramos un ciclo infinito y buscamos un "+" o "-". Si no encontramos ninguno, esto significa que hemos terminado de leer la lista de términos adicionales proporcionada por , por lo que podemos salir del bucle.
De lo contrario, leemos otro término del texto. Luego, dependiendo del operador, lo sumamos o lo restamos del valor inicial. Continuamos con este proceso hasta que no consigamos un "+" o "-", y devolvemos el valor al final.
Implementaremos term() de la misma manera:
def term(self):
rv = self.match('factor')
while True:
op = self.maybe_keyword('*', '/')
if op is None:
break
term = self.match('factor')
if op == '*':
rv *= term
else:
rv /= term
return rv A continuación, implementaremos "Factor". Primero intentaremos leer un paréntesis izquierdo, lo que significa que hay una expresión entre paréntesis. Si encontramos un paréntesis, leemos una expresión y el paréntesis de cierre, y devolvemos el valor de la expresión. De lo contrario, simplemente leemos y devolvemos un número.
def factor(self):
if self.maybe_keyword('('):
rv = self.match('expression')
self.keyword(')')
return rv
return self.match('number')
En la siguiente sección, haremos que nuestro analizador reconozca un número.
Reconocer números
Para reconocer un número, necesitamos mirar los caracteres individuales en nuestro texto. Los números constan de uno o más dígitos, opcionalmente seguidos de una parte decimal. La parte decimal tiene un punto (.), seguido de al menos un dígito. Además, los números pueden tener un signo como "+" o "-" delante de ellos, como "-124,33".
Implementaremos el number() método así:
def number(self):
chars = []
sign = self.maybe_keyword('+', '-')
if sign is not None:
chars.append(sign)
chars.append(self.char('0-9'))
while True:
char = self.maybe_char('0-9')
if char is None:
break
chars.append(char)
if self.maybe_char('.'):
chars.append('.')
chars.append(self.char('0-9'))
while True:
char = self.maybe_char('0-9')
if char is None:
break
chars.append(char)
rv = float(''.join(chars))
return rv
Aunque la función es larga, es bastante simple. Tenemos un chars lista en la que ponemos los caracteres del número. Primero, observamos cualquier símbolo "+" o "-" que pueda estar presente antes del número. Si está presente, lo agregamos a la lista. Luego, buscamos el primer dígito obligatorio del número y seguimos buscando más dígitos usando el maybe_char() método. Una vez que obtengamos None a través de maybe_char , sabemos que hemos pasado el conjunto de dígitos y finalizamos el bucle.
Del mismo modo, buscamos la parte decimal y sus dígitos. Finalmente, convertimos todos los caracteres en una cadena, que a su vez convertimos en un número de punto flotante.
Una interfaz para nuestro analizador
Hemos terminado de construir nuestro analizador. Como paso final, agregaremos un poco de código en el alcance global que nos permitirá ingresar expresiones y ver resultados:
if __name__ == '__main__':
parser = CalcParser()
while True:
try:
print(parser.parse(input('> ')))
except KeyboardInterrupt:
print()
except (EOFError, SystemExit):
print()
break
except (ParseError, ZeroDivisionError) as e:
print('Error: %s' % e)
Si has seguido hasta ahora, ¡felicidades! ¡Has creado tu primer analizador de descenso recursivo!
Si está siguiendo un IDE local, puede ejecutar su código en este punto. Alternativamente, puede usar el área de juegos a continuación para ejecutar el analizador. Puede ingresar expresiones a través de la pestaña "Entrada" a continuación:
También puede encontrar el código completo aquí.
Segundo ejemplo de analizador:un analizador JSON "extendido"
JSON es un formato de intercambio de datos que admite estructuras de datos básicas como números, cadenas y listas. Es un formato muy utilizado, aunque su sencillez hace que carezca de comentarios y sea estricto en lo que acepta. Por ejemplo, no puede tener una coma final en una lista o tener un "+" explícito delante de un número para indicar su signo.
Dado que Python ya tiene un módulo JSON, apuntaremos un poco más alto y crearemos un analizador JSON que admita comentarios, comas finales y cadenas sin comillas.
La implementación de este analizador le enseñará cómo manejar los comentarios. También ilustrará cómo crear un lenguaje fácil de usar puede complicar el análisis y cómo puede lidiar con tales situaciones.
Antes de implementar nuestra gramática, tengamos una idea de nuestro formato JSON extendido:
{
# Comments begin with a '#' and continue till the end of line.
# You can skip quotes on strings if they don't have hashes,
# brackets or commas.
Size: 1.5x,
# Trailing commas are allowed on lists and maps.
Things to buy: {
Eggs : 6,
Bread: 4,
Meat : 2,
},
# And of course, plain JSON stuff is supported too!
"Names": ["John", "Mary"],
"Is the sky blue?": true
} Reglas de producción para la gramática JSON
Nuestro JSON extendido se adhiere a los mismos tipos de datos que admite JSON. JSON tiene cuatro tipos de datos primitivos:nulos, booleanos, números y cadenas, y dos tipos de datos complejos:listas (o matrices) y mapas (también llamados hashes o diccionarios). Las listas y hashes tienen un aspecto similar al de Python.
Dado que los datos JSON consistirían en uno de estos tipos, podría escribir las reglas de producción así:
Luego, puede dividir estos dos tipos en tipos de JSON:
Esta gramática está bien para analizar JSON normal, pero necesita algunos ajustes para nuestro caso. Dado que vamos a admitir cadenas sin comillas, lo que significa que "1,5" (sin las comillas) es un número, pero "1,5x" (nuevamente, sin las comillas) es una cadena. Nuestra gramática actual leería "1.5" de "1.5x" y luego causaría un error porque no se esperaba "x" después de un número.
Esto significa que primero tendríamos que obtener el conjunto completo de caracteres sin comillas. A continuación, analizaremos los caracteres y determinaremos si es un número o una cadena. Entonces, combinaremos números y cadenas sin comillas en una sola categoría, "Sin comillas". Las cadenas entre comillas están bien, así que las separaremos en otra categoría, "Cadena entre comillas". Nuestra regla de producción modificada para "PrimitiveType" ahora se ve así:
Además, el orden de las reglas es importante. Dado que tenemos claves sin comillas, primero debemos intentar analizar el texto como nulo o booleano. De lo contrario, podríamos terminar reconociendo "nulo" o "verdadero" como una cadena sin comillas.
Implementación del analizador y manejo de comentarios
Para implementar el analizador JSON, comenzaremos extendiendo la clase de analizador base de la siguiente manera:
class JSONParser(Parser): # ...
Primero abordaremos el problema de tratar con los comentarios. Si lo piensa, los comentarios son muy similares a los espacios en blanco:aparecen en los mismos lugares donde pueden aparecer los espacios en blanco y se pueden descartar al igual que los espacios en blanco. Entonces, volveremos a implementar eat_whitespace() para tratar con los comentarios, así:
def eat_whitespace(self):
is_processing_comment = False
while self.pos < self.len:
char = self.text[self.pos + 1]
if is_processing_comment:
if char == 'n':
is_processing_comment = False
else:
if char == '#':
is_processing_comment = True
elif char not in ' fvrtn':
break
self.pos += 1
Aquí, debemos realizar un seguimiento de si estamos procesando espacios en blanco o un comentario. Recorremos el texto carácter por carácter, comprobando si tenemos espacios en blanco o un # . Cuando hay un # , actualizamos is_processing_comment a True y en las próximas iteraciones del while bucle, podemos descartar con seguridad todos los caracteres hasta llegar al final de la línea. Sin embargo, al procesar caracteres de espacio en blanco, debemos detenernos una vez que aparece un carácter que no es un espacio en blanco.
A continuación, implementaremos las reglas de producción y el start() método. El texto de entrada tendrá un tipo JSON contenido, por lo que simplemente llamaremos a any_type() en el start() método:
def start(self):
return self.match('any_type')
def any_type(self):
return self.match('complex_type', 'primitive_type')
def primitive_type(self):
return self.match('null', 'boolean', 'quoted_string', 'unquoted')
def complex_type(self):
return self.match('list', 'map')
Listas de análisis y mapas
Anteriormente, vimos cómo analizar listas separadas por comas. Las listas de JSON son solo una lista separada por comas con corchetes añadidos, y la lista puede tener cero o más elementos. Veamos cómo implementaría el análisis de una lista:
def list(self):
rv = []
self.keyword('[')
while True:
item = self.maybe_match('any_type')
if item is None:
break
rv.append(item)
if not self.maybe_keyword(','):
break
self.keyword(']')
return rv
Comenzamos leyendo el corchete inicial seguido de un elemento de la lista usando self.maybe_match('any_type') . Si no logramos obtener un elemento, esto indica que probablemente hayamos terminado de revisar todos los elementos, por lo que salimos del ciclo. De lo contrario, agregamos el elemento a la lista. Luego tratamos de leer una coma de la lista, y la ausencia de una coma también indica que hemos terminado con la lista.
De manera similar, los mapas son solo listas separadas por comas de "pares" con llaves, donde un par es una clave de cadena seguida de dos puntos (:) y un valor. A diferencia del dict de Python s que pueden tener cualquier tipo "hashable" como clave (que incluye int s y tuple s), JSON solo admite claves de cadena.
Así es como implementaría las reglas para mapas y pares:
def map(self):
rv = {}
self.keyword('{')
while True:
item = self.maybe_match('pair')
if item is None:
break
rv[item[0]] = item[1]
if not self.maybe_keyword(','):
break
self.keyword('}')
return rv
def pair(self):
key = self.match('quoted_string', 'unquoted')
if type(key) is not str:
raise ParseError(
self.pos + 1,
'Expected string but got number',
self.text[self.pos + 1]
)
self.keyword(':')
value = self.match('any_type')
return key, value
En pair() , tratamos de leer una "Cadena entre comillas" o "Sin comillas" para la clave. Como mencionamos anteriormente, "Sin comillas" puede devolver un número o una cadena, por lo que verificamos explícitamente si la clave que hemos leído es una cadena. pair() luego devuelve una tupla con una clave y un valor, y map() llamadas pair() y los agrega a un dictado de Python.
Reconociendo valores nulos y booleanos
Ahora que las partes principales de nuestro analizador están implementadas, comencemos reconociendo tokens simples como nulos y booleanos:
def null(self):
self.keyword('null')
return None
def boolean(self):
boolean = self.keyword('true', 'false')
return boolean[0] == 't'
None de Python es el análogo más cercano al null de JSON . In the case of booleans, the first characters is sufficient to tell whether it’s true or false , and we return the result of the comparison.
Recognizing unquoted strings and numbers
Before moving on to recognize unquoted strings, let us first define the set of acceptable characters. We’ll leave out anything that’s considered special in such as braces, quotes, colons, hashes (since they are used in comments) and backslashes (because they’re used for escape sequences). We’ll also include spaces and tabs in the acceptable set of characters so that you can write strings like “Things to buy” without using quotes.
So, what are the characters that we want to accept? We can use Python to figure this out:
>>> import string
>>> ''.join(sorted(set(string.printable) - set('{}[]:#"'fvrn')))
't !$%&()*+,-./0123456789;<=>[email protected]^_`abcdefghijklmnopqrstuvwxyz|~'
The next question is, how do you figure out if the text you read is a number or a string? The answer is — we cheat! Since Python’s int() and float() can take a string and return a number, we’ll use them and if those result in a ValueError , we’ll return a string. As for when to use int() or float() , we’ll use a simple rule. If the text contains “E”, “e” or “.”, (for example, “12.3” or “2e10”), we’ll call float(); otherwise, we’ll use int() .
Here’s the code:
def unquoted(self):
acceptable_chars = '0-9A-Za-z t!$%&()*+./;<=>?^_`|~-'
number_type = int
chars = [self.char(acceptable_chars)]
while True:
char = self.maybe_char(acceptable_chars)
if char is None:
break
if char in 'Ee.':
number_type = float
chars.append(char)
rv = ''.join(chars).rstrip(' t')
try:
return number_type(rv)
except ValueError:
return rv
Since matching rules are handled by match() , this takes care of stripping any initial whitespace before unquoted() can run. In this way, we can be sure that unquoted() won’t return a string consisting of only whitespaces. Any whitespace at the end is stripped off before we parse it as a number or return the string itself.
Recognizing quoted strings
Quoted strings are fairly simple to implement. Most programming languages (including Python) have single and double quotes that behave in the same way, and we’ll implement both of them.
We’ll support the following escape sequences — b (backspace), f (line feed), n (newline), r (carriage return), t (tab) and u(four hexadecimal digits) where those digits are used to represent an Unicode “code point”. For anything else that has a backslash followed by a character, we’ll ignore the backslash. This handles cases like using the backslash to escape itself ( ) or escaping quotes (" ).
Here’s the code for it:
def quoted_string(self):
quote = self.char('"'')
chars = []
escape_sequences = {
'b': 'b',
'f': 'f',
'n': 'n',
'r': 'r',
't': 't'
}
while True:
char = self.char()
if char == quote:
break
elif char == '':
escape = self.char()
if escape == 'u':
code_point = []
for i in range(4):
code_point.append(self.char('0-9a-fA-F'))
chars.append(chr(int(''.join(code_point), 16)))
else:
chars.append(escape_sequences.get(char, char))
else:
chars.append(char)
return ''.join(chars)
We first read a quote and then read additional characters in a loop. If this character is the same type of quote as the first character we read, we can stop reading further and return a string by joining the elements of chars .
Otherwise, we check if it’s an escape sequence and handle it in the aforementioned way, and add it to chars . Finally, if it matches neither of them, we treat it as a regular character and add it to our list of characters.
An interface for our JSON parser
To make sure we can interact with our parser, we’ll add a few lines of code that accepts input and parses it as JSON. Again, this code will be in global scope:
if __name__ == '__main__':
import sys
from pprint import pprint
parser = JSONParser()
try:
pprint(parser.parse(sys.stdin.read()))
except ParseError as e:
print('Error: '+ str(e))
To ensure we can read multiple lines, we have used sys.stdin.read() . If you’re going to run this locally, you can enter text and use Ctrl+D to stop the program from asking for more input. Otherwise, you can use this runnable snippet:
You can find the complete code here.
Building other kinds of parsers
Now that we’ve gone through building two parsers, you might have a fairly good idea of how to roll your own for the task at hand. While every language is unique (and therefore, their parsers), there are some common situations that we haven’t covered. For the sake of brevity, we won’t cover any code in these sections.
Whitespace sensitive languages
Before we begin, let us clarify that we’re not referring to languages that use whitespace-based indentation — we’ll cover them in the next section. Here, we’ll discuss languages where the meaning of things change based on the whitespace you put between elements.
An example of such a language would be where “a=10” is different than “a =10”. With bash and some other shells, “a=10” sets an environment variable, whereas “a =10” runs the program “a” with “=” and “10” as command-line arguments. You can even combine the two! Consider this:
a=10 b=20 c = 30
This sets the environment variables “a” and “b” only for the program “c”. The only way to parse such a language is to handle the whitespaces manually, and you’d have to remove all the eat_whitespace() calls in keyword() and match() . This is how you might write the production rules:
Whitespace based indentation
Languages like C and Javascript use curly braces to indicate the body of loops and if-statements. However, Python uses indentation for the same purpose, which makes parsing tricky.
One of the methods to handle this is to introduce a term such as “INDENT” to keep track of indented statements. To see how this would work, consider the following production rule:
After matching a condition, our parser would look for INDENT. Since this is the first time it’s trying to match INDENT, it takes whatever whitespace (except for newlines) that appears along with a non-whitespace character (since that would be part of a statement).
In subsequent iterations, it looks for the same whitespace in the text. If it encounters a different whitespace, it can raise an error. However, if there’s no whitespace at all, it indicates that the “while” loop is finished.
For nested indentations, you’d need to maintain a list of all indentations that you’re currently handling. When the parser handles a new indented block, it should add the new indentation string on the list. You can tell if you’re done parsing the block, by checking that you were able to retrieve less whitespace than you did previously. At this point, you should pop off the last indentation off the list.