0.5 Văn phạm chính quy và các tính chất

Văn phạm chính quy (rg : regular grammar)

Như trong chương 3 ta đã biết, lớp ngôn ngữ được chấp nhận bởi ôtômát hữu hạn được gọi là ngôn ngữ chính quy và chúng có thể được ký hiệu một cách đơn giản bằng việc dùng một biểu thức chính quy. Chương này giới thiệu một cách khác để mô tả ngôn ngữ chính quy thông qua cơ chế sản sinh ngôn ngữ - đó là văn phạm chính quy.

Xét một định nghĩa cho văn phạm sinh ra các số nguyên không dấu (unsigned interger) bắt đầu bằng một chữ số, theo sau bởi một chuỗi các số (digit sequence) thường dùng trong các ngôn ngữ lập trình như sau:

<digit sequence>::= 0  1  2  3  4  5  6  7  8  9

 0<digit sequence> 1<digit sequence>

 2<digit sequence> 3<digit sequence>

 4<digit sequence> 5<digit sequence>

 6<digit sequence> 7<digit sequence>

 8<digit sequence> 9<digit sequence>

<unsighed integer>::= 0  1  2  3  4  5  6  7  8  9

 1<digit sequence> 2<digit sequence>

 3<digit sequence> 4<digit sequence>

 5<digit sequence> 6<digit sequence>

 7<digit sequence> 8<digit sequence>

 9<digit sequence>

Câu hỏi :

?

Bạn có nhận xét gì về dạng chuỗi trong vế phải của các luật sinh văn phạm ?

Trong ví dụ trên, ta thấy mỗi vế phải hoặc là một ký hiệu kết thúc hoặc có dạng của một ký hiệu kết thúc theo sau là một biến. Trong hầu hết mọi ngôn ngữ lập trình, tất cả các ký hiệu cơ bản (số nguyên, tên biến, toán hạng, từ khóa, các ký hiệu hết câu,…) đều có thể định nghĩa bởi những quy luật ngắn dạng này. Vì phần lớn thời gian tiêu tốn trong một trình biên dịch là dùng để nhận dạng các ký hiệu cơ bản, cho nên việc khảo sát lớp văn phạm với các luật sinh dạng như trên là rất cần thiết.