\documentclass[12pt, a4paper]{article}


\usepackage{hthtml}
\usepackage[dvips]{graphicx}

% === title
\title{KIF parser \\ draft\footnote{This document is under
    development as we are moving the documentation from December 1998
    to the current status of the project. Some bits still refer to the 
    old parser. This is now just short reference for the nzdis-kif
    module with KIF parser version 1.0} \\ 
  {\small (Document $Revision: 1.1 $)}}  

\author{NZDIS Team \\
  \htmailto{nzdis@waitaki.otago.ac.nz}}


% === document
\begin{document}
\maketitle


% ---- Table Of Contents
\tableofcontents


% === Introduction
\section{Introduction}

This document describes general features and ideas of the KIF parsing
engine, called nzdis-kif, or just KIF parser, version 1.0 (first
public release). 

{\bf Why \\} There was no KIF 3.0 or ``almost-full'' KIF 3.0 parser
available for Java at the time of writing it.  The existing one, Java
Kif Parser developed by X.Luan ({\it http://www.cs.umbc.edu/agents/kse/kif/jkp/ \/}) 
supported only Horn-Clause-Based logical inference. The general
purpose of this tool is to provide ``almost full'' support for KIF
parsing. All for Java programmers and developers.  This tool can be
successfully applied to number of projects. The very first version of KIF
parser was based on the KIF 3.0 specification. Current, nzdis-kif 1.0
is based on Knowledge Interchange Format (KIF) draft proposed American
National `Standard (dpANS KIF)  NCITS.T2/98-004.  We are aware, that
during the time span between the first parser and this release there
is possibly many more KIF parsers, however, this is the only one based 
completely on open source, object-oriented and Java-only based tools. 

{\bf How \\} The parser was implemented from the scratch. The grammar
was rewritten to match LALR(1), and the tool being used to generate the 
parser is SableCC Java-based, object-oriented compiler compiler.

{\bf More info \\} The reader can get more information about KIF itself from:
\begin{htdescription}
\item [\htlink{KIF 3.0 manual}{http://marni.otago.ac.nz/rep/DIST/specs/kif-html-doc/HTML/kif-manual.html}] This is a specification together with manual of KIF version 3.0 

\item [\htlink{KIF draft proposed to
    ANS}{http://marni.otago.ac.nz/rep/DIST/specs/kif-html-doc/dpans.html}] Knowledge Interchange Format - draft proposed American National Standards (dpANS) NCITS.T2/98-004 

\item [API of the \htlink{jkp package}{http://marni.otago.ac.nz/rep/DIST/kif-jkp/jkp/doc/packages.html}] This is a Java Kif Parser for sKIF (subset of KIF) based on Horn-Clause-Based logical inference
\end{htdescription}

% ==========================
\section{KIF parser}

\subsection{Grammar details}

The KIFparser object is basically the ANSI KIF draft parser with one
feature missing in the current version, namely character blocks.
Character blocks are not supported at all.

Apart from character blocks, the specification is fully supported in
the current release of nzdis-kif module.

\subsection{Grammar info}

The grammar is full KIF grammar rewritten to be LALR(1), and as such
can be used to generate very fast parsers. With LALR(1) the complexity 
of parsing the sentences is in linear relation to the size of the
input. The grammar is expressed in EBNF notation, with some additional 
keywords to meet SableCC input file requirements.

 base = {knowledge} form*;

 form = {sentence} sentence  | 
        {definition} definition ;

 sentence = {constant} constant |
            {equation} equation |
            {inequality} inequality |
            {relsent} relsent |
            {logsent} logsent |
            {quantsent} quantsent ;

All the KIF nodes are represented as objects, and object-oriented
switch (walker) can be applied to the generated Abstract Syntax Tree. 
For full list of nodes and classes please refer to the javadoc API.

\subsubsection*{KnowledgeBase}
This is the main node. 
This node represents the whole knowledge base unit, containing
set of sentences. It is important to notice, that in KIF unit is built
by set (not sequence) of sentences. The parser invoked with this
method should process several following sentences, and built
appropriate tree, with this as a root node.

\subsubsection*{SentenceForm}
This Java class represents sentence node of KIF grammar. The Sentence
is composed of different types of sentences, like:
EquationSentence, InequalitySentence, RelsentSentence,
LogsentSentence, etc. 

\subsubsection*{DefinitionForm}
This class represents definition sentences. For full list of nodes and
classes please refer to the javadoc API. 



% =====================
\section{User guide}

% -----------
\subsection{Trivial pretty printing}

When using the parser there is sometimes useful to print on the screen 
how the AST in fact looks like after parsing. One can do it using
utility classes provided with the parser itself.

As a simple example of processing of the parsing tree produced by
nzdis-kif parser there is implemented a PrintTree class. 

So for example parsing the KIF structure like (which can be treated as
query expressed in KIF:
\begin{verbatim}
(and
 (package ?x)
 (= (name ?x) "imap")
 (= (version ?x) 4.1)
 (= (type ?x) "sources")
)
\end{verbatim}
will produce a tree structure like:
\begin{verbatim}
  AKnowledgeBase
    ASentenceForm
      ALogsentSentence
        AConjunctionLogsent
          ARelsentSentence
            AImplicitRelsent
              AConstant
                AWordIdentifier
              AIndvarTerm
                AIndvar
          AEquationSentence
            AEquestion
              AFuntermTerm
                AImplicitFunterm
                  AConstant
                    AWordIdentifier
                  AIndvarTerm
                    AIndvar
              AStringTerm
          AEquationSentence
            AEquestion
              AFuntermTerm
                AImplicitFunterm
                  AConstant
                    AWordIdentifier
                  AIndvarTerm
                    AIndvar
              AConstantTerm
                AConstant
                  AWordIdentifier
          AEquationSentence
            AEquestion
              AFuntermTerm
                AImplicitFunterm
                  AConstant
                    AWordIdentifier
                  AIndvarTerm
                    AIndvar
              AStringTerm
\end{verbatim}

If one has the KIF source in a file called query.kif one can produce
this AST printout using the call:
\begin{verbatim}
 java nzdis.lang.kif.app.PrintTree query.kif
\end{verbatim}
assuming that nzdis-kif.jar is in the CLASSPATH.

\subsection{Traversing the tree}

Parser sequentially takes token by token from the KIF input stream,
and creates appropriate nodes which represents KIF {\bf words}.  Those
nodes are then placed in the appropriate places of the parsing tree.
Once the tree is successfully created,  one can do different
processing of this tree via appropriate traversing utilities.

The developer can simply extend 
nzdis.lang.kif.analysis.DepthFirstAdapter and apply this ``walker'' to 
the AST node nzdis.lang.kif.node.Node. This follows simply the
object-oriented switch pattern (visitor pattern), and the user should
have no problem using it.

% =====================
\section{Pattern matching}

Documentation is under development. 


% ----
\end{document}
