Ruby Internal - Code Ruby của bạn được thực thi như thế nào (Phần 2)
hardcore
17
Ruby
114
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

40 bài viết.
338 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
39 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 1 năm trước
39 9
White
37 6
Làm thế nào để chỉ với một đoạn text vài trăm ký tự, bạn có thể làm ngốn vài gigabyte bộ nhớ và từ chối dịch vụ của một hệ thống dùng XML? _____ ...
Cẩm Huỳnh viết 4 tháng trước
37 6
White
34 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 12 tháng trước
34 25
Bài viết liên quan
White
10 0
Hadoop là cái gì vậy? “Hadoop là một framework nguồn mở viết bằng Java cho phép phát triển các ứng dụng phân tán có cường độ dữ liệu lớn một cách ...
nguyenduyhao1111 viết gần 2 năm trước
10 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

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


White
{{userFollowed ? 'Following' : 'Follow'}}
40 bài viết.
338 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á!