Giáo trình môn Chương trình dịch (Compiler construction)

CHƯƠNG 5

BIÊN DỊCH DỰA CÚ PHÁP.

1. MỤC ĐÍCH, NHIỆM VỤ.

- Các hành động dịch phụ thuộc rất nhiều vào cú pháp của chương trình nguồn

cần dịch.Quá trình dịch được điều khiển theo cấu trúc cú pháp của chương

trình nguồn, cú pháp này được xác định thông qua bộ phân tích cú pháp.

- Nhằm điều khiển các phần hoạt động theo cú pháp, cách thường dùng là gia

cố các luật sản xuất ( mà ta biết cụ thể những luật nào và thứ tự thực hiện ra

sao thông qua cây phân tích) bằng cách thêm các thuộc tính cho văn phạm

đấy, và các qui tắc sinh thuộc tính gắn với từng luật cú pháp. Các qui tắc đó,

ta gọi là qui tắc ngữ nghĩa (semantic rules).

- thực hiện các qui tắc ngữ nghĩa đó sẽ cho thông tin về ngữ nghĩa, dùng để

kiểm tra kiểu, lưu thông tin vào bảng ký hiệu và sinh mã trung gian.

- Có hai tiếp cận để liên kết (đặc tả) các qui tắc ngữ nghĩa vào các luật cú pháp

(sản xuất) là cú pháp điều khiển (syntax-directed definition) và lược đồ dịch

(translation scheme).

- Các luật ngữ nghĩa còn có các hành động phụ (ngoài việc sinh thuộc tính cho

các ký hiệu văn phạm trong sản xuất) như in ra một giá trị hoặc cập nhật một

biến toàn cục.

Các kiến thức trong phần này không nằm trong khối chức năng riêng rẽ nào của chương

trình dịch mà được dùng làm cơ sở cho toàn bộ các khối nằm sau khối phân tích cú pháp.

Một xâu vào →Cây phân tích →Đồ thị phụ thuộc →thứ tựđánh giá cho các luật ngữ

nghĩa.

2. ĐỊNH NGHĨA CÚ PHÁP ĐIỀU KHIỂN.

Cú pháp điều khiển (syntax-directed definition) là một dạng tổng quát hoá của

văn phạm phi ngữ cảnh, trong đó mỗi ký hiệu văn phạm có một tập thuộc tính đi

kèm, được chia thành 2 tập con là thuộc tính tổng hợp (synthesized attribute) và

thuộc tính kế thừa (inherited attribute) của ký hiệu văn phạm đó.

Một cây phân tích cú pháp có trình bày các giá trị của các thuộc tính tại mỗi

nút được gọi là cây phân tích cú pháp có chú giải (hay gọi là cây phân tích đánh

dấu) (annotated parse tree).

2.1. Cú pháp điều khiển.

2.1.1. Dạng của định nghĩa cú pháp điều khiển.

Trong mỗi cú pháp điều khiển, mỗi sản xuất A->α có thể được liên kết với

một tập các qui tắc ngữ nghĩa có dạng b = f(c₁, . . .,c_k) với f là một hàm và

a) b là một thuộc tính tổng hợp của A, còn c₁, . . .,c_klà các thuộc tính của các ký

hiệu trong sản xuất đó. Hoặc

b) b là một thuộc tính kế thừa của một trong những ký hiệu ở vế phải của sản

xuất, còn c₁, . . . ,c_klà thuộc tính của các ký hiệu văn phạm.

Ta nói là thuộc tính b phụ thuộc vào các thuộc tính c₁, . . .,c_k.

- Một văn phạm thuộc tính (Attribute Grammar) là một cú pháp điều khiển

mà các luật ngữ nghĩa không có hành động phụ.

Ví dụ: Sau đây là văn phạm cho một chương trình máy tính bỏ túi với val là một

thuộc tính biểu diễn giá trị của ký hiệu văn phạm.

Sản xuất

L -> E n

E -> E₁+ T

E -> T

Luật ngữ nghĩa

Print(E.val)

E.val = E₁.val + T.val

E.val = T.val

T -> T₁* F

T -> F

T.val = T₁.val * F.val

T.val = F.val

F -> ( E )

F -> digit

F.val = E.val

F.val = digit.lexval

Từ tố digit có thuộc tính Lexval: là giá trị của digit đó được tính nhờ bộ phân tích từ vựng. Kí

hiệu n : xuống dòng, Print : in kết quả ra màn hình.

2.1.2. Thuộc tính tổng hợp.

Trên một cây phân tích, thuộc tính tổng hợp được tính dựa vào các thuộc ở

các nút con của nút đó, hay nói cách khác thuộc tính tổng hợp được tính cho các ký

hiệu ở vế trái của sản xuất và tính dựa vào thuộc tính của các ký hiệu ở vế phải.

Một cú pháp điều khiển chỉ sử dụng các thuộc tính tổng hợp được gọi là cú

pháp điều khiển thuần tính S (S-attribute definition).

Một cây phân tích cho văn phạm cú pháp điều khiển thuần tính S có thể thực

