¿Cuál es el analizador más poderoso?

28

Como proyecto paralelo, estoy escribiendo un lenguaje usando Python. Comencé usando un clon de flex / bison llamado Ply, pero estoy enfrentando los límites en el poder de lo que puedo expresar con ese estilo de gramática, y no estoy interesado en hackear mi lenguaje debido a un desajuste de impedancia con la herramienta. Por lo tanto, no soy reacio a escribir el mío.

Entonces, ¿cuál es el tipo de analizador más poderoso? Serían bienvenidas las citas a artículos (así como a más artículos introductorios).

(Sé que 'poderoso' no está definido con precisión, pero seamos un poco flojos y veamos a dónde van las respuestas)

Paul Biggar
fuente
1
Votación negativa: no nivel de investigación.
Warren Schudy
3
@Warren: Revisé las preguntas frecuentes antes de preguntar, eso no parece ser un requisito.
Paul Biggar
1
En realidad, hay dos preguntas frecuentes, una para el sitio general y otra para CStheory. La teoría CS indica que las preguntas que pueden responderse, por ejemplo, leyendo Wikipedia están fuera de tema; consulte "¿Qué tipo de preguntas son demasiado básicas?" en meta.cstheory.stackexchange.com/questions/225/… .
Warren Schudy
1
@ Warren: Esa es la pregunta frecuente que leí. Había leído Wikipedia, pero sentí que esto necesitaba una comprensión real.
Paul Biggar
1
¿Te refieres a analizadores en producción o teóricos, es decir, que abarcan tipos de gramática distintos de CFG?
Raphael el

Respuestas:

33

Una gramática generalmente se define como una gramática libre de contexto : se proporciona una definición precisa en la página de Wikipedia, pero funciona igual que en PLY, que se basa en Bison , que a su vez se basa en yacc .

Aquí dice que PLY usa un analizador LALR . Este es esencialmente un analizador LR donde las tablas de búsqueda se condensan, posiblemente introduciendo conflictos de análisis, reduciendo algo de la expresividad de una gramática LR (es decir, una gramática libre de contexto que un analizador LR puede analizar). Si usted quiere saber acerca de las limitaciones de esta rama particular de analizadores y los de otros programas de análisis, se da una visión general de todo tipo de técnicas de análisis sintáctico (LL, LR y otros) aquí .

Para responder a su pregunta: existen algoritmos de análisis capaces de analizar cualquier lenguaje sin contexto, incluso si el lenguaje es ambiguo (es decir, hay más de una forma de interpretar la entrada):

El primer algoritmo fue el algoritmo CYK , que desafortunadamente tiene un tiempo de ejecución de , donde es la longitud de la cadena de entrada yes el tamaño de la gramática y, por lo tanto, no es práctico para analizar idiomas.n | G |O(n3|G|)n|G|

El segundo algoritmo es el algoritmo de Earley . Este algoritmo también es capaz de analizar cualquier gramática libre de contexto. Aunque el algoritmo necesita tiempo para analizar un lenguaje ambiguo, solo necesita tiempo para analizar un lenguaje no ambiguo. Además, aparentemente funciona en tiempo lineal para la mayoría de las gramáticas LR y funciona particularmente bien en las gramáticas recursivas a la izquierda.O ( n 2 )O(n3)O(n2)

Aquí puede encontrar un documento que discute una implementación práctica del (algoritmo de Earley). Concluyen: "Dada la generalidad del análisis de Earley en comparación con el análisis LALR (1) ((que es más o menos lo que hace PLY)), y considerando que incluso los PEP ((su implementación del algoritmo de Earley)) el peor momento no sería notable por un usuario, este es un excelente resultado ".

El último tipo de analizador es el analizador GLR . Esta es una versión generalizada del análisis LR, capaz de analizar cualquier lenguaje sin contexto.

Una implementación madura de GLR es ASF + SDF . Bison también puede generar un analizador GLR, aunque sus implementaciones son ligeramente diferentes del algoritmo GLR 'estándar'. El algoritmo de Elkhound es un algoritmo híbrido GLR / LALR. Utiliza LALR cuando es posible y GLR cuando es necesario, para ser rápido y capaz de analizar cualquier gramática.

Más allá de las gramáticas libres de contexto, hay gramáticas sensibles al contexto , pero en general son difíciles de analizar y no agregan tanta expresividad: puede hacer más con ellas, pero para la mayoría de las aplicaciones los usos adicionales no son relevantes, a menos que esté analizando Un lenguaje natural.

