Haskell - Como melhor para representar a gramática de uma linguagem de programação?
https://stackoverflow.com/questions/679815
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu estive olhando Haskell e eu gosto muito de escrever um compilador (como um exercício de aprendizagem) na mesma, uma vez que muitas de suas características inatas pode ser facilmente aplicada a um compilador (particularmente um compilador decente recursivo) .
O que eu não consigo colocar minha cabeça em torno é como representar a gramática de uma língua de uma forma Haskell-ian. Meu primeiro pensamento foi usar definições tipo recursivo, mas eu não posso ver como eu usá-los para o jogo contra palavras-chave na língua ( "if"), por exemplo.
Os pensamentos e sugestões muito apreciada,
Pete
Solução
Um tipo recursivo é bom para isso. Por exemplo, dado o idioma:
expr ::= var
| "true"
| "false"
| "if" expr "then" expr "else" expr
| "(" expr ")"
uma expressão exemplo nesta língua seria:
if true then x else (if false then y else true)
O seu tipo de dados Haskell seria algo parecido com isto:
data Expr = Var String
| Lit Bool
| If Expr Expr Expr
O seu analisador, em seguida, tem o cuidado de traduzir, por exemplo, x em Var "x" e true em Lit True, etc. ou seja:.
parse "if x then false else true"
== If (Var "x") (Lit False) (Lit True)
Para escrever analisadores você pode rolar o seu próprio utilizando as técnicas mencionadas na resposta de Norman, ou usando parsec ou analisador de uso geradores como feliz .
Outras dicas
Você representam programas usando tipos de dados algébricos mutuamente recursivas, e aos programas de análise você usa parsing combinators . Há um milhão de sabores; você vai encontrar três papéis tutorial votos no para o meu classe para segunda-feira, 23 março de 2009. Eles são
- Graham Hutton e Erik Meijer, Pérola funcional: análise Monádico em Haskell (1998)
- Graham Hutton, Funções de ordem superior para análise (1992)
- Jeroen Fokker, Analisadores funcionais (1995)
O papel Hutton e Meijer é o mais curto e mais simples, mas usa mônadas, que não são óbvias para o amador. No entanto, eles têm um muito bom gramática e analisador para expressões. Se você não Grokar monads ainda, tutorial do Fokker é o único.
Talvez você pode olhar para alguns projetos do mundo real para ver como eles fazem isso?
Menos de uma semana atrás, projeto do Language-Python era anunciou na Haskell-Cafe mailinglist . É um Python parser implementado em Haskell, usando o Happy parser gerador e Alex gerador de lexer.
E, claro, há Pugs , uma implementação de Perl 6 em Haskell (a primeira implementação de Perl 6 que está em conformidade com um subconjunto significativo da especificação Perl 6).
Eu não posso dizer pelo tom de sua pergunta se esta é a primeira vez que você está tentando escrever um compilador, ou se você escreveu compiladores antes e está procurando conselhos específicos para Haskell. Se você já é um guru do compilador, o pouco conselho que eu tenho para oferecer não vai ajudar. :)
Programação gramáticas de língua são comumente representada em BNF forma , que pode ser usado por ferramentas como Yacc ou Bison para analisar o código-fonte. Eu não sei se isso conta como uma forma Haskell-ian de fazê-lo, mas é a única maneira que eu já ouvi falar. Com algumas escavações em torno de você provavelmente pode cavar-se uma ferramenta para gerar o código Haskell de uma gramática BNF; Eu encontrei esta ferramenta que afirma ser capaz de fazer isso.
Um rápido Google Search apareceu essa gramática BNF para Haskell , e há provavelmente outros lá fora, no caso de você querer escrever um compilador para Haskell (talvez você gostaria de escrever um compilador Haskell em Haskell?) BNF gramáticas para C e Java parece ser popular.
Finalmente, se você está procurando um livro sobre projeto de compiladores, o texto clássico é " The Dragon Book ".
