Giáo trình Nguyên lý ngôn ngữ lập trình - Chương II: Một trình biên dịch đơn giản

CHƯƠNG II

MỘT TRÌNH BIÊN DỊCH ÐƠN GIẢN

Nội dung chính:

Chương này giới thiệu một trình biên dịch cho các biểu thức số học đơn giản (trình

biên dịch đơn giản) gồm hai kỳ: Kỳ đầu (Front end) và kỳ sau (Back end). Nội dung

chính của chương tập trung vào kỳ đầu gồm các giai đoạn: Phân tích từ vựng, phân

tích cú pháp và sinh mã trung gian với mục đích chuyển một biểu thức số học đơn giản

từ dạng trung tố sang hậu tố. Kỳ sau chuyển đổi biểu thức ở dạng hậu tố sang mã máy

ảo kiểu stack, sau đó sẽ thực thi đoạn mã đó trên máy ảo kiểu stack để cho ra kết quả

tính toán cuối cùng.

Mục tiêu cần đạt:

Sau khi học xong chương này, sinh viên phải nắm được:

• Các thành phần cấu tạo nên trình biên dịch đơn giản.

• Hoạt động và cách cài đặt các giai đoạn của kỳ trước của một trình biên dịch

đơn giản.

• Cách sử dụng máy trừu tượng kiểu stack để chuyển đổi các biểu thức hậu tố

sang mã máy ảo và cách thực thi các đoạn mã ảo này để có được kết quả cuối

cùng.

Kiến thức cơ bản

Để tiếp nhận các nội dung được trình bày trong chương 2, sinh viên phải:

• Biết một ngôn ngữ lập trình nào đó: C, Pascal, v.v để hiểu cách cài đặt trình

biên dịch.

• Có kiến thức về cấu trúc dữ liệu để hiểu cách tổ chức dữ liệu khi thực hiện cài

đặt.

Tài liệu tham khảo:

[1] Trình Biên Dịch - Phan Thị Tươi (Trường Ðại học kỹ thuật Tp.HCM) - NXB

Giáo dục, 1998.

[2] Compilers : Principles, Technique and Tools - Alfred V.Aho, Jeffrey

D.Ullman - Addison - Wesley Publishing Company, 1986.

I. ÐỊNH NGHĨA CÚ PHÁP

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

Ðể xác định cú pháp của một ngôn ngữ, người ta dùng văn phạm phi ngữ cảnh CFG

(Context Free Grammar) hay còn gọi là văn phạm BNF (Backers Naur Form)

Văn phạm phi ngữ cảnh bao gồm bốn thành phần:

1. Một tập hợp các token - các ký hiệu kết thúc (terminal symbols).

Ví dụ: Các từ khóa, các chuỗi, dấu ngoặc đơn, ...

11

2. Một tập hợp các ký hiệu chưa kết thúc (nonterminal symbols), còn gọi là các

biến (variables).

Ví dụ: Câu lệnh, biểu thức, ...

3. Một tập hợp các luật sinh (productions) trong đó mỗi luật sinh bao gồm một

ký hiệu chưa kết thúc - gọi là vế trái, một mũi tên và một chuỗi các token

và / hoặc các ký hiệu chưa kết thúc gọi là vế phải.

4. Một trong các ký hiệu chưa kết thúc được dùng làm ký hiệu bắt đầu của văn

phạm.

Chúng ta qui ước:

- Mô tả văn phạm bằng cách liệt kê các luật sinh.

- Luật sinh chứa ký hiệu bắt đầu sẽ được liệt kê đầu tiên.

- Nếu có nhiều luật sinh có cùng vế trái thì nhóm lại thành một luật sinh duy

nhất, trong đó các vế phải cách nhau bởi ký hiệu “|”đọc là “hoặc”.

Ví dụ 2.1: Xem biểu thức là một danh sách của các số phân biệt nhau bởi dấu + và dấu

-. Ta có, văn phạm với các luật sinh sau sẽ xác định cú pháp của biểu thức.

list → list + digit

list → list - digit

list → digit

⇔

list → list + digit | list - digit | digit

digit → 0 | 1 | 2 ...| 9

digit → 0 | 1 | 2 | ...| 9

Như vậy văn phạm phi ngữ cảnh ở đây là:

- Tập hợp các ký hiệu kết thúc: 0, 1, 2, ..., 9, +, -

- Tập hợp các ký hiệu chưa kết thúc: list, digit.

- Các luật sinh đã nêu trên.

- Ký hiệu chưa kết thúc bắt đầu: list.

Ví dụ 2.2:

Từ ví dụ 2.1 ta thấy: 9 - 5 + 2 là một list vì:

9 là một list vì nó là một digit.

9 - 5 là một list vì 9 là một list và 5 là một digit.

9 - 5 + 2 là một list vì 9 - 5 là một list và 2 là một digit.

Ví dụ 2.3:

Một list là một chuỗi các lệnh, phân cách bởi dấu ; của khối begin - end trong

Pascal. Một danh sách rỗng các lệnh có thể có giữa begin và end.

Chúng ta xây dựng văn phạm bởi các luật sinh sau:

block

→ begin opt_stmts end

opt_stmts → stmt_list | ε

stmt_list → stmt_list ; stmt | stmt

12

Trong đó opt_stmts (optional statements) là một danh sách các lệnh hoặc không có

lệnh nào (ε).

Luật sinh cho stmt_list giống như luật sinh cho list trong ví dụ 2.1, bằng cách thay

thế +, - bởi ; và stmt thay cho digit.

2. Cây phân tích cú pháp (Parse Tree)

Cây phân tích cú pháp minh họa ký hiệu ban đầu của một văn phạm dẫn đến một

chuỗi 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

Z

X

Y

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.

2. Mỗi một lá có nhãn là một ký hiệu kết thúc hoặc một ε.

3. Mỗi nút trong có nhãn là một ký hiệu chưa kết thúc.

4. Nếu A là một ký hiệu chưa kết thúc được dùng làm nhãn cho một nút trong

nào đó và X1 ... Xn là nhãn của các con của nó theo thứ tự từ trái sang phải thì

A → X1X2 ... Xn là một luật sinh. Ở đây X1, ..., Xn có thể là ký hiệu kết thúc

