Пролог-переводчик

Question

Я уже промок от функционального программирования;Я знаком (хотя и не опытен) в Схеме Haskell и PLT.Я использовал схему PLT для создания небольших интерпретаторов для игрушечных языков (ссылаясь на PLAI) - я лучше владею императивными языками.

Может ли кто-нибудь направить меня к ресурсам, которые я мог бы использовать для создания небольшого интерпретатора игрушкикакой язык я выбрал с Прологом?

Answer 1

Я в основном использую swi-prolog, поэтому большая часть того, что я говорю, будет связана с swi-prolog.Однако другие реализации пролога могут иметь похожие предикаты / библиотеки (возможно, с немного другим именем), поэтому вы можете искать их руководства и находить их.Кроме того, я пишу компилятор, а не интерпретатор, в прологе, поэтому, возможно, некоторые части не так связаны с интерпретатором.

Сайт документации SWI-Prolog действительно хорош для поиска вещей: используйте окно поиска, чтобы найти любой предикат, или выполните обычный поиск.Существует множество библиотек, но вы, возможно, захотите реализовать некоторые вещи самостоятельно, чтобы получить опыт.Вы могли бы в итоге заново изобрести колесо, но это было бы полезно.

В книге "Искусство Пролога" (Стерлинг, Шапиро) есть глава, посвященная созданию компилятора в прологе (и это хорошая книга для пролога).

Возможно, есть некоторыеинструменты, эквивалентные лексам / бизонам для пролога;я никогда не искал.
Imho, лексер довольно прост в простом прологе;естественно, это будет в значительной степени основано на сопоставлении с образцом.

Для синтаксического анализатора я предлагаю использовать DCG: определенные грамматики предложения: swi-prolog doc , Google для более подробной информации.
Проблема в том, что вам придется анализировать весь файл (или, по крайней мере, я не нашел способ сделать это иначе).Кстати, лексер также можно сделать с помощью DCG, но я не думаю, что это действительно лучше.

Если вы решите использовать промежуточный код, абстрактное синтаксическое дерево легко создать из синтаксического анализатора (вы можете оценить многои во время синтаксического анализа).
О семантических проверках: в моем компиляторе для игрушечного языка я выполняю большинство семантических проверок (связанных с областью действия, вызовами функций) во время синтаксического анализа, а остальное - на отдельном шаге.Это немного грязно

другие полезные вещи: проверка assert / 1, глобальные переменные, мета-предикаты (maplist / [2-6]).
не чистый пролог, и вы можете сделатьваш код слишком императивен, злоупотребляя ими (и тогда у вас могут возникнуть некоторые действительно неприятные побочные эффекты)

Для таблицы символов (если вам это нужно) вы можете просто использовать assert / 1 для добавления предикатов: swi-prolog используетдинамические хеш-таблицы для динамических предикатов.предупреждение: динамические предикаты медленнее статических, поэтому, когда вы заполняете таблицу и не собираетесь вносить какие-либо изменения, используйте compile_predicates / 1, чтобы сделать их статичными.Например, когда я закончу синтаксический анализ, мой ST будет готов, поэтому я скомпилирую его.Другим решением для ST является использование списков ассоциаций .они реализованы с помощью деревьев AVL, поэтому стоимость O (log (N)).

Answer 2

Маркус Триска ( здесь его домашняя страница) показывает, что вам могут быть интересны несколько вещей: например, игрушка LISP или несколько жестов для мета-интерпретаторов .

Answer 3

Я написал простой интерпретатор для функционального языка программирования на Прологе.Полная реализация показана здесь с примером ее использования:

:- initialization(main).
:- set_prolog_flag('double_quotes','chars').

main :- functional_syntax((
            writeln(factorial(3)+factorial(4)),
            Concatenated_string = "hello" + " " + "world",
            writeln(Concatenated_string),
            writeln(length(Concatenated_string)),
            writeln(type(Concatenated_string)),
            writeln(nth0(0,Concatenated_string)),
            writeln(msort([1,3,2,15,-1]))
        ),true).

factorial(N,Output) :-
    functional_syntax((
        (N=1 -> Output = 1);
        Output = N*factorial(N-1)
    )).

type(A,B) :-
    functional_syntax(A,A1),
    (number(A),B='number';
    is_list(A),B='list';
    atom(A),B='atom').

functional_syntax(A) :- functional_syntax(A,true).
functional_syntax(A,A) :- number(A);var(A);atom(A).
functional_syntax(not(X),Output) :-
    functional_syntax((X = false),Output).
functional_syntax(writeln(A),true) :-
    functional_syntax(A,A1),writeln(A1).
functional_syntax(A+B,C) :-
    functional_syntax([A,B],[A1,B1]),
    ((number(A1),number(B1)) ->
        C is A1+B1;
    (is_list(A1),is_list(B1)) ->
        append(A1,B1,C)).
functional_syntax(A-B,C) :-
    functional_syntax([A,B],[A1,B1]),C is A1-B1.
functional_syntax(A*B,C) :-
    functional_syntax([A,B],[A1,B1]),C is A1*B1.
functional_syntax(A/B,C) :-
    functional_syntax([A,B],[A1,B1]),C is A1/B1.
functional_syntax(A=B,Result) :-
    functional_syntax(B,B1),
    (A=B1,Result=true;dif(A,B1),Result=false).
functional_syntax(A->B,Result) :-
    (functional_syntax(A,A1),A1=true) -> (functional_syntax(B,B1),Result=true,B1=true);
    Result=false.
functional_syntax([],[]).
functional_syntax([A|B],[A1|B1]) :-
    functional_syntax(A,A1),functional_syntax(B,B1).
functional_syntax((A,B),Result) :-
    functional_syntax([A,B],[A1,B1]),
    (A1,B1,Result=true;([A1,B1]=[true,false];[A1,B1]=[false,true]),Result=false).
functional_syntax((A;B),Result) :-
    (functional_syntax(A,A1),call(A1);
    functional_syntax(B,B1),call(B1)) -> (Result = true);
    (functional_syntax(A,A1),A1=false,Result=false).
functional_syntax(Input,Output1) :-
    not(number(Input)),
    Input =.. [Name|Params],
    \+member(Name,['=','->',not,'[|]',',',';',+,-,*,/]),
    length(Params,Params_length),
    Params_length > 0,
    functional_syntax(Params,Params1),
    append([Name|Params1],[Output1],Input0),
    Input1 =.. Input0,
    call(Input1).

Аналогично, можно написать интерпретаторы для императивных языков программирования в Прологе.