Bài giảng Trình biên dịch TS. Vũ Đức Lung: Chương 1, 2, 3

05/04/2012

MỤC ĐÍCH & NỘI DUNG MỤC ĐÍCH & NỘI DUNG

TRÌNH BIÊN DỊCH TRÌNH BIÊN DỊCH (COMPILER) (COMPILER)

(cid:1) Thời gian:

- Lý Thuyết: 45 tiết (3 TC)

(cid:2) Môn học Trình biên dịch hay còn gọi là Chương trình dịch sẽ giới thiệu những nguyên tắc và kỹ thuật cơ bản để cài đặt một trình biên dịch.

(cid:1) Điểm số:

(cid:2) Những kiến thức này sẽ giúp hiểu được cơ cấu và cách vận

- Điểm chuyên cần: 10% - Điểm báo cáo: 40% - Điểm thi cuối kỳ: 50%

hành trong các trình biên dịch của các ngôn ngữ lập trình thông dụng như Pascal, C, C++ và Java, nhờ đó hiểu thấu đáo hơn về các ngôn ngữ này, giúp nâng cao kỹ năng lập trình và gỡ lỗi chương trình.

(cid:1) Khoa Kỹ thuật máy tính (cid:1) GV: TS. Vũ Đức Lung (cid:1) Email: lungvd@uit.edu.vn

TÀI LIỆU THAM KHẢO TÀI LIỆU THAM KHẢO

CHƯƠNG 1: CHƯƠNG 1: GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH

Phan Thị Tươi. Giáo trình Trình biên dịch, nhà xuất bản đại học quốc gia tp HCM, 2009.

2. Aho, Sethi, and Ullman [1986]. Compilers: Principles,

1. Ngôn ngữ lập trình: 1.1 Giới thiệu: (cid:2) Con người muốn máy tính thực hiện công việc, phải viết các

yêu cầu đưa cho máy bằng ngôn ngữ máy hiểu được.

(cid:2) Việc viết các yêu cầu ta gọi là lập trình (cid:2) Ngôn ngữ dùng để lập trình được gọi là ngôn ngữ lập trình

Techniques, and Tools, Addison-Wesley, Reading Mass., 1986. (Bản dịch tiếng Việt gồm hai tập với tựa đề: Trình biên dịch: Nguyên lý, Kỹ thuật và Công cụ, nhà xuất bản Thống kê, 2000-2001).

3. Cao Hoàng Trụ. Ngôn ngữ lập trình-Các nguyên lý và mô

hình. Nhà xuất bản ĐHQG tp.HCM, 2004.

Khoa KTMT Vũ Đức Lung 1 Khoa KTMT Vũ Đức Lung 2

GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH

1.2 Phân loại:

(cid:2) Ngôn ngữ máy.

1.4 Phiên dịch (translation): (cid:2) Quá trình biến đổi một chương trình được viết bằng một

10110011010010010011010110110001

(cid:2) Hợp ngữ.

ngôn ngữ (ngôn ngữ nguồn) thành một chương trình tương đương nhưng được diễn tả bằng một ngôn ngữ khác (ngôn ngữ đích).

; move B into register r0 ; add

(cid:2) Ngôn ngữ đích thường là ngôn ngữ máy. (cid:2) Có hai dạng phiên dịch: Biên dịch (compilation) và Thông

• MOV r0, B • ADD r0, C • MOV A, r0 ; store (cid:2) Ngôn ngữ cấp cao.

dịch (interpretation):

A := B + C

1.3 Chương trình:

(cid:2) Chương trình chịu trách nhiệm dịch từ một ngôn ngữ này sang một ngôn ngữ khác được gọi chung là chương trình dịch (translator) và có thể được chia thành hai loại: Trình biên dịch (compiler) và Trình thông dịch (interpreter).

(cid:2) Tập hợp các yêu cầu được sắp đặt hợp lý để máy thực hiện. (cid:2) Các yêu cầu có thể được diễn tả bằng nhiều ngôn ngữ khác nhau, thế nhưng máy tính chỉ hiểu được một ngôn ngữ duy nhất: ngôn ngữ máy (machine language).

Khoa KTMT Vũ Đức Lung 3 Khoa KTMT Vũ Đức Lung 4

Khoa KTMT Vũ Đức Lung 5 Khoa KTMT Vũ Đức Lung 6

1 05/04/2012

GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH

1.4.1 Biên dịch (compilation): (cid:2)

(cid:2)

Chương trình nguồn được ghi trong các tập tin rồi được dịch thành chương trình đích và được ghi lại trong các tập tin. Sau đó chúng ta có thể cho chương trình chạy bằng cách "mở" tập tin chứa chương trình đích ra. Công việc này tương tự như công việc của một chuyên gia dịch thuật khi thực hiện dịch một văn bản (tác phẩm văn học, tài liệu kỹ thuật).

(cid:1) Trình biên dịch, còn gọi là phần mềm biên dịch, compiler, là một chương trình máy tính làm công việc dịch một chuỗi các câu lệnh được viết bằng một ngôn ngữ lập trình (gọi là ngôn ngữ nguồn hay mã nguồn), thành một chương trình tương đương nhưng ở dưới dạng một ngôn ngữ máy tính mới (gọi là ngôn ngữ đích) và thường là ngôn ngữ ở cấp thấp hơn, như ngôn ngữ máy.

(cid:1) Chương trình mới được dịch gọi mã đối tượng (cid:1) Chương trình đích có thể được thi hành trực tiếp bởi một máy

tính hay bởi một máy ảo

GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH

Biên dịch và thông dịch Biên dịch và thông dịch

1.4.2 Thông dịch (interpretation): (cid:2) Chương trình nguồn được dịch rồi cho thực hiện ngay mà

Compiler

không ghi lại bản dịch.

Chương trình nguồn

Chương trình đích

(cid:2) Công việc này tương tự như công việc của một thông dịch

viên.

Chương trình đích

Input

Output

Interpreter

Output

Chương trình nguồn

Input

Khoa KTMT Vũ Đức Lung 7 Khoa KTMT Vũ Đức Lung 8

GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH

11..55. . ĐặĐặc c tả tả ngôn ng

ngôn ngữ ữ llậập p trìtrìnhnh

(cid:1) Cú pháp và Ngữ nghĩa (cid:1) Cú pháp: sự kết hợp của các ký hiệu (dạng của biểu thức, các

phát biểu, các đơn vị nhỏ trong chương trình)

(cid:1) Ngữ nghĩa: ý nghĩa của các kết hợp

Tối thiểu cần định nghĩa: 1. Tập các ký hiệu cần dùng trong các chương trình hợp lệ 2. Tập các chương trình hợp lệ 3. Nghĩa của chương trình hợp lệ

Các phương pháp xác định nghĩa của CT hợp lệ:

- Phương pháp thứ nhất là định nghĩa bằng phép ánh xạ. Sử dụng phép toán hàm: hàm Lamda. - Phương pháp thứ hai: Máy trừu tượng. - Phương pháp thứ ba: Tập (x,y) là sự biên dịch,x là CT nguồn, y là đích.

Khoa KTMT Vũ Đức Lung 9 Khoa KTMT Vũ Đức Lung 10

Khoa KTMT Vũ Đức Lung 11 Khoa KTMT Vũ Đức Lung 12

2 05/04/2012

TRÌNH BIÊN DỊCH TRÌNH BIÊN DỊCH

1.2 Bảng danh biểu Ví dụ: COST := (PRICE + TAX) * 65

1. Các thành phần của trình biên dịch: 1.1 Phân tích từ vựng: Nhận dạng token. Token: danh biểu, hằng, từ khóa, các toán tử phép toán, các ký hiệu phân cách, khoảng trắng, các ký hiệu đặc biệt

Ví dụ: COST := ( PRICE + TAX )*65 Đầu ra của bộ phân tích từ vựng: () := ( () + () ) * (,4) Viết gọn: id1 := (id2 + id3) * num4

Bảng danh biểu

TRÌNH BIÊN DỊCH TRÌNH BIÊN DỊCH

