Hai cách tiếp cận tổng quát được sử dụng cho việc phân tích câu. Các phương pháp từ-trên-xuống (top-down) cho phép tìm một chương trình hợp lệ bằng cách trước tiên tìm các thành phần của một chương trình hợp lệ, sau đó tìm các thành phần của các thành phần này…cho đến khi các mẩu thông tin đủ nhỏ để đối sánh với dữ liệu nhập một cách trực tiếp. Các phương pháp từ-dưới-lên (bottom-up) đặt các mẩu dữ liệu nhập lại với nhau theo một phương pháp có cấu trúc để tạo ra các mẩu ngày càng lớn hơn cho đến khi một cương trình hợp lệ được tạo ra. Thông thường các phương pháp từ-trên-xuống là đệ quy, các phương pháp từ-dưới-lênlà lặp; các phương pháp từ-trên-xuống được coi là dễ cài đặt hơn, các phương pháp từ-dưới-lên được coi là hiệu quả hơn.

Bằng cách xây dựng “trình biên dịch” đơn giản để hoàn chỉnh thuật toán đối-sánh-mẫu, chúng ta sẽ có khả năng xem xét một vài khái niệm cơ bản có liên quan. Đầu tiên ta sẽ dây dựng một bộ phân tích từ-trên-xuống cho một ngôn ngữ đơn giản để mô tả các biểu thức chính quy. Sau đó ta sẽ sửa đổibộ phân tích để tạo ra một chương trình dịch các biểu thức chính quy thành các máy-đối-sánh-mẫu.

Văn phạm phi-ngữ-cảnh

trước khi viết được một chương trình để xác định xem một chương trình nào đó đã được viết trong một ngôn ngữ cho trước có là hợp lệ hay không, ta cần một mô tả chính xác về những gì cấu thành một chương trình hợp lệ. Mô tả này được gọi là một bộ văn phạm; để tán thành với thuật ngữ, hãy nghĩ đến một ngôn ngữ như tiếng Anh chẳng hạn và đọc “câu” cho “chương trình” trong câu trước đó (ngoại trừ lần xuất hiện đầu tiên !). Các ngôn ngữ lập trình thường được mô tả bởi một kiểu văn phạm cụ thể được gọi là văn phạm phi-ngữ-cảnh. Ví dụ, văn phạm phi ngữ cảnh định nghĩa tập tất cả các biểu thức chính quy như sau:

Văn phạm này mô tả các biểu thức chính quy, ví dụ như (1+01)*(0+1) hay (A*B+AC)D. Mỗi dòng trong văn phạm được gọi là một luật sinh hay luật thay thế. Các luật sinh bao gồm các ký hiệu kết thúc (terminal) (,). + và * là những ký hiệu được dùng trong ngôn ngữ đang được mô tả (“v”, một ký hiệu đặc biệt, đại diện cho bất kỳ một ký tự chữ hay số nào); các ký hiệu chưa kết (nonterminal) , và là những ký hiệu trung gian của văn phạm; các siêu ký hiệu (meta symbols) ::= và | được dùng để mô tả ý nghĩa của các luật sinh. Ký hiệu ::=, đọc “là một”, định nghĩa vế trái của luật sinh theo vế phải; và ký hiệu |, được đọc là “hoặc”, chỉ ra các tuỳ chọn khác nhau. Các luật sinh khác nhau, dù được biểu diễn trong dạng ký hiệu ngắn gọn này, lại tương ứng mộtcách đơn giảnvới một mô tả trực quan của bộ văn phạm. Ví dụ, luật sinh thứ hai trong bộ văn phạm thí dụ có thể được đọc là “một là một hoặc là một được theo sau bởi một ”. Một ký hiệu chưa biết, trong trường hợp này được phân biệt theo ý nghĩa là một chuỗi các ký hiệu kết, là thuộc về ngôn ngữ đang được mô tả bởi bộ văn phạm nếu và chỉ nếu có một cách nào đó dùng các luật sinh để phát sinh chuỗi đó từ các ký hiệu chưa kết phân biệt bằng cách thay thế (theo số bước tuỳ ý) một ký hiệu chưa kết bằng bấtkỳ một mệnh đề nào trong số các mệnh đề “hoặc” ởvế phải cảu một luật sinh cho ký hiệu chưa kết đó.

