Usos apropiados para yacc/byacc/bison y lex/flex

Question

La mayoría de las publicaciones que leo relacionadas con estas utilidades generalmente sugieren utilizar algún otro método para obtener el mismo efecto. Por ejemplo, las preguntas que citan estas herramientas habituales tienen al menos una respuesta que contiene algunos de los siguientes:

• utilizar la biblioteca de impulso (inserte biblioteca de impulso apropiado en este caso)
• no crean un uso DSL (insertar script favorito idioma aquí)
• Antlr es mejor

---

Suponiendo que el desarrollador ...

• ... es cómodo con el lenguaje C
• ... no saber por lo menos uno de scripting idioma (por ejemplo, Python, Perl, etc.)
• ... debe escribir algo de código de análisis en casi cada proyecto trabajó en

---

Así que mis preguntas son:

• ¿Cuáles son apropiados situa las cuales son adecuadas para estas utilidades?
• ¿Hay situaciones (razonables) donde no hay una mejor alternativa a un problema que yacc y lex (o derivados)?
• ¿Con qué frecuencia en los problemas reales de análisis se puede esperar encontrarse con ningún cortos idas en yacc y lex que son mejor abordados por los últimos soluciones más?
• Para un desarrollador que no es ya familiarizados con estas herramientas es que vale la pena para ellos invertir tiempo en aprender sobre su sintaxis /modismos? ¿Cómo se comparan con otras soluciones?

Answer 1

Las razones por las que lex/yacc y derivados parecen tan omnipresentes hoy en día son que han existido por mucho más tiempo que otras herramientas, tienen mucha más cobertura en la literatura y tradicionalmente vienen con sistemas operativos Unix. Tiene muy poco que ver con la forma en que se comparan con otras herramientas generadoras de lexer y analizador sintáctico.

No importa qué herramienta elijas, siempre habrá una curva de aprendizaje significativa.Entonces, una vez que haya usado una herramienta determinada varias veces y se haya sentido relativamente cómodo en su uso, es poco probable que desee incurrir en el esfuerzo extra de aprender otra herramienta. Eso es solo natural.

Además, a fines de la década de 1960 y principios de la década de 1970, cuando se creó lex/yacc, las limitaciones del hardware planteaban un serio desafío para el análisis sintáctico. El método de análisis de LR controlado por tabla utilizado por Yacc era el más adecuado en ese momento porque se podía implementar con una pequeña huella de memoria mediante el uso de una lógica de programa general relativamente pequeña y manteniendo el estado en archivos en cinta o disco. Los métodos de análisis basados ​​en código como LL tenían una huella de memoria mínima mayor porque el código del programa analizador representa la gramática y, por lo tanto, debe ajustarse por completo a la RAM para ejecutarse y mantiene el estado en la pila en la RAM.

Cuando la memoria se hizo más abundante, mucha más investigación se dirigió a diferentes métodos de análisis sintáctico como LL y PEG y cómo crear herramientas utilizando esos métodos. Esto significa que muchas de las herramientas alternativas que se han creado después de la familia lex/yacc utilizan diferentes tipos de gramáticas. Sin embargo, cambiar los tipos de gramática también incurre en una curva de aprendizaje significativa. Una vez que esté familiarizado con un tipo de gramática, por ejemplo, gramáticas LR o LALR, es menos probable que desee cambiar a una herramienta que utiliza un tipo diferente de gramática, por ejemplo, las gramáticas LL.

En general, la familia de herramientas lex/yacc es generalmente más rudimentaria que las llegadas más recientes que a menudo tienen interfaces de usuario sofisticadas para visualizar gráficamente gramática y conflictos gramaticales o incluso resolver conflictos mediante refactorización automática.

Entonces, si no tiene experiencia previa con ninguna herramienta analizadora, si tiene que aprender una nueva herramienta de todos modos, entonces probablemente debería considerar otros factores como la visualización gráfica de gramáticas y conflictos, autorefactorización, disponibilidad de buena documentación, idiomas en los que los lexers/analizadores generados pueden mostrarse, etc. No seleccione ninguna herramienta simplemente porque "esto es lo que todo el mundo parece estar usando".

Aquí hay algunas razones que se me ocurrieron para el uso de la lex/yacc o flex/bison:

• el desarrollador ya está familiarizado con la lex/yacc o Flex/bisontes
• el desarrollador es más familiar y cómodo con LR/LALR gramáticas
• el desarrollador tiene un montón de libros que cubren lex/yacc pero hay libros que cubren otros
• el desarrollador tiene una oferta de trabajo prospectivo se aproximan y se ha dicho que las habilidades lex/yacc aumentarían sus posibilidades de ser contratado
• el desarrollador podría no obtener los titulares de aceptación por parte de los miembros del proyecto/juego para el uso de otras herramientas
• el medio ambiente ha instalado lex/yacc y por alguna razón no es factible instalar otras herramientas

Answer 2

En un proyecto anterior, necesitaba una forma de poder generar consultas sobre datos arbitrarios de una manera que fuera fácil de usar para una persona relativamente no técnica. Los datos eran de tipo CRM (por ejemplo, nombre, apellido, dirección de correo electrónico, etc.) pero se suponía que trabajaran contra varias bases de datos diferentes, todas con esquemas diferentes.

Así que desarrollé una pequeña DSL para especificar las consultas (por ejemplo, [FirstName] = 'Joe' Y [LastName] = 'Bloggs' seleccionaría a todos los llamados "Joe Bloggs"). Tenía algunas opciones más complicadas, por ejemplo, la sintaxis "optedout (medio)" que seleccionaba a todas las personas que habían optado por no recibir mensajes en un medio en particular (correo electrónico, sms, etc.). Hubo "endogrupo (xyz)" que seleccionaría a todos en un grupo en particular, etc.

Básicamente, nos permite especificar consultas como "grupo interno ('GrupoA') y no del grupo interno ('Grupo B')", que se traduce en una consulta SQL como esto:

SELECT 
    * 
FROM 
    Users 
WHERE 
    Users.UserID IN (SELECT UserID FROM GroupMemberships WHERE GroupID=2) AND 
    Users.UserID NOT IN (SELECT UserID GroupMemberships WHERE GroupID=3) 

(Como puede ver, las consultas no son tan eficientes como sea posible, pero eso es lo que obtienes con la generación de máquinas, supongo).

no hizo uso de la flexión/bisontes para ello, pero hice uso de un generador de analizadores sintácticos (cuyo nombre se me ha escapado por el momento ...)

Answer 3

Creo que es un buen consejo para evitar la creación de nuevos lenguajes solo para admitir un lenguaje específico de Dominio. Será un mejor uso de su tiempo tomar un idioma existente y ampliarlo con la funcionalidad del dominio.

Si está intentando crear un nuevo idioma por algún otro motivo, quizás para investigar sobre el diseño del lenguaje, estas herramientas están un poco desactualizadas. Generadores más nuevos como antlr, o incluso nuevos lenguajes de implementación como ML, hacen que el diseño del lenguaje sea mucho más fácil.

Si hay una buena razón para utilizar estas herramientas, es probablemente debido a su legado. Es posible que ya tenga un esqueleto de un idioma que necesita mejorar, que ya está implementado en una de estas herramientas. También puede beneficiarse de los enormes volúmenes de información tutorial escritos sobre estas herramientas antiguas, para las cuales no existe un corpus tan grande escrito para las formas más nuevas e ingeniosas de implementar lenguajes.

Answer 4

Tenemos todo un lenguaje de programación implementado en mi oficina. Lo usamos para eso Creo que debe ser una forma rápida y fácil de escribir intérpretes para las cosas. Posiblemente podría escribir casi cualquier tipo de analizador de texto usándolos, pero muchas veces es A) más fácil escribirlo usted mismo rápidamente o B) necesita más flexibilidad de la que brindan.

Answer 5

Si vale la pena aprender estas herramientas o no dependerá en gran medida (casi en su totalidad en la cantidad de código de análisis que escribe, o qué tan interesado está en escribir más código en ese orden general. He usado un poco, y les resulta extremadamente útil.

La herramienta que utiliza en realidad no hace tanta diferencia como muchos creen. Para aproximadamente el 95% de las entradas que he tenido que tratar, hay poca diferencia entre uno y otro que la mejor opción es simplemente aquella con la que estoy más familiarizado y cómodo.

Por supuesto, lex y yacc producen (y exigen que escribas tus acciones en) C (o C++). Si eres no comfo rtable with them, una herramienta que utiliza y produce el idioma que prefiera (p. Python o Java) sin duda será una opción mucho mejor. Yo, por mi parte, no aconsejaría tratar de usar una herramienta como esta con un idioma con el que no estés familiarizado o incómodo. En particular, si escribe código en una acción que produce un error de compilación, es probable que obtenga considerablemente menos ayuda del compilador de lo habitual para rastrear el problema, por lo que realmente debe estar lo suficientemente familiarizado con el idioma para reconocer el problema. con solo una mínima pista sobre dónde el compilador notó que algo andaba mal.