реализовать простой C-подобный язык в Prolog?

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

the ultimate goal is to be able to execute something like this:
?- run([begin,a,:=,10,while,a,>,5,begin,write,a,a,:=,a,-,1,end,end]).

and get: 
10 
9
8
7
6 
yes

Однако я застрял на первом шаге. Это то, чего я достиг до сих пор. вне локального стека!

statement(Vars,_Vars) --> assign(Vars,_Vars).
statement(Vars,Vars2) --> statement(Vars,Vars1), statement(Vars1,Vars2). 

assign(Vars,_Vars) --> default_assign(Vars,_Vars).
assign(Vars,_Vars) --> simple_assign(Vars,_Vars).

% a //default value 0
default_assign(Vars,_Vars) --> 
    var_name(Var_Name),
    {update_vars([Var_Name,0],Vars,_Vars)}.

% a = 0
simple_assign(Vars,_Vars) --> 
    var_name(Var_Name),[=],var_value(Var_Value),
    {update_vars([Var_Name,Var_Value],Vars,_Vars)}.

% a = b
simple_assign(Vars,_Vars) --> 
    var_name(Var_Name1),[=],var_name(Var_Name2),
    {
    update_vars([Var_Name1,Var_Value],Vars,_Vars)
    }.

var_name(Var_Name) --> [Var_Name],{\+number(Var_Name2)}.    
var_value(Var_Value) -->[Var_Value],{number(Var_Value)}.

% found match, update
update_vars(Var,Vars,_Vars):-
    member(Var,Vars),
    update(Var,Vars,_Vars),
    _Vars\==[].
% no match, append
update_vars(Var,Vars,_Vars):-
    \+member(Var,Vars),
    append(Var,Vars,_Vars).

update([Name,Value],[],[]).
update([Name,Value],[[Name,Old_Value]|T1],[[Name,Value]|T2]):-
    update([Name,Value],T1,T2).
update([Name,Value],[[Name1,Value1]|T1],[[Name1,Value1]|T2]):-
    [Name,Value]\=[Name1,Value1],
    update([Name,Value],T1,T2).

append([Name,Value],[],[[Name,Value]]).
append([Name,Value],[H|T1],[H|T2]):-
    append([Name,Value],T1,T2).

Вот моя логика. Во-первых, я хочу иметь возможность использовать список (вот как я его интерпретирую - -!), поэтому структура грамматики действительно очень важна. И я также думаю об использовании списка переменных «Vars» в формах [[Name, Value], [a, 1], [b, 2]...], и обновленной версии - «_Vars». Поэтому я могу передать его другим операторам, таким как цикл while и запись.

statement(Vars,Vars2) --> statement(Vars,Vars1), statement(Vars1,Vars2).
% this seems wrong...

Но... Похоже, логика неверна с самого начала. :\ ниже приведена упрощенная версия. Я был бы очень признателен, если бы вы могли помочь мне здесь. И я очень надеюсь, что не возьму это с собой на Рождество. Т.Т.

statement --> assign.
statement --> statement, statement.

assign --> simple_assign.
assign --> default_assign.

default_assign --> 
    var_name(Var_Name).
simple_assign --> 
    var_name,[=],var_value.

var_name --> 
    [Var_Name],{\+number(Var_Name)}.    
var_value -->
    [Var_Value],{number(Var_Value)}.

declarative interpreter prolog dcg
person Hashbug    schedule 17.12.2013    source источник
comment
С-подобный, ты уверен? Это ужасно похоже на Паскаль :)   -  person    schedule 17.12.2013
comment
Это интересное упражнение, в отличие от всего, что я видел.   -  person hardmath    schedule 17.12.2013
comment
Ха-ха. Я буду обновлять этот пост.   -  person Hashbug    schedule 18.12.2013
comment
мое окончательное решение здесь: github.com/iqhash/interpreter/tree/master /c-в-прологе   -  person Hashbug    schedule 10.05.2014

Ответы (2)


arrow_upward
2
arrow_downward

Вот как бы я поступил:

  1. преобразовать исходный код в абстрактное синтаксическое дерево

    begin 
  a := 1
  while a < 5
  begin
    a := a + 1;
  end
