Jerarquía Chomsky y analizadores LL (*)

Question

Quiero analizar un lenguaje de programación. Leí mucho sobre lenguajes formales y la jerarquía de Chomsky y ANTLR. Pero no pude encontrar información sobre cómo relacionar los lenguajes ANTLR v3 como un analizador de descenso recursivo LL (*) acepta con la jerarquía Chomsky.

¿Cómo se mezclan los tipos Chomsky con LL (*)? Cualquier información (en línea, libros, documentos) es muy apreciada.

Editar: ¿Cómo se relacionan los predicados sintácticos / semánticos y el retroceso del ANTLR en este?

Answer 1

La jerarquía de Chomsky es básicamente:

1. Idiomas regulares
2. Gramáticas sin contexto
3. Gramáticas sensibles al contexto
4. Gramáticas recursivamente enumerables (completas de Turing)

LL Gramáticas (y analizadores) son un subconjunto de gramáticas libres de contexto. Se usan porque los lenguajes normales son demasiado débiles para fines de programación y porque un analizador general sin contexto es O (n ^ 3), que es demasiado lento para analizar un programa. De hecho, aumentar un analizador sintáctico con funciones auxiliares lo hace más fuerte. La entrada de Wikipedia en analizadores LL explica algo de esto. El Libro del Dragón se considera un libro de texto líder en compiladores, y puede explicar más.

Answer 2

LL (*) es un subconjunto de lenguajes libres de contexto. Sin embargo, una pregunta diferente es qué antlr puede analizar, dados los predicados y el retroceso, lo que extiende sus capacidades.

Tenga en cuenta que si hablamos de LL (*), eso significa ANTLR v3, no 2.