1.5 Phân tích ngữ nghĩa:

1.3 Phát hiện và thông báo lỗi 1.4 Phân tích cú pháp

Vídụ: COST := (PRICE + TAX) * 65 Kết quả phân tích từ vựng: id1 := ( id2 + id3 )* num4

Kết quả phân tích cú pháp: Cây cú pháp của phát biểu

Cây cú pháp có xử lý ngữ nghĩa

Khoa KTMT Vũ Đức Lung 13 Khoa KTMT Vũ Đức Lung 14

TRÌNH BIÊN DỊCH TRÌNH BIÊN DỊCH

1.6 Sinh mã trung gian: temp1:= intoreal(65) temp2:= id2+ id3 temp3:= temp2* temp1 id1:= temp3

1.8 Sinh mã đối tượng: movF id2, R1 movF id3, R2 addF R2, R1 multF# 65.0, R1 movF R1, id1

1.7 Tối ưu mã trung gian: temp1:= id2+ id3 id1:= temp1 * 65

Khoa KTMT Vũ Đức Lung 15 Khoa KTMT Vũ Đức Lung 16

Khoa KTMT Vũ Đức Lung 17 Khoa KTMT Vũ Đức Lung 18

3 05/04/2012

TRÌNH BIÊN DỊCH TRÌNH BIÊN DỊCH

Tổng hợp quá trình Tổng hợp quá trình biên dịch biên dịch

CÁC MỐI LIÊN QUAN VỚI TRÌNH BIÊN DỊCH CÁC MỐI LIÊN QUAN VỚI TRÌNH BIÊN DỊCH

2. Trình biên dịch hợp ngữ: Phát biểu gán b := a + 2 được dịch ra mã hợp ngữ

a, R1 #2 , R1

1. Bộ tiền xử lý: (cid:2) Xử lý macro (macro processing) (cid:2) Chêm tập tin (file inclusion) (cid:2) Bộ xử lý hoà hợp (rational processor) (cid:2) Mở rộng ngôn ngữ (language extension)

LOAD ADD STORE R1, b

Khoa KTMT Vũ Đức Lung 19 Khoa KTMT Vũ Đức Lung 20

CÁC MỐI LIÊN QUAN VỚI TRÌNH BIÊN DỊCH CÁC MỐI LIÊN QUAN VỚI TRÌNH BIÊN DỊCH

3. Trình biên dịch hợp ngữ hai chuyến: Chuyến thứ nhất: đọc mã hợp ngữ và tạo bảng danh biểu Danh biểu

Điạ chỉ tương đối

4. Bộ cất liên kết soạn thảo: Loader là chương trình thực hiện hai nhiệm vụ: cất và soạn thảo liên kết. Quá trình cất bao gồm lấy mã máy khả định vị tính lại thành địa chỉ tuyệt đối. Như ở ví dụ phần 3: Giả sử mã máy được cất trong bộ nhớ trong tại địa chỉ L = 00001111 => địa chỉ tuyệt đối của a, b là 00001111 và 00010011.

a 0 4 b

Ba chỉ thị (1.6) được viết lại dưới dạng mã máy tuyệt đối:

Chuyến thứ hai: đọc mã hợp ngữ và dịch sang mã máy khả định vị địa chỉ:

(1.7)

(1.6)

0001 01 00 00001111 0011 01 10 00000010 0010 01 00 00010011

LOAD ADD STORE

a, R1 0001 01 00 00000000 * #2, R1 0010 01 10 00000010 R1, b

0100 01 00 00000100 *

Link-editor cho phép tạo một chương trình duy nhất từ nhiều tập tin ở dạng

mã máy khả định vị của những lần biên dịch riêng biệt và từ các tập tin thư viện do hệ thống cung cấp.

Khoa KTMT Vũ Đức Lung 21 Khoa KTMT Vũ Đức Lung 22

Khoa KTMT Vũ Đức Lung 23 Khoa KTMT Vũ Đức Lung 24

4 05/04/2012

CÁC MỐI LIÊN QUAN VỚI TRÌNH BIÊN DỊCH CÁC MỐI LIÊN QUAN VỚI TRÌNH BIÊN DỊCH

(cid:1) Hệ thống xử lý ngôn ngữ

5. Nhóm các giai đoạn của trình biên dịch (cid:2) Giai đoạn trước và giai đoạn sau(front end and back end) (cid:2) Các chuyến (cid:2) Thu giảm số lượng các chuyến goto L Thídụ: : goto L : L : a = b + c

LLợợii ííchch củcủaa ngônngôn ngữngữ trung

trung giangian

ch dùng CIL Lợi Lợi íích dùng CIL

(cid:1) Tương tác giữa các ngôn ngữ lập trình:

Khoa KTMT Vũ Đức Lung 25 Khoa KTMT Vũ Đức Lung 26

BÀI TẬP

(cid:1) Tìm hiểu thêm về các Tool cho phép xây dựng các Compiler

– ANTLR – Lex, Yacc

http:// lhu.edu.vn 27 http:// lhu.edu.vn 28

5 05/04/2012

Chương 2 : Cú pháp và ngữ nghĩa Chương 2 : Cú pháp và ngữ nghĩa

TRÌNH BIÊN DỊCH (COMPILER)

Nội dung: Nội dung: (cid:1)(cid:1) Các khái niệm cơ bản (cid:1) Đặc tả hình thức (Formal description) (cid:1) Đặc tả từ vựng (cid:1) Biểu thức chính quy (cid:1) Đặc tả cú pháp hình thức

(cid:1) Khoa Kỹ thuật máy tính (cid:1) TS. Vũ Đức Lung (cid:1) Email: lungvd@uit.edu.vn

Các khái niệm cơ bản

Đặc tả hình thức (Formal description)

(cid:1) Đặc tả hình thức cung cấp một mô tả chính xác về một ngôn

ngữ lập trình(nnlt)

(cid:1) NNLT = Ký hiệu + qui tắc kết hợp (cid:1) Cú pháp: sự kết hợp của các ký hiệu (dạng của biểu thức, các

phát biểu, các đơn vị nhỏ trong chương trình)

Đặc tả NNLT

(cid:1) Ngữ nghĩa: ý nghĩa của các kết hợp (cid:1) Ngữ dụng: Mối quan hệ của L (cú pháp+ngữ nghĩa) với thế

giới bên ngoài

(cid:1) Ví dụ 1:

– BT1 = 4 BT2 = 1 + 3

BT3 = 1 + 1 + 1 +1

Chương trình

Bộ dịch

(cid:1) VD 2: vòng lặp WHILE và REPEAT trong Pascal (cid:1) VD 3: Số lượng tối đa các phần tử mảng array phụ thuộc

– Kích thước kiểu dữ liệu – Dung lượng bộ nhớ

Khoa KTMT - UIT TS. Vũ Đức Lung 1 Khoa KTMT - UIT TS. Vũ Đức Lung 2

Đặc tả hình thức

Đặc tả từ vựng

