Vị Trí, Chức Năng, Nhiệm Vụ Của Giai Đoạn Phân Tích Cú Pháp

2.22. Cho các biểu thức chính quy a) 0(0 + 1)* 0+

b) ((0+ 1)*0(0 + 1))+

c) (1+ 0)00 (0* + 1+)

d) (a + ba + aab)*(ε + a)+

Hãy xây dựng các NFAε tương đương với mỗi biểu thức trên.

2.23. Cho các biểu thức chính quy sau: a) ( a* + b+)*

b) ((ε + a) b*)+

c) (a + b)+ abb (a + b)*

d) ab* + (a + bb) a*b

Có thể bạn quan tâm!

• Mô Tả Quá Trình Đoán Nhận Xâu
• Biểu Diễn Automat Bằng Đồ Thị
• Automat Đoán Nhận R=(A  B) * Abb
• Minh Họa Một Cây Phân Tích Cú Pháp
• A, B, C. Mô Tả Quá Trình Phân Tích Xâu W = Cad
• Mô Tả Hình Tổ Chức Dữ Liệu Của Kỹ Thuật Dự Đoán

Xem toàn bộ 224 trang tài liệu này.

1) Xây dựng NFAε đoán nhận các biểu thức chính quy trên.

2) Hãy chuyển mỗi sang DFA tương đương.

2.24. Quá trình phân tích từ vựng dựa vào sơ đồ chuyển có thể được tiến hành theo giải thuật sau:

Input: Sơ đồ chuyển của token và xâu vào w$ Output: phân tích xâu vào có từ vị của token? Process:

Bước 1: Xuất phát từ trạng thái bắt đầu của ký tự khởi đầu của token, con trỏ trỏ vào ký tự đầu tiên của xâu vào w.

Bước 2: Nếu trên sơ đồ chuyển đang ở nút i và cung đi ra có nhãn là  đang nối với nút j thì khi đó:

- Nếu  là ký tự kết thúc (Terminal) và ký tự mà con trỏ đang trỏ trong w cũng là  thì con trỏ trỏ đến ký tự tiếp theo của xâu w và quá trình duyệt chuyển sang nút j.

- Nếu  là token thì quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của token .

+ Nếu quá trình duyệt đến được trạng thái kết thúc của biến  thì quá trình duyệt quay trở lại nút j.

+ Ngược lại

* Nếu ở nút i còn cung đi ra thì chọn cung đi ra tiếp theo và quay lại

bước 2.

* Nếu đã xét hết các cung đi ra khỏi nút i và quá trình duyệt không đến

được trạng thái kết thúc của token  thì báo lỗi.

- Nếu từ nút i đến nút j có cung mang nhãn , thì quá trình duyệt chuyển thẳng đến nút j và con trỏ trỏ vào ký tự trên xâu vào w đứng yên.

Bước 3: Nếu quá trình duyệt đã duyệt hết xâu vào và:

- Nếu quá trình duyệt đến được trạng thái kết thúc của sơ đồ chuyển của token thì thông báo thành công.

- Ngược lại thì thông báo lỗi.

Cho các sơ đồ chuyển:

Start

0,1,2,3,4,5,6,7,8,9

q0

q1

1)

Digit:

2)

Digits:

Start

+, -

q4

q5



3)

sign:

4) Digitsign:

Start

q

9

+,- ,q

10

digit q

11

.

digit

q12 q13



5)

number:

digit

Start

q2

digit

q3

sign

Start

q6

q7

digit

q8

digit

digit

digit

6)

nums: Start

q14

+,- ,

q15

digit

digit

q16 .

q17

digit

digit

q18 E

q19

+,- ,

q20

digit

digit q21

7)

8)

Và các xâu:

Letter:

id:

Hình BT 2.24

Start

q24

letter

q25

Start

q

A,…,Z, a, …,z

22

q

23

letter, digit

1) 123; -23467; 123.56; +123.789; - 001.34256; 123b

2) X1, a23b5; 1b34a; bien12, anpha1