hoặc chưa kết thúc. Ðặc biệt, nếu A → ε thì nút có nhãn A có thể có một con

có nhãn ε.

3. Sự mơ hồ của văn phạm

Một văn phạm có thể sinh ra nhiều hơn một cây phân tích cú pháp cho cùng một

chuỗi nhập thì gọi là văn phạm mơ hồ.

Ví du 2.4: Giả sử chúng ta không phân biệt một list với một digit, xem chúng đều

là một string ta có văn phạm:

string → string + string | string - string | 0 | 1 | ... | 9.

Với văn phạm này thì chuỗi biểu thức 9 - 5 + 2 có đến hai cây phân tích cú

pháp như sau :

string

-

string

9

string

+

-

2

string

+

string

2

9

5

Hình 2.1 - Minh họa văn phạm mơ hồ

13

Tương tự với cách đặt dấu ngoặc vào biểu thức như sau :

(9 - 5) + 2

9 - ( 5 + 2)

Bởi vì một chuỗi với nhiều cây phân tích cú pháp thường sẽ có nhiều nghĩa, do

đó khi biên dịch các chương trình ứng dụng, chúng ta cần thiết kế các văn phạm không

có sự mơ hồ hoặc cần bổ sung thêm các qui tắc cần thiết để giải quyết sự mơ hồ cho

văn phạm.

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

Thông thường, theo quy ước ta có biểu thức 9 + 5 + 2 tương đương (9 + 5) + 2 và 9

- 5 - 2 tương đương với (9 - 5) - 2. Khi một toán hạng như 5 có hai toán tử ở trái và

phải thì nó phải chọn một trong hai để xử lý trước. Nếu toán tử bên trái được thực hiện

trước ta gọi là kết hợp trái. Ngược lại là kết hợp phải.

Thường thì bốn phép toán số học: +, -, *, / có tính kết hợp trái. Các phép toán như

số mũ, phép gán bằng (=) có tính kết hợp phải.

Ví dụ 2.5: Trong ngôn ngữ C, biểu thức a = b = c tương đương a = ( b = c) vì

chuỗi a = b = c với toán tử kết hợp phải được sinh ra bởi văn phạm:

right → letter = right | letter

letter → a | b | ... | z

Ta có cây phân tích cú pháp có dạng như sau (chú ý hướng của cây nghiêng về bên

phải trong khi cây cho các phép toán có kết hợp trái thường nghiêng về trái)

right

letter

a

=

right

=

letter

c

letter

b

Hình 2.2 - Minh họa cây phân tích cú pháp cho toán tử kết hợp phải

5. Thứ tự ưu tiên của các toán tử

Xét biểu thức 9 + 5 * 2. Có 2 cách để diễn giải biểu thức này, đó là 9 + (5 * 2)

hoặc ( 9 + 5) * 2. Tính kết hợp của phép + và * không giải quyết được sự mơ hồ này,

vì vậy cần phải quy định một thứ tự ưu tiên giữa các loại toán tử khác nhau.

Thông thường trong toán học, các toán tử * và / có độ ưu tiên cao hơn + và -.

Cú pháp cho biểu thức :

Văn phạm cho các biểu thức số học có thể xây dựng từ bảng kết hợp và ưu tiên của

các toán tử. Chúng ta có thể bắt đầu với bốn phép tính số học theo thứ bậc sau :

Kết hợp trái +, -

Kết hợp trái *, /

Thứ tự ưu tiên

từ thấp đến cao

14

Chúng ta tạo hai ký hiệu chưa kết thúc expr và term cho hai mức ưu tiên và một ký

hiệu chưa kết thúc factor làm đơn vị phát sinh cơ sở của biểu thức. Ta có đơn vị cơ bản

trong biểu thức là số hoặc biểu thức trong dấu ngoặc.

factor → digit | (expr)

Phép nhân và chia có thứ tự ưu tiên cao hơn đồng thời chúng kết hợp trái nên luật

sinh cho term tương tự như cho list :

term → term * factor | term / factor | factor

Tương tự, ta có luật sinh cho expr :

expr → expr + term | expr - term | term

Vậy, cuối cùng ta thu được văn phạm cho biểu thức như sau :

expr → expr + term | expr - term | term

term → term * factor | term / factor | factor

factor → digit | (expr)

Như vậy: Văn phạm này xem biểu thức như là một danh sách các term được phân

cách nhau bởi dấu + hoặc -. Term là một list các factor phân cách nhau bởi * hoặc /.

Chú ý rằng bất kỳ một biểu thức nào trong ngoặc đều là factor, vì thế với các dấu

ngoặc chúng ta có thể xây dựng các biểu thức lồng sâu nhiều cấp tuỳ ý.

Cú pháp các câu lệnh:

Từ khóa (keyword) cho phép chúng ta nhận ra câu lệnh trong hầu hết các ngôn

ngữ. Ví dụ trong Pascal, hầu hết các lệnh đều bắt đầu bởi một từ khóa ngoại trừ lệnh

gán. Một số lệnh Pascal được định nghĩa bởi văn phạm (mơ hồ) sau, trong đó id chỉ

một danh biểu (tên biến).

stmt → id := expr

| if expr then stmt

| if expr then stmt else stmt

| while expr do stmt

| begin opt_stmts end

Ký hiệu chưa kết thúc opt_stmts sinh ra một danh sách có thể rỗng các lệnh,

phân cách nhau bởi dấu chấm phẩy (;)

II. DỊCH TRỰC TIẾP CÚ PHÁP (Syntax - Directed Translation)

Ðể dịch một kết cấu ngôn ngữ lập trình, trong quá trình dịch, bộ biên dịch cần lưu

lại nhiều đại lượng khác cho việc sinh mã ngoài mã lệnh cần tạo ra cho kết cấu. Chẳng

hạn nó cần biết kiểu (type) của kết cấu, địa chỉ của lệnh đầu tiên trong mã đích, số lệnh

phát sinh,v.v Vì vậy ta nói một cách ảo về thuộc tính (attribute) đi kèm theo kết cấu.

Một thuộc tính có thể biểu diễn cho một đại lượng bất kỳ như một kiểu, một chuỗi,

một địa chỉ vùng nhớ, v.v

Chúng ta sử dụng định nghĩa trực tiếp cú pháp (syntax - directed definition)

