Я бы подошел к этому, начав с определения грамматики для арифметических выражений. «Стандартный» способ определения грамматик — леворекурсивный. Поскольку в прологе выполняется рекурсивный разбор по спуску, грамматика не может быть леворекурсивной. Каждая итерация должна что-то удалять из потока токенов, чтобы не попасть в смертельную спираль бесконечной рекурсии. Вот моя нелевая рекурсивная грамматика для калькулятора с 4 ударами, такого как ваш:
expression : multiplicative_expression '+' expression
| multiplicative_expression '-' expression
| multiplicative_expression
;
multiplicative_expression : factor '*' multiplicative_expression
| factor '/' multiplicative_expression
| factor '%' multiplicative_expression
| factor
;
factor : '-' value
| '(' expression ')'
| value
;
value : number
Когда у нас есть грамматика, код пролога в значительной степени пишет сам себя. Сначала несколько фактов для работы. Нам нужен список операторов и их типов (вместе с эквивалентным оператором пролога:
operator( plus , additive , '+' ) .
operator( minus , additive , '-' ) .
operator( times , multiplicative , '*' ) .
operator( divided_by , multiplicative , '/' ) .
operator( modulo , multiplicative , 'mod' ) .
И карта слов в числа:
number_word( zero , 0 ).
number_word( one , 1 ).
...
number_word( nineteen , 19 ) .
number_word( twenty , 20 ) .
И нам нужен наш предикат интерфейса, calculate/2:
%--------------------------------------------------------------------
% we can calculate a result if Expr is a valid expression
% that consumes all the available tokens in the token stream
%---------------------------------------------------------------------
calculate(Expr,Result) :- expr( Expr , Result , [] ) .
Это вызывает «начальный символ» грамматики, expr/3. expr/3 (и другие рабочие предикаты) в значительной степени являются прямыми переформулировками грамматики с дополнительным требованием, что они должны возвращать неиспользованную часть потока входных токенов. Разбор считается успешным, если в конце дня поток токенов пуст:
expr( Xs , Result , Tail ) :- % per the grammar, an expression is
mult( Xs , LHS , [Sym|X1] ) , % - a multiplicative expression, followed by
operator( Sym , additive , Op ) , % - an infix additive operator, followed by
expr( X1 , RHS , X2 ) , % - another expression
Term =.. [Op,LHS,RHS] , % * in which case, we construct the proper prolog structure
Result is Term , % * in which case, we evaluate the result in the usual way
Tail = X2 % * and unify any remaining tokens with the Tail
. %
expr( Xs , Result , Tail ) :- % alternatively, an expression is simply
mult( Xs , Result , Tail ) % - a single multiplicative expression
. %
Рабочий предикат для мультипликативных терминов mult/3 в значительной степени идентичен прямому повторению грамматики:
mult( Xs , Result, Tail ) :- % a multiplicative expression is
factor( Xs , LHS , [Sym|X1] ) , % - a factor, followed by
operator( Sym , multiplicative , Op ) , % - an infix multiplicative operator, followed by
mult( X1 , RHS , X2 ) , % - another factor
evaluate( Op , LHS , RHS , Result ) , % * in which case, we evalute the result in the usual way
Tail = X2 % * and unify any remaining tokens with the tail
. %
mult( Xs , Result , Tail ) :- % alternatively, a multiplicative expression is simply
factor( Xs , Result , Tail ) % - a single factor
. %
Наконец, поскольку мы не возимся с операциями с более высоким приоритетом, такими как унарный минус, возведение в степень или круглые скобки, которые изменяют приоритет операций, множитель — это просто числовое слово, которое можно преобразовать в целочисленное значение:
factor( [X|Xs] , Value , Xs ) :- % a factor is simply
number_word(X,Value) % - a number value (in our case, a word that we convert to an integer)
.
и простой помощник для оценки каждого подвыражения по мере необходимости:
evaluate( Op , LHS , RHS , Result ) :- % to evaluate an infix term,
Term =.. [Op,LHS,RHS] , % - use univ to convert to the correct prolog structure, and
Result is Term % evaluate it as the result
. %
22.02.2014
?- calculator([one, plus, four, minus, three], Total). Total = two. 21.02.2014