Wprowadzenie do gramatyki

W sensie literackim tego terminu gramatyki oznaczają reguły składniowe konwersacji w językach naturalnych. Językoznawstwo próbowało zdefiniować gramatykę od czasu powstania języków naturalnych, takich jak angielski, sanskryt, mandaryński itp.

Teoria języków formalnych znajduje szerokie zastosowanie w dziedzinie informatyki. Noam Chomsky przedstawił matematyczny model gramatyki w 1956 roku, który jest skuteczny w pisaniu języków komputerowych.

Gramatyka

Gramatyka G można formalnie zapisać jako 4-krotkę (N, T, S, P), gdzie -

N lub V_N jest zbiorem zmiennych lub symboli nieterminalnych.
T lub ∑ to zestaw symboli terminala.
S to specjalna zmienna nazywana symbolem Start, S ∈ N
Pto Zasady produkcji dla terminali i terminali. Zasada produkcja ma postać α → p, gdzie α i β są struny V _N ∪ Ď i co najmniej jeden symbol α należy do V _N .

Przykład

Gramatyka G1 -

({S, A, B}, {a, b}, S, {S → AB, A → a, B → b})

Tutaj,

S, A, i B są symbolami nieterminowymi;
a i b to symbole terminala
S to symbol startu, S ∈ N
Produkcje, P : S → AB, A → a, B → b

Przykład

Gramatyka G2 -

(({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε})

Tutaj,

S i A są symbolami nieterminowymi.
a i b to symbole terminala.
ε jest pustym ciągiem.
S to symbol startu, S ∈ N
Produkcja P : S → aAb, aA → aaAb, A → ε

Wyprowadzenia z gramatyki

Łańcuchy mogą pochodzić z innych ciągów przy użyciu produkcji w gramatyce. Jeśli gramatykaG ma produkcję α → β, możemy to powiedzieć x α y pochodzi x β y w G. To wyprowadzenie jest zapisane jako -

x α y ⇒G x β y