Từ Lexer đến Semantic Analysis: Compiler hiểu mã nguồn như thế nào?

Compiler là chương trình chuyển đổi mã nguồn từ một biểu diễn sang một biểu diễn khác, thường từ ngôn ngữ lập trình bậc cao sang mã máy, assembly, bytecode hoặc một dạng biểu diễn trung gian.

Quá trình biên dịch không chỉ là phép thay thế văn bản. Mã nguồn phải được nhận diện thành các đơn vị từ vựng, tổ chức thành cấu trúc cú pháp và kiểm tra các ràng buộc ngữ nghĩa.

Một pipeline compiler có thể được giản lược như sau:

Source Code

↓

Lexical Analysis

↓

Tokens

↓

Parsing

↓

Parse Tree / AST

↓

Semantic Analysis

↓

Validated Representation

Các compiler thực tế có thể chia nhỏ, hợp nhất hoặc bổ sung nhiều giai đoạn khác. Mô hình trên chỉ biểu diễn các tầng cần thiết cho phạm vi bài viết.

1. Compiler làm gì với mã nguồn?

Mã nguồn ban đầu là một chuỗi ký tự.

result = a + b * 2

Ký tự → Đơn vị → Cấu trúc → Ngữ nghĩa

score = value + 10

IDENTIFIER("score")

ASSIGN&quot;=&quot;

IDENTIFIER("value")

PLUS("+")

INTEGER(10)

Trong đó:

| Mã nguồn | Loại token |

|---|---|

| score | Identifier |

| = | Assignment operator |

| value | Identifier |

| + | Arithmetic operator |

| 10 | Integer literal |

Token không nhất thiết tương ứng với một ký tự. score gồm nhiều ký tự nhưng tạo thành một token duy nhất.

Token chủ yếu cung cấp thông tin về loại đơn vị, chưa xác định đầy đủ vai trò cấu trúc của đơn vị đó.

3. Lexer và Lexical Analysis — từ ký tự thành token

Lexical Analysis là quá trình phân tích chuỗi ký tự của mã nguồn thành các token. Thành phần thực hiện quá trình này thường được gọi là lexer hoặc lexical analyzer.

Characters

↓

Lexer

↓

Tokens

Ví dụ:

total = price * 2

IDENTIFIER("total")

ASSIGN

IDENTIFIER("price")

MULTIPLY

INTEGER(2)

Lexer thường xử lý các loại đơn vị như:

identifier;
keyword;
operator;
literal;
delimiter.

Lexical analysis không có nhiệm vụ xác định toàn bộ quan hệ cú pháp giữa các token.

Lexer xác định các đơn vị. Parser xác định cấu trúc giữa các đơn vị.

4. Grammar — các quy tắc cấu tạo ngôn ngữ

Grammar là hệ thống quy tắc hình thức mô tả cách các cấu trúc hợp lệ của một ngôn ngữ có thể được tạo thành.

Một grammar giản lược có thể chứa các production rule:

Expression → Expression + Expression

Expression → Expression * Expression

Expression → Identifier

Expression → Integer

Ký hiệu:

A → B C

a + b * c

a + (b * c)

/ \

a *

/ \

b c

Cấu trúc này khác với:

(a + b) * c

/ \

+ c

/ \

a b

Parser vì vậy không chỉ nhận diện sự xuất hiện của a, +, b, *, c. Nó xác định quan hệ phân cấp giữa chúng.

6. Parse Tree — cấu trúc tầng bậc của cú pháp

Parse Tree là cây biểu diễn cách một chuỗi token được phân tích theo các production rule của grammar.

Với:

a + b * c

Expression

├── Expression

│ └── Identifiera

├── "+"

└── Expression

├── Expression

│ └── Identifierb

├── "*"

└── Expression

└── Identifierc

Parse tree thể hiện:

thành phần nào kết hợp với thành phần nào;
chúng tạo thành cấu trúc trung gian nào;
cấu trúc lớn hơn được hình thành theo thứ bậc nào.

