Análisis sin escáner

En informática , el análisis sin escáner (también llamado análisis sin lexer ) realiza la tokenización (dividir un flujo de caracteres en palabras) y el análisis (organizar las palabras en frases) en un solo paso, en lugar de dividirlo en una canalización de un lexer seguido de un analizador , ejecutándose simultáneamente . Una gramática de un idioma no tiene escáner si utiliza un formalismo único para expresar la estructura léxica (nivel de palabra) y de frase del idioma.

Dividir el procesamiento en un lexer seguido de un analizador es más modular; El análisis sin escáner se utiliza principalmente cuando una distinción clara entre lexer y analizador es innecesaria o no deseada. Ejemplos de cuándo esto es apropiado incluyen TeX , la mayoría de las gramáticas wiki , archivos MAKE , lenguajes de secuencias de comandos simples específicos de aplicaciones y Raku .

Ventajas

Sólo se necesita un metalenguaje
La estructura léxica no regular se maneja fácilmente
La "clasificación de tokens" no es necesaria, lo que elimina la necesidad de adaptaciones de diseño como " el truco de Lexer " y palabras reservadas de idioma (como "mientras" en C ).
Las gramáticas pueden ser compositivas (se pueden fusionar sin intervención humana) ^[a]

Desventajas

Dado que se combinan el escaneo léxico y el análisis sintáctico, el analizador resultante tiende a ser más complicado y, por lo tanto, más difícil de entender y depurar. Lo mismo se aplicará a la gramática asociada, si se utiliza una gramática para generar el analizador.
El analizador resultante tiende a ser significativamente menos eficiente que una canalización de analizador Lexer con respecto al tiempo y la memoria. ^[1]

Implementaciones

SGLR es un analizador para el formalismo de definición de sintaxis modular (SDF) y es parte del metaentorno ASF+SDF y del sistema de transformación de programas Stratego/XT.
JSGLR, una implementación Java pura de SGLR, también basada en SDF.
TXL admite el análisis a nivel de carácter.
dparser genera código ANSI C para analizadores GLR sin escáner .
Spirit permite el análisis tanto sin escáner como basado en escáner.
SBP es un analizador sin escáner para gramáticas booleanas (un superconjunto de gramáticas libres de contexto), escrito en Java.
Laja es un generador de analizador sin escáner de dos fases con soporte para mapear reglas gramaticales en objetos, escrito en Java.
Las gramáticas Raku son características del lenguaje de programación de propósito general Raku .
PyParsing es un analizador sin escáner escrito en Python puro.
META II Tiene funciones de analizadores de tokens integradas.
TREE-META Al igual que META II, tampoco tiene escáner y tiene funciones Lexer integradas.
Compilador CWIC para escribir e implementar compiladores. Tiene reglas simbólicas como parte de su lenguaje. Las reglas del CWIC se compilaron en funciones booleanas que devolvían el éxito o el fracaso.

Notas

^a Esto se debe a que el análisis a nivel de caracteres hace que el lenguaje reconocido por el analizador sea un lenguaje único libre de contexto definido en caracteres, a diferencia de un lenguaje libre de contexto de secuencias de cadenas en los lenguajes normales . Algunos analizadores sin lexer manejan toda la clase de lenguajes libres de contexto, que está cerrada bajo composición.

Referencias

^ Economopoulos, Giorgios; Klint, Pablo; Vinju, Jürgen (2009). "Análisis GLR sin escáner más rápido" (PDF) . Construcción del compilador . Apuntes de conferencias sobre informática. vol. 5501, págs. 126-141. doi : 10.1007/978-3-642-00722-4_10 . ISBN 978-3-642-00721-7.

Otras lecturas

Visser, E. (agosto de 1997). Análisis LR generalizado sin escáner . Países Bajos: Universidad de Amsterdam. CiteSeerX 10.1.1.37.7828 .