nhằm đặc tả việc phiên dịch các kết cấu ngôn ngữ lập trình theo các thuộc tính đi kèm

15

với thành phần cú pháp của nó. Chúng ta cũng sẽ sử dụng một thuật ngữ có tính thủ

tục hơn là lược đồ dịch (translation scheme) để đặc tả quá trình dịch. Trong chương

này, ta sử dụng lược đồ dịch để dịch một biểu thức trung tố thành dạng hậu tố.

1. Ký pháp hậu tố (Postfix Notation)

Ký pháp hậu tố của biểu thức E có thể được định nghĩa quy nạp như sau:

1. Nếu E là một biến hay hằng thì ký pháp hậu tố của E chính là E.

2. Nếu E là một biểu thức có dạng E1 op E2 trong đó op là một toán tử hai ngôi

thì ký pháp hậu tố của E là E1’ E2’ op. Trong đó E1’, E2’ tương ứng là ký pháp hậu tố

của E1, E2.

3. Nếu E là một biểu thức dạng (E1) thì ký pháp hậu tố của E là ký pháp hậu tố

của E1.

Trong dạng ký pháp hậu tố, dấu ngoặc là không cần thiết vì vị trí và số lượng các

đối số chỉ cho phép xác định một sự giải mã duy nhất cho một biểu thức hậu tố.

Ví dụ 2.6:

Dạng hậu tố của biểu thức (9 - 5) + 2 là 9 5 - 2 +

Dạng hậu tố của biểu thức 9 - (5 + 2) là 9 5 2 + -

2. Ðịnh nghĩa trực tiếp cú pháp (Syntax - Directed Definition)

Ðịnh nghĩa trực tiếp cú pháp sử dụng văn phạm phi ngữ cảnh để đặc tả cấu trúc cú

pháp của dòng input nhập. Nó liên kết mỗi ký hiệu văn phạm với một tập các thuộc

tính và mỗi luật sinh kết hợp với một tập các quy tắc ngữ nghĩa (semantic rule) để tính

giá trị của thuộc tính đi kèm với những ký hiệu có trong luật sinh văn phạm. Văn phạm

và tập các quy tắc ngữ nghĩa tạo nên định nghĩa trực tiếp cú pháp.

Phiên dịch (translation) là một ánh xạ giữa input - output (input - output mapping).

Output cho mỗi input x được xác định theo cách sau. Trước hết xây dựng cây phân

tích cú pháp cho x. Giả sử nút n trong cây phân tích cú pháp có nhãn là ký hiệu văn

phạm X. Ta viết X.a để chỉ giá trị của thuộc tính a của X tại nút đó. Giá trị của X.a tại

n được tính bằng cách sử dụng quy tắc ngữ nghĩa cho thuộc tính a kết hợp với luật

sinh cho X tại nút n. Cây phân tích cú pháp có thể hiện rõ giá trị của thuộc tính tại mỗi

nút gọi là cây phân tích cú pháp chú thích (annotated parse tree).

3. Thuộc tính tổng hợp (Synthesized Attributes)

Một thuộc tính được gọi là tổng hợp nếu giá trị của nó tại một nút trên cây cú pháp

được xác định từ các giá trị của các thuộc tính tại các nút con của nút đó.

Ví dụ 2.7: Ðịnh nghĩa trực tiếp cú pháp cho việc dịch các biểu thức các số cách

nhau bởi dấu + hoặc - thành ký pháp hậu tố như sau:

Luật sinh

E → E1 + T

E → E1 - T

E → T

Quy tắc ngữ nghĩa

E.t := E1.t || T.t || ‘+’

E.t := E1.t || T.t || ‘-’

E.t := T.t

T → 0

T.t := ‘0’

...

16

T → 9

T.t := ‘9’

Hình 2.3 - Ví dụ về định nghĩa trực tiếp cú pháp

Chẳng hạn, một quy tắc ngữ nghĩa E.t := E1.t || T.t || ‘+’ kết hợp với luật sinh xác

định giá trị của thuộc tính E.t bằng cách ghép các ký pháp hậu tố của E1.t và T.t và

dấu ‘+’. Dấu || có nghĩa như sự ghép các chuỗi.

Ta có cây phân tích cú pháp chú thích cho biểu thức 9 - 5 + 2 như sau :

E.t = 9 5 - 2 +

E.t = 9 5 -

T.t = 2

E.t = 9

T.t = 9

9

T.t = 5

-

5

2

+

Hình 2.4 - Minh họa cây phân tích cú pháp chú thích

Giá trị của thuộc tính t tại mỗi nút được tính bằng cách dùng quy tắc ngữ nghĩa kết

hợp với luật sinh tại nút đó. Giá trị thuộc tính tại nút gốc là ký pháp hậu tố của chuỗi

được sinh ra bởi cây phân tích cú pháp.

4. Duyệt theo chiều sâu (Depth - First Traversal)

Quá trình dịch được cài đặt bằng cách đánh giá các luật ngữ nghĩa cho các thuộc

tính trong cây phân tích cú pháp theo một thứ tự xác định trước. Ta dùng phép duyệt

cây theo chiều sâu để đánh giá quy tắc ngữ nghĩa. Bắt đầu từ nút gốc, thăm lần lượt

(đệ qui) các con của mỗi nút theo thứ tự từ trái sang phải.

Procedure visit (n : node);

begin

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

visit (m);

Ðánh giá quy tắc ngữ nghĩa tại nút n;

end

5. Lược đồ dịch (Translation Scheme)

Một lược đồ dịch là một văn phạm phi ngữ cảnh, trong đó các đoạn chương trình

gọi là hành vi ngữ nghĩa (semantic actions) được gán vào vế phải của luật sinh. Lược

đồ dịch cũng như định nghĩa trực tiếp cú pháp nhưng thứ tự đánh giá các quy tắc ngữ

nghĩa được trình bày một cách rõ ràng. Vị trí mà tại đó một hành vi được thực hiện

được trình bày trong cặp dấu ngoặc nhọn { } và viết vào vế phải luật sinh.

Ví dụ 2.8: rest → + term {print (‘+’)} rest1.

17

rest

{print(‘+’) }

rest1

term

+

Hình 2.5 - Một nút lá được xây dựng cho hành vi ngữ nghĩa

Lược đồ dịch tạo ra một output cho mỗi câu nhập x sinh ra từ văn phạm đã cho

