\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}