parsing - nomenclatura - pep8 online

PEG para sangría de estilo Python

Question

Cómo escribiría una gramática de expresión de análisis en cualquiera de los siguientes generadores de analizador ( PEG.js , Citrus , Treetop ) que pueden manejar la sangría de estilo de Python / Haskell / CoffeScript:

Ejemplos de un lenguaje de programación aún no 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 intente escribir un intérprete para los ejemplos anteriores. Solo estoy interesado en el problema de sangría. Otro ejemplo podría ser analizar lo siguiente:

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

Answer 1

Creo que un lenguaje sensible a las indentaciones es sensible al contexto. Creo que PEG solo puede hacer lenguajes sin contexto.

Tenga en cuenta que, aunque la respuesta de nalply es ciertamente correcta, que PEG.js puede hacerlo a través de un estado externo (es decir, las temidas variables globales), puede ser una ruta peligrosa para caminar (peor que los problemas habituales con variables globales). Algunas reglas pueden coincidir inicialmente (y luego ejecutar sus acciones) pero las reglas primarias pueden fallar, lo que hace que la ejecución de la acción no sea válida. Si se modifica el estado externo en dicha acción, puede terminar con un estado no válido. Esto es súper horrible y podría provocar temblores, vómitos y la muerte. Algunos problemas y soluciones están en los comentarios aquí: https://github.com/dmajda/pegjs/issues/45

Answer 2

Entonces, lo que estamos haciendo aquí con sangría es crear algo así como un bloque de estilo C que a menudo tiene su propio alcance léxico. Si estuviera escribiendo un compilador para un lenguaje como ese, creo que trataría de hacer que el lexer no pierda de vista la sangría. Cada vez que la sangría aumenta, podría insertar un token ''{''. Del mismo modo, cada vez que disminuye puede insertar un token ''}''. Luego, escribir una expresión gramatical con llaves explícitas para representar el alcance léxico se vuelve más directo.

Answer 3

Puedes hacer esto en Treetop usando predicados semánticos. En este caso, necesita un predicado semántico que detecte el cierre de un bloque indentado de espacio en blanco debido a la aparición de otra línea que tiene la misma sangría o menos. El predicado debe contar la sangría de la línea de apertura, y devolver verdadero (bloque cerrado) si la sangría de la línea actual ha terminado en la misma longitud o más corta. Debido a que la condición de cierre depende del contexto, no debe ser memorada. Aquí está el código de ejemplo que estoy a punto de agregar a la documentación de Treetop. Tenga en cuenta que he anulado el método de inspección SyntaxNode de Treetop 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 de prueba de controlador para que pueda probarlo 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 4

Pure PEG no puede analizar la sangría.

Pero peg.js puede.

Hice un experimento rápido y sucio (inspirándome en el comentario de Ira Baxter sobre hacer trampa).

/* 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. indent () devuelve una matriz de tokens de sangría y start () desenvuelve la matriz para hacer que el analizador se comporte de forma similar a una secuencia.

peg.js produce para 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",
"",
""
]

Este analizador incluso detecta malas sangrías.

Answer 5

Sé que este es un hilo viejo, pero solo quería agregar un código PEGjs a las respuestas. Este código analizará un fragmento de texto y lo "anidará" en una especie de estructura "AST-ish". Solo va uno profundo y se ve feo, además, realmente no usa los valores de retorno para crear la estructura correcta pero mantiene un árbol en memoria de tu sintaxis y lo devolverá al final. Esto podría volverse difícil de manejar y causar algunos problemas de rendimiento, pero al menos hace lo que se supone que debe hacer.

Nota: ¡Asegúrate de tener 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"