(cid:1) Ngôn ngữ là tập hợp chuỗi các ký tự từ alphabet (A…Z, a…z,

(cid:1) Đặc tả hình thức cho phép:

$ @ 0 …9, + - = ….

(cid:1) Sự kết hợp một số ký tự trong alphabet → từ vựng

– VD: BEGIN

– Người học có thể tiếp thu nnlt dễ dàng – Bộ dịch có thể sinh mã đúng đắn – Bộ dịch có thể kiểm tra lỗi tự động – Có thể chứng minh được tính đúng đắn của chương trình

Lexemes

Tokens

(cid:1) Token là một dạng của lexeme – VD: index = 2*count + 17;

(cid:1) Đặc tả hình thức:

– Từ vựng – Văn phạm (cú pháp) – Ngữ nghĩa

Tokens tương tự như loại từ trong ngôn ngữ học. Tương tự như danh từ hay tính từ, động từ, tokens sẽ được định nghĩa gồm từ khóa (keyword), định danh (identifier), số nguyên, số chấm động tùy theo đặc điểm của trình biên dịch

Index = 2 * Count + 17 ;

Identifier Equal_sign Int_literal Mult_op Identifier Plus_op Int_literal semicolon

Khoa KTMT - UIT TS. Vũ Đức Lung 3 Khoa KTMT - UIT TS. Vũ Đức Lung 4

Khoa KTMT - UIT TS. Vũ Đức Lung 5 Khoa KTMT - UIT TS. Vũ Đức Lung 6

1 05/04/2012

Ngôn ngữ

Ví dụ: L = {A, B, ..., Z, a, b, ..., z } và

D = { 0, 1, , ..., 9 }

1. L ∪ D là tập hợp các chữ cái và chữ số 2. LD là tập hợp các xâu bao gồm một chữ cái và một chữ số

(cid:1) Chuỗi và ngôn ngữ – Tập hợp các ký tự Σ – Một chuỗi S trên Σ là 1 dãy hữu hạn các ký tự thuộc Σ – Chuỗi rỗng ∈∈∈∈ – Một ngôn ngữ L trên Σ là tập hợp các chuỗi trên Σ

3. L4 là tập hợp tất cả các xâu 4 chữ cái

(cid:1) Tác vụ trên ngôn ngữ

4. L * là tâp hợp tất cả các xâu của các chữ cái bao gồm cả chuỗi rỗng 5. L(L ∪ D)* là tập hợp tất cả các xâu mở đầu bằng một chữ cái theo sau là chữ

∪ L2

cái hay chữ số

– Hợp: – Kết nối: L1 L2

6. D+ là tập hợp tất cả các xâu gồm một hoặc nhiều chữ số

Biểu thức chính quy (regular expression)

Định nghĩa chính qui Định nghĩa chính qui (regular definition) (regular definition)

(cid:1) Để thuận tiện về mặt kí hiệu, ta dùng định nghĩa chính qui

(cid:1) Một chuỗi miêu tả một bộ các chuỗi khác, theo những quy tắc

(ĐNCQ) để đặt tên cho các BTCQ

cú pháp nhất định

(cid:1) Một ĐNCQ là một dãy các định nghĩa có dạng

(cid:1) Có thể hiểu như là 1 ngôn ngữ nhỏ dùng cho mục đích : để tìm

chuỗi con trong biểu thức chuỗi lớn

(cid:1) Microsoft cho nó vào Windows trong namespace .NET :

→ r1 → r2

d1 d2 ......... → rn dn

System.Text.RegularExpressions VD: email – /^(?:\w+\.?)*\w+@(?:\w+\.)+\w+$/ – Tìm hiểu các biểu thức chính qui trong RegularExpressionValidator

Trong đó di là các tên, ri là các BTCQ trên tập các kí hiệu Σ∪{d1, d2, ....di-1}

trong Validation Control trong ASP.NET?

Khoa KTMT - UIT TS. Vũ Đức Lung 7 Khoa KTMT - UIT TS. Vũ Đức Lung 8

Biểu thức chính quy

(cid:1) Ví dụ: ĐNCQ cho tập số không dấu được viết lại như sau

(cid:1) Để biểu diễn các tokens, người ta dùng biểu thức chính quy

digit → 0 | 1 |...| 9 digits → digit +

optional_fraction → (. digits) ? optional_exponent → ( E ( + | - ) ? digits) ? num → digits optional_fraction optional_exponent

a : có xuất hiện ký tự 'a' ab : có xuất hiện ký tự 'b' theo sau ký tự 'a' (theo đúng thứ tự) a|b : có 'a' hoặc có 'b' a* : xuất hiện nhiều hoặc không xuất hiện ký tự 'a' a+ : xuất hiện nhiều hoặc ít nhất là một ký tự 'a'

(cid:1) Sử dụng các tập kí tự [abc]=a | b | c, [a-z]=a | b |..z ta có thể đặc tả

các định danh bởi BTCQ

[A - Z a - z] [A - Z a - z 0 - 9]*

(a)+ == a(a)* a3 : xuất hiện 3 ký tự a a? : xuất hiện a hoặc không xuất hiện (a)? = a | ∈

(cid:1) VD: biểu diễn số nguyên:

digits = '0' | '1' | '2' | '3' | '4 | '5' | '6' | '7' | '8' | '9' integer = '−'?(digits)+

Khoa KTMT - UIT TS. Vũ Đức Lung 9 Khoa KTMT - UIT TS. Vũ Đức Lung 10

Khoa KTMT - UIT TS. Vũ Đức Lung 11 Khoa KTMT - UIT TS. Vũ Đức Lung 12

2 05/04/2012

Biểu thức chính quy

(cid:1) Biểu thức chính qui r diễn tả ngôn ngữ L(r)

{∈} ⇒

– ∈ ⇒ – a ∈ Σ

{a}

(cid:1) Giả sử r và s lần lượt diễn tả ngôn ngữ L(r) và L(s) thì

Ví dụ: Cho Σ= { a, b}. 1. BTCQ a | b đặc tả {a, b} 2. BTCQ (a | b) (a | b) đặc tả {aa, ab, ba, bb}.Tập hợp này có thể được đặc tả bởi BTCQ tương đương sau: aa | ab | ba | bb 3. BTCQ a* đặc tả {ε, a, aa, aaa, ... } 4. BTCQ (a | b)* đặc tả {a, b, aa,bb, ...}. Tập hợp này có thể đặc tả bởi (a*b* )* 5. BTCQ a | a* b đặc tả {a, b, ab, aab,... }

– (r) | (s) ⇒ L(r) ∪ L(s) – (r)(s) ⇒ L(r)L(s) – (r)* ⇒ (L(r))* – (r) ⇒ L(r)

Đặc tả cú pháp hình thức (Formal methods of Describing Syntax)

Ví dụ: ĐNCQ của các định danh trong pascal là

(cid:1)(cid:1) Cú pháp trừu tượng (Abstract syntax) Cú pháp trừu tượng (Abstract syntax)

(cid:1) Cú pháp cụ thể (concrete syntax)

letter → A | B | ...| Z | a | b |...| z digit → 0 | 1 | ...| 9 id → letter (letter | digit)*

– Văn phạm phi ngữ cảnh (context-free grammar) – BNF (Backus-Naur Form)

Ví dụ: ĐNCQ của các số không dấu trong pascal như 3254,

(cid:1) Sơ đồ cú pháp (Syntax diagrams) (cid:1) Chuỗi dẫn xuất và Cây phân tích (Derivations and parse

23.243E5,16.264E-3... là digit → 0 | 1 |...| 9 digits → digit digit*

trees)

optional_fraction → (. digits)? optional_exponent → ( E ( + | - )? digits)? num → digits optional_fraction optional_exponent

(cid:1) Sự nhập nhằng (Ambiguity) (cid:1) Tính kết hợp của toán tử (Associativity of Operator) (cid:1) BNF mở rộng (Extended BNF)

Khoa KTMT - UIT TS. Vũ Đức Lung 13 Khoa KTMT - UIT TS. Vũ Đức Lung 14

Cú pháp trừu tượng Cú pháp trừu tượng

• Ưu điểm: đơn giản

• Khuyết điểm:

(cid:1) Phân các yếu tố ngôn ngữ thành các lớp văn phạm (Syntactic class)

(cid:2) Không có định nghĩa ký tự kết thúc (cid:2) Có thể xảy ra hiện tượng nhập nhằng

(cid:1) Liệt kê tất cả các dạng

(Syntactic form) của mỗi lớp

(cid:1) Ví dụ:

– Lớp cú pháp:

C Hằng (constant) I Định danh (Identifier) O Toán tử (operator) E Biểu thức (expression)

– Dạng cú pháp:

E ::= I | C | E O E | ( E )

Khoa KTMT - UIT TS. Vũ Đức Lung 15 Khoa KTMT - UIT TS. Vũ Đức Lung 16

Khoa KTMT - UIT TS. Vũ Đức Lung 17 Khoa KTMT - UIT TS. Vũ Đức Lung 18

3 05/04/2012

Đặc tả cú pháp hình thức (Formal methods of Describing Syntax)

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

(cid:1) Cú pháp trừu tượng (Abstract syntax)

(cid:1) 1956-1959, Chomsky (cid:1) Là một bộ gồm 4 thành phần:

(cid:1)(cid:1) Cú pháp cụ thể (concrete syntax) Cú pháp cụ thể (concrete syntax) – Văn phạm phi ngữ cảnh (context-free grammar) – BNF (Backus-Naur Form)

(cid:1) Sơ đồ cú pháp (Syntax diagrams) (cid:1) Chuỗi dẫn xuất và Cây phân tích (Derivations and parse

(cid:2) Ký hiệu bắt đầu S ∈ N(Start symbol) (cid:2) Tập các ký hiệu không kết thúc N (Non-terminals) (cid:2) Tập các ký hiệu kết thúc Σ (Terminals) (cid:2) Tập các luật sinh (Production) có dạng: A →→→→ αααα

trees)

Với A ∈ N và α là chuỗi các ký hiệu kết thúc và không kết thúc

(cid:1) Sự nhập nhằng (Ambiguity) (cid:1) Tính kết hợp của toán tử (Associativity of Operator) (cid:1) BNF mở rộng (Extended BNF)

Naur Form) BNF (Backus--Naur Form) BNF (Backus

Ví dụ số nguyên không dấu Ví dụ số nguyên không dấu (Unsigned Integers) (Unsigned Integers)

• Ký hiệu bắt đầu

• Ký hiệu không kết thúc ,

(cid:1) 1959, John Backus giới thiệu ALGOL 58 thuộc nhóm ACM-GAMM (cid:1) 1960 Peter Naur cho ra phiên bản mới ALGOL 60 (cid:1) BNF là một ký hiệu tự nhiên mô tả cú pháp, là một siêu ngôn ngữ mô tả ngôn ngữ khác (cid:1) Rất gần với văn phạm phi ngữ cảnh

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

• Ký hiệu kết thúc

• Luật

VD: ::= |

→ |

Khoa KTMT - UIT TS. Vũ Đức Lung 19 Khoa KTMT - UIT TS. Vũ Đức Lung 20

Naur Form) BNF (Backus--Naur Form) BNF (Backus

Ví vụ một biểu thức Ví vụ một biểu thức

(cid:2) Start symbol (cid:2) Non-terminals

, , ,

, ,

(cid:1) left-hand side (LHS) (cid:1) right-hand side (RHS) (cid:1) Có thể có nhiều RHS

(cid:2) Terminals

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, *, /

VD:

-> | begin end

(cid:2) Productions:

(cid:1) Danh sách cú pháp ( Syntactic lists) dùng đệ qui

→→→→ |

-> ident | ident,

→→→→ |

→→→→ | ()

→→→→ + | −−−−

→→→→ ∗∗∗∗ | ////

Khoa KTMT - UIT TS. Vũ Đức Lung 21 Khoa KTMT - UIT TS. Vũ Đức Lung 22

Khoa KTMT - UIT TS. Vũ Đức Lung 23 Khoa KTMT - UIT TS. Vũ Đức Lung 24

4 05/04/2012

Đặc tả cú pháp hình thức (Formal methods of Describing Syntax)

Sơ đồ cú pháp Sơ đồ cú pháp (Syntax Diagrams) (Syntax Diagrams)

Sơ đồ cú pháp của biểu thức

(cid:1) Cú pháp trừu tượng (Abstract syntax)

exp

(cid:1) Cú pháp cụ thể (concrete syntax)

term

– Văn phạm phi ngữ cảnh (context-free grammar) – BNF (Backus-Naur Form) (cid:1)(cid:1) Sơ đồ cú pháp (Syntax diagrams) Sơ đồ cú pháp (Syntax diagrams) (cid:1) Chuỗi dẫn xuất và Cây phân tích (Derivations and parse

exp

term_op

term

trees)

(cid:1) Sự nhập nhằng (Ambiguity) (cid:1) Tính kết hợp của toán tử (Associativity of Operator) (cid:1) BNF mở rộng (Extended BNF)

Đặc tả cú pháp hình thức (Formal methods of Describing Syntax)

Chuỗi dẫn xuất Chuỗi dẫn xuất (Derivations) (Derivations)

Chuỗi dẫn xuất của biểu thức: 32*5 + 8

(cid:1) Cú pháp trừu tượng (Abstract syntax)

(cid:1) Cú pháp cụ thể (concrete syntax)

– Văn phạm phi ngữ cảnh (context-free grammar) – BNF (Backus-Naur Form)

⇒ ⇒ + ⇒ + ⇒ * + 8 ⇒ * 5 + 8 ⇒ 32 * 5 + 8

(cid:1) Sơ đồ cú pháp (Syntax diagrams) (cid:1)(cid:1) Chuỗi dẫn xuất và Cây phân tích (Derivations and Chuỗi dẫn xuất và Cây phân tích (Derivations and parse trees) parse trees)

(cid:1) Sự nhập nhằng (Ambiguity) (cid:1) Tính kết hợp của toán tử (Associativity of Operator) (cid:1) BNF mở rộng (Extended BNF)

Khoa KTMT - UIT TS. Vũ Đức Lung 25 Khoa KTMT - UIT TS. Vũ Đức Lung 26

Cây phân tích cú pháp Cây phân tích cú pháp (Parse Trees) (Parse Trees)

Cây cú pháp Cây cú pháp (Parse Trees) (Parse Trees)

Cây cú pháp

Khoa KTMT - UIT TS. Vũ Đức Lung 27 Khoa KTMT - UIT TS. Vũ Đức Lung 28

Khoa KTMT - UIT TS. Vũ Đức Lung 29 Khoa KTMT - UIT TS. Vũ Đức Lung 30

5 05/04/2012

Đặc tả cú pháp hình thức (Formal methods of Describing Syntax)

Sự nhập nhằng Sự nhập nhằng (Ambiguity) (Ambiguity)

(cid:1) Văn phạm cho câu lệnh gán đơn giản

(cid:1) Cú pháp trừu tượng (Abstract syntax)

(cid:1) Cú pháp cụ thể (concrete syntax)

→→→→ = →→→→ A|B|C →→→→ + | * | () |

– Văn phạm phi ngữ cảnh (context-free grammar) – BNF (Backus-Naur Form)

(cid:1) VD biểu thức gán: A = B * (A + C) có chuỗi dẫn xuất cực tả:

(cid:1) Sơ đồ cú pháp (Syntax diagrams) (cid:1) Chuỗi dẫn xuất và Cây phân tích (Derivations and parse

trees) (cid:1)(cid:1) Sự nhập nhằng (Ambiguity) Sự nhập nhằng (Ambiguity) (cid:1) Tính kết hợp của toán tử (Associativity of Operator) (cid:1) BNF mở rộng (Extended BNF)

Sự nhập nhằng Sự nhập nhằng (Ambiguity) (Ambiguity)

(cid:1) Văn phạm cho câu lệnh gán đơn giản (mở rộng VD trước)

→→→→ = →→→→ A|B|C →→→→ + | * | () |

(cid:1) Là một văn phạm nhập nhằng vì A = B + C * A có 2 cây cú pháp

Khoa KTMT - UIT TS. Vũ Đức Lung 31 Khoa KTMT - UIT TS. Vũ Đức Lung 32

Sự nhập nhằng Sự nhập nhằng (Ambiguity) (Ambiguity)

Đặc tả cú pháp hình thức (Formal methods of Describing Syntax)

(cid:1) Văn phạm không nhập nhằng cho câu lệnh gán đơn giản

(cid:1) Cú pháp trừu tượng (Abstract syntax)

(cid:1) Cú pháp cụ thể (concrete syntax)

– Văn phạm phi ngữ cảnh (context-free grammar) – BNF (Backus-Naur Form)

→→→→ = →→→→ A|B|C →→→→ + | term →→→→ * | factor →→→→ () |

(cid:1) Sơ đồ cú pháp (Syntax diagrams) (cid:1) Chuỗi dẫn xuất và Cây phân tích (Derivations and parse

trees)

(cid:1) Sử dụng toán tử ưu tiên (operator precedence) (cid:1) VD tìm chuỗi dẫn xuất và cây cú pháp cho biểu thức :

A = B + C * A

(cid:1) Sự nhập nhằng (Ambiguity) (cid:1)(cid:1) Tính kết hợp của toán tử (Associativity of Operator) Tính kết hợp của toán tử (Associativity of Operator) (cid:1) BNF mở rộng (Extended BNF)

Khoa KTMT - UIT TS. Vũ Đức Lung 33 Khoa KTMT - UIT TS. Vũ Đức Lung 34

Khoa KTMT - UIT TS. Vũ Đức Lung 35 Khoa KTMT - UIT TS. Vũ Đức Lung 36

6 05/04/2012

Tính kết hợp của toán tử (Associativity of Operator)

Đặc tả cú pháp hình thức (Formal methods of Describing Syntax)

(cid:1) Cú pháp trừu tượng (Abstract syntax)

(cid:1) Đối với các toán tử có cùng mức độ ưu tiên (cid:1) VD: A = B + C + A

(cid:1) Cú pháp cụ thể (concrete syntax)

– Biến là số nguyên: không có sự khác biệt – Biến là số chấm động: có khác biệt, ví dụ số chấm động dùng độ chính

– Văn phạm phi ngữ cảnh (context-free grammar) – BNF (Backus-Naur Form)

xác 7 bit (1 bit trước dấu phẩy và 6 bit sau dấu phẩy)

107 + 1 + … + 1 = ?

(cid:1) Sơ đồ cú pháp (Syntax diagrams) (cid:1) Chuỗi dẫn xuất và Cây phân tích (Derivations and parse

trees)

10 – (107 + 1) + 1 + … = ? – 1 + 1 + … + 107 = ?

(cid:1) Sự nhập nhằng (Ambiguity) (cid:1) Tính kết hợp của toán tử (Associativity of Operator) (cid:1)(cid:1) BNF mở rộng (Extended BNF) BNF mở rộng (Extended BNF)

BNF mở rộng (Extended BNF)

BNF vs EBNF

(cid:1) Không làm tăng khả năng đặc tả của BNF, chỉ là cách biểu

BNF:

diễn gọn hơn

1. Phần lựa chọn được đặt vào trong dấu []

-> + | - |

-> if () [else )]

