XML Validation for Context-Free Grammars
Yasuhiko Minamide1 and Akihiko Tozawa2
1

Department of Computer Science
University of Tsukuba
2
IBM Research,
Tokyo Research Laboratory, IBM Japan, ltd.

Abstract. String expression analysis conservatively approximates thepossible string values generated by a program. We consider the validationof a context-free grammar obtained by the analysis against XML schemas
and develop two algorithms for deciding inclusion L(G1 ) ⊆ L(G2 ) where
G1 is a context-free grammar and G2 is either an XML-grammar or aregular hedge grammar. The algorithms for XML-grammars and regularhedge grammars have exponential and doubly exponential time complexity, respectively. We have incorporated the algorithms into the PHP
string analyzer and validated several publicly available PHP programs
against the XHTML DTD. The experiments show that both of the algorithms are eﬃcient in practice although they have exponential complexity.

1

Introduction

String expression analysis conservatively approximates the possible string values
generated by a program [CMS03b]. Minamide adopted context-free grammars
as a foundation of string expression analysis and developed a string analyzer for
PHP [Min05]. We consider the validation of a context-free grammar obtainedby the analysis against XML schemas and develop two algorithms for deciding
inclusion L(G1 ) ⊆ L(G2 ) where G1 is a context-free grammar and G2 is either
an XML-grammar or a regular hedge grammar, which are subclasses of contextfree grammars theoretically corresponding to XML schema languages such as
Document Type Deﬁnition (DTD) and RELAX NG [CM01].
To simplify the discussion on XML validation, we consider languages overa paired alphabet. Context-free languages with parentheses or paired alphabets
were studied extensively in the 1960s and 1970s [McN67,Knu67,Tak75]. Let A
be a base alphabet. Then, we introduce a paired alphabet consisting of two sets
Á and À:Á = { á | a ∈ A }À = { à | a ∈ A }where Á and À correspond to the set of start tags and the set of end tags,
respectively. We consider that á and à match. We write Σ for Á ∪ À. This
notation is based on Takahashi’s work on context-free grammars [Tak75].
The fundamental notion on a string over a paired alphabet is whether it isbalanced. For example, áb́b̀ćc̀à and áàb́b̀ are balanced, but áb̀ and áb́b̀ are not.

This notion of balanced strings corresponds to well-formed documents in XML.
We call the set of all balanced strings B(Σ) the Dyck set over Σ.
As a balanced subclass of context-free languages, Berstel and Boasson proposed XML-grammars modeling DTDs and studied their formal properties [BB02].
An XML-grammar consists of a set of terminals Σ = Á∪ À, a set of nonterminals
V in one-to-one correspondence with base alphabet A, a start nonterminal S,
and a set of productions. For each a ∈ A, there must be a unique production of
the following form:
Xa → áRa à
where Xa is the nonterminal corresponding to a and Ra is a regular expression
over V .
Example 1. Consider the following DTD, taken from [BB02].
<!DOCTYPE a [<!ELEMENT a ((a|b),(a|b)) ><!ELEMENT b (b)* >]>This DTD can be represented by an XML-grammar with the following productions:
Xa → á(Xa |Xb )(Xa |Xb )à
Xb → b́Xb∗ b̀where Xa and Xb are the nonterminals corresponding to a and b, respectively,
and Xa is the start symbol.
In this formal setting, validating a context-free grammar against a DTD
corresponds to checking L(G) ⊆ L(Gxml ) for a context-free grammar G andan XML-grammar Gxml . To develop an algorithm checking this inclusion, we
exploit locality in DTDs and XML-grammars. They have locality in the sensethat they can only describe a relation between an element and its children as canseen in the deﬁnition of XML-grammars. The algorithm has exponential timecomplexity and is presented in Section 4.
There is a larger class of grammars called regular hedge grammars corresponding to regular tree languages over unranked alphabets [Mur99]. The classof regular hedge grammars can be formulated as an extension of XML-grammars
where each production has the following form:
X→R
where R is an arbitrary regular expression over áY à. Also there is an alternative formulation of regular hedge grammars. We obtain grammars of the same
expressiveness by restricting each production to one of the following forms:
X → áY àZor

X → .

Example 2. The following is a regular hedge grammar where I is the start symbol.
I→X

X → (áY à)∗ (áXà)(áY à)∗X → (áY à)∗ (b́Y b̀)(áY à)∗Y → (áY à)∗The same language is obtained by the following productions.
I→X
Y → áY àY

X → áXàYY →

X → áY àX

X → b́Y b̀Y

