compiler construction - opciones - Haskell-¿Cómo representar mejor la gramática de un lenguaje de programación?

lenguajes funcionales

Question

He estado buscando en Haskell y me gustaría escribir un compilador (como un ejercicio de aprendizaje) en él, ya que muchas de sus características innatas se pueden aplicar fácilmente a un compilador (particularmente un compilador decente recursivo).

Lo que no puedo entender es cómo representar la gramática de un idioma de una manera haskelliana. Mi primer pensamiento fue usar definiciones de tipos de datos recursivos, pero no puedo ver cómo los uso para compararlos con palabras clave en el idioma ("si"), por ejemplo.

Pensamientos y sugerencias muy apreciados,

Pete

Answer 1

Desafortunadamente, no existe una gramática de Haskell para ANTLR , pero quizás pueda usar el enlace citado anteriormente para crear una. ANTLR es un gran generador de analizador basado en Java.

Steve Yegge tiene un buen blog sobre compiladores de escritura, si necesita más motivación. Es entretenido.

Answer 2

No puedo decir por el tono de su pregunta si esta es la primera vez que intenta escribir un compilador, o si ha escrito compiladores antes y está buscando consejos específicos para Haskell. Si ya eres un gurú del compilador, los pequeños consejos que tengo para ofrecerte no te ayudarán. :)

Las gramáticas del lenguaje de programación se representan comúnmente en formato BNF , que puede ser utilizado por herramientas como Yacc o Bison para analizar el código fuente. No sé si esto cuenta como una manera haskelliana de hacerlo, pero es la única forma en que he escuchado. Probablemente pueda desenterrar una herramienta para generar código Haskell a partir de una gramática BNF; Encontré esta herramienta que dice ser capaz de hacer eso.

Una rápida búsqueda en Google mostró esta gramática de BNF para Haskell , y probablemente haya otras por ahí, en caso de que quieras escribir un compilador para Haskell (¿quizás te gustaría escribir un compilador de Haskell en Haskell?) Gramáticas de BNF para C y Java parece ser popular.

Finalmente, si estás buscando un libro sobre el diseño del compilador, el texto clásico es "El Libro del Dragón" .

Answer 3

Tal vez puedas mirar algunos proyectos del mundo real para ver cómo lo hacen.

Hace menos de una semana, el proyecto Language-Python se anunció en la lista de correo de Haskell-Cafe . Es un analizador Python implementado en Haskell, que utiliza el generador Happy parser y el generador Alex lexer.

Y, por supuesto, hay Pugs , una implementación de Perl 6 en Haskell (la primera implementación de Perl 6 que se ajusta a un subconjunto significativo de la especificación de Perl 6).

Answer 4

Un tipo de datos recursivo está bien para esto. Por ejemplo, dado el lenguaje:

expr ::= var
      |  "true"
      |  "false"
      |  "if" expr "then" expr "else" expr
      |  "(" expr ")"

una expresión de ejemplo en este lenguaje sería:

if true then x else (if false then y else true)

Tu tipo de datos Haskell se vería así:

data Expr = Var String
          | Lit Bool
          | If Expr Expr Expr

Su analizador luego se encarga de traducir, por ejemplo, x en Var "x" , y true en Lit True , etc. Es decir:

parse "if x then false else true" 
  ==  If (Var "x") (Lit False) (Lit True)

Para escribir analizadores, puede usar su propio rol usando las técnicas mencionadas en la respuesta de Norman, o usar Parsec o usar generadores de análisis como Happy .

Answer 5

Usted representa programas que usan tipos de datos algebraicos recursivos, y para analizar programas usa combinadores de análisis . Hay un millón de sabores; Encontrará tres útiles tutoriales en el calendario de mi clase para el lunes 23 de marzo de 2009.

• Graham Hutton y Erik Meijer, Functional Pearl: Monadic parsing en Haskell (1998)
• Graham Hutton, Funciones de orden superior para análisis (1992)
• Jeroen Fokker, analizadores funcionales (1995)

El papel de Hutton y Meijer es el más corto y simple, pero usa mónadas, que no son obvias para el aficionado. Sin embargo, tienen una gramática muy buena de y un analizador de expresiones. Si aún no has desarrollado monadas, el tutorial de Fokker es el indicado.