Haskell - Como mejor para representar la gramática de un lenguaje de programación?

Question

He estado buscando en Haskell y que había bastante gusta escribir un compilador (como un ejercicio de aprendizaje) en el mismo, ya que muchos de sus características innatas pueden aplicarse fácilmente a un compilador (particularmente un compilador decente recursivo) .

Lo que no puedo sacarlo de mi cabeza es la forma de representar la gramática de una lengua de una manera Haskell-ian. Lo primero que pensé fue utilizar las definiciones de tipos de datos recursivas, pero no puedo ver cómo los utilizo a contrastar palabras clave en el idioma ( "si"), por ejemplo.

Pensamientos y sugerencias muy apreciados,

Pete

Answer 1

Un tipo de datos recursiva está muy bien para esto. Por ejemplo, dada la lengua:

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

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

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

Su Haskell tipo de datos sería algo como esto:

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

Su analizador se encarga entonces de traducir, por ejemplo, en x 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 analizadores de escritura se puede rodar su propio uso de las técnicas mencionadas en la respuesta de Norman, o el uso de Parsec o el uso del analizador generadores como feliz .

Answer 2

Usted manifiesta programas utilizando los tipos de datos algebraicos mutuamente recursivos, y permite analizar programas que utiliza combinadores analisis de . Hay un millón de sabores; se encuentran tres tutoriales útiles sobre el horario rel="noreferrer"> lunes por, 23 de marzo de 2009. son

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

El papel Hutton y Meijer es la más corta y sencilla, pero utiliza mónadas, que no son obvias para el aficionado. Sin embargo, tienen una muy buena gramática del analizador y las expresiones adecuadas. Si no asimilo mónadas sin embargo, el tutorial de Fokker es el uno.

Answer 3

Tal vez se puede ver en algunos proyectos del mundo real para ver cómo lo hacen?

Hace menos de una semana, el lenguaje Python proyecto fue anunció en la Haskell-Cafe lista de correo . Es un Python analizador implementado en Haskell, usando el feliz generador de análisis y generador de analizador léxico Alex .

Y, por supuesto, no es amasados, una implementación de Perl 6 en Haskell (la primera implementación de Perl 6 que se ajusta a un subconjunto importante de la especificación de Perl 6).

Answer 4

No puedo decir por el tono de su pregunta de si esta es la primera vez que intenta escribir un compilador, o si ha compiladores escrito antes y están en busca de asesoramiento específico a Haskell. Si ya es un gurú del compilador, lo pequeño consejo que tengo para ofrecer no va a ayudar. :)

gramáticas del lenguaje de programación se representan comúnmente en BNF forma , que puede ser utilizado por herramientas como Yacc o bisonte para analizar el código fuente. No sé si esto cuenta como una forma Haskell-ian para hacerlo, pero es la única manera que he oído hablar. Con algo de investigación en torno a que probablemente pueda buscar una herramienta para generar código Haskell de una gramática BNF; He encontrado este herramienta que pretende ser capaz de hacer que.

Una rápida búsqueda en Google se presentó esta gramática BNF para Haskell , y probablemente hay otros por ahí, en caso de que desea escribir un compilador de Haskell (tal vez desea escribir un compilador de Haskell en Haskell?) gramáticas de BNF para C y Java parecen ser popular.

Por último, si usted está buscando un libro sobre el diseño del compilador, el texto clásico es " el dragón libro ".

Answer 5

Desafortunadamente no hay gramática Haskell para antlr , pero tal vez usted puede utilizar el enlace antes citado para crear una. Antlr es un gran generador de análisis basado en Java.

Steve Yegge tiene un bonito sobre escribir compiladores, si necesita más motivación. Es entretenido.