Prolog Tutorial
prolog作业 | 编译原理 – 这道题目是利用prolog进行的编程代写任务, 涵盖了编译原理等程序代做方面
2.14 DFA parser
The following program simulates a parser/acceptor for an arbitrary deterministic finite automaton (DFA). When
this and a state table program are loaded into Prolog, the parser/acceptor may be used to check inputs to the DFA
to see whether or not they are acceptable. The program traces its action using write statements; these have been
indented in order to better display the logical structure of the clauses.
parse(L) :- start(S),
trans(S,L).
trans(X,[A|B]) :-
delta(X,A,Y), /* X ---A---> Y */
write(X),
write(' '),
write([A|B]),
nl,
trans(Y,B).
trans(X,[]) :-
final(X),
write(X),
write(' '),
write([]), nl.
As an example, the following Prolog code specifies a state table for a DFA that accepts the language
(a,b)ab(a,b).
delta(0,a,1).
delta(0,b,0).
delta(1,a,1).
delta(1,b,2).
delta(2,a,2).
delta(2,b,2).
start(0).
final(2).
A state diagram for this machine is as follows:
Fig. 2.
Suppose that both the driver program and the state table program are loaded …
?- parse([b,b,a,a,b,a,b]).
0 [b,b,a,a,b,a,b]
0 [b,a,a,b,a,b]
0 [a,a,b,a,b]
1 [a,b,a,b]
1 [b,a,b]
2 [a,b]
2 [b]
2 []
yes
https://www.cpp.edu/~jrfisher/www/prolog_tutorial/2_14.html 2 / 2
?- parse([b,b,a]).
0 [b,b,a]
0 [b,a]
0 [a]
no