The grammar generates the set of balanced strings over { á, à, b́, b̀ } containing
one pair of b́ and b̀.
There is a regular hedge grammar that cannot be represented as an XMLgrammar. The example above is indeed such a regular hedge grammar. Inversely,an XML-grammar can always be considered as a regular hedge grammar. We
describe an XML validation algorithm of a context-free grammar against a regular hedge grammar in Section 3. This makes it possible to validate a context-freegrammar against XML schemas such as RELAX NG which is more expressive
than DTD. This validation algorithm has doubly exponential time complexity.
We introduce two new algorithms for deciding inclusion L(G1 ) ⊆ L(G2 )for G1 a context-free grammar and G2 either an XML-grammar or a regularhedge grammar. However, they do not extend known results on subclasses ofcontext-free grammars for G2 , for which the above inclusion problem is decidable. Greibach and Friedman considered the inclusion problem for a subclass ofdeterministic pushdown automata called superdeterministic PDA [GF80]. They
showed that it is decidable whether L(M1 ) ⊆ L(M2 ) for M1 an arbitrary nondeterministic PDA and M2 a superdeterministic PDA. The complexity of theiralgorithm is doubly exponential in the size of the machines. It was also shownthat generalized parenthesis languages studied by Takahashi [Tak75] are superdeterministic: a generalized parenthesis grammar is translated into a superdeterministic PDA, which is exponential in its size. Since regular hedge grammars
are a subclass of generalized parenthesis grammars, their result is more general than ours and we can apply their algorithm to validation of a context-freegrammar against a regular hedge grammar. However, if we naively estimate thecomplexity of the validation through a superdeterministic PDA, the complexity
is triply exponential. This is one order of exponential worse than our validation
algorithm.
Hereafter in this paper, we assume that a context-free grammar (CFG) is
reduced. This means that every nonterminal is accessible from the start symbol
and every nonterminal produces at least one terminal string.
This paper is organized as follows. In Section 2, we describe the algorithm of
Berstel and Boasson, which decides whether or not every word of a context-freegrammar is balanced. This is the basis of both of our algorithms. In Sections 3
and 4, we introduce our validation algorithms for regular hedge grammars andXML-grammars, respectively. In Section 5, we describe the implementation of
the algorithms as backend validators of the PHP string analyzer and show ourexperimental results. Finally, we review related work and present some conclusions.

2

Checking Balancedness

One of the most fundamental notions of strings over a paired-alphabet is theirbalancedness. Knuth [Knu67] developed an algorithm to decide whether the
language of a context-free grammar is balanced for a language with a single
pair of parentheses. Berstel and Boasson [BB02] extended this for a language
over a paired alphabet.
Proposition 1. Given a context-free grammar G over a paired alphabet, it isdecidable whether or not its language is balanced.
This balancedness check is the basis of validation algorithms because a grammar
G is valid against some XML or regular hedge grammar only if G is balanced.
However, the original algorithm by Berstel and Boasson for this balancedness
check was not eﬃcient as it could be, so that we here give an improved versionof their algorithm.
Berstel and Boasson started from the following observation. We say a string
φ is partially balanced if it is a factor, i.e., substring, of some balanced string. If φis partially balanced, we have a = b whenever áψ b̀ occurs in φ with ψ balanced.
As a result, each such φ is always uniquely factorized into the following form
with all φi balanced.
φ = φ1 à1 φ2 à2 φ3 · · · àn φn+1 án+1 · · · φm ám φm+1
Let us deﬁne a partial function ρ : Σ ∗  À∗ Á∗ by
à1 à2 · · · àn án+1 · · · ám φ is partially balanced
ρ(φ) =
undeﬁnedotherwise
Observe that (1) φ is balanced iﬀ ρ(φ) = , and (2) ρ(φψ) = ρ(ρ(φ)ρ(ψ)) if φand ψ are partially balanced. This means that to determine whether all strings
generated from a context-free grammar G are balanced, it is suﬃcient to check
G under interpretation by ρ.
Example 3. Consider the following grammar.
I → ááXàà

X → ààáá

X → áXà

The language of this grammar is balanced. A set of strings generated from X is{ák ààááàk | k ≥ 0} whose interpretation by ρ is a ﬁnite set {ààáá, àá, }. We
can easily see that for each string φ in this set ρ(ááφàà) = .

The idea of the balancedness check is to compute the ﬁnite set Irr(X)(⊆∗À Á∗ ) = {ρ(φ) | X −→ φ} for each nonterminal X. As in the above example,
given a balanced grammar this set is always ﬁnite. Furthermore, each length ofφ ∈ Irr(X) is at most exponential to the size of the balanced grammar. These
facts suggest that we can stop the computation of Irr(X) whenever some stringφ ∈ Irr(X) is found to be longer than a given ﬁxed length. This is the idea of
Berstel and Boasson.
Let us look at this idea more precisely. In general, for each nonterminal X,∗
we have a derivation in the form I −→ ψXζ such that both ψ and ζ are at
most of exponential length to the size of grammar 3 . Now, the balancedness∗
implies that ρ(ψφζ) =  for any φ such that X −→ φ. We can observe that thisholds iﬀ ρ(ψ), ρ(ζ) and ρ(φ) are in the following forms, ρ(ψ) = b́k · · · b́1 án · · · á1 ,ρ(ζ) = c̀1 · · · c̀m b̀1 · · · b̀k (an = cm ), and ρ(φ) = à1 · · · àn b̀1 · · · b̀j b́j · · · b́1 ćm · · · ć1(j ≤ k). Hence we have |ρ(φ)| ≤ |ρ(ψ)| + |ρ(ζ)|.
However, this bound is not always small, as shown in the following example.
∗

I → XYn

Y0 → àY1 → Y0 Y0...

Yn → Yn−1 Yn−12n  
We can see that I −→ X à · · · à. Therefore, for this grammar to be balanced(e.g., deﬁne rules for X(= Xn ) by X0 → á, X1 → X0 X0 , . . . , Xn → Xn−1 Xn−1 ),∗each φ such that X −→ φ should be at most 2n in length. On the other hand,
the grammar is not balanced if we deﬁne the following rules:∗

