Какой класс формального языка представляет собой XML и JSON с уникальными ключами?

Я переместил этот вопрос из stackoverflow, где id не получил ответов. У нас был похожий вопрос , является ли JSON регулярным :

JSON и XML часто называют языками без контекста - они оба определяются в основном формальной грамматикой в ​​EBNF. Однако это верно только для JSON, как определено в RFC 4329, раздел 2.2, который не требует уникальности ключей объекта (многие могут не знать, но {"a": 1, "a": 2} является допустимым JSON!). Но если вам требуются уникальные ключи в JSON или уникальные имена атрибутов в XML, это не может быть выражено безконтекстной грамматикой. Но какой класс языка JSON с уникальными ключами и для правильно сформированного XML (что подразумевает уникальные имена атрибутов?).

Одна из лучших работ по этой теме, которую я нашел (Murato и др., 2001: Таксономия языков XML-схем с использованием теории формального языка ), явно исключает ограничения целостности, такие как ключи / keyrefs и уникальность, которые нужно проверять на дополнительном слое. Кроме того, подмножество XML, определенное схемой XML или DTD, не зависит от контекста. Но не полный набор всех правильно оформленных XML-документов.

Я думаю, что вложенный стек стека (= индексированный язык) должен иметь возможность анализировать JSON с ограничением уникального ключа. Для XML можно упростить вопрос к языку S из всех разделенных запятыми списков уникальных целых чисел. Кто-нибудь знает больше, желательно с цитатами?

PS: простой алгоритм для определения языков (кроме контекстно-свободной части) основан на хорошем алгоритме сортировки. Следовательно, оно должно быть разрешимо в «линейное время» с O (n log n) наихудшим случаем. Я еще не выяснил, является ли класс сложности, например, «слегка контекстно-зависимым» или «индексированным», но, вероятно, что-то между контекстно-свободным и контекстно-зависимым (?).

x := a+ $\Leftrightarrow$ x := a | x a^a^a

Использование BNF с вашим оператором уникального повторения x := S^говорит о том , что это xэкземпляр aсимвола S, за которым необязательно следует экземпляр bнабора S - a, за самим собой необязательно следует экземпляр cнабора S - a - bи т. Д. Если |S|число возможных Sи конечно, то 2 ^ |S|! - 1число возможных S^.

В действительности не имеет смысла говорить с точки зрения вычислительной мощности описываемого языка, поскольку речь идет о статической семантике, в сумерках между синтаксисом и обычной (динамической) семантикой. Выразительная сила грамматики расширена, поскольку она имеет формальные средства выражения определенного типа адаптации ввода.

В частности, он предоставляет средство принятия перестановки подмножества определенного набора. Я не думаю, что существует какое-либо существующее название для этого класса языка. Это, конечно, не является контекстно-свободным, но контекстное требование, по крайней мере, довольно строго контролируется. Если вам нужен термин для этого, просто монета один. Я предлагаю соблюдение контекста для класса языков, которые не могут быть описаны с помощью контекстно-свободной грамматики без дополнительной встроенной информации о статических семантических ограничениях, которые, если честно, имеют смутно синтаксический характер.

Наиболее полезным применением этого конкретного расширения, вероятно, является просто возможность введения ограничений уникального ключа, но оно также позволяет описывать такие интересные наборы как x := [0-7]^, которые соответствуют любому восьмеричному числу из 8 или менее неповторяющихся цифр. Что касается его сложности, то определение того, был ли элемент набора замечен, не хуже логарифмического, а частота проверки линейна по числу сопоставляемых элементов, поэтому ^оператор действительно разрешим в линеарифическом времени наихудшего случая.