hiện các luật ngữ nghĩa theo hướng từ lá đến gốc và có thể sử dụng trong phương

pháp phân tích LR.

L

Ví dụ: vẽ cây cho đầu vào: 3*4+4n

E

n

1

E

T

F

+

2

3

1

3

ví dụ 1

T

F

2

*

2

4

Chúng ta duyệt và thực hiện các hành

động ngữ nghĩa của ví dụ trên theo đệ

trên xuống: khi gặp một nút ta sẽ thực

hiện tính thuộc tính tổng hợp của các

con của nó rồi thực hiện hành động ngữ

1

qui

4

3

nghĩa trên nút đó. Nói cách khác, khi phân tích cú pháp theo kiểu bottom-up, thì khi nào

gặp hành động thu gọn, chúng ta sẽ thực hiện hành động ngữ nghĩa để đánh giá thuộc

tính tổng hợp.

F₁.val=3 (syntax: F₁->3 semantic: F₁.val=3.lexical)

F₂.val=4 (syntax: F₂->3 semantic: F₂.val=4.lexical)

T₂.val=3 (syntax: T₂->F₁semantic: T₂.val=F₁.val )

T₁.val=3*4=12 (syntax: T₁->T₂*F₂semantic: T₁.val=T₂.val*F₂.val)

F₃.val=4 (syntax: F₃->4 semantic: F₃.val=4.lexical)

T₃.val=4 (syntax: T₃->F₃semantic: T₃.val=F₃.val )

E₁.val=12+4=16 (syntax: E₁->E₂+T₃semantic: E₁.val=E₂.val+T₃.val)

“16” (syntax: L->E₁n semantic: print(E₁.val))

2.1.3. Thuộc tính kế thừa.

Thuộc tính kế thừa (inherited attribute) là thuộc tính tại một nút có giá trị

được xác định theo giá trị thuộc tính của cha hoặc anh em của nó.

Thuộc tính kế thừa rất có ích trong diễn tả sự phụ thuộc ngữ cảnh. Ví dụ

chúng ta có thể xem một định danh xuất hiện bên trái hay bên phải của toán tử gán

để quyết định dùng địa chỉ hay giá trị của định danh.

Ví dụ về khai báo:

sản xuất

D -> T L

T -> int

luật ngữ nghĩa

L.in := T.type

T.type := interger

T -> real

L -> L₁, id

L -> id

T.type := real

L₁.in := L.in ; addtype(id.entry, L.in)

addtype(id.entry,L.in)

D

Ví dụ: int a,b,c Ta có cây cú pháp:

L₁

T

L₂

int

,

a

Chúng ta duyệt và thực hiện các hành

động ngữ nghĩa sẽ được kết quả như

sau:

,

b

L₃

c

T.type = interger (syntax:T->int semantic: T.type=interger)

L₁.in = interger (syntax: D -> T L₁semantic: L₁.in=T.type)

L₂.in = interger (syntax: L₁-> L₂, a semantic: L₂.in = L₁.in )

a.entry = interger (syntax: L₁-> L₂, a semantic: addtype(a.entry,L₁.in) )

L₃.in = interger (syntax: L₂-> L₃, b semantic: L₃.in = L₂.in )

b.entry = interger (syntax: L₂-> L₃, b semantic: addtype(b.entry,L₂.in) )

c.entry = interger (syntax: L₃-> c semantic: addtype(c.entry,L₃.in) )

Bài luyện tập:

1) Cho văn phạm sau định nghĩa một số ở hệ cơ số 2

B -> 0 | 1 | B 0 | B 1

Hãy định nghĩa một cú pháp điều khiển để dịch một số ở hệ cơ số 2 thành một số ở hệ cơ số

10 (hay nói cách khác là tính giá trị của một số ở hệ cơ số 2). Xây dựng cây đánh dấu(xây

dựng cây cú pháp cùng với giá trị thuộc tính trên mỗi nút) với đầu vào là “1001”.

Mở rộng: sinh viên tự làm bài toán này với các sản xuất định nghĩa một số thực ở hệ cơ số 2:

S->L.L | L

L->LB | B

B->0 | 1

Lời giải: Định nghĩa thuộc tính tổng hợp val của ký hiệu B để chứa giá trị tính được của số

biểu diễn bởi B.

xuất phát từ cách tính:

(a_na_n-1. . . a₁a₀)₂:= a_n*2ⁿ+a_n-1*2^n-1+. . . +a₁*2+a₀

:= 2*(a_n*2^n-1+. . .+a₁)+a₀

:= 2*(a_n. . .a₁)+a₀

Do đó nếu có

B -> B₁1 thì B.val := 2*B₁.val+1

B -> B₁0 thì B.val := 2*B₁.val

Vì vậy, chúng ta xây dựng các luật dịch như sau:

Luật phi ngữ cảnh

B->0

Luật dịch

B.val=0;

B->1

B.val:=1;

B->B₁0

B->B 1

B.val:=2*B₁.val +0

B.val:=2*B₁.val+1

Cây đánh dấu:

B: val:=2*4+1=9

B: val:=2*2+0=4

1

B: val:=2*1+0=2

0