2. Đặt những phần tương tự trong RHS vào trong () và ngăn

-> * | / |

cách bởi | -> (+ | -) const

EBNF:

3. Đặt những phần lập lại trong {}

-> letter {letter | digit}

(cid:1)

-> {(+ | -) } -> {(* | /) }

Khoa KTMT - UIT TS. Vũ Đức Lung 37 Khoa KTMT - UIT TS. Vũ Đức Lung 38

Ngữ nghĩa hình thức (Formal Semantics)

(cid:1) Đặc tả ngữ nghĩa hình thức cho phép:

– Chứng minh tính đúng đắn của chương trình

– Kiểm tra tính đúng đắn của chương trình dịch

(cid:1) Các phương pháp đặc tả:

Khoa KTMT - UIT TS. Vũ Đức Lung 39 Khoa KTMT - UIT TS. Vũ Đức Lung 40

BÀI TẬP

(cid:2) Ngữ nghĩa tác vụ (Operational semantics) (cid:2) Ngữ nghĩa tiên đề (Axiomatic semantics) (cid:2) Ngữ nghĩa biểu thị (Denotational semantics)

Khoa KTMT - UIT TS. Vũ Đức Lung 41 Khoa KTMT - UIT TS. Vũ Đức Lung 42

7 05/04/2012