Một cách tự nhiên để mô tả kết quả của tiến trình phát sinh này là một cây phântích: đó là một lược đồ cấu trúc văn phạm hoàn chỉnh của chuỗi đang được phân tích. Ví dụ như cây văn phạm dưới đây:

Cây văn phạm này cho thấy chuối (A*B + AC)D là nằm trong ngôn ngữ được mô tả bởi văn phạm ở trên. Các cây phân tích giống như cây này đôi khi được dùng cho tiếng Anh để ngắt một câu thành chủ ngữ, động từ, vị ngữ…

Chức năng chính của một bộ phân tích là chấp nhận các chuỗi mà nó có thể được phát sinh như vậy là không nhận các chuỗi không thể được phát sinh như vậy bằng cách thử tạo ra một cây phân tích cho bất kỳ một chuỗi nào. Nghĩa là, bộ phân tích có thể nhận diện khi nào thì một chuỗi thuộc về ngôn ngữ đang được mô tả bởi văn phạm bằng cách xác định xem khi nào thì tồn tại một cây phân tích cho chuỗi đó. Các bộ phân tích từ-trên-xuống làm điều này bằng cách xây dựng cây bắt đầu bằngký hiệu chưa kết nằm ở đỉnh và đi xuống dưới hướng về chuỗi sẽ được nhận diện nằm ở đáy; các bộ phân tích từ-dưới-lên thực hiện điều này bằng cách khởi đầu từ chuỗi nằm ở đáy và đi ngược lên trên hướng tới ký hiệu chưa kết phân biệt nằm ở đỉnh. Như ta đã thấy, nếu ý nghĩa các chuỗi đang được nhận dạng còn có liên quan đến việc xử lý khác nữa, thì bộ phân tích có thể chuyển chúng thành một biểu diễn bên trong mà nó có thể khiến cho việc xử lý như thế trở nên dễ dàng.

Ví dụ, bộ văn phạm sau đây mô tả một tập con rất nhỏ các biểu thức số học của Pascal bao gồm phép cộng và phép nhân:

Các luật này mô tả một cách hình thức những gì có thể được thừa nhận: Chúng là các luật quy định việc tạo nên các biểu thức số học “hợp lệ”. Một lần nữa, v là một ký hiệu đặc biệt đại diện cho bất kỳ kí tự nào, nhưng tỏng văn phạm này, các chữ cái cso thể biểu diễn các biến với giá trị số. Các ví dụ về những chuỗi hợp lệ cho văn phạm này là A + (B* C) và A *(((B+C)*(D*E)+F).

Như đã xác định, một vài chuỗi là hợp lệ hoàn toàn cả về biểu thức số học lẫn biểu thức chính quy. Ví dụ A*(B+C) có thể hiểu là “cộng b với C và nhân kết quả với A” hoặc “lấy một dãy tuỳ ý các chữ A theo sau bởi B hoặc C”. Điều này cho thấy một sự kiện hiển nhiên là việc kiểm tra khi nào một chuỗi được tạo thành một cách hợp lệ là một chuyện, còn việc hiểu nó có ý nghĩa gì lại là chuyện hoàn toàn khác. Ta sẽ trở lại vấn đề này sau khi đã xem làm thế tnào phân tích một chuỗi để xác định xem no được mô tả bởi một văn phạm nào đó hay không.

Mỗi một biểu thức chính quy bản thân nó là một ví dụ của một bộ văn phạm phi ngữ cảnh: bất kỳ một ngôn ngữ nào mà nó có thể được mô tả bởi một biểu thức chính quy thì cũng có thể được mô tả bởi một văn phạm phi ngữ cảnh. Điều ngược lại không đúng. Ví dụ, khái niệm về sự “cân bằng” số dấu ngoặc đơn không thể nắm bắt được bởi các biểu thức chính quy. Các kiểu văn phạm khác có thể mô tả các ngôn ngữ mà các văn phạm phi ngữ cảnh không thể mô tả được. Ví dụ, các văn phạm cảm ngữ cảnh giống với văn phạm phi ngữ cảnh, ngoại trừ về trái của các luật sinh không nhất thiết là các ký hiệu chưa kếtđơn lẻ. Những khác biệt giữa các lớp ngôn ngữ và công việc phân cấp các văn phạm để mô tả chúng đã được giải quyết một cách rất cẩn thận và tạo nên một lý thuyết đẹp, có vị trí trung tâm trong khoa học máy tính.

Thuật toán đệ quy trong phân tích câu-Phân tích từ-trên-xuống

Một phương pháp phân tích sử dụng đệ quy để nhận dạng các chuỗi từ một ngôn ngữ được mô tả một cách chính xác như đã quy định bởi bộ văn phạm. Nói một cách khác đơn giản, văn phạm là một đặc tả của ngôn ngữ mà nó hoàn chỉnh đến nỗi nó có thể được trực tiếp thành chương trình.

Mỗi luật sinh ứng với một thủ tục có tên là ký hiệu chưa kết ở vế trái. Các ký hiệu chưa kết ở vế phải của dãy nhập tương ứng (có thể là đệ quy) với các lệnh gọi thủ tục; các ký hiệu kết tương ứng với việc dò trên chuỗi nhập vào. Ví dụ, thủ tục sau là một phần của một bộ phân tích từ-trên-xuống đối với bộ văn phạm biểu thức chính tắc của chúng ta:

++

procedure expression;

begin

term;

if p[j]= ‘+’ then

begin

j:=j+1;

expression;

end

end;

++

Một mảng p chứa biểu thức chính quy đang được phân tích và một chỉ mục j trỏ tới ký tự hiện đang được kiểm tra. Để phân tích một biểu thức chính quy cho trước, ta đặt nó trong p[1..M] (với một ký tự cầm canh trong p[M+1] không được dùng trong văn phạm), đặt j là 1, và gọi expression. Nếu điều này không khiến cho j được đặt về giá trị M+1, thì biểu thức chính quy là ở trong ngôn ngữ được mô tả bởi văn phạm. Nếu không, ta sẽ xem ở dưới đây các trường hợp sai khác nhau được kiểm soát như thế nào.

Điều đầu tiên mà expression làm là gọi term, được cài đặt hơi phức tạp hơn một chút:

++

procedure term;

begin

factor;

if (p[j] = ‘(‘ ) or letter(p[j]) then

term;

end;

++

Một phép biên dịch trực tiếp từ văn phạm đơn giản là để cho term gọi factor và sau đó tới term. Điều này hiển nhiên sẽ không hoạt động được vì nó không có cách nào để thoát khỏi term: chương trình này sẽ đi vào một vòng lặp đệ quy vô tận nếu được gọi (các vòng lặp như vậy có những tác động không tốt trong nhiều hệ thống). Việc cài đặt ở trên né qua được chỗ này bằng cách trước tiên kiểm tra dãy nhập vào để quyết định xem khi nào thì term sẽ được gọi. Việc đầu tiên mà term làm là gọi factor, là thủ tục duy nhất trong số các thủ tục có thể phát hiện ra một sự bất đối sánh trong dãy nhập. Từ bộ văn phạm, ta biết rằng khi factor được gọi, thì ký tự nhập vào hiện thời phải là một ký tự “(“ hoặc phải là một chữ cái nhập (biểu diễn bởi v). Tiến trình kiểm tra ký tự này mà không tăng j để quyết định xem sẽ làm gì thì được gọi là nhìn trước (lookahead). Đối với một vài bộ văn phạm, điều này là không cần thiết; đối với những bộ văn phạm khác, có thể cần nhiều lần nhìn trước hơn.

Giờ đây, cài đặt của factor tuân thủ một cách trực tiếp theo bộ văn phạm. Nếu ký tự nhập đang được quét không phải là một ký tự “(“ hay một chữ cái nhập, thì một thủ tục error được gọi để kiểm soát trường hợp lỗi:

++

Procedure factor;

begin if p[j]= ‘(‘ then

begin

j:=j+1;

expression;

if p[j]=’)’ then j:= j+1

else error

end

else if letter(p[j]) then

j:= j+1

else error;

if p[j]=’*’ then

j:=j+1

end;

++

Một trường hợp sai khác xảy ra khi thiếu một dấu “)”

Các thủ tục expression, term và factor rõ ràng là đệ quy; thực vậy, chúng quyện vào nhau quá chặt đến nỗi ta không thể biên dịch được chúng trong Pascal nếu không dùng cấu trúc forward để né tránh quy tắc dựa trên việc dùng một thủ tục mà không khai báo chúng trước.

Cây phân tích đối với một chuỗi cho trước sẽ sinh ra cấu trúc gọi đệ quy trong lúc phân tích. Hình sau:

Trên hình dò theo thao tác của 3 thủ tục ở trên khi p chứa (A*B+AC)D và expression được gọi với j=1. Ngoại trừ dấu công, toàn bộ việc “quét” là được thực hiện trong factor. Để dễ đọc, các ký tự mà thủ tục factor quét, ngoại trừ các dấu ngoặc, sẽ được đặt trên cùng một dòng với lệnh gọi factor.

Độc giả có thể liên hệ tiến trình này với văn phạm và cây trong hình 1. Tiến trình này tương ứng với việc dịch chuyển trên cây theo tiền-thứ-tự, mặc dù sự tương ứng là không chính xác do chiến lược nhìn trước của chúng a chung quy là để thay đổi văn phạm. Vì ta bắt đầu ở đỉnh của cây và đi xuống, nguồn gốc của tên từ-trên-xuống là dễ hiểu. Các bộ văn phạm như cũng thường được gọi là những bộ phân tích đệ-quy-xuống do chúng di chuyển xuống phía dưới của cây phân tích một cách đệ quy.

***

expression

term

factor

{

expression

term

factor A

term

factor B

+

expression

term

factor A

term

factor C

}

term

factor D

***

Cách tiếp cận từ-trên-xuống sẽ không hoạt động được đối với tất cả các văn phạm phi ngữ cảnh có thể có. Ví dụ, với luật sinh , nếu ta tuân theo cách dịch máy móc thành Pascal như ở trên, ta sẽ nhận được kết quả không mong muốn.

**

procedure badexpression;

begin

if letter(p[j]) then

j:= j+1

else

begin

badespression;

if p[j] <> ‘+’ then error

else

begin

j:=j+1;

term

end

end

end;

**

Nếu thủ tục này được gọi với p[j] không phải là chữ cái (như ví dụ của ta, với j=1) nó sẽ đi vào một vòng lặp đệ quy vô hạn. Việc tránh những vòng lặp như vậy là một khó khăn chủ yếu trong việc cài đặt các bộ phân tích đệ quy xuống. Đối với term, ta đã dùng việc nhìn trước để tránh một vòng lặp như vậy; trong trường hợp này cách thích hợp là đi đường vòng để tránh khó khăn này bằng cách chuyển văn phạm qua . Sự xuất hiện một ký hiệu chưa kết giống như cái đầu tiên trên về phải của một luật thay thế cho chính nó thì được gọi là đệ-quy-trái. Thực ra, vấn đề khó khăn hơn, do việc đệ quy trái có thể xảy ra gián tiếp, ví dụ như với các luật sinh

Các bộ phân tích đệ quy xuống sẽ không hoạt động được đối với các văn phạm như vậy. Chúng phải được biến đổi thành các văn phạm tương đương mà không có sự đệ quy trái, hay phải dùng đến một phương pháp phân tích nào đó. Thông thường, có một mối liên lạc mật thiết và được nghiên cứu rộng rãi giữa các bộ phân tích và các bộ văn phạm mà chúng nhận dạng, và được chọn lựa một kỹ thuật phân tích thường được truyền đạt bởi các đặc trưng của văn phạm sẽ phân tích.

School@net