Cómo usar la sangría como delimitadores de bloque con bisonte y flex

Question

Me pregunto cómo implementar sangría como delimitadores de bloque en bison + flex. Como en python. Estoy escribiendo mi propio lenguaje de programación (principalmente para divertirme, pero tengo la intención de usarlo junto con un motor de juego), intentaré crear algo especial que minimice el estándar y maximice la velocidad de desarrollo.

Ya he escrito un compilador (en realidad un `langToy ' para el traductor Nasm) en C, pero falló. Por alguna razón, solo fue capaz de manejar una cadena en todo el archivo fuente (bueno, había estado despierto por más de 48 horas, así que ... ya sabes, crisis cerebral).

No sé si las llaves y / o comienzan - > son más fáciles de implementar (no tengo problemas para hacerlo) o si es solo mi cerebro el que se bloquea.

¡Gracias de antemano!

---

Actualización: Bien, no tengo idea de cómo hacerlo con flex. Tengo problemas para devolver varios DEDENTES al analizador. Flex / Bison son relativamente nuevos para mí.

---

Actualización 2: Este es el archivo flexible que he encontrado hasta ahora; no lo entiende del todo:

%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();
}

Puedes intentar jugar con él, tal vez veas lo que me falta. devolver múltiples abolladuras sería una facilidad en Haxe (return t_dedent (num);).

Este código no siempre coincide con las sangrías / abolladuras correctamente.

---

Actualización 3: creo que perderé la esperanza en flex y lo haré a mi manera. Si alguien sabe cómo hacerlo en flex, me alegraría escucharlo de todos modos.

Answer 1

Lo que debe hacer es que Flex cuente la cantidad de espacios en blanco al comienzo de cada línea e inserte un número apropiado de tokens INDENT / UNINDENT para que el analizador los use para agrupar cosas. Una pregunta es qué desea hacer con las pestañas frente a los espacios: ¿solo desea que sean equivalentes con tabulaciones fijas o desea que la sangría sea coherente (por lo tanto, si una línea comienza con una pestaña y la siguiente con un espacio, señala un error, que probablemente sea un poco más difícil).

Suponiendo que desea tabulaciones fijas de 8 columnas, puede usar algo como

%{
/* 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 ...

Debe asegurarse de iniciar el análisis en modo de sangría (para obtener la sangría en la primera línea).

Answer 2

La respuesta de Chris contribuye en gran medida a una solución utilizable, ¡muchas gracias por esto! Desafortunadamente, faltan algunos aspectos más importantes que necesitaba:

• Múltiples salidas (unindents) a la vez. Tenga en cuenta que el siguiente código debe emitir dos salidas después de la llamada a baz :

  def foo():
    if bar:
      baz()
  

• Emite outdents cuando se alcanza el final del archivo y todavía está en algún nivel de sangría.

• Niveles de sangría de diferente tamaño. El código actual de Chris solo funciona correctamente para las sangrías de 1 espacio.

Basado en el código de Chris, se me ocurrió una solución que funciona en todos los casos que he encontrado hasta ahora. He creado un proyecto de plantilla para analizar texto basado en sangría usando flex (y bison) en github: https://github.com/lucasb-eyer/flex-bison-indentation . Es un proyecto totalmente funcional (basado en CMake) que también rastrea la posición de la línea y el rango de columnas del token actual.

En caso de que el enlace se rompa por cualquier razón, aquí está la carne del 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

Los corchetes (y demás) solo son más simples si usa un tokenizador que elimina todos los espacios en blanco (el uso es solo para separar tokens). Consulte esta página (la sección " ¿Cómo analiza el compilador la sangría? ") para algunas ideas sobre la tokenización de Python.

Si no está haciendo tokenización antes de analizar, entonces puede haber trabajo adicional que hacer, depende de cómo esté construyendo el analizador.

Answer 4

Necesita una regla que se parezca a esto (suponiendo que use pestañas para sus sangrías):

\ t: {return TABDENT; }

Francamente, siempre he encontrado que los corchetes (o principio / fin) son más fáciles de escribir y leer, tanto como humano como como escritor lexer / parser.