gramática Cima del bucle infinito

Question

he tenido algunas ideas para un nuevo lenguaje de programación flotando en mi cabeza, así que pensé que tomaría un tiro en su aplicación. Un amigo me sugirió que intente usar Treetop (la gema de Ruby) para crear un analizador. La documentación de Treetop es escasa, y nunca antes había hecho este tipo de cosas.

Mi analizador está actuando como si tuviera un bucle infinito en el mismo, pero sin trazas de la pila; está resultando difícil de rastrear. ¿Puede alguien señalarme una guía de análisis sintáctico/AST de nivel de entrada? Realmente necesito algo que enumere las reglas, el uso común, etc. para usar herramientas como Treetop. Mi gramática de analizador está en GitHub, en caso de que alguien quiera ayudarme a mejorarla.

class { 
    initialize = lambda (name) { 
    receiver.name = name 
    } 

    greet = lambda { 
    IO.puts("Hello, #{receiver.name}!") 
    } 
}.new(:World).greet() 

Answer 1

Realmente disfruté Language Implementation Patterns by Parr; ya que Parr creó el generador de analizador ANTLR, es la herramienta que utiliza a lo largo del libro, pero debe ser lo suficientemente simple como para aprender de todos modos.

Lo que me gustó de todo fue la forma en que cada ejemplo el fruto de la anterior; él no comienza con un analizador gigante capaz de AST, sino que lentamente introduce problemas que necesitan más y más 'inteligencia de back-end' para hacer el trabajo, por lo que el libro se adapta bien al lenguaje que necesita analizar.

Lo que deseo es cubierto en un poco más a fondo es los tipos de lenguajes que se puede escribir y dar consejos sobre idiomas cuando se diseñan de Do y qué no hacer Do. He visto algunos idiomas que son un gran dolor para analizar y me hubiera gustado saber más sobre las decisiones de diseño que se podrían haber hecho de otra manera.

Answer 2

me preguntó copas de los árboles para compilar su idioma en un archivo .rb. Eso me dio algo para cavar en:

$ tt -o /tmp/rip.rb /tmp/rip.treetop 

Luego utiliza este pequeño trozo de recrear el bucle:

require 'treetop' 
load '/tmp/rip.rb' 
RipParser.new.parse('') 

Este cuelga. Ahora, ¡no es tan interesante! Una cadena vacía reproduce el comportamiento tan bien como el ejemplo de la docena o la línea en su pregunta.

para averiguar dónde está colgado, he usado una macro de teclado de Emacs para editar rip.rb, la adición de una declaración de depuración a la entrada de cada método. Por ejemplo:

def _nt_root 
    p [__LINE__, '_nt_root'] #DEBUG 
    start_index = index 

Ahora podemos ver el alcance del bucle:

[16, "root"] 
[21, "_nt_root"] 
[57, "_nt_statement"] 
... 
[3293, "_nt_eol"] 
[3335, "_nt_semicolon"] 
[3204, "_nt_comment"] 
[57, "_nt_statement"] 
[57, "_nt_statement"] 
[57, "_nt_statement"] 
... 

Además depuración de allí revela que un número entero se le permite ser una cadena vacía:

rule integer 
    digit* 
end 

Esto permite indirectamente que una instrucción sea una cadena vacía, y la regla de nivel superior statement* para consumir declaraciones vacías para siempre. Cambiando * a + fija el bucle, pero revela otro problema:

/tmp/rip.rb:777:in `_nt_object': stack level too deep (SystemStackError) 
     from /tmp/rip.rb:757:in `_nt_compound_object' 
     from /tmp/rip.rb:1726:in `_nt_range' 
     from /tmp/rip.rb:1671:in `_nt_special_literals' 
     from /tmp/rip.rb:825:in `_nt_literal_object' 
     from /tmp/rip.rb:787:in `_nt_object' 
     from /tmp/rip.rb:757:in `_nt_compound_object' 
     from /tmp/rip.rb:1726:in `_nt_range' 
     from /tmp/rip.rb:1671:in `_nt_special_literals' 
     ... 3283 levels... 

rango es de izquierda recursividad, de forma indirecta, a través de special_literals, literal_object, objeto y compound_object. Treetop, cuando se enfrenta con recursividad a la izquierda, se come hasta que vomita. No tengo una solución rápida para ese problema, pero al menos tienes un rastro de pila para ir desde ahora.

Además, este no es su problema inmediato, pero la definición de digit es impar: puede ser de un dígito o múltiple. Esto causa digit* o digit+ para permitir el (presumiblemente) número entero ilegal 1________2.