analyseurs de lexers vs

Question

Sont lexers et analyseurs vraiment différents de la théorie ?

Il semble à la mode de la haine des expressions régulières: codage de l'horreur, un autre blog.

Toutefois, populaire lexing des outils basés sur: pygments, geshi, ou de l' embellir, de toute utilisation des expressions régulières. Ils semblent lex quoi que ce soit...

Quand est-lexing assez, quand avez-vous besoin d'EBNF ?

Quelqu'un a utilisé les jetons produits par ces lexers avec le bison ou antlr analyseur générateurs?

Answer 1

Ce analyseurs et lexers ont en commun:

1. Ils lisent les symboles de certains alphabet à partir de leur entrée.
   Astuce: L'alphabet n'a pas nécessairement à être des lettres. Mais il doit être de symboles qui sont atomiques pour la langue comprise par l'analyseur/lexer.
   • Les symboles pour le lexer: les caractères ASCII.
   • Les symboles de l'analyseur: le particulier jetons, qui sont des terminaux de leur grammaire.
2. L'analyse de ces symboles et d'essayer de les faire correspondre avec la grammaire de la langue qu'ils comprenaient.
   Et c'est là la vraie différence se trouve généralement. Voir ci-dessous pour plus d'.
   • Grammaire compris par lexers: régulière de la grammaire (Chomsky niveau 3).
   • Grammaire compris par les parseurs: context-free grammar (Chomsky de niveau 2).
