Comment utiliser l'indentation comme délimiteurs de blocs avec les bisons et les flex

Question

J’ai appris à utiliser l’indentation comme délimiteurs de bloc dans bison + flex. Tout comme en python. J'écris mon propre langage de programmation (principalement pour le plaisir, mais j'ai l'intention de l'utiliser conjointement avec un moteur de jeu). Je vais essayer de créer quelque chose de spécial qui minimise le comportement général et optimise la vitesse de développement.

J'ai déjà écrit un compilateur (en fait un `langToy ' au traducteur Nasm) en C, mais cela a échoué. Pour une raison quelconque, il n’a pu gérer qu’une chaîne dans l’ensemble du fichier source (eh bien, je suis réveillé depuis plus de 48 heures - alors ... Vous savez, une crise de cerveau).

Je ne sais pas si les accolades et / ou le début - > fin sont plus faciles à mettre en œuvre (je n’ai pas de problème à le faire) ou si c’est juste mon cerveau qui se bloque.

Merci d'avance!

Mise à jour: D'accord, je ne sais pas comment le faire avec flex. J'ai des problèmes pour renvoyer plusieurs DEDENT à l'analyseur. Flex / Bison sont relativement nouveaux pour moi.

Mise à jour 2: C'est le fichier flex que j'ai créé jusqu'à présent; il ne comprend pas tout à fait:

%x t
%option noyywrap

%{
  int lineno = 0, ntab = 0, ltab = 0, dedent = 0;
%}

%%

<*>\n  { ntab = 0; BEGIN(t); }
<t>\t  { ++ntab; }
<t>.   { int i; /* my compiler complains not c99 if i use for( int i=0... */
         if( ntab > ltab )
           printf("> indent >\n");
         else if( ntab < ltab )
           for( i = 0; i < ltab - ntab; i++ )
             printf("< dedent <\n");
         else
           printf("=        =\n");

         ltab = ntab; ntab = 0;
         BEGIN(INITIAL);
         /* move to next rule */
         REJECT;}
.    /* ignore everything else for now */

%%

main()
{
  yyin = fopen( "test", "r" );
  yylex();
}

Vous pouvez essayer de jouer avec, peut-être que vous voyez ce que je manque. le retour de plusieurs versements serait une facilité dans Haxe (retour t_dedent (num);).

Ce code ne correspond pas toujours correctement aux retraits / déductions.

Mise à jour 3: Je pense que je vais perdre espoir en Flex et le faire à ma façon. Si quelqu'un sait comment le faire en flex, je serais heureux de l'entendre de toute façon.

Answer 1

Ce que vous devez faire est de faire en sorte que flex compte le nombre d’espaces au début de chaque ligne et insère un nombre approprié de jetons INDENT / UNINDENT que l’analyseur utilisera pour regrouper les éléments. Une question concerne ce que vous voulez faire à propos des tabulations par rapport aux espaces - voulez-vous simplement qu’elles soient équivalentes à des taquets de tabulation fixes, ou voulez-vous exiger l’indentation pour être cohérent (si une ligne commence par une tabulation et la suivante)? avec un espace, vous signalez une erreur, ce qui est probablement un peu plus difficile).

En supposant que vous vouliez des tabulations à 8 colonnes fixes, vous pouvez utiliser quelque chose comme

%{
/* globals to track current indentation */
int current_line_indent = 0;   /* indentation of the current line */
int indent_level = 0;          /* indentation level passed to the parser */
%}

%x indent /* start state for parsing the indentation */
%s normal /* normal start state for everything else */

%%
<indent>" "      { current_line_indent++; }
<indent>"\t"     { current_line_indent = (current_line_indent + 8) & ~7; }
<indent>"\n"     { current_line_indent = 0; /*ignoring blank line */ }
<indent>.        {
                   unput(*yytext);
                   if (current_line_indent > indent_level) {
                       indent_level++;
                       return INDENT;
                   } else if (current_line_indent < indent_level) {
                       indent_level--;
                       return UNINDENT;
                   } else {
                       BEGIN normal;
                   }
                 }

<normal>"\n"     { current_line_indent = 0; BEGIN indent; }
... other flex rules ...

Vous devez vous assurer de lancer l'analyse en mode retrait (pour obtenir le retrait sur la première ligne).

Answer 2

La réponse de Chris va très loin vers une solution utilisable, merci beaucoup pour cela! Malheureusement, il manque quelques aspects plus importants dont j'avais besoin:

• Plusieurs surpassements (unindents) à la fois. Considérez que le code suivant devrait émettre deux à la suite de l'appel à baz :

  def foo():
    if bar:
      baz()
  

• L'émission est dépassée lorsque la fin du fichier est atteinte et se trouve toujours à un niveau d'indentation.

• Niveaux d'indentation de taille différente. Le code actuel de Chris ne fonctionne correctement que pour les retraits d'une case.