Yêu cầu

Ngữ nghĩa hình thức (Formal Semantics)

(cid:1) Đầy đủ

(cid:1) Đặc tả ngữ nghĩa hình thức cho phép:

– Chứng minh tính đúng đắn của chương trình

Mọi chương trình đúng và dừng thì phải có ngữ nghĩa phù hợp được cho bởi các luật

– Kiểm tra tính đúng đắn của chương trình dịch

(cid:1) Nhất quán

(cid:1) Các phương pháp đặc tả:

Cùng một chương trình không thể cho nhiều ngữ nghĩa khác nhau và mâu thuẫn

(cid:1) Không phụ thuộc

Không có luật nào có thể dẫn xuất từ một luật khác

(cid:2)(cid:2) Ngữ nghĩa tác vụ (Operational semantics) Ngữ nghĩa tác vụ (Operational semantics) (cid:2) Ngữ nghĩa tiên đề (Axiomatic semantics) (cid:2) Ngữ nghĩa biểu thị (Denotational semantics)

Ngữ nghĩa tác vụ (Operational Semantics)

Ngữ nghĩa tác vụ

(cid:1) Dùng ngữ nghĩa tác vụ để đặc tả ngữ nghĩa một ngôn ngữ lập trình L cần:

(cid:1) Ý tưởng: đặc tả ý nghĩa một chương trình khi thực thi từng câu

lệnh trên máy tính (máy thật hoặc mô phỏng)

– Bộ chuyển đổi (translator) đổi L thành ngôn ngữ cấp thấp – Máy ảo cho ngôn ngữ cấp thấp

(cid:1) VD:

(cid:1) Sự thay đổi trạng thái của máy tính cho ta ý nghĩa của câu lệnh (cid:1) Dựa vào một máy ảo mà tập các tác vụ của nó đã được định

nghĩa chính xác

(cid:1) Ngữ nghĩa của mỗi phần tử chương trình được đặc tả bằng 1

tập các tác vụ của máy ảo

Ngôn ngữ C: for ( expr1; expr2; expr3 ) { }

Ngữ nghĩa tác vụ: expr1; Loop: if expr2 == 0 goto out … Expr3; goto Loop; out:…

Khoa KTMT - UIT TS. Vũ Đức Lung 43 Khoa KTMT - UIT TS. Vũ Đức Lung 44

Ngữ nghĩa tiên đề (Axiomatic semantics)

Ngữ nghĩa hình thức (Formal Semantics)

(cid:1) Đặc tả ngữ nghĩa hình thức cho phép:

– Chứng minh tính đúng đắn của chương trình

• Ý nghĩa của chương trình được xác định bởi tập hợp các quy tắc làm thay đổi dữ liệu sau khi thực hiện một phép toán nào đó của ngôn ngữ lập trình.

– Kiểm tra tính đúng đắn của chương trình dịch

• NNTĐ dùng để chứng minh các tính chất của chương

(cid:1) Các phương pháp đặc tả:

trình

• Tác dụng của một phát biểu (statement) được định

nghĩa thông qua tiền diều kiện (precondition) và hậu điều kiện (postcondition).

(cid:2) Ngữ nghĩa tác vụ (Operational semantics) (cid:2)(cid:2) Ngữ nghĩa tiên đề (Axiomatic semantics) Ngữ nghĩa tiên đề (Axiomatic semantics) (cid:2) Ngữ nghĩa biểu thị (Denotational semantics)

• Tập hợp các tiên đề và luật cho định nghĩa tác dụng của

chương trình.

Khoa KTMT - UIT TS. Vũ Đức Lung 45 Khoa KTMT - UIT TS. Vũ Đức Lung 46

Khoa KTMT - UIT TS. Vũ Đức Lung 47 Khoa KTMT - UIT TS. Vũ Đức Lung 48

8 05/04/2012

Ngữ nghĩa tiên đề

(cid:1) Ký hiệu NNTĐ thông thường: {P} S {Q}

{P} S {Q}

• x = E, Q – hậu đk

Tiền ĐK

Phát biểu

Hậu ĐK

• Tiên đề: P = Qx→E

• VD: a = b/2 – 1 {a < 10} => P={b<22}

(cid:1) Nếu P đúng thì sau khi S đươc thực thi xong thì Q đúng (cid:1) Tiền điều kiện yếu nhất (weakest precondition) ωp(S,Q) là tiền điều kiện

yếu nhất có thể thỏa mãn

(cid:1) Phát biểu gán: {Qx→E} x := E {Q} (cid:1) Nhiều sách ghi:

