lexers vs parsingurs

Ce que les parseurs et les lexers ont en commun:

1. Ils lisent les symboles de certains alphabets de leurs entrées.

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

2. Ils parsingnt ces symboles et essayent de les faire correspondre à la grammaire de la langue qu’ils ont comprise.
   

   • Voici la principale différence. Voir ci-dessous pour plus.
   • Grammaire comprise par les lexeurs: grammaire régulière (niveau 3 de Chomsky).
   • La grammaire comprise par les parsingurs syntaxiques: la grammaire sans contexte (niveau 2 de Chomsky).

3. Ils attachent une sémantique (signification) aux morceaux de langage qu’ils trouvent.

   • Les Lexers ont un sens en classant les lexèmes (chaînes de symboles de l’entrée) comme les jetons particuliers. Par exemple, tous ces lexèmes: * , == , <= , ^ seront classés comme jeton "opérateur" par le lexer C / C ++.
   • Les parsingurs ont un sens en classant les chaînes de jetons de l'entrée (phrases) comme des non - terminaux particuliers et en construisant l' arbre d'parsing . Par exemple, toutes ces chaînes de jetons: [number][operator][number] , [id][operator][id] , [id][operator][number][operator][number] seront classées comme "expression" non terminale par l'parsingur C / C ++.

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

   • Lorsqu'un lexer reconnaît une séquence de caractères constituant un nombre approprié, il peut la convertir en valeur binary et la stocker avec le jeton "number".
   • De même, lorsqu'un parsingur 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 des phrases appropriées 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 le niveau 3, pas le niveau 2), mais cela n'a pas d'importance pour les données de sortie et pour celles qui les lisent.
   • Les parsingurs produisent des arbres de syntaxe , qui sont des représentations de phrases du langage sans contexte qu'ils reconnaissent. En général, il ne s'agit que d'une seule grande arborescence pour l'ensemble du document / fichier source, car le document / fichier source complet est une phrase appropriée pour eux. Mais il n'y a aucune raison pour laquelle l'parsingur ne pourrait pas produire une série d'arbres de syntaxe sur sa sortie. Par exemple, il pourrait s'agir d'un parsingur reconnaissant les balises SGML collées en texte brut. Il va donc transformer le document SGML en une série de jetons: [TXT][TAG][TAG][TXT][TAG][TXT]...

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

Alors, que se passe-t-il dans 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, c'est-à-dire qu'ils ne peuvent contenir que les symboles de l'alphabet ( a , b ), leurs concaténations ( ab , aba , bbb etd.) Ou des alternatives (par exemple, a|b ).
  Ils peuvent être implémentés sous forme d'automates à états finis (FSA), tels que les automates finis non déterministes (NFA) ou mieux (automates finis déterministes).
  Les grammaires régulières ne peuvent pas gérer avec une syntaxe nestede , par exemple des parenthèses correctement nestedes / appariées (()()(()())) , des balises HTML / BBcode nestedes, des blocs nesteds, etc. avoir un nombre infini d'états pour gérer une infinité de niveaux de nidification.

• Niveau 2: grammaires sans contexte

  Ils peuvent avoir des twigs nestedes, récursives et auto-similaires dans leurs arbres de syntaxe, afin de pouvoir gérer avec des structures nestedes.
  Ils peuvent être implémentés en tant qu'automate d'état avec stack. Cette stack est utilisée pour représenter le niveau d'imbrication de la syntaxe. En pratique, ils sont généralement utilisés comme un parsingur récursif descendant descendant qui utilise la stack d'appels de procédure 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+3 et dans un contexte, ce x pourrait être le nom d'une variable et, dans un autre contexte, il pourrait s'agir d'un nom de fonction, etc.

• Niveau 1: grammaires sensibles au contexte

• Niveau 0: grammaires illimitées
  Aussi appelé "grammaires à structure de phase".

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

Les Lexers sont utilisés pour reconnaître des “mots” qui constituent des éléments de 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’expression régulière très performants utilisés pour implémenter des lexers.

Les parsingurs syntaxiques sont utilisés pour reconnaître la “structure” des expressions linguistiques. 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 parsingurs “sensibles au contexte” pour extraire une telle structure. Les parsingurs contextuels sont difficiles à construire, de sorte que le compromis d’ingénierie consiste à utiliser des grammaires “sans contexte” et à append des hacks aux parsingurs (“tables de symboles”, etc.) pour gérer la partie contextuelle.