Chuỗi tuyến tính:

a + b * c

├── a

└── *

├── b

└── c

Thứ tự tuyến tính và cấu trúc tầng bậc là hai loại thông tin khác nhau.

7. AST — Abstract Syntax Tree

Abstract Syntax Tree $AST$ là biểu diễn cây trừu tượng của cấu trúc cú pháp.

AST thường loại bỏ những node hoặc chi tiết chỉ cần thiết cho quá trình parsing nhưng không cần thiết cho các giai đoạn xử lý tiếp theo.

Ví dụ parse tree:

Expression

├── Expression

│ └── Identifiera

├── "+"

└── Expression

├── Expression

│ └── Identifierb

├── "*"

└── Expression

└── Identifierc

có thể được rút gọn thành AST:

Add

├── Identifiera

└── Multiply

├── Identifierb

└── Identifierc

AST giữ lại quan hệ quan trọng:

Multiply(b, c)

Add(a, ...)

a + b * c

(a + b) * c

a + (b * c)

"hello" - 5

Expression → Expression - Expression

Subtract

├── String("hello")

└── Integer(5)

Cấu trúc này thỏa quy tắc cú pháp của một binary expression.

Tuy nhiên, nếu ngôn ngữ chỉ định toán tử - cho các kiểu số, phép toán:

String - Integer

Syntax: hợp lệ

Semantic: không hợp lệ

Parser đã hoàn thành nhiệm vụ của nó. Lỗi chỉ xuất hiện khi hệ thống kiểm tra các ràng buộc nằm ngoài cấu trúc cú pháp đơn thuần.

Một cấu trúc có thể parse được nhưng vẫn không hợp lệ về ngữ nghĩa.

11. Semantic Analysis — kiểm tra ngữ nghĩa của cấu trúc

Semantic Analysis là giai đoạn kiểm tra các thuộc tính và ràng buộc ngữ nghĩa của cấu trúc đã được phân tích cú pháp.

Tùy thiết kế ngôn ngữ, semantic analysis có thể kiểm tra:

identifier đã được khai báo hay chưa;
phạm vi của identifier;
kiểu dữ liệu;
tính tương thích giữa các kiểu;
tham số của function;
kiểu trả về;
khả năng áp dụng operator;
các ràng buộc ngữ nghĩa khác.

Ví dụ:

x: Integer

x + 10

có thể hợp lệ.

Trong khi:

x: String

x - 10

có thể không hợp lệ.

Hai biểu thức đều có thể có cùng cấu trúc cú pháp tổng quát:

BinaryExpression

├── LeftOperand

├── Operator

└── RightOperand

Sự khác biệt nằm ở các thuộc tính và quan hệ ngữ nghĩa của những node bên trong.

12. Type Checking và Semantic Constraints

Type checking là quá trình kiểm tra một biểu thức hoặc thao tác có tương thích với các kiểu dữ liệu liên quan hay không.

Giả sử:

add(Int, Int) → Int

add(1, 2)

add(Int, Int)

add("one", 2)

add(String, Int)

Expected:

add(Int, Int)

Received:

add(String, Int)

Result:

Type mismatch

Khái niệm tổng quát hơn là semantic constraint: một cấu trúc chỉ hợp lệ khi các thành phần của nó đáp ứng những điều kiện ngữ nghĩa nhất định.

Một node vì vậy có thể xuất hiện tại vị trí được grammar cho phép nhưng vẫn không đáp ứng constraint của cấu trúc chứa nó.

13. Syntax và Semantic khác nhau ở đâu?

Syntax mô tả cách các đơn vị được tổ chức thành cấu trúc.

Semantic xác định các thuộc tính, quan hệ và ràng buộc có ý nghĩa trên cấu trúc đó.

Ví dụ:

"hello" - 5

Subtract

├── String

└── Integer

Semantic analysis kiểm tra:

subtract(String, Integer)

Tokens

↓

Syntactic Structure

