Analyse sans scanner - Scannerless parsing

En informatique , l' analyse sans scanner (également appelée analyse sans lexer ) effectue la tokenisation (décomposant un flux de caractères en mots) et l'analyse (en organisant les mots en phrases) en une seule étape, plutôt que de la décomposer en un pipeline d'un lexer suivi de un analyseur , s'exécutant simultanément . Une grammaire de langue est sans scanner si elle utilise un formalisme unique pour exprimer à la fois la structure lexicale (niveau du mot) et au niveau de la phrase de la langue.

La division du traitement en un lexer suivi d'un analyseur est plus modulaire; L'analyse sans scanner est principalement utilisée lorsqu'une distinction claire entre lexer et l'analyseur est inutile ou indésirable. Des exemples de cas où cela est approprié incluent TeX , la plupart des grammaires de wiki , des makefiles , des langages de script simples spécifiques à une application et Raku .

Avantages

  • Un seul métalangage est nécessaire
  • La structure lexicale non régulière est gérée facilement
  • La "classification des jetons" n'est pas nécessaire, ce qui supprime le besoin d'accommodements de conception tels que " le lexer hack " et les mots réservés à la langue (tels que "while" en C )
  • Les grammaires peuvent être compositionnelles (peuvent être fusionnées sans intervention humaine)

Désavantages

  • Puisque l'analyse lexicale et l'analyse syntaxique sont combinées, l'analyseur résultant a tendance à être plus compliqué et donc plus difficile à comprendre et à déboguer . Il en sera de même pour la grammaire associée, si une grammaire est utilisée pour générer l'analyseur.
  • L'analyseur résultant a tendance à être nettement moins efficace qu'un pipeline lexer-parser en ce qui concerne à la fois le temps et la mémoire .

Implémentations

  • SGLR est un analyseur pour le SDF de formalisme de définition de syntaxe modulaire , et fait partie du méta-environnement ASF + SDF et du système de transformation de programme Stratego / XT .
  • JSGLR , une implémentation purement Java de SGLR, également basée sur SDF .
  • TXL prend en charge l'analyse au niveau des caractères.
  • dparser génère du code ANSI C pour les analyseurs GLR sans scanner .
  • Spirit permet une analyse à la fois sans scanner et basée sur un scanner.
  • SBP est un analyseur sans scanner pour les grammaires booléennes (un sur-ensemble de grammaires sans contexte), écrit en Java.
  • Laja est un générateur d'analyseur à deux phases sans scanner avec prise en charge du mappage des règles de grammaire en objets, écrits en Java.
  • La fonction Grammaires Raku du langage de programmation à usage général Raku .
  • PyParsing est un analyseur sans scanner écrit en pur Python.
  • META II a intégré des fonctions d'analyseurs de jetons.
  • TREE-META Comme META II est également sans scanner avec des fonctions lexer intégrées.
  • Compilateur CWIC pour l'écriture et l'implémentation de compilateurs. A des règles de jeton dans son langage. Les règles de CWIC ont été compilées en fonctions booléennes renvoyant le succès ou l'échec.

Remarques

  • ^ C'est parce que l'analyse au niveau des caractères fait du langage reconnu par l'analyseur un langage unique sanscontextedéfini sur des caractères, par opposition à un langage sans contexte de séquences de chaînes dans les langues régulières . Certains analyseurs sans lexer gèrent toute la classe des langages sans contexte, qui est fermée sous composition.

Les références

Lectures complémentaires