CGIF Syntax

Following are the syntax rules for the Conceptual Graph Interchage Format (CGIF), as defined in Annex B of the ISO/IEC 24707 standard for Common Logic. For the semantics, see the rules in Section B.3 of the standard, which define CGIF by a translation of each construct to the abstract syntax of Common Logic.

1. Lexical rules

The syntax rules are written in Extended Backus-Naur Form (EBNF) rules, as specified by ISO/IEC 14977. For each CGIF syntax rule, the lexical categories of Section A.2.2 of ISO/IEC 24707 shall be assumed. In Section A.2.3.2, the category name includes a category enclosedname of strings enclosed in quotes and a category namesequence of strings that are not enclosed. To avoid possible ambiguities, the category CGname requires that all CLIF name sequences except those in the CGIF category identifier shall be enclosed in quotes:

   CGname  =  identifier | '"', (namesequence - identifier), '"'
            | numeral | enclosedname | quotedstring;
   identifier  =  letter, {letter | digit | "_"};

When CGIF is translated to CL, any CGname shall be translated to a CLIF name by removing any quotes around a name sequence. CLIF does not make a syntactic distinction between constants and variables, but in CGIF any CGname that is not used as a defining label or a bound label shall be called a constant.

The start symbol for CGIF syntax shall be the category text, if the input is a complete text, or the category CG, if the input is a string that represents a conceptual graph.

2. Core CGIF Syntax

An actor is a conceptual relation that represents a function in Common Logic. It begins with (, an optional comment, an optional string #?, a CG name, |, an arc, an optional end comment, and ). If the CG name is preceded by #?, it represents a bound coreference label; otherwise, it represents a type label. The arc sequence represents the arguments of the CL function and the last arc represents the value of the function.

   actor  =  "(", [comment], ["#", "?"], CGname, arcSequence, "|", arc,
                  [endComment], ")";

An arc is an optional comment followed by a reference. It links an actor or a conceptual relation to a concept that represents one argument of a CL function or relation.

   arc  =  [comment], reference;

An arc sequence is a sequence of zero or more arcs, followed by an option consisting of an optional comment, ?, and a sequence name.

   arcSequence  =  {arc}, [[comment], "?", seqname];

A comment or an end comment is a character string that has no effect on the semantics of a conceptual graph or any part of a conceptual graph. A comment begins with "/*", followed by a character string that contains no occurrence of "*/", and ends with "*/". A comment may occur immediately after the opening bracket of any concept, immediately after the opening parenthesis of any actor or conceptual relation, immediately before any arc, or intermixed with the concepts and conceptual relations of any conceptual graph. An end comment begins with ;, followed by a character string that contains no occurrence of ] or ). An end comment may occur immediately before the closing bracket of any concept or immediately before the closing parenthesis of any actor or conceptual relation.

   comment = "/*", {(character-"*") | ["*", (character-"/")]}, ["*"], "*/";

   endComment  =  ";", {character - ("]" | ")")};

A concept is either a context, an existential concept, or a coreference concept. Every concept begins with [ and an optional comment; and every concept ends with an optional end comment and ]. Between the beginning and end, a context contains a CG; an existential concept contains * and either a CG name or a sequence name; and a coreference concept contains : and a sequence of one or more references. A context that contains a blank CG is said to be empty, even if it contains one or more comments; any comment that occurs immediately after the opening bracket shall be part of the concept, not the following CG.

   concept  =  "[", [comment],
                (CG | "*", (CGname | seqname) | ":", {reference}- ),
                [endComment], "]";

A conceptual graph (CG) is an unordered set of concepts, conceptual relations, negations, and comments.

   CG  =  {concept | conceptualRelation | negation | comment};

