The EBNF grammar for PNG/JNG/MNG datastreams (draft, version 0.4)
The EBNF grammar for PNG-1.2 datastreams is here: png.ebnf
The EBNF grammar for JNG-1.0 datastreams is here: jng.ebnf
The EBNF grammar for MNG-1.0 datastreams is here: mng.ebnf
Corrections and other changes:
-
Changes from version 0.3 to version 0.4:
-
Allowed SAVE to immediately follow TERM [Gerard]
-
Reorganized the PNG/JNG rules and renamed the symbols using more abstract
names; updated the MNG rules according to these changes
-
Updated the lister "mnglist.c" to ignore the non-standard MNG chunks, and
to make possible to use MNG files with non-standard chunks in testing
-
Updated the ebnf-to-flex compiler "mkmnglex.pl" to expand the nested loops
up to 12 levels [based on an idea of Glenn]
-
Renamed the output of FLEX from "lex.yy.c" to "test_mnglex.c" and made
it available for download
-
Changes from version 0.2 to version 0.3:
-
Allowed nested loops [Gerard]
-
Allowed IDAT, JDAT, JDAA, JSEP in Delta-PNG [Gerard]
-
Fixed typo JPNG >> IJNG in Delta-PNG
-
Moved DROP, DBYK and ORDR in mng_dpng_mod_chunk and allow them before IHDR,
IPNG, JHDR or IJNG [Gerard]
-
Split the Delta-PNG chunks into mng_dpng_png_chunks and mng_dpng_jng_chunks
-
Moved PLTE and tRNS in png_toplevel_chunks [Gerard, Glenn]
-
Renamed mng_image_def to mng_image_edit [Gerard, Glenn]
-
Renamed mng_object to mng_embedded_object [Glenn]
-
Updated the ebnf-to-flex compiler "mkmnglex.pl" to remove the nested loops
from the flex file
-
Changes from version 0.1 to version 0.2:
-
Introduced rules for standalone PNG, JNG datastreams and MNG complete datastreams
[Glenn]
Notes:
-
These grammars do not express multiplicity for some chunks, i.e. it cannot
be inferred from the grammars that some chunks can appear only once.
-
The multiplicity and ordering rules for the PNG-1.2 standard chunks are
described here: png.ord.txt
-
The multiplicity and ordering rules for the JNG-1.0 standard chunks are
described here: jng.ord.txt
-
The multiplicity and ordering rules for the Delta-PNG-1.0 standard chunks
are described here: dpng.ord.txt
-
The multiplicity for the MNG-1.0 standard chunks will come soon.
-
Due to allowing embedded loops, the MNG grammar is not regular anymore.
Therefore, checking it using FLEX is not possible. While it is possible
to check its subset that does not allow embedded loops, a new method for
checking the entire grammar is being investigated. Any help will be very
appreciated.
Testing:
You are welcome to test the grammar against valid MNGs, provided
that, if there are embedded loops, their physical (not logical)
nesting level is no bigger than 12.
gcc -o test_mnglex test_mnglex.c # you should be able to use your favorite compiler
mnglist -c -s file.mng | test_mnglex
You can download test_mnglex.c (745K
!!) or test_mnglex.c.gz (165K),
or you can generate it by yourself (see below). The program mnglist.c
is needed to list the chunk names of PNG/JNG/MNG files.
Do not be discouraged by the BIG size of test lexer - that's
because it is just a dummy tester, and there is no optimization in it at
all. Its size is due mainly to the expansion of mng_loop, which yields
a very big number of DFA states. A much more efficient approach would be
to translate the EBNF productions to a LR(1) or a LALR(1) grammar (e.g.
YACC), rather than to a regular grammar.
How to generate the test lexer
The script to produce FLEX files is here: mkmnglex.pl.
Please note that this script expands the recursive definition of mng_loop
only 12 times, because FLEX would run out of NFA states otherwise.
# png.l and jng.l can be compiled as standalone parsers for PNG and JNG files
mkmnglex.pl png.ebnf > png.l
mkmnglex.pl jng.ebnf > jng.l
mkmnglex.pl png.ebnf jng.ebnf mng.ebnf > mng.l
flex -otest_mnglex.c mng.l
Last updated: Jan 29, 2001
Cosmin Truta