Giới thiệu ngữ pháp không theo ngữ cảnh

Definition - Ngữ pháp không có ngữ cảnh (CFG) bao gồm một tập hợp hữu hạn các quy tắc ngữ pháp là một bộ tứ (N, T, P, S) Ở đâu

N là một tập hợp các ký hiệu không phải đầu cuối.
T là một tập hợp các thiết bị đầu cuối mà N ∩ T = NULL.
P là một tập hợp các quy tắc, P: N → (N ∪ T)*, tức là, mặt trái của quy tắc sản xuất P không có bất kỳ ngữ cảnh bên phải hoặc bên trái.
S là biểu tượng bắt đầu.

Example

Văn phạm ({A}, {a, b, c}, P, A), P: A → aA, A → abc.
Văn phạm ({S, a, b}, {a, b}, P, S), P: S → aSa, S → bSb, S → ε
Văn phạm ({S, F}, {0, 1}, P, S), P: S → 00S | 11F, F → 00F | ε

Thế hệ cây phát sinh

Cây dẫn xuất hoặc cây phân tích cú pháp là một cây gốc có thứ tự biểu thị bằng đồ thị thông tin ngữ nghĩa của một chuỗi có nguồn gốc từ ngữ pháp không có ngữ cảnh.

Kỹ thuật đại diện

Root vertex - Phải được gắn nhãn bằng ký hiệu bắt đầu.
Vertex - Được gắn nhãn bằng ký hiệu không phải đầu cuối.
Leaves - Được gắn nhãn bằng ký hiệu đầu cuối hoặc ε.

Nếu S → x ₁ x ₂ …… x _n là quy tắc sản xuất trong CFG, thì cây phân tích cú pháp / cây dẫn xuất sẽ như sau:

Có hai cách tiếp cận khác nhau để vẽ một cây dẫn xuất -

Top-down Approach −

Bắt đầu với ký hiệu bắt đầu S
Đi xuống lá cây bằng cách sử dụng các sản phẩm

Bottom-up Approach −

Bắt đầu từ lá cây
Tiến lên gốc là biểu tượng bắt đầu S

Nguồn gốc hoặc sản lượng của cây

Dẫn xuất hoặc sản lượng của cây phân tích cú pháp là chuỗi cuối cùng thu được bằng cách nối các nhãn của các lá cây từ trái sang phải, bỏ qua các Null. Tuy nhiên, nếu tất cả các lá là Null, dẫn xuất là Null.

Example

Giả sử một CFG {N, T, P, S} là

N = {S}, T = {a, b}, Ký hiệu bắt đầu = S, P = S → SS | aSb | ε

Một dẫn xuất từ CFG ở trên là "abaabb"

S → SS → aSbS → abS → abaSb → abaaSbb → abaabb

Biểu mẫu thông tin và cây dẫn xuất một phần

Cây dẫn xuất một phần là cây con của cây dẫn xuất / cây phân tích cú pháp sao cho tất cả các cây con của nó đều nằm trong cây con hoặc không cây nào trong số chúng nằm trong cây con.

Example

Nếu trong bất kỳ CFG nào, sản phẩm sẽ -

S → AB, A → aaA | ε, B → Bb | ε

cây dẫn xuất một phần có thể như sau:

Nếu một cây dẫn xuất một phần chứa gốc S, nó được gọi là sentential form. Cây con ở trên cũng ở dạng gửi.

Xuất phát ngoài cùng bên trái và ngoài cùng bên phải của một chuỗi

Leftmost derivation - Đạo hàm ngoài cùng bên trái thu được bằng cách áp dụng sản xuất cho biến ngoài cùng bên trái trong mỗi bước.
Rightmost derivation - Một suy ra ngoài cùng bên phải thu được bằng cách áp dụng sản xuất cho biến ngoài cùng bên phải trong mỗi bước.

Example

Hãy để bất kỳ bộ quy tắc sản xuất nào trong CFG được

X → X + X | X * X | X | a

qua bảng chữ cái {a}.

Dẫn xuất ngoài cùng bên trái của chuỗi "a+a*a" có thể là -

X → X + X → a + X → a + X * X → a + a * X → a + a * a

Dẫn xuất từng bước của chuỗi trên được hiển thị như sau:

Dẫn xuất ngoài cùng bên phải cho chuỗi trên "a+a*a" có thể là -

X → X * X → X * a → X + X * a → X + a * a → a + a * a

Dẫn xuất từng bước của chuỗi trên được hiển thị như sau:

Ngữ pháp đệ quy trái và phải

Trong ngữ pháp không có ngữ cảnh G, nếu có sản xuất ở dạng X → Xa Ở đâu X không phải là thiết bị đầu cuối và ‘a’ là một chuỗi các thiết bị đầu cuối, nó được gọi là left recursive production. Ngữ pháp có sản xuất đệ quy bên trái được gọi làleft recursive grammar.

Và nếu trong ngữ pháp không có ngữ cảnh G, nếu có sản xuất thì ở dạng X → aX Ở đâu X không phải là thiết bị đầu cuối và ‘a’ là một chuỗi các thiết bị đầu cuối, nó được gọi là right recursive production. Ngữ pháp có sản xuất đệ quy đúng được gọi làright recursive grammar.