stringtranslate.com

Comparación de generadores de analizadores sintácticos

Esta es una lista de generadores de analizador léxico y generadores de analizadores sintácticos notables para varias clases de idiomas.

Lenguajes regulares

Los lenguajes regulares son una categoría de lenguajes (a veces denominados Chomsky Tipo 3 ) que pueden ser comparados por una máquina de estados (más específicamente, por un autómata finito determinista o un autómata finito no determinista ) construido a partir de una expresión regular . En particular, un lenguaje regular puede comparar construcciones como "A sigue a B", "A o B", "A, seguido de cero o más instancias de B", pero no puede comparar construcciones que requieren consistencia entre elementos no adyacentes, como "algunas instancias de A seguidas por el mismo número de instancias de B", y tampoco puede expresar el concepto de "anidación" recursiva ("cada A es eventualmente seguida por una B coincidente"). Un ejemplo clásico de un problema que una gramática regular no puede manejar es la cuestión de si una cadena dada contiene paréntesis correctamente anidados. (Esto es manejado típicamente por una gramática Chomsky Tipo 2, también denominada gramática libre de contexto ).

Lenguajes deterministas independientes del contexto

Los lenguajes libres de contexto son una categoría de lenguajes (a veces denominados de tipo 2 de Chomsky ) que pueden ser emparejados por una secuencia de reglas de reemplazo, cada una de las cuales esencialmente asigna cada elemento no terminal a una secuencia de elementos terminales y/o a otros elementos no terminales. Las gramáticas de este tipo pueden coincidir con cualquier cosa que pueda ser emparejada por una gramática regular y, además, pueden manejar el concepto de "anidación" recursiva ("cada A es seguida eventualmente por una B coincidente"), como la pregunta de si una cadena dada contiene paréntesis anidados correctamente. Sin embargo, las reglas de las gramáticas libres de contexto son puramente locales y, por lo tanto, no pueden manejar preguntas que requieren un análisis no local como "¿Existe una declaración para cada variable que se usa en una función?". Para hacerlo técnicamente se requeriría una gramática más sofisticada, como una gramática de tipo 1 de Chomsky, también denominada gramática sensible al contexto . Sin embargo, los generadores de analizadores sintácticos para gramáticas independientes del contexto suelen permitir que el código escrito por el usuario introduzca cantidades limitadas de sensibilidad al contexto. (Por ejemplo, al encontrar una declaración de variable, el código escrito por el usuario podría guardar el nombre y el tipo de la variable en una estructura de datos externa, de modo que se puedan comparar con referencias de variables posteriores detectadas por el analizador sintáctico).

Los lenguajes deterministas libres de contexto son un subconjunto adecuado de los lenguajes libres de contexto que pueden analizarse de manera eficiente mediante autómatas de inserción deterministas .

Análisis de gramáticas de expresión, gramáticas booleanas deterministas

Esta tabla compara los generadores de analizadores sintácticos con gramáticas de expresiones de análisis y gramáticas booleanas deterministas .

Lenguajes generales libres de contexto, conjuntivos o booleanos

Esta tabla compara los lenguajes generadores de analizadores sintácticos con una gramática general libre de contexto , una gramática conjuntiva o una gramática booleana .

Gramáticas sensibles al contexto

Esta tabla compara los generadores de analizadores sintácticos con gramáticas sensibles al contexto .

Véase también

Notas


