Vous recherchez une définition claire de ce que sont un «tokenizer», un «parser» et des «lexers» et comment ils sont liés les uns aux autres et utilisés?

151

Je cherche une définition claire de ce que sont un "tokenizer", "parser" et "lexer" et comment ils sont liés les uns aux autres (par exemple, un analyseur utilise-t-il un tokenizer ou vice versa)? J'ai besoin de créer un programme qui passera par les fichiers source c / h pour extraire la déclaration de données et les définitions.

J'ai cherché des exemples et je peux trouver des informations, mais j'ai vraiment du mal à comprendre les concepts sous-jacents tels que les règles de grammaire, les arbres d'analyse et l'arbre de syntaxe abstraite et comment ils sont liés les uns aux autres. Finalement, ces concepts doivent être stockés dans un programme réel, mais 1) à quoi ressemblent-ils, 2) y a-t-il des implémentations communes.

J'ai regardé Wikipedia sur ces sujets et programmes comme Lex et Yacc, mais n'ayant jamais suivi de cours de compilation (majeure EE), j'ai du mal à comprendre pleinement ce qui se passe.

parsing lexer tokenize seigneur
la source

Réponses:

166

Un tokenizer divise un flux de texte en jetons, généralement en recherchant des espaces (tabulations, espaces, nouvelles lignes).

Un lexer est fondamentalement un tokenizer, mais il attache généralement un contexte supplémentaire aux tokens - ce token est un nombre, ce token est une chaîne littérale, cet autre token est un opérateur d'égalité.

Un analyseur prend le flux de jetons du lexer et le transforme en un arbre de syntaxe abstraite représentant le programme (généralement) représenté par le texte original.

La dernière fois que j'ai vérifié, le meilleur livre sur le sujet était "Compilers: Principles, Techniques, and Tools" généralement connu sous le nom de "The Dragon Book".

Roger Lipscombe
la source
8
Il ne fait aucun doute que "The Dragon Book" est un bon livre, mais il demande au lecteur d'avoir de bonnes bases en CS. Certains livres avec un attrait plus pratique seraient "Writing Compilers and Interpreters" de Ronald Mak, "Modern Compiler Implementation", Andrew Appel; "Construction du compilateur", Niklaus Wirth; «Compiler avec C # et Java» et «Compilateurs et générateurs de compilateurs: une introduction avec C ++» par Pat Terry; et, bien sûr, "The Definitive ANTLR Reference" de Terrence Parr.
Andre Artus
5
Pour être sûr, je ne rejette pas votre recommandation. "The Dragon Book" a été mon premier livre sur la technologie des compilateurs, mais c'était difficile comparé, disons, au livre de Wirth, qui est un livre que vous pouvez lire en quelques heures. À l'époque, j'avais peu d'options car c'était le seul livre sur lequel je pouvais mettre la main (c'était en 1991, avant Amazon et le WWW). J'avais ça et une collection de fichiers texte produits par Jack W. Crenshaw appelé "LET'S BUILD A COMPILER" (merci Jack!). C'est toujours le livre à obtenir pour une compréhension plus complète des principes, mais la plupart des programmeurs ont juste besoin d'une introduction pragmatique.
Andre Artus
10
Je ne serais pas d'accord qu'un analyseur / par définition / produise un arbre de syntaxe abstrait. Les analyseurs peuvent produire toutes sortes de sorties différentes. Par exemple, il est courant qu'un analyseur produise une séquence d'appels à une interface de générateur - voir le modèle de générateur dans le livre de modèles Gang of Four. Le point clé est que l'analyseur analyse une séquence de jetons pour déterminer si la séquence est conforme ou non à une grammaire (généralement sans contexte) et peut produire une sortie basée sur la structure grammaticale de la séquence.
Theodore Norvell
2
"Construisons un compilateur" est ici: compilers.iecc.com/crenshaw . J'ai trouvé le lien d'ici: prog21.dadgum.com/30.html
Roger Lipscombe
1
@Pithkos: si ce sont les seules contraintes, tout ce que vous avez dit, c'est que la fonction prend une entrée dans un domaine (mathématique) sans nom et produit et sortie dans un autre domaine sans nom, par exemple, F (X) -> Y À peu près cela signifie vous ne pouvez appeler cela qu'une «fonction». Si vous insistez sur le fait que le domaine de X est <StreamOfCharacter, Grammar> et le domaine de Y est Tree avec la propriété qu'il reflète la forme de la grammaire, alors F (X, G) -> T serait quelque chose que j'appellerais un analyseur. Souvent, nous curry F par rapport à G parce que G ne change pas souvent, donc F [G] (X) -> T est ce que vous voyez généralement comme un analyseur.
Ira Baxter
18

