Venir avec des jetons pour un lexer

J'écris un analyseur pour un langage de balisage que j'ai créé (écrit en python, mais ce n'est pas vraiment pertinent pour cette question - en fait, si cela semble être une mauvaise idée, j'aimerais une suggestion pour un meilleur chemin) .

Je lis sur les analyseurs ici: http://www.ferg.org/parsing/index.html , et je travaille sur l'écriture du lexer qui devrait, si je comprends bien, diviser le contenu en jetons. Ce que j'ai du mal à comprendre, c'est quels types de jetons je dois utiliser ou comment les créer. Par exemple, les types de jetons dans l'exemple auquel j'ai lié sont:

• CHAÎNE
• IDENTIFICATEUR
• NOMBRE
• WHITESPACE
• COMMENTAIRE
• EOF
• De nombreux symboles tels que {et (comptent comme leur propre type de jeton

Le problème que j'ai, c'est que les types de jetons plus généraux me semblent un peu arbitraires. Par exemple, pourquoi STRING a-t-il son propre type de jeton distinct par rapport à IDENTIFIER. Une chaîne peut être représentée par STRING_START + (IDENTIFIER | WHITESPACE) + STRING_START.

Cela peut aussi avoir à voir avec les difficultés de ma langue. Par exemple, les déclarations de variables sont écrites en tant que {var-name var value}et déployées avec {var-name}. Il semble '{'et '}'devraient être leurs propres jetons, mais les types de jetons VAR_NAME et VAR_VALUE sont-ils éligibles, ou ces deux tomberaient-ils sous IDENTIFIER? De plus, le VAR_VALUE peut contenir des espaces. L'espace après var-nameest utilisé pour signifier le début de la valeur dans la déclaration. Tout autre espace fait partie de la valeur. Cet espace blanc devient-il son propre jeton? L'espace blanc n'a cette signification que dans ce contexte. De plus, ce {n'est peut-être pas le début d'une déclaration de variable .. cela dépend du contexte (il y a encore ce mot!). {:démarre une déclaration de nom, et{ peut même être utilisé dans le cadre d'une certaine valeur.

Mon langage est similaire à Python dans la mesure où les blocs sont créés avec indentation. Je lisais sur la façon dont Python utilise le lexer pour créer des jetons INDENT et DEDENT (qui servent plus ou moins comme quoi {et }feraient dans beaucoup d'autres langues). Python prétend être sans contexte, ce qui signifie pour moi qu'au moins le lexer ne devrait pas se soucier de l'endroit où il se trouve dans le flux lors de la création de jetons. Comment le lexeur de Python sait-il qu'il construit un jeton INDENT d'une longueur spécifique sans connaître les caractères précédents (par exemple, que la ligne précédente était une nouvelle ligne, alors commencez à créer les espaces pour INDENT)? Je demande parce que j'ai besoin de le savoir aussi.

Ma dernière question est la plus stupide: pourquoi un lexer est-il même nécessaire? Il me semble que l'analyseur pourrait aller caractère par caractère et déterminer où il se trouve et ce qu'il attend. Le lexer ajoute-t-il l'avantage de la simplicité?

Votre question (comme l'indique votre dernier paragraphe) ne concerne pas vraiment le lexer, elle concerne la conception correcte de l'interface entre le lexer et l'analyseur. Comme vous pouvez l'imaginer, il existe de nombreux livres sur la conception de lexers et d'analyseurs. Il se trouve que j'aime le livre d'analyse de Dick Grune , mais ce n'est peut-être pas un bon livre d'introduction. Il se trouve que je n'aime pas intensément le livre basé sur C d'Appel , car le code n'est pas utilement extensible dans votre propre compilateur (en raison des problèmes de gestion de la mémoire inhérents à la décision de prétendre que C est comme ML). Ma propre introduction était le livre de PJ Brown , mais ce n'est pas une bonne introduction générale (bien que très bonne pour les interprètes en particulier). Mais retournons à votre question.

La réponse est de faire tout ce que vous pouvez dans le lexer sans avoir besoin d'utiliser des contraintes prospectives ou rétrospectives.

Cela signifie que (en fonction bien sûr des détails de la langue), vous devez reconnaître une chaîne comme un "caractère suivi d'une séquence de non -" puis d'un autre "caractère. Renvoyez-le à l'analyseur comme une seule unité. Il existe plusieurs raisons, mais les plus importantes sont

1. Cela réduit la quantité d'état que l'analyseur doit maintenir, limitant sa consommation de mémoire.
2. Cela permet à l'implémentation de lexer de se concentrer sur la reconnaissance des blocs de construction fondamentaux et de libérer l'analyseur pour décrire comment les éléments syntaxiques individuels sont utilisés pour construire un programme.

Très souvent, les analyseurs peuvent prendre des mesures immédiates en recevant un jeton du lexer. Par exemple, dès que IDENTIFIER est reçu, l'analyseur peut effectuer une recherche dans la table des symboles pour savoir si le symbole est déjà connu. Si votre analyseur analyse également les constantes de chaîne en tant que CITATION (ESPACES D'IDENTIFICATION) au point où vous êtes maintenant sûr de ne pas regarder une chaîne.

Pour reformuler ce que j'essaie de dire, mais différemment, le lexer devrait se préoccuper de l'orthographe des choses, et l'analyseur de la structure des choses.

Vous remarquerez peut-être que ma description de ce à quoi ressemble une chaîne ressemble beaucoup à une expression régulière. Ce n'est pas un hasard. Les analyseurs lexicaux sont fréquemment implémentés dans de petits langages (dans le sens de l'excellent livre Programming Pearls de Jon Bentley ) qui utilisent des expressions régulières. J'ai l'habitude de penser en termes d'expressions régulières lors de la reconnaissance de texte.

Concernant votre question sur les espaces, reconnaissez-la dans le lexer. Si votre langue est destinée à être au format assez libre, ne renvoyez pas les jetons WHITESPACE à l'analyseur, car il n'aura qu'à les jeter, de sorte que les règles de production de votre analyseur seront essentiellement polluées par du bruit - des choses à reconnaître juste à lancer les éloigner.

Quant à ce que cela signifie sur la façon dont vous devez gérer les espaces quand ils sont syntaxiquement significatifs, je ne suis pas sûr de pouvoir vous faire un jugement qui fonctionnera vraiment bien sans en savoir plus sur votre langue. Mon jugement instantané est d'éviter les cas où les espaces sont parfois importants et parfois non, et d'utiliser une sorte de délimiteur (comme des guillemets). Mais, si vous ne pouvez pas concevoir la langue comme vous le souhaitez, cette option peut ne pas être disponible pour vous.

Il existe d'autres façons de faire des systèmes d'analyse de langage de conception. Certes, il existe des systèmes de construction de compilateurs qui vous permettent de spécifier un système combiné de lexeurs et d'analyseurs (je pense que la version Java d' ANTLR le fait) mais je n'en ai jamais utilisé un.

Une note historique. Il y a des décennies, il était important que le lexer fasse autant que possible avant de passer le relais à l'analyseur, car les deux programmes ne tenaient pas en mémoire en même temps. Faire plus dans le lexer a laissé plus de mémoire disponible pour rendre le parseur intelligent. J'ai utilisé le compilateur Whitesmiths C pendant un certain nombre d'années, et si je comprends bien, il fonctionnerait dans seulement 64 Ko de RAM (c'était un programme MS-DOS de petit modèle) et même ainsi, il a traduit une variante de C qui était très très proche de ANSI C.