B: val:=1

1

Xét một cây đánh dấu khác cho xâu vào “1011”

B:

val:=5*2+1=11

B: val:=2*2+1=5

1

B: val:=2*1+0=2

1

B: val:=1

0

1

2.2. Đồ thị phụ thuộc.

Nếu một thuộc tính b tại một nút trong cây phân tích cú pháp phụ thuộc vào một

thuộc tính c, thế thì hành động ngữ nghĩa cho b tại nút đó phải được thực hiện sau khi

thực hiện hành động ngữ nghĩa cho c. Sự phụ thuộc qua lại của các thuộc tính tổng hợp

và kế thừa tại các nút trong một cây phân tích cú pháp có thể được mô tả bằng một đồ thị

có hướng gọi là đồ thị phụ thuộc (dependency graph).

- Đồ thị phụ thuộc là một đồ thị có hướng mô tả sự phụ thuộc giữa các thuộc

tính tại mỗi nút của cây phân tích cú pháp.

Trước khi xây dựng một đồ thị phụ thuộc cho một cây phân tích cú pháp,

chúng ta chuyển mỗi hành động ngữ nghĩa thành dạng b := f(c₁,c₂,. . .,c_k) bằng cách

dùng một thuộc tính tổng hợp giả b cho mỗi hành động ngữ nghĩa có chứa một lời

gọi thủ tục. Đồ thị này có một nút cho mỗi thuộc tính, một cạnh đi vào một nút cho

b từ một nút cho c nếu thuộc tính b phụ thuộc vào thuộc tính c. Chúng ta có thuật

toán xây dựng đồ thị phụ thuộc cho một văn phạm cú pháp điều khiển như sau:

for mỗi nút n trong cây phân tích cú pháp do

for mỗi thuộc tính a của ký hiệu văn phạm tại n do

xây dựng một nút trong đồ thị phụ thuộc cho a;

for mỗi nút n trong cây phân tích cú pháp do

for mỗi hành động ngữ nghĩa b:=f(c₁,c₂, . . .,c_k)

đi kèm với sản xuất được dùng tại n do

for i:=1 to k do

xây dựng một cạnh từ nút c_iđến nút b

VD 1: Dựa vào cây phân tích ( nét đứt đoạn) và luật ngữ nghĩa ứng với sản xuất ở bảng, ta thêm

các nút và cạnh thành đồ thị phụ thuộc:

E

Sản xuất

E →E₁| E₂

Luật ngữ nghĩa

E.val = E₁.val + E₂.val

E₁

E₂

+

Val

Ví dụ 2:

Với ví dụ 2, ta có một đồ thị phụ thuộc như sau:

chú ý:

+ chuyển hành động ngữ nghĩa addentry(id.entry,L.in) của sản xuất L->L , id thành thuộc tính giả

f phụ thuộc vào entry và in

sản xuất

D -> T L

T -> int

luật ngữ nghĩa

L.in := T.type

T.type := interger

T -> real

L -> L₁, id

L -> id

T.type := real

L₁.in := L.in ; addtype(id.entry, L.in)

addtype(id.entry,L.in)

D

in

f

T

L

type

in

entry

f

L

,

c

rea

l

in

entry

f

L

,

b

entry

a

2.3. Thứ tự đánh giá thuộc tính.

Trên đồ thị DAG được xây dựng như ví dụ trên, chúng ta phải xác định thứ

tự của các nút để làm sao cho khi duyệt các nút theo thứ tự này thì một nút sẽ có

thứ tự sau nút mà nó phụ thuộc ta gọi là một sắp xếp topo. Tức là nếu các nút được

đánh thứ tự m₁, m₂, . . .,m_kthì nếu có m_i->m_jlà một cạnh từ m_iđến m_jthì m_ixuất

hiện trước m_jtrong thứ tự đó hay i<j. Nếu chúng ta duyệt theo thứ tự đã được sắp

xếp này thì sẽ được một cách duyệt hợp lý cho các hành động ngữ nghĩa. Nghĩa là

trong một sắp xếp topo, giá trị các thuộc tính phụ thuộc c₁,c₂, _{. . .},c_ktrong một hành

động ngữ nghĩa b:=f(c₁,c₂, _{. . .},c_k) đã được tính trước khi ta ước lượng f.

Đối với một đồ thị tổng quát, chúng ta phải để ý đến các đặc điểm sau:

+ xây dựng đồ thị phụ thuộc cho các thuộc tính của ký hiệu văn phạm phải

được xây dựng trên cây cú pháp. Tức là xây dựng cây cú pháp với mỗi nút (đỉnh)

đại diện cho một ký hiệu văn phạm sau đó mới xây dựng đồ thị phụ thuộc theo

thuật toán 5.1

+ trong đồ thị phụ thuộc, mỗi nút đại diện cho một thuộc tính của một ký

hiệu văn phạm.

+ có thể một loại thuộc tính này lại phụ thuộc vào một loại thuộc tính khác,

chứ không nhất thiết là chỉ các thuộc tính cùng loại mới phụ thuộc vào nhau. Trong

