Mêler combinateurs, continuations et EBNF pour une analyse syntaxique efficace en OCaml


Rodolphe Lepigre et Christophe Raffalli, LAMA. 5 mars 2015 10:00 limd
Abstract:

Partie I (Rodolphe Lepigre) : Le développement de Patoline (un nouveau système de composition de documents) nécessite un parseur extensible d'OCaml sans contrainte, notamment sur l'analyse lexicale. Nous présentons ici un environnement de développement léger pour l'analyse syntaxique, conçu en deux mois pendant l'été 2014 pour répondre à ce besoin. Le système propose une syntaxe intuitive de type BNF, sans récursion à gauche. Les parseurs sont traduits vers des expressions OCaml utilisant DeCaP, notre bibliothèque de combinateurs monadiques, et sont donc des expressions de première classe. Pour optimiser les combinateurs, nous utilisons des continuations et une méthode de prédiction des premiers caractères acceptés par une grammaire. Sur la grammaire d'OCaml, on obtient en moyenne une analyse cinq fois plus lente qu'avec le parseur d'origine et deux fois plus rapide qu'avec Camlp4. De plus, on dispose de combinateurs inspirés de la notion de continuation délimitée pour optimiser les grammaires. Notons que nous gérons aussi les grammaires ambigües. Partie II (Christophe Raffalli) : Parser combinators are popular among functional programmers because they can be used to define languages parameterised by other languages and benefit from the strong type systems of the host language. Parser combinators have the reputation of being slow... However, with a few improvement, they become no more than five to ten times slower than stack automaton. It is easy to translate a BNF-like syntax into calls to combinators while keeping there advantages. However one main drawback remains: left recursion is forbidden. Although left recursion can easily be eliminated from a context free grammar, the presence of parametrised grammars requires more: a fixpoint combinator compatible with left recursion.