A conceptual relation is either an ordinary relation or an actor. An ordinary relation, which represents a CL relation, begins with (, an optional comment, an optional string #?, a CG name, an optional end comment, and ). If the CG name is preceded by #?, it represents a bound coreference label; otherwise, it represents a type label. An ordinary relation has just one sequence of arcs, but an actor has two sequences of arcs.

   conceptualRelation  =  ordinaryRelation | actor;

   ordinaryRelation  =  "(", [comment], ["#", "?"], CGname, arcSequence,
                             [endComment], ")";

A negation is ~ followed by a context.

   negation  =  "~", context;

A reference is an optional ? followed by a CG name. A CG name prefixed with ? is called a bound coreference label; without the prefix ?, it is called a name.

   reference  =  ["?"], CGname;

A text is a context, called an outermost context, that has an optional name, has an arbitrarily large conceptual graph, and is not nested inside any other context. It consists of [, an optional comment, the type label Proposition, :, an optional CG name, a conceptual graph, an optional end comment, and ]. Although a text may contain core CGIF, the type label Proposition is outside the syntax of core CGIF.

   text  =  "[", [comment], "Proposition", ":", [CGname], CG,
                 [endComment], "]";

3. Extended CGIF Syntax

Extended CGIF is superset of core CGIF, and every syntactically correct sentence of core CGIF is also syntactically correct in extended CGIF. Its most prominent feature is the option of a type label or a type expression on the left side of any concept. In addition to types, extended CGIF adds the following features to core CGIF:

More options in concepts, including universal quantifiers.
Boolean contexts for representing the operators or, if, and iff.
The option of allowing concept nodes to be placed in the arc sequence of conceptual relations.
The ability to import text into a text.

These extensions are designed to make sentences more concise, more readable, and more suitable as a target language for translations from natural languages and from other CL dialects, including CLIF. None of them, however, extend the expressive power of CGIF beyond the CG core, since the semantics of every extended feature is defined by its translation to core CGIF, whose semantics is defined by its translation to the abstract syntax of Common Logic. Exended

The following grammar rules of extended CGIF have the same definitions as the core CGIF rules of the same name: arcSequence, CG, conceptualRelation, negation, ordinaryRelation, text. The following grammar rules of extended CGIF don't occur in core CGIF, or they have more options than the corresponding rules of core CGIF: actor, arc, boolean, concept, eitherOr, equivalence, ifThen, arcSequence, arcSequence, arcSequence, typeExpression. Although some rules, such as CG, may be identical in form, extended CGIF is defined in terms of subcategories that have more options; therefore, the CGs of extended CGIF have many more options than CGs in core CGIF.

An actor in extended CGIF has the option of zero or more arcs following | instead of just one arc.

   actor  =  "(", [comment], ["#", "?"], CGname,
             arcSequence, "|", {arc}, [endComment], ")";

An arc is

   arc = [comment], (reference | "*", CGname | concept);

A boolean is either a negation or a combination of negations that represent an either-or construction, an if-then construction, or an equivalence. Instead of being marked with ~, the additional negations are represented as contexts with the type labels Either, Or, If, Then, Equiv, Equivalence, or Iff.

   boolean  =  negation | eitherOr | ifThen | equivalence;

An either-or is a negation with a type label Either that contains zero or more negations with a type label Or.

   eitherOr = "[", [comment], "Either", [":"],
                   {"[", [comment], "Or", [":"], CG, [endComment], "]"}
                   [endComment], "]";

An if-then is a negation with a type label If that contains a negation with a type label Then.

   ifThen  =  "[", [comment], "If", [":"], CG,
                   "[", [comment], "Then", [":"], CG, [endComment], "]",
                   [endComment], "]";

An equivalence is a context with a type label Equivalence or Equiv that contains two contexts with a type label Iff. It is defined as a pair of if-then constructions, each with one of the iff-contexts as antecedent and the other as consequent.

   equivalence = "[", [comment], ("Equivalence" | "Equiv"), [":"],
                     "[", [comment], "Iff", [":"], CG, [endComment], "]",
                     "[", [comment], "Iff", [":"], CG, [endComment], "]",
                      [endComment], "]";

A concept is

   concept = "[", [comment],
           ( (typeExpression, ":"
             | ["#", ("?", CGname) | CGname], [":"]),
             [["@every"], "*", CGname], {reference}, [CG]
           | ["@every"], "*", seqname
           ), [endComment], "]";

Four options are permitted in the type field: a type expression tx, a bound coreference label prefixed with "#", a constant, or the empty string; a colon is required after tx, but optional after the other three. The rewrite rules move features from the concept c to four strings, which are concatenated to form the conceptual graph g: g1 is an existential concept with the defining label from c or with a label generated by gensym() if no defining label or reference occurs in c; g2 is a coreference concept if any references occur in c; g3 is either a conceptual relation with a type label ty or a conceptual graph generated from a type expression tx; and g4 is a context containing any nonblank CG x. Any comments cm and ecm are placed in the first nonblank concept, which shall be either g1 or g2.

A conceptual graph (CG) is

   CG  =  {concept | conceptualRelation | boolean | comment};

A conceptual relation is

   conceptualRelation = ordinaryRelation | actor;

   ordinaryRelation  =  "(", [comment], (["#", "?"], CGname),
                        arcSequence, [endComment], ")";

The first line of the rewrite rule extracts a conceptual graph from the arc sequence s. The second line adds the opening comment, type label, and arc sequence of a conceptual relation. The third line adds the sequence name, if any, the end comment, and the closing parenthesis of the conceptual relation.

As an example, the conceptual relation (On [Cat: Yojo] [Mat]) would be translated by the rules for conceptual relations, arcs, arc sequences, and concepts to generate a conceptual graph, such as the following, expressed in core CGIF:

   [: Yojo] (Cat Yojo) [*g00719] (Mat ?g00719) (On Yojo ?g00719)

The CGname g00719 would be generated by the function gensym().

A text is

   text = "[", [comment], "Proposition", ":", [CGname],
          CG, [endComment], "]";

A type expression is

   typeExpression  =  "@", "*", CGname, CG;

If a concept c contains a type expression, the rewrite rules that specify concept(c) use the function for every occurrence of b in g.

A type expression corresponds to a lambda expression in which the CG name n specifies the formal parameter, and the conceptual graph g is the body of the expression. If a concept c contains a type expression, the transformation rules that process c shall substitute a reference derived from c for every occurrence of the bound label ?n that occurs in g.