Una herramienta importante y útil que ya forma parte del arsenal de la mayoría de los programadores es la expresión regular de confianza . Pero más allá de eso se encuentran las gramáticas libres de contexto. Este es un concepto simple con un nombre elegante.
Una expresión regular es un método para validar y encontrar patrones en el texto. Los tipos de patrones (también conocidos como gramáticas) que pueden describirse y detectarse mediante una expresión regular se denominan lenguajes regulares . Los lenguajes regulares son los lenguajes formales más simples de la jerarquía de Chomsky .
Las expresiones regulares son excelentes para encontrar o validar muchos tipos de patrones simples, por ejemplo, números de teléfono, direcciones de correo electrónico y URL. Sin embargo, se quedan cortos cuando se aplican a patrones que pueden tener una estructura recursiva, como:
- Etiquetas HTML / XML para abrir / cerrar
- llaves para abrir / cerrar {/} en lenguajes de programación
- abrir / cerrar paréntesis en expresiones aritméticas
Para analizar este tipo de patrones, necesitamos algo más poderoso. Podemos pasar al siguiente nivel de gramáticas formales llamadas gramáticas libres de contexto (CFG).
Analizar expresiones matemáticas
Analizar el conjunto de todas las expresiones matemáticas está más allá del poder de una verdadera expresión regular. La razón es que estos pueden contener pares de paréntesis anidados arbitrariamente profundos.
Por ejemplo, considere la expresión: (2 + (3 * (7–4)))
Observe que la estructura de la expresión aritmética es efectivamente un árbol:
+ / \ 2 * / \ 3 - / \ 7 4La estructura de árbol generada como resultado de ejecutar un analizador CFG se denomina árbol de análisis .
Describir gramáticas libres de contexto
Hay dos métodos populares para expresar las gramáticas CFG:
- Formulario extendido de Bachus-Naur (EBNF): describe un CFG en términos de reglas de producción . Son reglas que, aplicadas, pueden generar todas las frases legales posibles en el idioma.
- Análisis gramatical de expresión (PEG): describe un CFG en términos de reglas de reconocimiento . Estas son reglas que se pueden usar para hacer coincidir frases válidas en el idioma.
El formalismo PEG tiene la ventaja sobre EBNF de que la asignación a un analizador no es ambigua y se puede automatizar fácilmente.
El siguiente es un PEG simple extraído de su página de Wikipedia que describe fórmulas matemáticas que aplican las cuatro operaciones básicas a no negativos
enteros.
Expr ← SumSum ← Product ((‘+’ / ‘-’) Product)*Product ← Value ((‘*’ / ‘/’) Value)*Value ← [0–9]+ / ‘(‘ Expr ‘)’En inglés simple, podemos leer esto como:
Expres unSumSumes unProductseguido de cero o más subpatrones que constan de un "+" o "-" seguido de unProductProductes unValueseguido de cero o más subpatrones que constan de un "*" o "/" seguido de unValueValuees uno o más miembros del juego de caracteres {0, .. 9}, o es un paréntesis abierto "(" seguido de unExprparéntesis de cierre ")".
Generadores de analizadores versus bibliotecas de análisis
Suponiendo que no eres el tipo de persona a la que le gusta reinventar la rueda (no es que haya nada de malo en eso), generalmente hay dos opciones para crear un analizador:
1. Utilice un generador de analizador sintáctico : una herramienta que genera el código fuente de un analizador sintáctico a partir de una definición abstracta del analizador sintáctico. Algunos ejemplos populares en JavaScript incluyen Jison, PEG.js, nearley y ANTLR.
2. Utilice una biblioteca de análisis : una biblioteca que permite la expresión de las reglas de análisis como una API. Algunos ejemplos en JavaScript incluyen Myna, Parsimmon y Chevrotain.
Mi preferencia es utilizar bibliotecas de análisis, porque son más fáciles de entender, depurar, mantener y personalizar.
Escribir analizadores en TypeScript / JavaScript utilizando la biblioteca de análisis de Myna
Recientemente, un proyecto en el que estaba trabajando (el lenguaje Heron) requería una biblioteca de análisis que pudiera ejecutarse en el navegador. Encontré la complejidad y la sobrecarga de las bibliotecas existentes demasiado grandes. Dado que tenía experiencia previa en la escritura de bibliotecas de análisis en C ++ y C #, decidí escribir una biblioteca de análisis llamada Myna usando TypeScript.
Myna usa una sintaxis fluida (encadenamiento de métodos) para facilitar la definición de un analizador como un conjunto de reglas (sub-analizador) que se asemejan a una gramática PEG.
El siguiente ejemplo es del repositorio de Myna GitHub:
Del árbol de sintaxis concreto (CST) al árbol de sintaxis abstracto (AST)
Cuando un analizador procesa la entrada, cada regla coincidente con éxito (también conocida como producción gramatical) se puede asignar a un nodo en el árbol de análisis. Este mapeo literal de reglas de producción a nodos en un árbol es un árbol de sintaxis concreto (CST).
En algunos casos, el CST tiene un uso limitado ya que contiene una gran cantidad de desorden sintáctico, por ejemplo, comentarios en el código fuente, o si un literal de cadena tiene comillas dobles o simples. Puede contener resultados de reglas que se crean para facilitar el uso de la gramática, pero no representan la estructura de árbol prevista para el análisis.
Lo más sencillo es crear solo nodos en el árbol de salida para reglas específicas y omitir otras reglas. Esta versión simplificada del árbol de análisis se denomina árbol de sintaxis abstracta (AST) . Puede haber varias pasadas realizadas en un AST para transformarlo en representaciones AST alternativas, para simplificar los pasos de procesamiento posteriores.
En Myna, un AST se genera creando nodos a partir de reglas etiquetadas con la astpropiedad. Técnicamente, esta propiedad devuelve una nueva regla que tiene un conjunto de propiedades internas que le dice al analizador que genere un nodo de análisis en el árbol de análisis.
Usando el árbol de sintaxis abstracto generado de Myna
A continuación, se muestra un ejemplo del uso de un analizador definido por Myna en "Node.JS" para evaluar una expresión aritmética:
Ultimas palabras
Si está interesado en aprender más sobre la creación y el uso de analizadores, independientemente de que la biblioteca de Myna satisfaga sus necesidades específicas, le animo a que se tome un poco de tiempo para leer el código fuente de la biblioteca de análisis de Myna.
Myna fue escrito en TypeScript (que tiene una sintaxis familiar para la mayoría de los programadores), está contenido en un solo archivo sin dependencias y tiene menos de 1200 líneas, incluida la documentación detallada.
Si está interesado en ver a Myna aplicada a un escenario más complejo, eche un vistazo al lenguaje de programación Chickadee. Esto se implementa completamente en TypeScript y depende solo de la biblioteca de análisis de Myna. Chickadee es un pequeño lenguaje de programación diseñado específicamente para ayudar a las personas a aprender técnicas de implementación de lenguajes de programación.
Si le gustó este artículo, hágamelo saber y considere compartirlo con sus amigos y colegas.