Thiết kế trình biên dịch - Phân tích ngữ nghĩa

Chúng ta đã học cách trình phân tích cú pháp xây dựng cây phân tích cú pháp trong giai đoạn phân tích cú pháp. Cây phân tích cú pháp đơn giản được xây dựng trong giai đoạn đó thường không sử dụng cho trình biên dịch, vì nó không mang bất kỳ thông tin nào về cách đánh giá cây. Việc tạo ra ngữ pháp không có ngữ cảnh, tạo ra các quy tắc của ngôn ngữ, không phù hợp với cách diễn giải chúng.

Ví dụ

E → E + T

Việc sản xuất CFG ở trên không có quy tắc ngữ nghĩa đi kèm với nó, và nó không thể giúp ích cho việc tạo ra bất kỳ ý nghĩa nào cho việc sản xuất.

Ngữ nghĩa

Ngữ nghĩa của một ngôn ngữ cung cấp ý nghĩa cho các cấu trúc của nó, như mã thông báo và cấu trúc cú pháp. Ngữ nghĩa học giúp giải thích các ký hiệu, kiểu của chúng và mối quan hệ của chúng với nhau. Phân tích ngữ nghĩa đánh giá liệu cấu trúc cú pháp được xây dựng trong chương trình nguồn có thu được bất kỳ ý nghĩa nào hay không.

CFG + semantic rules = Syntax Directed Definitions

Ví dụ:

int a = “value”;

không nên đưa ra lỗi trong giai đoạn phân tích từ vựng và cú pháp, vì nó đúng về mặt từ vựng và cấu trúc, nhưng nó sẽ tạo ra lỗi ngữ nghĩa vì kiểu của bài tập khác nhau. Các quy tắc này được đặt ra bởi ngữ pháp của ngôn ngữ và được đánh giá trong phân tích ngữ nghĩa. Các tác vụ sau cần được thực hiện trong phân tích ngữ nghĩa:

• Độ phân giải phạm vi
• Loại kiểm tra
• Kiểm tra giới hạn mảng

Lỗi ngữ nghĩa

Chúng tôi đã đề cập đến một số lỗi ngữ nghĩa mà trình phân tích ngữ nghĩa dự kiến ​​sẽ nhận ra:

• Loại không phù hợp
• Biến không được khai báo
• Sử dụng sai mã định danh dành riêng.
• Khai báo nhiều biến trong một phạm vi.
• Truy cập một biến ngoài phạm vi.
• Thực tế và thông số chính thức không khớp.

Ngữ pháp thuộc tính

Ngữ pháp thuộc tính là một dạng ngữ pháp không có ngữ cảnh đặc biệt, trong đó một số thông tin bổ sung (thuộc tính) được nối vào một hoặc nhiều đầu cuối không phải của nó để cung cấp thông tin nhạy cảm theo ngữ cảnh. Mỗi thuộc tính có miền giá trị được xác định rõ ràng, chẳng hạn như số nguyên, số float, ký tự, chuỗi và biểu thức.

Ngữ pháp thuộc tính là một phương tiện để cung cấp ngữ nghĩa cho ngữ pháp không có ngữ cảnh và nó có thể giúp xác định cú pháp và ngữ nghĩa của một ngôn ngữ lập trình. Ngữ pháp thuộc tính (khi được xem như một cây phân tích cú pháp) có thể chuyển các giá trị hoặc thông tin giữa các nút của cây.

Example:

E → E + T { E.value = E.value + T.value }

Phần bên phải của CFG chứa các quy tắc ngữ nghĩa chỉ định cách diễn giải ngữ pháp. Ở đây, các giá trị của không phải đầu cuối E và T được cộng lại với nhau và kết quả được sao chép vào đầu cuối E.

Các thuộc tính ngữ nghĩa có thể được gán cho các giá trị của chúng từ miền của chúng tại thời điểm phân tích cú pháp và đánh giá tại thời điểm gán hoặc điều kiện. Dựa trên cách các thuộc tính nhận được giá trị của chúng, chúng có thể được chia thành hai loại: thuộc tính tổng hợp và thuộc tính kế thừa.

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

