lexers vs parsers

Les lexeurs et les analyseurs sont-ils vraiment si différents en théorie?

Il semble à la mode de détester les expressions régulières: coder l'horreur , un autre article de blog .

Cependant, les outils populaires basés sur lexing: pygments , geshi ou prettify , utilisent tous des expressions régulières. Ils semblent lécher quoi que ce soit ...

Quand est-ce que lexing suffit, quand avez-vous besoin d'EBNF?

Quelqu'un a-t-il utilisé les jetons produits par ces lexers avec des générateurs d'analyseurs de bisons ou d'antlr?

Ce que les analyseurs et les lexeurs ont en commun:

1. Ils lisent les symboles d'un alphabet à partir de leur entrée.

   • Astuce: l'alphabet ne doit pas nécessairement être composé de lettres. Mais il doit s'agir de symboles atomiques pour le langage compris par l'analyseur / lexeur.
   • Symboles pour le lexer: caractères ASCII.
   • Symboles pour l'analyseur: les jetons particuliers, qui sont des symboles terminaux de leur grammaire.

2. Ils analysent ces symboles et essaient de les faire correspondre avec la grammaire de la langue qu'ils ont comprise.
   

   • C'est là que réside généralement la vraie différence. Voir ci-dessous pour en savoir plus.
   • Grammaire comprise par les lexers: grammaire régulière (niveau 3 de Chomsky).
   • Grammaire comprise par les parseurs: grammaire hors contexte (niveau 2 de Chomsky).

3. Ils attachent la sémantique (sens) aux pièces de langage qu'ils trouvent.

   • Les lexèmes attachent du sens en classant les lexèmes (chaînes de symboles de l'entrée) en tant que jetons particuliers . Par exemple , toutes ces lexèmes: *, ==, <=, ^seront classés comme « opérateur » jeton par le C / C de la lexer.
   • Les analyseurs attachent un sens en classant les chaînes de jetons de l'entrée (phrases) en tant que non terminaux particuliers et en construisant l' arbre d'analyse . Par exemple , toutes ces chaînes symboliques: [number][operator][number], [id][operator][id], [id][operator][number][operator][number]seront classés comme « l' expression » non - terminal par l'analyseur de l'C / C.

4. Ils peuvent attacher une signification supplémentaire (données) aux éléments reconnus.

   • Lorsqu'un lexeur reconnaît une séquence de caractères constituant un nombre correct, il peut la convertir en sa valeur binaire et la stocker avec le jeton "nombre".
   • De même, lorsqu'un analyseur reconnaît une expression, il peut calculer sa valeur et la stocker avec le nœud "expression" de l'arbre de syntaxe.

5. Ils produisent tous sur leur sortie une phrase appropriée de la langue qu'ils reconnaissent.

   • Les Lexers produisent des jetons , qui sont des phrases du langage courant qu'ils reconnaissent. Chaque jeton peut avoir une syntaxe interne (bien que niveau 3, pas niveau 2), mais cela n'a pas d'importance pour les données de sortie et pour celle qui les lit.
   • Les analyseurs produisent des arbres de syntaxe , qui sont des représentations de phrases du langage sans contexte qu'ils reconnaissent. Habituellement, ce n'est qu'une seule grande arborescence pour l'ensemble du document / fichier source, car l'ensemble du document / fichier source est une phrase appropriée pour eux. Mais il n'y a aucune raison pour que l'analyseur ne puisse pas produire une série d'arbres de syntaxe sur sa sortie. Par exemple, il pourrait s'agir d'un analyseur qui reconnaît les balises SGML collées en texte brut. Donc , il va tokenize le document SGML en une série de jetons: [TXT][TAG][TAG][TXT][TAG][TXT]....

Comme vous pouvez le voir, les analyseurs et les tokeniseurs ont beaucoup en commun. Un analyseur peut être un tokenizer pour un autre analyseur, qui lit ses jetons d'entrée comme des symboles de son propre alphabet (les jetons sont simplement des symboles d'un alphabet) de la même manière que les phrases d'une langue peuvent être des symboles alphabétiques d'un autre, de niveau supérieur Langue. Par exemple, si *et -sont les symboles de l'alphabet M(en tant que "symboles de code Morse"), vous pouvez créer un analyseur qui reconnaît les chaînes de ces points et lignes comme des lettres codées dans le code Morse. Les phrases dans la langue "Morse Code" pourraient être des jetons pour un autre analyseur, pour lesquels ces jetonssont des symboles atomiques de sa langue (par exemple la langue "English Words"). Et ces "mots anglais" pourraient être des jetons (symboles de l'alphabet) pour un analyseur de niveau supérieur qui comprend la langue des "phrases anglaises". Et toutes ces langues ne diffèrent que par la complexité de la grammaire . Rien de plus.

