Unrestricted Gapping Grammars

1. INTRODUCTION

Gaps have been introduced into logic grammars. resulting in extraposition gramtTUlT's (Pereira. 1981) and gapping grammors (Dahl and Abramson. 1984). to express a more general grammar rule that can be interpreted with "reasonable" efficiency by a computer. The rules of these grammars are of the form "nt. a --> (3". where nt is a nonterminal symbol called the head. and a and f3 may contain terminal symbols. nonterminal symbols. procedure calls. and gap symbols." Extraposition grammars are able to provide concise descriptions for left extraposition as found in sentences like the rrwuse thot the cat chased squeaked. However. extraposition grammar rules are more restrictive than those of gapping grammars. since the gaps

referenced on the left band side of the rule must be repositioned in the same order at the end of the right band side. Also. the contents of multiple gaps must be nested (one gap totally contained within another ). or non­ intersecting. With gapping grammars, concise descriptions of coordination . free word order. and right extraposition can be obtained (Dahl. 1984).

'This work was supported by Engineering Research Council of Grant no. A4309. Installation Postgraduate Schalarship #800. the Natural Seiences and Canada under Operating Grant no. SMI-74 and

"Gap symbols are used to reference sequences of unspecified symbols.

Unrestricted gapping grammars extend gapping grammars by the removal of the restriction that the left band side of all rules must start with a nonterminal symbol. Consequently. the unrestricted gapping grammar rules resemble "a -> (3". where a and f3 may contain terminals. nonterminals. gaps and procedure calls in any order. This type of rule facilitates easier description of unrestricted left movement of symbols.

Unfortunately. the use of gaps can result in less efficient computer processing of the rules. Consequently. many applications of gapping grammars have not been explored except from a theoretical point of view. One : method to circumvent this "efficiency problem" is to add · procedural control to the otherwise declarative grammar rules. (The cut facility of Prolog (Clocksin and Mellish. 1981) is an example of this procedural intervention). FIGG. a Flexible Implementation of Gapping GramtTUlT's, is a programming language that incorporates procedural control to process many unrestricted gapping grammars with tolerable response time in an interactive environment. Using FIGG. the different forms of procedural control can be examined for their uses with unrestricted gapping grammars.

2. UNRESTRICI'ED GAPPING GRAMMARS

Unrestricted gapping grammars, like other logic grammars. use logic terms as grammar symbols. A logic ierm consists of a functor. which may possess zero or .more arguments. Each functor possesses an order. which : corresponds to the number of arguments. and is an 'element of some finite set F. The arguments. which are ' enclos~d in parenthesis and separated by commas. may be 'logic terms. or variables. Il [F] is used to ref er to the set _ ' of Jogi~ terms that can be constructed from F. In this · paper. elements of F will be represented by words starting with a lower case Ietter. or enclosed in single quotes. Words which start with an upper case Ietter or an und er ,c,.re · "_ ·. will represent variables . A list. which is a logtc term of the form '.'(a< 1 .'.'(a< 2 ·.. .'.'(a<n.nil) ... )), is usually represented as [a< 1 ,a< 2 · . ... an]. Also. [tll] is a shorthand for '.'(t.l). During a derivation according to the grammar. variables may be unified with other logic terms (CI<·cksm dnd Mellish. 1981). Logic grammars also tend to possess facilities for handling procedure call.s appearing within the grammar rules.

An unrestricted gapping grammar can be defined as a quintuple (V N' V T' r. r.. P) where: V N is the set of nonterminal symbols. VNcll [F]; VT is the set of terminal symbols. VTcll [F] . with vNnvT = cf>; r is the set of gap Symbols. feit [F]. with rnV = cf>, where V = V NU V T; r. is the set of starting symbols. with r.cv N ' and P is the set of productions of the form

.., .., v'."' 0 <::: j <::: n. ai.ßi E with m, n;?!: 0. 0 ~ i ~ m. and gap(G ). gap{G'.) Er. l 1 · between elements of V may The rewrite relation. ==>. be defined as

for a production (2.1) where Y;o'Y'· E V'. lgnoring variable substitution, the language. LCG). associated with this grammar is

Unrestricted GGs can provide simpler description of some forms of left extraposition than was possible using GGs. To illustrate this point. Iet us examine a language. L. described in Ooshi. 1983). This language is obtained from ((ba)"c" I n;?!: 1} by "dislocating some a·s to the Jeft." Using an unrestricted gapping grammar. this language can be described by the following productions.

