Измените DCG на детерминированный

Вы можете переписать последнее правило следующим образом:

s_e --> "a", e.
s_e --> "b", e.

Теперь, наверное, имеет смысл разместить следующие разрезы:

s_e --> "a", !, e.
s_e --> "b", !, e.

Вы также можете поместить сокращения в исходную компактную форму с помощью (;)/2, но я нахожу вышеприведенное более прозрачным. Вышесказанное справедливо, если s_e не вызывается несколько раз с одним и тем же входным списком.

Но у вашей грамматики есть недостаток, e остается рекурсивным, и s_e будет вызываться несколько раз с одним и тем же входным списком. Означает, что ваша грамматика, например, будет зацикливаться на отрицательных предложениях, т. е. она не сможет их отклонить, и ваша грамматика будет зацикливаться после повтора для положительных предложений, т. е. когда ввод будет принят.

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

 e --> s_e, rest_e.
 e --> "*", rest_e.
 e --> [].

 rest_e --> s_e, rest_e.
 rest_e --> "*", rest_e.
 rest_e --> [].

И мы также можем разместить разрезы:

 e --> s_e, !, rest_e.
 e --> "*", !, rest_e.
 e --> [].

 rest_e --> s_e, !, rest_e.
 rest_e --> "*", !, rest_e.
 rest_e --> [].

Кроме того, приведенная выше грамматика немного изменена в том смысле, что несколько пустых производных e больше не входят в само e через s_e. Он также более жадный, поскольку продукция sub e всегда полностью анализируется. Так, например, предложение:

 aaa

Разбирается только как:

 a(a(a))

А не как:

 a(a)a

Or:

 aa(a)

Or:

 aaa

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

С уважением