grammar_def.rb

# grammar_def.rb - define the PowerLoom KIF grammar
#
# This file encodes the BNF description for Powerloom KIF into
# a hash of lists (of lists), as:
#
#   @grammar = { <name> => [ ... [ ... ] ], ... }
#
# The code in grammar_exp.rb expands this description into a
# set of reference data structures for performing recognition
# of KIF syntactic elements,
#
# Origins:
#
#   This file was adapted from Chapter 11 (PowerLoom Grammar)
#   of the PowerLoom manual (Version 1.40; 25 May 2006), with
#   amendments and extensions as needed to deal with current
#   example KIF.  Lines containing text taken from the manual
#   begin with the sequence "#M".
#
#   Basically, the text and BNF were turned into comments.  The
#   BNF was then transliterated into Ruby code.  Although the
#   result is a bit large, I think this integration will help
#   in comprehending the material, reducing errors, etc.
#
#
# Transliteration rules:
#
#   Note: Although PowerLoom's BNF uses braces "{...}"
#         (to mean "zero or more of these") and brackets
#         "[...]" (to mean "zero or one of these"),
#         parentheses stand for themselves.
#
#     <a>                      '<a>'         # abstract
#      a                       'a'           # concrete
#
#     <a>   b                  '<a>', 'b'    # sequence
#
#   ( <a>   b )         [ :LI, '<a>', 'b' ]  # list
#
#     <a> | b           [ :OR, '<a>', 'b' ]  # this or that
#   { <a> | b }         [ :ZM, '<a>', 'b' ]  # { embedded }
#
#   [ <a> ]             [ :ZO, '<a>'      ]  # zero or one
#
#     <a>*              [ :ZM, '<a>'      ]  # zero or more
#
#     <a>+              [ :OM, '<a>'      ]  # one  or more
#
# Note: The :LI tag is added automagically as the default, so
#       it doesn't need to be included in the source code.  


#M  11 PowerLoom Grammar 
#M
#M  The syntax of PowerLoom is described below using a modified
#M  BNF notation adapted from the KIF specification. 
#M
#M  11.1 Alphabet 
#M
#M  We distinguish between terminals, which are part of the
#M  language, and nonterminals.  All nonterminals are bracketed
#M  as follows <nonterminal>.  Squared brackets means zero or
#M  one instances of the enclosed expression; <nonterminal>*
#M  means zero or more occurrences and <nonterminal>+ means one
#M  or more occurrences of <nonterminal>.  The notation 
#M  <nonterminal1> - <nonterminal2> refers to all of the members
#M  of <nonterminal1> except for those in <nonterminal2>. 
#M  A word is a contiguous sequence of characters, which include
#M  all upper case letters, lower case letters, digits and alpha
#M  characters (ASCII character set from 93 to 128) excluding
#M  some special characters like white spaces, single and double
#M  quotes and brackets.
#M
#M    <word>   ::= a primitive syntactic object 
#M
#M  Special words are those who refer to a variable.  All
#M  variables are preceded by a question mark. 
#M
#M    <indvar> ::= a word beginning with the character ? 
#M
#M  A string <string> is a character sequence including words
#M  plus all special charcters (except double quotes) enclosed
#M  in double quotes. A double quote can be included in a string
#M  if it is preceeded by the escape character '\'.


# Transliterate the BNF into a Ruby data structure.  

#M  11.2 Grammar

# Define a few helper variables.

doc = ':documentation'
exi = 'exists'
frl = 'forall'
key = '<keyword-option>'
sen = '<sentence>'
str = '<string>'
var = '<vardecl>'