↓

Semantic Validation

Ba tầng này không thay thế lẫn nhau.

Nhận diện token không đủ để xác định cấu trúc. Xác định cấu trúc không đủ để xác nhận ngữ nghĩa.

14. Programming Language và Natural Language

Ngôn ngữ lập trình và ngôn ngữ tự nhiên không hình thành theo cùng một cơ chế.

Một ngôn ngữ lập trình thường có specification hoặc tập quy tắc được xác định trước:

Language Specification

↓

Grammar + Semantic Rules

↓

Valid Programs

Chương trình được đánh giá dựa trên các quy tắc của ngôn ngữ.

Ngôn ngữ tự nhiên không vận hành theo chiều này. Một mô hình giản lược phù hợp hơn là:

Language Usage

↓

Observed Data

↓

Analysis

↓

Generalization

↓

Grammatical Model

Người nói không cần một grammar do nhà ngôn ngữ học viết ra trước khi sử dụng ngôn ngữ. Grammar trong nghiên cứu ngôn ngữ học chủ yếu là kết quả của việc quan sát, mô tả và khái quát các hiện tượng ngôn ngữ.

Dữ liệu lịch sử cũng không hoàn chỉnh. Một cấu trúc có thể đã tồn tại trong khẩu ngữ trước khi được ghi nhận trong văn bản. Chứng cứ sớm nhất còn lại không nhất thiết là thời điểm cấu trúc đó xuất hiện.

Vì vậy, grammar của một programming language mang tính quy định hệ thống theo specification, trong khi grammar mô tả của ngôn ngữ tự nhiên chủ yếu là mô hình được xây dựng từ dữ liệu ngôn ngữ.

15. Tại sao Parser và Semantic Analysis hữu ích khi nghiên cứu ngữ pháp tự nhiên?

Các khái niệm của compiler cung cấp một mô hình đối chiếu để phân biệt ba vấn đề:

Nhận diện đơn vị

↓

Xác định cấu trúc

↓

Kiểm tra quan hệ ngữ nghĩa

Ba vấn đề này cũng xuất hiện trong phân tích ngôn ngữ tự nhiên.

Một chuỗi từ có thể cho phép nhiều cách phân tầng. Một cấu trúc có thể phù hợp với một pattern hình thức nhưng không bảo toàn quan hệ ngữ nghĩa của phát ngôn. Một thành phần cũng có thể phù hợp với một vị trí cú pháp nhưng không đáp ứng yêu cầu ngữ nghĩa của thành phần khác.

Phép đối chiếu này không đồng nhất:

Natural Language = Programming Language

Phân tích ngữ pháp = Compiler

Source

↓

Lexer

↓

Tokens

↓

Parser

↓

Parse Tree / AST

↓

Semantic Analysis

↓

Validated Representation

Ba tầng quan trọng nhất là:

Token

↓

Structure

↓

Meaning / Constraints

Lexer xác định các đơn vị từ vựng.

Parser xác định cấu trúc phân cấp giữa các đơn vị.

Semantic Analysis kiểm tra các thuộc tính và ràng buộc ngữ nghĩa của cấu trúc.

Một pattern có thể tạo ra một candidate structure. Candidate structure không tự động trở thành một phân tích hợp lệ chỉ vì nó có thể được biểu diễn dưới dạng cây.

17. Đọc tiếp: Từ Parser đến 层次分析

Bài tiếp theo đối chiếu các khái niệm trên với phân tích ngữ pháp ngôn ngữ tự nhiên:

Từ Parser đến 层次分析: Cấu trúc cú pháp và quan hệ ngữ nghĩa trong phân tích ngữ pháp

Trọng tâm gồm:

Pattern

↓

Candidate Structure

↓

Hierarchical Analysis

↓

Semantic Relations

với các cấu trúc tiếng Hán dùng để phân biệt khả năng tạo thành một cụm về hình thức và quan hệ ngữ nghĩa thực sự giữa các thành phần.