parsing - top - semantic analysis compilers
¿Hay tal cosa como LL(0) analizadores? (3)
Vi una pregunta en algún lugar que preguntaba la diferencia entre los analizadores LL (0) y LR (0). ¿Existe tal cosa como los analizadores LL (0)? Si es así, ¿cómo se analizan sin mirar ninguna ficha?
Cuando tomé compiladores, nunca hablamos de ellos, aunque sí hablamos de LL (1). No hay mención de ellos en Wikipedia .
Un analizador LL (0) significaría que el analizador podría tomar una decisión sin saber el siguiente token en la secuencia. Yo esperaría que si existen idiomas con esa propiedad, son bastante raros.
La k en LR (k) se refiere al número de tokens de búsqueda anticipada. Siempre se usa al menos un token para determinar la acción a realizar. La página de la página de Wikipedia tiene más información sobre esto.
De manera intuitiva, los símbolos de lookahead adicionales le permiten realizar elecciones de reducción con más información, por lo que permiten que las clases más grandes de gramáticas se expresen sin conflictos.
Los analizadores LL (0) sí miran los tokens, pero no deciden qué producciones aplicar sobre ellos. Solo determinan si la secuencia pertenece al idioma o no. Esto significa que cada símbolo no terminal debe tener un solo lado derecho y que puede no haber recursión.
G == ID name lastname
name == STRING
lastname == STRING
# lexer rules
# -----------
ID == [0-9]+
STRING == <unicode>+
Tenga en cuenta que, como se menciona en @ 280Z28, se necesita un lexer separado para tratar las partes de longitud variable ( ID y STRING ), o la gramática no será LL(0) .
La secuencia de producciones que se aplicarán para analizar una entrada con esa gramática requiere cero lookahead.
Se requiere un lookahead para el determinismo cuando hay más de una producción que podría aplicarse después de que se haya analizado parte de la secuencia de entrada dada.
En teoría, una gramática genera un lenguaje y, en eso, la ambigüedad (tener más de una forma de derivar una frase dada) está bien. En el análisis, tener una forma única y única es en el sentido de la semántica (significado), y es lo que queremos.
En el análisis de los lenguajes de programación, un lookahead es la información requerida para saber qué producción de gramática usaremos a continuación.
En los idiomas LL (0), no hay opciones, por lo que la secuencia de entrada se acepta, se analiza o se rechaza.