@grammar = {


#M  <form>       ::=         <statement> |
#M                           <definition> 

   '<form>'      =>  [ :OR, '<statement>',
                            '<definition>' ],


#M  11.2.1 Constants and Typed Variables
#M
#M  The language consists of several groups of operators,
#M  defined as follows:
#M 
#M  <termop>     ::=          listof        |
#M                            setof         |
#M                            the           |
#M                            setofall      |
#M                            kappa 

   '<termop>'    =>  [ :OR,  'listof',
                             'setof',
                             'the',
                             'setofall',
                             'kappa' ],


#M  <sentop>     ::=          =              |
#M                            /=             |
#M                            not            |
#M                            and            |
#M                            or             |
#M                            forall         |
#M                            exists         |
#M                            <=             |
#M                            =>             |
#M                            <=>            |
#M                            <<=            |
#M                            =>>            |
#M                            <~             |
#M                            ~>             |
#M                            <<~            |
#M                            ~>> 

   '<sentop>'    =>  [ :OR,  '=',
                             '/=',
                             'not',
                             'and',
                             'or',
                             frl,
                             exi,
                             '<=',
                             '=>',
                             '<=>',
                             '<<=',
                             '=>>',
                             '<~',
                             '~>',
                             '<<~',
                             '~>>'  ],


#M  <defop>      ::=          defconcept     |
#M                            deffunction    |
#M                            defrelation    |
#M                            defrule        | 
#M                            :documentation |
#M                            :->            |
#M                            :<=            |
#M                            :=>            |
#M                            :<<=           |
#M                            :=>>           |            
#M                            :<=>           |
#M                            :<=>>          |
#M                            :<<=>          |
#M                            :<<=>>         |
#M                            :=             |
#M                            :axioms 

   '<defop>'     =>  [ :OR,  'defconcept',
                             'deffunction',
                             'defrelation',
                             'defrule',
                             doc,
                             ':->',
                             ':<=',
                             ':=>',
                             ':<<=',
                             ':=>>',
                             ':<=>',
                             ':<=>>',
                             ':<<=>',
                             ':<<=>>',
                             ':=',
                             ':axioms' ],


#M  <operator>   ::=          <termop> |
#M                            <sentop> |
#M                            <defop> 

  '<operator>'   =>  [ :OR,  '<termop>',
                             '<sentop>',
                             '<defop>' ],


#M  All other words are constants
#M  (words which are not operators or variables):
#M 
#M  <constant>    ::=  <word> - <indvar> - <operator>
#M
#M   So, if it's a <word>, and it's neither an <indvar>
#M   nor an <operator>, it must be a <constant>.
#M 
#M  Semantically, there are different categories of constants:
#M
#M    Concept  constants   <conceptconst>
#M    Function constants   <funconst>
#M    Relation constants   <relconst>
#M    Rule     constants   <ruleconst>
#M    Logical  constants   <logconst>
#M
#M  The differences between these categories are entirely semantic.
#M  However, some operators will only accept specific constants.
#M
#M  In contrast to the specification of KIF3.0, PowerLoom supports
#M  a typed syntax. Therefore, variables in quantified terms and
#M  sentences can appear either typed or untyped, as follows: 
#M
#M  <vardecl>     ::=         (  <indvar>    <constant> ) |
#M                               <indvar>

   '<vardecl>'    =>  [ :OR,  [ '<indvar>', '<constant>' ],
                                '<indvar>' ],


#M  11.2.2 Terms 
#M
#M  Terms are used to denote objects in the world being described: 
#M 
#M  <term>        ::=           <indvar>   |
#M                              <constant> |
#M                              <funterm>  |
#M                              <listterm> |
#M                              <setterm>  |
#M                              <quanterm>

   '<term>'       =>  [ :OR,   '<indvar>',
                               '<constant>',
                               '<funterm>',
                               '<listterm>',
                               '<setterm>',
                               '<quanterm>' ],


#M  <listterm>    ::=      ( listof                <term>* )

   '<listterm>'   =>       [ 'listof',     [ :ZM, '<term>' ] ],


#M  <setterm>     ::=      ( setof                 <term>* )
  
   '<setterm>'    =>       [ 'setof',      [ :ZM, '<term>' ] ],


#M  <funterm>     ::=      ( <funconst>            <term>+ )

   '<funterm>'    =>       [ '<funconst>', [ :OM, '<term>' ] ],

#M  Note: Zero arguments are allowed for <funterm> in KIF3.0: <term>* 
#M
#M  <quanterm>    ::=
#M     ( the        <vardecl>                    <sentence> ) | 
#M     ( setofall   <vardecl>                    <sentence> ) | 
#M     ( kappa    { <vardecl> | ( <vardecl>+ ) } <sentence> ) | 
#M     ( lambda   { <vardecl> | ( <vardecl>+ ) } <term>     )

   '<quanterm>'   =>
     [ :OR, [ 'the',               var,     sen      ],
            [ 'setofall',          var,     sen      ],
            [ 'kappa',             var,     sen      ],
            [ 'kappa',    [ [ :OM, var ] ], sen      ],
            [ 'lambda',            var,     '<term>' ],
            [ 'lambda',   [ [ :OM, var ] ], '<term>' ] ],

#M  Note: KIF3.0 allows <term> instead of <vardecl> for setofall.
#M  No <quanterm> as well as no <setterm> in core of KIF as a result
#M  of decision 95-3 (March 1995). 


#M  11.2.3 Sentences 
#M
#M  Sentences are used to express propositions about the world: 
#M 
#M  <sentence>    ::=          <constant>    |
#M                             <equation>    |
#M                             <inequality>  | 
#M                             <relsent>     |
#M                             <logsent>     |
#M                             <quantsent>

   '<sentence>'   =>   [ :OR, '<constant>',
                              '<equation>',
                              '<inequality>',
                              '<relsent>',
                              '<logsent>',
                              '<quantsent>' ],


#M  <equation>    ::=  (  =     <term>    <term>  )

   '<equation>'   =>   [ '=',  '<term>', '<term>' ],


#M  <inequality>  ::=  ( /=     <term>    <term>  )
 
   '<inequality>' =>   [ '/=', '<term>', '<term>' ],


#M  <relsent>     ::=  (  <constant>          <term>+   )

   '<relsent>'    =>   [ '<constant>', [ :OM, '<term>' ]  ],

#M  Note: Zero arguments allowed in KIF3.0 for <relsent> (<term>*).
#M  <funconst> is currently not allowed in PowerLoom
#M  (use (= <funterm> <term>) instead). 
#M
#M  <logsent>    ::=
#M           ( not     <sentence>                   ) | 
#M           ( and     <sentence>*                  ) | 
#M           ( or      <sentence>*                  ) | 
#M           ( =>      <sentence>*    <sentence>    ) |
#M           ( =>>     <sentence>*    <sentence>    ) | 
#M           ( <=      <sentence>     <sentence>*   ) |
#M           ( <<=     <sentence>     <sentence>*   ) |
#M           ( ~>      <sentence>*    <sentence>    ) |
#M           ( ~>>     <sentence>*    <sentence>    ) | 
#M           ( <~      <sentence>     <sentence>*   ) |
#M           ( <<~     <sentence>     <sentence>*   ) 

# Q: Can any of these have _no_ arguments?

# Q: Why not "<sentence>+" instead of
#            "<sentence>* <sentence>", etc ???

  '<logsent>'   =>
    [ :OR, [ 'not',         sen   ],
           [ 'and',  [ :OM, sen ] ],
           [ 'or',   [ :OM, sen ] ],
           [ '=>',   [ :OM, sen ] ],
           [ '=>>',  [ :OM, sen ] ],
           [ '<=',   [ :OM, sen ] ],
           [ '<<=',  [ :OM, sen ] ],
           [ '~>',   [ :OM, sen ] ],
           [ '~>>',  [ :OM, sen ] ],
           [ '<~',   [ :OM, sen ] ],
           [ '<<~',  [ :OM, sen ] ] ],


#M  <quantsent> ::=
#M    (forall { <vardecl> | ( <vardecl>+ ) } <sentence>            ) | 
#M    (forall { <vardecl> | ( <vardecl>+ ) } <sentence> <sentence> ) | 
#M    (exists { <vardecl> | ( <vardecl>+ ) } <sentence>            )

# Q: Why not "<vardecl>*" instead of
#            "{ <vardecl> | ( <vardecl>+ ) }"

  '<quantsent>' =>
    [ :OR, [ frl, [ :ZM, var ], sen      ],
           [ frl, [ :ZM, var ], sen, sen ],
           [ exi, [ :ZM, var ], sen      ] ],



#M  11.2.4 Definitions 
#M
#M  PowerLoom supports two distinct categories of definitions --
#M  relation definitions (including concept and function
#M  definitions) and rule definitions.  A relation definition
#M  introduces a new logical constant, and states some facts about
#M  that constant (e.g., who its parents are in a subsumption
#M  taxonomy).  A rule definition binds a new constant to a
#M  proposition (so that the constant denotes the proposition) and
#M  asserts the truth of that proposition.  Usually, the
#M  proposition asserted by a defrule is an implication.  The
#M  assertional truth of a proposition defined by a rule can be
#M  altered by asserting or retracting the constant that denotes
#M  the proposition. 
#M 
#M  <keyword-option>   ::=    <keyword>    <word> 

  '<keyword-option>'  =>  [ '<keyword>', '<word>' ],


#M  <definition>       ::=         <reldefinition>  |
#M                                 <objdefinition>  |
#M                                 <ruledefinition>

  '<definition>'      =>  [ :OR, '<reldefinition>',
                                 '<objdefinition>',
                                 '<ruledefinition>' ], 


#M  <reldefinition> ::= 
#M    ( defconcept <conceptconst> <vardecl> 
#M      [ :documentation <string>        ]
#M      [ :<=            <sentence>      ] |
#M      [ :=>            <sentence>      ] | 
#M      [ :<<=           <sentence>      ] |
#M      [ :=>>           <sentence>      ] | 
#M      [ :<=>           <sentence>      ] |
#M      [ :<=>>          <sentence>      ] |
#M      [ :<<=>          <sentence>      ] | 
#M      [ :<<=>>         <sentence>      ] | 
#M      [ :axioms        { <sentence> | ( <sentence>+ ) } ]
#M      [ <keyword-option>* ]
#M    ) | 
#M    ( deffunction <funconst> ( <vardecl>+ ) 
#M      [ :documentation <string>        ]
#M      [ :->            <vardecl>       ] |
#M      [ :<=            <sentence>      ] |
#M      [ :=>            <sentence>      ] | 
#M      [ :<<=           <sentence>      ] |
#M      [ :=>>           <sentence>      ] | 
#M      [ :<=>           <sentence>      ] |
#M      [ :<=>>          <sentence>      ] |
#M      [ :<<=>          <sentence>      ] | 
#M      [ :<<=>>         <sentence>      ] | 
#M      [ :axioms        { <sentence> | ( <sentence>+ ) } ] 
#M      [ <keyword-option>* ]
#M    ) | 
#M    ( defrelation <relconst> ( <vardecl>+ ) 
#M      [ :documentation <string>        ]
#M      [ :<=            <sentence>      ] |
#M      [ :=>            <sentence>      ] | 
#M      [ :<<=           <sentence>      ] |
#M      [ :=>>           <sentence>      ] | 
#M      [ :<=>           <sentence>      ] |
#M      [ :<=>>          <sentence>      ] |
#M      [ :<<=>          <sentence>      ] | 
#M      [ :<<=>>         <sentence>      ] |
#M      [ :axioms        { <sentence> | ( <sentence>+ ) } ]
#M      [ <keyword-option>* ]
#M    ) 

# Q: Can :axioms have _no_ arguments?

  '<reldefinition>'  =>
    [ :OR, [ '<defconcept>',
             '<conceptconst>',
             var,
             [ :ZO, [ doc,               str   ] ],
             [ :OR, [ ':<=',             sen   ],
                    [ ':=>',             sen   ],
                    [ ':<<=',            sen   ],
                    [ ':=>>',            sen   ],
                    [ ':<=>',            sen   ],
                    [ ':<=>>',           sen   ],
                    [ ':<<=>',           sen   ],
                    [ ':<<=>>',          sen   ],
                    [ ':axioms', [ :ZM,  sen ] ],
                    [            [ :ZM,  key ] ] ] ],
           [ '<deffunction>',
             '<funconst>',
             [ :OM, var ],
             [ :ZO, [ doc,               str   ] ],
             [ :OR, [ ':->',             var   ],
                    [ ':=>',             sen   ],
                    [ ':<=',             sen   ],
                    [ ':<<=',            sen   ],
                    [ ':=>>',            sen   ],
                    [ ':<=>',            sen   ],
                    [ ':<=>>',           sen   ],
                    [ ':<<=>',           sen   ],
                    [ ':<<=>>',          sen   ],
                    [ ':axioms', [ :ZM,  sen ] ],
                    [            [ :ZM,  key ] ] ] ],
           [ '<defrelation>',
             '<relconst>',
             [ :OM, var ],
             [ :ZO, [ doc,               str   ] ],
             [ :OR, [ ':<=',             sen   ],
                    [ ':=>',             sen   ],
                    [ ':<<=',            sen   ],
                    [ ':=>>',            sen   ],
                    [ ':<=>',            sen   ],
                    [ ':<=>>',           sen   ],
                    [ ':<<=>',           sen   ],
                    [ ':<<=>>',          sen   ],
                    [ ':axioms', [ :ZM,  sen ] ],
                    [            [ :ZM,  key ] ] ] ] ],


#M  <objdefinition> ::=
#M    ( defobject
#M      <constant> 
#M      [ :documentation <string> ] 
#M      [ <keyword-option>*       ] ) 

  '<objdefinition>' =>
    [ 'defobject',
      '<constant>',
      [ :ZO, [ doc, str ] ],
      [ :ZM, key      ] ],


#M  <ruledefinition> ::=
#M   ( defrule <constant> <sentence> 
#M     [ :documentation <string> ] 
#M     [ <keyword-option>*       ] ) 

  '<ruledefinition>' => 
    [ 'defrule',
      '<constant>',
      sen,
      [ :ZO, [ doc, str ] ],
      [ :ZM, key      ] ] 
}

1


This wiki page is maintained by Rich Morin, an independent consultant specializing in software design, development, and documentation. Please feel free to email comments, inquiries, suggestions, etc!

Topic revision: r1 - 05 Jul 2008, RichMorin
This site is powered by Foswiki Copyright © by the contributing authors. All material on this wiki is the property of the contributing authors.
Foswiki version v2.1.6, Release Foswiki-2.1.6, Plugin API version 2.4
Ideas, requests, problems regarding CFCL Wiki? Send us email