2.1 Context Sensitive Situations

Context sensitive situations involve the interpretation of data in which the interpretation of one segment of data is dependent upon the interpretation of another segment. In other words, the meaning of one piece of data can potentially change the meaning of a piece of data elsewhere in the system. This is often the case with data transmission, where signals to change the interpretation mode are encountered regularly, or in situation-reactive systems, where interpretation of data from one set of sensors or instruments affects the interpretation of another set of data. Context sensitive situations are a source of subtle programming errors which are difficult to identify and fix. The solution we are exploring is to define a set of formal languages powerful enough to handle the common context sensitive situations identified in problematic components.

The following example outlines the problem, and shows why concise specification is an extremely important attribute of a well-engineered solution. The basic scenario is simple. A data stream includes the following structure:

startVal count time frame₁ frame₂... frame$_{\rm count}$endVal

Although the grammar is simple, implementing the parser for the data stream with a context-free (or worse yet, with a hand-built) parser has led to several unintentional errors. In the most straightforward formal specification, the grammar had the following fragment of BNF:

frames::=   startVal frameList endVal
frameList::=startVal count time frame  |
       frameList frame

The source of errors with this scheme is that the count is ignored; there is no declaration of the legal values for count. Further, the actions for the first frame are different than for the second and subsequent frames. The next fragment attempts to include more context sensitivity, but still tries to do so with a context free grammar.

frames::=    frameList
frameList::=startVal 1 time frame  |
            startVal 2 time frame frame endVal
                    ...

Although there is now a special case for each possible value of count, the actions for processing the frames are replicated

$${\rm maxCount + maxCount-1}+\dots + 3 +2 +1 = \frac{\rm{(maxCount +1)maxCount}}{2} \nonumber$$

times, where maxCount is the largest value count can assume. From a linguistic point of view, the grammar accomplished its mission. However from the point of view of the engineered solution, there was a high degree of likelihood one of the frames would not be processed correctly.

The alternative we propose is an extension of the standard context sensitive grammar (where standard here refers to Chomsky level 2, which has limitation that the length of the left side of a production be less than or equal to the length of the right side of the production, see [3]). The following grammar is compact enough for human verification and also explicitly allows the designer to specify the semantic processing for the frame in exactly one location.

frameList ::= completeFrame |
	         frameList completeFrame
completeFrame ::=  time frame

{processing action for the frame}

time frame::= startVal 1 time frame endVal
time frame startVal 1 time ::= startVal 2 time frame
time frame startVal 2 time ::= startVal 3 time frame
...

time frame startVal maxCount-1 time ::= startVal maxCount time frame

In short, for each production

$$A \rightarrow B \nonumber$$

where the length of A is n and the length of B is m, and m < n, there must also exist a second production

$$C \rightarrow D \nonumber$$

such that

1.

the length of D = x, where $x \ge n-m+1$

2.

the length of C =1

3.

D corresponds to the first x symbols of A.

Even though this is a small generalization of the standard (simplest) context sensitive grammar, the impact on the architecture of the software component studied was enormous: rather than a huge number of `special cases', the component can now be specified with a few dozen compact and precise rules. This example, along with our interactions with the engineers that built the original implementation of the module, leads to several observations:

1.

The formal specification must match the application closely for it to be useful to the application designer.

2.

Most software engineers avoid generating (or even admit that they know about) formal specification methods because they are so difficult to use.

3.

Therefore, there exists a need for simpler formal specification generation tools.