Chương 1:

Cấu trúc chương trình dịch

-          Chương trình dịch là chuyển từ một chương trình viết bầng ngôn ngữ bậc cao về chương trình gần với mã máy.

-          Cấu trúc một chương trình dịch

Các giai đoạn của chương trình dịch

Gồm 2 giai đoạn :

-          Phân tích: Câu cần dịch trong ngôn ngữ nguồn phải là câu hiểu được có nghĩa là xác định được các từ là đúng và các thành phần của câu phải tuân theo các luật ngữ pháp dễ hiểu được ta phải phân tích. Là giai đoạn gắn liền với chương trình nguồn  

-                      + Phân tích từ vựng

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

+ Phân tích ngữ nghĩa

-          Tổng hợp: các thông tin thu được thành câu mới trong ngôn ngữ đích sao cho nó có cùng ý nghĩa đối với câu ban đầu. Là giai đoạn gắn với chương trình đích

+ Sinh mã trung gian

+ Sinh mã đích

Cho ví dụ

-          Chuyển chương trình viết bằng ngôn ngữ bậc cao như C#, C++ sang ngôn ngữ máy như Asemblly. Hay chuyển các file *.CCP sang file *.EXE

Chương 2: Phân tích từ vựng

Mục đích, nhiệm vụ, ý nghĩa của phân tích từ vựng

-            Mục đích: bộ phân tích từ vựng là đọc các ký tự vào từ văn bản chương trình nguồn và đưa ra lần lượt các từ tố cùng một số thông tin thuộc tính. Phân tích từ vựng còn được gọi là phân tích tuyến tính hoặc đơn giản hơn là phần quét.

-              Nhiệm vụ: Chuyển đổi dãy các kí tự của chương trình nguồn thành dãy các từ tố (token) bao gồm <loại từ tố> và <thuộc tính>

-          Ý nghĩa: Nâng cao tốc độ phân tích của một chương trình dịch

Các bước xây dựng bộ phân tích từ vựng

Gồm 6 bước:

-          Bước 1:  Sưu tầm luật từ tố (Mô tả bằng lời)

-          Bước 2: Biểu diển các từ tố bằng biểu diễn chính quy

-          Bước 3: Đồ thị dịch chuyển

-          Bước 4: Kết hợp các đồ thị chuyển thành một đồ thị duy nhất

+ Viết chương trình cho đồ thị chuyển

+ Chuyển sang bước 5

-          Bước 5: Automat

-          Bước 6: Viết chương trình cho Automat

3.  Ví dụ: Xây dựng bộ phân tích từ vự để dón nhận tên, số nguyên

-          Bước 1: Mô tả

+ Tên: Bắt đầu bằng chữ cái theo sau là không hoặc nhiều chữ cái, chữ số

+ Số nguyên: Bắt đầu bằng chữ số, theo sau là không hoặc nhiều chữ số

-          Bước 2:Biểu diễn chính quy

+ Tên: (chữ cái) (chữ cái/chữ số)*

+ Số nguyên: (chữ số) (chữ số)*

-        Bước 3: Đồ thị dịch chuyển

+ Tên

+ Chữ số

-        Bước 4: Kết hợp các đồ thị

-          Bước 5: Automat

A = < S, d, qo, Q, F> với:

S = { cc, cs}

d: Hàm chuyển

qo: trạng thái bắt đầu

Q: Trạng thái chuyển

F: Tập kết thúc

Bảng Automat

cc

cs

Khác

0

1

3

1

1

1

2

2

Î F

3

4

3

4

4

Î F

Chương 3: Phân tích cú pháp

Phương pháp TOP – DOWN

-          Ý tưởng:

 Tạo ra một cây phân tích cho xâu vào bắt đầu từ đỉnh và đi dần cho đến lá. Với một văn phạm phi ngữ cảnh cho trước thì trước tiên chúng ta sẽ đanh dấu mọi lựa chọn trong từng SX (đánh số thứ tự). Ta dùng một con trỏ, trỏ đến xâu vào kí hiệu trên, xâu vào do con trỏ trỏ đến gọi là kí hiệu vào hiện tại.