VD: a := b + 1 {a > 1}

{Px→E} x := E {P}

một tiền đk có thể: {b > 10} Tiền đk yếu nhất: {b > 0}

(cid:1) VD: x = 2*y – 3 {x>25} => {y>14}

(cid:1) ωωωωp(S,Q) với Q là biến số có thể xem là ngữ nghĩa chính xác của S

Ngữ nghĩa tiên đề

(cid:1)(cid:1) HỆ LUẬT HOARE HỆ LUẬT HOARE

Chứng minh tính đúng của chương trình

VD: {x > 3} x := x - 3 {x > 0}

L1: Nếu {P} S {Q} ∧ (Q ⇒ R) thì {P} S {R} L2: Nếu {P} S {Q} ∧ (R ⇒ P) thì {R} S {Q} L3: {Qx→E} x := E {Q}

VD1: CM tính đúng: {x > 5} x := x - 3 {x > 0} ? VD2: CM tính đúng của đặc tả:

E = x - 3 Q = x > 0 Qx→E = x - 3 > 0 = x > 3

Trong trường hợp {x > 5} x := x - 3 {x > 0} ?

{f=i!} i:=i+1 {f*i=i!} VD3: CM tính đúng của đặc tả: {f*i=i!} f:=f*i {f=i!}

Khoa KTMT - UIT TS. Vũ Đức Lung 49 Khoa KTMT - UIT TS. Vũ Đức Lung 50

Ngữ nghĩa tiên đề

(cid:1)(cid:1) HỆ LUẬT HOARE HỆ LUẬT HOARE

L4: luật phát biểu ghép (sequences) if ({P} S1 {Q}) ∧∧∧∧ ({Q} S2 {R}) then

{P} S1 ; S2 {R}

VD4: CM tính đúng của đặc tả:

{f=i!} i:=i+1, f = f*i {f = i!}

Với ¬B = NOT B

CM: theo vd 2 & 3

VD4: CM tính đúng của đặc tả:

{xy<0} if x>y then max:=x else max:=y {max>0}

CM: theo L3 & L2

Khoa KTMT - UIT TS. Vũ Đức Lung 51 Khoa KTMT - UIT TS. Vũ Đức Lung 52

Khoa KTMT - UIT TS. Vũ Đức Lung 53 Khoa KTMT - UIT TS. Vũ Đức Lung 54

9 05/04/2012

Ngữ nghĩa tiên đề

Chứng minh chương trình Chứng minh chương trình (Program Proofs) (Program Proofs)

(cid:1)(cid:1) HỆ LUẬT HOARE HỆ LUẬT HOARE

VD4: CM tính đúng của đặc tả:

{f=i!} while i # n do begin i:=i+1; f:=f*I end {f=n!}

(cid:1) VD: Chứng minh tính ñúng của chương trình

CM:

{ x = A AND y = B} t = x; x = y; y = t; {x = B AND y = A}

Ngữ nghĩa biểu thị (Denotational semantics)

Ngữ nghĩa hình thức (Formal Semantics)

(cid:1) Đặc tả ngữ nghĩa hình thức cho phép:

– Chứng minh tính đúng đắn của chương trình

– Kiểm tra tính đúng đắn của chương trình dịch

(cid:1) Trên cơ sở lý thuyết hàm đệ qui (cid:1) Phương pháp đặc tả ngữ nghĩa trừ tượng nhất (cid:1) Phiên bản gốc được phát triển bởi Scott và Strachey (1970) (cid:1) Tiến trình xây dựng đặc tính biểu thị cho một ngôn ngữ:

(cid:1) Các phương pháp đặc tả:

1. định nghĩa các đối tượng toán học cho mỗi thực thể ngôn ngữ

2. Định nghĩa hàm ánh xạ mỗi thể hiện của thực thể đến thể hiện của đối tượng toán học tương ứng

(cid:2) Ngữ nghĩa tác vụ (Operational semantics) (cid:2) Ngữ nghĩa tiên đề (Axiomatic semantics) (cid:2)(cid:2) Ngữ nghĩa biểu thị (Denotational semantics) Ngữ nghĩa biểu thị (Denotational semantics)

(cid:1) Mỗi cấu trúc chương trình là một hàm ánh xạ đầu vào đến đầu ra (cid:1) Một chương trình là sự hợp thành của nhiều hàm (cid:1) Sự khác nhau giữa ngữ nghĩa tác vụ và ngữ nghĩa biểu thị: Trong NN tác vụ trạng thái thay đổi bởi thuật toán, còn trong NN biểu thị NN được định nghĩa là các hàm toán học chính xác

Khoa KTMT - UIT TS. Vũ Đức Lung 55 Khoa KTMT - UIT TS. Vũ Đức Lung 56

Ngữ nghĩa biểu thị

(cid:1) VD cấu trúc ngôn ngữ số nhị phân.

(cid:1) Ngữ nghĩa biểu thị của các ký tự số thập phân

– Cú pháp: → 0 | 1 | 0 | 1 – Để biểu thị ý nghĩa của số nhị phân sử dụng ngữ nghĩa biểu thị và cú

→→→→ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | (0 | 1 | 2 | 3 | 4 |

pháp trên sử dụng hàm ngữ nghĩa:

5 | 6 | 7 | 8 | 9)

• Mbin(‘0’) = 0 • Mbin(‘1’) = 1 • Mbin( ‘0’) = 2* Mbin() • Mbin( ‘1’) = 2* Mbin() + 1

Cây phân tích số 110 và ngữ nghĩa biểu thị của nó?

Mdec('0') = 0, Mdec ('1') = 1, …, Mdec ('9') = 9 Mdec ( '0') = 10 * Mdec () Mdec ( '1’) = 10 * Mdec () + 1 … Mdec ( '9') = 10 * Mdec () + 9

Khoa KTMT - UIT TS. Vũ Đức Lung 57 Khoa KTMT - UIT TS. Vũ Đức Lung 58

Khoa KTMT - UIT TS. Vũ Đức Lung 59 Khoa KTMT - UIT TS. Vũ Đức Lung 60

10 05/04/2012

BÀI TẬP

Khoa KTMT - UIT TS. Vũ Đức Lung 61

11 05/04/2012

CHƯƠNG 33:TRÌNH BIÊN DỊCH CHƯƠNG

:TRÌNH BIÊN DỊCH ĐĐƠƠN N GIẢGIẢNN

TRÌNH BIÊN DỊCH TRÌNH BIÊN DỊCH (COMPILER) (COMPILER)

Nội dung: Nội dung: (cid:2) Định nghĩa cú pháp (cid:2) Cây phân tích (cid:2) Biên dịch điều khiển bởi cú pháp (cid:2) Lược đồ dịch (cid:2) Phân tích cú pháp

• •

Phân tích cú pháp từ trên xuống Sự phân tích cú pháp đoán nhận trước

(cid:2) Sự phân tích từ vựng (cid:2) Thiết kế trình biên dịch đơn giản

(cid:1) Khoa Kỹ thuật máy tính (cid:1) TS. Vũ Đức Lung (cid:1) Email: lungvd@uit.edu.vn

Tổng quát Tổng quát

Định nghĩa cú pháp Định nghĩa cú pháp

(cid:2) Ta dùng văn phạm phi ngữ cảnh để miêu tả cú pháp cho

(cid:1) Cấu trúc trình biên dịch “Front end”

ngôn ngữ.

(cid:2) Văn phạm phi ngữ cảnh (PNC) được định nghĩa:

G = (Vt, Vn, S, P) P : A -> α1| α 2|………| α n

(cid:2) Ví dụ 1:

Cho văn phạm G: P: list -> list + digit |list –digit |digit

digit ->0 |1|2 |…|9

FCE-UIT TS. Vũ Đức Lung 1 FCE-UIT TS. Vũ Đức Lung 2

Định nghĩa cú pháp Định nghĩa cú pháp

Cây phân tích Cây phân tích

(cid:2) Ví dụ 2: Văn phạm miêu tả phát biểu hỗn hợp begin end của

1. Gốc là ký hiệu mục tiêu S. 2. Mỗi lá là token hay ký hiệu rỗng €. 3. Mỗi nút không phải là nút cuối của cây là ký hiệu

Pascal P : block -> begin opt_stmts end opt_stmts-> stmt_list |€ stmt_list -> stmt_list ; stmt |stmt

không kết thúc.

4. Nếu A là nhãn của nút không phải là nút cuối, X1, X2, …Xn là nhãn các con của nút có nhãn Atừ trái sang phải thì A-> X1X2…Xn là luật sinh thuộc tập luật sinh P.

FCE-UIT TS. Vũ Đức Lung 3 FCE-UIT TS. Vũ Đức Lung 4

FCE-UIT TS. Vũ Đức Lung 5 FCE-UIT TS. Vũ Đức Lung 6

1 05/04/2012

Cây phân tích Cây phân tích

Sự kết hợp của các toán tử Sự kết hợp của các toán tử

(cid:2) Mức ưu tiên của các toán tử: * và / có mức ưu tiên hơn + , -. Dựa vào nguyên tắc trên chúng ta xây dựng cú pháp cho biểu thức số học:

(cid:2) Lưu ý: phép toán lũy thừa và phép gán trong C là phép toán kết

hợp phải. Văn phạm cho phép gán như sau:

assign -> letter = right |letter right-> right|letter letter -> a |b |…|z

ch điềều khi

u khiểển bn bởởi i cú phá

cú phápp

Biên dịdịch đi Biên

ch điềều khi

u khiểển bn bởởi i cú phá

cú phápp

Biên Biên dịdịch đi Directed Translation Syntax--Directed Translation Syntax

2. Định nghĩa trực tiếp cú pháp (Syntax-directed definition)

(cid:1) Dùng: dịch các cấu trúc ngôn ngữ lập trình (cid:1) Phần tử: kết hợp giữa thuộc tính & các thành phần cú pháp (cid:1) Biểu thức số học: Infix expression, postfix expression (cid:1) Ký hiệu hậu tố (postfix notation):

Văn phạm phi ngữ cảnh và tập luật ngữ nghĩa sẽ thiết lập định nghĩa trực tiếp cú pháp. Biên dịch là phép ánh xạ từ nhập → xuất. Dạng xuất của chuỗi nhập x được xác định như sau: 1. Xây dựng cây phân tích cho chuỗi x. 2. Giả sử nút n của cây phân tích có tên cú pháp X, X.a biểu thị giá trị thuộc tính a của X tại nút n. X.a được tính nhờ luật ngữ nghĩa. Cây phân tích có chú thích các trị thuộc tính ở mỗi nút được gọi là cây phân tích chú thích (annotated parse tree)

1) Nếu E là biến hoặc hằng số thì ký hiệu hậu tố của E chính là E. 2) Nếu E là biểu thức có dạng E1 op E2 với op là toán tử hai ngôi thì ký hiệu hậu tố của E là E1’E2’ op. 3) Nếu E là biểu thức có dạng (E1) thì ký hiệu hậu tố của E1 cũng là ký hiệu hậu tố của E. Lưu ý: Không cần có dấu đóng, mở ngoặc trong ký hiệu

hậu tố.

FCE-UIT TS. Vũ Đức Lung 7 FCE-UIT TS. Vũ Đức Lung 8

Biên Biên dịdịch đi

ch điềều khi

u khiểển bn bởởi i cú phá

cú phápp

Biên dịdịch đi Biên

ch điềều khi

u khiểển bn bởởi i cú phá

cú phápp

Ví dụ 4: cây phân tích chú thích câu 9 – 5 + 2

Tổng hợp thuộc tính (synthesized attributes) Ví dụ 3. Cho văn phạm G có tập luật sinh P:

FCE-UIT TS. Vũ Đức Lung 9 FCE-UIT TS. Vũ Đức Lung 10

FCE-UIT TS. Vũ Đức Lung 11 FCE-UIT TS. Vũ Đức Lung 12

2 05/04/2012

Lược đồ dịch Lược đồ dịch

Ví dụ 6: Lược đồ dịch cho câu 9 – 5 + 2

(cid:2) Lược đồ dịch là văn phạm PNC, trong đó các đoạn chương trình gọi là hành vi ngữ nghĩa được nhúng vào vế phải của luật sinh.

(cid:2) Ví dụ 5:. Lược đồ dịch của văn phạm G:

Phân tích cú pháp Phân tích cú pháp