bằng cách thực hiện các hành vi theo thứ tự mà chúng xuất hiện trong quá trình duyệt

theo chiều sâu cây phân tích cú pháp của x. Chẳng hạn, xét cây phân tích cú pháp với

một nút có nhãn rest biểu diễn luật sinh nói trên. Hành vi ngữ nghĩa { print(‘+’) } được

thực hiện sau khi cây con term được duyệt nhưng trước khi cây con rest1 được thăm.

6. Phát sinh bản dịch (Emitting a Translation)

Trong chương này, hành vi ngữ nghĩa trong lược đồ dịch sẽ ghi kết quả của quá

trình phiên dịch vào một tập tin, mỗi lần một chuỗi hoặc một ký tự. Chẳng hạn, khi

dịch 9 - 5 + 2 thành 9 5 - 2 + bằng cách ghi mỗi ký tự trong 9 - 5 + 2 đúng một lần mà

không phải ghi lại quá trình dịch của các biểu thức con. Khi tạo ra output dần dần theo

cách này, thứ tự in ra các ký tự sẽ rất quan trọng.

Chú ý rằng các định nghĩa trực tiếp cú pháp đều có đặc điểm sau: chuỗi biểu diễn

cho bản dịch của ký hiệu chưa kết thúc ở vế trái của mỗi luật sinh là sự ghép nối của

các bản dịch ở vế phải theo đúng thứ tự của chúng trong luật sinh và có thể thêm một

số chuỗi khác xen vào giữa. Một định nghĩa trực tiếp cú pháp theo dạng này được xem

là đơn giản.

Ví dụ 2.9: Với định nghĩa trực tiếp cú pháp như hình 2.3, ta xây dựng lược đồ dịch

như sau :

E → E1 + T

E → E1 - T

E → T

{ print (‘+’) }

{ print (‘-’) }

T → 0

{ print (‘0’) }

{ print (‘9’) }

....

T → 9

Hình 2.6 - Lược đồ dịch biểu thức trung tố thành hậu tố

Ta có các hành động dịch biểu thức 9 - 5 + 2 thành 9 5 - 2 + như sau :

E

+

T