-          Thuật toán:

@ Đánh số thứ tự của các sản xuất trong VP

@ Quét xâu vào từ trái sang phải

@ Lần lượt khai triển theo các danh sách đã được đánh số

+ So sánh nếu kí tự bên trái nhất của xâu vào mà khớp với kí hiệu bên trái nhất của xâu phân tích thì dịch chuyển con trỏ sang kí hiệu vào tiếp theo của xâu vào và lấy node bên phải của cây để xét tiếp.

+ Nếu ko khớp thì quay lại bước gần nhất và lựa chọn sản xuất được đánh số tiếp theo để khai triển.

@ Dừng lại khi:

+ Quét hết xâu vào mà không còn kí hiệu nào trên cây mà chưa được xét à THÀNH CÔNG

+ Nếu quay lui hết các trường hợp mà ko đạt được kí hiệu kết thúc à THẤT BẠI

-          Ví dụ: Xem trong vở nhé J

Phương pháp BOTTOM UP

-          Ý tưởng:

Phương pháp này ngược lại phương pháp phân tích Top – Down tức là bắt đầu từ lá cố gắng xây dựng thành cây bằng cách hướng lên gốc còn gọi là gạt thu gọn. Quá trình phân tích sử dụng bộ phân tích phải duyệt các suy dẫn phải có thể được tương ứng với xâu vào

-          Thuật toán

@ Gạt lần lượt các kí tự của xâu vào trong STACK

@ So sánh với các kí tự trên đỉnh của STACK có trùng với vế phải của sản xuất thì ta thực hiện thu gọn bằng cách thay kí hiệu trên cùng của STACK bằng kí tự bên trái của sản xuất. Nếu có nhiều lựa chọn thì ghi nhớ để quay lui

@ Nếu trên đỉnh của STACK la kí hiệu bắt đầu và xâu vào là kí hiệu $ thì dừng và bào THÀNH CÔNG

@ Nếu quay lui hết các trường hợp mà không đạt được kí hiệu kết thúc xâu thì dừng và bào THẤT BẠI

-          Ví dụ

Cho văn phạm:      E à E + T       (1)                                E à T                  (4)

E à E * T       (2)                               

T à id             (3)                               Xâu vào: id * id + id

TT

STACK

Xâu vào

Hành động

1

id * id + id $

Gạt

2

Id

* id + id $

Thu gọn (3)

3

T

* id + id $

Thu  gọn (4)

4

E

* id + id $

Gạt

5

E *

id + id $

Gạt

6

E * id

+ id $

Thu gọn (3)

7

E * T

+ id $

Thu gọn (2)

8

E

+ id $

Gạt

9

E +

id $

Gạt

10

E + id

$

Thu gọn (3)

11

E + T

$

Thu gọn (1)

12

E

$

THÀNH CÔNG

Pq

Phân tích LL

-          Thuật toán tính FIRST và FOLLOW

@ Thuật toán tính FIRST(X):  là tập các kí tự kết thúc sao cho a bắt đầu là tiền tố của X

+ Nếu X là kí hiệu kết thúc thì X à FIRST(X)

+ Nếu X à e là một sản xuất thì thêm e à FIRST (X)

+ Nếu X à X1X2...Xn thì FIRST (X1) à FIRST (X). Khi $ (1 < t < n) mà e Î FIRST (X) thì thêm FIRST (Xt+1) à FIRST (X).

@ Thuật toán tính FOLLOW (A): là tập các kí tự kết thúc a sao cho FOLLOW(A) = {a|S àaAab}

+ Nếu A là kí tự bắt đầu thì thêm $ à FOLLOW (A)

