% Linguistics 484 -- Example: CCG_SRA.TXT % % Combinatory Categorial Grammar Shift/Reduce Automaton % % This example illustrates how a shift/reduce automaton might be % modified to operate on the basis of a combinatory categorial grammar. % The operations performed by this automaton include the following: % % Forward Functional Composition, % Forward Type-Raising, and % Type-Changing, % % as well as the Forward and Backward Functional Application operations % demonstrated in the previous example. % % As in the previous example illustrating the implementation of a % categorial grammar, syntactic types of the combinatory categorial grammar % are encoded as lists. Note, however, that in the syntactic type % associations in the clauses of the word/1 predicate below, the word % 'cats' is associated with the type 'N', rather than 'NP', as was the % case in the previous example. In this implementation of a combinatory % categorial grammar, the 'N' type is converted to the 'NP' type by a % type-changing operation as described below in order that the string % 'nice dogs like cats' can be accepted. %word/1 : Associates syntactic types with word forms. % % word(Word_Type) : Word_Type is a list encoding the association % of a word form with its syntactic type. This % list consists of three elements, each of which is itself a list. % The Word_Type list has the following form: % % [[Word], [Operator], Type] % % where Word is a word form, % Operator is the atom 'a' which stands for the ':=' type % association operator symbol, and % Type is a list that encodes the syntactic type of the word. % % In the encoding of an atomic type, Type is a singleton list such % as [n] . % % For functional types, Type is a three-element list with the % following form: % % [Result, [Operator], Arg] % % where Result and Arg are lists, and Operator is either the atom % 'f' or the atom 'b' where % 'f' stands for the '/' forward application operator, and % 'b' stands for the '\' backward application operator. % % If the result or argument of the encoded functional type is % atomic, then Result or Arg is a singleton list such as [np] % or [n], (as in '[[np], [f], [n]]]' for the type of the % word 'nice'). % % If either the result or argument is a functional type, then it % is encoded as a list with the same format as prescribed above % (as in '[[[s], [b], [np]], [f], [np]]]' for the type of the % word 'like'). % dogs := N word( [[dogs], [a], [n]] ) . % cats := N word( [[cats], [a], [n]] ) . % nice := NP / N word( [[nice], [a], [[np], [f], [n]]] ) . % like := ( S \ NP ) / NP word( [[like], [a], [[[s], [b], [np]], [f], [np]]] ) . % As was the case with the previous example, the machine demonstated % here has been adapted to display output consisting of the sequence % of its moves as it accepts an input string. Thus, typing % the following query: % % s([nice, dogs, like, cats]) . % % will cause output something like the following to be displayed: % % Action % <[], [nice,dogs,like,cats]> % Shift : <[[[np],[f],[n]]], [dogs,like,cats]> % Shift : <[[[np],[f],[n]], [n]], [like,cats]> % Apply : <[[np]], [like,cats]> % Shift : <[[np], [[[s],[b],[np]],[f],[np]]], [cats]> % Raise : <[[[s],[f],[[s],[b],[np]]], [[[s],[b],[np]],[f],[np]]], [cats]> % Compose: <[[[s],[f],[np]]], [cats]> % Shift : <[[[s],[f],[np]], [n]], []> % Change : <[[[s],[f],[np]], [np]], []> % Apply : <[[s]], []> % % where the contents of the push-down store or stack together with what % remains of the input string are shown as the automaton executes the % operations required to accept the input string. % % Note that the different kinds of reduction operation, corresponding to % the different combinatory categorial grammar operations, are identified % in the foregoing table of configurations. In the previous example, the % forward and backward functional application operations were identified as % Reduce operations. % % As the configuration table indicates, the first four transitions of the % automaton are the same as those performed by the automaton in the previous % example. The syntactic types of the first two words of the string, 'nice' % and 'dogs', are shifted onto the stack during the first two transitions. % After the second transition, the stack therefore contains the types NP/N % and N , encoded as [[np],[f],[n]] and [n] , respectively. In the % third transition, a forward functional application is performed leaving % the NP type, encoded as [np] , as the only item in the stack. During % the fourth transition, the syntactic type (S\NP)/NP of the third word % 'like', encoded as [[[s],[b],[np]],[f],[np]] is shifted onto the stack % above the [np] type. % % The next transition of the automaton demonstrated in this example % performs a forward type-raising operation. This operation has the form % % NP ==> S/(S\N) . % % As a consequence, the [np] below the [[[s],[b],[np]],[f],[np]] that % encodes the type of the verb 'like' is replaced by [[s],[f],[[s],[b],[np]]] . % % Note that the type S/(S\NP) to which the NP type is raised is % determined by the type (S\NP)/NP of the verb that follows the noun phrase: % the NP is the argument of the functional type S\NP . Thus, the type- % raising operation might be represented as follows: % % NP (S\NP)/NP ==> S/(S\N) (S\NP)/NP ; % % that is, the raising of the NP to S/(S\NP) takes place in the context % of (S\NP)/NP . This suggests that the raising operation is context- % sensitive, which leads to the observation that combinatory categorial % grammar is "mildly context-sensitive." % % During its next transition, the automaton performs a forward functional % compostion operation: thus function S/(S\N) is composed with the % function (S\NP)/NP to yield the function S/NP . This operation may % represented as follows: % % S/(S\N) (S\NP)/NP ==> S/NP . % % As a result, the stack contains the [[s],[f],[np]] encoding of the S/NP % type. % % The next transition performs a shift operation whereby the [n] encoding % of the N type of the word 'cats' is shifted onto the stack. % % The function type S/N below the N in the stack, however, requires an % NP argument. The automaton therefore executes a transition that performs % a type-changing operation. This operation in this case may be represented % as follows: % % N ==> NP ; % % but, as the type-changing operation is implemented in this example, this % operation is performed in the context of the S/NP type. Therefore, the % type-changing operation might be written as % % S/NP N ==> S/NP NP ; % % which constitutes another context-sensitive rule. % % The automaton can now execute a transition that performs a forward % functional application operation which may be represented by writing % % S/NP NP ==> S . % % Since the input string has been exhausted, and the stack contains only % the sentence type symbol S , encoded as [s] , the automaton accepts % 'nice dogs like cats' as a sentence. %s/1 s(String) : The list of data tokens in String comprises a % sentence if it is accepted by a shift/reduce % automaton the transitions of which are emulated % by the move/3 predicate. % s(String) :- move(String, [], Moves), nl, write('Action '), nl, write(' <[], '), write(String), write('>'), nl, list_moves(Moves). % move/3 : Controls the transitions of the shift/reduce automaton. % % move(String, Stack, Path) : String is a list of the words % comprising the input string; % Stack is a list representing the push-down store of the % automaton; and, Path is a list the elements of which trace % the acceptance path of the string. % % The Path list includes the action performed by the automaton % (whether a shift or a reduce operation is executed), and the % contents of the stack and the remainder of the input string % following the action. % % The first clause tests whether or not the input string % has been consumed and the stack contains just the root % or sentence type of the grammar. If this test succeeds, the % string is accepted. % % The second clause performs the reduce operation by proving % the reduce/3 predicate. % % The third clause performs the shift operation by pushing the % syntactic type of the current word of the input string onto % the stack. % move( [], [[s]], [] ) . move( String, Stack_Before, [[Action, Stack_After, String] | Moves] ) :- reduce( Stack_Before, Stack_After, Action), move( String, Stack_After, Moves ). move( [Word | String], Stack, [['Shift ', [Type | Stack], String] | Moves] ) :- word( [[Word], [a], Type] ), move( String, [Type | Stack], Moves ) . % reduce/3 : Invokes predicates that, as they are proved, perform the % operations of a combinatory categorial grammar on the basis % of the syntactic types in the stack. The result of the % operation replaces these syntactic types in the stack. In % this example, the operations performed include forward % composition, forward type-raising, and type-changing, as % well as the functional application operations demonstrated % in the previous example. % % reduce( Stack_In, Stack_Out, Action ) : Stack_In is the stack % before the categorial grammar operation, % and Stack_Out is the stack afterward. Action is the % combinatory categorial grammar operation performed. Note % that, in this example, the difference kinds of reduction % operation, corresponding to the different grammar operations, % are identified in the configurations displayed as the % automaton accepts a string. % % The first rule of the reduce/3 predicate invokes the % fcompose/3 predicate to perform a forward functional % composition operation. % % The second rule results in proof of the fraise/3 goal to % perform forward type-raising. % % In the third rule of the reduce/3 predicate, the change/2 % goal is proved to perform a type-changing operation. % % The last rule invokes the apply/3 goal to perform the % functional application operations. reduce( [Top, Next | Stack], [Compose | Stack], 'Compose' ) :- fcompose( Next, Top, Compose ) . reduce( [Top, Next | Stack], [Top, Raise | Stack], 'Raise ' ) :- fraise( Next, Top, Raise) . reduce( [Top, Next | Stack], [Change, Next | Stack], 'Change ' ) :- change( Top, Next, Change) . reduce( [Top, Next | Stack], [Result | Stack], 'Apply ' ) :- apply( Next, Top, Result) . %fcompose/3 : Performs a forward functional composition of the functional % types specified in its first and second arguments, and % returns the composed syntactic type in its third argument. % % The symbols in the comment immediately above the clause % illustrate the syntactic types in the stack and the % syntactic type that results from the following functional % composition operation: % % S/(S\NP) (S\NP)/NP ==> S/NP % % S / (S\NP) (S\NP) / NP S / NP fcompose( [Res, [f], Match], [Match, [f], Arg], [Res, [f], Arg] ). %fraise/3 : Performs a forward type-raising operation. % % The symbols in the comment immediately above the clauses % illustrate the syntactic types in the stack and the % syntactic type that results from the following type-raising % operations: % % NP ==> S/(S\NP) % % The first clause accounts for cases such as an NP type followed % by a S\NP type. The second clause accounts for cases such as % an NP followed by a (S\NP)/NP . % % NP S \ NP S / ( S \ NP ) fraise( [Arg], [[Res], [b], [Arg]], [[Res], [f], [[Res], [b], [Arg]]] ) . % NP ( S \ NP ) / NP S / ( S \ NP ) fraise( [Arg], [[[Res], [b], [Arg]], [Op], [Arg2]], [[Res], [f], [[Res], [b], [Arg]]] ) . %change/3 : Performs a type-changing operation. % % The symbols in the comment immediately above the clause % illustrate the syntactic types in the stack and the % syntactic type that results from a type-changing operations % such as the following: % % N ==> NP % % Note that, although a type-changing operation such as this is % normally presented as unary, it is treated as binay in the sense % that it is applied only in the context that the adjacent functional % syntactic type requires an NP type, rather than an N . % % N S / NP NP change( [n], [Result, [f], [np]], [np] ) . %apply/3 : Performs either a forward or a backward functional % application operation. % % apply( Next, Top, Result ) : Top and Next are the top and next % types in the stack and Result is % the result of the functional application operation. (Note that % the order of two topmost syntactic types in the stack are switched % in the argument list so that their order corresponds to their % order in the input string.) % % The first clause of the apply/3 predicate performs a forward % application. % % Y/X X ==> Y % % In this case, the argument X is on Top of the stack, and the % functional type Y/X is the Next element below its argument in % the stack. % % The second clause performs a backward application. % % X Y\X ==> Y % % The functional type Y\X is on Top and its argument X is the % Next element below it in stack. % % Preceding each of the two clauses is a comment showing the % corresponding functional application operation written in % categorial grammar notation. % Y / X X Y apply( [Result, [f], Arg], Arg, Result ) . % X Y \ X Y apply( Arg, [Result, [b], Arg], Result ) . %list_moves/1 % % list_moves( M ) : M is a list of the moves executed by the % shift-reduce recogniser during an analysis. list_moves( [] ). list_moves( [[Action, Stack, Input] | Moves] ) :- write( Action ), write( ': ' ), show_move( Stack, Input ), list_moves( Moves ) . %show_move/2 % % show_move( Stack, Input ) : Display the contents of the % push-down store (Stack) and the % remaining segment of the input string of the % recogniser as an ordered pair. 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_move( Stack, Input ) :- reverse( Stack, Store ), write( '<' ), write( Store ), write( ', ' ), write( Input ), 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]).