Изменить DCG, чтобы быть детерминированным - PullRequest
Новая
       14

Изменить DCG, чтобы быть детерминированным

0 голосов
/ 01 апреля 2012

как изменить эту грамматику, чтобы она была детерминированной 

e --> [].
e --> "*".
e --> s_e.
e --> e, s_e.
s_e --> ("a",e);("b",e).

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

1 Ответ

2 голосов
/ 01 апреля 2012

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

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 --> [].

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

 aaa

анализируется только как: 

 a(a(a))

А не как: 

 a(a)a

Или: 

 aa(a)

Или: 

 aaa

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

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

...