3) 123. 01E02; -021E-03; +23. 098E+04

a) Sử dụng các giải thuật trên, kiểm tra các xâu trên là từ vị của token nào trong các token sau:

1) Digits

2) Digitsign

3) Number

4) Nums

5) id

b) Hãy tổng hợp các sơ đồ trên để có được các sơ đồ chuyển dùng để nhận biết các token:

1) Digits

2) Digitsign

3) Number

4) Nums

5) id

c) Sử dụng các sơ đồ đã tổng hợp được, kiểm tra các xâu trên là từ vị của token nào trong các token trên.

Mục tiêu:

Chương 3 PHÂN TÍCH CÚ PHÁP

Giúp sinh viên có khả năng:

- Biết được vị trí, nhiệm vụ của giai đoạn phân tích cú pháp

- Biết được các phương pháp phân tích cú pháp.

- Hiểu được các kỹ thuật biến đổi văn phạm.

- Hiểu được các kỹ thuật trong phương pháp phân tích top - down.

- Hiểu được các kỹ thuật trong phương pháp phân tích bottom - up .

- Vận dụng các kỹ thuật vào phân tích cú cho một số văn phạm đơn giản

Nội dung chính:

- Vị trí, nhiệm vụ của giai đoạn phân tích cú pháp và các phương pháp phân tích cú pháp.

- Các kỹ thuật biến đổi văn phạm: khử đệ quy trái, thừa số hoá bên trái, khử nhập nhằng.

- Phương pháp phân tích top – down: phân tích cú pháp đệ quy xuống, phân tích cú pháp dự đoán.

- Phương pháp phân tích bottom – up: phân tích cú pháp đẩy thu, phân tích cú pháp LR(k).

3.1. Giai đoạn phân tích cú pháp

3.1.1. Vị trí, chức năng, nhiệm vụ của giai đoạn phân tích cú pháp

Giai đoạn phân tích cú pháp là giai đoạn tiếp theo của giai đoạn phân tích từ vựng và trước giai đoạn phân tích ngữ nghĩa.

Chức năng của giai đoạn phân tích cú pháp là phân tích chương trình nguồn về mặt cú pháp: Xây dụng cây phân tích cú pháp hoặc báo lỗi. Nhiệm vụ chính của giai đoạn này là nhận vào dòng các thẻ từ (token) có được từ giai đoạn phân tích từ vựng và xác nhận rằng nó có thể được sinh ra từ văn phạm của ngôn ngữ nguồn bằng cách tạo ra cây phân tích cú pháp cho dòng thẻ từ này và đầu ra của nó là cây phân tích cú pháp (parsing tree). Ngoài ra, bộ phân tích cú pháp còn có cơ chế ghi nhận các lỗi cú pháp theo một phương thức linh hoạt và có khả năng phục hồi được

các lỗi thường gặp để có thể tiếp tục xử lý phần còn lại của xâu vào. Có thể chỉ ra vị trí của giai đoạn này với các giai đoạn liên quan ở hình 3.1.

Cây phân tích

Thẻ từ mới

Phần còn lại của front end

Bảng ký hiệu

Bộ phân tích từ vựng

Bộ phân tích cú pháp

Chương trình nguồn

Thẻ từ Yêu cầu

cú pháp (Parsing tree)

Hình 3.1. Vị trí của bộ phân tích cú pháp

3.1.2. Xử lý lỗi cú pháp

Chương trình nguồn có thể chứa các lỗi ở nhiều mức độ khác nhau:

- Lỗi từ vựng: như tên, từ khóa, toán tử viết không đúng.

- Lỗi cú pháp: như ghi một biểu thức toán học với các dấu ngoặc đóng và mở không cân bằng, thiếu dấu chấm phảy (;), thiếu từ khoá.

- Lỗi ngữ nghĩa: như một toán tử áp dụng vào một toán hạng không tương thích, sai kiểu dữ liệu.

- Lỗi logic: như thực hiện một lời gọi đệ quy không thể kết thúc.

Phần lớn việc phát hiện và phục hồi lỗi trong một chương chương trình biên dịch tập trung vào giai đoạn phân tích cú pháp. Vì thế, bộ xử lý lỗi (error handler) trong quá trình phân tích cú pháp phải đạt được mục đích sau:

- Ghi nhận và thông báo lỗi một cách rò ràng và chính xác.

- Phục hồi lỗi một cách nhanh chóng để có thể xác định các lỗi tiếp theo.

- Không làm chậm tiến trình của một chương trình đúng.

3.1.3. Các chiến lược phục hồi lỗi

Phục hồi lỗi là kỹ thuật vượt qua các lỗi để tiếp tục quá trình dịch. Nhiều chiến lược phục hồi lỗi có thể dùng trong bộ phân tích cú pháp. Mặc dù không có chiến lược nào được chấp nhận hoàn toàn nhưng một số trong chúng đã được áp dụng rộng rãi. Ở đây sẽ giới thiệu một số chiến lược:

1) Phương thức "hoảng sợ" (panic mode recovery)

Đây là phương pháp đơn giản nhất cho cài đặt và có thể dùng cho hầu hết các phương pháp phân tích. Khi một lỗi được phát hiện thì bộ phân tích cú pháp bỏ qua từng ký hiệu một cho đến khi tìm thấy một tập hợp được chỉ định của các token đồng bộ (synchronizing tokens), các token đồng bộ thường là dấu chấm phẩy (;) hoặc end.

2) Chiến lược mức ngữ đoạn (phrase_level recovery)

Khi phát hiện một lỗi, bộ phân tích cú pháp có thể thực hiện sự hiệu chỉnh cục bộ trên phần còn lại của xâu vào. Cụ thể là thay thế phần đầu còn lại bằng một chuỗi ký tự có thể tiếp tục. Chẳng hạn, dấu phẩy (,) bởi dấu chấm phẩy (;), xóa một dấu phẩy lạ hoặc thêm vào một dấu chấm phẩy.

3) Chiến lược dùng các luật sinh sửa lỗi (error production)

Thêm vào văn phạm của ngôn ngữ những luật sinh lỗi và sử dụng văn phạm này để xây dựng bộ phân tích cú pháp, giúp có thể sinh ra bộ đoán lỗi thích hợp để chỉ ra cấu trúc lỗi được nhận biết trong xâu vào.

4) Chiến lược hiệu chỉnh toàn cục (global correction)

Một cách lý tưởng là chương trình biên dịch tạo ra một số thay đổi trong khi xử lý một lỗi. Có những giải thuật để lựa chọn một số tối thiểu các thay đổi để đạt được một hiệu chỉnh có chi phí toàn cục nhỏ nhất. Cho một xâu vào có lỗi x và một văn phạm G, các giải thuật này sẽ tìm được một cây phân tích cú pháp cho xâu y mà số lượng các thao tác chèn, xóa và thay đổi token cần thiết để chuyển x thành y là nhỏ nhất. Nói chung, hiện nay kỹ thuật này vẫn còn ở dạng nghiên cứu lý thuyết.

3.1.4. Các phương pháp phân tích cú pháp

Hiện tại có nhiều phương pháp phân tích cú pháp khác nhau; tuy nhiên, người ta có thể phân chúng thành 3 loại: phương pháp phân tích tổng hợp, phương pháp phân tích top – down và phương pháp phân tích bottom – up.

1) Phương pháp phân tích tổng hợp (Universal parsing)

Tiêu biểu cho phương pháp phân tích tổng hợp là giải thuật Cooke – Young Kasami và giải thuật Earley; Người ta gọi chúng là giải thuật tổng hợp hay giải thuật vạn năng vì chúng phân tích cú pháp cho văn phạm bất kỳ. Tuy nhiên do tính vạn năng của chúng cho nên nói chung phương pháp này không hiệu quả với một

văn phạm cụ thể; vì lý do trên, người ta ít sử dụng chúng để viết các chương trình dịch (Compiler).