X→X → XáX → X b́where Irr(X) = {á, b́}∗ . Unfortunately in checking this unbalancedness, the algorithm by Berstel and Boasson tries to compute subsets of Irr(X) includingwords at most of length 2n , i.e., k≤2n {á, b́}k whose size is doubly exponential
to the size of the grammar.
We can relax this double-exponential behavior to exponential by a small
modiﬁcation to the algorithm. Let be the minimal ordering over À∗ Á∗ satisfyingφ̀φ́ φ̀àáφ́ .
Our idea is simply to compute Irr(X) as far as every two elements are consistent
wrt this ordering, i.e., if φ, φ ∈ Irr(X) then either φφ or φφ. Again∗∗
assume I −→ ψXζ and X −→ φ, φ . By the previous discussion, if ρ(ψφζ) =ρ(ψφ ζ) = , we have both ρ(φ) and ρ(φ ) in the formà1 · · · àn b̀1 · · · b̀j b́j · · · b́1 ćm · · · ć1
3

The depth of derivations to compute ψ and ζ is bounded by the number of nonterminals n of canonical two normal form [Har78] of G where only the productions of
the following forms are allowed: X → Y Z, X → Y , X → a, and X → . Then, thesizes of ψ and ζ are at most 2n .

Input CFG (V, Σ, P, I).
Output BALANCED or NOT BALANCED.
∗
1 For each X ∈ V , let bound (X) = |ρ(ψ)| + |ρ(ζ)| for some I −→ ψXζ.
2 Set Irr[X] = {} for each X ∈ V
3 For each X → γ[X1 , . . . , Xn ] ∈ P where γ[] is a context made from terminal symbols,
and X1 , . . . , Xn are nonterminals.
– For each tuple φ1 , . . . , φn such that each φi ∈ Irr[Xi ],• Let φ = ρ(γ[φ1 , . . . , φn ]). If this φ is undeﬁned, return NOT BALANCED.
• If |φ| > bound (X), return NOT BALANCED.
• If φ  φ nor φ  φ for some φ ∈ Irr[X], return NOT BALANCED.
• Otherwise, update Irr[X] := Irr[X] ∪ {φ}.
4 If some Irr[X] has been updated, go to 3.
5 If Irr[I] = {} then return BALANCED, else return NOT BALANCED.
Fig. 1. The algorithm of balancedness checkwith only j diﬀering. Hence ρ(φ) and ρ(φ ) are always consistent wrt . In otherwords, we can stop the computation of Irr(X) whenever we found an inconsistentelement. We obtain the algorithm in Figure 1 by extending Berstel and Boasson’salgorithm with this additional consistency check.
To observe the complexity improvement, note that is a linear ordering. So
if Irr(X) only has consistent elements wrt , its size is bounded by the maximal
length of strings in Irr(X).
The algorithm presented here still requires exponential time, i.e., 2O(n) -time
where n is the size of the grammar. However, we conjecture that the balancedness check itself is even a PTIME problem. For this, the ﬁrst step is to simplify
the algorithm to check and remember only the maximal element of Irr(X) according to , rather than Irr(X) itself.4 The remaining steps involve the use of
a PTIME algorithm for the equivalence of straight line programs [Pla94]. We
do not explain these details in this paper due to space limitation. Because thebalancedness check is a subproblem of validation, and the complexity of our validation algorithms is exponential or doubly exponential, an improvement here
will be canceled out in the analysis of total complexity.

3

Regular Hedge Grammar Validation

In this section, we give the ﬁrst algorithm of XML validation for CFG. Thisalgorithm determines
L(G) ⊆ L(Greg )where Greg is speciﬁed as a regular hedge grammar. This algorithm runs in doublep(n)exponential-time, i.e., time complexity bounded by 22
for some polynomialp(n), to the size of inputs n.
4

However, Irr(X) as we compute it here is still required in complete qualiﬁcation ofa grammar used in Section 4.

3.1

Regular Hedge Grammar and Binoid

We ﬁrst introduce a ﬁnite algebra called binoid. We believe that a binoid is a
useful algorithmic tool to solve problems related to XML and DTDs. In theory,a binoid is similar to a deterministic tree automaton whose size can grow exponentially if we construct it from a nondeterministic tree automaton. However, as
we will see in the experimentation section, binoids are fairly small for practical
XML schemas. For example, we can construct a ﬁnite binoid for the XHTML
strict DTD with only 58 elements.
Let B(Σ) be a Dyck set, i.e., the set of balanced strings, over Σ. We havethe following proposition.
Proposition 2. (Existence of binoid) For any regular hedge grammar Greg withalphabet Σ, we have a ﬁnite algebra H(Greg ) = (H, ε, F,ˆ( ), ( . )) such that there
is a (homomorphic) mapping ◦ : B(Σ) → H such that(i) ◦ = ε,(ii) (áφà)◦ = â(φ◦ ) for each a ∈ A,(iii) (φψ)◦ = φ◦ .ψ ◦ , and(iv) φ ∈ L(Greg ) iﬀ φ◦ ∈ F .
This algebra H(Greg ) is called a binoid [PQ68]. Similarly to monoids, ( . ) is
associative and ε is its unit. A diﬀerence from monoids is that we now have a
new operator ˆ( ), corresponding to construction of tree node, or enclosure byparentheses. We can construct a binoid from a regular hedge grammar using avariation of the algorithm of tree automata determinization [Toz06].
Example 4. A grammar in Example 2 is captured by the following binoid withthree elements.
H = {η0 , η1 , η }, ε = η0 , F = {η1 },ηkâ(ηk ) = η1 (k = 0)ηk+kb̂(ηk ) =(ηk .ηk ) =η (otherwise)η(k + k  ≤ 1)
(otherwise)

