¿Cómo implementaría la regla de fuera de juego?

Question

Ya he escrito un generador que hace el truco, pero me gustaría saber la mejor manera posible de implementar la regla de fuera de juego.

En pocas palabras: Off-side rule significa en este contexto que la indentación se reconoce como un elemento sintáctico.

Esta es la regla del fuera de juego en pseudocódigo para hacer que la captura tokenizers hendidura en forma utilizable, no quiero limitar respuestas por idioma:

token NEWLINE 
    matches r"\n\ *" 
    increase line count 
    pick up and store the indentation level 
    remember to also record the current level of parenthesis 

procedure layout tokens 
    level = stack of indentation levels 
    push 0 to level 
    last_newline = none 
    per each token 
     if it is NEWLINE put it to last_newline and get next token 
     if last_newline contains something 
      extract new_level and parenthesis_count from last_newline 
      - if newline was inside parentheses, do nothing 
      - if new_level > level.top 
       push new_level to level 
       emit last_newline as INDENT token and clear last_newline 
      - if new_level == level.top 
       emit last_newline and clear last_newline 
      - otherwise 
       while new_level < level.top 
        pop from level 
        if new_level > level.top 
         freak out, indentation is broken. 
        emit last_newline as DEDENT token 
       clear last_newline 
     emit token 
    while level.top != 0 
     emit token as DEDENT token 
     pop from level 

comments are ignored before they are getting into the layouter 
layouter lies between a lexer and a parser 

Este Layouter no genera más de una nueva línea al tiempo, y no genera NEWLINE cuando hay una sangría por venir. Por lo tanto, las reglas de análisis siguen siendo bastante simples. Es bastante bueno, creo, pero informar si hay mejor manera de lograrlo.

Mientras uso esto por un tiempo, he notado que después de los DEDENTES puede ser bueno emitir newline de todos modos, de esta manera usted puede separar las expresiones con NEWLINE manteniendo el INDENT DEDENT como un avance de la expresión.

Answer 1

He escrito tokenizadores y analizadores sintácticos para un par de pequeños lenguajes específicos de dominio centrados en sangrías en los últimos años, y lo que tienes allí me parece bastante razonable, para lo que sea que valga la pena. Si no me equivoco, su método es bastante similar al de Python, por ejemplo, que parece que debería tener algo de peso.

Convertir NEWLINE NEWLINE INDENT en simplemente INDENTAR antes de que llegue al analizador definitivamente parece ser la forma correcta de hacer las cosas; ¡es una pena (IME) estar siempre mirando hacia adelante en el analizador sintáctico! De hecho, he hecho ese paso como una capa separada en lo que terminó siendo un proceso de tres pasos: el primero combinó lo que hacen tu lexer y layouter menos todas las cosas de NEWLINE lookahead (que lo hicieron muy simple), el segundo (también muy simple)) layer NEWLED consecutivas dobladas y NEWLINE INDENT convertido a solo INDENT (o, en realidad, COLON NEWLINE INDENT a INDENT, ya que en este caso todos los bloques sangrados siempre fueron precedidos por dos puntos), entonces el analizador fue la tercera etapa además de eso. Pero también tiene mucho sentido para mí hacer las cosas de la forma en que las describiste, especialmente si deseas separar el Lexer del creador de planos, lo que presumiblemente querrías hacer si estuvieras usando una herramienta de generación de código hacer tu Lexer, por ejemplo, como es práctica común.

tuve una aplicación que necesita para ser un poco más flexible en cuanto a las reglas de sangría, dejando esencialmente el analizador de hacerlas cumplir cuando sea necesario - A continuación necesita para ser válidos en ciertos contextos, por ejemplo:

this line introduces an indented block of literal text: 
    this line of the block is indented four spaces 
    but this line is only indented two spaces 

que no funciona muy bien con tokens INDENT/DEDENT, ya que terminas necesitando generar un INDENT para cada columna de sangría y un igual número de DEDENTES en el camino de regreso, a menos que mires hacia adelante para descubrir dónde está Los niveles de sangrado van a terminar siendo, lo que no parece que quieras que haga un tokenizador. En ese caso probé algunas cosas diferentes y terminé simplemente almacenando un contador en cada token NEWLINE que dio el cambio en la sangría (positiva o negativa) para la siguiente línea lógica. (Cada token también almacenaba todos los espacios en blanco finales, en caso de que fuera necesario conservarlos, para NEWLINE, el espacio en blanco almacenado incluía el EOL mismo, las líneas en blanco intermedias y la sangría en la siguiente línea lógica.) No token en absoluto INDENT o DEDENT. Lograr que el analizador manejara eso fue un poco más trabajo que simplemente anidar INDENT y DEDENT, y bien podría haber sido un infierno con una gramática complicada que necesitaba un generador de analizadores sofisticado, pero no era tan malo como lo había temido, ya sea. De nuevo, no es necesario que el analizador mire hacia adelante desde NEWLINE para ver si hay un INDENT en este esquema.

