Vị Trí Của Bộ Phân Tích Cú Pháp Trong Mô Hình Trình Biên Dịch

2.5.2. Ðặc tả lex

Một chương trình lex bao gồm 3 thành phần:

Khai báo

Quy tắc dịch

Các thủ tục phụ

Phần khai báo bao gồm khai báo biến, hằng và các định nghĩa chính quy.

Phần quy tắc dịch cho các lệnh có dạng:

p1 {action 1 }

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

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

p2 {action 2 }

. . .

pn {action n }

Trong đó pi là các biểu thức chính quy, action i là đoạn chương trình mô tả hành động của bộ phân tích từ vựng thực hiện khi pi tương ứng phù hợp với trị từ vựng. Trong lex các đoạn chương trình này được viết bằng C nhưng nói chung có thể viết bằng bất cứ ngôn ngữ nào.

Các thủ tục phụ là sự cài đặt các hành động trong phần 2.

Ví dụ 3.8: Sau đây trình bày một chương trình Lex nhận dạng các token của văn phạm đã nêu ở phần trước và trả về token được tìm thấy.

/* định nghĩa các hằng LT, LE, EQ, NE, GT, GE, IF, THEN, ELSE, ID, NUMBER, RELOP */

/* định nghĩa chính quy */ delim [tn]

ws {delim}+ letter [A - Za - z] digit [0 - 9] id {letter}({letter}| {digit})*

number {digit}+(.{digit}+)?(E[+-]?{digit}+)?

{ws} {/* Không có action, không có return */} if {return(IF); }

then {return(THEN); }

else {return(ELSE); }

{id} {yylval = install_id( ); return(ID) }

{number} {yylval = install_num( ); return(NUMBER) } “< ” {yylval = LT; return(RELOP) }

“<= “ {yylval = LE; return(RELOP) } “= “ {yylval = EQ; return(RELOP) } “<> “ {yylval = NE; return(RELOP) } “> “ {yylval = GT; return(RELOP) } “>= “ {yylval = GE; return(RELOP) }

install_id ( ) {

/* Thủ tục phụ cài id vào trong Bảng danh biểu */

}

install_num ( ) {

/* Thủ tục phụ cài một số vào trong Bảng danh biểu */

}

BÀI TẬP CHƯƠNG II- PHÂN TÍCH TỪ VỰNG

2.1. Viết chỉ thị máy ảo kiểu Stack cho quá trình dịch các biểu thức sau sang dạng hậu tố:

a) y := a + 2013 b3c

b) t : = a div b + ( c -2012 * d ) mod 2013 / 3

c) t : = (a mod b) * 2010 - (2011 * c +2012 ) div 4 +2013

2.2. Cho văn phạm phi ngữ cảnh sau:

T → T T + | T T * | a

a) Viết các luật sinh dẫn ra câu nhập: a a + a *

b) Xây dựng một cây phân tích cú pháp cho câu nhập trên.

c) Văn phạm này sinh ra ngôn ngữ gì? Giải thích câu trả lời.

Bài tập nâng cao- phần này mời quý bạn đọc xem thêm chương 2, chương 3 giáo trình chương trình dịch, tác giả Phạm Hồng Nguyên, NXB đại học Quốc Gia Hà Nội.

2.3. Xác định bộ chữ cái của các ngôn ngữ sau:

a) Pascal

b) C

c) LISP

2.4. Viết một thủ tục phân tích từ vựng

2.5. Chuyển đổi từ SLANG sang VIM

Nội dung chính:

CHƯƠNG III. PHÂN TÍCH CÚ PHÁP

Chương này giúp bạn đọc hiểu vai trò của bộ phân tích cú pháp, trái tim của trình biên dịch. Chỉ ra bằng cách nào trình biên dịch hiểu được và chuyển sang mã máy được các giải thuật của người lập trình trong mã nguồn một ứng dụng.

Biên dịch một mã nguồn một ứng dụng không phải là việc biên dịch từ sang từ. Trong mã nguồn của người lập trình biên soạn phần lớn là các chỉ thị (lệnh) cho máy vi tính thực hiện. Bằng sự thỏa thuận giữa người lập trình và trình biên dịch, dù công việc tính toán (xử lý) phức tạp đến đâu thì người lập trình củng phải sử dụng những cấu trúc lệnh được quy định sẵn của ngôn ngữ lập trình đang được người lập trình sử dụng.

Bộ phân tích cú pháp của trình biên dịch xem xét các từ tố mang chỉ thị của người sử dụng viết trong mã nguồn, phân rã nó ra và đưa vào các cấu trúc định sẵn này, việc thiết lập ra cấu trúc định sẵn này chính là nội dung Bộ phân tích cú pháp.

Mục tiêu

Giúp cho bạn đọc hiểu cách thiết kế ra cấu trúc định sẵn này chính là nội dung Bộ phân tích cú pháp.