Referencias

  1. ^ "Compilador de máquina de estados Ragel".
  2. ^ http://www.colm.net/open-source/ragel/ [ verificación necesaria ]
  3. ^ "Análisis adaptativo LL(*): el poder del análisis dinámico" (PDF) . Terence Parr . Consultado el 3 de abril de 2016 .
  4. ^ "Encuesta sobre diversas herramientas de análisis sintáctico". www.ijraset.com . Consultado el 16 de septiembre de 2023 .
  5. ^ Boyland, John; Spiewak, Daniel (17 de septiembre de 2010). "Artículo sobre herramientas: generador de analizadores sintácticos ascendentes y descendentes recursivos de ScalaBison". Notas electrónicas en informática teórica . Actas del noveno taller sobre herramientas y aplicaciones de descripciones de lenguajes (LDTA 2009). 253 (7): 65–74. doi : 10.1016/j.entcs.2010.08.032 . ISSN  1571-0661.
  6. ^ "Beaver - un generador de analizador LALR". beaver.sourceforge.net . Consultado el 16 de septiembre de 2023 .
  7. ^ Newton, Jim E.; Demaille, Akim; Verna, Didier (9 de mayo de 2016). "Verificación de tipos de secuencias heterogéneas en Common Lisp" (PDF) . Actas del 9.º Simposio Europeo de Lisp en European Lisp Symposium . ELS2016. Cracovia, Polonia: European Lisp Scientific Activities Association: 13–20. ISBN 978-2-9557474-0-7.
  8. ^ "CL-Yacc: un generador de analizador LALR(1) para Common Lisp". www.irif.fr . Consultado el 16 de septiembre de 2023 .
  9. ^ Hosseinpour, Sahereh; Alavi Milani, Mir Mohammad Reza; Pehlivan, Hüseyin (julio de 2018). "Una metodología de solución paso a paso para expresiones matemáticas". Simetría . 10 (7): 285. Bibcode :2018Symm...10..285H. doi : 10.3390/sym10070285 . ISSN  2073-8994.
  10. ^ "Página de inicio de CppCC". cppcc.sourceforge.net . Consultado el 16 de septiembre de 2023 .
  11. ^ "Copa Java". pages.cs.wisc.edu . Consultado el 16 de septiembre de 2023 .
  12. ^ "CUP". www2.cs.tum.edu . Consultado el 16 de septiembre de 2023 .
  13. ^ Thiemann, Peter; Neubauer, Matthias (31 de diciembre de 2004). "Análisis de LR parametrizado". Notas electrónicas en informática teórica . Actas del cuarto taller sobre descripciones de lenguajes, herramientas y aplicaciones (LDTA 2004). 110 : 115–132. doi : 10.1016/j.entcs.2004.06.007 . ISSN  1571-0661.
  14. ^ Gray, Robert W.; Levi, Steven P.; Heuring, Vincent P.; Sloane, Anthony M.; Waite, William M. (1992). "Eli: un sistema de construcción de compiladores completo y flexible". Comunicaciones de la ACM . 35 (2): 121–130. doi : 10.1145/129630.129637 . ISSN  0001-0782. S2CID  5121773.
  15. ^ Owens, Scott; Flatt, M.; Shivers, O.; McMullan, Benjamin (1 de octubre de 2004). "Generadores de analizador léxico y analizador sintáctico en Scheme" (PDF) . Scheme 2004: Actas del quinto taller sobre Scheme y programación funcional .
  16. ^ ab Areías, Hugo; Simões, Alberto; Henriques, P.; Cruz, Daniela Carneiro da (01/09/2010). "Generación de analizadores en Perl: descripción general y herramientas disponibles" (PDF) . {{cite journal}}: Requiere citar revista |journal=( ayuda )
  17. ^ Volkman, Victor (19 de julio de 2007). "Deja que tu analizador busque el ORO". Developer.com . Consultado el 4 de noviembre de 2023 .
  18. ^ "Análisis en C#: todas las herramientas y bibliotecas que puede utilizar (parte 2) - DZone". dzone.com . Consultado el 4 de noviembre de 2023 .
  19. ^ Ortín, Francisco; Quiroga, José; Rodríguez-Prieto, Oscar; García, Miguel (03-03-2022). "Una evaluación empírica de las herramientas de generación de analizadores Lex/Yacc y ANTLR". MÁS UNO . 17 (3): e0264326. Código Bib : 2022PLoSO..1764326O. doi : 10.1371/journal.pone.0264326 . ISSN  1932-6203. PMC 8893623 . PMID  35239695. 
  20. ^ Enseling, Oliver (29 de diciembre de 2000). "Construye tus propios lenguajes con JavaCC". InfoWorld . Consultado el 4 de noviembre de 2023 .
  21. ^ "JavaCC". JavaCC . Consultado el 4 de noviembre de 2023 .
  22. ^ "Construcción de analizadores para la web con JavaCC y GWT (primera parte)". Chris Ainsley. 14 de abril de 2014. Consultado el 4 de mayo de 2014 .
  23. ^ "El generador de analizador Lemon". sqlite.org . Consultado el 30 de noviembre de 2023 .
  24. ^ "El sistema de análisis sintáctico Lezer".
  25. ^ "Creación de un editor de código de ShopifyQL". Shopify . Consultado el 6 de diciembre de 2023 .
  26. ^ "Patrocinio del sistema analizador Lezer | Tines". www.tines.com . 2022-03-11 . Consultado el 6 de diciembre de 2023 .
  27. ^ "Un generador de analizador LR(*) para C++".
  28. ^ "Racc". i.loveruby.net . Consultado el 26 de noviembre de 2021 .
  29. ^ "Referencia de archivo de gramática de Racc". i.loveruby.net . Consultado el 26 de noviembre de 2021 .
  30. ^ "El generador de analizador SLK admite C, C++, Java, JavaScript y C#, retroceso opcional, gratuito".
  31. ^ http://www.slkpg.tech/license.txt [ URL simple del archivo de texto sin formato ]
  32. ^ "ASTUTO (El astuto Lex Yacc)".
  33. ^ "Tree-Sitter - Un sistema de análisis incremental para herramientas de programación".
  34. ^ "Parse - Generador de analizadores sintácticos seguros en tiempo de compilación (LR) para C++". GitHub . 30 de diciembre de 2021.
  35. ^ Bifurcación mantenida de PEG.js
  36. ^ taocpp/PEGTL, El arte de C++, 14 de marzo de 2024 , consultado el 16 de marzo de 2024
  37. ^ "Parrot: Grammar Engine". The Parrot Foundation. 2011. Las reglas PGE brindan todo el poder del análisis descendente recursivo y del análisis de precedencia de operadores.
  38. ^ "Resumen de declaración (Bison 3.8.1)". www.gnu.org .

Enlaces externos