{"slug":"tu-lexer-den-semantic-analysis-compiler-hieu-ma-nguon-nhu-the-nao","title":"Từ Lexer đến Semantic Analysis: Compiler hiểu mã nguồn như thế nào?","summary":"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.\n\nQuá 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.","excerpt":"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.\n\nQuá 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.","markdown":"# Từ Lexer đến Semantic Analysis: Compiler hiểu mã nguồn như thế nào?\n\nCompiler 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.\n\nQuá 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.\n\nMột pipeline compiler có thể được giản lược như sau:\n\nSource Code\n↓\nLexical Analysis\n↓\nTokens\n↓\nParsing\n↓\nParse Tree / AST\n↓\nSemantic Analysis\n↓\nValidated Representation\n\n\nCá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.\n\n## 1. Compiler làm gì với mã nguồn?\n\nMã nguồn ban đầu là một chuỗi ký tự.\n\nresult = a + b * 2\n\n\nỞ dạng này, compiler chưa thể trực tiếp suy ra toàn bộ cấu trúc của biểu thức. Nó phải xác định:\n\ncác đơn vị từ vựng;\nloại của từng đơn vị;\nquan hệ cú pháp giữa chúng;\ncấu trúc phân cấp của biểu thức;\ncác ràng buộc ngữ nghĩa.\n\nBa tầng cần phân biệt là:\n\nKý tự → Đơn vị → Cấu trúc → Ngữ nghĩa\n\n\nNhận diện đúng các đơn vị không đồng nghĩa với xác định đúng cấu trúc. Xác định được cấu trúc cú pháp cũng không đồng nghĩa với cấu trúc đó hợp lệ về ngữ nghĩa.\n\n\n\n## 2. Token — đơn vị cơ bản của mã nguồn\n\n**Token** là một đơn vị từ vựng được compiler nhận diện trong mã nguồn.\n\nVí dụ:\n\nscore = value + 10\n\n\ncó thể được biểu diễn thành:\n\nIDENTIFIER(\"score\")\nASSIGN(\"=\")\nIDENTIFIER(\"value\")\nPLUS(\"+\")\nINTEGER(10)\n\n\nTrong đó:\n\n| Mã nguồn | Loại token |\n|---|---|\n| `score` | Identifier |\n| `=` | Assignment operator |\n| `value` | Identifier |\n| `+` | Arithmetic operator |\n| `10` | Integer literal |\n\nToken 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.\n\nToken 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ị đó.\n\n\n\n## 3. Lexer và Lexical Analysis — từ ký tự thành token\n\n**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**.\n\nCharacters\n↓\nLexer\n↓\nTokens\n\n\nVí dụ:\n\ntotal = price * 2\n\n\ncó thể được lexer chuyển thành:\n\nIDENTIFIER(\"total\")\nASSIGN\nIDENTIFIER(\"price\")\nMULTIPLY\nINTEGER(2)\n\n\nLexer thường xử lý các loại đơn vị như:\n\nidentifier;\nkeyword;\noperator;\nliteral;\ndelimiter.\n\nLexical analysis không có nhiệm vụ xác định toàn bộ quan hệ cú pháp giữa các token.\n\n**Lexer xác định các đơn vị. Parser xác định cấu trúc giữa các đơn vị.**\n\n\n\n## 4. Grammar — các quy tắc cấu tạo ngôn ngữ\n\n**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.\n\nMột grammar giản lược có thể chứa các production rule:\n\nExpression → Expression + Expression\nExpression → Expression * Expression\nExpression → Identifier\nExpression → Integer\n\n\nKý hiệu:\n\nA → B C\n\n\ncó nghĩa rằng cấu trúc thuộc loại `A` có thể được tạo bởi các thành phần `B` và `C` theo quy tắc tương ứng.\n\nGrammar không chỉ mô tả token nào có thể xuất hiện. Nó mô tả **cách các token hoặc cấu trúc nhỏ hơn kết hợp thành cấu trúc lớn hơn**.\n\nTrong ngôn ngữ lập trình thực tế, grammar còn phải xử lý các vấn đề như precedence, associativity, grouping và nhiều loại cấu trúc khác.\n\n\n\n## 5. Parser — từ chuỗi token đến cấu trúc\n\n**Parser** là thành phần phân tích chuỗi token dựa trên grammar để xác định cấu trúc cú pháp của chương trình.\n\nXét:\n\na + b * c\n\n\nChuỗi token tuyến tính là:\n\na + b * c\n\n\nNhưng cấu trúc của biểu thức có thể là:\n\na + (b * c)\n\n\nBiểu diễn dưới dạng cây:\n\n+\n/ \\\na *\n/ \\\nb c\n\n\nCấu trúc này khác với:\n\n(a + b) * c\n\n\ntương ứng:\n\n*\n/ \\\n+ c\n/ \\\na b\n\n\nParser 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.\n\n\n\n## 6. Parse Tree — cấu trúc tầng bậc của cú pháp\n\n**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.\n\nVới:\n\na + b * c\n\n\nmột parse tree giản lược có thể là:\n\nExpression\n├── Expression\n│ └── Identifier(a)\n├── \"+\"\n└── Expression\n├── Expression\n│ └── Identifier(b)\n├── \"*\"\n└── Expression\n└── Identifier(c)\n\n\nParse tree thể hiện:\n\nthành phần nào kết hợp với thành phần nào;\nchúng tạo thành cấu trúc trung gian nào;\ncấu trúc lớn hơn được hình thành theo thứ bậc nào.\n\nChuỗi tuyến tính:\n\na + b * c\n\n\nvì vậy được chuyển thành cấu trúc phân cấp:\n\n+\n├── a\n└── *\n├── b\n└── c\n\n\n**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.**\n\n\n\n## 7. AST — Abstract Syntax Tree\n\n**Abstract Syntax Tree (AST)** là biểu diễn cây trừu tượng của cấu trúc cú pháp.\n\nAST 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.\n\nVí dụ parse tree:\n\nExpression\n├── Expression\n│ └── Identifier(a)\n├── \"+\"\n└── Expression\n├── Expression\n│ └── Identifier(b)\n├── \"*\"\n└── Expression\n└── Identifier(c)\n\n\ncó thể được rút gọn thành AST:\n\nAdd\n├── Identifier(a)\n└── Multiply\n├── Identifier(b)\n└── Identifier(c)\n\n\nAST giữ lại quan hệ quan trọng:\n\nMultiply(b, c)\n\n\nlà một cấu trúc con của:\n\nAdd(a, ...)\n\n\nCác giai đoạn semantic analysis, optimization hoặc code generation thường làm việc trên AST hoặc những biểu diễn trung gian được xây dựng từ nó.\n\n\n\n## 8. Parse Tree và AST khác nhau thế nào?\n\nParse tree và AST đều biểu diễn cấu trúc phân cấp nhưng có mục đích khác nhau.\n\n| Đặc điểm | Parse Tree | AST |\n|---|---|---|\n| Quan hệ với grammar | Trực tiếp | Trừu tượng hóa |\n| Production trung gian | Thường được giữ | Thường được lược bỏ |\n| Dấu câu và chi tiết cú pháp | Có thể được giữ | Có thể bị loại |\n| Mục tiêu | Biểu diễn quá trình phân tích | Biểu diễn cấu trúc cần xử lý |\n| Mức độ chi tiết | Cao hơn | Thấp hơn |\n\nKhông phải mọi compiler đều xây dựng hai cấu trúc này thành hai giai đoạn vật lý riêng biệt. Một parser có thể trực tiếp tạo AST.\n\n`Parse Tree` và `AST` vì vậy là hai khái niệm liên quan nhưng không đồng nhất.\n\n\n\n## 9. Candidate Parse và Ambiguity — một input, nhiều cách phân tích\n\nMột chuỗi token có thể cho phép nhiều cấu trúc cú pháp nếu grammar không cung cấp đủ điều kiện để xác định duy nhất một cấu trúc.\n\nVí dụ:\n\na + b * c\n\n\ncó hai candidate parse:\n\n(a + b) * c\n\n\nvà:\n\na + (b * c)\n\n\nHai cấu trúc tạo ra hai cây khác nhau và có thể tạo ra hai kết quả khác nhau.\n\nHiện tượng một input có nhiều cách phân tích được gọi là **syntactic ambiguity**.\n\nNgôn ngữ lập trình thường được thiết kế để loại bỏ hoặc kiểm soát ambiguity bằng:\n\nprecedence;\nassociativity;\ndấu ngoặc;\ngrammar design;\ncác quy tắc bổ sung của ngôn ngữ.\n\nMột nguyên tắc quan trọng có thể rút ra:\n\n**Surface form không tự nó xác định đầy đủ cấu trúc bên dưới.**\n\n\n\n## 10. Syntax hợp lệ chưa chắc Semantic hợp lệ\n\nXét biểu thức giả định:\n\n\"hello\" - 5\n\n\nNếu grammar cho phép:\n\nExpression → Expression - Expression\n\n\nparser có thể dựng:\n\nSubtract\n├── String(\"hello\")\n└── Integer(5)\n\n\nCấu trúc này thỏa quy tắc cú pháp của một binary expression.\n\nTuy nhiên, nếu ngôn ngữ chỉ định toán tử `-` cho các kiểu số, phép toán:\n\nString - Integer\n\n\nkhông hợp lệ.\n\nHai kết quả khác nhau:\n\nSyntax: hợp lệ\nSemantic: không hợp lệ\n\n\nParser đã 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.\n\n**Một cấu trúc có thể parse được nhưng vẫn không hợp lệ về ngữ nghĩa.**\n\n\n\n## 11. Semantic Analysis — kiểm tra ngữ nghĩa của cấu trúc\n\n**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.\n\nTùy thiết kế ngôn ngữ, semantic analysis có thể kiểm tra:\n\nidentifier đã được khai báo hay chưa;\nphạm vi của identifier;\nkiểu dữ liệu;\ntính tương thích giữa các kiểu;\ntham số của function;\nkiểu trả về;\nkhả năng áp dụng operator;\ncác ràng buộc ngữ nghĩa khác.\n\nVí dụ:\n\nx: Integer\nx + 10\n\n\ncó thể hợp lệ.\n\nTrong khi:\n\nx: String\nx - 10\n\n\ncó thể không hợp lệ.\n\nHai biểu thức đều có thể có cùng cấu trúc cú pháp tổng quát:\n\nBinaryExpression\n├── LeftOperand\n├── Operator\n└── RightOperand\n\n\nSự 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.\n\n\n\n## 12. Type Checking và Semantic Constraints\n\n**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.\n\nGiả sử:\n\nadd(Int, Int) → Int\n\n\nLời gọi:\n\nadd(1, 2)\n\n\nthỏa yêu cầu:\n\nadd(Int, Int)\n\n\nTrong khi:\n\nadd(\"one\", 2)\n\n\ntạo ra:\n\nadd(String, Int)\n\n\nvà không thỏa signature đã định nghĩa.\n\nCó thể biểu diễn dưới dạng constraint:\n\nExpected:\nadd(Int, Int)\n\nReceived:\nadd(String, Int)\n\nResult:\nType mismatch\n\n\nKhá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.\n\nMộ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ó.\n\n\n\n## 13. Syntax và Semantic khác nhau ở đâu?\n\n**Syntax** mô tả cách các đơn vị được tổ chức thành cấu trúc.\n\n**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 đó.\n\nVí dụ:\n\n\"hello\" - 5\n\n\nSyntax có thể tạo:\n\nSubtract\n├── String\n└── Integer\n\n\nSemantic analysis kiểm tra:\n\nsubtract(String, Integer)\n\n\nvà có thể bác bỏ nó.\n\nCó thể khái quát:\n\nTokens\n↓\nSyntactic Structure\n↓\nSemantic Validation\n\n\nBa tầng này không thay thế lẫn nhau.\n\nNhậ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.\n\n\n\n## 14. Programming Language và Natural Language\n\nNgô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ế.\n\nMộ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:\n\nLanguage Specification\n↓\nGrammar + Semantic Rules\n↓\nValid Programs\n\n\nChương trình được đánh giá dựa trên các quy tắc của ngôn ngữ.\n\nNgô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à:\n\nLanguage Usage\n↓\nObserved Data\n↓\nAnalysis\n↓\nGeneralization\n↓\nGrammatical Model\n\n\nNgườ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ữ.\n\nDữ 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.\n\nVì 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ữ**.\n\n\n\n## 15. Tại sao Parser và Semantic Analysis hữu ích khi nghiên cứu ngữ pháp tự nhiên?\n\nCá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 đề:\n\nNhận diện đơn vị\n↓\nXác định cấu trúc\n↓\nKiểm tra quan hệ ngữ nghĩa\n\n\nBa vấn đề này cũng xuất hiện trong phân tích ngôn ngữ tự nhiên.\n\nMộ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.\n\nPhép đối chiếu này không đồng nhất:\n\nNatural Language = Programming Language\n\n\nvà cũng không đồng nhất:\n\nPhân tích ngữ pháp = Compiler\n\n\nNó chỉ cung cấp một hệ thuật ngữ và mô hình hình thức để phân biệt **đơn vị, cấu trúc và ngữ nghĩa**.\n\n\n\n## 16. Tổng kết: Token → Structure → Meaning\n\nQuá trình được trình bày trong bài có thể rút gọn thành:\n\nSource\n↓\nLexer\n↓\nTokens\n↓\nParser\n↓\nParse Tree / AST\n↓\nSemantic Analysis\n↓\nValidated Representation\n\n\nBa tầng quan trọng nhất là:\n\nToken\n↓\nStructure\n↓\nMeaning / Constraints\n\n\n**Lexer** xác định các đơn vị từ vựng.\n\n**Parser** xác định cấu trúc phân cấp giữa các đơn vị.\n\n**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.\n\nMộ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.\n\n\n\n## 17. Đọc tiếp: Từ Parser đến 层次分析\n\nBà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:\n\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**\n\nTrọng tâm gồm:\n\nPattern\n↓\nCandidate Structure\n↓\nHierarchical Analysis\n↓\nSemantic Relations\n\n\nvớ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**.","html":"

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

Ở dạng này, compiler chưa thể trực tiếp suy ra toàn bộ cấu trúc của biểu thức. Nó phải xác định:

Ba tầng cần phân biệt là:

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

Nhận diện đúng các đơn vị không đồng nghĩa với xác định đúng cấu trúc. Xác định được cấu trúc cú pháp cũng không đồng nghĩa với cấu trúc đó hợp lệ về ngữ nghĩa.

2. Token — đơn vị cơ bản của mã nguồn

Token là một đơn vị từ vựng được compiler nhận diện trong mã nguồn.

Ví dụ:

score = value + 10

có thể được biểu diễn thành:

IDENTIFIER(\"score\")
ASSIGN"="
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

có thể được lexer chuyển thành:

IDENTIFIER(\"total\")
ASSIGN
IDENTIFIER(\"price\")
MULTIPLY
INTEGER(2)

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

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

có nghĩa rằng cấu trúc thuộc loại A có thể được tạo bởi các thành phần B và C theo quy tắc tương ứng.

Grammar không chỉ mô tả token nào có thể xuất hiện. Nó mô tả cách các token hoặc cấu trúc nhỏ hơn kết hợp thành cấu trúc lớn hơn.

Trong ngôn ngữ lập trình thực tế, grammar còn phải xử lý các vấn đề như precedence, associativity, grouping và nhiều loại cấu trúc khác.

5. Parser — từ chuỗi token đến cấu trúc

Parser là thành phần phân tích chuỗi token dựa trên grammar để xác định cấu trúc cú pháp của chương trình.

Xét:

a + b * c

Chuỗi token tuyến tính là:

a  +  b  *  c

Nhưng cấu trúc của biểu thức có thể là:

a + (b * c)

Biểu diễn dưới dạng cây:

      +
     / \\
    a   *
       / \\
      b   c

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

(a + b) * c

tương ứng:

        *
       / \\
      +   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

một parse tree giản lược có thể là:

Expression
├── Expression
│   └── Identifiera
├── \"+\"
└── Expression
    ├── Expression
    │   └── Identifierb
    ├── \"*\"
    └── Expression
        └── Identifierc

Parse tree thể hiện:

  1. thành phần nào kết hợp với thành phần nào;
  2. chúng tạo thành cấu trúc trung gian nào;
  3. 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

vì vậy được chuyển thành cấu trúc phân cấp:

+
├── 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)

là một cấu trúc con của:

Add(a, ...)

Các giai đoạn semantic analysis, optimization hoặc code generation thường làm việc trên AST hoặc những biểu diễn trung gian được xây dựng từ nó.

8. Parse Tree và AST khác nhau thế nào?

Parse tree và AST đều biểu diễn cấu trúc phân cấp nhưng có mục đích khác nhau.

| Đặc điểm | Parse Tree | AST |

|---|---|---|

| Quan hệ với grammar | Trực tiếp | Trừu tượng hóa |

| Production trung gian | Thường được giữ | Thường được lược bỏ |

| Dấu câu và chi tiết cú pháp | Có thể được giữ | Có thể bị loại |

| Mục tiêu | Biểu diễn quá trình phân tích | Biểu diễn cấu trúc cần xử lý |

| Mức độ chi tiết | Cao hơn | Thấp hơn |

Không phải mọi compiler đều xây dựng hai cấu trúc này thành hai giai đoạn vật lý riêng biệt. Một parser có thể trực tiếp tạo AST.

Parse Tree và AST vì vậy là hai khái niệm liên quan nhưng không đồng nhất.

9. Candidate Parse và Ambiguity — một input, nhiều cách phân tích

Một chuỗi token có thể cho phép nhiều cấu trúc cú pháp nếu grammar không cung cấp đủ điều kiện để xác định duy nhất một cấu trúc.

Ví dụ:

a + b * c

có hai candidate parse:

(a + b) * c

và:

a + (b * c)

Hai cấu trúc tạo ra hai cây khác nhau và có thể tạo ra hai kết quả khác nhau.

Hiện tượng một input có nhiều cách phân tích được gọi là syntactic ambiguity.

Ngôn ngữ lập trình thường được thiết kế để loại bỏ hoặc kiểm soát ambiguity bằng:

Một nguyên tắc quan trọng có thể rút ra:

Surface form không tự nó xác định đầy đủ cấu trúc bên dưới.

10. Syntax hợp lệ chưa chắc Semantic hợp lệ

Xét biểu thức giả định:

\"hello\" - 5

Nếu grammar cho phép:

Expression → Expression - Expression

parser có thể dựng:

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

không hợp lệ.

Hai kết quả khác nhau:

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:

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

Lời gọi:

add(1, 2)

thỏa yêu cầu:

add(Int, Int)

Trong khi:

add(\"one\", 2)

tạo ra:

add(String, Int)

và không thỏa signature đã định nghĩa.

Có thể biểu diễn dưới dạng constraint:

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

Syntax có thể tạo:

Subtract
├── String
└── Integer

Semantic analysis kiểm tra:

subtract(String, Integer)

và có thể bác bỏ nó.

Có thể khái quát:

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

và cũng không đồng nhất:

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

Nó chỉ cung cấp một hệ thuật ngữ và mô hình hình thức để phân biệt đơn vị, cấu trúc và ngữ nghĩa.

16. Tổng kết: Token → Structure → Meaning

Quá trình được trình bày trong bài có thể rút gọn thành:

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.

","tags":[],"author":"virgoricomp_102605","publishedAt":"2026-09-27T20:03:16.850Z","updatedAt":"2026-09-27T23:09:02.836Z","published_at":"2026-09-27T20:03:16.850Z","updated_at":"2026-09-27T23:09:02.836Z","view_count":10,"canonical":"https://wiki.quizzman.com/wiki/tu-lexer-den-semantic-analysis-compiler-hieu-ma-nguon-nhu-the-nao","url":"https://wiki.quizzman.com/wiki/tu-lexer-den-semantic-analysis-compiler-hieu-ma-nguon-nhu-the-nao","markdownUrl":"https://wiki.quizzman.com/api/articles/tu-lexer-den-semantic-analysis-compiler-hieu-ma-nguon-nhu-the-nao.md","apiUrl":"https://wiki.quizzman.com/api/articles/tu-lexer-den-semantic-analysis-compiler-hieu-ma-nguon-nhu-the-nao"}