Yêu cầu chung

Độc giả phải có các kiến thức cơ bản của các học phần như ngôn ngữ lập trình: hiểu và nhận dạng được trình biên dịch; cấu trúc máy tính: hiểu trình biên dịch chạy trên môi trường nào; lý thuyết ngôn ngữ: hiểu trình biên dịch minh họa cho cái gì, mục đích gì; cấu trúc dữ liệu: hiểu các dữ liệu cài đặt sẵn của 1 trình biên dịch; phân tích thiết kế giải thuật và công nghệ phần mềm: hiểu cách thức tạo ra một ứng dụng gọi là trình biên dịch một cách bài bản.

TÀI LIỆU THAM KHẢO:

[1] Dương Tuấn Anh (1986), “Giáo trình trình biên dịch” - NXB Đại Học Bách Khoa TPHCM

[2] Phạm Hồng Nguyên, “Giáo trình Chương trình Dịch” - NXB Đại Học Quốc Gia Hà Nội

[3] Phan Thị Tươi (2011), “Trình Biên Dịch” - (Trường Ðại học kỹ thuật Tp.HCM) - NXB Giáo dục

[4] Automata and Formal Language. An Introduction – Dean Kelley – Prentice Hall, Englewood Cliffs, New Jersey 07632.

[5] Compilers : Principles, Technique and Tools - Alfred V.Aho, Jeffrey D.Ullman - Addison - Wesley Publishing Company, 1986.

[6] Compiler Design – Reinhard Wilhelm, Dieter Maurer - Addison – Wesley Publishing Company, 1996.

[7] Design of Compilers : Techniques of Programming Language Translation - Karen A. Lemone - CRC Press, Inc, 1992.

[8] Modern Compiler Implementation in C - Andrew W. Appel – Cambridge University Press, 1997

3.1. Phương pháp phân tích cú pháp

3.1.1. Vai trò của bộ phân tích cú pháp

Phân tích cú pháp nhận đầu vào là danh sách các từ tố của chương trình nguồn thành các thành phần theo văn phạm và biểu diễn cấu trúc này bằng cây phân tích hoặc theo một cấu trúc nào đó tương đương với cây.

từ tố

Phân tích từ vựng

Phân tích cú pháp

Phân tích ngữ nghĩa

Bảng ký hiệu

Chương trình nguồn

Lấy từ tố

Cây Phân tích

Biểu diễn trung gian

Hình 3.1 - Vị trí của bộ phân tích cú pháp trong mô hình trình biên dịch

3.1.1.1. 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ư danh biểu, 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.

- 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.

- Lỗi logic như thực hiện một lời gọi đệ qui 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 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 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.1.2. 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, chúng ta giới thiệu một số chiến lược :

a. 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.

b. 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 dòng nhập. 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.

c. 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, chúng ta 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 dòng nhập.

d. Chiến lược hiệu chỉnh toàn cục (global correction): Một cách lý tưởng là 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 chuỗi nhập 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 chuỗi 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.2. 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 các văn phạm phi ngữ cảnh (context-free grammar) G với 4 thành phần G (V, T, P, S), trong đó:

• V : 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).

• P : là tập luật sinh của văn phạm (productions).

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

Ví dụ 3.1: 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:

E → E A E| (E) |- E | id A → + | - | * | / | ↑

3.1.2.1. Cây phân tích cú pháp và dẫn xuất

* Định nghĩa: Cây phân tích trong một văn phạm phi ngữ cảnh G = (V,T,P,S) là một cây thỏa mãn các điều kiện sau:

1) Mọi nút có một nhãn, là một ký hiệu trong (V  T  {ε})

2) Nhãn của gốc là S

3) Nếu một nút có nhãn X là một nút trong thì X  T

4) Nếu nút n có nhãn X và các nút con của nó theo thứ tự trái qua phải có nhãn Y1, Y2, . . ., Yk thì X->Y1Y2 . . . Yk sẽ là một sản xuất  P

5) Nút lá có nhãn thuộc V hoặc là ε

* Suy dẫn trái nhất (nói gọn là suy dẫn trái), nếu ở mỗi bước suy dẫn, biến được thay thế là biến nằm bên trái nhất trong dạng câu.

* Suy dẫn phải nhất: (nói gọn là suy dẫn phải), nếu ở mỗi bước suy dẫn, biến được thay thế là biến nằm bên phải nhất trong dạng câu.

Cây phân tích cú pháp có thể được xem như một dạng biểu diễn hình ảnh của dẫn xuất. Ta nói rằng αAβ dẫn xuất ra αγβ (ký hiệu: αAβ  αγβ) nếu A → γ là 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 hoặc nhiều bước.

+ : dẫn xuất ra qua 1 hoặc nhiều 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. Chuỗi trong L(G) có thể chỉ chứa một ký