+ Nếu B à aAb thì thêm mọi phần tử của FIRST (b) à FOLLOW (A) trừ e

+ Nếu B à aAb hoặc [ B à aAb mà e Î FIRST (b) ] thì FOLLOW (A) = FOLLOW (b)

Ví dụ:

Cho VP:

S à AB

A à aA| e

B à bB | e

Tình FIRST

FIRST

S

a, b, e

A

a, e

B

b, e

Tính FOLLOW

FOLLOW

S

$

A

b, $

B

$

-          Bảng phân tích LL

Kí hiệu M(X,Y) với X tập kí hiệu không kết thúc, Y là tập kí hiệu kết thúc

 Với mỗi sản xuất A à a thực hiện:

            + Với "a Î FIRST (a) thì ta đưa A à a vào M (A, a)

            + Nếu e Î FIRST (a) và "b Î FOLLOW (A) thì đưa A à a vào M (A,b)

            + Nếu e Î FIRST (a) và $ Î FOLLOW (A) thì đưa A à a vào M (A,$)

Điều kiện để là bảng LL(1) là các ô trong bảng phải đơn định

Ví dụ:

Cho VP:

S à AB

A à aA| e

B à bB | e

Xâu: “aabb"

Tình FIRST

FIRST

S

a, b, e

A

a, e

B

b, e

Tính FOLLOW

FOLLOW

S

$

A

b, $

B

$

Bảng phân tích với xâu vào là “aabb”

TT

STACK

Xâu vào

Hoạt động

1

$S

aabb$

S à AB

2

$BA

aabb$

A à aA

3

$BAa

aabb$

Rút gọn

4

$BA

abb$

A à aA

5

$BAa

abb$

RG

6

$BA

bb$

A à e

7

$B

bb$

B à bB

8

$Bb

bb$

RG

9

$B

b$

B à bB

10

$Bb

b$

RG

11

$B

$

B à e

12

$

$

FINISH

 Bảng LL

a

b

$

S

S à AB

S à AB

S à AB

A

A à aA

A à e

A à e

B

B à bB

B à e

-          Phương pháp kiểm tra lỗi trong LL(1)

Nếu M(A,a) = “Error” thì ta xây dựng một tập Syn rồi

+ Đưa mọi phần từ của FIRST (A) vào Syn hoặc đưa mọi phần tử của FOLLOW (A) vào Syn

+ Bỏ qua kí hiệu trên xâu vào hoặc kí hiệu đầu tiên của STACK

Phân tích LR ( Cái này mình ko biết nên ko làm, mọi người tự tìm hiểu nhé J)

Chương 4: Dịch dựa cú pháp

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

-        Với mỗi sản xuất A à a bổ sung vào quy tắc ngữ nghĩa b = f (c1, c2, ..., cn) với b là thuộc tính kế thừa của A và ci là những thuộc tính kế thừa của a hoặc ngược lại

-        Cú pháp điều khiển có 2 thuộc tính đó là kế thừa và tổng hợp

+ Thuộc tính kế thừa: là thuộc tính mà giá trị của nó tại một nút trong cây phân tích được xác định từ các thuộc tính tù cha, các anh, em của nó hoặc kết hợp từ các nút đó. Thuộc tính kế thừa rất thuận tiện để nhấn mạnh sự phụ thuộc của một cấu trúc ngôn ngữ lập trình vào ngữ cảnh mà nó xuất hiện trong đó.

+ Thuộc tính tổng hợp: được dùng rộng rãi trong thực tế. Một định nghĩa cú pháp điều khiển dùng các thuộc tính tổng hợp được gọi riêng là định nghĩa thuộc tính S. Một cây phân tích cho một định nghĩa thuộc tính S có thể luôn được đánh dấu (trang hoàng) bằng đánh giá các luật ngữ nghĩa đối với các thuộc tính tại mỗi nút từ dưới lên, từ lá đến gốc.

Văn phạm định nghĩa cú pháp