We deﬁne the homomorphism ◦ as φ◦ = ηk if φ is a balanced string containingk occurrences, i.e., 0, 1 or meaning more than one, of pairs of letters b́ and b̀.
We can easily verify the requirements of binoid, e.g., (b́b̀)◦ .(áà)◦ = η1 .η0 = η1 =(b́b̀áà)◦ .
The homomorphism (◦ ) ∈ B(Σ) → H can interpret an arabitrary balanced
word as an element of H so that (1) constructors , vw, and áwà for balanced
words are preserved by corresponding operators ε, ( . ) and ˆ( ), and (2) the
membership for L(Greg ) is preserved by the membership for F . We can judge
whether a set of strings is contained in L(Greg ) without enumerating true stringsin the set, but rather by enumerating elements of H computed by H’s operators.
This is the basic idea behind our algorithm.

3.2

Validation Algorithm

Assume that G = (Σ, V, P, I) deﬁnes a balanced language. We also assume that
we have a ﬁnite binoid H(Greg ) = (H, ε, F,ˆ( ), ( . )) with a homomorphism(◦ ) ∈ B(Σ) → H.
As mentioned, the idea of the algorithm is to interpret a set of strings generated for each nonterminal of G using the algebra H(Greg ). However, each∗string φ such that X −→ φ is not necessarily balanced, but rather partiallybalanced. Therefore, we again use the factorization of φ. Assume that Irr(X) =a`1 a`2 · · · àn án+1 · · · ám . Each φ is factorized as follows:φ = φ1 a`1 φ2 a`2 φ3 · · · àn φn+1 án+1 · · · φm ám φm+1
where φi are balanced strings. Then, assume that a function ν maps a partiallybalanced string φ to ν(φ) ∈ H(ΣH)∗ as follows.
ν(φ) = φ◦1 a`1 φ◦2 a`2 φ◦3 · · · àn φ◦n+1 án+1 · · · φ◦m ám φ◦m+1Here a`1 a`2 · · · àn án+1 · · · ám is a member of Irr(X). Since G is balanced and H is∗
ﬁnite, the set {ν(φ) | X −→ φ} for each X is ﬁnite. Similar to the algorithm of
the balancedness check, we wish to construct this set by induction.
Let us extend ν(φ) to ν(ω) for words ω ∈ (Σ ∪ H)∗ . In the following rewrite
rules, we assume σ, σ  ∈ Σ, υ, ω ∈ (H ∪ Σ)∗ and η, η  ∈ H.
υηηω ⇒ υ(η.η )ω
υáηàω ⇒ υâ(η)ω

υσσ  ω ⇒ υσεσ  ωσω ⇒ εσωωσ ⇒ ωσε⇒εNow ν(ω) is deﬁned as a normal form such that ω ⇒∗ ν(ω) and ν(ω) can nolonger be rewritten by ⇒. Here, the two rules on the left interpret a given
word using H’s operators. The four rules on the right canonicalize the word
by removing all leftmost, rightmost and two successive occurrences of σ, σ  ∈ Σ.
Since the rules on the left never introduce such occurrences of σ and σ  , and they
decrease the length of the word, this rewrite terminates. Similar to the discussionon ρ, we can see that (1) φ◦ = ν(φ) if φ is balanced, and hence ν(φ) ∈ F iﬀ
φ ∈ L(Greg ), and (2) ν(ν(φ)ν(ψ)) = ν(φψ) for partially balanced φ and ψ.
Example 5. Some examples using the binoid given in Example 4.
ν(àáàb́) = η0 à(áà)◦ b́η0 = η0 àη0 b́η0 ,ν(b̀á) = η0 b̀η0 áη0 ,ν(àáàb́b̀à) = ν(ν(àáàb́)ν(b̀á)) = η0 àη0 .b̂(η0 .η0 ).η0 áη0 = η0 àη1 áη0 .
The rest of the algorithm is very close to that of the balancedness check. Thisis given in Figure 2.

Input CFG G = (V, Σ, P, I) deﬁning a balanced language, and binoid H(Greg ) = (H, ε,F,ˆ( ), ( . )).
Output VALID or INVALID.
1 Set Abs[X] = {} for each X ∈ V
2 For each X → γ[X1 , . . . , Xn ] ∈ P where X1 , . . . , Xn are nonterminals.
– For each tuple ω1 , . . . , ωn such that each ωi ∈ Abs[Xi ],• update Abs[X] := Abs[X] ∪ {ν(γ[ω1 , . . . , ωn ])}.
3 If some Abs[X] has been updated, go to 2.
4 If Abs[I] ⊆ F then return VALID else return INVALID.
Fig. 2. The validation algorithm for regular hedge grammars

3.3

Complexity

