en fr Approximating Context-Free Grammars for Parsing and Verification Approximation de grammaires algébriques pour lanalyse syntaxique et la vérification Reportar como inadecuado




en fr Approximating Context-Free Grammars for Parsing and Verification Approximation de grammaires algébriques pour lanalyse syntaxique et la vérification - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 I3S - Laboratoire d-Informatique, Signaux, et Systèmes de Sophia Antipolis

Abstract : Programming language developers are blessed with the availability of efficient, powerful tools for parser generation. But even with automated help, the implementation of a parser remains often overly complex.Although programs should convey an unambiguous meaning, the parsers produced for their syntax, specified by a context-free grammar, are most often nondeterministic, and even ambiguous. Facing the limitations of traditional deterministic parsers, developers have embraced general parsing techniques, capable of exploring every nondeterministic choice, but offering no unambiguity warranty. The real challenge in parser development lies then in the proper identification and treatment of ambiguities-but these issues are undecidable.The grammar approximation technique discussed in the thesis is applied to nondeterminism and ambiguity issues in two different ways. The first application is the generation of noncanonical parsers, less prone to nondeterminism, mostly thanks to their ability to exploit an unbounded context-free language as right context to guide their decision. Such parsers enforce the unambiguity of the grammar, and furthermore warrant a linear time parsing complexity. The second application is ambiguity detection in itself, with the insurance that a grammar reported as unambiguous is actually so, whatever level of approximation we might choose.

Résumé : La thèse s-intéresse au problème de l-analyse syntaxique pour les langages de programmation. Si ce sujet a déjà été traité à maintes reprises, et bien que des outils performants pour la génération d-analyseurs syntaxiques existent et soient largement employés, l-implémentation de la partie frontale d-un compilateur reste encore extrêmement complexe.Ainsi, si le texte d-un programme informatique se doit de n-avoir qu-une seule interprétation possible, l-analyse des langages de programmation, fondée sur une grammaire algébrique, est, pour sa part, le plus souvent non déterministe, voire ambiguë. Confrontés aux insuffisances des analyseurs déterministes traditionnels, les développeurs de parties frontales se sont tournés massivement vers des techniques d-analyse générale, à même d-explorer des choix non déterministes, mais aussi au prix de la garantie d-avoir bien traité toutes les ambiguïtés grammaticales. Une difficulté majeure dans l-implémentation d-un compilateur réside alors dans l-identification non décidable en général et le traitement de ces ambiguïtés.Les techniques décrites dans la thèse s-articulent autour d-approximations des grammaires à deux fins. L-une est la génération d-a\-na\-ly\-seurs syntaxiques non canoniques, qui sont moins sensibles aux dif\-fi\-cultés grammaticales, en particulier parce qu-ils peuvent exploiter un langage algébrique non fini en guise de contexte droit pour résoudre un choix non déterministe. Ces analyseurs rétablissent la garantie de non ambiguïté de la grammaire, et en sus assurent un traitement en temps linéaire du texte à analyser. L-autre est la détection d-ambiguïté en tant que telle, avec l-assurance qu-une grammaire acceptée est bien non ambiguë quel que soit le degré d-approximation employé.

en fr

Keywords : Ambiguity context-free grammar noncanonical parser position automaton grammar engineering verification of infinite systems

Mots-clés : Ambiguïté grammaire algébrique analyseur syntaxique non canonique automate de positions ingénierie des grammaires vérification de systèmes infinis





Autor: Sylvain Schmitz -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados