Niech Σ będzie niepustym, skończonym zestawem symboli, zwanym alfabetem . Wówczas Σ * jest policzalnym nieskończonym zbiorem skończonych słów, które można utworzyć przez połączenie zero lub więcej symboli z Σ. Każdy dobrze zdefiniowany podzbiór L ⊆ Σ * jest językiem .
Zastosujmy to do XML. Jego alfabet jest Unicode zestaw znaków U , który jest niepusty i skończony. Nie każda kombinacja zerowego lub więcej znaków Unicode jest dobrze sformułowanym dokumentem XML, na przykład ciągiem znaków
<tag> soup &; not <//good>
wyraźnie nie jest. Podzbiór XML ⊂ U *, który tworzy dobrze sformułowane dokumenty XML, jest rozstrzygalny (lub „rekurencyjny”). Istnieje maszyna (algorytm lub program komputerowy), która przyjmuje jako dane wejściowe dowolne słowo w ∈ U * i po skończonym czasie wyprowadza 1, jeśli w ∈ XML i 0 w przeciwnym razie. Taki algorytm jest podprogramem każdego oprogramowania przetwarzającego XML. Nie wszystkie języki są rozstrzygalne. Na przykład zestaw prawidłowych programów C, które kończą się w skończonym czasie, nie jest (jest to znane jako problem zatrzymania). Kiedy projektuje się nowy język, ważną decyzją jest podjęcie decyzji, czy powinien on być tak potężny, jak to możliwe, czy też ekspresja powinna być ograniczona na korzyść rozstrzygalności.
Niektóre języki mogą być definiowane za pomocą gramatyki , że mówi się produkować język. Gramatyka składa się z
- skończony zestaw literałów (zwanych także symbolami terminalnymi ),
- odłączony skończony zestaw zmiennych gramatyki (zwany również nie końcowych symbole)
- wyróżniający się symbol początkowy , wzięty z zestawu zmiennych i
- skończony zestaw zasad (tzw. produkcje ), które pozwalają na pewne rodzaje zamienników.
Każde słowo, które składa się wyłącznie z literałów i można je uzyskać, zaczynając od symbolu początkowego, a następnie stosując podane reguły, należy do języka tworzonego przez gramatykę.
Na przykład następująca gramatyka (w raczej nieformalnym zapisie) pozwala uzyskać dokładnie liczby całkowite w zapisie dziesiętnym.
- W literały z gramatyki są cyfry
1
, 2
, 3
, 4
, 5
, 6
, 7
, 8
, 9
, i 0
.
- Te zmienne symbole S i D .
- S jest symbolem początkowym.
- Każde wystąpienie zmiennej S może zostać zastąpione
- z literałem
0
lub
- dowolnymi literałach innych niż
0
następuje zmiennej D .
- Każde wystąpienie zmiennej D może zostać zastąpione
- przez dowolny literał, po którym następuje kolejne wystąpienie zmiennej D lub
- przez pusty ciąg.
Oto, w jaki sposób otrzymujemy 42
:
S - (zastosowanie zasada 4 2 ND wariant) → 4
D - (zastosowanie zasada 5, 1 st wariant) → 42
D - (zastosowanie zasada 5, 2 nd wariant) → 42
.
W zależności od skomplikowanych reguł, na jakie zezwalasz w gramatyce, wymagane są różne zaawansowane maszyny do udowodnienia, że gramatyka może wytworzyć dane słowo. Powyższy przykład to zwykła gramatyka, która jest najprostsza i najmniej potężna. Następna potężna klasa gramatyk nosi nazwę kontekstu . Te gramatyki są również bardzo łatwe do zweryfikowania. XML (chyba że przeoczę jakąś niejasną funkcję, o której nie wiem) można opisać gramatyką bezkontekstową. Klasyfikacja gramatyki stanowi Chomską Hierarchię gramatyki (a zatem języków). Każdy język, który można opisać gramatyką, jest co najmniej częściowo rozstrzygalny(lub „rekurencyjnie wyliczalne”). Oznacza to, że istnieje maszyna, która biorąc pod uwagę słowo, które faktycznie należy do języka, uzyskuje dowód, że gramatyka może ją wytworzyć w skończonym czasie i nigdy nie przedstawi złego dowodu. Taka maszyna nazywa się weryfikatorem . Zauważ, że maszyna nigdy nie może się zatrzymać, gdy otrzyma słowo, które w rzeczywistości nie należy do języka. Oczywiście chcemy, aby nasze języki programowania były opisywane przez słabsze gramatyki, aby móc odrzucić nieprawidłowe programy w określonym czasie.
Schematy są dodatkiem do XML, który pozwala udoskonalić zestaw poprawnie sformułowanych dokumentów. Dobrze sformułowany dokument zgodny z określonym schematem nazywa się ważny zgodnie z tym schematem. Na przykład ciąg
<?xml version="1.0" encoding="utf-8" ?>
<root>all evil</root>
jest poprawnie sformułowanym dokumentem XML, ale nie jest prawidłowym dokumentem XHTML. Istnieją schematy dla XHTML , SVG , XSLT i nie tylko. Sprawdzanie poprawności schematu można również wykonać za pomocą algorytmu, który gwarantuje zatrzymanie po skończonej liczbie kroków dla każdego wejścia. Taki program nazywa się walidatorem lub parserem sprawdzającym poprawność. Schematy są definiowane przez tak zwane języki definicji schematu , które są formalnym sposobem definiowania gramatyki. XSD jest oficjalnym językiem definicji schematów dla XML i jest oparty na XML. RELAX NG jest bardziej elegancką, znacznie prostszą i nieco mniej wydajną alternatywą dla XSD.
Ponieważ możesz definiować własne schematy, XML jest nazywany rozszerzalnym językiem, który jest początkiem „X” w „XML”.
Możesz zdefiniować zestaw reguł, które będą interpretować dokumenty XML jako opisy programów komputerowych. Wspomniany wcześniej XSLT jest przykładem takiego języka programowania zbudowanego przy pomocy XML. Mówiąc bardziej ogólnie, można serializować abstrakcyjne drzewo składniowe prawie każdego języka programowania całkiem naturalnie do XML, jeśli tego właśnie chcesz.