{ print(‘+’)

E

T

{ print(‘-’) }

{ print(‘2’) }

2

-

T

{ print(‘5’) }

5

9

{ print(‘9’) }

Hình 2.7 - Các hành động dịch biểu thức 9-5+2 thành 9 5- 2 +

18

Xem như một quy tắc tổng quát, phần lớn các phương pháp phân tích cú pháp đều

xử lý input của chúng từ trái sang phải, trong lược đồ dịch đơn giản (lược đồ dịch dẫn

xuất từ một định nghĩa trực tiếp cú pháp đơn giản), các hành vi ngữ nghĩa cũng được

thực hiện từ trái sang phải. Vì thế, để cài đặt một lược đồ dịch đơn giản, chúng ta có

thể thực hiện các hành vi ngữ nghĩa trong lúc phân tích cú pháp mà không nhất thiết

phải xây dựng cây phân tích cú pháp.

III. PHÂN TÍCH CÚ PHÁP (PARSING)

Phân tích cú pháp là quá trình xác định xem liệu một chuỗi ký hiệu kết thúc

(token) có thể được sinh ra từ một văn phạm hay không ? Khi nói về vấn đề này,

chúng ta xem như đang xây dựng một cây phân tích cú pháp, mặc dù một trình biên

dịch có thể không xây dựng một cây như thế. Tuy nhiên, quá trình phân tích cú pháp

(parse) phải có khả năng xây dựng nó, nếu không thì việc phiên dịch sẽ không bảo

đảm được tính đúng đắn.

Phần lớn các phương pháp phân tích cú pháp đều rơi vào một trong 2 lớp: phương

pháp phân tích từ trên xuống và phương pháp phân tích từ dưới lên. Những thuật ngữ

này muốn đề cập đến thứ tự xây dựng các nút trong cây phân tích cú pháp. Trong

phương pháp đầu, quá trình xây dựng bắt đầu từ gốc tiến hành hướng xuống các nút lá,

còn trong phương pháp sau thì thực hiện từ các nút lá hướng về gốc. Phương pháp

phân tích từ trên xuống thông dụng hơn nhờ vào tính hiệu quả của nó khi xây dựng

theo lối thủ công. Ngược lại, phương pháp phân tích từ dưới lên lại có thể xử lý được

một lớp văn phạm và lược đồ dịch phong phú hơn. Vì vậy, đa số các công cụ phần

mềm giúp xây dựng thể phân tích cú pháp một cách trực tiếp từ văn phạm đều có xu

hướng sử dụng phương pháp từ dưới lên.

1. Phân tích cú pháp từ trên xuống (Top - Down Parsing)

Xét văn phạm sinh ra một tập con các kiểu dữ liệu của Pascal

type → simple | ↑ id | array [simple] of type

simple → integer | char | num .. num

Phân tích trên xuống bắt đầu bởi nút gốc, nhãn là ký hiệu chưa kết thúc bắt đầu và

lặp lại việc thực hiện hai bước sau đây:

1. Tại nút n, nhãn là ký hiệu chưa kết thúc A, chọn một trong những luật sinh

của A và xây dựng các con của n cho các ký hiệu trong vế phải của luật sinh.

2. Tìm nút kế tiếp mà tại đó một cây con sẽ được xây dựng. Ðối với một số văn

phạm, các bước trên được cài đặt bằng một phép quét (scan) dòng nhập từ trái qua

phải.

Ví dụ 2.10: Với các luật sinh của văn phạm trên, ta xây dựng cây cú pháp cho

dòng nhập: array [num .. num] of integer

Mở đầu ta xây dựng nút gốc với nhãn type. Ðể xây dựng các nút con của type

ta chọn luật sinh type → array [simple] of type. Các ký hiệu nằm bên phải của luật

sinh này là array, [, simple, ], of, type do đó nút gốc type có 6 con có nhãn tương ứng

(áp dụng bước 1)

Trong các nút con của type, từ trái qua thì nút con có nhãn simple (một ký hiệu

chưa kết thúc) do đó có thể xây dựng một cây con tại nút simple (bước 2)

19

Trong các luật sinh có vế trái là simple, ta chọn luật sinh simple → num .. num

để xây dựng. Nói chung, việc chọn một luật sinh có thể được xem như một quá trình

thử và sai (trial - and - error). Nghĩa là một luật sinh được chọn để thử và sau đó quay

lại để thử một luật sinh khác nếu luật sinh ban đầu không phù hợp. Một luật sinh là

không phù hợp nếu sau khi sử dụng luật sinh này chúng ta không thể xây dựng một

cây hợp với dòng nhập. Ðể tránh việc lần ngược, người ta đưa ra một phương pháp gọi

là phương pháp phân tích cú pháp dự đoán.

type

(a)

(b)

(c)

array

[ simple

type

]

of

(d)

(e)

simple

integer

num

..

Hình 2.8 - Minh họa quá trình phân tích cú pháp từ trên xuống

2. Phân tích cú pháp dự đoán (Predictive Parsing)

Phương pháp phân tích cú pháp đệ qui xuống (recursive-descent parsing) là một

phương pháp phân tích trên xuống, trong đó chúng ta thực hiện một loạt thủ tục đệ qui

để xử lý chuỗi nhập. Mỗi một thủ tục kết hợp với một ký hiệu chưa kết thúc của văn

phạm. Ở đây chúng ta xét một trường hợp đặc biệt của phương pháp đệ qui xuống là

phương pháp phân tích dự đoán trong đó ký hiệu dò tìm sẽ xác định thủ tục được chọn

đối với ký hiệu chưa kết thúc. Chuỗi các thủ tục được gọi trong quá trình xử lý chuỗi

nhập sẽ tạo ra cây phân tích cú pháp.

Ví dụ 2.11: Xét văn phạm như trên, ta viết các thủ tục type và simple tương ứng

với các ký hiệu chưa kết thúc type và simple trong văn phạm. Ta còn đưa thêm thủ tục

match để đơn giản hóa đoạn mã cho hai thủ tục trên, nó sẽ dịch tới ký hiệu kế tiếp nếu

tham số t của nó so khớp với ký hiệu dò tìm tại đầu đọc (lookahead).

procedure match (t: token);

begin

if lookahead = t then

lookahead := nexttoken

else error

end;

procedure type;

begin

if lookahead in [integer, char, num] then

simple

else if lookahead = ‘↑‘ then begin

20

match (‘↑‘); match(id);

end

else if lookahead = array then begin

match(array); match(‘[‘);

simple;

match(‘]’); match(of);

type

end

else error;

end;

procedure simple;

begin

if lookahead = integer then match(integer)

else if lookahead = char then match(char)

else if lookahead = num then

begin

match(num); match(dotdot); match(num);

end

else error

end;

Hình 2.9 - Ðoạn mã giả minh họa phương pháp phân tích dự đoán

Phân tích cú pháp bắt đầu bằng lời gọi tới thủ tục cho ký hiệu bắt đầu type. Với

dòng nhập array [num .. num] of integer thì đầu đọc lookahead bắt đầu sẽ đọc token

array. Thủ tục type sau đó sẽ thực hiện chuỗi lệnh: match(array); match(‘[‘); simple;

match(‘]’); match(of); type. Sau khi đã đọc được array và [ thì ký hiệu hiện tại là

num. Tại điểm này thì thủ tục simple và các lệnh match(num); match(dotdot);

match(num) được thực hiện.

Xét luật sinh type → simple. Luật sinh này có thể được dùng khi ký hiệu dò tìm

sinh ra bởi simple, chẳng hạn ký hiệu dò tìm là integer mặc dù trong văn phạm không

có luật sinh type → integer, nhưng có luật sinh simple → integer, do đó luật sinh

type → simple được dùng bằng cách trong type gọi simple.

Phân tích dự đoán dựa vào thông tin về các ký hiệu đầu sinh ra bởi vế phải của

một luật sinh. Nói chính xác hơn, giả sử ta có luật sinh A → γ , ta định nghĩa tập hợp :

FIRST(γ) = { token | xuất hiện như các ký hiệu đầu của một hoặc nhiều chuỗi

sinh ra bởi γ }. Nếu γ là ε hoặc có thể sinh ra ε thì ε ∈ FIRST(γ).

Ví dụ 2.12: Xét văn phạm như trên, ta dễ dàng xác định:

FIRST( simple) = { integer, char, num }

21

FIRST(↑id) = { ↑ }

FIRST( array [simple] of type ) = { array }

Nếu ta có A → α và A → β, phân tích đệ qui xuống sẽ không phải quay lui nếu

FIRST(α) ∩ FIRST(β) = ∅. Nếu ký hiệu dò tìm thuộc FIRST(α) thì A → α được

dùng. Ngược lại, nếu ký hiệu dò tìm thuộc FIRST(β) thì A → β được dùng.

Trường hợp α = ε (Luật sinh ε)

Ví dụ 2.13: Xét văn phạm chứa các luật sinh sau :

stmt → begin opt_stmts end

opt_stmts → stmt_list | ε

Khi phân tích cú pháp cho opt_stmts, nếu ký hiệu dò tìm ∉ FIRST(stmt_list) thì

sử dụng luật sinh: opt_stmts → ε. Chọn lựa này hòan tòan chính xác nếu ký hiệu dò

tìm là end, mọi ký hiệu dò tìm khác end sẽ gây ra lỗi và được phát hiện trong khi phân

tích stmt.

3. Thiết kế bộ phân tích cú pháp dự đoán

Bộ phân tích dự đoán là một chương trình bao gồm các thủ tục tương ứng với các

ký hiệu chưa kết thúc. Mỗi thủ tục sẽ thực hiện hai công việc sau:

1. Luật sinh mà vế phải α của nó sẽ được dùng nếu ký hiệu dò tìm thuộc

FIRST(α). Nếu có một sự đụng độ giữa hai vế phải đối với bất kỳ một ký hiệu dò tìm

nào thì không thể dùng phương pháp này. Một luật sinh với ε nằm bên vế phải được

dùng nếu ký hiệu dò tìm không thuộc tập hợp FIRST của bất kỳ vế phải nào khác.

2. Một ký hiệu chưa kết thúc tương ứng lời gọi thủ tục, một token phải phù hợp

với ký hiệu dò tìm. Nếu token không phù hợp với ký hiệu dò tìm thì có lỗi.

4. Loại bỏ đệ qui trái

Một bộ phân tích cú pháp đệ quy xuống có thể sẽ dẫn đến một vòng lặp vô tận nếu

gặp một luật sinh đệ qui trái dạng E → E + T bởi vì ký hiệu trái nhất bên vế phải cũng

giống như ký hiệu chưa kết thúc bên vế trái của luật sinh.

Ðể giải quyết được vấn đề này chúng ta phải loại bỏ đệ qui trái bằng cách thêm

vào một ký hiệu chưa kết thúc mới. Chẳng hạn với luật sinh dạng A → Aα | β.Ta thêm

vào một ký hiệu chưa kết thúc R để viết lại thành tập luật sinh như sau :

A → β R

R → α R | ε

Ví dụ 2.14: Xét luật sinh đệ quy trái : E → E + T | T

Sử dụng quy tắc khử đệ quy trái nói trên với : A ≅ E, α ≅ + T, β≅ T .

Luật sinh trên có thể biến đổi tương đương thành tập luật sinh :

E → T R

R → + T R | ε

22

IV. MỘT CHƯƠNG TRÌNH DỊCH BIỂU THỨC ÐƠN GIẢN

Sử dụng các kỹ thuật nêu trên, chúng ta xây dựng một bộ dịch trực tiếp cú pháp mà

nó dịch một biểu thức số học đơn giản từ trung tố sang hậu tố. Ta bắt đầu với các biểu

thức là các chữ số viết cách nhau bởi + hoặc -.

Xét lược đồ dịch cho dạng biểu thức này :

expr → expr + term { print (‘+’) }

expr → expr - term { print (‘-’) }

expr → term

term → 0

...

{ print (‘0’) }

term → 9

{ print (‘9’) }

Hình 2.10 - Ðặc tả lược đồ dịch khởi đầu

Văn phạm nền tảng cho lược đồ dịch trên có chứa luật sinh đệ qui trái, bộ phân tích

cú pháp dự đoán không xử lý được văn phạm dạng này, cho nên ta cần loại bỏ đệ quy

trái bằng cách đưa vào một ký hiệu chưa kết thúc mới rest để được văn phạm thích hợp

như sau:

expr → term rest

rest → + term { print(‘+’) } rest | - term {print(‘-’) rest | ε

term → 0 { print(‘0’) }

term → 1 { print(‘1’) }

...

term → 9 { print(‘9’) }

Hình sau đây mô tả quá trình dịch biểu thức 9 - 5 + 2 dựa vào lược đồ dịch trên:

expr

term

{ print(‘9’) }

rest

-

9

{ print(‘-’) }

rest

term

+

{ print(+’) }

rest

term

{ print(‘5’) }

5

2

ε

{ print(‘2’) }

Hình 2.11 - Dịch 9 - 5+2 thành 9 5- 2+

Bây giờ ta cài đặt chương trình dịch bằng C theo đặc tả như trên. Phần chính của

chương trình này là các đoạn mã C cho các hàm expr, term và rest.

// Hàm expr( ) tương ứng với ký hiệu chưa kết thúc expr

expr( )

23

{

term( ) ; rest( );

}

// Hàm expr( ) tương ứng với ký hiệu chưa kết thúc expr

rest( )

{

if (lookahead = = ‘+’ ) {

match(‘+’) ; term( ) ; putchar (‘+ ‘) ; rest( );

}

else if (lookahead = = ‘-’) {

match(‘-’) ; term( ) ; putchar (‘-’) ; rest( );

}

else ;

}

// Hàm expr( ) tương ứng với ký hiệu chưa kết thúc expr

term( )

{

if (isdigit (lookahead) {

putchar (lookahead); match (lookahead);

}

else error( );

}

Tối ưu hóa chương trình dịch

Một số lời gọi đệ quy có thể được thay thế bằng các vòng lặp để làm cho chương

trình thực hiện nhanh hơn. Ðoạn mã cho rest có thể được viết lại như sau :

rest( )

{

L : if (lookahead = = ‘+’ ) {

match(‘+’) ; term( ) ; putchar (‘+ ‘) ; goto L;

}

else if (lookahead = = ‘-’) {

match(‘-’) ; term( ) ; putchar (‘-’) ; goto L;

24

}

else ;

}

Nhờ sự thay thế này, hai hàm rest và expr có thể được tích hợp lại thành một.

Mặt khác, trong C, một câu lệnh stmt có thể được thực hiện lặp đi lặp lại bằng

cách viết : while (1) stmt với 1 là điều kiện hằng đúng. Chúng ta cũng có thể thóat

khỏi vòng lặp dễ dàng bằng lệnh break.

Ðoạn chương trình có thể được viết lại như sau :

expr ( )

{

term ( )

while (1)

if (lookahead = = ‘+’ ) {

match(‘+’) ; term( ) ; putchar (‘+ ‘) ;

}

else if (lookahead = = ‘-’) {

match(‘-’) ; term( ) ; putchar (‘-’) ;

}

else break;

}

Chương trình C dịch biểu thức trung tố sang hậu tố

Chương trình nguồn C hoàn chỉnh cho chương trình dịch có mã như sau :

# include< ctype.h>

int lookahead;

/* nạp tập tin chứa isdigit vào*/

main ( )

{

lookahead = getchar( );

expr( ) ; putchar(‘ \n‘);

/* thêm vào ký tự xuống hàng */

}

expr( )

{

term( );

while(1)

25

if (lookahead = = ‘+’)

{ match(‘+’); term( ); putchar(‘+ ‘); }

else if (lookahead = = ‘-’ )

{ match(‘-’); term( ); putchar(‘-’); }

else break;

}

term( )

{

}

if (isdigit(lookahead))

{ putchar(lookahead); match(lookahead); }

else error( );

match ( int t)

{

if (lookahead = = t)

lookahead = getchar();

else error( );

}

error( )

{

printf (“syntax error \n”);

exit(1);

/* in ra thông báo lỗi */

/* rồi kết thúc */

}

V. PHÂN TÍCH TỪ VỰNG (Lexical Analysis)

Bây giờ chúng ta thêm vào phần trước trình biên dịch một bộ phân tích từ vựng để

đọc và biến đổi dòng nhập thành một chuỗi các từ tố (token) mà bộ phân tích cú pháp

có thể sử dụng được. Nhắc lại rằng một chuỗi các ký tự hợp thành một token gọi là trị

từ vựng (lexeme) của token đó.

Trước hết ta trình bày một số chức năng cần thiết của bộ phân tích từ vựng.

1. Loại bỏ các khoảng trắng và các dòng chú thích

Quá trình dịch sẽ xem xét tất cả các ký tự trong dòng nhập nên những ký tự không

có nghĩa (như khoảng trắng bao gồm ký tự trống (blanks), ký tự tabs, ký tự newlines)

26

hoặc các dòng chú thích (comment) phải bị bỏ qua. Khi bộ phân tích từ vựng đã bỏ

qua các khoảng trắng này thì bộ phân tích cú pháp không bao giờ xem xét đến chúng

nữa. Chọn lựa cách sửa đổi văn phạm để đưa cả khoảng trắng vào trong cú pháp thì

hầu như rất khó cài đặt.

2. Xử lý các hằng

Bất cứ khi nào một ký tự số xuất hiện trong biểu thức thì nó được xem như là một

hằng số. Bởi vì một hằng số nguyên là một dãy các chữ số nên nó có thể được cho bởi

luật sinh văn phạm hoặc tạo ra một token cho hằng số đó. Bộ phân tích từ vựng có

nhiệm vụ ghép các chữ số để được một số và sử dụng nó như một đơn vị trong suốt

quá trình dịch.

Ðặt num là một token biểu diễn cho một số nguyên. Khi một chuỗi các chữ số xuất

hiện trong dòng nhập thì bộ phân tích từ vựng sẽ gửi num cho bộ phân tích cú pháp.

Giá trị của số nguyên được chuyển cho bộ phân tích cú pháp như là một thuộc tính của

token num. Về mặt logic, bộ phân tích từ vựng sẽ chuyển cả token và các thuộc tính

cho bộ phân tích cú pháp. Nếu ta viết một token và thuộc tính thành một bộ nằm giữa

< > thì dòng nhập 31 + 28 + 59 sẽ được chuyển thành một dãy các bộ :

<num, 31>, < +, >, <num, 28>, < +, >, <num, 59>.

Bộ <+, > cho thấy thuộc tính của + không có vai trò gì trong khi phân tích cú pháp

nhưng nó cần thiết dùng đến trong quá trình dịch.

3. Nhận dạng các danh biểu và từ khóa

Ngôn ngữ dùng các danh biểu (identifier) như là tên biến, mảng, hàm và văn phạm

xử lý các danh biểu này như là một token. Người ta dùng token id cho các danh biểu

khác nhau do đó nếu ta có dòng nhập count = count + increment; thì bộ phân tích từ

vựng sẽ chuyển cho bộ phân tích cú pháp chuỗi token: id = id + id (cần phân biệt

token và trị từ vựng lexeme của nó: token id nhưng trị từ vựng (lexeme) có thể là

count hoặc increment). Khi một lexeme thể hiện cho một danh biểu được tìm thấy

trong dòng nhập cần phải có một cơ chế để xác định xem lexeme này đã được thấy

trước đó chưa? Công việc này được thực hiện nhờ sự lưu trữ trợ giúp của bảng ký hiệu

(symbol table) đã nêu ở chương trước. Trị từ vựng được lưu trong bảng ký hiệu và một

con trỏ chỉ đến mục ghi trong bảng trở thành một thuộc tính của token id.

Nhiều ngôn ngữ cũng sử dụng các chuỗi ký tự cố định như begin, end, if, ... để xác

định một số kết cấu. Các chuỗi ký tự này được gọi là từ khóa (keyword). Các từ khóa

cũng thỏa mãn qui luật hình thành danh biểu, do vậy cần qui ước rằng một chuỗi ký tự

được xác định là một danh biểu khi nó không phải là từ khóa.

Một vấn đề nữa cần quan tâm là vấn đề tách ra một token trong trường hợp một ký

tự có thể xuất hiện trong trị từ vựng của nhiều token. Ví dụ một số các token là các

toán tử quan hệ trong Pascal như : <, < =, < >.

4. Giao diện của bộ phân tích từ vựng

Bộ phân tích từ vựng được đặt xen giữa dòng nhập và bộ phân tích cú pháp nên

giao diện với hai bộ này như sau:

27

Đọc ký tự

Chuyển

token và

thuộc tính

Bộ phân tích cú

Bộ phân tích

từ vựng

Input

pháp

Đẩy ký tự trở về

Hình 2.12 - Giao diện của bộ phân tích từ vựng

Bộ phân tích từ vựng đọc từng ký tự từ dòng nhập, nhóm chúng lại thành các trị từ

vựng và chuyển các token xác định bởi trị từ vựng này cùng với các thuộc tính của nó

đến những giai đoạn sau của trình biên dịch. Trong một vài tình huống, bộ phân tích từ

vựng phải đọc vượt trước một số ký tự mới xác định được một token để chuyển cho bộ

phân tích cú pháp. Ví dụ, trong Pascal khi gặp ký tự >, phải đọc thêm một ký tự sau đó

nữa; nếu ký tự sau là = thì token được xác định là “lớn hơn hoặc bằng”, ngược lại thì

token là “lớn hơn” và do đó một ký tự đã bị đọc quá. Trong trường hợp đó thì ký tự

đọc quá này phải được đẩy trả về (push back) cho dòng nhập vì nó có thể là ký tự bắt

đầu cho một trị từ vựng mới.

Bộ phân tích từ vựng và bộ phân tích cú pháp tạo thành một cặp "nhà sản xuất -

người tiêu dùng" (producer - consumer). Bộ phân tích từ vựng sản sinh ra các token và

bộ phân tích cú pháp tiêu thụ chúng. Các token được sản xuất bởi bộ phân tích từ vựng

sẽ được lưu trong một bộ đệm (buffer) cho đến khi chúng được tiêu thụ bởi bộ phân

tích cú pháp. Bộ phân tích từ vựng không thể hoạt động tiếp nếu buffer bị đầy và bộ

phân tích cú pháp không thể hoạt động nữa nếu buffer rỗng. Thông thường, buffer chỉ

lưu giữ một token. Ðể cài đặt tương tác dễ dàng, người ta tạo ra một thủ tục phân tích

từ vựng được gọi từ trong thủ tục phân tích cú pháp, mỗi lần gọi trả về một token.

Việc đọc và quay lui ký tự cũng được cài đặt bằng cách dùng một bộ đệm nhập.

Một khối các ký tự được đọc vào trong buffer nhập tại một thời điểm nào đó, một con

trỏ sẽ giữ vị trí đã được phân tích. Quay lui ký tự được thực hiện bằng cách lùi con trỏ

trở về. Các ký tự trong dòng nhập cũng có thể cần được lưu lại cho công việc ghi nhận

lỗi bởi vì cần phải chỉ ra vị trí lỗi trong đoạn chương trình.

Ðể tránh việc phải quay lui, một số trình biên dịch sử dụng cơ chế đọc trước một

ký tự rồi mới gọi đến bộ phân tích từ vựng. Bộ phân tích từ vựng sẽ đọc tiếp các ký tự

cho đến khi đọc tới ký tự mở đầu cho một token khác. Trị từ vựng của token trước đó

sẽ bao gồm các ký tự từ ký tự đọc trước đến ký tự vừa ngay ký tự vừa đọc được. Ký tự

vừa đọc được sẽ là ký tự mở đầu cho trị từ vựng của token sau. Với cơ chế này thì mỗi

ký tự chỉ được đọc duy nhất một lần.

5. Một bộ phân tích từ vựng

Bây giờ chúng ta xây dựng một bộ phân tích từ vựng cho chương trình dịch các

biểu thức số học. Hình sau đây gợi ý một cách cài đặt giao diện của bộ phân tích từ

vựng được viết bằng C dưới dạng hàm lexan. Lexan đọc và đẩy các ký tự trong input

trở về bằng cách gọi thủ tục getchar va ungetc.

28

Dùng getchar() đọc

Trả token cho

bên gọi

input

Bộ phân tích

từ vựng

lexan ( )

Đẩy ký tự trở về bằng

ungetc (c, stdin)

Đặt giá trị thuộc tính

vào biến toàn cục

tokenval

Hình 2.13 - Cài đặt giao diện của bộ phân tích từ vựng

Nếu ngôn ngữ cài đặt không cho phép trả về các cấu trúc dữ liệu từ các hàm thì

token và các thuộc tính của nó phải được truyền riêng rẽ. Hàm lexan trả về một số

nguyên mã hóa cho một token. Token cho một ký tự có thể là một số nguyên quy ước

được dùng để mã hóa cho ký tự đó. Một token như num có thể được mã hóa bằng một

số nguyên lớn hơn mọi số nguyên được dùng để mã hóa cho các ký tự, chẳng hạn là

256. Ðể dễ dàng thay đổi cách mã hóa, chúng ta dùng một hằng tượng trưng NUM

thay cho số nguyên mã hóa của num. Hàm lexan trả về NUM khi một dãy chữ số

được tìm thấy trong input. Biến toàn cục tokenval được đặt là giá trị của chuỗi số này.

Cài đặt của hàm lexan như sau :

# include<stdio.h>

# include<ctype.h>

int lineno = 1;

int tokenval = NONE;

int lexan ( )

{

int t;

while(1) {

t = getchar( );

if ( t = = ‘ ‘ || t = = ‘\t‘) ;

/* loại bỏ blank và tab */

else if (t = = ‘\n’)

lineno = lineno + 1;

else if ( isdigit (t) )

{

tokenval = t - ‘0’;

t = getchar( );

while ( isdigit (t) ) {

tokenval = tokenval * 10 + t - ‘0’;

t = getchar( );

29

}

ungetc (t, stdin);

return NUM;

}

else {

tokenval = NONE;

return t;

}

/* while */

}

/* lexan */

VI. SỰ HÌNH THÀNH BẢNG KÝ HIỆU

Một cấu trúc dữ liệu gọi là bảng ký hiệu (symbol table) thường được dùng để lưu

giữ thông tin về các cấu trúc của ngôn ngữ nguồn. Các thông tin này được tập hợp từ

các giai đoạn phân tích của trình biên dịch và được sử dụng bởi giai đoạn tổng hợp để

sinh mã đích. Ví dụ trong quá trình phân tích từ vựng, các chuỗi ký tự tạo ra một token

(trị từ vựng của token) sẽ được lưu vào một mục ghi trong bảng danh biểu. Các giai

đoạn sau đó có thể bổ sung thêm các thông tin về kiểu của danh biểu, cách sử dụng nó

và vị trí lưu trữ. Giai đoạn sinh mã sẽ dùng thông tin này để tạo ra mã phù hợp, cho

phép lưu trữ và truy xuất biến đó.

1. Giao diện của bảng ký hiệu

Các thủ tục trên bảng ký hiệu chủ yếu liên quan đến việc lưu trữ và truy xuất các

trị từ vựng. Khi một trị từ vựng được lưu trữ thì token kết hợp với nó cũng được lưu.

Hai thao tác sau được thực hiện trên bảng ký hiệu.

Insert (s, t): Trả về chỉ mục của một ô mới cho chuỗi s, token t.

Lookup (s): Trả về chỉ mục của ô cho chuỗi s hoặc 0 nếu chuỗi s không tồn tại.

Bộ phân tích từ vựng sử dụng thao tác tìm kiếm lookup để xác định xem một ô cho

một trị từ vựng của một token nào đó đã tồn tại trong bảng ký hiệu hay chưa? Nếu

chưa thì dùng thao tác xen vào insert để tạo ra một ô mới cho nó.

2. Xử lý từ khóa dành riêng

Ta cũng có thể sử dụng bảng ký hiệu nói trên để xử lý các từ khóa dành riêng

(reserved keyword). Ví dụ với hai token div và mod với hai trị từ vựng tương ứng là

div và mod. Chúng ta có thể khởi tạo bảng ký hiệu bởi lời gọi:

insert (“div”, div);

insert (“mod”, mod);

Sau đó lời gọi lookup (“div”) sẽ trả về token div, do đó “div” không thể được dùng

làm danh biểu.

Với phương pháp vừa trình bày thì tập các từ khóa được lưu trữ trong bảng ký hiệu

trước khi việc phân tích từ vựng diễn ra. Ta cũng có thể lưu trữ các từ khóa bên ngoài

30