Грамматика с использованием фигурных скобок

Question

Я пытаюсь решить грамматику DCG в прологе и добился определенного результата, я застрял в оценке выражений с использованием таких скобок.expr( T, [’(’, 5, +, 4, ’)’, *, 7], []),

expr(Z) --> num(Z).
expr(Z) --> num(X), [+], expr(Y), {Z is X+Y}.
expr(Z) --> num(X), [-], expr(Y), {Z is X-Y}.
expr(Z) --> num(X), [*], expr(Y), {Z is X*Y}.
num(D) --> [D], {number(D)}.

eval(L, V, []) :- expr(V, L, []).

Answer 1

Это одна из самых странных вещей, которые я наблюдал в истории Пролога. А именно, неправильный синтаксис выражений присутствует уже целую вечность. Неправильный синтаксис уже найден в документации DEC10 Prolog и несоответствие видно, когда мы смотрим на правило:

 expr(Z) --> num(X), "/", expr(Y), {Z is X/Y}.
 etc..

Это делает оператор деления xfy, но это должен быть yfx. Таким образом, с вышеприведенное правило выражение 10/2/5 читается как 10 / (2/5) и приводит к 25 в результате. Но на самом деле пример следует читать как (10/2) / 5 в результате 1.

Проблема в том, что правильный синтаксис останется рекурсивным. И у DCG действительно есть проблемы с левыми рекурсивными правилами. Пролог интерпретатор просто столкнется с бесконечным циклом для левого рекурсивные правила путем многократного вызова expr / 3:

 expr(Z) --> expr(X), "/", num(Y), {Z is X/Y}
 etc..

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

 expr(Y) --> num(X), expr_rest(X,Y).

 expr_rest(X,T) --> "/", !, num(Y), {Z is X/Y}, expr_rest(Z,T).
 etc..
 expr_rest(X,X).

Приведенная выше грамматика является немного более сложной DCG. Это не больше чистый Пролог, так как он использует разрез (!). Но мы могли устранить порез, например, с помощью отталкивания, что-то вдоль следующие строки. Откат снова сложный вопрос, чтобы объяснить во введении DCG, и нам нужно ввести символ остановки в конце выражения, чтобы сделать это работает:

 etc..
 expr_rest(X,X), [C] --> [C], {not_operator(C)}.

Или мы не могли бы вдаваться в длины реза или отталкивания и жить с этим, что при возврате парсер будет делать дополнительные, в данном случае ненужно, работа. Таким образом, суть, вероятно, хотя пример не верный, он достаточно прост, чтобы объяснить DCG без необходимости много продвинутых вещей DCG.

Интересно, что синтаксис отсутствующих скобок почти не подвержен влиянию устранение левой рекурсии. Просто добавьте:

 num(X) --> "(", !, expr(X), ")".

Упс, снова порез!

С наилучшими пожеланиями

Полный код можно посмотреть здесь: http://www.jekejeke.ch/idatab/doclet/prod/en/docs/05_run/06_bench/09_programs/10_calculator/01_calculator.p.html

П.С .: Вместо устранения левой рекурсии мы могли бы также иметь работал с некоторой формой таблирования.

Answer 2

Синтаксические анализаторы, реализованные грамматиками DCG Пролога, представляют собой LL ( что-то ) (предикативные) грамматики с рекурсивным спуском. Он проходит ввод слева направо и производит самый левый вывод по ходу дела. Их легко изготовить, но грамматика должна соответствовать нескольким ограничениям:

Они не могут быть леворекурсивными. Бесконечная рекурсия может / закончится. Это означает, что по крайней мере один символ (токен) должен быть удален из входного потока перед тем, как следовать по рекурсивному пути. Рефакторинг грамматик для удаления левой рекурсии - довольно механическое упражнение, хотя и утомительное. Смотрите любую приличную книгу компиляторов о том, как это сделать.

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

ArithmeticExpression     : AdditiveExpression
                         ;

AdditiveExpression       : MultiplicativeExpression
                         | MultiplicativeExpression '+' AdditiveExpression
                         | MultiplicativeExpression '-' AdditiveExpression
                         ;

MultiplicativeExpression : ExponentialExpression
                         | ExponentialExpression '*' MultiplicativeExpression
                         | ExponentialExpression '/' MultiplicativeExpression
                         | ExponentialExpression '%' MultiplicativeExpression
                         ;

ExponentialExpression    : UnaryExpression
                         | UnaryExpression '^' ExponentialExpression
                         ;

UnaryExpression          : '-' UnaryExpression
                         | AtomicExpression
                         ;

AtomicExpression         : '(' ArithmeticExpression ')'
                         | ['0'..'9']+
                         ;

Термин на каждом уровне приоритета оператора строится из выражений следующего более высокого порядка приоритета. Так что произвольное арифметическое выражение - это всего лишь одно аддитивное выражение.

Каждое аддитивное выражение представляет собой 1 или более мультипликативных выражений, объединенных операторами сложения и вычитания.

Каждое мультипликативное выражение представляет собой 1 или более экспоненциальных выражений, соединенных операторами умножения, деления и остатка.

Каждое экспоненциальное выражение является унарным выражением с оператором степени параметра, за которым следует другое унарное выражение.

Каждое унарное выражение является либо атомарным выражением, либо унарным минусом, за которым следует другое унарное выражение.

Каждое атомарное выражение является либо произвольным арифметическим выражением, заключенным в скобки, либо целочисленным токеном без знака.

Перевод вышеприведенного в синтаксис Prolog DCG должен быть тривиальным. Как оценивать термин, представленный каждым пунктом в грамматике, должно быть самоочевидным.

Answer 3

Это просто работает. Однако это не проще, чем yacc / bison.

%?-eval('11*(7+5-2)^2*(11+8)').
eval(A) :- lex(A,L), evallist(L).

%?-evallist([11,*,'(',7,+,5,-,2,')',^,2,*,'(',11,+,8,')']).
evallist(L) :- e(R,L,[]),write(R),!.

e(N) --> t(N1), erest(N1,N).

erest(N1,N) --> [+], !, t(N2), {N3 is N1+N2}, erest(N3,N);
                [-], !, t(N2), {N3 is N1-N2}, erest(N3,N).
erest(N,N) --> [].

t(N) --> f(N1), trest(N1,N).

trest(N1,N) --> [*], !, f(N2), {N3 is N1*N2}, trest(N3,N);
                [/], !, f(N2), {N3 is N1/N2}, trest(N3,N).
trest(N,N) --> [].

f(N) --> n(N);
     n(N1), [^], f(N2), {N is N1**N2}.

n(N) --> ['('], !, e(N), [')'];
     [-], !, e(N1), {N is -N1};
     num(N). 

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

lex(A,NL) :- 
  atom_chars(A,L), lex0(_,L,NL).

lex0(S,L,NL) :-
  L=[], (number(S), NL=[S], !; NL=[]), !;
  L=[E|R], (d(E,N), (number(S), !; S=0), S1 is S*10+N, lex0(S1, R, NL), !;
     lex0(_,R,NR), (number(S), NL=[S|[E|NR]], !;
        NL=[E|NR])).

d(I,N) :- 
  char_code(I,C), C > 47, C < 58, N is C - 48.

Answer 4

Добавление этого предложения работает: num(D) --> ['('], expr(D), [')'].