A PROCEss-AcTIVATION \]8~SF, D PARS~gl ~kL, GOR~'I-la~ 
I~OR 
TIlE DEVELOPMENT OF \]NATURAL LANGIIAGIg Gk~ 
Massimo MARINO 
Department of lAnguisties -, University of \]~51sa 
Via S. Maria 36 - 56100 Plsa -- ITALY 
Electronic Mall: MASSIMOM@ICNUCEVM.BITNET 
ABST~CT 
A running system, named SAIL, for the development 
of Natural Language Grammars is described. Stress Is put 
on the particular grammar rule model adopted, named 
Complex Grammar Units, and on the parsing algorithm 
that runs rules written In according to this model. 
Moreover, the parser is like a processor and sees grammar 
rules as processes which cart be activated or Inactivated, 
and eaxi handle exchange of information, structured as 
:messages, among rules for long distance analysis. A brief 
description of the frmnework of SAIL a user can interact 
with, neaned SiS, is also given. Finally, an example shows 
that different greanmar formalisms can be implemented 
into the frame of SAIL. 
X o INTRODUCTION 
Most recent research in the field of grammar 
Ibrmalisms and parsers for naturallanguage has seen the 
flourishing of various theoretical as well as 
coralmtational accounts, which, however, bring into 
consideration the same lacts. The most relevant ones 
~,mem the following: 
-~ whatever representation is adopted for the structure of 
the parsed sentence (basically f-structures or trees), it is 
agreed that {complex) sets of features must describe the 
linguistic units. It is, therefore, necessary to provide 
feature handling mechanisms; 
long distance dependency, or, more generMly, 
dependency, requires a specific treatment, which Is to be 
naturally embedded in the theoretical or computational 
model of syntax, and must be subject to language 
dependent constraints. In aaly case, the treatment of 
dependencies takes the form of a differently constrained 
search Ibr a referent; 
- a certaln amount of context-sensitiveness is to be 
allowed in natural language parsing. 
As an additional feature of recent research, the 
l~mlinatlon towards the one-to-one correspondence 
between semantic and syntactic rules has to be 
mentioned. 
SAIL Is the parsing algorithm of a development 
environment, called SAIL Interfacing System, where 
different grammars corresponding to different 
grammatical theories can be hnplemented (/Marlno 
1988/I. Its basic features, which allow full 
implementation of grmnmars and their debugging are as 
lbllows: 
a ,teh lmlguage for the handling of features; 
grammar rules are seen as processes which can be 
activated or Inactivated, and can exchange messages; 
this mechanism allows a natural treatment of 
dependencies and the running of context-sensitive rules; 
the format of the rules Is such as to allow semantic 
processing in parallel with syntactic processing; 
the traditional structure of the parser, a bottomoup 
all-paths algorithm, allows relative efficiency mid the 
590 
ca W integration of a diagnostic component fi~w debugging; 
the development envirotJrnent is based on dllterent 
layers of rules, which are processed by the same parser 
and can handle the external interface, the particular 
application, and the debugger. This enables the user to 
modify also the front-end of SAIL, by modifying tile 
corresponding grammar. 
2. TItN G~AR RI\[1LN FONISN 
The grammar rules are expres,~md ix-, a tbrmallsm 
called Complex Grammm Units g','.G.Uos) having the 
tbllowing BNF: 
CGD" ::= 
<Syntactic-Rule> :::: 
<ProducUo~ ::= 
<LHS> ;;= 
<I~-IS> ::= 
<Synerests> ::= 
<S~\]n-ActIo~> ::= 
<Syn-Recovery-Actiorr~> ::= 
<Semantie~Rule> ::= 
<Sere:rests> ::= 
<Sem-Recov(,, y ,Actions> ::A 
<Syntactic-Rule> <Semantic-Rule> 
<Prrnluetlon> <8yn-.Tests> 
<Syn-Actlons> 
<8yn-Recovery-Actions> 
<LHS> <RHS> 
A non-ternmaal symbol of the 
g~mrim~' 
A pat*era st~lng of terminal 
arid/or non..termUral uymbols 
Borne teats on the applicability of 
ttte syntactic aetimm 
Arbitrary syntactic actions 
Syntactic actions for the recovery 
In case of rmatch-ihfl or test-f-.dl 
<Sere-Tests> <Sere.Actions> 
<SemoRecovery-Actions> 
Some te~t.~ on the applicability of 
the semantic rule 
/U'blhary semantic actiorLs 
"Semantic aetloIlg for the recovery 
in case of match4all or test-fall 
In. each grmimlar rule the syntactic intexpretation is 
directly connected with the corresponding semantic 
interpretation: hL this way the pea'ser processes in parallel 
both interpretations. 
Inside the augmentations we can do several things: 
- the tests arc evaluated before the application of a rule 
and through *hera we can check its applicability; 
- every node of the parsing structure contains structural 
infbrmation about the part of sentence it covers; this 
information is local to each node and is stored as a 
feature structure tree. "l~e features are classically 
stored as attribute-value pairs, with the possibili .ty that 
a value la itseff an attribute-value pair; several feature 
handling functions are defined inside the system, so we 
cea~ use them with the augmentations to create, delete. 
test, get, copy and raise features; 
the semantic rule acts on the semantic part of the 
system, which can be, for example, a t~ handled by a 
knowledge representation language; tkfls side is 
dependent on the system application; 
-the semantic actions are a sequence of semantic 
operations, includkng the possibility of assigning :,t 
semmatic value to the new node built by the ~:ule; The 
semant;e value assigned to a node represents, In 
general, the meaning of tb.c" t)mt of the sentence the 
node covers, accordh~g i(~ the chosen fonrmlism; 
• the eye, tactic and se_manti.e recovery aetimm allow 
tdte~ rmt ive actions ff the rule fails during the matehi~ ~g 
phase or the test checking, so the rules need not be 
m-udely rejected Mten they fail; 
-- soirie bLdlt.4n system functions are available: these 
tools handle, for example, the particular execution of a 
rule, o, ,.nodlly tile parsing processing, etc.; these 
~ilecha:~iJ.sllks are discrtssed below. 
The production in each nile Is classically represented as 
a Cmfi;c~_rt -lq:ee producttm,: A- ~ w, w= _. w,, where A 1,.; a 
no~ ~ 4:~:~_utJn~d syt~llool a lid w~ wa ... w,, is a si~:lng of terminal 
atul/or :ta~m. te~miual symbols. 
The ~ ole,'~ of the grammm are applied by the parser hi a 
bottoln-lt i) 'w~ly: it ,';tin t,'~ fiom the sentence and build,~ 
over it the parsing sh tlctnre as a graph. 
In our system we Mso have a dh;ttonmy D. Each item 
in the dictionary is (:::filed a .~.'ox',t.< We dlsLing~fish betweeu 
ah~gle £ox~ta al~d ~aut¢itAe i'ox~as. The first matehes the 
ge,mral concept of ~, word; the second defines a nmltl- 
word expxession of the language, typically an idiom. 
One or more interpretations are associated with each 
tb~at and they consist of the syntactic categmy, the 
se.mantie value and a \[(~ature structure. 
A sentence is a conlpoLllld of fonus. For every set~temm f, 
fa...~ SUCh ttrat every tbrm i~ D, and a grammar G defined 
in our model we say that f~ f,...f, is palaable If we car~ 
build a sU'uc.tu,e lhrough a finite sequence of rule 
applleatirms, where at least one node covers the entire 
aentenee and its; category Is the root synibol of the 
gl~mnlna, ~ 
Rule appllcation,~3 are performed by tt}.e pro'set in a 
bottom-hi) ,';tratep~ whez~eve~:: 
a. at leae;i: one sequence of nodes exists in the sh-ucture 
the l)a>'scr has been building, matching the <RtIS> 
part of the rule; 
b. if' the above condition holds tile parser verifies the 
tests of the rule; if they ate veiified the nile is applied; 
c. if the match fails, or the tests are not verified, then the 
parser eKe.cures recovexy actions° 
~lt~e core application oft CGU consists in: 
d. bnllding a new node cot.responding to the <I,I-IS> part 
of the ~ ule; 
e. assigning lcature,~.; to the new trade by executing the 
~'~y~ffacl:ic action'.; of the rule; 
f. exeent;h~g the semantic actions of rile nile, and 
possibl~, assigning the semantle value to the new 
nude. 
In the ibllowing we always rep~et;ent the production In tile 
standard way as above; the feature structures associated 
wl~:h a no0e of category w~ are represented as \[\[~,1 and tile 
semmttlc vahm as \[Iw,\]i, 
We.' carl Sl),~cii ) tile complete process of a rule application 
by means of a PASCAL-lithe statement as follows. 
Ne~4~eeover3ro.Aetlons 
t~d 
hq~J~ 
~y~x-Ite c ovety-Aetlo~; 
~ ~e ,'~-lleeovea-~-Acllom~ 
"llm rules are grouped in such a way that the parser 
accesses to a restricted number of them, i.e. only the 
currently applicable ones, when it t~tes to apply SOlne. 
This is accomplished by partitioning the rules into 
~-meket~ discriminated by the last: category in fire right- 
band side. If a grammar is partitioned as t'~ ..... Pk then for 
every ld:,l ..... k, i:~l, we must have tlmi. I., r~ P~ ::: {}. So when 
the parser acee.s.~;es a packet through the category of a 
node, thc rrdes In that packet are the tufty ones al~l)lleable 
at that momeut. 
Now let us introduce the coneepl of Not Operative 
/~:oflttet, tiOnu. 
In gene, ral such productions do not build a new node If one 
of the three special categories <NOP>, <NOP-ASE>, 
<NOP-.SE> is the left-hand side. A Not Operative 
Production is one of the following: 
{ <NOP> I <NOP--ASE> I <NOP-SE> } - > v% % ... w 
Rules •with such productions are ealled NOt- Rules. 
l)epending on the NOP-eategoly used, tile rule 
appliealton is performed i,~ a special was. 
A NOP rule with <NOP> as lett-.hand side Is applied as 
follows Jf lhe syrltaette tests succeed: 1) no new node is 
l)uJlt; 2) only ihe syntactic rule is iakci~ into accomlt by 
the parser; 3) the semantic rule is never considered. 
Therefore the application of such a rule iy.pc ia pe~ lbnned 
as in the following PASCAL-like statemc~.l : 
iJ_' i~tch ( w~ ..... wu, graph ) 
Iben LfNyn-Test,a (\[it~l ..... I!~,J ) 
gloat Sy~t,,Recovery-Aetton~ 
'.¢ !f~Jt S y~141ec ore ~-y.,Ae, t Ions; 
This kind of NOP rule is useful when we are interested ir~ 
performing modlfleatlons or particular consh-uctions or 
analyses on features Inside a eetiain contexi without 
building a new node. Such a kind of NOr' rule is purely 
syntactic. 
in a producl~on with <NOP-ASE> a s left-hand side, ff both 
syutaetle and semantic tests succeed: 1) no new node is 
built; 2) the rule application is preformed in the standm'd 
way° irmlndiug feature hmadllng if it does not iovolve the 
non--existent parent node. 
In a production with <NOP-.SE> as left-hand side, if oMy 
itic semantic tests succeed: 1) no new node is t)uilt', 2) only 
the semantic rule is taken Into account by the parser; 3) 
file syntaclle rule is never considered. From thereon 
application is the dual of that defined for tim <NOP> 
category. 
.!( lVlal;ch ( v, l ..... w. graph ) 
/* ~;c:.~:~'~q~ one o~ mo~c ,~clt; ~1" ~mdcs matching the <I:tIIS> */ 
~;em.-'r~ata ( \[1%11 ..... \[\[wJl, SEM ) 
/* :~;EM ie, presetllt; {he s;elnain'lc itlode\] */ 
~'~a~td (A, ,.% ..... %, J; 
/* build a **eve node A ovm the matched nodes */ 
f~ls~q .i)eghL 
& R'(JLE~ AS PROCESSES 
The rtfles defined ill our sysiem ~re viewed as 
proeesses to be executed by the proset which has the roie 
ofi~e processor° Aa a consequence, a state is assigned to 
each rifle which is determined at the moment of grammar 
dellni|ion. Rules can assume two different ~tates: aettve 
or i~xaefive state. A rule is aettw.~ when the parser 
normally takes it into account for application; rules are 
acLivc when their names are in their colresponding 
packets. A rule is inae, ttve when the parser does not 
normally take it into consideration for application; rules 
are inactive when their names are not in any packet. 
It is possible to modify the state of a rule by memm of two 
39\] 
tunetions within the augmentations dining a rule 
application. 
A rule R, changes its state from active to Inactive if some 
rule Rj calls within its augmentations the function nile- 
dtsable for R,, performing a disabling operation; on the 
termination of the disabling rule R j, the disabled nile 
name R, is removed from the corresponding packet, and 
the parser does not take into account R,, Conversely, a 
rule l~ ehaazges its state from Inactive to active If some rule 
calls the function rule-enable for Ph within its 
augmentations, perlbrming an enabling operation. On 
the termination of tlm enabling rule R r the enabled rule 
name R, becomes present into the corresponding packet. 
It Is possible to change the state of one or more rules at 
a time through these functions and the rules can perform 
self-enabling and self:disabling operations. Changes of 
state effected during the parsing are not penuanent. At 
the end of each parse the rules are reconfigured as 
indicated in their original definition. 
In addition we cruz invoke an inactive rule for just one 
application from another rule. We say that an inactive 
rule R~ is activated to be applied Just once, when a call to 
the function rifle-activation is in some augmentation of 
another rule R r The activation of an inactive rule R, allows 
just one application of it by the parser, immediately after 
the termination of the activating rule R r The state of the 
activated rule Is not modified. The activation of more than 
one rule at a time Is possible, and once a rule ls activated 
it can activate other rules, 
4o CONTEXTUAL RULES 
Rule activation bymeans of the rule-actlvation 
function, together with NOP rules can be used to handle 
context sensitive languages, However, rials is entirely 
done by means of CF productions and the 
augmentations. 
A typical CS production is: ~h A p~ --~ p, 1~ ~h where p,, 
p~, 13 are strings Of symbols, and A is a non-terminal 
symbol. A bottom-up applieation of such a production is 
possible lfit happens in two steps: 1) indlviduation of the 
context p~ I~ P~; the right-hand side must match a 
sequence of sub-trees that covers 1~13 1~; 2} Inside this 
context we can perform the api~lleaflon of the CF 
production A .-~ \[~ building the node A over the sequence 
of nodes characterized by ~l. So the complete application 
for a CS production is made in two steps: the tlrst one 
concerns context determination, the context being 
represented by the right-hand side of the CS production; 
the second step is just the application of a CF production 
if and only if the first step has determined the context 
where the CF production is applicable. These 
considerations allow us to say that: step 1 can be 
performed by the application ofa NOP rule using the NOP- 
special categories; in fact this kind of rule Is useful in 
detet~ining the context by defining a NOP rule with 
production: 
{ <NOP> I <NOP.-SE> I <NOP-ASE> } --> ~t, ~ bt2 
Step 2 can be performed by the application of an activated 
rule; in fact, wizen the rule at step 1 determines the 
context it cart activate an inactive rule with a production 
A--~13, indicating in the cMI to rule-activation the last 
node In the sequence ~. 
Now we can give the definition of contextual nile. 
We say that a rule is contextual if it is a NOP rule with 
production: 
{<NOP> I <NOP-SE> \[ <NOP-ASE> } -~ w z ... w 
and inside the augmentations there is a rule activation of 
,gJ~g_~t one inactive rule which has a production: 
A --> w k wk.~ ... w~, 1 <_k.<_m~n 
Ae VNu{<NOI~>,<NOP-SE>,<NOP-/LSE>} 
392 
where VN is the set of the non--terminal symbols of the 
grammar. 
This definition allows a nesting of contextual xnules: In thct 
an activated rule can be a contextual rule itself, In 
addition, we can activate more than one rule at a time; in 
this way we can access several contexts Inside a main 
context. 
We suggest a method to make possible asynchronous 
operations, i.e., how two independent rules can interact 
with each other in order to perform long distance 
operations. All this is based on the fact that we must be 
sure that a certain rule will be applied after mlother and 
the earlier rule wants to communicate some information 
to the other one, To this end we have adopted a 
communication meeharflsm, that we call message 
pa~alug, which Is not based on nmtehing as all the 
previously explained opexations, but on executing two 
basic tasks: sending and receiving, The sending task is 
firstly performed by the sending rule that sends a 
message to a receiving rule; afterwards the receiving rule 
must perlbrm the receiving task to receive the message, 
These two tasks are executed by the two rules at two 
independent thnes, i.e., when the rules are applied, In the 
following we denote the sending rule as Rs and the 
receiving rule as Rr, and we assume they are standard 
rules: so we denote with SN the node built by Rs mad with 
RN the node built by Pa °. 
We state two different approaches for what a ~is: 
1) the rules access a global feature structure where they 
store global features. Each role can access this structure 
and whatever feature value In It; 2) a Message-Box exists 
where a rule can send a message to another specified rule. 
"l~e Message-Box is accessible from every rule but the 
messages are accessible only by receiving rules. A 
message is composed as follows: a reference to the teature 
structure of SN: Rs makes avafiable its feature structure 
to Rr; a sequence of operations, possibly empty, that Rr 
~-o.ust execute. 
It Is not necessm3r that both these Items m'e present ina 
message, 
In the case of the global feature structure all the rules 
have access to It. We recall that all the feature structures 
Included Ill the nodes of the graph are local to their own 
node, Each rule earl store in or get from the global 
structure features that are global for the sentence: then 
the messages are feature structures and the same type of 
oIJerations allowed on the feature structures of the nodes 
of the graph Is possible on this sta~aetureo 
The Message-Box Is a structure referred to by all rules 
that want to send or receive messages. A rule Rs, building 
the node 8N. sends a message which is automatically 
inserted In the Message-Box specifying: Its name Rs, the 
receiving rule Rr, a reference to the feature structure of SN 
which is made available to Rr, a list of operations, possibly 
empty, to be perlbrmed by Rr. Until the messages are sent, 
they are the exclusive property of Rs. Wizen they are sent 
Rs loses Its property, rights, and only the rule Rr specified 
In the messages is authorized to get them. In addition, Rr 
finds In the message a reference to a feature structure ~md 
this structure is available only to It and always local to its 
own node. 
Message passing, In either of the two realizations, is a 
way to facilitate the tndlviduation and treatment of 
existing relations among phrases or parts of them. It is 
certainly flexible and not expensive because It avoids 
searches, i,e., matches, Inside the graph, and it can be a 
valid alternative to NOP rules that require a certain 
number of matches to find particular nodes In the graph. 
In fact, if there was not overlapping of the sub--trees rooted 
In SN and RN, thenwe can solve relations between SN and 
RN by applying a proper NOP rule, but, more efficiently, 
message passing allows us to avoid a certain 
computational overhead peribnning proper operations 
directly in Iks and Rx. 
When NOP rules are applied they act upon a structure 
already built. It Is also possible to activate i~ales that 
pertbl-m further building (contextual rules) and/or 
teaturing operations within a context. This process of 
activation can be nested many times inside a certain 
structure, This analysis per/orms a kind of operation that 
is virtually directed toward the bottom, in depth. If there 
was a partial or total overlapping between the sub-trees 
rooted In SN and RN, then - In this case .- when iLs sends 
a message;, assuraes that Rr will be applied above its node 
SN; in thkl way it Is possible to evaluate the consequences 
of certain operations on a structure which Is not yet but 
It could be butt. In this case we act toward the top of the 
parsing slxueture, through as many levels as we want, In 
contrast, using NOP rules, we only act on an existing 
structure representing deeper levels. 
So we can distinguish two ways of operation for long 
distance analysis araong phrases or parts of them: 
breadth ;malysls, using both NOP rules or message 
passing; depth analysis which can be top-down with NOP 
rules or bottom-up with message passing. 
The mechanism of the messages so described is 
performed through functions that can be used within the 
augmentations. 
6° TI-~ P,,~RSER 
Our parser is a CF-based one, derived from the ICA 
(inmledia~:e Constituent Analysis) algorithm described in 
/Gxishman 1976/, designed to run CGU rules, carrying 
out the syntactic and semantic analysis In parallel. It is 
a bottom-up algorithm, a~nd it performs left-toorlght 
scanning and reduction in an Immediate constituent 
analysis. The data structure It works on is a graph where 
all possible parse trees are connected. The complete parse 
h'ee(s) is (are) extracted from the graph in a subsequent 
step, Therefore, the parser Is also able to create structure 
fragment,~ for ill-formed sentences, thus returning, even 
in tills ca;~e, partial analyses. This Is particularly useful 
for diagnosis and debugghlg. 
Parsing te.rmination occurs In a natural way, when no 
more rule can be applied and the input string is 
completely scanned, 
Before entering the parser a preprocessor scans the 
sentence fi'om left to ~ght, performs the dictionary look- 
up tbr each form in the Input string, and returns a 
structure, tile preprocessed sentence, with the syntactic 
and semantic Information taken from the dictionary. 
The graph Is composed of nodes: the nodes can be 
either terminals or non-termln~s. Terminal nodes are 
built in co:a'espondence to a scanned form, whereas non- 
terminal ones arc built whenever a rule is applied, 
obviously the rule must not be a NOP rule. 
As stated above the parser is seen as a processor arid 
It sees the rules as processes, It handles a queue of 
w~ting processes/rules to be executed. When the parser 
takes a packet, for every rule it builds a process descriptor 
and Insexts it in the queue. We call such a process 
descriptor an application specification (AS), while the 
queue is c~dlcd the application specifications Hst (ASL), 
ASs are composed of: 
a node identifier, through this node the parser starts 
fl'ie ntatching; 
the nmne of the rule that the parser will apply; 
- only in the case of an AS of an activated rule this Item 
is the context where the nmned activated rule will be 
applied, l.e. the nodes that matched the right-hand side 
of the activating rule, otherwise this item is left empty. 
ASs in ASL are ordered depending upon the rule 
involved in an AS. In general, ff stm~dard active rules have 
to be executed, ASL is handled with a LIFO policy. If we 
consider the case of NOP rules° then these rules must be 
ordered before the others, since featm'e modifications 
they may produce can ser~e as input to other rules of the 
same packet, which are applied after them..4.n Inactive 
rule can be activated Just ibr one application by means of 
rule-activation traction: the activated rules must be 
applied immediately alter the end of the activating rule. So 
this kind of rules has the highest priority of execution with 
respect to NOP rules and s "tandard active rules. Then xalle- 
activation inserts an activation ~pect/tea~lo~ on the 
top of/KSL for the activated rule. Sunamarlzlng, the roles 
have the tbllowing decreasing priority order of execution: 
1) activated rules; 2) active NOP rules; 3) standard active 
rules, 
Once a node is created, be it terminal (in 
correspondence to a scarined tbrm) or non~terminal (in 
eon'espondence to a reduction), the parser inserts In the 
ASL an AS for every rule in the packet corresponding to 
the categoxy of the new created node: i.e. the new node Is 
tile one specified In every inserted AS, The parser 
performs all possible reductions building more than one 
node if possible, extracting one AS at a time before 
analyzing the next one. After ml AS ls extracted tom the 
ASL, the parser gets file specified rule: the first step is to 
match the right-hand side on the graph. The nodes 
matching a right-hand side are searched by the matcher: 
It returns one or more sets of these nodes, called 
reduction sets. For every reduction set, the application 
of the current rule is h-led. In this way we can connect 
together all possible parses for a sentence in a unique 
structure. Termination occurs when the ASL is e~.npty and 
the preprocessed string is completely scanned. 
Afterwards the parser returns the graph, kom which ~1 
parse trees satisi~ing the tbllowing conditions are 
extracted: a node covers the entire sentence and Its 
category Is the root symbol of the grmnmar. Here is the 
complete algorithm of the parser: 
* Until the end of tile sentence ts not reached: 
, Scan atorm: 
* Ill,lid a new ternmml xmde for the scanned tbxm; 
~ interpretation of the node: 
o g.~ the packet corresponding to Its categoi T and for every 
rule In the packet ~ tile AS In the ASL ; 
F_Qr~ AS in the ASL: 
* gt£ the first AS from the top of the ASL; 
* ggi the specified rule kl tile AS, it Is the current rule, and 
access to the node specified in the AS, it is tim emxent node; 
* starting from the cun~nt node perform tile match on the 
graph using tile production of the current rule; 
i_f at least one reduction set is found hlh.c_r_l: 
° F r_~K._C~YC,~t reduction set: 
- Apply the current rule; 
o If a new non-terminal node is butt ~ gtk the 
corresponding packet to its category and for every rule 
in it ~ the AS in the ASL; 
.¢g.~: o Apply recovery actions of the current rule; 
In this algorithm by match we mean the operation of 
searching the reduction sets and by 'apply the current 
rule' we mean the standard rule application starting from 
tile test checking as stated for the CGU model; particular 
ways of application, e,g, NOP rules, depend on the 
particular rule definition. 
7. AN EXAMPLE 
The example concerns a simple fragment of a LFG 
written in SAIL according to the CGU model, Our example 
is taken from/Kaplan 1982/and/Winograd 1983/. 
The lexical entries for this grammar in SAIL are the 
following: 
a {(Determiner NIL (Definiteness) (Indefinite) 
{Number) (singular))) 
baby ((Noun NIL (Number) (Singular) 
(Predicate) {Baby)}} 
girl {(Noun NIL {Number} (Singular} 
(Predicate) {Girl)l} 
handed ((Verb NIL (Tense) (Past) 
(Predicate) (Hand))) 
the ((Determiner NIL (Definiteness) {Definite))) 
toys ((Noun NIL (Number) (Plural} 
(Predicate) (Toys))) 
Rules in SAIL are written using a def~ttle format where 
all the fields appearing in the CGUs can be defined; in 
addition two fields are devoted to the state definition 
(STATUS field) and the rule type definition, that is ff the 
rule is a standard rule or a contextual or a NOP rule 
(CNTXTLORNOPR field). The rules are the following: 
(defrule NPRule ; NP --> Determiner Noun (STATUS active) 
(CNTXTLORNOPR NIL) 
(PRODUCTION (NP (Determiner Noun))) 
(SYN-TESTS T) 
(SEM-TESTS T) 
(SYN-ACTIONS 
(ralsef "(* DefiniteneSS Determiner) 
;raise the values of the specified features from the 
;son node into the parent node 
"(* * Noun)l}} 
; second * means all features of the son node 
;first * means the storing of the features as they are 
;in the son node into the parent node 
(defrule VPRule ; VP --> Verb NP NP (STATUS active) 
(CNTXTLORN OPR NIL) 
(PRODUCTION (Via (Verb NP NP))) 
(SYN-TESTS T) 
(SEM-TESTS T) 
(SYN-ACTIONS 
{raiser "(* * Verb) ;all features of the Verb node are 
;copied in the parent node 
((Object Definiteness) Definiteness NP) ;lst NP 
"((Object Number) Number NP) 
"((Object Predicate} Predicate NP) 
"((Object-2 Definiteness) Definiteness NP 2} ;2nd NP 
"((Object-2 Number} Number NP 2) 
"((Object-2 Predicate) Predicate NP 2)})) 
(defrule TOPRule ; S --->NP VP (STATUS active} 
(CNTXTLORNOPR NIL) 
(PRODUCTION (S (NP VP))) 
(SYN-TESTS T) 
(SEM-TESTS T) 
(SYN-ACTIONS 
{ralaef "({Subject Definiteness) Definiteness NP) 
"({Subject Number) Number NP) 
"{(Subject Predicate} Predicate NP) 
"{* * vP}}) 
\[SEM-ACTIONS 
{put-sem-val ;stores the EVALuation of the following 
;expression as the semantic value of the 
;parent node S 
39g 
(append (getf-pn "Predicate) 
{getf-pn "{Subject Predicatel} 
(getl-pn "(Object Predicate)) 
(getf-pn "(Object-2 Predicate)))))) 
; getf-pn gets feature values from the parent node 
The graph built by the parser applying these rules to the 
sentence 'a girl handed the baby the toys' is equivalent 
to the e-structure built by the corresponding LFG as 
shown in/Wlnograd 1983/. The top node S contains the 
following feature structure: 
" -Definiteness : Indefiniteq- 
Subject : Nmnber Singular | 
Predicate Girl ._! 
Object : \[ DefiniteneSSpredicateNUmber ::: BabySlngularDeftnite\] 
Object-2 : |F NumberDefiniteness : PluralDefinite \] 
L P~edicate Toys 
Terme : Past 
Predicate : Hand 
with the semantic value: (Hand Girl Baby Toys), 
Comparing the solution of the LFG version with the 
feature structure and the semantic value of the SAIL 
version we have that the LFG solution is equivalent to the 
above feature structure plus the semantic value. 
8. THE SAIL INTERFACING SYSTEM 
The SAIL Interfacing System (S.I.S.) is the framework 
where a user can interact with SAIL in developing NL 
applications. In fact SIS is organized in Interface Levels 
(I.L.s): in SIS we commonly speak of Interface Level 
Applications (I.L.A.s) which are the association of an IL 
with a grammar. 
If IL-Name is the name of an IL, and G-Name is the name 
of a grammar which defines a particular language 
through a dictionary and a set of CGU rules, then the pair 
<IL-Name, G-Name> defines an 1LA inside the SIS: this 
application is a task performed by that particular IL. 
In this way the development environment is based on 
different layers of rules, which are processed by the same 
parser and can handle the external Interface, the 
particular application, and any request issued by the 
user. In fact, the grammar of an ILA defines a language 
which can be used by the user for sending to the system 
his requests so that are caught by the parsing system and 
immediately satisfied. 
SIS is structured in 2 main ILs: the Kenael Interface 
Level (K.I.L.) and the Natural Language IL (N.L.I.L). 
When the system runs only two ILAs are active and 
available to the user: the KIL, associated to the Kernel 
Grammar (K.G.) and the Current Running Interface Level 
(C.R.I.L.). The KIL is always aetive because it is the core 
ILA of SIS and Its purpose Is to handle the overall system, 
so when the system Is started the user is introduced to the 
Kernel Interface Level. The Kernel Grammar is a semantic 
grammar associated with the KIL and defines a kernel 
language of commands and through them the user can 
use all the functionality of the system such as grammar 
building, parse checking, running other lI.As. 
When SAIL starts up, the KIL is also the CRIL, but when 
the user wants to load as CRIL another ILA defined In the 
system, for example a NLIL application, then a KIL 
command allows this and NLIL becomes the CRIL by 
loading a grammar associated to the NLIL: in this way the 
CRIL is updated to the new application and the loaded 
grammal becomes the current rumllng grammar. 
A subset of KIL commands defines a language through 
which the user can e~e the parsing structures 
generated by the parser for all the sentences input until 
that moment. This tool, named ANAPAR (ANAlysis of 
PARsing), is useful for the grammar and parse checking 
in deveh)ping NL applications, 
Finally, we want to point out that the particular structure 
given to ~IS enables the user to modify the front-end to 
SAIL by n mdifying the corresponding grammar of the KIL; 
in fact, all the files involved in their definition are 
accessible to the user who can modify those files as he 
wishes, or extend the language by introducing new 
gramma~ rules. 
CONCLUSIONS 
The example has shown the possibility of 
implementing different grammar formalisms into the 
frame of SAIL and also the searching of standard 
procedures for building grammars in the CGU model 
starting feom Categorial Grammars is planned, 
An experimental component has also been 
implemented, which performs some diagnosis of ill- 
formed input, and confirmed that the chosen parsing 
algorithm easily supports such a component. 
A fuU evaluation of some of the described mechanisms 
(such as message passing) has not been carried yet, as 
application to real linguistic cases has not been designed, 
but theoretically. 
However, a whole view of the system, and the 
described example show that SAIL is a valuable tool for 
the development of concrete grammars, even of large 
coverage. 
The whole system described in this paper is currently 
implemented in Common Lisp and runs on Sun and 
Orion wockstations. 
"ITils work has been carried out within the framework 
of the ESPRIT Project P527 CFID (Conmmnlcation 
Failure in Dialogue: Techniques for Detection and 
Repair). 
ACKNOWLEDGMENTS 
The author is thankful to Giaeomo Ferrari and Irlna 
Prodanof for their helpful support. The author is also 
grateful to Ronan Reilly who read the draft of the paper. 
References

/Aho 1972/Aho, A. E. and UIlman, J. D. (1972). The 
theory of parsing, translation and 
compiling. Vol I: Parsing. Prentice-Hall 
Inc. 

/Grishman 1976/Grishman, R. (1976). A survey of 
syntactic analysis procedures for natural 
language. AJCL, Microfiches 47, pp. 2-96. 

/Kaplan 1982/ Kaplan, R. and Bresnan, J. (1982). 
Lexical-Functional Grannnar: A Formal 
System for Grammatical Representation. In 
The Mental Representation of 
Grammatical Relations, Bresnan, J, Ed. 
Cambridge, MA: MIT Press, pp.173-281. 

/Marino 1987a/ Marino, M., Spiezio, A., Ferrari, G. and 
Prodanof, I. SAIL: a natural language 
interface for the building of and interacting 
with knowledge bases. In Proceedings of 
the 2nd International Conference on 
Artificial Intelligence: Methodology, 
Systems and Application9 (AIMSA '86)° 

Varna, Bulgaria, 1986, Jon'and, P. told 
Sgurev, V., Eds. North-Holland, 1987, pp. 
349-356. 

/Marlno 1987b/ Marino, M., Splezlo, A., Ferrari, G. and 
Prodanof, I. An efficient context-free parser 
for augmented phrase-structure grammars. 
In Proceedings of 1987 ACL Europe 
Conference, Copenhagen, Denmark, 1987. 

/Marino 1988/ Marino, M. {1988). The SAIL 
Interfacing System: a Framework for the 
Development of Natural Language 
Grannnars and Applications. Technical 
Report DL-NLP-1988-1, Department of 
Linguistics, University of Pisa, Italy. 

/Robinson 1980/Robinson, J., J, (1980). Interpreting 
natural-language utterances in dialogues 
about tasks. Teehn. Note 210, SRI 
International, Menlo Park, CA, 

/Robinson 1982/Robinson, J., J. (1982). DIAGRAIVI: A 
grammar for dialogues. CACM, 25, 1, pp. 27-47. 

/Winograd 1983/Winograd, T. (1983). Lauguage as a 
Cognitive Process. Vol. l: Syx~tax. 
Addison-Wesley. 
