Как построить абстрактные синтаксические деревья из спецификации грамматики в Haskell?

Я никогда не использовал bnfc-meta (предложено @phg), но настоятельно рекомендую вам изучить BNFC (на взлома: http://hackage.haskell.org/package/BNFC). Основной подход заключается в том, что вы пишете свою грамматику в аннотированном стиле BNF, и он автоматически генерирует AST, синтаксический анализатор и симпатичный принтер для грамматики.

Насколько подходит BNFC, зависит от сложности вашей грамматики. Если это не зависит от контекста, вам, вероятно, будет трудно добиться какого-либо прогресса (я добился некоторого успеха, взламывая контекстно-зависимые расширения, но этот код, вероятно, уже немного сгнил). Другим недостатком является то, что ваш AST будет напрямую отражать спецификацию грамматики. Но поскольку у вас уже есть спецификация BNF, добавление необходимых аннотаций для BNFC должно быть довольно простым, так что это, вероятно, самый быстрый способ получить пригодный для использования AST. Даже если вы решите пойти другим путем, вы можете взять сгенерированные типы данных в качестве отправной точки для рукописной версии.

Что ж, в Haskell есть 2 основных способа разбора чего-либо: комбинаторы разбора или генератор парсеров. Поскольку у вас уже есть BNF, я бы предложил последнее.

Хороший вариант — alex. Парсер GHC IIRC написан с использованием этого, так что вы будете в хорошей компании.

Далее у вас будет большой стек деклараций данных для анализа:

data JavaClass = {
    className :: Name,
    interfaces :: [Name],
    contents :: [ClassContents],
    ...
 }
  data ClassContents = M Method
                     | F Field
                     | IC InnerClass

и для выражений и всего, что вам нужно. Наконец, вы объедините их во что-то вроде

data TopLevel = JC JavaClass
              | WhateverOtherForms
              | YouWillParse

Как только вы это сделаете, весь AST будет представлен как один TopLevel или их список в зависимости от того, сколько классов/файлов вы анализируете.

Чтобы продолжить отсюда, зависит от того, что вы хотите сделать. Существует ряд библиотек, таких как syb (выбросьте свой шаблон), которые позволяют вам писать очень краткие обходы дерева и модификации. lens тоже вариант. Как минимум выезд Data.Traversable и Data.Foldable.

Чтобы изменить дерево, вы можете сделать что-то простое, например

ignoreInnerClasses :: JavaClass -> JavaClass
ignoreInnerContents c = c{contents = filter isClass $ contents c}
 --                           ^^^ that is called a record update
    where isClass (IC _) = True
          isClass _      = False

и тогда вы могли бы использовать что-то вроде syb для записи

 everywhere (mkT ignoreInnerClass) toplevel

который будет проходить все и применять ignoreInnerClass ко всем JavaClasses. Это можно сделать и в lens, и во многих других библиотеках, но syb очень легко читается.

Алекс + Хэппи.

Существует множество подходов к изменению/исследованию проанализированных терминов (AST). Ключевое слово для поиска - это программирование с общим типом данных. Но будьте осторожны: это сложная тема...

http://people.cs.uu.nl/andres/Rec/MutualRec.pdf

http://www.cs.uu.nl/wiki/GenericProgramming/Multirec

Он имеет общую реализацию молнии, доступную здесь:

http://hackage.haskell.org/packages/archive/zipper/0.3/doc/html/Generics-MultiRec-Zipper.html

Также проверьте https://github.com/pascalh/Astview.

Вы также можете ознакомиться с серией компиляторов Haskell, которая хороша как введение в использование alex и с удовольствием анализирует подмножество Java: http://bjbell.wordpress.com/haskell-compiler-series/.

Поскольку ваша грамматика может быть выражена в BNF, она относится к классу грамматик, которые эффективно анализируются синтаксическим анализатором сдвига-уменьшения (грамматики LALR). Такие эффективные синтаксические анализаторы могут быть сгенерированы генератором синтаксических анализаторов yacc/bison (C, C++) или его эквивалентом Haskell "Happy".

Вот почему я бы использовал «Happy» в вашем случае. Он принимает правила грамматики в форме БНФ и напрямую генерирует парсер. Результирующий синтаксический анализатор примет язык, описанный вашими грамматическими правилами, и создаст AST (абстрактное синтаксическое дерево). Руководство пользователя Happy очень удобно и поможет вам быстро приступить к работе: http://www.haskell.org/happy/doc/html/

Чтобы преобразовать полученный AST, хорошей идеей будет универсальное программирование. Вот классическое объяснение того, как сделать это в Haskell на практике с нуля: http://research.microsoft.com/en-us/um/people/simonpj/papers/hmap/

Я использовал именно это, чтобы создать компилятор для небольшого предметно-ориентированного языка, и это было простое и лаконичное решение.