Alors, qu'est-ce que c'est que ces "niveaux de grammaire de Chomsky"? Eh bien, Noam Chomsky a classé les grammaires en quatre niveaux en fonction de leur complexité:

• Niveau 3: grammaires régulières

  Ils utilisent des expressions régulières, qui est, ils peuvent consister uniquement des symboles de l' alphabet ( a, b), leurs concaténations ( ab, aba, bbbETD.), Ou alternatives (par exemple a|b).
  Ils peuvent être implémentés comme des automates à états finis (FSA), comme NFA (Nondeterministic Finite Automaton) ou mieux DFA (Deterministic Finite Automaton).
  Les grammaires normales ne peuvent pas gérer la syntaxe imbriquée , par exemple les parenthèses correctement imbriquées / appariées (()()(()())), les balises HTML / BBcode imbriquées, les blocs imbriqués, etc.

• Niveau 2: grammaires sans contexte

  Ils peuvent avoir des branches imbriquées, récursives et auto-similaires dans leurs arbres de syntaxe, afin de bien gérer les structures imbriquées.
  Ils peuvent être implémentés comme automate d'état avec pile. Cette pile est utilisée pour représenter le niveau d'imbrication de la syntaxe. En pratique, ils sont généralement implémentés comme un analyseur descendant descendant récursif qui utilise la pile d'appels de procédures de la machine pour suivre le niveau d'imbrication et utilise des procédures / fonctions appelées récursivement pour chaque symbole non terminal dans leur syntaxe.
  Mais ils ne peuvent pas gérer avec une syntaxe contextuelle . Par exemple, lorsque vous avez une expression x+3et dans un contexte, cela xpourrait être le nom d'une variable, et dans un autre contexte, ce pourrait être le nom d'une fonction, etc.

• Niveau 1: grammaires contextuelles

• Niveau 0: Grammaires illimitées
  Aussi appelées grammaires récursivement énumérables.

Oui, ils sont très différents en théorie et en mise en œuvre.

Les lexers sont utilisés pour reconnaître les «mots» qui composent les éléments du langage, car la structure de ces mots est généralement simple. Les expressions régulières sont extrêmement efficaces pour gérer cette structure plus simple, et il existe des moteurs de correspondance d'expressions régulières très performants utilisés pour implémenter des lexers.

Les analyseurs sont utilisés pour reconnaître la "structure" des phrases d'une langue. Une telle structure est généralement bien au-delà de ce que les "expressions régulières" peuvent reconnaître, il faut donc des analyseurs "sensibles au contexte" pour extraire une telle structure. Les analyseurs sensibles au contexte sont difficiles à construire, donc le compromis d'ingénierie consiste à utiliser des grammaires "sans contexte" et à ajouter des hacks aux analyseurs ("tables de symboles", etc.) pour gérer la partie sensible au contexte.

Ni lexing ni la technologie d'analyse ne devraient disparaître prochainement.

Ils peuvent être unifiés en décidant d'utiliser la technologie «d'analyse» pour reconnaître les «mots», comme l'explorent actuellement les analyseurs GLR sans scanner. Cela a un coût d'exécution, car vous appliquez des machines plus générales à ce qui est souvent un problème qui n'en a pas besoin, et vous payez généralement cela en frais généraux. Lorsque vous avez beaucoup de cycles gratuits, ces frais généraux peuvent ne pas avoir d'importance. Si vous traitez beaucoup de texte, la surcharge importe et les analyseurs d'expressions régulières classiques continueront d'être utilisés.

Quand est-ce que lexing suffit, quand avez-vous besoin d'EBNF?

EBNF n'ajoute vraiment pas beaucoup à la puissance des grammaires. C'est juste une commodité / notation de raccourci / "sucre syntaxique" sur les règles de grammaire standard de la forme normale (CNF) de Chomsky. Par exemple, l'alternative EBNF:

S --> A | B

vous pouvez réaliser dans CNF en listant simplement chaque production alternative séparément:

S --> A      // `S` can be `A`,
S --> B      // or it can be `B`.

