Disclaimer. CSUSB and the CS Dept have no responsibility for the content of this page.
Copyright. Richard J. Botting ( Thu Nov 8 14:28:24 PST 2012 ). Permission is granted to quote and use this document as long as the source is acknowledged.
Revised March 1995
Revised March-April 1996 [ rjb96x.xbnf.html ]
Revised June 1999 to include latest additions to the notations: Tables and distinguishing quotation from assertion.
Revised November 2012 to give a better reference to Cantor's Theorem.
I will further show that there comes a point when BNF style definitions can cease to have meaning and lead to paradoxes.
I then define EBNF formally and then to explore the consequences of making small changes to the syntax and semantics of EBNF. This gives rise to a version called XBNF that has proved useful in teaching a programming languages course.
We can define terms of other types: Sets, functions, relations, types, classes, ... Definitions become a way of naming that can be used in any kind of documentation.
Finally, we can treat a piece of documentations itself as a piece of data. I will show how BNF can be used for pieces of documentation. The effect is to introduce an enhanced for inheritance into general documentation. Documentation becomes a "first class object" for its users. The theory of the resulting system seems to need recently developed theories of types, semantics, etc[Example: Leeuwen 90].
I prove that one set of extensions leads to paradox and hence has to be forbidden.
. . . . . . . . . ( end of section Introduction) <<Contents | End>>
BNF <number>::=<digit>|<number><digit> [Naur et al 64]
EBNF number::= digit {digit} [ANSI 83 ADA]The '{...}' indicate 'zero or more of. In EBNF a series of non_terminal are defined in terms of a regular expression that represents a set of strings (a language). However, EBNF-like dictionaries turn up in all parts of software engineering theory and practice, see Table 1 below.
Name | Elements | Defined_terms | Examples |
---|---|---|---|
Syntax | |||
Grammar | Tokens|Lexemes | Syntactic units | Naur et al 64,...Ada 93 |
Lexicon | String | Lexems | Bell Labs 83(lex) |
Abstract | Syntactic Units | Structures | Prog Lang Semantics |
Dictionary | Phrases | Terms | - |
Data Communication | |||
Protocol | Messages | Protocols | Zave 85, Naik & Sarikaya 92 |
RFC | Chars/Lines | Messages | SMTP |
Path exprs | Calls | Synchronisation | S/SL |
Ada Tasks | Entry names | Structure | Hemendinger 90 |
Interfaces | Methods | Objects | Botting 86a |
Data | |||
Dictionary | Data types | Data files | De Marco 80, JSP |
Structure | Data types | I/O Patterns | Warnier/Orr, JSP, |
Dynamics | Events | Neural nets | Kleene 1940s,DAD |
? | Commands | System Behaviors | Belli & Grosspietsch 91 |
ELH | Events | Life Histories | Robinson 79, JSD,SSADM |
Logic Grammar | Terms | Predicates | Abramson & Dahl 89 |
Programs | |||
Scenarios | Actions | Scenario | - |
Structure | C Function Call | C Functions | Baecker & Marcus 90 |
A string is treated as a singleton set when it is in a context that needs a set of strings:
In this section I stands for the set of the empty string:
The definition of (#) takes more machinery.
We could write,
but this formula uses an undefined idea: "...". This makes it difficult to reason accurately about #.
We could define the powers of a set (A^n) and then write an infinite union
So we start from the desirable property
and define #A as the smallest solution to the equation X = I | A X:
Note. In MATHS I write the set of x such that P as { x || P }.
Kleene showed that by repeatedly applying the operation that replaces X by ( I | A X) we get closer and closer to #A in the obvious sense. So
K1 and K2 above give a paradigm for defining the meaning of any grammar. For instance, the grammar { L::= a L b | "". } has one definitionL::= a L b | ""., one defined_term "L" and two elements: "a", "b". We define the meaning of "L" to be M where M is the smallest set of strings such that the following equation is true:
So
The above gives a recursive process testing whether a string lies in M. It does not tell us how to find elements in M. By Kleene's work M is also the smallest fixed-point of the mapping g, where
So to find M we use the iterative process below to generate the Kleene Sequence( S(0). S(1), ...).
Indeed M is a fixed point of g since M = g(M). Any proper subset of M is not a fixed point. The reason that the Ss seem to get closer to M is that as i tends to infinity we have to look at longer and longer strings to find a string in M that is not in S(i). Using a limit to define the meaning of grammar has been around in the literature for a long time (a bibliography is in section 6.7 of chapter 3 of my unpublished monograph). The fixed point definition came later and is similar to Scott's denotational semantics [ACM 86]. Fixed points, iteration, and topological spaces appear to be a vital part of the theory of software.
::=as in BNF. The "<" and ">" of the original BNF are used as relations and as parts of arrows and crosses. Parentheses "()" are used as they are in algebra. It adds "#" to mean any number of, including zero thus letting the brace symbols of EBNF be used for mathematical sets. The Ada EBNF symbols "[]" are used to show subscripts and bindings and so are not used for optional parts in XBNF. XBNF also has a standard dictionary that defines some simple functions: Ada EBNF { x } is #( x ) in XBNF and x #(x) is written N( x ) . [x ] in Ada EBNF is O(x ).
Here is a comparison of BNF, Ada EBNF and XBNF:
BNF <number>::=<digit>|<number><digit> [Naur et al 64]
EBNF number::= digit {digit} [ANSI 83 ADA]
XBNF number::= N(digit) [Botting 9x]We take over the notation from section 2.3 above and add intersection (&) and complementation (~) by:
A dictionary has any number of definitions and comments.
::=
A definition has a definer between the term being defined and the expression defining it.
In XBNF we are interested in sets of sequences:
A set_expression is either an item, or a union, or, ...
An item is either an element (defined below), or a defined term, or any set expression in parentheses,
A union has at least one alternative. Alternatives in a union are separated by vertical bars.
Each alternative is either a complementary_form or a sequence.
A sequence is a number of phases. The "number sign" (ASCII code hex(23), hash, sharp) shows the occurrence of any number of the next item - including none. A sequence can therefore be empty, one phase, or two phases, etc..
A phase is part of a sequence where an item occurs once, or the same item can occur any number of times including no times at all.
The ampersand character("&") shows that all the descriptions (items) must hold at once.
A complementary_form - A~B say - describes the set of As that are not Bs. Here is an example:
Any number characters (in a dictionary ) that are not a definition form a comment. This paragraph is a comment in this XBNF dictionary.
In MATHS the character names used in Ada are preferred
Here are some of the named ASCII characters:
A function call is written the usual way in XBNF. And the same form is used in defining functions:
Simple functions defined by non-recursive definitions do not change the expressive power but makes a practical difference. The following are a standard functions and can used in any lexical or syntactic dictionary:
Introducing the ability to define and use syntactic functions allows context sensitive features to be handled elegantly and efficiently... See below.
Some identifiers are defined_terms:
When the defined_terms are identifiers and the expressions have no intersections or complements then the dictionary is context free. The three dots (...) indicate that there a defined term can take other forms. A natural identifier is made up of words :
Words are either numbers or are made of letters. When made of letters they must be in a dictionary - either of a natural language or a special dictionary for the project,
Rules for creating and using identifiers in general documentation are discussed in my monograph. Meanwhile note that it is common to have several names with one meaning - typically there is a mathematical variable or symbol (like "a", "+", "\λ", ...) which is used in formulae plus a longer natural_identifier .
Often, a language is defined by two dictionaries - a lexicon that gives names to strings of symbols, and a syntactic dictionary or grammar. The grammar describes the structure of the language in terms of the tokens identified in the lexicon. In this presentation I combined both lexical and syntactic "shells" into a single presentation. Normally they would be split up into separate pieces of documentation - to do this I have experimented with a formalism that treats a dictionary as a module. This is described later. Meanwhile we will assume that the terms defined in the standard lexicon for the ASCII code can be used in future examples: thus terms like comma, r_paren, etc will be used in later syntax definitions.
I would suggest that we extend EBNF to also be a glossary. A glossary definition is a definition in the form:
So in a general piece of documentation a term may have two different definitions:
The glossary definitions above should be used to make bridges between the notations being defined and other things. They should be used for designations in Michael Jackson's terms.
.See URLMy mth2html, define, and lookup commands take account of this feature. The effect is that the C++ syntax file inherits definitions from the C syntax plus a glossary of object oriented terms. The syntax inherits the definitions of the ASCII characters and the functions and notation in a meta- definition of EBNF. define always searches a general glossary of computer science. This is all transparent to the user.
A recent addition is to allow a defined term to refer directly to part of (or the whole of) a document on the WWW:
term::=URL.
For example:
. . . . . . . . . ( end of section XBNF in XBNF) <<Contents | End>>
Therefore
The last result (L1) shows that a dictionary with an intersection can describe a non-context free language. Since a complement of a union is the intersection of the complements the same effect can be got by permitting complementation and NO intersection. However this seems to be a useless restriction.
Defining a language as the intersection of several grammatical constraints is neither new nor inefficient - Constrained Expressions are expressive and based on simple regular expressions [Dillon et al 86]. Hehner and Silverberg[83] use the term Communicating Grammars for a set of grammars with some terminals and non-terminals occurring in both. The model here is simpler - I propose the terms concurrent context free grammars (CCFG) for the dictionary model proposed here, and concurrent context free languages(CCFLs) for the family of languages defined by CCFGs. Hemendinger notes that Ada tasks have communication patterns that are CCFLs[Hemendinger 90]. Dictionaries with intersections define languages that are recognized by networks of parallel CFG acceptors. Psychologists use a network of "daemons" for modelling perceptual processes [ Human Information Processing, Lindsay & Norman, Pub Academic Press, 1970]. Finally: the hardest part of Jackson Structured Programming [JSP] is the use of semi-co-routines (in COBOL!) and to handle non-context- free problems by quasi-concurrency[Jackson 1975...].
where List maps a set of strings into another set of strings. As in all mathematics a function has a domain and a codomain that are set:
The image of a function F can be written post(F) - the set produced after F is applied to all the elements in it domain
Similarly,
For example, if F is a map from the Positive_Integers into sets of strings defined by:
then
This technique leads to a way to express the context dependencies found programming languages. For example take the labelled loop in Ada. Suppose that loop_with_label is a function the maps identifiers into valid Ada loops:
(for example
To be made precise the statement in the Ada grammar would also need to an argument representing the set of valid labels in internal loops.
Now, this is a context dependent set of strings and yet the definition shows us a simple and efficient way to parse (and check the syntax) loops: First, use CFG a parser for
and check for the reoccurrence of label . Clearly functions get us to the level of attribute grammars. Indeed we can handle context dependent productions:
Combining intersection with functions is interesting. Suppose that we have already defined declaration(V), usage(V), and no_ref(V) as the strings in a language which (1) declare or introduce V, (2) make use of V, and (3) don't refer to V respectively then:
describes all sequences of components where the argument is declared before it is used - and is NOT re-declared. If we now define
where the '&' is an intersection of all the valid_wrt(_) sets:
defines a block with all its variables declared exactly once before they are used. This is a common context sensitivity in programming languages. Finally the '&'s in the definition imply that the parser would be structured as a number of parallel parsers, all with the same structure. This form concurrency is very easy to handle in both theory [Hoare 79 & 85] and in practice [Jackson 75, Andre Banatre & Routeau 81, Cameron 89].
Definitions that include parameters are useful for defining and specifying maps and relations. Sets of definitions that include parameters are called Logical Grammars [ Abramson & Dahl 89 ]. A more general form of dictionary is the W-Grammar, or Two-level Grammar or Van-Wijngarten Grammar that contributed to the demise of Algol 68 yet is alive as a tool for documenting data structures[Gonnet & Tompa, Gonnet & Baeza-Yates 91]. The effect is that of a logic programming language [Ballance et al 90].
In the theory of programming languages, some recent papers, in data bases, systems analysis and design, several programming languages, and in object oriented programming there is a need to describe the structure of something rather than its precise syntax. A very simple extension to XBNF allows it to describe abstract structures: Change the definition
Add
An example is:
which defines the structure of a LISP list. In a binding, an item like
car:Listindicates that there is a map called car from the defined class structure with car:List & cdr:List to List.
The optional base is used to get the effect of inheritance:
term::@base=bindingsas a short hand notation for
term ::= base "with" bindings
However
term::base=valuedefines an object within the base universe, not a subset of it.
This formal model of abstract structure can be used to model the kind of formal and semiformal documentation that we are used to seeing texts, papers, manuals, and scribbled notes [ Documentation] .
Then we could write
This definition leads to a paradox when we try to work out how big P is. The size(cardinality) of P is written |P|. Clearly
However there is no number n such that:
Indeed if P = A|@P then we would have a set that included a subset isomorphic to its power-set. Cantor has shown such sets to be impossible.
Similarly when we use BNF to define function spaces:
We hit a similar paradox. Dana Scott replaces the above by
and shows this to be consistent and meaningful.
It seems wise therefore to not allow the use of '@X' (or X->) directly or indirectly to define 'X'. The normal mathematical forms can be used instead:
It can be shown however [ math_5_Object_Theory.html ] that when a set of equations can be modeled by an iteration of sets:
Source: Date: Mon, 11 Mar 1996 11:45:00 -0600 (CST)// Message-Id: <199603111745.LAA26492@asia.cs.rice.edu>// From: Corky Cartwright <cork@cs.rice.edu>// To: dick@csci.csusb.edu (Dr. Richard Botting)// Subject: Re: Domains (was Re: CBS and Coq)
A more powerful form is to parameterize a complete set of documentation by indicating that certain terms are generic. There are two kinds of generic terms that are needed. The first are those supplied by the person who is reusing the documentation - call these "given". Then there are the terms that are constructed and made available by the documentation. Call these the "goals". The result can be called a template, generic or a lever.
The syntactic extension is
Semantically these do no more than declare the type of the term. However they imply that the document is designed to be reused with the given terms redefined and the goal terms generated as a result:
. . . . . . . . . ( end of section Grammars and Dictionaries) <<Contents | End>>
Consider
These define the magnetic tape's physical structure. If we were designing a program to process a file of student records we might describe a file sorted by sections as follows:
Strictly speaking a definition of form
A::= B | A~Bis a theorem |-A = B | A~B.
If the domain has the words "file", "section" and "student" we use a similar structure, even if the class header is absent and a student record identifies the student's class instead. The result is called a logical structure.
If the problem is to summarize the data on each section then we might show the output as:
and note that each section corresponds to exactly one section_summary and the input corresponds to the output. It is easy to combine these into one abstract structure:
The structure above becomes a program when operations and conditions are added (see my monograph or any good JSP book).
A data dictionary is free of semantic and pragmatic structures because a file can be used for many purposes and hence is parsed into different structures. Typically:
Now if a,b,c,... are elements then
is the free semigroup or unstructured structure. In categorical terminology this is a free, initial, or universal repelling object in the category of semigroups with units. Free dictionaries are the weakest useful dictionaries. In consequence a design that has two or processes that communicate by consuming and producing strings(files) can interpret or structure the files as they wish. This is the powerful form of information hiding that is implicit in Jackson's work.
Data dictionaries can show a non-programmer what a program is expected to do in their own terminology not computer jargon. The canonical grammar/dictionary /glossary shows the user or client that we understand all their terminology. Canonical diagrams and dictionaries show how the user's data is handled in terms that the users and clients understand. The test of a canonical dictionary is that clients and users certify it as complete and accurate. Canonical dictionaries are the strongest useful dictionaries.
These imply
However, simple maps can be written with a constant blank space symbol (_) instead of the variable x:
As an immediate application are the STANDARD definitions of the syntax functions mentioned in the previous section:
So if we wrote
then some_map(x) = x. So, (_) must represent the identity map. Extend this line of thought further. Putting any function in an expression where a value is expected and we get an expression for a function instead of an expression of a value. So if g maps into the domain of f then
If 1st, 2nd, 3rd, 4th, ... n.th ... are maps from n-tpls into their components:
implies that
The result is a notation like the command line arguments in a C program, a UNIX shell script, ICL George 3 Macros, ... The same simple approach, starting with simple operations like successor (succ), predecessor(pred), and a constant zero(0) lets us develop the Peano arithmetic in EBNF_like definitions:
Here the semicolon acts like "if_then_": (;)=if (1st) then (2nd) but is actually the relational product described next.
I have shown that BNF definitions can define functions in a natural way.
Further if 1st and rest map a string into two parts so that x=1st(x)!rest(x), then
or any of the following forms
Given two binary relations R and S then For R: @(T1,T2), S:@(T2,T3),
/R is the converse relation to R. For example (_^2) is the 'square' function and /(_^2) is the square root relation, Similarly sin is the sin function and /sin includes the arcsin function. Further we want /parent_of=child_of. Therefore define:
In context, a set can also be used as a relation:
Complex situations can be defined quickly using these notations in and EBNF- like way see [ rjb95a.Relations.vs.Programs.html ]
Each document, package, or net can be have the formal content extracted and assembled into a binding:
The extraction and assembly process being like compilation.
Bindings are used in many other formula:
MATHS borrows an idea from the Ada package and the Z schema: networks can be named.. The original BNF notation is appropriate:
Nets are not interpreted as logic program. In many ways they can thought to define algebraic systems rather than a program,... indeed in most of these system the Unification Algorithm is not a valid deduction. MATHS provides the ability to show that the uncertain statements must follow from less doubtful ones. A special sign (|-) shows that the formula is either assumed or else that it can be derived from previous formulae. A complete inference engine or automatic theorem prover will be an uneconomic investment since the engineer can work interactively with a simpler proof checker. A proof typically has a Natural Deduction form like like the following, or an algebraic "Calculational" proof as praised by Shnieder and Gries.
It would be good to have a standard ASCII notation for writing down our ideas as long as it was easy and natural to use. Given the notations developed so far I think this is possible. Further in many cases one can create tools that translate this notation in other equivalent forms for different readers:
All formal documentation techniques so far have one of two opposed failings. When mathematically powerful they are not expressible easily in ASCII. When expressible in ASCII they are an extension to a programming language rather than a mathematical model. Only "Spec" [ Berzins & Luqi ?? ] is both sophisticated and in ASCII.
My attempt at solving this is to suggest that documentation has comments and more formal parts. The formal parts have precisely three kinds of element:
he detailed syntax is less important than the simple idea that documentation is itself a kind of more-or-less formal data. However I have developed several experimental syntaxes. One of these is documented in [ intro_documentation.html ] , . . . [ notn_00_README.html ] , . . . [ notn_10_Lexicon.html ] , . . . [ notn_11_Names.html ] , . . . [ notn_12_Expressions.html ] , . . . [ notn_13_Docn_Syntax.html ] , . . . [ notn_14_Docn_Semantics.html ] , . . . [ notn_15_Naming_Documentn.html ] , . . . [ notn_2_Structure.html ] , . . . [ notn_3_Conveniences.html ] , . . . [ notn_5_Form.html ] , . . . [ notn_8_Evidence.html] .
Thus EBNF has become a way to document mathematical and logical systems:
Once named and filed these systems can be referred to in other documents. For example, a group inherits the structure of a semigroup or monoid:
The effect is to formalize what mathematicians have always done and simultaneously introduce inheritance into computer documentation. I have converted most of my notes on algebra and topology into this form on a 7K floppy disk.
Here is an example of a practical application based on a recent publication:
Source: [Snyder 93, Alan Snyder<alan.snyder@eng.sun.com>, The Essence of Objects: Concepts and Terms, IEEE Software V10n1(Jan 93)pp31-42]
We proceed by abstracting noun phrases from these sentences and replacing them by sets and relations:
. . . . . . . . . ( end of section Applications) <<Contents | End>>
By extending EBNF to XBNF and then to MATHS we get a powerful way to document the domain in which software is or will be operating. "An application domain system model of the equipment and its intended environment of use is defined. This is a dynamic system model, and defines the overall states of the system as functions of time. Requirements are constraints on this model" [Hansen Ravn & Rischel 91 ]. Simple mathematics - sets, mappings, relations, definitions, assertions, etc.-
MATHS is more abstract than any programming language. It is designed to be too powerful for any conceivable computer to use as a programming language because the language used at the sharp end of a project must be able to define problems well enough so that we can recognize that they are (1) hard, or (2) not computable. Problems of efficiency, computability, data vs algorithms, etc. are handled as part of the implementation. The MATHS description of the problem and the specification of a requirement should be independent of all implementations and technology. Ignoring efficiency etc. is difficult at first. It is essential to describe the purpose and qualities of something before choosing or testing techniques. Hence:
MATHS & XBNF help solve several outstanding problems in the software process. First, we can show how the user's data is handled in terms that they understand. We can guarantee that this understanding is accurately modeled in the software by using rigorous design techniques. Second, Strachey pointed out the need to discover data structures before attempting functional design [Strachey 66]. The sets and maps found by formal analysis connect facts to conceptual data structures. Standard data base and data structures techniques can then implement the conceptual solution to the problem.
Projects that use MATHS can "zero-in" on the best software. First: Define things that appear in the description of the problem and (1) are outside the software, (2) interact with the software, and (3) are individually identifiable by the software. Second: Define events, entities, identifiers, relationships, attributes, facts, and patterns. These steps are an exercise in stating the obvious. Facts are recorded and verified by experts and by observation. Simple facts lead to validation of algorithms, data structures, and data bases.
If a system interacts with another system then it will have an internal model of the external system. An abstract model of the external system is a model for the internal system and so a structure for a design. Computer Science already teaches the techniques to implement the designs plus the calculus of sets, maps, and relations. So software design can be based on science. There is also a natural graphic representation (TEMPO). This is a basis for Software Engineering.
Formal Analysis proceeds by stating the obvious and so certain truths. Simple facts often delimit the set of logically correct structures. Grammars and dictionaries are used to document the data and dynamics of a domain. Relations can specify processes in a structured dictionary. Sets and maps define entity types, abstract data types, and classes of objects of the problem domain and are used to document requirements and specifications. When implemented, maps become paths through the data structures and data bases. So they define the structure shared by solution and problem.
Project documentation also describes the physical constraints caused by the technology used. Again there are two extremes: free and inconsistent. Some where between them is the best level. This records every assumption that can be made about the implementation technology. It is the canonical documentation of the technology being used when the software engineers are its clients and users.
This annex summarizes the notation I have developed to express discrete mathematics in ASCII.
. . . . . . . . . ( end of section Introduction) <<Contents | End>>
Equality is a special predicate that is defined for all universes of discourse. It is symbolized by "=". "<>" is (as in Pascal and BASIC) used for "not equal". [ logic_11_Equality_etc.html ] .Proofs [ logic_2_Proofs.html ]
. . . . . . . . . ( end of section Appendix) <<Contents | End>>
. . . . . . . . . ( end of section Body of Paper) <<Contents | End>>
. . . . . . . . . ( end of section How Far Can EBNF Stretch?) <<Contents | End>>