The rules are constructed to allow an a to be moved only once. An equivalent grammar using GG rules. that does not shift b"s to the right. requires the addition of at least one production.

ln (2.5) . the nonterminal target represents a location where an a may be moved to. while epsilon. E, corresponds to the empty string.

"'For any set S. s' = u:aS;·

"" == >' is the reflexive transitive closure of == >.

Along with easier description of left relocation of symbols. there is another phenomenon that· follows from the removal of the nonterminal head restriction. The definition of rules resembling "e --> ß" is no Ionger prohibited. With this style of production. rule (2.4c) could be replaced by the following two rules.

Any targets introduced somewhere to the left of an a by (2.6b). can be replaced by an a which is dislocated to the left according to (2.6a).

To facilitate further study of unrestricted gapping grammars. and to examine mechanisms for introducing procedural control to provide more efficiently executable productions. the FIGG programming language was developed. FIGG is a Prolog programme that implements a !arge subset of unrestricted gapping grammars.

3. FIGG

FIGG currently consists of a bottom-up shift-reduce parser and a top-down depth-first parser which can operate (independently) on a set of unrestricted GG rules. The system also provides built-in control operators which allow the user to create efficiently executable grammar rules. The top-down depth-first backtrack parser incorporates these procedural control mechanisms in a parser which is based on one described in (Dahl and Abramson. 1984). It differs from its predecessor by allowing left recursion in its grammar rules. and by being more efficient. although not as general. Rules are still required to have a nonterminal as the head. The shift reduce parser used with FIGG is a variation of a context free shift reduce parser (Aho and Ullman, 1972) (Stabler, 1983) extended to allow non-context-free rules and gaps. To mirror the left to right processing of the top-down parser. the shift reduce parser processes a sentence from right to left. Details about the syntax and implementation of FIGG can be found in (Popowich. forthcoming) .

The implementations of many previous logic grammars incorporated clumsy mechanisms for procedural control. Unless one resorted to arbitrary procedure calls. the only options available for such control were rule order. the introduction of marker symbols. or the cut operation. Increased control facilities provided in FIGG include control of gap processing. more sophisticated variations of cut, and restrictions on applicability of rules. For example. when the FIGG parser is processing a gap symbol. gap(G). it initially assumes an empty gap and then attempts to parse the next symbol. Through backtracking. the gap size is increased. However. a decreasing gap. gap(- .G). is initially assumed to contain the rest of the sentence. and is decreased in size during backtracking. Also. although the cut behaves as in Prolog during top-down parsing. it behaves differently during bottom-up parsing since the top-down parser operates on terminal symbols - like the definite clause grammar parser (Pereira and Warren. 1980) - while the shift reduce parser works with sentential forms. For bottom-up processing. each rule is converted into a single Prolog clause that modifies a list which eorresponds to a sentential form. When the right band side of a rule rnatches part of a sentential form. the rnatched region can be replaced by the left band side of the rule. Consequently. cuts - and other control rnechanisrns - that appear in the right band of a rule affect the left to right matehing of the rule to a sentential form. Once the portion of a rule to the left of a eut has rnatched a sentential form. a subsequent failure in the rnatch occurring to the right of the cut cannot force the rnatch to the left of the cut to be reatternpted. A cut found in t he left band side of a rule. R , will prevent any subsequent rule. K . frorn matehing a region entirely to the right of the cut. That is. the application of K to the sentential form resulting frorn the application of R rnust include at least one syrnbol to the left of the cut. If a rule. R. is entirely enclosed in a cut. (R)!. then the decision to apply R to a sentential form cannot be revoked once the rule has been successfully applied.

4. USE OF PROCEDURAL CONTROL

Unrestricted gapping gramrnars. as implernented in FJGG. can be considered as a prograrnrning language. and can be used to provide parsers for languages. given a grarnrnatical specification. Few studies have been done to exarnine the applicability of gapping grarnrnars as a prograrnrning tool. since the earlier irnplernentations were either inefficient or processed too srnall of a subset of these grarnrnars. We will exarnine sorne ways to control the processing of unrestricted GG specifications to irnprove the efficiency of the parsing. and to restriet the language descr ibed. In this section. we shall use a selection of f arniliar f orrnal languages to various control rnechanisrns . . natural languages is exarnined (Popowich forthcorning) . exarnine the use of the The use of FIGG with in (Popowich. 1985) and

Consider the context sensttlve language L 1 = {ambncmdn I m.n ;;l: 0} . A set of productions (Dahl. 1984) of a gramrnar. G 1 · that describes this language is provided in (4.1).

Behaviour of fJGG with this grarnrnar and with, strings of increasing length is surnrnarised in Table 4-1. Tirnes are in CPU seconds for a SUN Workstation running C-Prolog (Pereira. 1984) under UNIX."'" The first nurnber represents the time required for a successful parse. and the second number includes the time spent looking for all other possible parses. The results expose a severe parsing problern for G 1 with increasing sentence length. However. closer exarnination of (4.1) illustrates that the gaps should result in the ith a matehing the ith c . and sirnilarly for the b's and d 's. If a decreasing gap is used in the productions. then the first sueeessful gap followed by a e ( or d . depending on the rule) will result in the correct rnatching. A cut ean then prevent the other alternatives from being tried. Thus. G' 1 is obtained by modifying (4.1b-e) as shown in (4.2). resulting in rnueh irnproved perforrnance as illustrated in Table 4-1.

"'"UNIX is a tradernark of Bell Laboratories.

While G 1 and G' 1 are processed by the top-down parser. �~ tn Table 4-1 represents a grarnrnar equivalent to G' 1 that ts processed by the bottom-up parser. In this case. the bottom-up proeessing takes about two and a half tirnes Ionger than top-down parsing.

Now eonsider the produetions that describe the language L 2 = {anbncn I n > 0} .

Unfortunately . a gapping grarnrnar containing these productions would be ambiguous. The arnbiguity ean be removed through modifieation of (4.3b-e). as shown in (4.4). resulting in a new gapping grarnrnar Gi.

An unambiguous unrestricted gapping grarnmar. a;. which has one Iess produetion and one less nonterminal syrnbol than Gi. can also be provided for this language.

The parse times for various sentences. where G2 and a; are proeessed by the top-down and bottom-up parsers respectively . are sumrnarised in Table 4-2. This time. the bottom- up parser is slower by a constant multiple of three However . 1ts slowness is offset by the fact that it can process many more grammars than its top-down counterpart. <\n unrestricted gapping grammar can be used by the bottom-up parser as long as it does not result in bottom-up cycles. For example. any grammar containing the rule "nt --> e". can not be used by this parser. Further development on this Prolog parser may improve its efficiency.

Thus. the results illustrate that the introduction of some limited procedural control can be done simply with very beneficial results. Without its introduction. the processing time may be intolerable in some cases. It will not always be possible though. to introduce simple restrictions on gaps and parsing. The effect of a control mechanism is also very dependent on the grammar itself. As illustrated in the examples. the same operator - the cut - can result in more efficient parsing. or can restriet the language described by the grammar. The determination of which control to use. and how to use it. is the responsibility of the person who contructs the grammar. Obviously. more study of procedural control is required.

5. SUMMARY

Lnrestricted gapping grammars provide more concise grammatical descriptions than previous logic grammar formalisms for many languages due to the more general rule format allowed. However, with such a general rule formal . caution must be taken to insure that the grammar is restricted. by some form of control. to describe the required language. Control facilities provided in FIGG permit rel ined control mechanisms while maintaining a high degree of descriptiveness in the grammar rules. These control facilities can be used either to restriet the language described by the grammar. or to obtain more efficient parsing The parsers of FIGG have successfully combined prol·essmg efficiency along with a !arge subset of unrestncted gapping grammars to produce a programming environment to study grammars and their languages.

ACKNOWLEDGEMENTS

I would like to thank Nick Cercone and the referees for their comments and suggestions. Facilities for this research were provided by the Labaratory for Computer and Communications Research.