Je vais répondre à votre dernière question, qui n'est en fait pas stupide. Les analyseurs peuvent construire et construisent des constructions complexes caractère par caractère. Si je me souviens bien, la grammaire de Harbison et Steele ("C - Un manuel de référence") a des productions qui utilisent des caractères uniques comme terminaux, et construisent des identifiants, des chaînes, des nombres, etc. comme non-terminaux à partir des caractères uniques.

Du point de vue des langages formels, tout ce qu'un lexeur basé sur une expression régulière peut reconnaître et classer comme "littéral de chaîne", "identificateur", "numéro", "mot-clé", etc., même un analyseur LL (1) peut le reconnaître. Il n'y a donc aucun problème théorique à utiliser un générateur d'analyseur pour tout reconnaître.

D'un point de vue algorithmique, un identificateur d'expressions régulières peut fonctionner beaucoup plus rapidement que n'importe quel analyseur. D'un point de vue cognitif, il est probablement plus facile pour un programmeur de séparer le travail entre un lexer d'expression régulière et un analyseur écrit de générateur d'analyseur.

Je dirais que des considérations pratiques obligent les gens à prendre la décision d'avoir des lexers et des parseurs séparés.

Il semble que vous tentiez d'écrire un lexer / analyseur sans vraiment comprendre les grammaires. En règle générale, lorsque les gens écrivent un lexer et un analyseur, ils les écrivent pour se conformer à une grammaire. Le lexeur doit renvoyer les jetons dans la grammaire tandis que l'analyseur utilise ces jetons pour faire correspondre les règles / non-terminaux . Si vous pouviez facilement analyser votre entrée simplement octet par octet, alors un lexer et un analyseur pourraient être exagérés.

