0.3 Văn phạm phi ngữ cảnh  (Page 2/17)

<expression>::=<expression>+<expression>

<expression>::=<expression>*<expression>

<expression>::= (<expression>)

<expression>::=<identifier>

Việc nghiên cứu các văn phạm phi ngữ cảnh đã tạo nên một cơ sở lý luận vững chắc cho việc biểu diễn ngôn ngữ lập trình, việc tìm kiếm các giải thuật phân tích cú pháp vận dụng trong chương trình dịch và cho nhiều ứng dụng khác về xử lý chuỗi. Chẳng hạn, nó rất hữu ích trong việc mô tả các biểu thức số học với nhiều dấu ngoặc lồng nhau hoặc cấu trúc khối trong ngôn ngữ lập trình mà biểu thức chính quy không thể đặc tả.

Định nghĩa

Văn phạm phi ngữ cảnh là một tập hợp hữu hạn các biến (còn gọi là các ký hiệu chưa kết thúc), mỗi biến biểu diễn một ngôn ngữ. Ngôn ngữ được biểu diễn bởi các biến được mô tả một cách đệ quy theo thuật ngữ của một khái niệm khác gọi là ký hiệu kết thúc. Quy tắc quan hệ giữa các biến gọi là luật sinh. Mỗi luật sinh có dạng một biến ở vế trái sinh ra một chuỗi có thể gồm biến lẫn các ký hiệu kết thúc trong văn phạm.

Văn phạm phi ngữ cảnh (CFG) là một hệ thống gồm bốn thành phần, ký hiệu là văn phạm G (V, T, P, S), trong đó :

. V là tập hữu hạn các biến (hay ký tự chưa kết thúc)

. T là tập hữu hạn các ký tự kết thúc, V  T = 

. P là tập hữu hạn các luật sinh mà mỗi luật sinh có dạng A   với A là biến và  là chuỗi các ký hiệu  (V  T)*

. S là một biến đặc biệt gọi là ký hiệu bắt đầu văn phạm.

Thí dụ 5.1 : Văn phạm G ({S, A, B}, {a, b}, P, S ), trong đó P gồm các luật sinh sau:

S ® AB

A ® aA

A ® a

B ® bB

B ® b

Quy ước ký hiệu:

- Các chữ in hoa A, B, C, D, E, ... và S ký hiệu các biến (S thường được dùng làm ký hiệu bắt đầu ).

- Các chữ nhỏ a, b, c, d, e, ...; các chữ số và một số ký hiệu khác ký hiệu cho các ký hiệu kết thúc.

- Các chữ in hoa X, Y, Z là các ký hiệu có thể là ký hiệu kết thúc hoặc biến.

- Các chữ Hi-lạp , , , ... biểu diễn cho chuỗi các ký hiệu kết thúc và biến.

Ta sẽ biểu diễn văn phạm một cách tóm tắt bằng cách chỉ liệt kê các luật sinh của nó. Nếu A ® 1, A ® 2 , ... , A ® k là các luật sinh của biến A trong văn phạm nào đó, ta sẽ ghi ngắn gọn là A ® 1 | 2 | ... | k

Thí dụ 5.2 : Văn phạm trong Thí dụ 5.1 trên có thể viết gọn là :

S ® AB

A ® aA  a

B ® bB  b

Câu hỏi :

?

Bạn nghĩ gì về lớp ngôn ngữ có thể được sinh bởi văn phạm trong ví dụ trên ? Cơ chế nào có thể được sử dụng cho văn phạm để phát sinh ngôn ngữ ?

Dẫn xuất và ngôn ngữ

Dẫn xuất: Để định nghĩa ngôn ngữ sinh bởi văn phạm CFG G (V, T, P, S), ta dẫn nhập khái niệm dẫn xuất. Trước hết ta giới thiệu hai quan hệ G và *G giữa hai chuỗi trong tập (V  T)*. Nếu A   là một luật sinh trong văn phạm và ,  là hai chuỗi bất kỳ trong tập (V  T)* thì A G , hay ta còn nói luật sinh A   áp dụng vào chuỗi A để thu được chuỗi , nghĩa là A sinh trực tiếp  trong văn phạm G. Hai chuỗi gọi là quan hệ nhau bởi G nếu chuỗi thứ hai thu được từ chuỗi thứ nhất bằng cách áp dụng một luật sinh nào đó.

Giả sử 1, 2, ..., m là các chuỗi thuộc (V  T)* với m  1 và :

1 G 2, 2 G 3, …, m -1 G m

thì ta nói 1*G m hay 1 dẫn xuất ra m trong văn phạm G.