Estoy tratando de definir el BNF de BNF. En otras palabras, estoy tratando de definir la meta-gramática de BNF. Es decir, una gramática BNF que es una instancia de sí mismo y puede generar cualquier otra gramática BNF.¿Cuál es el BNF de BNF? es decir, ¿cómo definimos una meta gramática BNF?
¡Cualquier sugerencia/sugerencia/fragmento sería muy apreciada!
Gracias!
Aquí hay uno:
bnf = rules ;
rules = rule ;
rules = rules rule ;
rule = lefthandside EQUAL righthandside SEMICOLON ;
lefthandside = IDENTIFIER ;
righthandside = ;
righthandside = righthandside token ;
token = IDENTIFIER ;
token = QUOTEDLITERAL ;
Esto deja identificador, QUOTEDLITERAL, EQUAL y COMA indefinido, bajo el supuesto de que el BNF se define sobre fichas de langauge.
Puede definir BNF sobre los caracteres. Sólo tiene que añadir:
EQUAL = '=' ;
SEMICOLON = ';' ;
IDENTIFIER = letter ;
IDENTIFIER = IDENTIFIER letterordigit ;
letterordigit = letter ;
letterordigit = digit ;
letter = 'A' ;
...
letter = 'Z' ;
digit = '0' ;
...
digit = '9' ;
deja como ejercicio para el lector: añadir elección (|), varias reglas, y la estrella de Kleene a hacer de esto una BNF para EBNF; esta respuesta obviamente se comporta con el manejo de los espacios en blanco, pero puede manejar eso insertando un espacio en blanco no final donde los espacios en blanco están permitidos (repulsivo pero funciona). Existen sistemas de especificación BNF en los que realmente se escribe la gramática esencialmente sobre los caracteres, y ese tipo de inserción no final implícita en blanco se hace por usted (por ejemplo, Stratego's "Syntax Definition Formalism").
Si desea una lección alucinante en BNF-about-BNF, debe leer el paper/do the tutorial para un sistema de procesamiento BNF de honest-to-gosh 1965 llamado "MetaII". Este documento describe cómo hacer BNF en BNF, y cómo construir dos compiladores, en todas las 10 páginas.
(Una gran lección aquí: lea todo el material de ciencias de la computación de los años 60 y 70. No hay mucho de eso, y se sorprenderá de la cantidad de material bueno que hay).
<line> ::= '<' <word> '>' '::=' <definition>
<definition> ::= <word> '|' | '' <definition> | ''
Su pregunta parece ser respondidas por el [artículo de Wikipedia sobre BNF] (http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form#Further_examples). –
@GregHewgill Interesante. Frank de Remer me enseñó que BNF no puede describirse a sí mismo. – EJP
@EJP: De Remer era (¿es?) Bastante espectacular con generadores de analizadores y gramáticas No creo que él hubiera enseñado eso. Sospecho que algunos recordaron mal lo que aprendieron. –