Les Lexers simplifient les choses.

Présentation de la grammaire : une grammaire est un ensemble de règles sur l'apparence d'une syntaxe ou d'une entrée. Par exemple, voici une grammaire du jouet (simple_command est le symbole de début):

simple_command:
 WORD DIGIT AND_SYMBOL
simple_command:
     addition_expression

addition_expression:
    NUM '+' NUM

Cette grammaire signifie que -
Une simple_commande est composée de
A) WORD suivi de DIGIT suivi de AND_SYMBOL (ce sont des "jetons" que je définis)
B) Une "addition_expression" (c'est une règle ou "non-terminal")

Une expression_addition est composée de:
NUM suivi d'un '+' suivi d'un NUM (NUM est un "jeton" que je définis, '+' est un signe plus littéral).

Par conséquent, puisque simple_command est le "symbole de départ" (l'endroit où je commence), lorsque je reçois un jeton, je vérifie s'il correspond à simple_command. Si le premier jeton dans l'entrée est un MOT et le prochain jeton est un CHIFFRE et le prochain jeton est un AND_SYMBOL, alors j'ai fait correspondre une simple commande et je peux prendre des mesures. Sinon, je vais essayer de le faire correspondre à l'autre règle de simple_command qui est addition_expression. Ainsi, si le premier jeton était un NUM suivi d'un '+' suivi d'un NUM, alors je fais correspondre une simple_commande et je prends une action. Si ce n'est ni l'une ni l'autre de ces choses, j'ai une erreur de syntaxe.

C'est une introduction très, très basique aux grammaires. Pour une compréhension plus approfondie, consultez cet article wiki et recherchez sur le Web des didacticiels de grammaire sans contexte.

En utilisant un arrangement lexer / analyseur, voici un exemple de l'apparence de votre analyseur:

bool simple_command(){
   if (peek_next_token() == WORD){
       get_next_token();
       if (get_next_token() == DIGIT){
           if (get_next_token() == AND_SYMBOL){
               return true;
           } 
       }
   }
   else if (addition_expression()){
       return true;
   }

   return false;
}

bool addition_expression(){
    if (get_next_token() == NUM){
        if (get_next_token() == '+'){
             if (get_next_token() == NUM){
                  return true;
             }
        }
    }
    return false;
}

Ok, donc ce type de code est moche et je ne recommanderais jamais les instructions if imbriquées triple. Mais l'important est d' imaginer essayer de faire cette chose ci-dessus caractère par caractère au lieu d'utiliser vos belles fonctions modulaires "get_next_token" et "peek_next_token" . Sérieusement, essayez-le. Vous n'aimerez pas le résultat. Maintenant, gardez à l'esprit que la grammaire ci-dessus est environ 30 fois moins complexe que presque toute grammaire utile. Voyez-vous l'avantage d'utiliser un lexer?

Honnêtement, les lexers et les parseurs ne sont pas les sujets les plus fondamentaux au monde. Je recommanderais d'abord de lire et de comprendre les grammaires, puis de lire un peu sur les lexers / analyseurs, puis de plonger.

Ma dernière question est la plus stupide: pourquoi un lexer est-il même nécessaire? Il me semble que l'analyseur pourrait aller caractère par caractère et déterminer où il se trouve et ce qu'il attend.

Ce n'est pas stupide, c'est juste la vérité.

Mais la praticabilité dépend en quelque sorte de vos outils et objectifs. Par exemple, si vous utilisez yacc sans lexer et que vous souhaitez autoriser les lettres unicode dans les identificateurs, vous devrez écrire une règle grande et laide qui explicite énumère tous les caractères valides. Alors que, dans un lexer, vous pourriez peut-être demander à une routine de bibliothèque si un personnage est membre de la catégorie des lettres.

Utiliser ou ne pas utiliser de lexer, c'est avoir un niveau d'abstraction entre votre langue et le niveau du personnage. Notez que le niveau de caractère, de nos jours, est une autre abstraction au-dessus du niveau d'octet, qui est une abstraction au-dessus du niveau de bit.

Donc, enfin, vous pouvez même analyser le niveau de bits.

STRING_START + (IDENTIFIER | WHITESPACE) + STRING_START.

Non, ça ne peut pas. Et alors "("? Selon vous, ce n'est pas une chaîne valide. Et s'échappe?

En général, la meilleure façon de traiter les espaces blancs est de l'ignorer, au-delà de la délimitation des jetons. Beaucoup de gens préfèrent des espaces blancs très différents et l'application des règles des espaces blancs est au mieux controversée.