ví dụ trên, thuộc tính entry phụ thuộc vào thuộc tính in.

+ có thể có “vòng” trong đồ thị phụ thuộc, khi đó chúng ta sẽ không tính

được giá trị ngữ nghĩa cho các nút vì gặp một hiện tượng khi tính a cần tính b, mà

khi tính b lại cần tính a.

Chính vì vậy, trong thực tế chúng ta chỉ xét đến văn phạm cú pháp ngữ nghĩa

mà đồ thị phụ thuộc của nó là một DAG không có vòng.

Đối với ví dụ trên, chúng ta xây dựng được một thứ tự phụ thuộc trên các

thuộc tính đối với cây cú pháp cho câu vào “real a,b,c” như sau:

D

in: 5

f: 6

L

T

type: 4

in: 7

entry: 3

f: 8

L

,

c

rea

l

in: 8

entry: 2

f: 9

,

b

L

a

entry: 1

Sau khi chúng ta đã có đồ thị phụ thuộc này, chúng ta thực hiện các hành động ngữ

nghĩa theo thứ tự như sau (ký hiệu a_ilà giá trị thuộc tính ở nút thứ i):

- đối với nút 1,2 ,3 chúng ta duyệt qua nhưng chưa thực hiện hành động ngữ

nghĩa nào cả

- nút 4: ta có a₄:= real

- nút 5: a₅:= a₄:= real

- nút 6: addtype(c.entry,a₅) = addtype(c.entry,real)

- nút 7: a₇:= a₅:= real

- nút 8: addtype(b.entry,a₇) = addtype(b.entry,real)

- nút 9: addtype(a.entry,a₈) = addtype(a.entry,real)

Các phương pháp duyệt hành động ngữ nghĩa

1. Phương pháp dùng cây phân tích cú pháp. Kết quả trả về của phân tích cú

pháp phải là cây phân tích cú pháp, sau đó xây dựng một thứ tự duyệt hay

một sắp xếp topo của đồ thị từ cây phân tích cú pháp đó. Phương pháp này

không thực hiện được nếu đồ thị phụ thuộc có “vòng”.

2. Phương pháp dựa trên luật. Vào lúc xây dựng trình biên dịch, các luật ngữ

nghĩa được phân tích (thủ công hay bằng công cụ) để thứ tự thực hiện các

hành động ngữ nghĩa đi kèm với các sản xuất được xác định trước vào lúc

xây dựng.

3. Phương pháp quên lãng (oblivious method). Một thứ tự duyệt được lựa chọn

mà không cần xét đến các luật ngữ nghĩa. Thí dụ nếu quá trình dịch xảy ra

trong khi phân tích cú pháp thì thứ tự duyệt phải phù hợp với phương pháp

phân tích cú pháp, độc lập với luật ngữ nghĩa. Tuy nhiên phương pháp này

chỉ thực hiện trên một lớp các cú pháp điều khiển nhất định.

Phương pháp dựa trên qui tắc và phương pháp quên lãng không nhất thiết phải xây dựng một đồ

thị phụ thuộc, vì vậy nó rất là hiệu quả về mặt thời gian cũng như không gian tính toán.

Trong thực tế, các ngôn ngữ lập trình thông thường có yêu cầu quá trình phân tích là tuyến tính,

quá trình phân tích ngữ nghĩa phải kết hợp được với các phương pháp phân tích cú pháp tuyến

tính như LL, LR. Để thực hiện được điều này, các thuộc tính ngữ nghĩa cũng cần thoả mãn điều

kiện: một thuộc tính ngữ nghĩa sẽ được sinh ra chỉ phụ thuộc vào các thông tin trước nó. Chính

vì vậy chúng ta sẽ xét một lớp cú pháp điều khiển rất thông dụng và được sử dụng hiệu quả gọi

là cú pháp điều khiển thuần tính L.

Cú pháp điều khiển thuần tính L

Một thứ tự duyệt tự nhiên đặc trưng cho nhiều phương pháp dịch Top-down và Bottom-up

là thủ tục duyệt theo chiều sâu (depth-first order). Thủ tục duyệt theo chiều sâu được trình bày

như dưới đây:

procedure dfvisit(n:node);

begin

end

for mỗi con m của n tính từ trái sang phải do

begin

tính các thuộc tính kế thừa của m

dfvisit(m)

end

tính các thuộc tính tổng hợp của n

Một lớp các cú pháp điều khiển được gọi là cú pháp điều khiển thuần tính L hay gọi là

điều khiển thuần tính L (L-attributed definition) có các thuộc tính luôn có thể tính toán theo chiều

sâu.

Cú pháp điều khiển thuần tính L:

Một cú pháp điều khiển gọi là thuần tính L nếu mỗi thuộc tính kế thừa của X_i

ở vế phải của luật sinh A -> X₁X₂. . . X_nvới 1<=j<=n chỉ phụ thuộc vào:

1.

sản xuất và

2.

các thuộc tính của các ký hiệu X₁, X₂, . . .,X_j-1ở bên trái của X_jtrong

các thuộc tính kế thừa của A

Chú ý rằng mỗi cú pháp điều khiển thuần tính S đều thuần tính L vì các điều

kiện trên chỉ áp dụng cho các thuộc tính kế thừa.

Ta thấy nếu ngôn ngữ mà ngữ nghĩa của một từ tố được xác định chỉ phụ

thuộc vào ngữ cảnh bên trái (các từ tố bên trái) thì một phương pháp duyệt cú pháp

từ trái sang phải cho đầu vào có thể kết hợp với điều khiển ngữ nghĩa để duyệt cả

cú pháp và ngữ nghĩa đồng thời. Từ đó, ta thấy cú pháp điều khiển thuần tính L

thoả mãn điều kiện này. Hay với cú pháp điều khiển thuần tính L, ta có thể duyệt

đầu vào từ trái sang phải để sinh các thông tin cú pháp và ngữ nghĩa một cách đồng

thời. Với phương pháp phân tích cú pháp tuyến tính LL và LR, ta có thể kết hợp để

thực hiện cả các hành động ngữ nghĩa thuần tính L.

Nhưng nếu mô tả các hành động ngữ nghĩa theo cú pháp điều khiển thì

không xác định thứ tự của các hành động trong một sản xuất. Vì vậy ở đây ta xét

một tiếp cận khác là dùng lược đồ dịch để mô tả luật ngữ nghĩa đồng thời với thứ tự

thực hiện chúng trong một sản xuất.

Thực hiện hành động ngữ nghĩa trong phân tích LL

Thiết kế dịch là dịch một lượt: khi ta đọc đầu vào đến đâu thì chúng ta sẽ

phân tích cú pháp đến đó và thực hiện các hành động ngữ nghĩa luôn.

Một phương pháp xây dựng chương trình phân tích cú pháp kết hợp với thực

hiện các hành động ngữ nghĩa như sau:

- với mỗi một ký hiệu không kết thúc được gắn với một hàm thực hiện. Giả sử

với ký hiệu không kết thúc A, ta có hàm thực hiện

void ParseA(Symbol A);

- mỗi ký hiệu kết thúc được gắn với một hàm đối sánh xâu vào

- giả sử ký hiệu không kết thúc A là vế trái của luật A-> α | α | . . . | α

1

2

n

Như vậy hàm phân tích ký hiệu A sẽ được định nghĩa như sau:

void ParseA(Symbol A, Rule r, ...)

{

if(r==A->α )

1

gọi hàm xử lý ngữ nghĩa tương ứng luật A->α

1

2

else if(r==A->α )

2

gọi hàm xử lý ngữ nghĩa tương ứng luật A->α

. . .

else if(r==A->α )

n

gọi hàm xử lý ngữ nghĩa tương ứng luật A->α

n

}

Đối chiếu ký hiệu đầu vào và A, tìm trong bảng phân tích LL xem sẽ khai

triển A theo luật nào. Chẳng hạn ký hiệu xâu vào hiện thời a first(α ),

i

chúng ta sẽ khai triển A theo luật A -> X₁. . . X_kvới α = X₁. . . X_k

i

Ở đây, ta sẽ sử dụng lược đồ dịch để kết hợp phân tích cú pháp và ngữ nghĩa.

Do đó đó khi khai triển A theo vế phải, ta sẽ gặp 3 trường hợp sau:

1. nếu phần tử đang xét là một ký hiệu kết thúc, ta gọi hàm đối sánh với xâu

vào, nếu thoả mãn thì nhẩy con trỏ đầu vào lên một bước, nếu trái lại là

lỗi.

2. nếu phần tử đang xét là một ký hiệu không kết thúc, chúng ta gọi hàm

duyệt ký hiệu không kết thúc này với tham số bao gồm các thuộc tính của

các ký hiệu anh em bên trái, và thuộc tính kế thừa của A.

3. nếu phần tử đang xét là một hành động ngữ nghĩa, chúng ta thực hiện

hành động ngữ nghĩa này.

Ví dụ:

E -> T {R.i:=T.val}

R {E.val:=R.s}

R ->

+

T {R₁.i:=R.i+T.val}

R₁{R.s:=R₁.s}

R -> ε {R.s:=R.i}

T -> ( E ) {T.val:=E.val}

T -> num {T.val:=num.val}

void ParseE(...)

{

// chỉ có một lược đồ dịch:

// E -> T {R.i:=T.val}

// R {E.val:=R.s}

ParseT(...);

R.i := T.val

ParseR(...); E.val := R.s

}

void ParseR(...)

// trường hợp 1

//R -> +

//T {R1.i:=R.i+T.val}

//R1 {R.s:=T.val+R1.i}

if(luật=R->TR₁)

{

match(‘+’);// đối sánh

ParseT(...); R₁.i:=R.i+T.val;

ParseR(...); R.s:=R₁.s

}

else if(luật=R->ε )

{ // R ->ε {R.s:=R.i}

R.s:=R.i

}

Tương tự đối với hàm ParseT()

Bây giờ ta xét xâu vào: “6+4”

First(E)=First(T) = {(,num}

First(R) = {ε ,+}

Follow(R) = {$,)}

Xây dựng bảng LL(1)

num

+

