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

Я работаю над проектом, который включает в себя оптимизацию определенных конструкций в очень небольшом подмножестве Java, формализованном в BNF.

Если бы я делал это на Java, я бы использовал комбинацию JTB и JavaCC, которая создает AST. Затем посетители используются для манипулирования деревом. Но, учитывая обширные библиотеки для анализа в Haskell (parsec, happy, alex и т. Д.), Я немного запутался в выборе подходящей библиотеки.

Итак, проще говоря, когда в BNF указан язык, какая библиотека предлагает самые простые средства для создания AST? И как лучше всего модифицировать это дерево в идиоматическом Haskell?

Источник

5 ответов

Решение

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

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

Источник

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

Хороший - Алекс. Парсер 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" в вашем случае. Он принимает грамматические правила в форме BNF и генерирует парсер из него напрямую. Результирующий синтаксический анализатор примет язык, который описан вашими правилами грамматики, и создаст AST (абстрактное синтаксическое дерево). Счастливое руководство пользователя довольно приятно и поможет вам быстро начать работу: http://www.haskell.org/happy/doc/html/

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

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

Источник
Другие вопросы по тегам