Aún así, creo que estarías de acuerdo en que permitir y preservar todo tipo de espacios en blanco de aspecto loco en el tokenizador/creador de listas y dejar que el analizador decida qué es un literal y qué es un código es un requisito inusual. Ciertamente no querrás que tu analizador se cargue con ese contador de sangría si solo quisieras analizar el código de Python, por ejemplo. La forma en que haces las cosas es casi seguro que es el enfoque correcto para tu aplicación y muchas otras. Aunque si alguien más tiene ideas sobre la mejor manera de hacer este tipo de cosas, obviamente me encantaría escucharlas ....

Answer 2

He estado experimentando con esto recientemente, y llegué a la conclusión de que, para mis necesidades al menos, quería que NEWLINES marcara el final de cada "declaración", ya sea la última declaración en un bloque sangrado o no, es decir, necesito las líneas nuevas incluso antes de DEDENTAR.

Mi solución fue darle la vuelta, y en lugar de que NEWLINES marque el final de las líneas, utilizo un token de LÍNEA para marcar el comienzo de una línea.

Tengo un lexer que contrae las líneas vacías (incluidas las líneas de solo comentario) y emite un solo token de LÍNEA con información sobre la sangría de la última línea. Entonces mi función de preprocesamiento toma esta secuencia de token y agrega INDENT o DEDENT "entre" cualquier línea donde la sangría cambie. Así

line1 
    line2 
    line3 
line4 

daría la cadena de componentes léxicos

LINE "line1" INDENT LINE "line2" LINE "line3" DEDENT LINE "line4" EOF 

Esto me permite escribir producciones gramaticales claras para declaraciones sin preocuparse por la detección del final de los estados, incluso cuando terminan con anidada, sangría, sub-bloques, algo eso puede ser difícil si coincide con NEWLINES (y DEDENTOS) en su lugar.

He aquí el núcleo del preprocesador, escrito en O'Caml:

match next_token() with 
     LINE indentation -> 
     if indentation > !current_indentation then 
      (
      Stack.push !current_indentation indentation_stack; 
      current_indentation := indentation; 
      INDENT 
     ) 
     else if indentation < !current_indentation then 
      (
      let prev = Stack.pop indentation_stack in 
       if indentation > prev then 
       (
        current_indentation := indentation; 
        BAD_DEDENT 
       ) 
       else 
       (
        current_indentation := prev; 
        DEDENT 
       ) 
     ) 
     else (* indentation = !current_indentation *) 
      let token = remove_next_token() in 
      if next_token() = EOF then 
       remove_next_token() 
      else 
       token 
    | _ -> 
     remove_next_token() 

no he añadido soporte para paréntesis todavía, pero que debería ser una simple extensión. Sin embargo, evita emitir una LINEA perdida al final del archivo.

Answer 3

Tokenizer de rubí para la diversión:

def tokenize(input) 
    result, prev_indent, curr_indent, line = [""], 0, 0, "" 
    line_started = false 

    input.each_char do |char| 

    case char 
    when ' ' 
     if line_started 
     # Content already started, add it. 
     line << char 
     else 
     # No content yet, just count. 
     curr_indent += 1 
     end 
    when "\n" 
     result.last << line + "\n" 
     curr_indent, line = 0, "" 
     line_started = false 
    else 
     # Check if we are at the first non-space character. 
     unless line_started 
     # Insert indent and dedent tokens if indentation changed. 
     if prev_indent > curr_indent 
      # 2 spaces dedentation 
      ((prev_indent - curr_indent)/2).times do 
      result << :DEDENT 
      end 
      result << "" 
     elsif prev_indent < curr_indent 
      result << :INDENT 
      result << "" 
     end 

     prev_indent = curr_indent 
     end 

     # Mark line as started and add char to line. 
     line_started = true; line << char 
    end 

    end 

    result 
end 

sólo funciona para dos-espacio-muesca. El resultado es algo así como ["Hello there from level 0\n", :INDENT, "This\nis level\ntwo\n", :DEDENT, "This is level0 again\n"].