kremer@cpsc.ucalgary.ca
robertof@cpsc.ucalgary.ca
The BNF given here isn't an LL1 grammar, but its reasonably close,
and is very easy to parse. The fact the MIME headers may have
parts that we don't understand (and should therefore ignore) is
what makes the grammar non-LL1. Using a line-based parser solves
the problem. The two sub-grammars can also be parsed easily using
a line-based parser.
The storage language is intended to be extended multi-part MIME
format. This allows several versions of the the application to
read the parts that they can understand. For example, a single
Constraint Graph file contains a part for the concept map (the
visual interface) and a second part for the constraint graph data
itself. A KSIMapper program cannot understand the second (constraint
graph) part, but it can understand the first part, so can at least
display it. The KSIMapper program should not, however, write it
back, since it does not understand what dependencies might be
violated by changing the CMap part. In general, the header follows
standard multipart MIME format, according to RFC 1521.
An abbreviated, but typical, BNF is given here.
Overall storage language, version 0.1
| MIMEfile | ::= | MIMEheader CRLF MIMEmultipartbody |
| MIMEheader | ::= | MIMEversion discardHeaderLine* MIMEcontentType discardHeaderLine* |
| discardHeaderLine | ::= | printable-char+ CRLF |
| MIMEversion | ::= | "MIME-Version" ":" Version discardLine |
| discardLine | ::= | printable-char* CRLF |
| Version | ::= | Major "." Minor { "." Release { { SPACE } "(" Platform ")" } } /* spaces only allowed between Release and "(" */ |
| Major | ::= | Integer /* <256 */ |
| Minor | ::= | Integer /* <256 */ |
| Release | ::= | Integer /* <256 */ |
| Platform | ::= | "Mac OS" | "X Windows" | "Motif" | "MS Windows 32 bit" | "MS Windows 16 bit" |
| MIMEcontentType | ::= | "Content-Type" ":" "multipart/mixed" ";" "boundary" "=" Delimiter discardLine |
| Delimiter | ::= | "****KSIDeLiMiTER****" /* or anything else that doesn't appear anywhere else */ |
| MIMEmultipartbody | ::= | discardLine* { InitialDelimiter Part }+ FinalDelimiter discardLine* |
| InitialDelimiter | ::= | "--" Delimiter CRLF /*no spaces*/ |
| FinalDelimiter | ::= | "--" Delimiter "--" CRLF /*no spaces*/ |
| Part | ::= | CMapPart | CGraphPart | OtherPart |
| CMapPart | ::= | CMapOptionalLine* "Content-Type" ":" "application/x-CMap" ";" "version" "=" Version discardLine CMapOptionalLine* CRLF ConceptMap |
| CMapOptionalLine | ::= | "Extension" ":" { "application/x-ConstraintGraph" ";" "version" "=" Version } discardLine |
| | | discardHeaderLine | |
| CGraphPart | ::= | discardHeaderLine* "Content-Type" ":" "application/x-ConstraintGraph" ";" "version" "=" Version discardLine discardHeaderLine* CRLF ConstraintGraph |
| OtherPart | ::= | discardLine* /*until a InitialDelimiter of FinalDelimiter is encountered*/ |
| ConceptMap | ::= | ConceptMapHeader ConceptMapBody |
| ConceptMapHeader | ::= | NextId { , OptionalExtension } CRLF ";" CRLF |
| ConceptMapBody | ::= | { ComponentFlag "," { NodeSection | ArcSection } }* ";" CRLF |
| ComponentFlag | ::= | HexInteger /* Interpretation: 0x1=node; 0x2=arc; 0x4=composite */ |
| NodeSection | ::= | NodeType , IDSpec , VisualType , BoundingBox , Text , FillColor , BorderColor , BorderStyle, BorderThickness, TextColor , VisualFlags { , OptionalExtension }* CRLF |
| ArcSection | ::= | ArcType , IDSpec , VisualType , BoundingBox , Arity { "," TerminalSpec }+ , { Text } , { FillColor } , { BorderColor } , { TextColor } , VisualFlags { , OptionalExtension }* CRLF /* TerminalID list must be the same length as the Arity value */ |
| TerminalSpec | ::= | ( TerminalID { , LineColor {, LineStyle {, LineThickness { , EndPointSpec { , EndPointSpec { , elbowPoint }* }}}}} ) |
| ElbowPoint | ::= | Point |
| EndPointSpec | ::= | { ArrowStyle } , { ArrowColor } , { Text } , { TextColor } |
| NextId | ::= | HexInteger |
| NodeType | ::= | QuotedString /* to be looked up in an object cloning library */ |
| IDSpec | ::= | HexInteger /* unique id of the object */ |
| VisualType | ::= | QuotedString /* to be looked up in an object cloning library */ |
| BoundingBox | ::= | Rectangle |
| VisualFlags
| ::= | HexInteger /* interpretation: 0x1=autosize, 0x2=selected, 0x4=shadowed, 0x8=htic, 0x10=vtic 0x20=hbar, 0x40=vbar, 0x80=highlight1, 0x100=highlight2, 0x200=highlight3, 0x400=highlight4, 0x1000=hidden, 0x2000=showMarks (was show handle 0x4000=autoplacement (was floatinghandle) */ |
| ArcType | ::= | QuotedString /* to be looked up in an object cloning library */ |
| Arity | ::= | HexInteger |
| TerminalID | ::= | IDSpec |
| ArrowStyle | ::= | QuotedString |
| Text | ::= | QuotedString |
| FillColor | ::= | ColorSpec |
| BorderColor | ::= | ColorSpec |
| BorderStyle | ::= | HexInteger /* interpretation: TBA */ |
| BorderThickness | ::= | HexInteger |
| LineStyle | ::= | HexInteger /* interpretation: TBA */ |
| L:ineThickness | ::= | HexInteger |
| TextColor | ::= | ColorSpec |
| LineColor | ::= | ColorSpec |
| ArrowColor | ::= | ColorSpec |
| ColorSpec | ::= | HexInteger /* interpretation: BBGGRR */ |
| Point | ::= | Integer Integer /* interpretation: x, y */ |
| Rectangle | ::= | Integer Integer Integer Integer /* intepretation: ULx ULy LRx LRy */ |
| QuotedString | ::= | """ String """ |
| String | ::= | { char }* |
| Integer | ::= | { - } { 0..9 }+ |
| hexInteger | ::= | { 0..9 | a..f | A..F }+ |
| OptionalExtension | ::= | /* application dependent */ |
The Constraint Graph application uses this sublanguage. It assumes that the Concept Map sublanguage part comes first, and that it is extended by replacing the OptionalExtension production with the following:
| OptionalExtension | ::= | hexInteger /*ID of an object in the constraint graph*/ |
The actual constraint graph sublanguage follows.
ConstraintGraph | ::= | /* TBA */ | |
The following is a simple example of a multipart MIME stream that contains only one instance of a concept map using the concept map sublanguage.
MIME-Version: 1.0 Content-Type: multipart/mixed; boundary=****KSIDeLiMiTER**** This file is written by the KSIMapper application, from the Knowledge Science Institute at the University of Calgary, Canada. --****KSIDeLiMiTER**** Content-Type: application/x-CMap; version=0.1 8 ; 1,"Node",5,"default",265 41 295 61,"C",ff80,0,,,0,0 2,"SMaplet",2,"BiDirect",110 75 110 75,2,(1,0),(4,0),,,,,3 1,"Node",7,"default",265 110 295 130,"D",ff0080,0,,,0,0 5,"ContextBox",4,"frame",144 8 304 142,"Context",ff8080,0,,,0,0 1,"Node",1,"default",10 44 76 107,"A",80ff,0,,,0,0 2,"SMaplet",6,"BTWN",234 85 234 85,3,(3,0),(5,0),(7,0),"BTWN",ffffff,0,0,1 1,"Node",3,"default",156 72 174 98,"B",8000ff,0,,,0,0 ; --****KSIDeLiMiTER****--
The above file should produce the following graph, assuming the application has the appropriate visual types "default", "BiDirect", "frame", and "BTWN":
The following is a sample of Constraint Graph (the second sublanguage above) concept map. A Constraint Graph file consists of a multi-part MIME structure containing at least an application/x-ConstraintGraph part followed by an application/x-CMap part. Note that because these grammars allow other MIME parts, a CMap program should also be able to read this file (by just ignoring the application/x-ConstraintGraph part before the application/x-CMap part).
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary=****KSI_CoNsTrAintGrAph****
This file is written by the ConstraintGraphs application, from the Knowledge Science
Institute at the University of Calgary, Canada.
Time: Wed Dec 11 14:52:50 1996
--****KSI_CoNsTrAintGrAph****
Content-Type: application/x-ConstraintGraph; version=0.1
1c,(),
("NodeComponent",a,"TOP",5,(("AttributeValuePair<unsigned long>","borderColor",65,0,0)("AttributeValuePair<unsigned long>","fillColor",65,0,80ffff)("AttributeValuePair<unsigned long>","textColor",65,0,0)))
("IsaComponent",b,"isa-11",5,(),((a,2)(2,1)),ffffffff)
("NodeComponent",c,"NODE",5,())
("IsaComponent",d,"isa-13",5,(),((c,2)(2,1)),ffffffff)
("NodeComponent",e,"ARC",5,())
("IsaComponent",f,"isa-15",5,(),((e,2)(2,1)),ffffffff)
("NodeComponent",10,"CONTEXT",5,())
("IsaComponent",11,"isa-17",5,(),((10,2)(2,1)),ffffffff)
("NodeComponent",12,"ISA",5,())
("IsaComponent",13,"isa-19",5,(),((12,2)(2,1)),ffffffff)
("NodeComponent",14,"BOTTOM",5,())
("IsaComponent",15,"isa-21",5,(),((14,2)(2,1)),ffffffff)
("IsaComponent",16,"?",5,(),((c,2)(a,1)),ffffffff)
("IsaComponent",17,"?",5,(),((e,2)(a,1)),ffffffff)
("IsaComponent",18,"?",5,(),((12,2)(e,1)),ffffffff)
("IsaComponent",19,"isa-25",5,(),((10,2)(c,1)),ffffffff)
("IsaComponent",1a,"?",5,(),((14,2)(e,1)),ffffffff)
("IsaComponent",1b,"?",5,(),((14,2)(c,1)),ffffffff)
--****KSI_CoNsTrAintGrAph****
Content-Type: application/x-CMap; version=0.1
Extension: application/x-ConstraintGraph; version=0.1
19,1,2,5,1,ffffffff,ffffffff
;
1,"ConsGraphNode",3,"ellipse",276 154 312 181,"ARC",80ffff,0,,,0,1,0,e
1,"ConsGraphNode",2,"ellipse",127 152 180 179,"NODE",80ffff,0,,,0,1,0,c
1,"ConsGraphNode",6,"ellipse",192 276 269 303,"BOTTOM",80ffff,0,,,0,1,0,14
1,"ConsGraphNode",1,"ellipse",209 76 246 103,"TOP",80ffff,0,,,0,1,0,a
1,"ConsGraphNode",5,"ellipse",332 220 362 247,"ISA",80ffff,0,,,0,1,0,12
1,"ConsGraphNode",4,"ellipse",61 217 150 244,"CONTEXT",80ffff,0,,,0,1,0,10
2,"ConsMaplet",7,"isa",193 127 193 127,2,(2,ff),(1,ff),,,,,3,0,16
2,"ConsMaplet",8,"isa",260 128 260 128,2,(3,ff),(1,ff),,,,,3,0,17
2,"ConsMaplet",9,"isa",321 200 321 200,2,(5,ff),(3,ff),,,,,3,0,18
2,"ConsMaplet",a,"isa",119 196 119 196,2,(4,ff),(2,ff),,,,,3,0,19
2,"ConsMaplet",b,"isa",255 226 255 226,2,(6,ff),(3,ff),,,,,3,0,1a
2,"ConsMaplet",c,"isa",201 225 201 225,2,(6,ff),(2,ff),,,,,3,0,1b
;
--****KSI_CoNsTrAintGrAph****--
The above file should yeild a graph that looks like this:
