Case Study: The GIF Format

Error

To be added later.

The GIF format is widely used to encode image sequences.

We start with a very short GIF to keep things simple (source): tinytrans.gif.

We can parse this file using Fandango:

!fandango parse -f gif89a.fan tinytrans.gif -o - --format=grammar --validate
assert _exit_code == 0

<start> ::= <GifHeader> <LogicalScreenDescriptor> <GlobalColorTable> <Data_1> <Trailer>  # b'GIF89a\x01\x00\x01\x00\x80\x01\x00\xff\xff\xff\x00\x00\x00!\xf9\x04\x01\n\x00\x01\x00,\x00\x00\x00\x00\x01\x00\x01\x00\x00\x02\x02L\x01\x00;'
  <GifHeader> ::= <GIFHEADER>
    <GIFHEADER> ::= <Signature> <Version>  # b'GIF89a'
      <Signature> ::= <char> <char> <char>  # b'GIF'
        <char> ::= <byte>
          <byte> ::= <_byte>
            <_byte> ::= b'G'  # Position 0x0000 (0)
        <char> ::= <byte>
          <byte> ::= <_byte>
            <_byte> ::= b'I'  # Position 0x0001 (1)
        <char> ::= <byte>
          <byte> ::= <_byte>
            <_byte> ::= b'F'  # Position 0x0002 (2)
      <Version> ::= <char> <char> <char>  # b'89a'
        <char> ::= <byte>
          <byte> ::= <_byte>
            <_byte> ::= b'8'  # Position 0x0003 (3)
        <char> ::= <byte>
          <byte> ::= <_byte>
            <_byte> ::= b'9'  # Position 0x0004 (4)
        <char> ::= <byte>
          <byte> ::= <_byte>
            <_byte> ::= b'a'  # Position 0x0005 (5)
  <LogicalScreenDescriptor> ::= <LOGICALSCREENDESCRIPTOR>
    <LOGICALSCREENDESCRIPTOR> ::= <Width> <Height> <PackedFields> <BackgroundColorIndex> <PixelAspectRatio>  # b'\x01\x00\x01\x00\x80\x01\x00'
      <Width> ::= b'\x01' b'\x00'  # Position 0x0006 (6); b'\x01\x00'
      <Height> ::= b'\x01' b'\x00'  # Position 0x0008 (8); b'\x01\x00'
      <PackedFields> ::= <LOGICALSCREENDESCRIPTOR_PACKEDFIELDS>
        <LOGICALSCREENDESCRIPTOR_PACKEDFIELDS> ::= <GlobalColorTableFlag> <ColorResolution> <SortFlag> <SizeOfGlobalColorTable>  # 0b10000000 (128)
          <GlobalColorTableFlag> ::= 1  # Position 0x000a (10), bit 7
          <ColorResolution> ::= 0 0 0  # Position 0x000a (10), bits 6-4; 0b0 (0)
          <SortFlag> ::= <bit>
            <bit> ::= <_bit>
              <_bit> ::= 0  # Position 0x000a (10), bit 3
          <SizeOfGlobalColorTable> ::= 0 0 0  # Position 0x000a (10), bits 2-0; 0b0 (0)
      <BackgroundColorIndex> ::= b'\x01'  # Position 0x000b (11)
      <PixelAspectRatio> ::= b'\x00'  # Position 0x000c (12)
  <GlobalColorTable> ::= <RGB> b'\x00' b'\x00' b'\x00'  # Position 0x000d (13); b'\xff\xff\xff\x00\x00\x00'
    <RGB> ::= <R> <G> <B>  # b'\xff\xff\xff'
      <R> ::= <UBYTE>
        <UBYTE> ::= <ubyte>
          <ubyte> ::= <uchar>
            <uchar> ::= <unsigned_char>
              <unsigned_char> ::= <byte>
                <byte> ::= <_byte>
                  <_byte> ::= b'\xff'  # Position 0x0010 (16)
      <G> ::= <UBYTE>
        <UBYTE> ::= <ubyte>
          <ubyte> ::= <uchar>
            <uchar> ::= <unsigned_char>
              <unsigned_char> ::= <byte>
                <byte> ::= <_byte>
                  <_byte> ::= b'\xff'  # Position 0x0011 (17)
      <B> ::= <UBYTE>
        <UBYTE> ::= <ubyte>
          <ubyte> ::= <uchar>
            <uchar> ::= <unsigned_char>
              <unsigned_char> ::= <byte>
                <byte> ::= <_byte>
                  <_byte> ::= b'\xff'  # Position 0x0012 (18)
  <Data_1> ::= <DATA>
    <DATA> ::= <GraphicControlExtension> <ImageDescriptor> <LocalColorTable> <ImageData>  # b'!\xf9\x04\x01\n\x00\x01\x00,\x00\x00\x00\x00\x01\x00\x01\x00\x00\x02\x02L\x01\x00'
      <GraphicControlExtension> ::= <GRAPHICCONTROLEXTENSION>
        <GRAPHICCONTROLEXTENSION> ::= <ExtensionIntroducer_1> <GraphicControlLabel_1> <GraphicControlSubBlock> <BlockTerminator_2>  # b'!\xf9\x04\x01\n\x00\x01\x00'
          <ExtensionIntroducer_1> ::= b'!'  # Position 0x0013 (19)
          <GraphicControlLabel_1> ::= b'\xf9'  # Position 0x0014 (20)
          <GraphicControlSubBlock> ::= <GRAPHICCONTROLSUBBLOCK>
            <GRAPHICCONTROLSUBBLOCK> ::= <BlockSize> <PackedFields_2> <DelayTime> <TransparentColorIndex>  # b'\x04\x01\n\x00\x01'
              <BlockSize> ::= b'\x04'  # Position 0x0015 (21)
              <PackedFields_2> ::= <GRAPHICCONTROLEXTENSION_DATASUBBLOCK_PACKEDFIELDS>
                <GRAPHICCONTROLEXTENSION_DATASUBBLOCK_PACKEDFIELDS> ::= 0 0 0 0 0 0 0 1  # Position 0x0016 (22), bits 7-0; 0b1 (1)
              <DelayTime> ::= b'\n' b'\x00'  # Position 0x0017 (23); b'\n\x00'
              <TransparentColorIndex> ::= b'\x01'  # Position 0x0019 (25)
          <BlockTerminator_2> ::= b'\x00'  # Position 0x001a (26)
      <ImageDescriptor> ::= <IMAGEDESCRIPTOR>
        <IMAGEDESCRIPTOR> ::= <ImageSeperator_1> <ImageLeftPosition> <ImageTopPosition> <ImageWidth> <ImageHeight> <PackedFields_1>  # b',\x00\x00\x00\x00\x01\x00\x01\x00\x00'
          <ImageSeperator_1> ::= b','  # Position 0x001b (27)
          <ImageLeftPosition> ::= b'\x00' b'\x00'  # Position 0x001c (28); b'\x00\x00'
          <ImageTopPosition> ::= b'\x00' b'\x00'  # Position 0x001e (30); b'\x00\x00'
          <ImageWidth> ::= b'\x01' b'\x00'  # Position 0x0020 (32); b'\x01\x00'
          <ImageHeight> ::= b'\x01' b'\x00'  # Position 0x0022 (34); b'\x01\x00'
          <PackedFields_1> ::= 0 0 0 0 0 0 0 0  # Position 0x0024 (36), bits 7-0; 0b0 (0)
      <LocalColorTable> ::= b'\x02' b'\x02' b'L'  # Position 0x0025 (37); b'\x02\x02L'
      <ImageData> ::= <IMAGEDATA>
        <IMAGEDATA> ::= <LZWMinimumCodeSize> <DataSubBlocks>  # b'\x01\x00'
          <LZWMinimumCodeSize> ::= b'\x01'  # Position 0x0028 (40)
          <DataSubBlocks> ::= b'\x00'  # Position 0x0029 (41)
  <Trailer> ::= <TRAILER>
    <TRAILER> ::= <GIFTrailer_1>
      <GIFTrailer_1> ::= b';'  # Position 0x002a (42)