(

)

$

E

T

R

E->TR

T->num

E->TR

T->(E)

R->+TR

R->ε

Đầu vào “6+4”, sau khi phân tích từ vựng ta được “num1 + num2”

Ngăn xếp

$E

Đầu vào

Luật sản xuất

Luật ngữ nghĩa

num1 + num2 $ E->TR

$RT

$Rnum1

$R

$R₁T+

$R₁T

$R₁num2

$R₁

num1 + num2 $ T->num1

num1 + num2 $

+ num2 $ R->+TR₁

+ num2 $

T.val=6

R.i=T.val=6

T.val=4

num2 $ T->num2

num2 $

$

R₁.i=T.val=4

R₁.s=T.val+R₁.i=10

R₁->ε

$

R.s=R₁.s=10

E.val=R.s=10

Nhận xét:

Mọi cú pháp điều khiển thuần tính L dựa trên văn phạm LL(1) đều có thể kết hợp quá

trình phân tích cú pháp tuyến tính với việc thực hiện các hành động ngữ nghĩa.

Thực hiện hành động ngữ nghĩa trong phân tích LR

Đối với cú pháp điều khiển thuần tính S (chỉ có các thuộc tính tổng hợp), tại mỗi

bước thu gọn bởi một luật, chúng ta thực hiện các hành động ngữ nghĩa tính thuộc tính

tổng hợp của vế trái dựa vào các thuộc tính tổng hợp của các ký hiệu vế phải đã được

tính.

Ví dụ, đối với cú pháp điều khiển tính giá trị biểu thức cho máy tính bỏ túi:

Luật cú pháp

Luật ngữ nghĩa (luật dịch)

L->E n

E->E₁+T

E->T

print(E.val)

E.val:=E₁.val+T.val

E.val:=T.val

T->T₁*F

T->F

T.val:=T₁.val*F.val

T.val:=F.val

F->(E)

F->digit

F.val:=E.val

F.val:=digit.lexval

Chẳng hạn chúng ta sẽ thực hiện các luật ngữ nghĩa này bằng cách sinh ra thêm một

ngăn xếp để lưu giá trị thuộc tính val cho các ký hiệu (gọi là ngăn xếp giá trị). Mỗi khi

trong ngăn xếp trạng thái có ký hiệu mới, chúng ta lại đặt vào trong ngăn xếp giá trị

giá trị thuộc tính val cho ký hiệu mới này. Còn nếu khi ký hiệu bị loại bỏ ra khỏi ngăn

xếp trạng thái thì chúng ta cũng loại bỏ giá trị tương ứng với nó ra khỏi ngăn xếp giá

trị. Chúng ta có thể xem qua quá trình phân tích gạt, thu gọn với ví dụ cho xâu vào

“3*5+4”:

chú ý:

+ phân tích từ tố cho ta kết quả xâu vào là (ký hiệu d là digit):

d1(3)*d2(5)+d3(4)n

+ với ký hiệu không có giá trị val, chúng ta ký hiệu ‘-‘ cho val của nó

xâu vào

ngăn xếp trạng ngăn xếp giá luật cú pháp, ngữ nghĩa

thái

trị

d1 * d2 + d3 n

* d2 + d3 n

gạt

F->digit

d1

F

3

F.val:=digit.lexval

(loại bỏ digit)

T->F

* d2 + d3 n

d2 + d3 n

T

3

T.val:=F.val

(loại bỏ F)

gạt

* T

- 3

+ d3 n

d2 * T

F * T

5 - 3

5 – 3

F->digit

F.val:=digit.lexval

(loại bỏ digit)

T->T₁*F

+ d3 n

T

E

15

T.val:=T₁.val*F.val

(loại bỏ T₁,*,F)

E->T

E.val:=T.val

(loại bỏ T)

gạt

d3 n

n

+ E

d3 + E

F + E

- 15

4 - 15

4 – 15

gạt

F->digit

F.val:=digit.lexval

(loại bỏ digit)

T->F

n

T + E

E

4 - 15

19

T.val:=F.val

(loại bỏ F)

E->E₁+T

E.val:=E₁.val+T.val

(loại bỏ E₁,+,T )

gạt

E n

L

- 19

19

L->E n

L.val:=E.val

(loại bỏ E,n)

Chú ý là không phải mọi cú pháp điều khiển thuần tính L đều có thể kết hợp thực hiện các

hành động ngữ nghĩa khi phân tích cú pháp mà không cần xây dựng cây cú pháp. Chỉ có một

lớp hạn chế các cú pháp điều khiển có thể thực hiện như vậy, trong đó rõ nhất là cú pháp điều

khiển thuần tuý S.

Sau đây, chúng ta giới thiệu một số cú pháp điều khiển khác mà cũng có thể thực hiện khi

phân tích LR bằng một số kỹ thuật:

1) loại bỏ việc gắn kết các hành động ngữ nghĩa ra khỏi lược đồ dịch

2) kế thừa các thuộc tính trên ngăn xếp

3) Mô phỏng thao tác đánh giá các thuộc tính kế thừa

4) Thay thuộc tính kế thừa bằng thuộc tính tổng hợp

