% Linguistics 484 -- Example: TD_DFR.TXT % % Production Systems: A Top-Down, Depth-First Recogniser. % % This example illustrates a Production System which operates top-down, % and depth-first, to recognise a sequence of data tokens as a sentence; % that is, it consists of a collection of facts representing a % Production Set, together with a set of rules for testing and applying % productions which cause the Prolog Listener to function as a Production % System Interpreter. % % This recogniser is described as working "top-down" because it begins % with the root symbol of its grammar and, by applying productions % (rewrite rules) successively, it essentially "derives" the sequence of % input tokens (assuming they constitute a sentence according to its % grammar). % % In its initial state, the Database contains the root symbol, s, of the % grammar. As the Production System Interpreter works, the left-hand % side symbols of productions in the Production Set are tested against % symbols in the Database. A production is applied by replacing the % symbol in the Database which matches its left-hand side with the % symbols comprising its right-hand side. On recognition of the data % tokens as a sentence, the Database contains just the data tokens. % Note that, in this implementation, the Database itself does not appear % explicitly; rather, the individual symbols comprising it, at any given % stage of the recognition, appear in the arguments of predicates as % productions are tested and applied. % % In the Prolog implementation of a Production System, the Production % Set consists of a collection of facts, each of which corresponds to a % production, that is, a rewrite rule. Other predicates in the module % consist of assertions which cause the Prolog interpreter to, in % effect, function as the Production System Interpreter; that is, these % assertions cause the Prolog interpreter to test productions, and apply % them to the Database. % % The productions of a Production System correspond to the rewrite rules % of a grammar. In fact, a Production System can be said to be % equivalent to a context-free phrase structure grammar in the sense % that, given a context-free grammar, a Production System can be devised % which will recognise just the sentences generated by the grammar. % A particular Production System, which is initially equivalent to one % grammar, can be made equivalent to another, different grammar by % changing its Production Set, that is, by adding, deleting, or % modifying productions so that they correspond to the rewrite rules of % the new grammar. In a Prolog implementation of a Production System, % these changes are made only to the facts comprising the Production % Set; it is not necessary to change those assertions associated with % the testing and application of the productions, that is, the % assertions which cause the Prolog interpreter to function as the % Production System Interpreter. % % A Production System recogniser can be contrasted with the Prolog % implementation of a Declarative Clause Grammar in terms of how the % rewrite rules of a context-free grammar are incorporated. In the % Declarative Clause Grammar implementations previously illustrated, % only the lexical category rules were transcribed as Prolog facts; all % other rewrite rules were represented as Prolog rules, with the left- % hand side of the rewrite rule as the head, and the right-hand side as % the body of the Prolog rule, and with the symbols in the rewrite rule % being used as the names of the goals (in lower case, of course). % % A further difference between Declarative Clause Grammars and % Production System recognisers is that, in a Prolog implementation of % a Declarative Clause Grammar, there is nothing corresponding to the % Production System Interpreter; assertions corresponding to rewrite % rules are simply tested directly by the Prolog interpreter. This % testing (and implicit application) of rewrite rules proceeds according % to the proof procedures followed by the Prolog interpreter, including % the order in which goals are tested. Thus, the testing process is % almost entirely under the control of the interpreter, and there is % virtually no provision for altering the process. In contrast with % this state of affairs, the Interpreter component of a Production % System provides control of the recognition process and affords a % facility whereby different procedures may be studied. For example, % as was shown in earlier examples, a recognition can be conducted % bottom-up, rather than top-down (as is "natural" for a Declarative % Clause Grammar), and breadth-first, rather than depth-first (again, % the "natural" strategy for a Declarative Clause Grammar). Furthermore, % a recognition can also be undertaken in a top-down, depth-first % fashion by a Production System, as the present example illustrates. % %s/1 % % s(Data) : The list of tokens in Data constitutes a sentence if, on % starting the recognition with the root symbol, s, in the % Database, all the tokens in Data are consumed, leaving the % null list (as a consequence of the successive application of % productions to the Database, beginning with a production % with the root symbol as its left-hand side). % s( Data ) :- test_rule( s, Data, [] ) . %test_rule/3 % % test_rule( LHS, Data, Data_i ) : A rule with left-hand side LHS (and % with right-hand side RHS) is selected, % if it can be applied, and as a % consequence, the initial data tokens in % Data are consumed, leaving the remaining % tokens in Data_i. % test_rule( LHS, Data, Data_i ) :- prod( LHS, RHS ), apply( RHS, Data, Data_i ) . %apply/3 % % apply( RHS, Data, Data_i ) : A rule with the right-hand side symbols % RHS is (or, has been) applied, with the % initial data tokens in Data being % consumed, and with the remaining tokens in % returned in Data_i, if -- % % - all the right-hand side symbols are matched; or, % % - the right-hand side symbol matches the initial data % token; or, % % - a right-hand side symbol matches the left-hand side of a % production which can be applied, and the other right-hand % symbols result in other productions being selected. apply( [], Data, Data ) . apply( [Word], [Word | Data_i], Data_i ) . apply( [Symbol | Symbols], Data, Data_j ) :- test_rule( Symbol, Data, Data_i ), apply( Symbols, Data_i, Data_j ) . %prod/2 % % prod( L, R ) : L is the left-hand side symbol of a production and R is a % list of the right-hand side symbols. % prod( s, [np, vp] ) . prod( np, [det, n] ) . prod( vp, [v, np] ) . prod( n, [cat] ) . prod( n, [rat] ) . prod( v, [ate] ) . prod( det, [the] ) . prod( vp, [v, np, pp] ) . prod( p, [in] ) . prod( n, [road] ) . prod( pp, [p, np] ) . prod( np, [np, pp] ) .