programming-languages - portero - que es un fuera de lugar en el futbol yahoo

¿Cómo implementarías la regla 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.

Brevemente: regla de fuera de juego significa en este contexto que la sangría se está reconociendo como un elemento sintáctico.

Aquí está la regla de fuera de juego en pseudocódigo para hacer tokenizadores que capturan sangrías en forma utilizable, no quiero limitar las 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 creador de listas no genera más de una NEWLINE a la vez, y no genera NEWLINE cuando está surgiendo una sangría. 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 nueva línea de todos modos, de esta forma puedes separar las expresiones con NEWLINE mientras mantienes el INDENT DEDENT como un avance de la expresión.

Answer 1

Tokenizer en ruby ​​por 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

Solo funciona para sangría de dos espacios. El resultado es algo así como ["Hello there from level 0/n", :INDENT, "This/nis level/ntwo/n", :DEDENT, "This is level0 again/n"] .

Answer 2

He escrito tokenizers y analizadores sintácticos para un par de pequeños lenguajes específicos de dominio centrados en sangría en los últimos años, y lo que tienes allí parece bastante razonable para mí, 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.

La conversión de NEWLINE NEWLINE INDENT a simplemente INDENT 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.

Tenía una aplicación que necesitaba ser un poco más flexible acerca de las reglas de sangría, esencialmente dejando que el analizador las aplicara cuando fuera necesario; lo siguiente tenía que ser válido 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

lo cual no funciona muy bien con los 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 averiguar dónde están los niveles de indentación 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. Nuevamente, 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 poco habitual. 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 3

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

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

Tengo un lector 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. Asi que

line1
    line2
    line3
line4

daría la transmisión de fichas

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

Esto me permite escribir producciones gramaticales claras para las afirmaciones sin preocuparme por detectar el final de las instrucciones, incluso cuando terminan con subbloques anidados y sangrados, algo que puede ser difícil si está coincidiendo con NEWLINES (y DEDENTES).

Aquí está 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 ()

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