Czy JSON jest językiem zwykłym?

Zastanawiałem się, czy specyfikacja JSON definiuje zwykły język. Wydaje się to dość proste, ale nie jestem pewien, jak sam to udowodnić.

Powodem, dla którego pytam, jest to, że zastanawiałem się, czy można użyć wyrażeń regularnych, aby skutecznie przetworzyć JSON.

Czy ktoś z wystarczającą liczbą przedstawicieli może dla mnie utworzyć tagi json i zwykły język ?

fl.formal-languages regular-expressions regular-language jjnguy
źródło

Usunąłem tag [json], ponieważ nie wydaje się on wart tagu w TCS SE.

Tsuyoshi Ito,

@Tsuy, brzmi dobrze. Oczywiście nie jestem zapalonym użytkownikiem strony, więc jestem pewien, że wiesz lepiej.

jjnguy

Pamiętaj, że implementacje wyrażeń regularnych często pasują do więcej niż zwykłych języków. Na przykład można użyć lookaheads w większości implementacji, które przyjmą

prawidłowo, rozwiązując

problemów inni wymienionych poniżej.

a^{n} b^{n}

$a^nb^n$

[^{n} x]^{n}

$[^nx]^n$

Xodarap,

Odpowiedzi:

Ponieważ nie jest językiem regularnym, JSON również nie jest, ponieważ jest poprawnym wejściem dla dowolnego . Podobnie, twój parser wyrażeń regularnych musiałby poprawnie odrzucać wszelkie dane wejściowe gdzie których nie możesz zrobić z wyrażeniami regularnymi. $a^n b^n$ $[^n 5 ]^n$ $n$ $[^m 4 ]^n$ $m \ne n$

Dlatego JSON nie jest regularny.

RegexFan
źródło

Ciekawe, jaka jest tutaj notacja w indeksie górnym / nawiasie?

jchook

@jchook Notacja w indeksie górnym oznacza „powtórzony”. Więc

byłoby

powtarzane

razy. Podobnie notacja

oznacza

powtórzone

razy. Nawiasy nie mają specjalnego znaczenia. Zwykły język nie może „policzyć”, ile nawiasów znajduje się po każdej stronie, więc nie może stwierdzić, czy obie strony mają taką samą liczbę nawiasów.

a^{n}

$a^n$

a

$a$

n

$n$

[^{n}

$[^n$

[

$[$

n

$n$

Nick ODell,

Nie, to nie jest regularne. Ponieważ pozwala na dowolne osadzanie zrównoważonych ograniczników, musi być przynajmniej pozbawione kontekstu.

Weźmy na przykład tablicę tablic tablic:

[ [ [ 1, 2], [2, 3] ] , [ [ 3, 4], [ 4, 5] ] ]

Oczywiście nie można tego przeanalizować za pomocą prawdziwych wyrażeń regularnych.

Marc Hamann
źródło

Aby tępo podzielić włosy, reprezentacje JSON wszystkich tablic tablic tablic liczb całkowitych są regularne.

Charles Stewart

Następnie dodawaj rekurencyjnie „tablice”, aż będziesz zadowolony. ;-)

Marc Hamann

Standardowy JSON jest bezkontekstowy, ale większość implementacji obsługuje tylko unikalne klucze. Przeniosłem moje pytanie bez odpowiedzi z stackoverflow do: cstheory.stackexchange.com/questions/4668/…

Jakob

Zauważ, że powiedziałem „przynajmniej bez kontekstu”.

Marc Hamann

Rozwijając komentarz @ CharlesStewart, czy to oznacza, że „JSON o ścisłej maksymalnej głębokości JEST zwykłym językiem”? A może inne funkcje JSON temu zapobiegają?

jchook