Ni la technologie du lexing ni celle de l’parsing syntaxique ne risquent de disparaître rapidement.

Ils peuvent être unifiés en décidant d’utiliser la technologie “d’parsing” pour reconnaître les “mots”, comme c’est actuellement le cas avec les parsingurs 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 pour cela dans les frais généraux. Lorsque vous avez beaucoup de cycles libres, cela n’a pas d’importance. Si vous traitez beaucoup de texte, alors la surcharge est importante et les parsingurs d’expressions régulières classiques continueront à être utilisés.

Quand le lexing suffit-il, quand avez-vous besoin d’EBNF?

EBNF n’ajoute pas grand chose au pouvoir des grammaires. C’est juste une notation pratique / raccourci / “sucre syntaxique” par rapport aux règles de grammaire standard de CNF (Chomsky’s Normal Form). Par exemple, l’alternative EBNF:

 S --> A | B 

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

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

L’élément facultatif 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ésignée simplement par 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 la forme du dernier B ci-dessus s’appelle “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).

Répétition zéro ou plus de EBNF:

 S --> A* 

vous pouvez l’obtenir en utilisant une production récursive , c’est-à-dire qui s’intègre quelque part. Cela peut se faire de deux manières. La première est la récursion gauche (qui devrait normalement être évitée, car les parsingurs récursifs de descente descendante ne peuvent pas l’parsingr):

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

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

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

Et quand il s’agit de + pour une répétition d’EBNF:

 S --> A+ 

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

 S --> AA* 

que vous pouvez exprimer dans CNF en tant que tel (j’utilise la récursivité correcte ici; essayez de trouver l’autre comme exercice):

 S --> AS // `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 reconnaître probablement une grammaire pour une expression régulière (c’est-à-dire une grammaire régulière ) qui peut être exprimée dans une production EBNF unique 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 terminaux, des non-terminaux simples pour les substitutions et les changements d’état, et en n’utilisant la récursivité que pour obtenir la répétition (itération qui est simplement une récursivité linéaire ). Rien de plus avancé au-dessus de cela, 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 sortingviale, pour produire des structures nestedes, semblables à des arbres, 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 de quelque manière que ce soit; vous finirez par substituer indéfiniment S , ce qui appenda toujours un autre s et b s des deux côtés. Les Lexers (plus précisément: les automates à états finis utilisés par les lexers) ne peuvent pas compter dans un nombre arbitraire (ils sont finis, rappelez-vous?), Ils ne savent donc pas combien de s ils étaient là pour les égaler. Les grammaires comme celles-ci sont appelées grammaires non contextuelles (au moins) et nécessitent un parsingur.

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 simultanément, indépendamment. Par exemple, lorsque vous voulez décrire une langue dans laquelle on peut utiliser des parenthèses et des accolades, mais elles doivent être appariées correctement (accolades, rondes). Ce type de grammaire est appelé contextuel . Vous pouvez le reconnaître par le fait qu’il a plus d’un symbole à gauche (avant la flèche). Par exemple:

 ARB --> ASB 

Vous pouvez considérer ces symboles supplémentaires à gauche comme un “contexte” pour appliquer la règle. Il pourrait y avoir des conditions préalables, des postconditions, etc. Par exemple, la règle ci-dessus remplacera R par S , mais seulement quand elle est entre A et B , laissant les A et B eux-mêmes inchangés. Ce type de syntaxe est très difficile à parsingr, car il nécessite une machine Turing complète. C’est une toute autre histoire, alors je vais terminer ici.

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

Les Lexers et les parseurs ne sont pas très différents, comme le suggère la réponse acceptée. Les deux sont basés sur des formalismes de langage simples: des langages réguliers pour les lexers et, presque toujours, des langages sans contexte (CF) pour les parsingurs. Ils sont tous deux associés à des modèles informatiques assez simples, l’automate à états finis et l’automate à stack. Les langues régulières sont un cas particulier des langages 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 devrait être doté de la technologie la plus appropriée, de sorte qu’il soit facile à produire, à comprendre et à entretenir. La technologie ne doit pas être exagérée (utiliser des techniques beaucoup plus complexes et coûteuses que nécessaire) et ne doit pas non plus être à la limite de sa puissance, ce qui nécessite des contorsions techniques pour atteindre le but 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 compter le fait que diverses extensions et ressortingctions dans la mise en œuvre réduisent quelque peu leur simplicité théorique. Les Lexers ne le font généralement pas et sont généralement une technologie simple, efficace et appropriée pour parsingr les jetons. Utiliser des parsingurs CF pour les jetons serait excessif, même si cela est possible.

