Giới thiệu về Ngữ pháp

n theo nghĩa văn học của thuật ngữ, ngữ pháp biểu thị các quy tắc cú pháp để hội thoại trong ngôn ngữ tự nhiên. Ngôn ngữ học đã cố gắng xác định ngữ pháp kể từ khi ra đời các ngôn ngữ tự nhiên như tiếng Anh, tiếng Phạn, tiếng Quan Thoại, v.v.

Lý thuyết về các ngôn ngữ hình thức có khả năng ứng dụng rộng rãi trong các lĩnh vực Khoa học Máy tính. Noam Chomsky đã đưa ra một mô hình toán học về ngữ pháp vào năm 1956 hiệu quả để viết ngôn ngữ máy tính.

Ngữ pháp

Một ngữ pháp G có thể được viết chính thức dưới dạng 4 bộ (N, T, S, P) trong đó -

N hoặc là V_N là một tập hợp các biến hoặc các ký hiệu không đầu cuối.
T hoặc là ∑ là một tập hợp các ký hiệu Terminal.
S là một biến đặc biệt được gọi là ký hiệu Bắt đầu, S ∈ N
Plà Quy tắc sản xuất cho Thiết bị đầu cuối và Thiết bị đầu cuối. Một nguyên tắc sản xuất có dạng α → β, nơi α và β là chuỗi trên V _N ∪ Σ và một biểu tượng nhất của α thuộc về V _N .

Thí dụ

Ngữ pháp G1 -

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

Đây,

S, A, và B là các ký hiệu không đầu cuối;
a và b là các ký hiệu đầu cuối
S là ký hiệu Bắt đầu, S ∈ N
Sản xuất, P : S → AB, A → a, B → b

Thí dụ

Ngữ pháp G2 -

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

Đây,

S và A là các ký hiệu không đầu cuối.
a và b là các ký hiệu đầu cuối.
ε là một chuỗi rỗng.
S là ký hiệu Bắt đầu, S ∈ N
Sản xuất P : S → aAb, aA → aaAb, A → ε

Nguồn gốc từ ngữ pháp

Các chuỗi có thể được bắt nguồn từ các chuỗi khác bằng cách sử dụng các sản phẩm trong một ngữ pháp. Nếu một ngữ phápG có một sản xuất α → β, chúng ta có thể nói về điều đó x α y dẫn xuất x β y trong G. Dẫn xuất này được viết là -

x α y ⇒G x β y