PEG para el sangrado de estilo de Python

Question

¿Cómo escribir una de análisis de expresión Gramática en cualquiera de los siguientes generadores de analizadores sintácticos ( PEG.js , Citrus , copa de árbol ) que puede manejar muesca estilo Python / Haskell / coffeescript:

Los ejemplos de un lenguaje de programación que aún no es existente:

square x =
    x * x

---

cube x =
    x * square x

---

fib n =
  if n <= 1
    0
  else
    fib(n - 2) + fib(n - 1) # some cheating allowed here with brackets

Actualización: No trate de escribir un intérprete para los ejemplos anteriores. Sólo estoy interesado en el problema de sangrado. Otro ejemplo podría ser analizar el siguiente:

foo
  bar = 1
  baz = 2
tap
  zap = 3

# should yield (ruby style hashmap):
# {:foo => { :bar => 1, :baz => 2}, :tap => { :zap => 3 } }

Answer 1

Pure PEG no puede muesca de análisis.

Pero peg.js puede.

Me hizo un experimento rápido y sucio (de haber sido inspirado por el comentario de Ira Baxter acerca de hacer trampa) y escribió un tokenizer sencilla.

Para una solución más completa (un analizador completo) consulte esta pregunta: Analizar muesca nivel con PEG.js

/* Initializations */
{
  function start(first, tail) {
    var done = [first[1]];
    for (var i = 0; i < tail.length; i++) {
      done = done.concat(tail[i][1][0])
      done.push(tail[i][1][1]);
    }
    return done;
  }

  var depths = [0];

  function indent(s) {
    var depth = s.length;

    if (depth == depths[0]) return [];

    if (depth > depths[0]) {
      depths.unshift(depth);
      return ["INDENT"];
    }

    var dents = [];
    while (depth < depths[0]) {
      depths.shift();
      dents.push("DEDENT");
    }

    if (depth != depths[0]) dents.push("BADDENT");

    return dents;
  }
}

/* The real grammar */
start   = first:line tail:(newline line)* newline? { return start(first, tail) }
line    = depth:indent s:text                      { return [depth, s] }
indent  = s:" "*                                   { return indent(s) }
text    = c:[^\n]*                                 { return c.join("") }
newline = "\n"                                     {}

depths es una pila de indentaciones. guión () devuelve un conjunto de fichas de sangría y start () desenvuelve la matriz para que el analizador se comporta un poco como una corriente.

peg.js produce el texto:

alpha
  beta
  gamma
    delta
epsilon
    zeta
  eta
theta
  iota

estos resultados:

[
   "alpha",
   "INDENT",
   "beta",
   "gamma",
   "INDENT",
   "delta",
   "DEDENT",
   "DEDENT",
   "epsilon",
   "INDENT",
   "zeta",
   "DEDENT",
   "BADDENT",
   "eta",
   "theta",
   "INDENT",
   "iota",
   "DEDENT",
   "",
   ""
]

Esta tokenizer incluso atrapa malos guiones.

Answer 2

creo un lenguaje muesca sensible como esa es sensible al contexto. Creo PEG puede hacer solamente langauges libres de contexto.

Tenga en cuenta que, mientras que la respuesta de nalply es ciertamente correcto que PEG.js puede hacerlo a través de estado externo (es decir, las variables globales temidas), puede ser un camino peligroso caminar hacia abajo (peores que los problemas habituales con las variables globales). Algunas reglas pueden igualar inicialmente (y luego ejecutar sus acciones) pero las reglas padres pueden fallar causando así la carrera de acción para ser inválida. Si se cambia el estado externo de tal acción una, puede terminar con estado no válido. Esto es súper horrible, y podría dar lugar a temblores, vómitos y muerte. Algunos problemas y soluciones a esto se encuentran en los comentarios aquí: https://github.com/dmajda/pegjs / temas / 45

Answer 3

Así que lo que realmente estamos haciendo aquí con muesca está creando algo así como unos bloques de tipo C que a menudo tienen su propio ámbito léxico. Si estuviera escribiendo un compilador para un lenguaje como el que yo creo que volvería a tratar de tener la pista lexer torreón de la sangría. Cada vez aumenta la sangría que podría insertar un '{' token. De la misma manera cada vez que se disminuye podría inserción de un '}' token. A continuación, escribir una gramática de expresión con llaves explícitos para representar léxica alcance se vuelve más sencillo.

Answer 4

Se puede hacer esto en copa de árbol mediante el uso de predicados semánticos. En este caso es necesario un predicado semántico que detecta el cierre de un espacio en blanco sangría de bloque debido a la ocurrencia de otra línea que tiene el mismo o menor sangrado. El predicado debe contar con la sangría desde la línea de apertura, y devolver verdadero (bloque cerrado) si la sangría de la línea actual ha terminado en el mismo o menor longitud. Debido a la condición de cierre es dependiente del contexto, no hay que memoized. Aquí está el código de ejemplo que voy a añadir a la documentación de copa de árbol. Tenga en cuenta que hemos anulado SyntaxNode de copa de árbol inspeccionar método para que sea más fácil visualizar el resultado.