Une autre raison de ne pas utiliser le formalisme des FC pour les lexistes est qu’il pourrait être tentant d’utiliser toute la puissance des FC. Mais cela pourrait poser des problèmes structurels en ce qui concerne la lecture des programmes.

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

Cependant, la FC composée avec CF (via des transducteurs CF… désolé pour les calculs) ne donne pas nécessairement la FC, ce qui peut rendre les choses plus générales, mais moins faciles à mettre en pratique. Le CF n’est donc pas l’outil approprié pour les lexeurs, même s’il peut être utilisé.

Une des différences majeures entre le CF et le CF est que les langages réguliers (et les transducteurs) composent très bien avec presque tous les formalismes de différentes manières, alors que les langages (et les transducteurs) ne le sont pas (à quelques exceptions près).

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

BNF n’est qu’une syntaxe spécifique pour la présentation des grammaires CF.

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

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

En résumé, la structure plus simple du jeton est mieux analysée avec la technologie plus simple des langages normaux, tandis que la structure orientée arborescence du langage (de la syntaxe du programme) est mieux gérée par les grammaires CF.

Je suggère également d’examiner la réponse de la procréation assistée .

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 (compositionalité via homomorphismes), comme indiqué ci-dessus. C’est 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’parsing car la technologie d’parsing utilisée par de nombreux professionnels (comme LL ou LR) ne s’applique qu’à un sous-ensemble de grammaires CF, forçant ainsi des distorsions grammaticales corrigées ultérieurement dans AST. Cela peut être évité avec une technologie d’parsing plus générale (basée sur la programmation dynamic) qui accepte toute grammaire CF.

Les déclarations sur le fait que les langages de programmation sont sensibles au contexte (CS) plutôt que CF sont arbitraires et discutables.

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 soit comme une partie de la syntaxe, soit comme une partie de la sémantique. Il en irait de même pour l’accord sur le genre et le nombre dans les langues naturelles. Mais il existe des langages naturels dans lesquels l’accord du pluriel dépend de la signification sémantique réelle des mots, de sorte qu’il ne correspond pas bien à la syntaxe.

De nombreuses définitions des langages de programmation dans la sémantique dénotationnelle placent les déclarations et vérifient le type dans la sémantique. Le fait de dire, comme l’a fait Ira Baxter, que les parsingurs des FC sont piratés pour obtenir une sensibilité au contexte requirejse 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.

En outre, les parsingurs CS (au sens utilisé dans d’autres réponses) ne sont pas simplement difficiles à construire et moins efficaces. Ils sont également insuffisants pour exprimer de manière perspicace la sensibilité au contexte qui pourrait être nécessaire. Et ils ne produisent pas naturellement une structure syntaxique (telle que des arbres d’parsing) qui permet de dériver la sémantique du programme, c’est-à-dire de générer le code compilé.

Il existe un certain nombre de raisons pour lesquelles la partie parsing d’un compilateur est normalement séparée en parsing lexicale et en parsing syntaxique.

1. La simplicité de conception est la considération la plus importante. La séparation de l’parsing lexicale et syntaxique permet souvent de simplifier au moins une de ces tâches. Par exemple, un parsingur devant traiter des commentaires et des espaces blancs en tant qu’unités syntaxiques. Beaucoup plus complexe que celui qui peut supposer que des commentaires et des espaces blancs ont déjà été supprimés par l’parsingur lexical. Si nous concevons un nouveau langage, séparer les préoccupations lexicales et syntaxiques peut mener à une conception linguistique globale plus propre.
2. L’efficacité du compilateur est améliorée. Un parsingur lexical séparé nous permet d’appliquer des techniques spécialisées qui ne servent que la tâche lexicale, et non l’parsing. De plus, des techniques de mise en mémoire tampon spécialisées pour la lecture des 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 à l’appareil d’entrée peuvent être limitées à l’parsingur lexical.

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