% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
%                                                                           %
% File:            burecog.dtr                                              %
% Purpose:         deterministic shift reduce context-free recogniser       %
% Author:          Dafydd Gibbon, September 1989                            %
%                  with revisions by James Kilbury, 1992                    %
% Email:           gibbon@spectrum.uni-bielefeld.de                         %
% Address:         Univ. Bielefeld, P 100131, D-33501, Bielefeld, Germany   %
% Version:         2.01                                                     %
%     Copyright (c) University of Bielefeld 1989.  All rights reserved.     %
%                                                                           %
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %

# vars $CAT: s np pp vp det n p vdt vpr vi vd vt vtpr c.

% Strategy
% (1) Initial lexical lookup.
% (2) If there is only a start symbol in the path, accept.
%     (This needs checking, e.g. with right recursion.)
% (3) If reduceable, do so.
% (4) Otherwise, shift.
% (6) If attempting to shift last item, remove it.
% Note that a generalisation is made between Reduce with
% straightforward left branching, and Reduce after Shift.
%
% Shift-reduce algorithm:
%  Or accept(initial symbol only on stack)
%     and reduce(if match with rhs of rule)
%         shift
%     shift.
%
% Example:
%    . det n v det n   Input
%    . np v det n      by Reduce
%    np . v det n      by Shift
%    np . v . det n    by Shift
%    np . v . np       by Reduce
%    np . v np         by Return
%    np . vp           by Reduce
%    np vp             by Return
%    s                 by Reduce

Recognise:
       <> == Shift_reduce:<Lookup:<> '#'>.

Shift_reduce:
       <> == <Reduce:<>>
       <s '#'> == true
       <false> == false
       <'#'> == false.

Reduce:<> == Shift
       <n> == np Map:<>               % np --> n
       <det n> == np Map:<>           % np --> det n
       <n pp> == np Map:<>            % np --> n pp
       <det n pp> == np Map:<>        % np --> det n pp
       <p np> == pp Map:<>            % pp --> p np
       <vt np> == vp Map:<>           % vp --> vt np
       <vdt np np> == vp Map:<>       % vp --> vdt np np
       <vpr pp> == vp Map:<>          % vp --> vpr pp
       <vtpr np pp> == vp Map:<>      % vp --> vtpr np pp
       <vi> == vp Map:<>              % vp --> vi
       <vd s> == vp Map:<>            % vp --> vd s
       <c s> == s  Map:<>             % s  --> c s
       <np vp> == s Map:<>            % s  --> np vp
       <np vp pp> == s Map:<>         % s  --> np vp pp
       <pp np vp> == s Map:<>         % s  --> pp np vp
       <pp np vp pp> == s Map:<>.     % s  --> pp np vp pp

Map:   <> == 
       <'#'> == '#'
       <$CAT> == $CAT <>.

Shift: <$CAT> == $CAT Reduce:<>
       <$CAT '#'> == '#'.

Lookup:<> == 
       <$WORD> == Undefined           % not contained in the lexicon
       <the> == det <>
       <this> == det <>
       <that> == det <>
       <th@t> == c <>
       <man> == n <>
       <woman> == n <>
       <child> == n <>
       <ball> == n <>
       <corner> == n <>
       <with> == p <>
       <in> == p <>
       <for> == p <>
       <on> == p <>
       <decide> == vpr <>
       <put> == vtpr <>
       <gave> == vdt <>
       <went> == vi <>
       <said> == vd <>
       <observed> == vt <>
       <visited> == vt <>.

% Comments (Kilbury)
%
% (1) As is stated explicitly above, this DATR implements a recognizer
%     rather than a parser. But it should be easy to modify the theory
%     so as to return the category found, if any, for the input string
%     or even a phrase structure tree in linear notation.
% (2) The end of the input string is treated incorrectly.  The axiom
%     added to LOOKUP allows BU_RECK.DTR to reject sentences like
%            *the man went foo
%     which contain words not in the lexicon, but strings like
%            *the man went went
%     are still incorrectly accepted.

% The next line is the Revision Control System Id: do not delete it.
% $Id: archive.dtr,v 1.1 1997/04/09 20:40:33 root Exp $