grammar IndentedBlocks
  rule top
    # Initialise the indent stack with a sentinel:
    &{|s| @indents = [-1] }
    nested_blocks
    {
      def inspect
        nested_blocks.inspect
      end
    }
  end

  rule nested_blocks
    (
      # Do not try to extract this semantic predicate into a new rule.
      # It will be memo-ized incorrectly because @indents.last will change.
      !{|s|
        # Peek at the following indentation:
        save = index; i = _nt_indentation; index = save
        # We're closing if the indentation is less or the same as our enclosing block's:
        closing = i.text_value.length <= @indents.last
      }
      block
    )*
    {
      def inspect
        elements.map{|e| e.block.inspect}*"\n"
      end
    }
  end

 rule block
    indented_line       # The block's opening line
    &{|s|               # Push the indent level to the stack
      level = s[0].indentation.text_value.length
      @indents << level
      true
    }
    nested_blocks       # Parse any nested blocks
    &{|s|               # Pop the indent stack
      # Note that under no circumstances should "nested_blocks" fail, or the stack will be mis-aligned
      @indents.pop
      true
    }
    {
      def inspect
        indented_line.inspect +
          (nested_blocks.elements.size > 0 ? (
            "\n{\n" +
            nested_blocks.elements.map { |content|
              content.block.inspect+"\n"
            }*'' +
            "}"
          )
          : "")
      end
    }
  end

  rule indented_line
    indentation text:((!"\n" .)*) "\n"
    {
      def inspect
        text.text_value
      end
    }
  end

  rule indentation
    ' '*
  end
end

Aquí hay un pequeño programa piloto de pruebas para que pueda probar fácilmente:

require 'polyglot'
require 'treetop'
require 'indented_blocks'

parser = IndentedBlocksParser.new

input = <<END
def foo
  here is some indented text
    here it's further indented
    and here the same
      but here it's further again
      and some more like that
    before going back to here
      down again
  back twice
and start from the beginning again
  with only a small block this time
END 

parse_tree = parser.parse input

p parse_tree

Answer 5

Yo sé que esto es un hilo viejo, pero yo sólo quería añadir algo de código PEGjs a las respuestas. Este código será analizar un fragmento de texto y "nido" en una especie de estructura "AST-ish". Sólo se da un profundo y se ve feo, además, que en realidad no utilizar los valores de retorno para crear la estructura correcta, pero mantiene un árbol en la memoria de su sintaxis y volverá que al final. Esto bien podría convertirse en difícil de manejar y causar algunos problemas de rendimiento, pero al menos se hace lo que se supone que es.

Nota: asegúrese de que tiene pestañas en lugar de espacios

{ 
    var indentStack = [], 
        rootScope = { 
            value: "PROGRAM",
            values: [], 
            scopes: [] 
        };

    function addToRootScope(text) {
        // Here we wiggle with the form and append the new
        // scope to the rootScope.

        if (!text) return;

        if (indentStack.length === 0) {
            rootScope.scopes.unshift({
                text: text,
                statements: []
            });
        }
        else {
            rootScope.scopes[0].statements.push(text);
        }
    }
}

/* Add some grammar */

start
  = lines: (line EOL+)*
    { 
        return rootScope;
    }


line
  = line: (samedent t:text { addToRootScope(t); }) &EOL
  / line: (indent t:text { addToRootScope(t); }) &EOL
  / line: (dedent t:text { addToRootScope(t); }) &EOL
  / line: [ \t]* &EOL
  / EOF

samedent
  = i:[\t]* &{ return i.length === indentStack.length; }
    {
        console.log("s:", i.length, " level:", indentStack.length);
    }

indent
  = i:[\t]+ &{ return i.length > indentStack.length; }
    {
        indentStack.push(""); 
        console.log("i:", i.length, " level:", indentStack.length);
    }

dedent
    = i:[\t]* &{ return i.length < indentStack.length; }
      {
          for (var j = 0; j < i.length + 1; j++) {
              indentStack.pop();
          } 
          console.log("d:", i.length + 1, " level:", indentStack.length);  
      }

text
    = numbers: number+  { return numbers.join(""); } 
    / txt: character+   { return txt.join(""); }


number
    = $[0-9] 

character 
    = $[ a-zA-Z->+]  
__
    = [ ]+

_ 
    = [ ]*

EOF 
    = !.

EOL
    = "\r\n" 
    / "\n" 
    / "\r"