3. Ils attachent de la sémantique (le sens) de la langue de morceaux qu'ils trouvent.
   • Lexers attribuer du sens par le classement de lexèmes (chaînes de symboles à partir de l'entrée) que des jetons. E. g. Tous ces lexèmes: *, ==, <=, ^ seront classés comme "opérateur" jeton par le C/C++ lexer.
   • Analyseurs de donner un sens par le classement des chaînes de jetons à partir de l'entrée (phrases) le particulier nonterminals et la construction de l' arbre d'analyse. E. g. tous ces jeton de chaînes de caractères: [number][operator][number], [id][operator][id], [id][operator][number][operator][number] seront classés comme "l'expression" non-terminal en question par le C/C++ de l'analyseur.
4. Ils peuvent attacher une signification supplémentaire (données) à l'reconnu éléments. E. g. lorsqu'un lexer reconnaît une séquence de caractères constituant un bon nombre, il peut convertir sa valeur binaire et de les stocker avec le "nombre de jeton". De même, lorsqu'un analyseur de reconnaître une expression, il est possible de calculer sa valeur et de les stocker avec le "expression" nœud de l'arbre syntaxique.
5. Ils produisent tous sur leur sortie un bon phrases de la langue qu'ils reconnaissent.
   • Lexers produire des jetons, qui sont des phrases de la langue régulier ils reconnaissent. Chaque pion peut avoir un intérieur de syntaxe (bien que niveau 3, niveau 2), mais qui n'a pas d'importance pour les données de sortie et pour celui qui les lit.
   • Analyseurs de produire de l'arbre de syntaxe, qui sont des représentations des phrases du contexte de la langue qu'ils reconnaissent. Habituellement, c'est un seul grand arbre pour l'ensemble du document/fichier source, parce que l'ensemble du document/fichier source est une bonne phrase pour eux. Mais il n'y a pas des raisons pour lesquelles l'analyseur ne pouvait pas produire une série de l'arbre de syntaxe sur sa sortie. E. g. il pourrait être un analyseur qui reconnaît les balises SGML collé en texte brut. Donc, il va marquer le document SGML dans une série de jetons: [TXT][TAG][TAG][TXT][TAG][TXT]....

Comme vous pouvez le voir, les analyseurs et des générateurs de jetons ont beaucoup en commun. Un analyseur peut être un générateur de jetons pour les autres analyseur, qui lit son entrée jetons comme des symboles à partir de son propre alphabet (les jetons sont simplement des symboles de certains alphabet) de la même manière que les phrases d'une langue peut être alphabétique des symboles de certains autres, de plus haut niveau de la langue. Par exemple, si * et - sont des symboles de l'alphabet M (en tant que "code Morse symboles"), alors vous pouvez construire un analyseur syntaxique qui reconnaît les chaînes de ces points et des lignes, des lettres codées dans le code Morse. Les phrases de la langue "Code Morse" pourrait être jetons pour certains autres analyseur, pour qui ces jetons sont atomiques symboles de sa langue (par exemple "anglais Mots" de la langue). Et ces "Mots anglais" pourrait être jetons (les symboles de l'alphabet) pour certains de plus haut niveau de l'analyseur qui comprend "des Phrases anglaises" de la langue. Et toutes ces langues ne diffèrent que dans la complexité de la grammaire. Rien de plus.

Donc, ce est tout au sujet de ces "Chomsky, la grammaire de niveaux"? Eh bien, Noam Chomsky classés grammaires en quatre niveaux en fonction de leur complexité:

• Niveau 3: les grammaires Régulières
  Ils utilisent des expressions régulières, c'est qu'ils peuvent porter que sur les symboles de l'alphabet (a,b), leur enchaînement (ab,aba,bbb de la def.), ou alternatives (par exemple, a|b).
  Ils peuvent être mis en œuvre comme des automates d'états finis (FSA), à l'instar de la NFA (Automate Fini non Déterministe) ou mieux DFA (Automate Fini Déterministe).
  Régulièrement des grammaires ne peut pas gérer avec imbriquée de la syntaxe, par exemple, correctement imbriquées/assorti parenthèses (()()(()())), imbriqués HTML/BBcode, étiquettes, blocs imbriqués etc. C'est parce que les automates d'états à traiter avec elle devrait avoir une infinité d'états à gérer un nombre infini de niveaux d'imbrication.
• Niveau 2: Contexte grammaires
  Ils peuvent avoir imbriqués, récursive, auto-similaire branches de leur arbre de syntaxe, de sorte qu'ils peuvent traiter avec structures imbriquées.
  Ils peuvent être mis en œuvre que de l'état d'automate à pile. Cette pile est utilisée pour représenter le niveau d'imbrication de la syntaxe. Dans la pratique, ils sont généralement mis en œuvre en tant que top-down, récursive de la descente de l'analyseur qui utilise la machine de la procédure de la pile des appels de suivre le niveau d'imbrication, et l'utilisation appelée récursivement les procédures/fonctions pour chaque non-terminal symbole dans leur syntaxe.
  Mais ils ne peuvent pas gérer avec un contexte sensible à la syntaxe. E. g. lorsque vous avez une expression x+3 et dans un contexte de ce x pourrait être un nom de variable, et dans d'autres contexte, il pourrait être un nom de fonction, etc.
• Niveau 1: Contexte de grammaires
• Niveau 0: Les grammaires
  Aussi appelé "phase-structure des grammaires".

Answer 2

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

Lexers sont utilisés pour reconnaître des "mots" qui constituent des éléments de la langue, parce que la structure de ces mots est généralement simple. Les expressions régulières sont très bons à la gestion de cette structure simple, et il existe de très haute performance correspondant à une expression rationnelle des moteurs utilisés pour mettre en œuvre lexers.

Les analyseurs sont utilisés pour reconnaître la "structure" d'une langue des phrases. Une telle structure est généralement au-delà de ce "expressions régulières" peut reconnaître, donc on a besoin "sensible au contexte" analyseurs d'extraire une telle structure. Sensible au contexte des analyseurs de sont difficiles à construire, de sorte que le génie compromis est d'utiliser "context-free" grammaires et ajouter des hacks pour les analyseurs syntaxiques ("tables de symboles", etc.) pour gérer le contexte sensible de la partie.

Ni lexing, ni l'analyse de la technologie est susceptible de disparaître de sitôt.

Ils peuvent être unifiée par décider de l'utilisation des "analyse" de la technologie de reconnaître des "mots", comme c'est actuellement explorée par les soi-disant scannerless GLR analyseurs. Qui a un temps d'exécution de coût, que vous présentez une demande plus générale, les machines à ce qui est souvent un problème qui n'en ont pas besoin, et le plus souvent vous payez pour que dans les frais généraux. Où vous avez beaucoup de libre des cycles, que les frais généraux ne peut pas d'importance. Si vous traitez un grand nombre de texte, puis les frais généraux importe et classique de l'expression régulière analyseurs continuera à être utilisé.

Answer 3

Quand est-lexing assez, quand avez-vous besoin d'EBNF?

EBNF n'est pas vraiment ajouter beaucoup à la puissance de grammaires. C'est juste une commodité / raccourci de notation / "sucre syntaxique" au-dessus du standard de Chomsky de la Forme Normale (CNF) de règles de grammaire. Par exemple, l'EBNF alternative:

S --> A | B

vous pouvez obtenir en CNF simplement en énumérant chaque alternative de production séparément:

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

L'élément facultatif de EBNF:

S --> X?

vous pouvez obtenir en CNF à l'aide d'un nullable de la production, qui est, celui qui peut être remplacé par une chaîne vide (notée par tout simplement vide de production; d'autres utilisent epsilon ou lambda ou le franchissement du cercle):

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

Une production dans une forme comme la dernière B ci-dessus est appelé "l'effacement", car il peut effacer ce que cela signifie en d'autres productions (produit une chaîne vide à la place de quelque chose d'autre).

Zéro ou la répétition de EBNF:

S --> A*

vous pouvez obtan par l'utilisation récursive de la production, qui est, celui qui s'incruste quelque part en elle. Il peut être fait de deux façons. Premier est récursive à gauche (ce qui devrait normalement être évitée, parce que de Haut en Bas Récursive Descente analyseurs ne peut pas 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 génère simplement une chaîne vide (en fin de compte), suivi par zéro ou plus As, la même chaîne (mais pas la même langue!) peut être exprimé en utilisant le bouton droit de la récursivité:

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 de + pour un ou plusieurs répétitions de EBNF:

S --> A+

il peut être fait en donnant un A et à l'aide de * comme avant:

S --> A A*

que vous pouvez exprimer au CNF en tant que tel (j'ai utiliser la récursivité ici; essayer 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 (qui est, régulières la grammaire) qui peut être exprimé en une seule EBNF de production composé uniquement à partir de la borne de symboles. Plus généralement, vous pouvez reconnaître les grammaires régulières quand 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.

C'est, en utilisant uniquement des chaînes vides, des terminaux, simple non-terminaux pour les remplacements et des changements d'état, et l'utilisation de la récursivité seulement pour parvenir à répétition (itération, qui est seulement linéaire de la récursivité - celui qui n'a pas de branche d'arbre). Rien de plus avancé ci-dessus, alors vous êtes sûr que c'est une syntaxe normale et vous pouvez aller avec juste lexer.

Mais quand votre syntaxe utilise la récursivité dans un non-trivial manière, pour produire de l'arbre, auto-similaire, structures imbriquées, comme le suivant:

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.

ensuite, vous peut facilement voir que cela ne peut être fait avec l'expression régulière, parce que vous ne pouvez pas le résoudre en un seul EBNF production en aucune façon; vous vous retrouverez avec un substituant S indéfiniment, ce qui vous permettra de toujours ajouter un autre as et bs sur les deux côtés. Lexers (plus précisément: les Automates d'états Finis utilisés par lexers) ne peut pas compter au nombre arbitraire (ils sont finis, vous vous souvenez?), donc, ils ne savent pas combien de as étaient là pour correspondre régulièrement avec autant d' bs. Les grammaires de ce genre sont appelés libre de tout contexte grammaires (à tout le moins), et ils ont besoin d'un analyseur.

Libre de tout contexte grammaires sont bien connus pour analyser, de sorte qu'ils sont largement utilisés pour décrire les langages de programmation syntaxe. Mais il y a plus. Parfois, un plus générale de la grammaire est nécessaire-si vous avez plus de choses à compter dans le même temps, de manière indépendante. Par exemple, quand vous voulez pour décrire une langue où l'on peut utiliser ronde des parenthèses et des crochets entrelacés, mais ils doivent être appariés correctement les uns avec les autres (les accolades avec des accolades, tour à tour). Ce type de grammaire est appelé sensible au contexte. Vous pouvez le reconnaître par qui il a plus d'un symbole sur la gauche (avant la flèche). Par exemple:

A R B --> A S B

Vous pouvez penser à ces symboles supplémentaires sur la gauche comme un "contexte" pour l'application de la règle. Il pourrait y avoir certaines préconditions, postconditions, etc. Par exemple, la règle ci-dessus pourra se substituer R en S, mais seulement quand il est dans l'entre - A et B, laissant ceux - A et B - mêmes inchangé. Cette syntaxe est vraiment difficile à analyser, car il a besoin d'une véritable machine de Turing. C'est une toute autre histoire, donc je vais terminer ici.

Answer 4

Pour répondre à la question posée (sans répéter indûment ce qui apparaît dans d'autres réponses)

Lexers et des analyseurs syntaxiques ne sont pas très différents, comme suggéré par l' accepté de répondre. Les deux sont basés sur un langage simple formalismes: régulière langues pour lexers et, presque toujours, libre de tout contexte (CF) langues pour les analyseurs syntaxiques. Ils sont tous les deux associés à assez simple de calcul les modèles, les finite state automaton et de la pousser en bas de la pile, l'automate. Langages réguliers sont un cas particulier de contexte langues, donc que lexers pourrait être produite avec un peu plus complexe CF de la technologie. Mais ce n'est pas une bonne idée pour au moins deux raisons.

Un point fondamental dans la programmation d'un composant de système devrait être réalisé avec la technologie la plus appropriée, de sorte qu'il est facile de produire, à comprendre et à maintenir. La technologie ne doit pas être overkill (en utilisant des techniques beaucoup plus complexe et coûteux que nécessaire), ni devrait-elle être à la limite de sa puissance, ce qui nécessite des techniques contorsions pour atteindre le but désiré.

C'est pourquoi "Il semble à la mode de la haine des expressions régulières". Bien qu'ils peuvent faire beaucoup de choses, parfois, ils ont besoin de très illisible le codage de l'atteindre, pour ne pas mentionner le fait que les diverses extensions et les restrictions dans la mise en œuvre réduire quelque peu leurs théorique de la simplicité. Lexers n'ont pas l'habitude de faire cela, et sont généralement une simple, efficace, et la technologie appropriée pour analyser le jeton. À l'aide de FC analyseurs pour jeton serait exagéré, mais il est possible.

Une autre raison de ne pas utiliser CF le formalisme lexers est qu'il pourrait alors tentant d'utiliser la totalité de la FC de puissance. Mais que pourrait soulever sructural problèmes concernant la lecture des programmes.

Fondamentalement, la plupart de la structure de texte du programme, à partir de laquelle le sens est extrait, est une structure en arbre. Elle exprime la façon dont l'analyse phrase (programme) est généré à partir de règles de syntaxe. La sémantique est obtenues par les techniques de composition (homomorphism pour l' mathématiquement orientée) de la façon dont les règles de syntaxe sont composées de construire l'arbre d'analyse. Par conséquent, la structure d'arbre est essentiel. Le fait que les jetons sont identifiés avec une brosse à définir en fonction des lexer ne pas changer la situation, parce que FC composé régulière encore donne FC (je parle de façon très lâche sur les transducteurs, qui transformer un flux de caractères en un flux de jeton).

Cependant, CF composé avec CF (via CF transducteurs ... désolé pour l' les mathématiques), ne donne pas nécessairement des FC, et peut-rend les choses plus général, mais moins souple dans la pratique. Donc CF n'est pas la bonne outil pour lexers, même si elle peut être utilisée.

L'une des différences majeures entre les réguliers et des FC est que la pratique régulière de les langues (et les transducteurs) composer très bien avec presque n'importe quel le formalisme de diverses manières, tout en CF les langues (et les transducteurs) ne non, même pas avec eux-mêmes (à quelques exceptions près).

(À noter que la pratique régulière de transducteurs peuvent avoir d'autres usages, tels que la formalisation de certaines erreur de syntaxe techniques de manipulation.)

La BNF est juste une syntaxe spécifique pour la présentation des grammaires CF.

EBNF est un sucre syntaxique pour la BNF, en utilisant les installations de l'ordinaire la notation de donner terser version de grammaires BNF. Il peut toujours être transformé en un équivalent pur de la BNF.

Cependant, la notation est souvent utilisé dans EBNF seulement de mettre en valeur ces les parties de la syntaxe qui correspondent à la structure lexicale éléments, et doit être reconnu par l'analyseur lexical, alors que le reste avec être plutôt présenté à droite de la BNF. Mais ce n'est pas une règle absolue.

Pour résumer, la structure plus simple de jeton est mieux analysé avec la technologie plus simple des langages réguliers, tandis que l'arbre orienté la structure de la langue (de programme de syntaxe) est mieux géré par les FC les grammaires.

Je suggère également à la recherche de PA de réponse.

Mais cela reste une question ouverte: Pourquoi les arbres?

Les arbres sont une bonne base pour la spécification de la syntaxe parce que

• ils donnent une structure simple pour le texte

• il y a très commode pour l'association de la sémantique avec le texte sur la base de cette structure, avec une mathématiquement bien compris la technologie (compositionnalité via homomorphisms), comme indiqué ci-dessus. C'est une base algébrique outil pour définir la la sémantique des formalismes mathématiques.

C'est donc une bonne représentation intermédiaire, comme le montre l' la réussite de l'arbre de Syntaxe Abstraite (AST). Notez que les AST sont souvent différent de arbre d'analyse, car l'analyse de la technologie utilisée par de nombreuses professionnels (Tels que LL ou LR) s'applique uniquement à un sous-ensemble de CF grammaires, forçant ainsi grammaticale des distorsions qui sont plus tard corrigé de l'AST. Ceci peut être évité avec plus générale d'analyse la technologie (basé sur la programmation dynamique) qui accepte toutes les CF de la grammaire.

Déclaration sur le fait que les langages de programmation sont sensibilité au contexte (CS) plutôt que de CF sont arbitraires et discutables.

Le problème est que la séparation de la syntaxe et de la sémantique est l'arbitraire. La vérification des déclarations ou type d'accord peut être considéré comme la partie de la syntaxe, ou d'une partie de la sémantique. Il en serait de même de égalité des sexes et de l'accord en nombre dans les langues naturelles. Mais il y a de naturel langues où le pluriel de l'accord dépend de la sémantique le sens des mots, de sorte qu'il ne correspond pas avec la syntaxe.

De nombreuses définitions de langages de programmation, denotational sémantique lieu déclarations et le type de la vérification de la sémantique. Donc, indiquant que réalisé par Ira Baxter FC analyseurs sont piratés pour obtenir un contexte la sensibilité requises par la syntaxe est, au mieux, l'arbitraire d'un point de vue de la situation. Il peut être organisé comme un hack dans certains compilateurs, mais il n'a pas à être.

Aussi il n'est pas juste que le CS analyseurs (dans le sens utilisé dans d'autres réponses ici) sont difficiles à construire, et moins efficace. Ils sont sont également insuffisants pour exprimer perspicuously l' kinf de sensibilité au contexte qui pourrait être nécessaire. Et ils ne sont pas produire naturellement une structure syntaxique (comme parse-arbres) est pratique à tirer de la sémantique du programme, c'est à dire de générer le code compilé.

Answer 5

Il y a un certain nombre de raisons pour lesquelles la partie d'analyse d'un compilateur est normalement séparées dans l'analyse lexicale et l'analyse ( analyse syntaxique) phases.

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 l'une de ces tâches. Par exemple, un analyseur qui avait à faire avec les commentaires et les espaces que syntaxique des unités. Considérablement plus complexes que l'on peut supposer que les commentaires et les espaces ont déjà été supprimés par l'analyseur lexical. Si nous travaillons à la conception d'une nouvelle langue, en séparant lexicale et syntaxique des préoccupations peut conduire à l'assainissement de l'ensemble de la langue de conception.
2. Compilateur amélioration de l'efficacité. Séparé analyseur lexical nous permet d'appliquer des techniques spécialisées qui servent uniquement la tâche lexicale, pas le travail de l'analyse. En outre, spécialisée techniques de mise en mémoire tampon pour la lecture de caractères d'entrée peut accélérer le compilateur de manière significative.
3. Compilateur portabilité est renforcée. Input-device-particularités spécifiques peuvent être limités à l'analyseur lexical.

des ressources___Compilateurs (2e Édition) écrit par Alfred V. Abo L'Université De Columbia Monica S. Lam L'Université De Stanford Ravi Sethi Avaya Jeffrey D. Ullman L'Université De Stanford