Sur la base du code de Chris, j'ai proposé une solution qui fonctionne dans tous les cas que j'ai rencontrés jusqu'à présent. J'ai créé un projet de modèle pour analyser le texte basé sur l'indentation à l'aide de flex (et bison) sur github: https://github.com/lucasb-eyer/flex-bison-indentation . C'est un projet entièrement fonctionnel (basé sur CMake) qui suit également la position de la ligne et la plage de colonnes du jeton actuel.

Juste au cas où le lien se briserait pour une raison quelconque, voici la viande du lexer:

#include <stack>

int g_current_line_indent = 0;
std::stack<size_t> g_indent_levels;
int g_is_fake_outdent_symbol = 0;

static const unsigned int TAB_WIDTH = 2;

#define YY_USER_INIT { \
    g_indent_levels.push(0); \
    BEGIN(initial); \
}
#include "parser.hh"

%}

%x initial
%x indent
%s normal

%%
    int indent_caller = normal;

 /* Everything runs in the <normal> mode and enters the <indent> mode
    when a newline symbol is encountered.
    There is no newline symbol before the first line, so we need to go
    into the <indent> mode by hand there.
 */
<initial>.  { set_yycolumn(yycolumn-1); indent_caller = normal; yyless(0); BEGIN(indent); }
<initial>\n { indent_caller = normal; yyless(0); BEGIN(indent); }    

<indent>" "     { g_current_line_indent++; }
<indent>\t      { g_current_line_indent = (g_current_line_indent + TAB_WIDTH) & ~(TAB_WIDTH-1); }
<indent>\n      { g_current_line_indent = 0; /* ignoring blank line */ }
<indent><<EOF>> {
                    // When encountering the end of file, we want to emit an
                    // outdent for all indents currently left.
                    if(g_indent_levels.top() != 0) {
                        g_indent_levels.pop();

                        // See the same code below (<indent>.) for a rationale.
                        if(g_current_line_indent != g_indent_levels.top()) {
                            unput('\n');
                            for(size_t i = 0 ; i < g_indent_levels.top() ; ++i) {
                                unput(' ');
                            }
                        } else {
                            BEGIN(indent_caller);
                        }

                        return TOK_OUTDENT;
                    } else {
                        yyterminate();
                    }
                }

<indent>.       {
                    if(!g_is_fake_outdent_symbol) {
                        unput(*yytext);
                    }
                    g_is_fake_outdent_symbol = 0;
                    // -2: -1 for putting it back and -1 for ending at the last space.
                    set_yycolumn(yycolumn-1);

                    // Indentation level has increased. It can only ever
                    // increase by one level at a time. Remember how many
                    // spaces this level has and emit an indentation token.
                    if(g_current_line_indent > g_indent_levels.top()) {
                        g_indent_levels.push(g_current_line_indent);
                        BEGIN(indent_caller);
                        return TOK_INDENT;
                    } else if(g_current_line_indent < g_indent_levels.top()) {
                        // Outdenting is the most difficult, as we might need to
                        // outdent multiple times at once, but flex doesn't allow
                        // emitting multiple tokens at once! So we fake this by
                        // 'unput'ting fake lines which will give us the next
                        // outdent.
                        g_indent_levels.pop();

                        if(g_current_line_indent != g_indent_levels.top()) {
                            // Unput the rest of the current line, including the newline.
                            // We want to keep it untouched.
                            for(size_t i = 0 ; i < g_current_line_indent ; ++i) {
                                unput(' ');
                            }
                            unput('\n');
                            // Now, insert a fake character indented just so
                            // that we get a correct outdent the next time.
                            unput('.');
                            // Though we need to remember that it's a fake one
                            // so we can ignore the symbol.
                            g_is_fake_outdent_symbol = 1;
                            for(size_t i = 0 ; i < g_indent_levels.top() ; ++i) {
                                unput(' ');
                            }
                            unput('\n');
                        } else {
                            BEGIN(indent_caller);
                        }

                        return TOK_OUTDENT;
                    } else {
                        // No change in indentation, not much to do here...
                        BEGIN(indent_caller);
                    }
                }

<normal>\n    { g_current_line_indent = 0; indent_caller = YY_START; BEGIN(indent); }

Answer 3

Les accolades (et autres) ne sont plus simples si vous utilisez un tokenizer qui supprime tous les espaces (utilisez simplement pour séparer les jetons). Voir cette page (la section " Comment le compilateur analyse-t-il l'indentation? ") pour quelques idées sur la création de jetons Python.

Si vous n'effectuez pas de création de jetons avant l'analyse, des travaux supplémentaires peuvent éventuellement être nécessaires, cela dépend de la manière dont vous générez l'analyseur.

Answer 4

Vous avez besoin d'une règle qui ressemble à ceci (si vous utilisez des tabulations pour vos retraits):

\ t: {return TABDENT; }

Franchement, j'ai toujours trouvé des accolades (ou un début / une fin) plus faciles à écrire et à lire, en tant qu'être humain et en tant que rédacteur lexer / parseur.