Como paso final hay gramáticas sin restricciones . En este punto, la gramática es completa de Turing, por lo que no hay límite que se pueda dar sobre cuánto tiempo llevará analizar un idioma en particular, lo que no es deseable para la mayoría de las aplicaciones de análisis. El poder extra casi nunca es necesario. Si desea utilizar toda esa potencia, existe la máquina de idiomas disponible.

Por último, implementar su propio generador de analizadores no es un asunto trivial, en particular para que sea rápido. Personalmente, acabo de terminar de hacer mi propia versión de flex (el generador de lexer), y si bien esto parecía un ejercicio de problemas algorítmicos relativamente simples, se volvió bastante complejo hacerlo bien, en particular cuando intenté admitir Unicode. Considere usar una implementación ya existente en lugar de escribir la suya.

Alex ten Brink
fuente
1
Excelente respuesta !! ¿Alguna idea sobre cómo encajan los PEG?
Paul Biggar
2
Los PEG son "diferentes" que los CFG: hay CFG que no son PEG y viceversa. Te remito aquí: stackoverflow.com/questions/1857022/… .
Alex ten Brink
Esto también podría ser de interés: blogs.ethz.ch/copton/2009/07/08/parsing-expression-grammars .
Alex ten Brink
1
En realidad, los generadores de analizadores más comunes (yacc, Antlr, bison) permiten conceptos que no son CF por predicados o código arbitrario que verifica si una regla puede aplicarse resp. decidir la precedencia. Esto se puede usar para implementar la semántica estática principalmente porque la sintaxis básica permanece esencialmente libre de contexto.
Raphael
1
Los lenguajes recursivos son precisamente los lenguajes decidibles por las máquinas Turing que siempre se detienen. Por lo tanto, cualquier lenguaje sensible al contexto también es recursivo, pero dado que los lenguajes sensibles al contexto son decidibles en tiempo exponencial, existen lenguajes recursivos que no son sensibles al contexto. Las gramáticas sin restricciones son aún más poderosas: el problema de detención puede describirse mediante una gramática sin restricciones, pero no es un lenguaje recursivo.
Alex ten Brink
15

Un artículo en ICFP 2010 este año, Total Parser Combinators , describe una biblioteca de combinación de analizador de terminación comprobable y también establece que en esta biblioteca "los combinadores de analizador son lo más expresivos posible" dado que se garantiza que el analizador termina. Lamentablemente, no recuerdo la explicación que dio el autor de lo que significa "lo más expresivo posible", pero ciertamente parece relevante a su pregunta sobre el "poder".

Rob Simmons
fuente
1
Tengo un automóvil que no contamina, en realidad tampoco se mueve ... Entonces la pregunta es: ¿qué tipo de lenguaje es analizado por esta biblioteca? No significa que este trabajo no sea interesante, por supuesto.
babou
2

Si desea ir más allá de las gramáticas libres de contexto para analizar los lenguajes de programación, pero aún así analizar en tiempo polinómico, puede recurrir a analizar las gramáticas de expresión o las gramáticas booleanas ; estas últimas también están disponibles en sabores LL y LR (ver aquí ). En la teoría del lenguaje formal, también se estudian los lenguajes de Church-Rosser poderosos pero reconocibles en tiempo lineal , pero no conozco ningún generador de analizadores implementado para estos.

En el procesamiento del lenguaje natural, los gustos son diferentes, por ejemplo, lidiar con la ambigüedad (también: ambigüedad inherente) y el orden de las palabras libres juega un papel muy destacado. Aquí las palabras clave lenguajes ligeramente sensibles al contexto y reiniciar autómatas pueden ayudarlo a comenzar a leer.

Hermann Gruber
fuente
1
Considerando la forma en que se hizo la pregunta y la queja de que la FQ es demasiado restrictiva, su respuesta es claramente la mejor. Así son las cosas ...
babou
0

Herramientas del generador de analizadores:

ANTLR es muy bueno. Alternativamente, puede echar un vistazo a JavaCC


fuente
No soy un experto en informática (a pesar de lo que dice mi título), por lo que mis palabras podrían pesar ligeramente aquí. Estoy de acuerdo con Sazzad: ANTLR es una herramienta muy poderosa. Está muy completo y todavía no he encontrado ningún problema con el generador de analizadores (LL (k) si recuerdo correctamente). Por otro lado, todavía tengo que implementar un compilador de una gramática algo compleja ...
Jörgen Sigvardsson
55
Creo que te estás perdiendo el punto de la pregunta, y tal vez todo el sitio. Se trata de la teoría de análisis, no de implementaciones y herramientas.
Paul Biggar