L'élément optionnel d'EBNF:

S --> X?

vous pouvez réaliser dans CNF en utilisant une production nullable , c'est-à-dire celle qui peut être remplacée par une chaîne vide (dénotée par juste une production vide ici; d'autres utilisent epsilon ou lambda ou un cercle croisé):

S --> B       // `S` can be `B`,
B --> X       // and `B` can be just `X`,
B -->         // or it can be empty.

Une production sous une forme comme la dernière ci- Bdessus est appelée "effacement", car elle peut effacer tout ce qu'elle représente dans d'autres productions (produire une chaîne vide au lieu de quelque chose d'autre).

Zéro ou plus de répétition de l'EBNF:

S --> A*

vous pouvez obtenir en utilisant production récursive , c'est-à-dire celle qui s'enfonce quelque part en elle. Cela peut se faire de deux manières. La première est la récursion gauche (ce qui devrait généralement être évité, car les analyseurs de descente récursive descendante ne peuvent pas l'analyser):

S --> S A    // `S` is just itself ended with `A` (which can be done many times),
S -->        // or it can begin with empty-string, which stops the recursion.

Sachant qu'il ne génère (finalement) qu'une chaîne vide suivie de zéro ou plus A s, la même chaîne ( mais pas le même langage! ) Peut être exprimée en utilisant la récursion à droite :

S --> A S    // `S` can be `A` followed by itself (which can be done many times),
S -->        // or it can be just empty-string end, which stops the recursion.

Et quand il s'agit d' +une ou plusieurs répétitions de l'EBNF:

S --> A+

cela peut être fait en factorisant un A et en utilisant *comme avant:

S --> A A*

que vous pouvez exprimer en CNF en tant que tel (j'utilise ici la bonne récursion; essayez de comprendre l'autre vous-même comme un exercice):

S --> A S   // `S` can be one `A` followed by `S` (which stands for more `A`s),
S --> A     // or it could be just one single `A`.

Sachant cela, vous pouvez maintenant probablement reconnaître une grammaire pour une expression régulière (c'est-à-dire, une grammaire régulière ) comme une grammaire qui peut être exprimée dans une seule production EBNF constituée uniquement de symboles terminaux. Plus généralement, vous pouvez reconnaître des grammaires régulières lorsque vous voyez des productions similaires à celles-ci:

A -->        // Empty (nullable) production (AKA erasure).
B --> x      // Single terminal symbol.
C --> y D    // Simple state change from `C` to `D` when seeing input `y`.
E --> F z    // Simple state change from `E` to `F` when seeing input `z`.
G --> G u    // Left recursion.
H --> v H    // Right recursion.

Autrement dit, en utilisant uniquement des chaînes vides, des symboles de terminal, des non-terminaux simples pour les substitutions et les changements d'état, et en utilisant la récursivité uniquement pour atteindre la répétition (itération, qui est juste une récursion linéaire - celle qui ne branche pas comme un arbre). Rien de plus avancé au-dessus de ceux-ci, alors vous êtes sûr que c'est une syntaxe régulière et vous pouvez aller avec juste lexer pour cela.

Mais lorsque votre syntaxe utilise la récursivité de manière non triviale, pour produire des structures imbriquées arborescentes, autosimilaires, comme la suivante:

S --> a S b    // `S` can be itself "parenthesized" by `a` and `b` on both sides.
S -->          // or it could be (ultimately) empty, which ends recursion.

alors vous pouvez facilement voir que cela ne peut pas être fait avec une expression régulière, car vous ne pouvez pas le résoudre en une seule production EBNF en aucune façon; vous finirez par remplacer Sindéfiniment, ce qui ajoutera toujours un autre as et un bs des deux côtés. Les lexers (plus précisément: les automates à états finis utilisés par les lexeurs) ne peuvent pas compter comme des nombres arbitraires (ils sont finis, vous vous en souvenez?), Ils ne savent donc pas combien ail y avait de correspondances égales avec autant de bs. Des grammaires comme celle-ci sont appelées (au moins des grammaires sans contexte ), et elles nécessitent un analyseur.

Les grammaires sans contexte sont bien connues pour être analysées, elles sont donc largement utilisées pour décrire la syntaxe des langages de programmation. Mais il y a plus. Parfois, une grammaire plus générale est nécessaire - lorsque vous avez plus de choses à compter en même temps, indépendamment. Par exemple, lorsque vous voulez décrire une langue où l'on peut utiliser des parenthèses rondes et des accolades carrées entrelacées, mais elles doivent être appariées correctement les unes avec les autres (accolades avec accolades, rondes avec rondes). Ce type de grammaire est appelé sensible au contexte . Vous pouvez le reconnaître par le fait qu'il a plus d'un symbole sur la gauche (avant la flèche). Par exemple:

A R B --> A S B

Vous pouvez considérer ces symboles supplémentaires à gauche comme un "contexte" pour l'application de la règle. Il pourrait y avoir des conditions préalables, etc. postconditions Par exemple, la règle ci - dessus substituera Ren S, mais seulement quand il est entre Aet B, laissant ceux Aet Bse inchangés. Ce type de syntaxe est vraiment difficile à analyser, car il a besoin d'une machine de Turing à part entière. C'est une toute autre histoire, donc je vais terminer ici.

Répondre à la question telle que posée (sans répéter indûment ce qui apparaît dans les autres réponses)

Lexers et parsers ne sont pas très différents, comme le suggère la réponse acceptée. Les deux sont basés sur des formalismes linguistiques simples: des langues régulières pour les lexers et, presque toujours, des langues sans contexte (CF) pour les parseurs. Ils sont tous deux associés à des modèles de calcul assez simples, l'automate à états finis et l'automate de pile déroulante. Les langues régulières sont un cas particulier des langues sans contexte, de sorte que les lexers pourraient être produits avec la technologie CF un peu plus complexe. Mais ce n'est pas une bonne idée pour au moins deux raisons.

Un point fondamental de la programmation est qu'un composant du système doit être construit avec la technologie la plus appropriée, afin qu'il soit facile à produire, à comprendre et à entretenir. La technologie ne doit pas être exagérée (en utilisant des techniques beaucoup plus complexes et coûteuses que nécessaire), ni à la limite de sa puissance, nécessitant ainsi des contorsions techniques pour atteindre l'objectif souhaité.

C'est pourquoi "Il semble à la mode de détester les expressions régulières". Bien qu'ils puissent faire beaucoup, ils nécessitent parfois un codage très illisible pour y parvenir, sans parler du fait que diverses extensions et restrictions de mise en œuvre réduisent quelque peu leur simplicité théorique. Les Lexers ne le font généralement pas et constituent généralement une technologie simple, efficace et appropriée pour analyser les jetons. L'utilisation d'analyseurs CF pour le jeton serait exagérée, bien que cela soit possible.

Une autre raison de ne pas utiliser le formalisme CF pour les lexers est qu'il pourrait alors être tentant d'utiliser la pleine puissance CF. Mais cela pourrait soulever des problèmes structurels concernant la lecture des programmes.

Fondamentalement, la majeure partie de la structure du texte du programme, dont le sens est extrait, est une structure arborescente. Il exprime comment la phrase d'analyse (programme) est générée à partir des règles de syntaxe. La sémantique est dérivée par des techniques de composition (homomorphisme pour les orientés mathématiques) de la façon dont les règles de syntaxe sont composées pour construire l'arbre d'analyse. Par conséquent, la structure arborescente est essentielle. Le fait que les jetons soient identifiés avec un lexer basé sur un ensemble régulier ne change pas la situation, car CF composé avec régulier donne toujours CF (je parle très vaguement de transducteurs réguliers, qui transforment un flux de caractères en un flux de jetons).

Cependant, CF composé avec CF (via des transducteurs CF ... désolé pour les mathématiques), ne donne pas nécessairement CF, et pourrait rendre les choses plus générales, mais moins maniables dans la pratique. CF n'est donc pas l'outil approprié pour les lexers, même s'il peut être utilisé.

L'une des principales différences entre le langage régulier et le langage CF est que les langues (et les transducteurs) réguliers se composent très bien avec presque tous les formalismes de diverses manières, tandis que les langages CF (et les transducteurs) ne le font pas, pas même avec eux-mêmes (à quelques exceptions près).

(Notez que les transducteurs réguliers peuvent avoir d'autres utilisations, telles que la formalisation de certaines techniques de gestion des erreurs de syntaxe.)

BNF est juste une syntaxe spécifique pour présenter les grammaires CF.

EBNF est un sucre syntaxique pour BNF , utilisant les fonctionnalités de notation régulière pour donner une version plus ters des grammaires BNF. Il peut toujours être transformé en BNF pur équivalent.

Cependant, la notation régulière est souvent utilisée en EBNF uniquement pour souligner ces parties de la syntaxe qui correspondent à la structure des éléments lexicaux, et doit être reconnue avec le lexer, tandis que le reste doit être plutôt présenté en BNF droit. Mais ce n'est pas une règle absolue.

Pour résumer, la structure plus simple du token est mieux analysée avec la technologie plus simple des langages réguliers, tandis que la structure arborescente du langage (de la syntaxe du programme) est mieux gérée par les grammaires CF.

Je suggérerais également d'examiner la réponse d'AHR .

Mais cela laisse une question ouverte: pourquoi les arbres?

Les arbres sont une bonne base pour spécifier la syntaxe car

• ils donnent une structure simple au texte

• il est très pratique d'associer la sémantique au texte sur la base de cette structure, avec une technologie mathématiquement bien comprise (compositionnalité via les homomorphismes), comme indiqué ci-dessus. Il s'agit d'un outil algébrique fondamental pour définir la sémantique des formalismes mathématiques.

Il s'agit donc d'une bonne représentation intermédiaire, comme le montre le succès des arbres à syntaxe abstraite (AST). Notez que AST est souvent différent de l'arbre d'analyse car la technologie d'analyse utilisée par de nombreux professionnels (tels que LL ou LR) ne s'applique qu'à un sous-ensemble de grammaires CF, forçant ainsi les distorsions grammaticales qui sont ensuite corrigées dans AST. Cela peut être évité avec une technologie d'analyse plus générale (basée sur une programmation dynamique) qui accepte n'importe quelle grammaire CF.

Une déclaration sur le fait que les langages de programmation sont contextuels (CS) plutôt que CF sont arbitraires et contestables.

Le problème est que la séparation de la syntaxe et de la sémantique est arbitraire. La vérification des déclarations ou de l'accord de type peut être considérée comme faisant partie de la syntaxe ou de la sémantique. Il en irait de même pour les accords de genre et de nombre dans les langues naturelles. Mais il y a des langues naturelles où l'accord pluriel dépend du sens sémantique réel des mots, de sorte qu'il ne cadre pas bien avec la syntaxe.

De nombreuses définitions des langages de programmation dans la sémantique dénotationnelle placent des déclarations et vérifient le type dans la sémantique. Donc, déclarant comme fait par Ira Baxter que les analyseurs CF sont piratés pour obtenir une sensibilité au contexte requise par la syntaxe est au mieux une vue arbitraire de la situation. Il peut être organisé comme un hack dans certains compilateurs, mais ce n'est pas obligatoire.

De plus, les analyseurs CS (dans le sens utilisé dans d'autres réponses ici) ne sont pas seulement difficiles à construire et moins efficaces. Ils sont également inadéquats pour exprimer avec perspicacité le degré de sensibilité au contexte qui pourrait être nécessaire. Et ils ne produisent pas naturellement une structure syntaxique (comme les arbres d'analyse) qui soit pratique pour dériver la sémantique du programme, c'est-à-dire pour générer le code compilé.

Il existe un certain nombre de raisons pour lesquelles la partie analyse d'un compilateur est normalement séparée en phases d'analyse lexicale et d'analyse (analyse syntaxique).

1. La simplicité de la conception est la considération la plus importante. La séparation de l'analyse lexicale et syntaxique nous permet souvent de simplifier au moins une de ces tâches. Par exemple, un analyseur qui devait traiter les commentaires et les espaces blancs comme des unités syntaxiques le serait. Beaucoup plus complexe que celui qui peut supposer que les commentaires et les espaces blancs ont déjà été supprimés par l'analyseur lexical. Si nous concevons un nouveau langage, la séparation des préoccupations lexicales et syntaxiques peut conduire à une conception globale du langage plus propre.
2. L'efficacité du compilateur est améliorée. Un analyseur lexical séparé nous permet d'appliquer des techniques spécialisées qui servent uniquement la tâche lexicale, pas le travail d'analyse. De plus, des techniques de mise en mémoire tampon spécialisées pour lire les caractères d'entrée peuvent accélérer considérablement le compilateur.
3. La portabilité du compilateur est améliorée. Les particularités spécifiques au périphérique d'entrée peuvent être limitées à l'analyseur lexical.

resource___ Compilers (2nd Edition) écrit par- Alfred V. Abo Columbia University Monica S. Lam Stanford University Ravi Sethi Avaya Jeffrey D. Ullman Stanford University