Написание официального парсера языка с Lisp

Question

Моя компания разрабатывает новый язык сценариев для конкретного домена; Я должен реализовать парсер, который переводит наш новый язык программирования на общий язык сценариев, чтобы иметь возможность его внедрять.

Обычный способ я делаю это с помощью Bison и Flex инструментов, которые генерируют код переводчика C/C++.

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

Не использовался ли для этого Lisp? Каков обычный способ написать парсер с Lisp?

Примечание: для меня любая реализация Lisp, которая могла бы помочь, в порядке, у меня нет никаких предпочтений.

Answer 1

Чтобы покрыть Racket части его:

Людей часто пишут парсер и есть много способов сделать это:

• Написать рекурсивный спуск парсер вручную.
• Используйте библиотеку parser-tools в Racket, которая представляет собой стиль lex/yacc.
• Использовать Ragg, генератор генератора AST, позволяющий вам писать BNF.
• Использовать Parsack, библиотеку комбинаторов синонимов, аналогичную Parsec Haskell.
• Возможно, у меня есть, по крайней мере, полдюжины других вариантов (например, я знаю, что для Racket существует хотя бы один стиль стиля PEG).

Answer 2

Ну, «обычный» способ сделать это в Common Lisp - это ... сделать это в Lisp.

Многие языки, поддерживающие домен (и Lisp в значительной степени известны для этой цели!), Просто записываются как расширения для самого Lisp, используя средство макроса. Потенциал: тривиально писать DSL. Недостатком является то, что они часто имеют тенденцию «выглядеть как» lisp.

Некоторые примеры DSL в стандарте Common Lisp включают собственный дополнительный язык макроса LOOP и подязык спецификаторов FORMAT.

Поскольку обозначение s-выражения Лиспа номинально является письменной формой абстрактного дерева синтаксиса, это один из способов избежать использования большого количества ваших лексеров или парсеров; вы можете просто использовать READ.

Что все сказано, вы можете использовать некоторые общие пакеты, которые могут быть найдены в GRAYLEX или CL-LEXER или так далее; поиск парсеров для другого языка с похожим синтаксисом для вас может помочь. В Quicklisp я вижу:

CL-USER> (ql:system-apropos "parse") 
#<SYSTEM cl-arff-parser/cl-arff-parser-20130421-git/quicklisp 2013-08-13>                                                 
#<SYSTEM cl-date-time-parser/cl-date-time-parser-20130813-git/quicklisp 2013-08-13>                                               
#<SYSTEM cl-html-parse/cl-html-parse-20130813-git/quicklisp 2013-08-13>                                                  
#<SYSTEM cl-html5-parser/cl-html5-parser-20130615-git/quicklisp 2013-08-13>                                                 
#<SYSTEM cl-html5-parser-tests/cl-html5-parser-20130615-git/quicklisp 2013-08-13>                                               
#<SYSTEM cl-pdf-parser/cl-pdf-20130420-git/quicklisp 2013-08-13>                                                    
#<SYSTEM cli-parser/cl-cli-parser-20120305-cvs/quicklisp 2013-08-13>                                                   
#<SYSTEM clpython.parser/clpython-20130615-git/quicklisp 2013-08-13>                                                   
#<SYSTEM com.gigamonkeys.parser/monkeylib-parser-20120208-git/quicklisp 2013-08-13>                                               
#<SYSTEM com.informatimago.common-lisp.html-parser/com.informatimago-20130813-git/quicklisp 2013-08-13>                                          
#<SYSTEM com.informatimago.common-lisp.parser/com.informatimago-20130813-git/quicklisp 2013-08-13>                                           
#<SYSTEM csv-parser/csv-parser-20111001-git/quicklisp 2013-08-13>                                                   
#<SYSTEM fucc-parser/fucc_0.2.1/quicklisp 2013-08-13>                                                      
#<SYSTEM http-parse/http-parse-20130615-git/quicklisp 2013-08-13>                                                   
#<SYSTEM http-parse-test/http-parse-20130615-git/quicklisp 2013-08-13>                                                  
#<SYSTEM js-parser/js-parser-20120909-git/quicklisp 2013-08-13>                                                    
#<SYSTEM parse-declarations-1.0/parse-declarations-20101006-darcs/quicklisp 2013-08-13>                                              
#<SYSTEM parse-float/parse-float-20121125-git/quicklisp 2013-08-13>                                                   
#<SYSTEM parse-float-tests/parse-float-20121125-git/quicklisp 2013-08-13>                                                 
#<SYSTEM parse-js/parse-js-20120305-git/quicklisp 2013-08-13>                                                    
#<SYSTEM parse-number/parse-number-1.3/quicklisp 2013-08-13>                                                     
#<SYSTEM parse-number-range/parse-number-range-1.0/quicklisp 2013-08-13>                                                  
#<SYSTEM parse-number-tests/parse-number-1.3/quicklisp 2013-08-13>                                                   
#<SYSTEM parse-rgb/cl-tcod-20130615-hg/quicklisp 2013-08-13>                                                     
#<SYSTEM parseltongue/parseltongue-20130312-git/quicklisp 2013-08-13>                                                  
#<SYSTEM parser-combinators/cl-parser-combinators-20121125-git/quicklisp 2013-08-13>                                               
#<SYSTEM parser-combinators-cl-ppcre/cl-parser-combinators-20121125-git/quicklisp 2013-08-13>                                            
#<SYSTEM parser-combinators-tests/cl-parser-combinators-20121125-git/quicklisp 2013-08-13>                                             
#<SYSTEM py-configparser/py-configparser-20101006-svn/quicklisp 2013-08-13>         

Answer 3

Существует два способа разбора неязыковых языков в общих словах.

1) Используйте считывающие устройства. это классический способ: алгоритм чтения Lisp - это простой рекурсивный-достойный парсер уже, который поддерживает отправку на основе символов.Vacietis делает это here

2) Используйте разборную библиотеку. Я могу порекомендовать esrap как полезную утилиту для парсинга packrat и самодовольный, чтобы сделать монадический синтаксический анализ. Оба доступны в скором времени.