¿Pautas de diseño para el analizador y el lexer?

Question

Escribo un lexer (con re2c) y un analizador (con Lemon) para un formato de datos ligeramente intrincado: similar al CSV, pero con tipos de cadena específicos en lugares específicos (caracteres alfanuméricos solamente, caracteres alfanuméricos y signos menos, cualquier char excepto comillas y coma pero con llaves equilibradas, etc.), cadenas dentro de llaves y cadenas que parecen llamadas de función con llaves de apertura y cierre que pueden contener parámetros.

La primera vez que lo vi fue un lexer con muchos estados, cada estado atendiendo el formato de cadena específico. Pero después de muchos mensajes inútiles de "entrada inesperada" del lexer (que se hizo muy grande) me di cuenta de que tal vez estaba intentando hacer el trabajo del analizador sintáctico. Deseché mi primer intento y fui con un lexer con solo un estado, muchos tokens de caracteres y un analizador que combina los tokens en los diferentes tipos de cadenas. Esto funciona mejor, obtengo más errores de sintaxis útiles del analizador cuando algo está apagado, pero todavía no se siente del todo bien. Estoy pensando en agregar uno o dos estados al lexer, pero iniciando los estados desde el analizador sintáctico, que tiene una "descripción general" mucho mejor sobre qué tipo de cadena se requiere en una instancia determinada. En general, me siento un poco estúpido :(

No tengo antecedentes formales de CS y me alejo un poco de la teoría de las matemáticas pesadas. Pero tal vez haya un tutorial o libro en algún lugar que explique qué debería hacer (y no debería) qué y qué parte del trabajo debe hacer el analizador sintáctico. Cómo construir buenos patrones de tokens, cuándo usar estados lexer, cuándo y cómo usar reglas recursivas (con un analizador LALR), cómo evitar reglas ambiguas. Un libro de cocina pragmático que enseña Lo básico. El "Primer/CÓDIGO Lex y YACC" fue agradable, pero no lo suficiente. Como solo quiero analizar un formato de datos, los libros sobre compilación (como el libro rojo del dragón) parecen un poco demasiado grandes.

O tal vez alguien me puede dar algunas reglas simples aquí.

Answer 1

Lo que realmente debe hacer es escribir una gramática para su idioma. Una vez conseguido eso, el límite es fácil:

• El analizador léxico es responsable de llevar a su entrada y que le dice lo que terminal de que tiene.
• El analizador es responsable de que coincide con una serie de terminales y no terminales a una regla de producción, en repetidas ocasiones, hasta que o bien tienen un árbol de análisis o un fracaso de análisis.

El analizador léxico no es responsable de la validación de entrada, excepto en la medida en que rechace personajes imposibles, y otros bits demuy básicas. El analizador hace todo eso.

Eche un vistazo a http://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html. Es una introducción al curso de CS en el análisis.

Answer 2

Una buena prueba de fuego para decidir si algo debe hacerse mediante un analizador léxico o es hacerse una pregunta:

¿La sintaxis tiene ningún anidados elementos de auto-similares, recursivas,?
(por ejemplo, paréntesis anidados, llaves, etiquetas, subexpresiones, subsentencias, etc.).

De lo contrario, las expresiones regulares simples son suficientes y el lexer podría hacerlo.
En caso afirmativo, debe analizarlo un analizador porque, al menos, es una gramática libre de contexto.

Lexer es generalmente para encontrar "palabras" de su idioma y clasificarlas (¿es un sustantivo?¿un verbo? ¿un adjetivo? etc.).
Parser es para encontrar "oraciones" apropiadas, estructurarlas y encontrarlas si son oraciones correctas en un idioma determinado.