Ruby Internal - Code Ruby của bạn được thực thi như thế nào (Phần 2)

Về phần 1

Ở phần trước chúng ta đã nghiên cứu về tokenization của ngôn ngữ Ruby, ở phần này chúng ta sẽ đi vào Parsing

Cũng như đã nói ở phần trước, bài này là một trong chuỗi bài #hardcore, vốn là một group học nhóm được thành lập để khuyến khích mọi người tìm hiểu về những vấn đề khó mà trong công việc thường ngày ít chạm phải.

Xem phần 1 tại đây, xem thêm về #hardcore tại đây.

Ruby parsing

Sau khi tokenize đoạn code Ruby của bạn thành một đống token rồi, Ruby sẽ tiến hành parse các token đó thành các câu, cụm có nghĩa với nó.

Như mọi ngôn ngữ khác, Ruby sử dụng một parser generator tên là Bison (có cơ hội mình sẽ viết một bài kĩ hơn về bison).

Như các bạn thấy ở hình trên, Bison sẽ sinh ra parser parse.c thông qua bộ luật được định nghĩa ở parse.y, sau đó parse.c sẽ thực hiện parse code Ruby thành các AST Nodes và biên dịch nó thành byte code, để máy ảo Ruby có thể thực thi.

LALR Algorithm

Ta sẽ tìm hiểu kĩ hơn về thuật toán parsing được sử dụng trong ngôn ngữ Ruby LALR (Look Ahead Left-reserved Right-most deviration, thông qua ví dụ nho nhỏ sau đây.

Giả sử bạn có câu.

Tôi ăn nhưng tôi không làm.

và một bộ luật sau để kiểm tra độ đúng đắn của nó.

(1) Sentence -> Phrase Conjunction Phrase
(2) Phrase -> PositivePhrase | NegativePhrase 
(3) PositivePhrase -> Subject Verb
(4) NegativePhrase -> Subject không Verb
(5) Subject -> "Tôi"
(6) Verb -> "ăn" | "làm"
(7) Conjunction -> "không"

Cách parse câu "Tôi ăn nhưng tôi không làm" theo LALR là như sau:

Cho [] bên trái là một cái grammar stack, ta có

[] | Tôi ăn nhưng tôi không làm

Đầu tiên "Tôi" được cho vào stack

[Tôi] | ăn nhưng tôi không làm

Match "Tôi" với luật (5) ta có

[Subject] | ăn nhưng tôi không làm

Sau đó ta không match với với luật nào tiếp cả, ta đọc token tiếp theo, lúc này token ngay top của stack là "ăn".

[Subject ăn] | nhưng tôi không làm

"ăn sẽ được match với luật (6), và Subject Verb chính là luật (3) PositivePhrase, mà PositivePhrase thì có thể sinh được Phrase

[Subject Verb] | nhưng tôi không làm

[PositivePhrase] | nhưng tôi không làm

[Phrase] | nhưng tôi không làm

Sau đó thì ta không triệt tiêu (derive) được luật nào nữa cả, nên đọc tiếp ta match được "but" với luật (7) Conjunction

[Phrase nhưng] | tôi không làm

[Phrase Conjunction] | tôi không làm

Sau đó là ta tiếp tục match nhanh được "tôi không làm"

[Phrase Conjunction NegativePhrase] | 

[Phrase Conjunction Phrase] |

Và ta có được production mong muốn là luật (1) Sentence, câu "Tôi ăn nhưng không không làm" được chấp thuận với bộ luật trên.

Kết luận

Thật ra bài viết vẫn còn một phần nữa cơ mà vì áp lực nộp bài và một phần là đêm đã khuya nữa, mình xin khất phần còn lại cho một ngày khác nhé.