La recherche d'une définition claire de ce qu'est un “tokenizer”, “parser” et “lexers” sont et comment ils sont liés les uns aux autres et utilisés?

Je suis à la recherche d'une définition claire de ce qu'est un "tokenizer", "parser" et "lexer" sont et comment ils sont liés les uns aux autres (par exemple, un analyseur d'utiliser un générateur de jetons ou vice-versa)? J'ai besoin de créer un programme en c/h fichiers source pour extraire des données de déclaration et de définitions.

J'ai été à la recherche d'exemples et peuvent trouver des infos, mais j'ai vraiment du mal à comprendre les concepts sous-jacents comme les règles de grammaire, d'analyser des arbres et de l'arbre de syntaxe abstraite et la manière dont ils sont liés les uns aux autres. Finalement, ces concepts doivent être stockés dans un programme, mais 1) que font-ils ressembler, 2) existe-il des communes des implémentations.

J'ai été à la recherche sur Wikipedia sur ces sujets et des programmes comme Lex et Yacc, mais n'ayant jamais passé par un compilateur de classe (EE majeur), je trouve qu'il est difficile de comprendre pleinement ce qui se passe.

InformationsquelleAutor lordhog | 2008-12-19
  1. 139

    Un tokenizer les ruptures de flux de texte en jetons, généralement par la recherche d'espaces (tabulations, espaces, de nouvelles lignes).

    Un analyseur lexical est essentiellement un générateur de jetons, mais il s'attache supplément de contexte pour les jetons -- ce jeton est un nombre, ce jeton est un littéral de chaîne, ce jeton est un opérateur d'égalité.

    Un analyseur prend le flux de jetons à partir de l'analyseur lexical et il se transforme en un arbre de syntaxe abstraite représentant l' (généralement) programme représenté par le texte original.

    Dernière, j'ai vérifié, le meilleur livre sur le sujet a été "Compilateurs: Principes, Techniques et Outils" habituellement juste connu comme "Le Dragon Book".

    • Pas de doute, "Le Dragon Book" est un bon livre, mais elle nécessite le lecteur à avoir une bonne mise à la terre dans les CS. Un livre avec plus pratique que l'appel serait "l'Écriture de Compilateurs et Interprètes" par Ronald Mak, "Moderne Compilateur de mise en Œuvre", Andrew Appel; "Compilateur de la Construction", Niklaus Wirth; "de la Compilation avec C# et Java" et "Compilateur de Compilateurs et des Générateurs: une Introduction à C++" par Pat Terry; et, bien sûr, "L'Définitive ANTLR de Référence", de Terrence Parr.
    • Assurez-vous. Dernière, j'ai vérifié, j'ai été faire un CS degré 🙂 je reporte à votre plus récente des recommandations.
    • Juste pour être sûr, je ne suis pas frapper votre recommandation. "Le Dragon Book" a été mon premier livre sur le compilateur tech, mais il était difficile d'aller par rapport à, disons, Wirth le livre, qui est un livre, vous pouvez analyser en quelques heures. A l'époque, j'avais quelques options comme il était le seul livre que je pourrais obtenir mes mains sur (étant 1991, avant d'Amazon et de les WWW). J'ai eu et une collection de fichiers texte produit par Jack W. Crenshaw appelé "construisons UN COMPILATEUR" (merci Jack!). C'est encore le livre pour en obtenir une compréhension plus complète des principes, mais la plupart des programmeurs juste besoin d'une pragmatique de l'introduction.
    • Je ne serais pas d'accord qu'un analyseur /par définition, produit un arbre de syntaxe abstraite. Les analyseurs peuvent produire toutes sortes de produits différents. Par exemple, il est fréquent qu'un analyseur produit une séquence d'appels de certains générateur d'interface -- voir le Générateur de Modèle dans la " bande des Quatre modèles de livre. Le point clé est que l'analyseur, les analyses d'une séquence de tokens pour déterminer si oui ou non la séquence est conforme à certains (généralement sans contexte) de la grammaire et peut générer de la sortie en fonction de la séquence de la structure grammaticale.
    • "Nous allons Construire un Compilateur" est ici: compilers.iecc.com/crenshaw. J'ai trouvé le lien ici: prog21.dadgum.com/30.html
    • Une fonction qui prend la saisie de l'utilisateur et crée une structure de données avec elle, devrait être nommé parser ou tokenizer?
    • si ceux-ci sont les seules contraintes, tout ce que vous avez dit est la fonction qui prend une entrée dans l'une sans nom (mathématique) de domaine et produit et une sortie dans un autre unamed de domaine, par exemple, F(X) -> Y Assez bien cela signifie que vous pouvez uniquement appeler cela une "fonction". Si vous insistez sur le fait que le domaine de X est <StreamOfCharacter,Grammaire>, et le domaine de Y est de l'Arbre 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 de F par rapport à G car G ne change pas souvent, donc F[G](X)->T est-ce que vous avez l'habitude de la voir comme un analyseur.

    InformationsquelleAutor Roger Lipscombe
  2. 14

    Exemple:

    int x = 1;

    Un analyseur lexical ou tokeniser va la diviser en jetons de 'int', 'x', '=', '1', ';'.

    Un analyseur de prendre ces jetons et de les utiliser pour comprendre d'une certaine façon:

    • nous avons une déclaration
    • il s'agit d'une définition d'un entier
    • l'entier est appelé 'x'
    • "x" doit être initialisé avec la valeur 1
    • Un analyseur lexical note que "int", "=", et les ";" sont des jetons sans plus de sens, que "x" est un nom d'identificateur ou quelque chose, la valeur de "x", et "1" est un entier ou un nombre, la valeur "1". Un générateur de jetons n'est pas nécessairement le faire.
    InformationsquelleAutor
  3. 4

    Je dirais qu'un analyseur lexical et un générateur de jetons sont fondamentalement la même chose, et qu'ils smash le texte en ses éléments constitutifs (les "jetons"). L'analyseur, puis interprète les jetons à l'aide d'une grammaire.

    Je n'aurais pas trop accroché sur la précision terminologique d'utilisation si - souvent, les gens utilisent 'analyse' pour décrire toute action de l'interprétation d'un morceau de texte.

    • Avec l'ancrage des analyseurs de la distinction entre le générateur de jetons et de l'analyseur est encore moins claire.
    InformationsquelleAutor Will Dean
  4. 1

    (ajoutant les réponses données)

    • Générateur de jetons sera aussi de supprimer les commentaires, et ne reviennent jetons de l'analyseur lexical.
    • Lexer sera aussi définir les étendues de ces jetons (variables/fonctions)
    • Analyseur alors générer le code/la structure du programme
    • Bonjour @downvoter, pouvez-vous expliquer pourquoi vous avez fait downvote?
    • Je ne suis pas le downvoter, mais je pense que le downvote peut-être parce que votre réponse ne semble pas correct. Un générateur de jetons peut supprimer le bruit (typiquement de l'espace, mais peut-être aussi les commentaires), mais il n'a souvent pas d'alimentation de l'analyseur lexical. Un DFA à base de lexer va marquer et d'identifier ce que les jetons sont (par exemple, un nombre, une chaîne, un identifiant, mais aussi à un espace ou un commentaire), mais il ne peut pas la portée de ces car ceci nécessiterait l'arbre de syntaxe qui est construit plus tard par l'analyseur.
    • 1) je ne comprends pas votre apparente distinction entre "lexer" et "tokenizer". J'ai construit analyseurs pour les plus de 50 langues et je n'ai jamais eu de séparer les deux mécanismes qui cassent le texte source en atomes, donc pour moi ce sont juste des synonymes. 2) Si vous êtes à la compilation, en supprimant les commentaires et les espaces de sens que dans l'analyseur lexical. Si vous êtes à la construction de la source-à-source outils de transformation, vous ne pouvez pas perdre de commentaires, car ils doivent réapparaître dans le texte transformé. Il faut donc TOUJOURS de retirer les commentaires qui est mal; nous pouvons nous demander comment l'on parvient à préserver les espaces. ...
    • [ ... ] [Les outils que j'ai créer (voir ma bio) la prise adéquate de la fidélité de les reproduire dans le nouveau code, nous allons plus loin, et de capturer le format des atomes, y compris des choses étranges comme les citations utilisées sur les chaînes de caractères et le radix/zéro compter sur les chiffres, tous, au service de l'éviter à l'utilisateur de rejet de la transformated résultat. Donc, ce que vous avez raté n'est pas seulement lexers pas nécessairement bande de l'information, mais en fait, ils peuvent avoir besoin de saisir les informations ci-dessus et au-delà de la crue jeton]. ....
    • ... 3) Lexers seulement de définir des "scopes" dans désespérément maladroit parseurs qui ont un moment difficile la manipulation des ambiguïtés syntaxiques. Le C et le C++ analyseurs sont l'exemple canonique; voir ma discussion à stackoverflow.com/a/1004737/120163). On n'a pas à faire ça (laid) façon. Donc, je trouve votre réponse tout simplement erronée.
    InformationsquelleAutor mcha