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 VN 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

Przykład

Rozważmy gramatykę -

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

Niektóre z ciągów, które można wyprowadzić, to:

S ⇒ aA b używając produkcji S → aAb

⇒ a aA bb używając produkcji aA → aAb

⇒ aaa A bbb przy użyciu produkcji aA → aAb

⇒ aaabbb używając produkcji A → ε