Parsing the prologue ends from the stack
I have this code
s(W) :- append(W1,W2,W), np(W1), vp(W2).
vp(W) :- append(W1,W2,W), v(W1), np(W2).
np(W) :-
( append(W1,W2,W), pn(W1), ph(W2)
; append(W1,W2,W), det(W1), n(W2)
).
pn([hans]).
ph([]).
v([beobachtet]).
n([mann]).
n([fernrohr]).
p([mit]).
det([den]).
det([dem]).
when i do something like np(X).
vp(X).
or pp(X)
get one possible parsing and then an error from the stack. when I quit s(X).
, I don't even understand. I know this is because there is an infinite loop, but I just cannot tell at what point it loops. I assumed this might be due to using the same names for all of my variables, but then I changed them to separate ones and it didn't change anything.
anyone got a hint?
early!
source to share
Reason for missing stack
Look at the following line from your code:
vp(W) :- append(W1,W2,W), v(W1), np(W2).
Running append(W1, W2, W)
separately gives the following:
?- append(W1, W2, W). W1 = [], W2 = W ; W1 = [_G1108], W = [_G1108|W2] ; W1 = [_G1108, _G1114], W = [_G1108, _G1114|W2] ; W1 = [_G1108, _G1114, _G1120], W = [_G1108, _G1114, _G1120|W2] .
As you can see, W1
this is a list of increasing length. Only for length 1 does it give solution (c v(W1)
). After this first instance W1
gets longer and longer and longer and ... but v(W1)
won't succeed for longer length lists.
DCG grammar
In Prolog, you can use DCG notation to create grammar. Your grammar will look like this:
s --> np, vp.
np --> pn.
np --> det, n.
vp --> v, np.
det --> [den].
det --> [dem].
n --> [mann].
n --> [fernrohr].
pn --> [hans].
v --> [beobachtet].
Usage example
?- phrase(s, S). S = [hans, beobachtet, hans] ; S = [hans, beobachtet, den, mann] ; S = [hans, beobachtet, den, fernrohr] ; S = [hans, beobachtet, dem, mann] ; S = [hans, beobachtet, dem, fernrohr] ; S = [den, mann, beobachtet, hans] ; S = [den, mann, beobachtet, den, mann] ; S = [den, mann, beobachtet, den, fernrohr] ; S = [den, mann, beobachtet, dem, mann] ; S = [den, mann, beobachtet, dem, fernrohr] ; S = [den, fernrohr, beobachtet, hans] ; S = [den, fernrohr, beobachtet, den, mann] ; S = [den, fernrohr, beobachtet, den, fernrohr] ; S = [den, fernrohr, beobachtet, dem, mann] ; S = [den, fernrohr, beobachtet, dem, fernrohr] ; S = [dem, mann, beobachtet, hans] ; S = [dem, mann, beobachtet, den, mann] ; S = [dem, mann, beobachtet, den, fernrohr] ; S = [dem, mann, beobachtet, dem, mann] ; S = [dem, mann, beobachtet, dem, fernrohr] ; S = [dem, fernrohr, beobachtet, hans] ; S = [dem, fernrohr, beobachtet, den, mann] ; S = [dem, fernrohr, beobachtet, den, fernrohr] ; S = [dem, fernrohr, beobachtet, dem, mann] ; S = [dem, fernrohr, beobachtet, dem, fernrohr].
source to share
Short duration is often difficult to understand in Prolog. Let's take a query as an example pn(X)
. Obviously what should be:
W = [hans] ;
W = [den, mann] ;
W = [den, fernrohr] ;
W = [dem, mann] ;
W = [dem, fernrohr].
as solutions (whatever [den, fernrohr]
is not German). But Prolog only finds one and then a loop. In a way, you can consider yourself happy because you discovered this problem early on. But imagine a situation where there are many answers before the loop. So you get the impression that everything is fine, but it is not.
To find these problems a little faster, try it pn(X), false
. While this request will never be true, it will complete exactly the same as pn(X)
, but it will not cause all these annoying decisions.
You can go even further by inserting it into your program, the resulting program is called a rejection slice. With a clean, monotonous program like yours, the following works: false
If the failure slice does not end (for a specific request) , then the original program does not end for that request.
Fault-tolerant slices are usually much shorter, so they are faster to read and understand. Whennp(X)
? - np (X), false . np (W): - (append (W1, W2, W), false ,pn (W1), ph (W2); false ,append (W1, W2, W), det (W1), n (W2)).
Thus, you no longer need to spend time searching for pn/1
, ph/1
, det/1
or n/1
to cycles. Above one failure-slice is already done without interruption. Thus, until it is fixed, it is pointless to look at the rest of the program.
The direct fix would be append/3
to end. This works for np/1
. But it doesn't work for recursive nonterminals with fixed length list.
Before the advent of Prolog, people really considered these encodings. They were puzzled by this discrepancy: both grammars and predicate logic are declarative formalism. But while many grammars can be analyzed very efficiently, proving that a sentence is described by the grammar seems to imply a giant search space. Where is this efficient method to use logic here?
The answer was concrete coding to allow parsing of simple grammars as efficiently as the handwritten parsers that spawned Prolog. By this date, this encoding is used in Prolog to implement Grammars with certain parameters. See @WouterBeeks answer for how it's done.
source to share