end

    становится

    statements([
    assign(a, number(1)),
    while(greater(variable(a), number(5))), 
          statements([
              assign(a, plus(variable(a), number(1)))
                     ])
         )
           ])

  2. построить интерпретатор для него.

    Существуют различные интерпретаторы. Самый простой — ванильный интерпретатор. Вот один из них, с которого я бы начал:

    interpret(number(N), State, N, State).
interpret(assign(Variable, Statement), State, Value, NewState) :- 
    interpret(Statement, State, Value, NewState1), 
    assignVariable(Variable, Value, NewState1, NewState).
person User    schedule 17.12.2013
comment
эта структура уже неявно обрабатывается DCG, как это используется в вопросе OP. - person CapelliC; 17.12.2013
comment
Проблема, с которой я сталкиваюсь прямо сейчас, - это шаблон рекурсии, а также обновление и передача списка переменных. Но все равно спасибо. абстрактное синтаксическое дерево вроде как звонит в колокол. - person Hashbug; 18.12.2013
comment
Я думаю, вы сможете обойти рекурсию, используя repeat и привязать и развязать переменные ИЛИ используя список всех состояний с несвязанной переменной в конце, которая специализирована для каждого повтора ИЛИ используя assert и retract. - person User; 18.12.2013

arrow_upward
2
arrow_downward

Ваш код кажется подходящим, просто некоторые опечатки, приводящие к singletons, которые, вероятно, нарушают надежность вашей попытки.

В simple_assign есть + 2 синглтона (Var_Name2 и Var_Value), а + Var_Name2 — синглтон в var_name

Я предполагаю, что вы не используете IDE с правильной подсветкой синтаксиса...

редактировать синглтоны, я должен сказать, что ответ пользователя более полезен, чем мой (+1). Попытка предоставить изменяемую среду во время синтаксического анализа не работает. Вот как я тестировал несколько иную версию вашей грамматики:

test :-
    phrase(statement(S), [begin,a,:=,10,while,a,>,5,begin,write,a,a,:=,a,-,1,end,end]),
    eval(S, [], _).

% grammar

statement(Var := Expr) --> var(Var), [:=], expr(Expr).
statement(write(E)) --> [write], expr(E).
statement(while(C, S)) --> [while], condition(C), statement(S).
statement(S) --> [begin], statements(S), [end].

statements([S|R]) --> statement(S), statements(R).
statements([]) --> [].

condition(L > R) --> expr(L), [>], expr(R).

expr(L - R) --> (var(L) ; num(L)), [-], expr(R).
expr(E) --> (var(E) ; num(E)).

var(var(V)) --> [V], {atom(V)}.
num(num(N)) --> [N], {number(N)}.

% evaluation

eval([S|R], Vs, Us) :- eval(S, Vs, V1), eval(R, V1, Us).
eval([], Vs, Vs).

eval(V := E, Vs, Us) :-
    exprv(E, Vs, Ve),
    ( select(V := _, Vs, R) -> Us = [V := Ve | R] ; Us = [V := Ve | Vs] ).
eval(write(E), Vs, Vs) :- exprv(E, Vs, Ve), writeln(Ve).
eval(while(C, S), Vs, Ts) :-
    satisfied(C, Vs) -> eval(S, Vs, Us), eval(while(C, S), Us, Ts) ; Vs = Ts.

% no side effect here

exprv(L-E, Vs, Ve) :- exprv(L, Vs, Vl), exprv(E, Vs, R), Ve is Vl - R.
exprv(num(N), _, N).
exprv(var(V), Vs, Vv) :- memberchk(var(V) := Vv, Vs).

satisfied(L > R, Vs) :- exprv(L, Vs, Vl), exprv(R, Vs, Vr), Vl > Vr.
person CapelliC    schedule 17.12.2013
comment
Спасибо, парни. Я использую текстовый помощник с подключаемым модулем подсветки синтаксиса пролога. И я склонен игнорировать синглтоны. - person Hashbug; 18.12.2013
comment
@Hashbug Не следует игнорировать синглтоны, так как они могут указывать на ошибку. - person lurker; 18.12.2013