% Linguistics 484 -- Example: PDA Prolog % % Push-Down Automaton. % % The predicates comprising this program cause the Prolog interpreter % to emulate the operations of a Push-Down Automaton that accepts % sentences generated by a Chomsky Normal Form context-free grammar. % % A Push-Down Automaton is a finite-state machine equipped with a % memory device. Thus it can be described as consisting of the % following four components: % % - Contol Unit, % - Read Unit, % - Input Tape, and % - Memory Unit. % % The nature and operations of the Control, Read, and Tape devices % are the same as those of the finite-state machine, except that % the transitions executed by the control unit of a push-down % automaton involve operations to store symbols in, and retrieve % symbols from its memory unit. The memory unit of a push-down % automaton operates as a "stack" or "push-down store," which leads % to the name for this variety of abstract machine. % % The stack or push-down store of a push-down automaton can be % treated as a list. Symbols can be added to or removed from this % list, however, only from one end. This end of the list is called % the "top" of the store. When a symbol is added to the store, it % is said to be "pushed" onto the top of the store. When a symbol % is removed, it is said to be "popped" from the store. A symbol % within the store can popped only after all the symbols above it % have been popped. Thus, the last symbol pushed onto the store is % always the first symbol to be popped from it. Hence, a push-down % store is sometimes called a "last in/first out" memory. % % The symbols stored in the push-down store of a push-down % automaton are the labels of its states. Thus, the machine, in % effect, uses its store to record the labels of certain of the % states it has experienced in the course of its processing an % input string. Because the store is a last in/first out memory, % the labels of the states experienced earlier in the processing % of the string are beneath those of the more recently experienced % states which are closer to the top of the store. % % If the automaton has been devised to accept the sentences % generated by a given grammar G, then the vocabulary of input % symbols that make up strings processed by the machine is just % the vocabulary of terminal symbols of G. The state label % vocabulary of the automaton then includes the non-terminal % vocabulary of the grammar G. Consequently, the vocabulary of % store symbols of a push-down automaton also includes non-terminal % vocabulary of the grammar G. % % Although the store of a push-down automaton has a top, it is not % considered to have a bottom. A push-down store can, in principle, % record infinitely many items. The end of the list of stored items, % however, is usually marked with a special symbol called the % "empty store" symbol because when the store is empty, this special % symbol is at the top. Thus, the empty store symbol is added to % the nonterminal vocabulary of the equivalent grammar to make up % the store vocabulary of a push-down automaton. % % In this emulation of a push-down automaton, the '#' sign is used % as the empty store symbol. Another special symbol, the '$' sign % in this example, is used to label the initial state of the % automaton. Thus, unlike the finite-state automaton, the initial % state is not labelled with the starting symbol 'S' of the grammar % G to which the machine is equivalent. Rather, in this emulation, % the starting symbol 'S' of G labels an accepting state of the % machine. Note that, while a push-down automaton may have a number % of accepting states, the machin emulated in this example has only % the one accepting state. % % The machine emulated by this program executes three types of % transition in the process of accepting an input string. The % names usually used to identify each type of transition, the % operations performed during the transition, and the rules of the % grammar to which the automaton is equivalent are as follows: % % - Initial Finite-State Transition during which the machine shifts % out of its initial state 's' to a new state while reading the % first word of the input string, but without changing the % contents of store so that, in the new state, the store contains % only the empty store symbol '#'. % % This transition corresponds to the application of a rewriting % rule of the form A --> a , whereby the machine reads the word % or terminal symbol 'a' while undergoing a transition into the % state labelled by the nonterminal symbol 'A'. % % - Read/Push Transitions during which the automaton shift out of its % current state into a new state while reading an input symbol % and pushing the label of its old state onto the top of its % store. % % These transitions also correspond to the application of rules % of the form A --> a , where the word 'a' is read while the % machine moves into a state labelled 'A'. % % - Lambda/Pop Transitions during which the machine does not read an % input symbol, but pops the topmost symbol from its push-down % store while shifting from its current state into a new state. % (Such moves are called lambda transitions because the machine, % in effect, "reads" the null string during the transition.) % % These transitions correpond to the applications of rewriting % rules of the form A --> B C , where the nonterminal symbol % 'A' labels the new state into which the automaton moves while % 'B' is the topmost symbol in its store with the machine in % the state labelled 'C'. % % Each of the transitions of a push-down automaton is represented as an % ordered quintuple of the form % % % % wherein the entries are as follows: % % Zi is the topmost symbol in the push-down store with the % machine in its current state Qi; % W is either the input symbol (word) read by the machine % during a read/push transition or an initial % finite-state transition, % or W stands for the null string in a lambda/pop % transition; and, % Zj is the topmost symbol in the store of the machine in % the new state Qj to which it moves during the % transition. % % The particular transitions of the machine emulated in this example % are specified by the clauses of the move/5 predicate that appear % at the end of this program. % % The push-down store of the automaton is modelled by a list. The % popping of a symbol from the store is then emulated by the removal % of the current head of this list. The push operation corresponds % to adding a new head to the list. % % The input tape is also modelled by a list. The read operation is % emulated by the process of removing the current head element of % this list. % % The operations of the control unit of the machine are emulated by % the recursive control/3 predicate which includes clauses corresponding % to each of the three types of transition that the push-down automaton % can execute. The arguments of the control/3 structure correspond to % the push-down store, the state of the machine, and the input tape. % The execution of a transition by the automaton is emulated by proving % the head structure of the appropriate control/3 clause. % % The first two clauses of the control/3 predicate correspond to the % accepting conditions of a push-down automaton. A string is accepted % by the machine if all the words comprising the string have been read % so that the input tape it empty and, either the automaton is in an % accepting state, or the push-down store is empty. %s/1 s(Tape) : The list of data tokens, Tape, comprises a % sentence if it is accepted by the push-down % the control unit of which is emulated by the control/3 predicate. % Thus, an input string is presented for processing by typing a query % such as the following: % % s([some, dogs, like, the cat]). % % Processing of the input string in the list Tape is begun with the % machine in its initial state, labelled with the symbol '$', which % is specified as the second argument of the control/3 goal. The % push-down store, represented by the first argument of control/3, % contains only the empty store symbol '#'. % s(Tape) :- control(['#'], '$', Tape). %control/3 control(Stack, State, Tape) : % % 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. % Empty store condition. control(['#'], State, []). % Final state condition. control(Stack, s, []). % Initial Finite-State Transition: A --> a (Eg., Det --> some) control(['#'], '$', [Token | Tape]) :- move('#', '$', Token, '#', Next), control(['#'], Next, Tape). % Read/Push Transition: A --> a (Eg., V --> like) control([Top | Stack], State, [Token | Tape]) :- move(Top, State, Token, State, Next), control([State, Top | Stack], Next, Tape). % Lambda/Pop Transition: A --> B C (Eg., S --> NP VP) control([Top, Under | Stack], State, Tape) :- move(Top, State, '\\', Under, Next), control([Under | Stack], Next, Tape). %move/5 % % The move/5 predicate represents the transition function of % the push-down automaton. The five arguments of the clauses % of the move/5 predicate correspond to the entries of the % ordered quintuples that specify the transitions of the % machine. Thus, each clause % % move(Zi, Qi, W, Zj, Qj). % % corresponds to an ordered quintuple of the form % % % % specifying a transition of the machine. The Chomsky Normal Form % rewriting rule to which each of the transitions executed by this % machine corresponds is identified in the comment following each % move/5 clause. % % The clauses immediately below specify initial % finite-state transitions. move('#', '$', nice, '#', a). % A --> nice move('#', '$', some, '#', det). % DET --> some move('#', '$', the, '#', det). % DET --> the % % The following clauses specify read/push transitions. move(Zi, Qi, nice, Qi, a). % A --> nice move(Zi, Qi, some, Qi, det). % DET --> some move(Zi, Qi, the, Qi, det). % DET --> the move(Zi, Qi, dogs, Qi, n). % N --> dogs move(Zi, Qi, dog, Qi, n). % N --> dog move(Zi, Qi, cats, Qi, n). % N --> cats move(Zi, Qi, cat, Qi, n). % N --> cat move(Zi, Qi, likes, Qi, v). % V --> likes move(Zi, Qi, like, Qi, v). % V --> like move(Zi, Qi, chases, Qi, v). % V --> chases move(Zi, Qi, chase, Qi, v). % V --> chase % The following move/5 clauses define lambda/pop % transitions, with the '\\' atom standing for the % Greek letter lambda which normally denotes the % null string. (Note that two back slant characters % are required because the single back slant % represents a control character. The Listener % treats the two characters as representing % a single back slant.) move(a, n, '\\', Zj, np). % NP --> A N move(det, n, '\\', Zj, np). % NP --> DET N move(v, np, '\\', Zj, vp). % VP --> V NP move(np, vp, '\\', Zj, s). % S --> NP VP