Sinh viên tự tham khảo trong tài liệu các phần này.

3. LƯỢC ĐỒ CHUYỂN ĐỔI(Lược đồ dịch) - Translation Scheme

Lược đồ chuyển đổi là một văn phạm phi ngữ cảnh trong đó các thuộc tính

được liên kết với các ký hiệu văn phạm và các hành động ngữ nghĩa nằm giữa hai

dấu ngoặc móc {} được chèn vào một vị trí nào đó bên vế phải của sản xuất.

+ Lược đồ dịch vẫn có cả thuộc tính tổng hợp và thuộc tính kế thừa

+ Lược đồ dịch xác định thứ tự thực hiện hành động ngữ nghĩa trong mỗi sản

xuất

Ví dụ: một lược đồ dịch để sinh biểu thức hậu vị cho một biểu thức như sau:

E -> T R

R -> + T {print(‘+’)} R

R -> ε

T -> num {print(num.val)}

Xét biểu thức “3+1+5”

Chúng ta duyệt theo thủ tục duyệt theo chiều sâu. Các hành động ngữ nghĩa được

đánh thứ tự lần lượt 1,2,3, . . .

E

3: print(‘+’)

T

3

R

+

T

R

5: print(‘+’)

1: print(‘3’)

1

+

T

5

R

2: print(‘1’)

ε

4: print(‘5’)

Kết quả dịch là “3 1 + 5 +”

Chú ý là nếu trong lược đồ dịch ta đặt hành động ngữ nghĩa ở vị trí khác đi, chúng ta sẽ

có kết quả dịch khác ngay. Ví dụ, đối với lược đồ dịch, ta thay đổi một chút thành lược đồ

dịch như sau:

E -> T R

R -> + T R {print(‘+’)}

R -> ε

T -> num {print(num.val)}

Xét biểu thức “3+1+5”

Chúng ta duyệt theo thủ tục duyệt theo chiều sâu. Các hành động ngữ nghĩa được

đánh thứ tự lần lượt 1,2,3, . . .

E

5: print(‘+’)

T

3

R

+

T

R

4: print(‘+’)

1: print(‘3’)

1

+

T

5

R

2: print(‘1’)

ε

3: print(‘5’)

Kết quả dịch là “3 1 5 + +”

Khi thiết kế lược đồ dịch, chúng ta cần một số điều kiện để đảm bảo rằng

một giá trị thuộc tính phải có sẵn khi chúng ta tham chiếu đến nó:

1. Một thuộc tính kế thừa cho một ký hiệu ở vế phải của một sản xuất phải

được tính ở một hành động nằm trước ký hiệu đó.

2. Một hành động không được tham chiếu đến thuộc tính của một ký hiệu ở

bên phải của hành động đó.

3. Một thuộc tính tổng hợp cho một ký hiệu không kết thúc ở vế trái chỉ có

thể được tính sau khi tất cả thuộc tính nó cần tham chiếu đến đã được tính

xong. Hành động như thế thường được đặt ở cuối vế phải của luật sinh.

Ví dụ lược đồ dịch sau đây không thoả mãn các yêu cầu này:

S -> A₁A₂{A₁.in:=1; A₂.in:=2}

A -> a {print(A.in)}

Ta thấy thuộc tính kế thừa A.in trong luật thứ 2 chưa được định nghĩa vào lúc muốn in ra

giá trị của nó khi duyệt theo hướng sâu trên cây phân tích cho đầu vào aa. Để thoả mãn

thuộc tính L, chúng ta có thể sửa lại lược đồ trên thành như sau:

S -> {A₁.in:=1 } A₁{A₂.in:=2} A₂

A -> a {print(A.in)}

Như vậy, thuộc tính A.in được tính trước khi chúng ta duyệt A.

Những điều kiện này được thoả nếu văn phạm có điều khiển thuần tính L.

Khi đó chúng ta sẽ đặt các hành động theo nguyên tắc như sau:

1. Hành động tính thuộc tính kế thừa của một ký hiệu văn phạm A bên vế

phải được đặt trước A.

2. Hành động tính thuộc tính tổng hợp của ký hiệu vế trái được đặt ở cuối

luật sản xuất.

Ví dụ:

Cho văn phạm biểu diễn biểu thức gồm các toán tử + và - với toán hạng là các số:

E -> T R

R -> + T R

R -> - T R

R -> ε

T -> ( E )

T -> num

Xây dựng lược đồ dịch trên văn phạm này để tính giá trị của biểu thức.

Giải đáp:

Trước hết, chúng ta thử xem cây phân tích cú pháp cho đầu vào “6+4-1”

E

T

R

num(6

)

+

T

R

num(4

-

T

R

)

num(1

)

ε

Gọi val là thuộc tính chứa giá trị tính được của các ký hiệu văn phạm E và T.

Thuộc tính s là thuộc tính tổng hợp và i là thuộc tính kế thừa để chứa giá trị tính

được của ký hiệu R. Chúng ta đặt R.i chứa giá trị của phần biểu thức đứng trước R