2) Phương pháp phân tích Top – Down

Về mặt trực giác có thể coi phương pháp phân tích Top – Down là phương pháp xây dựng cây phân tích cú pháp từ trên xuống hay có thể xem như một nỗ lực xây dựng cây phân tích cú pháp bắt đầu từ nút gốc và phát sinh dần xuống lá (Root

– Leaves).

3) Phương pháp phân tích Bottom – Up

Về mặt trực giác có thể coi phương pháp phân tích Bottom – Up là xây dựng cây phân tích cú pháp từ dưới lên trên hay hay có thể xem như một nỗ lực xây dựng cây phân tích cú pháp bắt đầu từ các nút lá và thu gọn dần về gốc (Leaves – root).

3.2. Biến Ðổi văn phạm phi ngữ cảnh

Nhiều ngôn ngữ lập trình có cấu trúc đệ quy mà nó có thể được định nghĩa bằng các văn phạm phi ngữ cảnh (context-free grammar) G với 4 thành phần G = (N, T, P, S), trong đó:

- N : là tập hữu hạn các ký hiệu chưa kết thúc hay các biến (variables)

- T : là tập hữu hạn các ký hiệu kết thúc (terminals) với N T = .

- P : là tập luật sinh của văn phạm (productions) có dạng: A  với A  N và  V* = (NT)*

- S  N: là ký hiệu bắt đầu của văn phạm (start symbol).

Ví dụ: Văn phạm với các luật sinh sau cho phép định nghĩa các biểu thức số học đơn giản (với E là một biểu thức - expression) :

E → EAE | (E) | - E | id ;

A → + | - | * | / | ↑ .

3.2.1. Cây phân tích cú pháp (Parsing tree) và dẫn xuất

Ta nói rằng αAβ dẫn xuất ra αγβ (ký hiệu: αAβ  αγβ) nếu A → γ là một luật sinh, α và β là các chuỗi tùy ý các ký hiệu văn phạm.

Nếu α1  α2  ...  αn ta nói α1 dẫn xuất ra (suy ra) αn

Ký hiệu  : dẫn xuất ra qua 1 bước

* : dẫn xuất ra qua 0, 1 hoặc nhiều bước.

+

 : dẫn xuất ra qua 1 hoặc nhiều bước.

i

 : dẫn xuất ra qua i bước.

Ta có tính chất:

*

1. α  α với α

*

* *

2. α  β và β  γ thì α  γ

+

Cho một văn phạm G với ký hiệu bắt đầu S. Ta dùng quan hệ  để định

nghĩa L(G) một ngôn ngữ được sinh ra bởi G. Xâu các ký hiệu kết thúc w thuộc

+

L(G) nếu và chỉ nếu S  w và xâu w được gọi là một câu của G. Một ngôn ngữ

được sinh ra bởi một văn phạm phi ngữ cảnh gọi là ngôn ngữ phi ngữ cảnh. Nếu hai văn phạm cùng sinh ra cùng một ngôn ngữ thì chúng được gọi là hai văn phạm tương đương.

Nếu S * α, trong đó α có thể chứa một ký hiệu chưa kết thúc thì ta nói rằng

α là một dạng câu (sentential form) của G. Một câu là một dạng câu chứa toàn các ký hiệu kết thúc.

Cây phân tích cú pháp là hình ảnh minh họa cho ký hiệu bắt đầu của một văn phạm dẫn đến một xâu trong ngôn ngữ.

Nếu ký hiệu chưa kết thúc A có luật sinh A  XYZ thì cây phân tích cú pháp có thể có một nút trong có nhãn A và có 3 nút con có nhãn tương ứng từ trái qua phải là X, Y, Z.

A

X Y Z

Hình 3.2. Minh họa một cây phân tích cú pháp

Một cách hình thức, cho một văn phạm phi ngữ cảnh thì cây phân tích cú pháp là một cây có các tính chất sau đây:

1. Nút gốc có nhãn là ký hiệu bắt đầu.