Re: Example of a text format that requires 2 passes?Q1

["Beckerle, Mike" <mb...@tresys.com>]

Q1: No I don't agree. But with modification of the example....yes.


This textual format is readily parsed via looking for name-value pairs until an integer is encountered. You then just verify that the array has the length given by the number, but you don't need the number in order to do the parsing. In fact you could parse the data, and present it, even if the number at the end is incorrect.


However, if you make this a binary format, so that there really is no way to distinguish the Name: Value string from an integer, then yes, you have to work from the end of the data backwards to isolate the integer, then work from the start of the data forwards. So 2 passes would be needed.


Q2: At parse time true. Unparse-time expressions - used in dfdl:outputValueCalc, often look later into the infoset.


Q3: True, your expression is not valid. You need to use a different occursCountKind here. It's simply not well defined to have the length or number of occurrences of something determined by something else that appears after them in the data. The constraint that these "should match" is not part of the format needed for parsing. It's just a validation constraint - a quality check if you will. Not needed for parsing.


Q4: Yes. Your example is simplistic, but in fixed-length data formats, this forward-reference-at-parse-time problem really does exist.  For example the NATO STANAG 5516 (aka  link16) format is not generally available to the public, but in it there are a few sub-formats where there is forward reference situations at parse time.


Neither the length, nor the occurs-count can involve forward reference, but a tag to determine a choice of two equal-length variants, can appear after that choice.


I have a couple slides, attached, that explain the way this happens. It's a natural thing in a way when you have older fixed-length data formats that are being extended/grown for new purposes.


DFDL cannot model this forward reference directly. Fortunately, these forward references are over very small distances in the formats where we've seen it, so there are other ways to model this.


-mike beckerle

Tresys






________________________________
From: Costello, Roger L. <co...@mitre.org>
Sent: Monday, January 28, 2019 11:41 AM
To: users@daffodil.apache.org
Subject: Example of a text format that requires 2 passes?

Hello DFDL community,

The following input file can be parsed in one pass:

5
Name: Tom
Name: Bill
Name: Jill
Name: Sara
Name: Bob

where 5 indicates the number of names that follow. I know a 1-pass parse is possible because I wrote a DFDL schema to do it.

Question #1: Do you agree that the following input file cannot be parsed in one pass; it requires two passes?

Name: Tom
Name: Bill
Name: Jill
Name: Sara
Name: Bob
5

Three more questions:

Question #2: An expression in a DFDL attribute can only look backward; an expression cannot look forward. Do you agree?

Question #3: The expression in the following dfdl:occursCount is trying to look forward; do you agree?

<xs:element name="names">
    <xs:complexType>
        <xs:sequence dfdl:separator="%NL;" dfdl:separatorPosition="infix">
            <xs:element name="entry" maxOccurs="unbounded"
                dfdl:occursCount="{ ../number-of-names }" dfdl:occursCountKind="expression">
                <xs:complexType>
                    <xs:sequence dfdl:separator=":" dfdl:separatorPosition="infix">
                        <xs:element name="name" type="xs:string" />
                        <xs:element name="value" type="xs:string" />
                    </xs:sequence>
                </xs:complexType>
            </xs:element>
            <xs:element name="number-of-names" type="xs:integer" />
        </xs:sequence>
    </xs:complexType>
</xs:element>

Question #4: My example of a text format that requires 2 passes is hokey (why would anyone put the number after the list of names). Can you think of a more realistic example of a text format that requires 2 passes?

/Roger