Giải thuật duyệt theo chiều sâu Giải thuật duyệt theo chiều sâu first traversals) của cây phân tích (depth--first traversals) của cây phân tích (depth

Phân tích cú pháp từ trên xuống Phân tích cú pháp từ trên xuống (cid:2) Ví dụ 7. Cho văn phạm G:

Procedure visit (n: node); begin

For với mỗi con m của n, từ trái sang phải do

type -> simple |↑id| array [simple] of type simple -> integer|char|num dotdot num

(cid:2) Hãy xây dựng cây phân tích cho câu:

visit (m); Tính trị ngữ nghiã tại nút n

array [num dotdot num] of integer

end;

FCE-UIT TS. Vũ Đức Lung 13 FCE-UIT TS. Vũ Đức Lung 14

Sự phân tích cú pháp đoán nhận trước Sự phân tích cú pháp đoán nhận trước

Xây dựng cây phân tích cho câu Xây dựng cây phân tích cho câu

(cid:2)

Dạng đặc biệt của phân tích cú pháp từ trên xuống là phương pháp đoán nhận trước. Phương pháp này sẽ nhìn trước một ký hiệu nhập để quyết định chọn thủ tục cho ký hiệu không kết thúc tương ứng. Thí dụ 8. Cho văn phạm G:

P: S -> xA

A -> z |yA

(cid:2)

Dùng văn phạm G để phân tích câu nhập xyyz

FCE-UIT TS. Vũ Đức Lung 15 FCE-UIT TS. Vũ Đức Lung 16

FCE-UIT TS. Vũ Đức Lung 17 FCE-UIT TS. Vũ Đức Lung 18

3 05/04/2012

Sự phân tích cú pháp đoán nhận trước Sự phân tích cú pháp đoán nhận trước

(cid:2) Thí dụ 9. Cho văn phạm với các luật sinh như sau:

S -> A |B A -> xA|y B -> xB|z Phân tích cú pháp cho câu

xxxz không thành công

Sự phân tích cú pháp đoán nhận trước Sự phân tích cú pháp đoán nhận trước

(cid:1) Ví dụ 10: Cho văn phạm G có tập luật sinh:

S → Ax A → x | ∈ Phân tích câu nhập x: sự phân tích thất bại

FCE-UIT TS. Vũ Đức Lung 19 FCE-UIT TS. Vũ Đức Lung 20

Sự phân tích từ vựng Sự phân tích từ vựng

Sự hình thành bảng danh biểu Sự hình thành bảng danh biểu

1. Giao tiếp với bảng danh biểu

Hai thao tác với bảng danh biểu: insert(s,t) và lookup(s).

2. Lưu giữ từ khóa 3. Hiện thực bảng danh biểu

1. Loại bỏ khoảng trắng và chú thích 2. Nhận biết các hằng 3. Nhận biết danh biểu và từ khóa Nhận dạng token của bộ phân tích từ vựng

Bảng danh biểu gồm có bảng symtable và dãy lexemes.

FCE-UIT TS. Vũ Đức Lung 21 FCE-UIT TS. Vũ Đức Lung 22

FCE-UIT TS. Vũ Đức Lung 23 FCE-UIT TS. Vũ Đức Lung 24

4 05/04/2012

Sự hình thành bảng danh biểu Sự hình thành bảng danh biểu

Thiết kế trình biên dịch đơn giản Thiết kế trình biên dịch đơn giản

Đặc tả trình biên dịch

start->list eof list->exp ;list | € exp -> exp + term {print (‘+’)} | exp–term {print (‘-’)} | term

term-> term * factor {print (‘*’)} | term /factor {print(‘/’)} | term divfactor {print (‘div’)} | term modfactor {print (‘mod’)} | factor factor ->(exp) |id|num

scanner: phân tích từ vụng scanner: phân tích từ vụng

Nhiệm vụ của các chương trình Nhiệm vụ của các chương trình con của trình biên dịch con của trình biên dịch

(cid:2) Các token cần được nhận dạng: (cid:2) +, -, *, /, div, mod, (, ), ID, NUM, DONE

(cid:1) scanner: phân tích từ vụng. (cid:1) parser: phân tích cú pháp. (cid:1) emit: tạo dạng xuất của token. (cid:1) symbol: xây dựng bảng danh biểu và thao tác với bảng danh

biểu bằng insert và lookup.

(cid:1) init: cất các từ khóa vào bảng danh biểu. (cid:1) error: thông báo lỗi.

FCE-UIT TS. Vũ Đức Lung 25 FCE-UIT TS. Vũ Đức Lung 26

parser: phân tích cú pháp parser: phân tích cú pháp

Giải thuật của trình biên dịch Giải thuật của trình biên dịch

(cid:2) Lược đồ dịch trực tiếp cú pháp cuả G sau khi được bỏ đệ

const bsize = 128; lpara= 40; rpara=41

quy trái:

none = 35; plus = 43; num = 256; minus = 45; div = 257; star = 42; mod = 258; slash = 47; id = 259; done = 260; strmax = 999;{Kích thước của dãy Lexemes} symax = 100; {Kích thước của Symtable}

FCE-UIT TS. Vũ Đức Lung 27 FCE-UIT TS. Vũ Đức Lung 28

FCE-UIT TS. Vũ Đức Lung 29 FCE-UIT TS. Vũ Đức Lung 30

5 05/04/2012

Giải thuật của trình biên dịch Giải thuật của trình biên dịch

Type entry = record

lexptr: integer; token : integer;

end;

Var str = string;

symtable: array [1..symax] of entry; lexbuf: string [bsize]; typetoken: integer; lexemes: array[1..strmax] of char; lastentry: integer; lastchar: integer;

tokenval: integer; {Trị thuộc tính của token} lineno: integer; lookahead: char;

FCE-UIT TS. Vũ Đức Lung 31 FCE-UIT TS. Vũ Đức Lung 32

scanner scanner

if t in [‘0’..’9’] then begin

Procedure scanner; Var t: char;

p, b, i: integer;

begin

val( i,t,e); {Dùng để kiểm tra ký tự đọc vào là ký tự số hay không} tokenval := 0; while e = 0 do begin

repeat

tokenval:= tokenval*10 + I; read (t); val(i,t,e);

read (t) if t = ‘\n’ then

end; typetoken := num;

lineno:= lineno+ 1;

end

until (t < > ‘ ‘) and (t < > ‘\t’) and (t <> ‘\n’);

FCE-UIT TS. Vũ Đức Lung 33 FCE-UIT TS. Vũ Đức Lung 34

scanner scanner

Error(“Lỗi thời gian dịch” ,lineno);

else if t in [ ‘A’..’Z’,’a’..’z’] then begin

end;

p:= 0; b := 0; while t in [‘0’..’9’,’A’..’Z’,’a’..’z’] do begin

lexbuf[b] := eos; p := lookup (lexbuf); if p = 0 then

p := insert ( lexbuf, id); tokenval:= p; typetoken:= symtable[p].token;

lexbuf[b] := t; read (t); b := b + 1; if(b > = bsize) then

end

FCE-UIT TS. Vũ Đức Lung 35 FCE-UIT TS. Vũ Đức Lung 36

6 05/04/2012

parser parser

scanner scanner

Procedure parser;

else if t = eof then

procedure exp;

typetoken:= done

else

begin

var t : integer; procedure term; var t : integer; procedure factor; begin

typetoken := ord(t); tokenval:= none;

case lookahead of

end

lpara:begin match ( lpara); exp; match(rpara);

end;

end; end; {scanner}

parser parser

num : begin

begin{term}

emit (num, tokenval); match (num)

factor; while lookahead in [star, slash, div, mod] do

end; id:begin

begin

emit (id, tokenval); match (id)

end;

else error (“Lỗi cú pháp”, lineno);

t := lookahead; match (lookahead); factor; emit (t, none);

end; {case}

end;{factor}

end; end; {term}

FCE-UIT TS. Vũ Đức Lung 37 FCE-UIT TS. Vũ Đức Lung 38

parser parser

begin{exp}

begin{parser}

scanner; lookahead:= typetoken; While lookahead< > done do

term; while (lookahead= plus) or (lookahead= minus) do begin

begin

exp; match (semicolon);

t := lookahead; match (lookahead); term; emit (t, none);

end;

end; end; {parser}

end;

FCE-UIT TS. Vũ Đức Lung 39 FCE-UIT TS. Vũ Đức Lung 40

FCE-UIT TS. Vũ Đức Lung 41 FCE-UIT TS. Vũ Đức Lung 42

7 05/04/2012

matchmatch

emit emit

Procedure emit (t : integer; tval: integer);

Procedure match (t : integer); begin

begin

Case t of

if lookahead= t then begin

scanner; lookahead:= typetoken;

end; else

error (“Lỗi cú pháp”, lineno);

plus, minus, star, slash : writeln(chr(t )); div : writeln(‘div’); mod : writeln(‘mod’); num : writeln(tval); id : writeln(symtable[tval].lexptr^); else writeln(chr(t), tval);

end;

end; end; {emit}

strcmp strcmp

strcopy strcopy

Fuction strcmp(cp : integer; s: str) : integer; Var i, l : integer; Begin i := 1; l := length (s);

Procedure strcopy(cp : integer; t : str); Var i : integer; begin

while( i < = l ) and(s[i] = lexemes [cp] do begin

for i := 1 to length (t) do begin

i := i + 1; cp := cp + 1;

lexemes [cp] := t [i] cp := cp + 1;

end;

lexemes [cp] := eos;

if i > l then strcmp:= 1 else strcmp:= 0

end; {Strcopy}

end; {strcmp}

FCE-UIT TS. Vũ Đức Lung 43 FCE-UIT TS. Vũ Đức Lung 44

lookup lookup

insert insert

function insert (s : str; typetoken: integer) : integer; Var len: integer; begin

function lookup (s : string) : integer; Var i, p: integer; begin

len:= length (s ); if(lastentry + 1 > = symax) then

error (“Bảng danh biểu đầy”, lineno);

p := lastentry; while (p > 0) and (Strcmp(symtable[p].lexptr^ , s) = 0) do

if(lastchar+ len+ 1 > = strmax) then

error (“Dãy lexemes đầy”, lineno);

p := p –1; lookup := p;

end; {lookup}

lastentry:= lastentry+ 1; symtable[ lastentry].token:= typyetoken; symtable[latsentry].lexptr:= @lexemes[lastchar + 1]; lastchar:= lastchar + len+ 1; strcopy(symtable[lastentry].lexptr^, s) insert := lastentry;

end;{insert}

FCE-UIT TS. Vũ Đức Lung 45 FCE-UIT TS. Vũ Đức Lung 46

FCE-UIT TS. Vũ Đức Lung 47 FCE-UIT TS. Vũ Đức Lung 48

8 05/04/2012

error error

init init

Procedure init; Var keyword : array[1.3] of

record

Procedure error (m : str; lineno: integer); begin

lexeme : string [10] token : integer;

end;

writeln(m, lineno); stop;

r, i : integer; begin

end;

keyword [1].lexeme := “div”; keyword [1].token := div; keyword [2].lexeme:= “mod”; keyword [2].token := mod; keyword [3].lexeme := “0”; keyword [3].token := 0; r := 3; for i := 1to r do

p := insert (keyword [i].lexeme,keyword [i].token);

end;

mainmain

begin{main}

lastentry:= 0; lineno:= 0; tokenval:= -1; lastchar:= 0; init; parser; end; {main}

TS. Vũ Đức Lung 49 FCE-UIT TS. Vũ Đức Lung 50 FCE-UIT

FCE-UIT TS. Vũ Đức Lung 51