Exemple:

int x = 1;

Un lexer ou un tokeniser divisera cela en jetons «int», «x», «=», «1», «;».

Un analyseur prendra ces jetons et les utilisera pour comprendre d'une manière ou d'une autre:

  • nous avons une déclaration
  • c'est une définition d'un entier
  • l'entier s'appelle 'x'
  • 'x' doit être initialisé avec la valeur 1
Gra
la source
9
Un lexer notera que "int", "=" et ";" sont des jetons sans autre signification, que "x" est un nom d'identifiant ou quelque chose, la valeur "x", et "1" est un entier ou un nombre, valeur "1". Un tokenizer ne fera pas nécessairement cela.
David Thornley
5

Je dirais qu'un lexer et un tokenizer sont fondamentalement la même chose, et qu'ils cassent le texte en ses composants (les «jetons»). L'analyseur interprète ensuite les jetons à l'aide d'une grammaire.

Je ne serais pas trop accroché à un usage terminologique précis - les gens utilisent souvent le terme «analyse» pour décrire toute action consistant à interpréter un morceau de texte.

Will Dean
la source
1
Avec les analyseurs PEG, la distinction entre tokenizer et parser est encore moins claire.
Andre Artus
0

(en ajoutant aux réponses données )

  • Tokenizer supprimera également tous les commentaires et ne renverra que les jetons au Lexer.
  • Lexer définira également des portées pour ces jetons (variables / fonctions)
  • L'analyseur construira alors la structure du code / programme
mcha
la source
1
Bonjour @downvoter, pouvez-vous expliquer pourquoi vous avez effectivement voté contre?
Koray Tugay
1
Je ne suis pas le contre-vote, mais je pense que le vote défavorable est peut-être dû au fait que votre réponse ne semble pas correcte. Un tokenizer peut supprimer le bruit (généralement des espaces mais peut-être aussi des commentaires), mais il n'alimente souvent pas le lexer. Un lexer basé sur DFA marquera et identifiera ce que sont les jetons (par exemple, un nombre, une chaîne, un identifiant, mais aussi un espace blanc ou un commentaire), mais il ne peut pas les étendre car cela nécessiterait l'arborescence de syntaxe qui sera ensuite construite par l'analyseur.
Lucero
1) Je ne comprends pas votre distinction apparente entre "lexer" et "tokenizer". J'ai construit des analyseurs pour plus de 50 langues et je n'ai jamais eu deux mécanismes séparés qui divisent le texte source en atomes, donc pour moi ce ne sont que des synonymes. 2) Si vous compilez, la suppression des commentaires et des espaces a du sens dans le lexer. Si vous créez des outils de transformation source-source, vous ne pouvez pas perdre les commentaires car ils doivent réapparaître dans le texte transformé. Donc, TOUJOURS supprimer les commentaires est faux; nous pouvons discuter de la façon dont on parvient à préserver les espaces. ...
Ira Baxter
1
... [Les outils que je construis (voir ma bio) capturent les deux avec une fidélité adéquate pour les reproduire dans le code transformé; nous allons plus loin, et capturons le format des atomes, y compris des choses étranges comme les guillemets utilisés sur les chaînes de caractères et le décompte de base / zéro de début sur les nombres, le tout au service d'éviter que l'utilisateur rejette le résultat transformé. Donc, ce que vous avez manqué, ce n'est pas seulement que les lexers ne suppriment pas nécessairement les informations, mais en fait ils peuvent avoir besoin de capturer des informations au-dessus et au-delà du jeton brut]. ....
Ira Baxter
... 3) Les lexers ne définissent les "portées" que dans des parseurs désespérément maladroits qui ont du mal à gérer les ambiguïtés syntaxiques. Les analyseurs C et C ++ sont l'exemple canonique; voir ma discussion sur stackoverflow.com/a/1004737/120163 ). Il n'est pas nécessaire de le faire de cette manière (moche). Je trouve donc votre réponse tout simplement erronée.
Ira Baxter