Các thuộc tính này nhận giá trị từ các giá trị thuộc tính của các nút con của chúng. Để minh họa, giả sử sản xuất sau:

S → ABC

Nếu S đang nhận các giá trị từ các nút con của nó (A, B, C), thì nó được cho là một thuộc tính tổng hợp, vì các giá trị của ABC được tổng hợp thành S.

Như trong ví dụ trước của chúng ta (E → E + T), nút cha E nhận giá trị từ nút con của nó. Các thuộc tính tổng hợp không bao giờ nhận giá trị từ các nút cha của chúng hoặc bất kỳ nút anh em nào.

Thuộc tính kế thừa

Ngược lại với các thuộc tính tổng hợp, các thuộc tính được kế thừa có thể lấy giá trị từ cha mẹ và / hoặc anh chị em. Như trong sản xuất sau,

S → ABC

A có thể nhận giá trị từ S, B và C. B có thể nhận giá trị từ S, A và C. Tương tự như vậy, C có thể nhận giá trị từ S, A và B.

Expansion : Khi một không phải đầu cuối được mở rộng thành các đầu cuối theo quy tắc ngữ pháp

Reduction: Khi một đầu cuối được giảm xuống không phải đầu cuối tương ứng của nó theo quy tắc ngữ pháp. Cây cú pháp được phân tích cú pháp từ trên xuống và từ trái sang phải. Bất cứ khi nào việc giảm xảy ra, chúng tôi áp dụng các quy tắc ngữ nghĩa tương ứng (hành động) của nó.

Phân tích ngữ nghĩa sử dụng Bản dịch theo hướng cú pháp để thực hiện các nhiệm vụ trên.

Bộ phân tích ngữ nghĩa nhận AST (Cây cú pháp trừu tượng) từ giai đoạn trước của nó (phân tích cú pháp).

Bộ phân tích ngữ nghĩa đính kèm thông tin thuộc tính với AST, được gọi là AST thuộc tính.

Các thuộc tính là hai bộ giá trị, <tên thuộc tính, giá trị thuộc tính>

Ví dụ:

int value  = 5;
<type, “integer”>
<presentvalue, “5”>

Đối với mỗi sản phẩm, chúng tôi đính kèm một quy tắc ngữ nghĩa.

SDT được phân bổ cho S

Nếu một SDT chỉ sử dụng các thuộc tính tổng hợp, nó được gọi là SDT phân bổ S. Các thuộc tính này được đánh giá bằng cách sử dụng các SDT được phân bổ S có các hành động ngữ nghĩa của chúng được viết sau khi sản xuất (phía bên phải).

Như được mô tả ở trên, các thuộc tính trong SDT do S phân bổ được đánh giá trong phân tích cú pháp từ dưới lên, vì giá trị của các nút cha phụ thuộc vào giá trị của các nút con.

SDT được phân bổ L

Dạng SDT này sử dụng cả thuộc tính tổng hợp và thuộc tính kế thừa với hạn chế là không lấy giá trị từ các anh chị em cùng phải.

Trong SDT được phân bổ L, một thiết bị đầu cuối không phải là thiết bị đầu cuối có thể nhận các giá trị từ các nút cha, con và anh chị em của nó. Như trong sản xuất sau

S → ABC

S có thể nhận giá trị từ A, B và C (tổng hợp). A chỉ có thể nhận các giá trị từ S. B có thể nhận các giá trị từ S và A. C có thể nhận các giá trị từ S, A và B. Không có đầu cuối nào có thể nhận các giá trị từ phần tử anh em bên phải của nó.

Các thuộc tính trong SDT do L phân bổ được đánh giá theo cách phân tích cú pháp theo chiều sâu từ trái sang phải.

Chúng tôi có thể kết luận rằng nếu một định nghĩa được quy cho S, thì nó cũng được quy cho L vì định nghĩa được quy cho L bao gồm các định nghĩa được quy cho S.