15
$\begingroup$

I moved this question from stackoverflow where id got no answers. We had a similar question whether JSON is regular:

JSON and XML are both frequently called to be context-free languages - they are both specified mainly by a formal grammar in EBNF. However this is only true for JSON as defined in RFC 4329, section 2.2 which does not require uniqueness of object keys (many may not know but {"a":1,"a":2} is valid JSON!). But if you require unique keys in JSON or unique attribute names in XML this cannot be expressed by a context-free grammars. But which is the language class of JSON with unique keys and for well-formed XML (which implies unique attribute names?).

One of the best paper I found on this subject (Murato et al, 2001: Taxonomy of XML Schema Languages using Formal Language Theory) explicitly excludes integrity constraints such as keys/keyrefs and uniqueness to be checked on an additional layer. Beside this the subset of XML defined by an XML Schema or by a DTD is context-free. But not the full set of all well-formed XML documents.

I think a nested stack automaton (=indexed language) should be able to parse JSON with unique key constraint. For XML can simlify the question to the language S of all comma-separated lists of unique integers. Does anyone know more, preferably with citations?

P.S: A simple algorithm to decide the languages (beside the context-free part) is based on a good sorting algorithm. Therefore it should be decidable in "linearithmic time" with O(n log n) worst case. I have not found out yet, whether the complexity class is for instance "mildly context-sensitive", or "indexed" but probably something between context-free and context-sensitive (?).

EDIT: Maybe I better reformulate the question for the more theoretical computer scientists. Given the class CFL of all languages that can be expressed by Backus-Naur-Form with repetition (x := a+ $\Leftrightarrow$ x := a | x a). Now what do I gain in computational power if I introduce a "repetition with unique instances" operator ^, so a^ is a sequence of a where each element results in a different sequence of terminals?

Improve this question
$\endgroup$
11
  • $\begingroup$ JSON with repeatable object keys is context-free (see JSON grammar), but how do you express the unique key constraint in a common grammar or automaton? Or: Which complexity class belongs an XML parser to, if it can detect the set of all well-formed XML documents (well-formed implies unique attribute names per element). $\endgroup$
    – Jakob
    Jan 31, 2011 at 14:26
  • 1
    $\begingroup$ Using compiler generator terms here. The respective syntax of both JSON and XML is certainly context-free. Properties like unique identifiers or value type restrictions are static semantics (some people call this syntax, too, but I reject that nomenclature for several reasons). Parser generators usually allow you to enrich a common parser by things like syntactic/semantic predicates that need not be context-free. In theory, attributed grammars are used. I don't know wether such features can be naturally expressed with formal grammars of any power. $\endgroup$
    – Raphael
    Jan 31, 2011 at 14:55
  • 1
    $\begingroup$ Which parts of a formal language goes beyond syntax, depends on the viewpoint. Simple nested structures like XML and JSON can be parsed by a pushdown automaton. I just want to know, which computable power you get, if the automaton is enriched with a dictionary to look up whether a stored value has been read before, to ensure the uniqueness constraint. I'd guess its an indexed grammar (a nested stack automaton?) but there are several kinds of indexed grammars. $\endgroup$
    – Jakob
    Jan 31, 2011 at 15:38
  • $\begingroup$ @Jakob, I'd fold this discussion (abbreviated) into the question so it's clear exactly what you're asking $\endgroup$
    – Suresh Venkat
    Jan 31, 2011 at 17:09
  • $\begingroup$ An LBA should be sufficient since you will never have to store more identifiers than you have characters in your text. I do not know enough about classes between CFL and CSL to be of help there. $\endgroup$
    – Raphael
    Feb 1, 2011 at 9:31

1 Answer 1

Reset to default
7
$\begingroup$

Using BNF with your unique-repetition operator, x := S^ says that an x is an instance a of symbol S, optionally followed by an instance b of set S - a, itself optionally followed by an instance c of set S - a - b, and so forth. If |S| is the number of possible S, and is finite, then 2 ^ |S|! - 1 is the number of possible S^.

It's not really meaningful to talk in terms of the computational power of the language being described, since this is about static semantics, in the twilight between syntax and ordinary (dynamic) semantics. The expressive power of the grammar is extended, since it has a formal means of expressing a particular type of input adaptation.

Specifically, it provides a means of accepting a permutation of a subset of a particular set. I don't think there is any existing name for this class of language. It's certainly not context-free, but the context requirement is at least pretty strictly controlled. If you need a term for it, just coin one. I suggest context-respecting for the class of languages that cannot be described by a context-free grammar without additional embedded information about static semantic constraints, which to be fair are vaguely syntactic in spirit.

The most useful application of this particular extension is probably just the ability to introduce unique-key constraints, but it also lets you describe such interesting sets as x := [0-7]^, which matches any octal number of 8 or fewer non-repeated digits. As for the complexity of it, determining whether an element of the set has been seen is no worse than logarithmic, and the frequency of checking is linear in the number of elements matched, so the ^ operator is indeed decidable in worst-case linearithmic time.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the answer and for the hint to think in permutations of a subset. Although the unique-repetition operator does not catch key-value pairs with unique keys, the complexity should be the same for this cases. However, if I start to apply the operator on arbitrary structures, the class S^ where S is some CFL may be get non-context-free because CFLs are not closed under difference. It should be doable if S is a regular language, but unfortunately you cannot decide whether a given CFL is regular. Maybe I'll raise another question as this is beyond the constraints of JSON and XML. $\endgroup$
    – Jakob
    Feb 7, 2011 at 8:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.