Пытаемся разобраться в парсере DCG в прологе

Недавно я играл с DCG в Прологе, но столкнулся с некоторыми проблемами, касающимися того, как именно это работает. Например, у меня есть такая маленькая грамматика:

<atom> :: <letter> <atom_part> | <letter>
<atom_part> :: <letter> | <digit> | <letter> <atom_part> | <digit> <atom_part>
<letter>:: 'a' | 'b' ... |'Z'
<digit> :: '0' |...|'9'

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

letter("a") --> "a".
number(X) --> number(X).
...
%etc
programme(I) --> atomm(I).
atomm(C) --> letter(Ch).
atomm(C) --> numb(Ch).
atomm((E)) --> atomm_part(E).
atomm_part(E1,E2) --> atomm(E1),!,atomm(E2).

Здесь я думаю ясно, что последние 2 строчки ошибочны. Это действительно потому, что я не уверен, как сделать «рекурсивный вызов», поэтому синтаксический анализатор снова проверяет, является ли следующий символ в строке числом или строкой. Как я могу это исправить? Заранее спасибо!

кстати, я использую swi-prolog


prolog dcg
person user1906589    schedule 06.01.2013    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Ваша грамматика кажется более сложной, чем необходимо, и вы можете упростить ее, используя «эпсилон» (пустая продукция, в DCG - []). Кроме того, вы должны придерживаться «программы» в большей степени в соответствии со спецификацией.

atom --> letter, atom_part | letter.
atom_part --> letter | digit | letter, atom_part | digit, atom_part.
letter --> "a" | "b" | /* omissis... */ "Z".
digit --> [D], {memberchk(D, "0123456789")}.

Вы можете видеть, насколько он похож на исходную спецификацию. С этим

?- phrase(atom, "a").
true ;
false.

?- phrase(atom, "3a").
false.

?- phrase(atom, "a3").
true ;
false.

letter и digit показывают разные способы сопоставления отдельных символов. digit проще, если вам нужно захватить значения из ввода, как это сделано в вашем коде. Но поскольку перечисление 26 * 2 символов подвержено ошибкам, рассмотрите возможность использования code_type / 2

atom(A) --> letter(L), atom_part(P), {A=[L|P]} | letter(L), {A=[L]}.
atom_part(P) --> letter(L), {P=[L]} | digit(D), {P=[D]} | letter(L), atom_part(A), {P=[L|A]} | digit(D), atom_part(A), {P=[D|A]}.
letter(L) --> [L], {code_type(L, alpha)}.
digit(D) --> [D], {memberchk(D, "0123456789")}.

Также учтите, что обычно альтернативы в Прологе кодируются таким образом

atom([L|P]) --> letter(L), atom_part(P).
atom([L]) --> letter(L).

Более простая форма позволяет перемещать «конструкцию данных» в шаблоне головы.

person CapelliC    schedule 06.01.2013