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

Cẩm Huỳnh viết ngày 26/09/2016

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).

alt text

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é.

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Cẩm Huỳnh

35 bài viết.
279 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
36 9
(Ảnh) Vì sao lại là Bật Đèn? Ai từng đọc qua Tắt Đèn hẳn đã biết tác phẩm được kết thúc bằng tình huống: Buông tay, chị vội choàng dậy, mở cửa...
Cẩm Huỳnh viết 9 tháng trước
36 9
White
32 25
Vừa rồi mình vừa tiết kiệm được $5 mỗi tháng sau khi migrate cái (Link) từ Digital Ocean sang Heroku Free Dyno. (Ảnh) Kết quả thật mĩ mãn vì hầu ...
Cẩm Huỳnh viết 7 tháng trước
32 25
White
31 4
(Ảnh) Bắt đầu một câu chuyện Vài ngày trước một người bạn nhờ tui xem giùm trang web của nó bị người dùng phàn nàn là hack tiền ảo. Tui mò vào ...
Cẩm Huỳnh viết 4 tháng trước
31 4
Bài viết liên quan
White
3 0
Chú thích: Bài này đăng lần đầu năm 2009 để chia sẻ kinh nghiệm, sau khi tác giả viết xong thư viện closed source để bán. Hiện tại năm 2016 đã có t...
Ngoc Dao viết gần 2 năm trước
3 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
35 bài viết.
279 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!