W3C home > Mailing lists > Public > w3c-wai-er-ig@w3.org > December 2000

Backus Naur Form (BNF) to XML

From: Leonard R. Kasday <kasday@acm.org>
Date: Fri, 15 Dec 2000 14:47:23 -0500
Message-Id: <4.3.2.7.2.20001215114523.00e03710@pop3.concentric.net>
To: w3c-wai-er-ig@w3.org
We've been discussing how to transform languages into XML form so we can 
use XPointer in our evaluation descriptions of them.

I took an action item to propose a generic way to convert any language 
expressed in Backus Naur Form (BNF).  See e.g. [1] for a BNF tutorial.

I propose an XML application with just three  tags

<rule name="foo">   </rule>
<terminal name="bar"/>
<cdata value="baz" />

"rule" and "terminal" correspond to BNF rule and terminal symbols (what else?).
We could get by without cdata, but then all the terminals would be 
individual characters. This is a shortcut to avoid that level of detail.

Lets jump to an example.  Here's a simple unix-like command

     sort +increasing -unique phonebook

BNF for this sort of command is as follows.


(I use the following BNF notation:
Unquoted strings are rules.
Quoted strings and characters are terminals.
  * means 0 or more.
| means "or".
Brackets [] enclose prose definitions.
)


command ::= command-name (argument)*   filename
command-name ::= "sort" | "print"| "mail"
argument ::=  prefix argument-name
argument-name ::= "increasing" | "unique"
prefix ::= '+' | '-'
filename = [any sequence of alpha characters]

Using the BNF to parse the example "sort" command, which I repeat here for 
convenience,

     sort +increasing -unique phonebook

we get:

<rule name="command">
       <rule name="command-name">
             <terminal name="sort"/>
       </rule>
       <rule name="argument"
             <rule name="prefix"
                    <terminal name="+" />
             </rule>
             <rule name="argument-name">
                   <terminal name="increasing" />
             </rule>
       </rule>
       <rule name="argument">
              <rule name="prefix"
                    <terminal name="-" />
             </rule>
             <rule name="argument-name">
                   <terminal name="unique" />
             </rule>
       </rule>
       <rule name="filename"
             <cdata value="phonebook">
       </rule>
</rule>

Note that if you just scan down and read the terminal and cdata tags, you 
reconstruct the original unparsed data.  So it's simple to see where you 
are in the raw input stream.

And, if you go up the XML tree, you unwrap the production rules that were 
involved in the parse.
In other words, this is a just an XML version of the parse tree.

So in principle we've got a way to represent CSS, ECMAScript, C++, Java, 
Cobal, ADA, anything that can be specified by BNF.    Hmmm.  Is there an 
BNF for HTML?

So... comments anyone?
Any yacc gurus out there who'd like to implement this?

Len

p.s.

I did a quick look around w3c and google and didn't find anything like 
this, but I expect that other folks have been thinking along the same 
lines.  If anyone knows of something like this, please post it, especially 
if they already have the converter coded up!


[1] http://burks.bton.ac.uk/burks/foldoc/82/9.htm
--
Leonard R. Kasday, Ph.D.
Institute on Disabilities/UAP and Dept. of Electrical Engineering at Temple 
University
(215) 204-2247 (voice)                 (800) 750-7428 (TTY)
http://astro.temple.edu/~kasday         mailto:kasday@acm.org

Chair, W3C Web Accessibility Initiative Evaluation and Repair Tools Group
http://www.w3.org/WAI/ER/IG/

The WAVE web page accessibility evaluation assistant: 
http://www.temple.edu/inst_disabilities/piat/wave/
Received on Friday, 15 December 2000 14:47:42 GMT

This archive was generated by hypermail 2.2.0 + w3c-0.30 : Thursday, 9 June 2005 12:10:38 GMT