% Linguistics 484 -- Example: PDA_E Prolog % % Push-Down Automata: Embedded Clause Processing. % % The purpose of this example is to illustrate how a Push-Down Automaton % employs its store during the course of its accepting sentences % with embedded constituents, including the left- and right-embedded % constituents of left-branching and right-branching sentences, as well % as centre-embedded constituents. % % The predicates comprising this program cause the Prolog interpreter % to emulate the operations of a Push-Down Automaton that has been % adapted to display output consisting of the contents of its store, % together with its state and the contents of its input tape, during % the course of its accepting an input string. % % To remove the need to type the demonstration sentences, clauses % of a demo/1 predicate have been included with this program. % The argument of each demo/1 clause is a number, and the body % of each of these clauses is an s/1 goal, the argument of which is % a list consisting of one of the demonstration sentences. % Hence, typing a demo/1 query with an appropriate argument will % cause the s/1 goal in its body to be proved, and consequently, cause % the Push-Down Automaton which this program emulates to undertake % the process of accepting the corresponding demonstration sentence. % For example, the first three clauses of the demo/1 predicate % appear as follows: % % demo(1) :- s( [the_cat, ran] ). % demo(2) :- s( [the_cat, the_dog, chased, ran] ). % demo(3) :- s( [the_cat, the_dog, the_girl, owned, chased, ran] ). % % Thus, typing the following query, after this program has been % consulted: % % demo(2). % % will cause the program to display the following output: % % <[#], $, [the_cat,the_dog,chased,ran]> % => <[#], np, [the_dog,chased,ran]> % => <[#,np], np, [chased,ran]> % => <[#,np,np], vp, [ran]> % => <[#,np], s, [ran]> % => <[#], np, [ran]> % => <[#,np], vp, []> % => <[#], s, []> % % showing the contents of its push-down store as the % machine processes the demonstration sentence % % 'the_cat the_dog chased ran.' % % Note that determiners have been attached to nouns, in the case % of the English sentences (and the case-marking particles in the % Japanese sentences) in order to simplify the recognition process. % It is thus easier to see the effect on the push-down store % of the machine's processing embedded constituents of the % demonstration sentences. % % The Japanese sentences have been adapted from examples in Kuno (1973) % _The Structure of the Japanese Language_ that were cited to illustrate % the left-branching structure of Japanese sentences, in contrast to the % predominantly right-branching structure of English sentences. %s/1 s(Tape) : The list of data tokens, Tape, comprises a % sentence if it is accepted by a PDA the control % unit of which is emulated by the predicate % control/4. % s(Tape) :- control(['#'], '$', Tape, [Stack, State, Data | Configs]), nl, write( ' ' ), show_config( Stack, State, Data ), list_configs(Configs). %control/4 control(Stack, State, Tape, Configs) : % % State is the label of the current state of the automaton, % and in this state, Tape is a list of the as yet unread % data tokens (words). Stack is a list of the symbols % currently in the push-down store. Configs is the sequence % of configurations of the machine, together with the % contents of the input tape, during the course of a % recognition. % Final state/Empty store conditions. control(['#'], s, [], [['#'], s, []] ). % Initial Finite-State Transition: A --> a (Eg., NP --> the_cat) control(['#'], '$', [Token | Tape], [['#'], '$', [Token | Tape] | Configs]) :- rule(Next, Token), control(['#'], Next, Tape, Configs). % Read/Push Transition: A --> a (Eg., VP --> ran) control(Stack, State, [Token | Tape], [Stack, State, [Token | Tape] | Configs]) :- rule(Next, Token), control([State | Stack], Next, Tape, Configs). % Lambda/Pop Transition: A --> B C (Eg., S --> NP VP) control([Top | Stack], State, Tape, [[Top | Stack], State, Tape | Configs]) :- rule(Next, Top, State), control(Stack, Next, Tape, Configs). %list_configs/1 % % list_configs( C ) : C is a list of the configurations visited by the % machine during a recognition. list_configs( [] ). list_configs( [Stack, State, Data | Configs] ) :- write( '=> ' ), show_config( Stack, State, Data ), list_configs( Configs ) . %show_config/3 % % show_config( Stack, State, Data ) : Display the contents of the % push-down (Stack), the contents % of the input tape (Date), and the current state (State) % of the machine at an ordered triple. Note that, the % order of the symbols in the push-down store is % reversed by the reverse/2, reverse/3 predicates. % The store is emulated by a Prolog list, which means % symbols are added, or pushed onto the left-end hand, % which therefore acts as the top of the store. % For the display produced here it is required that the % top of the store be the right-hand end of the list. show_config( Stack, State, Data ) :- reverse( Stack, Store ), write( '<' ), write( Store ), write( ', ' ), write( State ), write( ', ' ), write( Data ), write( '>' ), nl. % reverse/2, reverse/3 % Predicates to reverse the order of the elements of a list. reverse(AB, BA) :- reverse(AB, BA, []). reverse([], U, U). reverse([H | AB], U, W) :- reverse(AB, U, [H | W]). %rule/2 % % rule(Qj, Ti) : Qj is the label of the state to which the PDA moves % in a read/push transition, during which the data % token Ti is read, corresponding to the rewriting % rules of the form: Qj --> Ti . rule(np, john_ga). rule(np, neko_ga). rule(np, nezumi_ga). rule(np, tiizu_wa). rule(vp, katte-iru). rule(vp, korosita). rule(vp, tabeta). rule(vp, kusatte-ita). rule(relp, that). rule(be, was). rule(adj, rotten). rule(np, a_rat). rule(np, a_cat). rule(np, john). rule(np, cheese). rule(v, keeps). rule(v, killed). rule(v, ate). rule(np, the_cat). rule(np, the_dog). rule(np, the_girl). rule(vp, ran). rule(vp, chased). rule(vp, owned). %rule/3 % % rule(Qj, Zi, Qi) : Qj is the label of the state to which the PDA % moves from the state labelled Qi in a lambda/pop % transition, during which the symbol Zi is popped % from its store, corresponding to the rewriting % rules of the form: Qj --> Zi Qi . rule(s, np, vp). rule(s, relp, vp). rule(np, s, np). %left-branching subordinate s rule(np, np, s ). %right-branching subordinate s rule(vp, v, np). rule(vp, be, adj). %demo/1 % % demo(N) : N is an integer identifying the particular demonstration to % be tested. (This predicate is added so that the demonstration % sentences need not be typed to test them.) demo(1) :- s( [the_cat, ran] ). demo(2) :- s( [the_cat, the_dog, chased, ran] ). demo(3) :- s( [the_cat, the_dog, the_girl, owned, chased, ran] ). demo(4) :- s( [a_cat, killed, a_rat, that, ate, cheese, that, was, rotten] ). demo(5) :- s( [neko_ga, korosita, nezumi_ga, tabeta, tiizu_wa, kusatte-ita] ). demo(6) :- s( [john, keeps, a_cat, that, killed, a_rat, that, ate, cheese, that, was, rotten] ). demo(7) :- s( [john_ga, katte-iru, neko_ga, korosita, nezumi_ga, tabeta, tiizu_wa, kusatte-ita] ).