The dominant factor of the complexity is the size of Abs[X] for each X. The
number of iterations for the outer loop of the algorithm in Fig. 2 is boundedby the number of all pairs (X, ω) such that ω ∈ Abs[X]. The inner loop for
X → γ[X1 , . . . , Xn ] is repeated |P | times, and the innermost for-each is repeated|Abs[X1 ]|×· · · ×|Abs[Xn ]| times. Computing ν(ω) at most requires time polynomial to |ω| log |H|. The maximal length of strings in Irr(X) is bounded by 2O(|G|) .
2
It is known that the size of H obtained from Greg is at most 2O(|Greg | ) . Now for
O(|G|+log |Greg |)each X, the size of Abs[X] is at most Σφ∈Irr(X) |H||φ|+1 , hence 22.
O(|G|+log |Greg |)-time total
The O-notation absorbs all the other factors, giving 22
complexity of the algorithm, which is doubly-exponential to the size of G.

4

XML-Grammar Validation

We develop a validation algorithm of a context-free grammar against an XMLgrammar (or DTD) by exploiting its locality. DTDs and XML-grammars have
locality in the sense that they can only describe a relation between an element(tag) and its children, as we described in the introduction. This locality makes
it possible to decide the inclusion problem L(G) ⊆ L(Gxml ) for a CFG G and an
XML-grammar Gxml by checking local properties. As a result, we can obtain an
XML-grammar validation algorithm with time complexity 2O(|G|+|Gxml |) .
To formalize the idea, we introduce the notion of the trace and the surfacesof a balanced string by Berstel and Boasson [BB02]. Every balanced string φ isuniquely written into the following form:
φ = á1 φ1 à1 á2 φ2 à2 · · · án φn ànwhere φi are balanced strings. The trace of a balanced string picks up only thebase symbol of the toplevel tags. The trace of φ above is the following string.
Trace(φ) = a1 a2 · · · anThe surface of a in φ is deﬁned as:
Sa (φ) = { Trace(ψ) | áψà is a substring of φ and ψ is balanced }This formalizes the set of sequences of tags under the a-tag in φ. For example,` has the following surfaces for a and b.
the string áb́b̀ćc̀àád´dà` = { bc, d }Sa (áb́b̀ćc̀àád´dà)` ={}Sb (áb́b̀ćc̀àád´dà)

By using the surfaces of a string, we can decompose the validation of acontext-free grammar G against Gxml . Consider the following XML-grammar as
an example.
Xa → á(Xa |Xb )(Xa |Xb )à
Xb → b́Xb∗ b̀
For the validation, it is suﬃcient to check the following inclusion relations forthe surfaces of a and b.
Sa (L(G)) ⊆ L((a|b)(a|b))

Sb (L(G)) ⊆ L(b∗ )If we can obtain Sa (L(G)) and Sb (L(G)) as context-free grammars, the inclusion
relations above are decidable since they are inclusion relations between contextfree and regular languages.
We say a context-free grammar is completely balanced if LG (X) is balanced
for every nonterminal of G where LG (X) is the set of strings derivable fromthe nonterminal X. If a context-free grammar is completely balanced, then it isbalanced. The other direction does not necessarily apply.
Example 6. The following grammar is balanced, but it is not completely balanced.
A → áb́B b̀à
B →  | b̀b́B∗where A is a start symbol. It is not completely balanced because B −→ b̀b́, andb̀ and b́ are end and start tags, respectively.
In the remainder of this section, we ﬁrst show that we can compute surfaces if
the grammar is completely balanced and then show that any balanced CFG canbe converted into a completely balanced CFG with the same surfaces. Since thesurfaces are preserved by the conversion, it can be used for validation. However,the language of the obtained completely balanced grammar may not be same asthat of the original grammar.
4.1

Surfaces of a Completely Balanced CFG

We present an algorithm to obtain the surfaces of a completely balanced contextfree grammar. To simplify the presentation, we restrict the format of productionsof a completely balanced CFG to the following forms:
X → áX1 · · · Xn à
X → X1 · · · Xn

It is easy to transform a completely balanced CFG into one with productions
with these forms. From a grammar in this format, it is relatively easy to obtain
the grammars representing its surfaces. The ﬁrst step is to obtain the productions
to produce Trace(LG (X)) for each nonterminal X. Each production in G istransformed as follows:GX → áX1 · · · Xn à ⇒⇒X → X1 · · · Xn

GX→a
X → X1 · · · Xn

The ﬁrst rule just picks up a since the strings derived from X1 · · · Xn are under
the start and end a tags. For example, the productions of the grammar G below
are transformed as follows:GA → áà
B → b́b̀
C →  | ACB
D → ćCc̀ | ćDc̀

⇒
⇒
⇒
⇒

G
A→a
B→b
C →  | ACB
D→c|c

Then, we can construct the context-free grammar representing the surface of
a in G for each a ∈ A. Consider Sc (L(G)) for the grammar G above. For thisgrammar, we have Sc (L(G)) = Trace(C) ∪ Trace(D) because a pair of ć and c̀occurs only in the following two productions.
D → ćCc̀

D → ćDc̀

Therefore, Sc (L(G)) can be represented with a grammar with the following productions:
A→a
D→c
B→b
I→C|D
C →  | ACB
where I is the start symbol. This grammar generates the following language:
Sc (L(G)) = { an bn | n ≥ 0 } ∪ { c }The context-free grammars for Sa (L(G)) and Sb (L(G)) are constructed in thesame manner. Then, we can validate G against an XML-grammar using thesurfaces.
4.2

Transformation into a Completely Balanced CFG

The rest of our validation algorithm is to transform a balanced CFG into acompletely balanced CFG with the same surfaces. This is the most involved
part of the XML-grammar validation algorithm. The following grammar showsthat there is a balanced CFG that cannot be represented with a completely
balanced CFG [Knu67].
I → Aà

A → á | b́b̀Aćc̀This grammar generates { (b́b̀)n á(ćc̀)n à | n ≥ 0 }.
We say that a context-free grammar is completely qualiﬁed if Irr(X) is asingleton for every nonterminal X. Given a balanced CFG G, we can construct
a completely qualiﬁed CFG G where L(G ) = L(G) [Knu67]. Therefore, in thissection, we assume a balanced CFG is completely qualiﬁed and write Irr(X) = φ
if Irr(X) = { φ }.
The transformation we introduce is based on the factorization of partiallybalanced strings. Consider the following factorization of a partially balanced
string φ:
φ ≡ φ1 à1 φ2 à2 φ3 · · · φm àm φm+1 ám+1 φm+2 · · · φn án φn+1
where φi are balanced. We deﬁne the i-th factor Fi (φ) of φ as Fi (φ) = φi .
Let G = (V, Σ, P, I) be a balanced CFG. We construct a completely balanced
CFG G with the same surfaces as follows. For each nonterminal X, we introduce
nonterminals Xi (1 ≤ i ≤ |Irr(X)| + 1). Let V  be the set of nonterminals Xi
introduced above. Then, we deﬁne a function F from V to V  (ΣV  )∗ as follows:
F (X) = X1 a`1 X2 a`1 X3 · · · Xm àm Xm+1 ám+1 Xm+2 · · · Xn án Xn+1
where Irr(X) = a`1 a`2 · · · àm ám+1 · · · án . This function F on nonterminals is naturally extended to a function on (Σ ∪ V )∗ by F (á) = á and F (à) = à for all basesymbol a.
With this function we can expand production X → γ of G as follows.
F (X) → F (γ)
By construction, F (γ) must have the following form:
F (γ) = γ1 a`1 γ2 a`2 γ3 · · · γm àm γm+1 ám+1 γm+2 · · · γn án γn+1
where γi are balanced by considering that nonterminals are balanced. This isbecause G is completely qualiﬁed and thus Irr(γ) = Irr(X). Then, we constructG = (V  , Σ, P  , I1 ) where P  contains the following productions for each production X → γ ∈ P .
Xi → Fi (F (γ))(1 ≤ i ≤ |Irr(X)| + 1)

It is clear that only balanced strings can be derived from each nonterminal Xi in
G since the right-hand side of each production is a balanced factor. Therefore,G is a completely balanced CFG and the following are satisﬁed:
L(G) ⊆ L(G )Sa (G) = Sa (G ) for each a ∈ A
We proved these properties for a CFG G in Chomsky normal form. The ﬁrst
property is easily shown by construction and the second is obtained from thefollowing property:
Trace(LG (Xi )) = Trace(Fi (LG (X)))

An expanded production F (X) → F (γ) above can be considered as a contextsensitive production rule. To obtain a CFG, we split it into several productions
for factors. This is the source of approximation in the transformation.
Example 7. Consider again the following grammar considered by Knuth:
I → Aà

A → á | b́b̀Aćc̀

where Irr(A) = á and Irr(I) = . This grammar generates {(b́b̀)n á(ćc̀)n à | n ≥ 0}.
We have F (A) = A1 áA2 and F (I) = I1 . Therefore, the productions for A are
expanded as follows:
A1 áA2 → á | b́b̀A1 áA2 ćc̀
From F1 (b́b̀A1 áA2 ćc̀) = b́b̀A1 and F2 (b́b̀A1 áA2 ćc̀) = A2 ćc̀, we obtain the following grammar:
I1 → A1 áA2 à

A1 →  | b́b̀A1

A2 →  | A2 ćc̀This grammar generates { (b́b̀)n á(ćc̀)m à | n, m ≥ 0 }. The constraint betweenn and m is lost by the transformation and consequently they do not have thesame language. However, it is clear that it has the same surfaces as those of theoriginal grammar.
4.3

Complexity

Let n and m be the sizes of a balanced CFG G and an XML-grammar Gxml ,respectively. We assume that the length of the right-hand side of a production of
G is at most two. As described in Section 2, both the cardinality of Irr(X) andthe maximal length of strings in Irr(X) are bounded by 2n for every nonterminal
X in G. We deﬁne ι(G) for a balanced CFG G as follows:ι(G) = max { |γ| | γ ∈ Irr(X) for some nonterminal X in G }The ﬁrst step of the validation algorithm is to obtain an equivalent completely
qualiﬁed CFG G1 . We can obtain G1 with at most 22n productions by thetransformation of Knuth [Knu67] in time 2O(n) . The length of the right-handside of a production in G1 is again at most two and ι(G) = ι(G1 ).
The second step is to obtain a completely balanced CFG G2 that has the same
surfaces with G1 . Each nonterminal X with Irr(X) = a`1 a`2 · · · àm ám+1 · · · án in
G1 is translated as follows.
F (X) = X1 a`1 X2 a`1 X3 · · · Xm àm Xm+1 ám+1 Xm+2 · · · Xn án Xn+1
We have |F (X)| = 2|Irr(X)| + 1 ≤ 2ι(G1 ) + 1. A production X → γ in G1 istranslated into the following productions.
Xi → Fi (F (γ))(1 ≤ i ≤ |Irr(X)| + 1)

programs

size
the numbers oftime(sec)
depth Irr(X) nonterminals productions binoid surface
WebCalendar
84102
170 0.0121 0.0492
marktree∞432
54 0.0023 0.0127
phpScheduleIt
15
824
42 0.0062 0.0191
mrtask11
650
70 0.0059 0.0281
Table 1. XHTML validation

It is observed that each production rule is translated into at most ι(G1 ) + 1
production rules and |F (γ)| ≤ 2(2ι(G1 ) + 1) since |γ| ≤ 2. Thus, the size of G2
is bounded by O(22n · ι(G1 )) = O(23n ) and it is obtained in time 2O(n) .
To validate a context-free grammar G2 against an XML-grammar Gxml , weneed to check Sa (G2 ) ⊆ L(Ra ) for each Xa → áRa à in Gxml . The size of thedeterministic automaton for Ra has at most 2m states. Because intersection
emptiness between a context-free grammar and an automaton can be checkedin cubic time, the inclusion relation for each surface can be checked in time
2O(n+m) . Thus, the complexity of the algorithm in total is in 2O(n+m) .

5

Experimental Results

We have implemented our validation algorithms as backend validators of the
PHP string analyzer developed by Minamide [Min05]. The analyzer generatesa CFG that conservatively approximates the string output of a PHP program.
It is available from http://www.score.cs.tsukuba.ac.jp/~minamide/phpsa/.
In our experiments, we checked the validity of Web pages generated by a PHP
program against the XHTML speciﬁcation. However, we ignored attributes inour experiments and only checked the constraints on elements imposed by the
speciﬁcation. As a preliminary step of validation, the analyzer eliminates comments, attributes, and non-tag texts from a CFG and obtains the corresponding
CFG over a paired alphabet. The transformations for this simpliﬁcation are implemented as string transducers.
In our implementation of the validation algorithms, we ﬁrst extract the setof element names appearing in a CFG obtained by the analyzer and delete theelements from the DTD that do not appear in the set. Without this optimization,
it takes approximately 0.2 seconds to construct the binoid for the XHTML DTD
and this dominates validation time in the binoid-based validation.
We applied our validation algorithms to several PHP programs available
from SourceForge and validated the top Web pages generated by them. We repaired several validity bugs in these programs and had to modify the programs
to improve the precision of the analysis. The experiments were performed on aLinux PC with two Opteron processors (2.8 GHz) and 8 GB memory. The CFGs

were validated against XHTML version 1.0 Transitional DTD5 . Table 1 summarizes our experiments. The ﬁrst four columns show the various information
concerning the grammars over a paired-alphabet obtained by the analyzer. We
checked the grammars and found that all the grammars are completely qualiﬁed. The columns ‘depth’ and ‘Irr(X)’ show the maximum nesting depth ofelements (tags) and the maximum size of Irr(X). In the last two columns, thetable shows the validation time for the binoid-based and the surface-based validation algorithms6 . These do not include the time spent in obtaining the CFGs.
These results show that both algorithms are fast enough for common server-side
programs even if they have theoretically exponential complexity. We think that
it is because the size of Irr(X) is small in practice, as shown in the table, and a
regular expression in a content model of DTD must be deterministic.
It is interesting that the binoid-based validation is faster in these experiments
although it has higher complexity. This may be because the implementation of
the binoid-based validation is simpler than that of the surface-based validation.
However, it is also straightforward to write an artiﬁcial program where both of
the algorithms show their exponential behavior. Consider the following program
where $x = $x.$x; $y = $y.$y; is repeated n times.
$x = "<div>"; $y = "</div>";
if (rand()) $x = $x."<p></p>";$x = $x.$x; $y = $y.$y;...
$x = $x.$x; $y = $y.$y;
echo $x; echo $y;
The grammar obtained for this program is completely qualiﬁed and the size ofIrr(·) for the variables $x and $y is in O(2n ). The surface-based algorithm shows
exponential behavior for this program and it takes 1.0, 6.5, and 34.5 seconds tovalidate it for n = 10, 11, 12, respectively. On the other hand, the binoid-basedalgorithm shows doubly exponential behavior for this program because of the
if-statement in the program and can validate it only when n ≤ 5.

6

Related Work

The PHP string analyzer originally supported only the inclusion checking between a CFG and a regular expression [Min05]. This checking can partially support validation of dynamically generated Web pages by restring their depth. It
is because the set of valid Web pages can be described with a regular language
if we restrict their depth. The algorithms in this paper give more direct andgeneral solutions to the problem.
5

The content model (r)+ was interpreted as (r)∗ in the experiments to circumvent
imprecision due to analysis of loops in a program.
6
We measured the time spent to validate a CFG 100 times. The table shows anaverage time calculated from the total time.

The XML validation algorithms presented in this paper depend on previous
work on context-free grammars over languages with parentheses. A parenthesis grammar is a context-free grammar over a language with a single pair ofparentheses where each production has the form of A → (θ) where θ does notcontain parentheses. McNaughtotn showed that equivalence of parenthesis grammars is decidable [McN67]. Knuth extended the result and showed that there
exists an algorithm to determine whether a context-free grammar is a parenthesis language [Knu67]. Berstel and Boasson extended the theory of context-freegrammars over languages with parentheses to study the language described by
a DTD [BB02]. In this paper, we have developed a surface-based validation algorithm by exploiting their results that the language of an XML-grammar has
locality and can be characterized by its surfaces, and the regular hedge grammar
validation based on their algorithm for checking balancedness of a context-freelanguage.
Extensive studies have been done in tree-based validation of dynamically generated HTML/XML documents [CMS03a,HP03,HVP05]. The motivation of thework is the same as ours, but the validation algorithms developed in these works
cannot be directly applied to our setting of string-based validation. As shownin Section 4, we can retrieve a tree-based language for a balanced CFG withthe approximation preserving surfaces of the language. Thus, after the transformation, the methods for tree-based validation can be applied in principle.
Brabrand, Møller, and Schwartzbach proposed summary graphs to approximate
the set of dynamically generated XHTML documents [BMS01]. Although summary graphs can express constraints on attributes, they basically correspond tocompletely balanced CFGs. The validation of a completely balanced CFG canbe considered as a variant of their validation algorithm for summary graphs.

7

Conclusion

We have presented two new algorithms validating a context-free grammar against
a regular hedge grammar and an XML-grammar. Although both have exponential complexity, it is shown that they are eﬃcient in practice. Our validation
algorithms for regular hedge grammars and XML-grammars have doubly exponential and exponential time complexity. We plan to establish the lower bounds
for these validation problems. For simpler problems, it is known that the inclusion problems for regular expressions and regular hedge grammars are PSPACEcomplete and EXPTIME-complete, respectively. However, gaps remain between
the results and the complexity of our algorithms.
We have considered validation against a subclass of balanced context-freegrammars, such as XML-grammars and regular hedge grammars, but legacy
server-side programs generate HTML, which is not in XML format. In order tovalidate those Web pages, we need to consider validation against a grammarthat has an unbalanced language. Although the inclusion problem between twocontext-free grammars is undecidable in general, we think that it is possible tovalidate a context-free grammar against the HTML speciﬁcation because it isdesigned to be unambiguous and where end tags are omitted can be determined.

References[BB02]

Jean Berstel and Luc Boasson. Formal properties of XML grammars andlanguages. Acta Informatica, 38(9):649–671, 2002.
[BMS01] Claus Brabrand, Anders Møller, and Michael I. Schwartzbach. Static validation of dynamically generated HTML. In Proceedings of the 2001 ACM
SIGPLAN-SIGSOFT Workshop on Program Analysis For Software Tools
and Engineering, pages 38–45, 2001.
[CM01] J. Clark and M. Murata. RELAX NG speciﬁcation, 2001. http://www.oasisopen.org/committees/relax-ng/spec.
[CMS03a] Aske Simon Christensen, Anders Møller, and Michael I. Schwartzbach. Extending Java for high-level web service construction. ACM Transactions on
Programming Languages and Systems, 25(6):814–875, 2003.
[CMS03b] Aske Simon Christensen, Andres Møller, and Michael I. Schwartzbach. Precise analysis of string expressions. In Proceedings of the Static Analysis
Symposium (SAS), volume 2694 of LNCS, pages 1–18, 2003.
[GF80]
Sheila A. Greibach and Emily P. Friedman. Superdeterministic PDAs: A
subcase with a decidable inclusion problem. Journal of the Association for
Computing Machinery, 27(4):675–700, 1980.
[Har78] Michael A. Harrison. Introduction to Formal Language Theory, chapter 4.
Addison-Wesley, 1978.
[HP03]
Haruo Hosoya and Benjamin Pierce. XDuce: A statically typed XML processing language. ACM Transactions on Internet Technology, 3(2):117–148,
2003.
[HVP05] Haruo Hosoya, Jérôme Vouillon, and Benjamin Pierce. Regular expression
types for XML. ACM Transactions on Programming Languages and Systems,
27(1):46–90, 2005.
[Knu67] Donald E. Knuth. A characterization of parenthesis languages. Information
and Control, 11(3):269–289, 1967.
[McN67] Robert McNaughton. Parenthesis grammars. Journal of the Association for
Computing Machinery, 14(3):490–500, 1967.
[Min05] Yasuhiko Minamide. Static approximation of dynamically generated Web
pages. In Proceedings of the 14th International World Wide Web Conference,
pages 432–441. ACM Press, 2005.
[Mur99] Makoto Murata. Hedge automata: a formal model for XML schemata, 1999.
http://www.xml.gr.jp/relax/hedge nice.html.
[Pla94]
Wojciech Plandowski. Testing equivalence of morphisms on context-freelanguages. In Algorithms – ESA ’94 (Utrecht), volume 855 of LNCS, pages
460–470. Springer, 1994.
[PQ68]
C. Pair and A. Quere. Déﬁnition et étude des bilangages réguliers. Information and Control, 13(6):565–593, Dec 1968.
[Tak75] Masako Takahashi. Generalizations of regular sets and their application to a
study of context-free languages. Information and Control, 21(1):1–36, 1975.
[Toz06] Akihiko Tozawa. XML type checking using high-level tree transducer. In
Functional and Logic Programming, 8th International Symposium, FLOPS
2006, pages 81–96, 2006.