và R.s chứa kết quả. Chúng ta xây dựng lược đồ dịch như sau:

E -> T {R.i:=T.val}

R {E.val:=R.s}

R -> +

T {R₁.i:=R.i+T.val}

R₁{R.s:=R₁.s }

R -> -

T { R₁.i:=R.i-T.val }

R₁{R.s:=R₁.s}

R -> ε {R.s:=R.i}

T -> ( E ) {T.val:=E.val}

T -> num {T.val:=num.val}

E val=9

R i=6 s=9

T val=6

T

val=4

num(6

)

R i=10 s=9

T val=1

+

num(4

)

R i=9 s=9

-

num(1

)

ε

Lưu ý:

nếu chúng ta xác định một cách duyệt khác cách duyệt theo hướng sâu thì cách đặt

hành động dịch vào vị trí nào sẽ được làm khác đi. Tuy nhiên cách duyệt theo hướng

sâu là cách duyệt phổ biến nhất và tự nhiên nhất (vì ngữ nghĩa sẽ được xác định dần

theo chiều duyệt đầu vào từ trái sang phải) nên chúng ta coi khi duyệt một cây phân

tích, chúng ta sẽ duyệt theo hướng sâu.

4. DỰNG CÂY CÚ PHÁP.

4.1. Cây cú pháp.

Cây cú pháp (syntax - tree) là dạng rút gọn của cây phân tích cú pháp dùng

để biểu diễn cấu trúc ngôn ngữ. Trong cây cú pháp các toán tử và từ khóa không

phải là nút lá mà là các nút trong.

Ví dụ với luật sinh S → if B then S1 else S2 được biểu diễn bởi cây cú pháp:

Xây dựng cây cú pháp cho biểu thức.

Tương tự như việc dịch một biểu thức thành dạng hậu tố. Xây dựng cây con cho

biểu thức con bằng cách tạo ra một nút cho toán hạng và toán tử. Con của nút toán

tử là gốc của cây con biểu diễn cho biểu thức con toán hạng của toán tử đó. Mỗi

một nút có thể cài đặt bằng một mẩu tin có nhiều trường.

Trong nút toán tử, có một trường chỉ toán tử như là nhãn của nút, các trường còn lại

chứa con trỏ, trỏ tới các nút toán hạng.

Để xây dựng cây cú pháp cho biểu thức chúng ta sử dụng các hàm sau đây:

1/ mknode(op, left, right) : Tạo một nút toán tử ó nhãn là op và hai trờng chứa con

trỏ, trỏ tới left và right.

2/ mkleaf(id, entry): Tạo một nút lá với nhãn là id và một trờng chứa con trỏ entry,

trỏ tới ô trong bảng ký hiệu danh biểu.

3/ mkleaf(num,val): Tạo một nút lá với nhãn là num và trờng val, giá trị của số.

Ví dụ: Để xây dựng cây cú pháp cho biểu thức: a - 4 + c ta dùng một dãy các lời

gọi các hàm nói trên.

(1): p1 := mkleaf(id, entrya)

(2): p2 := mkleaf(num,4)

(4): p4 := mkleaf(id, entryc)

(5): p5 := mknode(" +", p3, p4)

(3): p3 := mknode(" -", p1, p2)

Cây được xây dựng từ dưới lên

entrya là con trỏ, trỏ tới ô của a trong bảng ký hiệu

entryc là con trỏ, trỏ tới ô của c trong bảng ký hiệu

* xây dựng cây cú pháp từ định nghĩa trực tiếp cú pháp.

Căn cứ vào các luật sinh văn phạm và luật ngữ nghĩa kết hợp mà ta phân bổ việc

gọi các hàm mknode và mkleaf để tạo ra cây cú pháp.

Ví dụ: Định nghĩa trực tiếp cú pháp giúp việc xây dựng cây cú pháp cho biểu thức

là:

Luật sinh Luật ngữ nghĩa

E →E1 + T E.nptr := mknode('+', E1.nptr, T.nptr)

E →E1 - T E.nptr := mknode('-', E1.nptr, T.nptr)

E →T E.nptr := T.nptr

T →(E) T.nptr := E.nptr

T →id T. nptr := mkleaf(id, id.entry)

T →num T.nptr := mkleaf(num, num.val)

Với biểu thức a - 4 + c ta có cây phân tích cú pháp (biểu diễn bởi đường chấm)

Luật ngữ nghĩa cho phép tạo ra cây cú pháp. Cây cú pháp có ý nghĩa về mặt cài đặt

còn cây phân tích cú pháp chỉ có ý nghĩa về mặt logic.

4.3. Đồ thị DRAG.

DAG ( Directed Acyclic Graph): Đồ thị bao gồm các đỉnh chứa các thuộc tính và

cỏc cạnh cú hướng để biểu thị sự phụ thuộc giữa các đỉnh. Cũng giống như cây cú

pháp, tuy nhiên trong cây cú pháp các biểu thức con giống nhau biểu diễn lặp lại

còn trong DAG thì không. Trong DAG, một nút con có thể có nhiều "cha".

Giáo trình môn Chương trình dịch (Compiler construction) - Phần 2