Cucumber với Erlang, hay câu chuyện về Leex và Yecc
Erlang
12
cucumber
2
compiler
9
White

Ngoc Dao viết ngày 20/03/2016

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ó thư viện open source xử lí cú pháp của Cucumber.

Biết cách tạo DSL có thể giúp tăng năng suất lên rất cao. Đối với nhiệm vụ chuyên biệt, thay vì viết code bằng ngôn ngữ tổng quát (general-purpose), bạn có thể tự tạo ngôn ngữ chuyên biệt giúp giải quyết nhiệm vụ thật hiệu quả. Ví dụ NASA tự tạo DSL để cải thiện độ tin cậy, giảm rủi ro, giảm chi phí, và tăng tốc độ phát triển. Ngay máy tính dẫn đường cho Apollo từ thập niên 1960 đã dùng đã dùng DSL để hỗ trợ việc tính toán vector.

Phần mềm chẳng qua chỉ là tập hợp các tính năng. BDD là phương pháp phát triển đang trở nên phổ biến do phần mềm thu được vừa đạt chất lượng cao mà những người tham gia dự án lại vừa thấy thoải mái. Scenario là chiêu thức rất độc đáo của BDD. Ruby có thư viện giúp viết scenario cực hay là Cucumber, nó cho phép diễn tả requirement của dự án bằng DSL dưới dạng plain text. Ví dụ dưới đây là tập tin login.feature miêu tả tính năng login:

Feature: Login
Scenario: Correct username/password
Given correct username joe
And password secret
When login
Then login would be seccessful

Erlang hiện chưa có thư viện như kiểu này. Bài viết này trình bày đầu tiên khái niệm về DSL và trình biên dịch nói chung, sau đó cách viết trình biên dịch cho DSL của Cucumber cho Erlang bằng Leex và Yecc nói riêng. Leex và Yecc là biến thể cho Erlang của 2 công cụ cực kì nổi tiếng là LexYacc. Hầu hết ngôn ngữ đều có thư viện biến thể của Lex và Yacc cho riêng mình, nên ngay cả khi bạn không dùng Erlang, đọc xong bài viết này có thể bạn cũng áp dụng điều học được lên ngôn ngữ mình thích.

DSL là gì?

DSL hiện đang là "mốt" nhờ được Ruby quảng bá giúp. Sau khi xem Ruby biểu diễn, nhiều người mới thấy sáng tác ra ngôn ngữ mới và viết trình biên dịch cho nó hóa ra cũng không khó, với một chút cố gắng, bạn cũng có thể làm được.

Hãy hình dung như sau:

  • Bạn đang lập trình bằng ngôn ngữ X.
  • Bạn muốn diễn tả cấu trúc S gì đó (domain specific), nhưng nếu dùng cú pháp bình thường của X thì sẽ phải viết thành cục SX gì đó rất dài dòng. S có thể là data, code, hoặc cả 2.
  • Bạn tự nghĩ ra ngôn ngữ L có cú pháp đặc biệt cho phép diễn tả S bằng cục SL ngắn gọn hơn. Chú ý: SX và SL chỉ là 2 hình thức khác nhau để diễn tả cùng ý nghĩa.
  • Bạn muốn viết trình biên dịch cho X để X hiểu được cục SL.

DSL là thuật ngữ để chỉ ngôn ngữ chuyên biệt cho phép diễn tả cấu trúc chuyên biệt gì đó một cách ngắn gọn, mà nếu diễn tả cấu trúc chuyên biệt đó một cách bình thường thì sẽ dài dòng. Có thể hiểu DSL là ngôn ngữ được tạo ra để nhúng vào ngôn ngữ khác, trợ giúp cho ngôn ngữ khác.

Có 2 loại DSL, internal và external:

  • Internal: L chỉ là tập con của X (cú pháp của L là cú pháp hợp lệ của X), nên X hiểu được ngay SL. Ruby là ngôn ngữ có nhiều tính năng thích hợp để sáng tác internal DSL, ví dụ nó có proc, lambda và mọi thứ đều là object. Nói chung ngôn ngữ nào càng xoá mờ ranh giới giữa code và data, nghĩa là hàm cũng là biến, thì càng dễ viết DSL.
  • External: L và X là 2 ngôn ngữ hoàn toàn khác nhau, nên X không hiểu được ngay SL. Cần viết thêm trình biên dịch để biến đổi SL thành SX, dạng theo đúng cú pháp của X để nó có thể hiểu.

Mặc dù trong Erlang hàm cũng là biến, nhưng Erlang không có khả năng diễn đạt cao và uyển chuyển như Ruby, nên hơi khó sáng tác internal DSL cho Erlang. Với Erlang, thường người ta chơi kiểu external:

  1. Tự sáng tác ra external DSL sao cho vừa phù hợp với nhu cầu vừa dễ biên dịch.
  2. Lưu chương trình viết bằng DSL thành tập tin mã nguồn ở dạng plain text.
  3. Tự viết trình biên dịch để dịch tập tin đã lưu thành cấu trúc Erlang, để nó có thể hiểu.

Trình biên dịch DSL là gì?

Mã nguồn là cái có cấu trúc. Chương trình là cái có cấu trúc. Về bản chất, nhiệm vụ của trình biên dịch là biến đổi cấu trúc ở dạng này (ví dụ plain text) thành cấu trúc ở dạng khác (ví dụ bytecode cho máy ảo hoặc mã máy thật).

Trường hợp DSL, vì nó được sử dụng theo kiểu nhúng vào chương trình viết bằng ngôn ngữ X, nên chỉ cần biến đổi DSL đến mức trung gian là X mà thôi. Sau khi biến đổi, đối tượng tiếp nhận không phải là X compiler ngay, mà là hàm trong chương trình ta viết. Do đó, yêu cầu quan trọng đối với DSL compiler là tạo ra cấu trúc sao cho hàm của ta càng dễ tiếp nhận/sử dụng càng tốt.

DSL -(DSL compiler)-> X -> (hàm viết bằng X) -> (X compiler)-> bytecode/machine code -> (máy ảo/thật)

Viết trình biên dịch DSL như thế nào?

Do đặc điểm trên, viết trình biên dịch cho DSL đơn giản hơn viết trình biên dịch cho ngôn ngữ bình thường rất nhiều. Wikipedia có hướng dẫn qui trình viết trình biên dịch, với mục đích viết trình biên dịch cho DSL thì đoạn này quan trọng nhất:

  1. Phân tích từ vựng - Chia nhỏ các dòng mã nguồn thành những phần tử nhỏ gọi là thẻ khóa. Mỗi thẻ khóa đại diện cho cho một đơn vị không thể chia nhỏ của ngôn ngữ. Thí dụ: một từ khóa, một kí hiệu nhận dạng hay một tên kí hiệu. Các thẻ khoá có thể nhận biết được bởi việc dùng máy hữu hạn trạng thái. Pha này còn gọi là pha đọc từ ngữ hay pha quét.
  2. Phân tích cú pháp - Nhận diện các cấu trúc cú pháp của mã nguồn. Nó chỉ tập trung lên cấu trúc. Nói cách khác, nó nhận diện trật tự sắp xếp của các thẻ khóa và hiểu cấu trúc thứ bậc trong bộ mã.

Bước 1 là viết lexical analyzer, còn gọi là lexer, scanner, tokenizer. Nó biến đổi cấu trúc có dạng chuỗi kí tự (mảng các kí tự) của tập tin mã nguồn thành cấu trúc có dạng mảng các token. Một token chẳng qua chỉ là một cặp {key, value}. Nghĩa là bước này biến đổi: [kí tự] -> [{key, value}].

Bước 2 là viết parser. Nó biến đổi cấu trúc mảng 1 chiều thành cấu trúc cây gọi là parse tree (chú ý đây chưa phải là AST). Bước này chỉ đơn giản sắp xếp lại cấu trúc 1 chiều thành cấu trúc nhiều chiều (cây là kết hợp của 2 kiểu dữ liệu là tuple và mảng), nghĩa là: [{key, value}] -> {kết hợp của {} và []}.

Chú ý cấu trúc tuple và mảng ở 2 bước trên phải là cấu trúc theo cú pháp của ngôn ngữ X. Xong bước 2 coi như xong 99% công việc vì đã thu được cấu trúc X có thể hiểu. 1% công việc còn lại chỉ là duyệt qua cây, dựa vào cấu trúc của cây để thực hiện hành vi thích hợp.

Viết trình biên dịch cho DSL của Cucumber cho Erlang

Erlang có 2 công cụ ứng với bước 1 là Leex và bước 2 là Yecc. Yecc có sẵn trong thư viện chuẩn của Erlang, Leex chắc cũng sắp được thêm vào. Leex dùng để sinh (generate) ra tokenizer, Yecc dùng để sinh ra parser.

Bạn hoàn toàn có thể tự viết chương trình đọc từng dòng text của tập tin login.feature ở đầu bài viết rồi xử lí thích hợp, không cần dùng thêm bất kì thư viện nào như Leex và Yecc. Tuy nhiên cách này vừa rất không thực dụng vừa không giúp bạn nâng cao kiến thức thêm tẹo nào.

Viết tokenizer

Cucumber có vài từ khoá, ta dùng luật tạo token sau:

  • Gặp cụm kí tự Feature: xxx thì biến đổi thành token {feature_start, xxx}
  • Background: xxx -> {background_start, xxx}
  • Given xxx -> {given, xxx}
  • v.v., chú ý ta phân làm 2 loại token: (1) loại _start là loại nonterminal để đánh dấu (xem bước viết parser) là chỗ này sẽ chứa cấu trúc con bên trong (sẽ dùng mảng để chứa danh sách các con), (2) loại còn lại là loại terminal, không chứa cấu trúc con.

Ta viết luật thành tập tin tokenizer.xrl rồi dùng Leex để sinh ra tokenizer thành tập tin mã nguồn tokenizer.erl. Tập tin .xrl có 3 phần Definitions, Rules, và Erlang code:

  • Rules là chỗ để khai báo luật biến đổi. Mỗi luật có dạng
    pattern của biểu thức chính qui : {token name, dòng xuất hiện, token value}
    Phần bên phải có thể là mã Erlang tuỳ ý, miễn nó trả về tuple theo đúng qui định của Leex (đọc giải thích chi tiết). Chú ý 2 bên dấu : phải có khoảng trắng. Mã Erlang ở bên phải có thể gọi hàm khai báo ở phần Erlang code.
  • Definitions là chỗ khai báo pattern dùng ở phần Rules. Khi một pattern được dùng ở nhiều dòng luật, thay vì viết đi viết lại nó nhiều lần ở phần Rules, có thể khai báo nó một lần duy nhất thành một macro ở phần Definitions.
  • Erlang code là chỗ khai báo hàm tiện ích dùng ở phần Rules.

tokenizer.xrl:

Definitions.

FeatureStart = Feature:.*
BackgroundStart = Background:.*
ScenarioOutline = Scenario\sOutline:.*
Examples = (Examples|Scenarios):.*
ScenarioStart = Scenario:.*
Step = (Given|When|Then|And|But).*
WS = ([\000-\s]|%.*)

Rules.

{FeatureStart} : {token, {feature_start, TokenLine, remove("Feature:", TokenChars)}}.
{BackgroundStart} : {token, {background_start, TokenLine, remove("Background:", TokenChars)}}.
{ScenarioOutline} : {token, {scenario_outline, TokenLine, remove("Scenario Outline:", TokenChars)}}.
{Examples} : {token, {examples, TokenLine, remove("Scenarios:", remove("Examples", TokenChars))}}.
{ScenarioStart} : {token, {scenario_start, TokenLine, remove("Scenario:", TokenChars)}}.
{Step} : {S, D} = remove_for_step(TokenChars),
{token, {S, TokenLine, D}}.
{WS}+ : skip_token.

Erlang code.

%% Returns stripped description for a token.
remove(Prefix, String) ->
Desc = re:replace(String, Prefix ++ "\s*", "", [global, {return, list}]),
strip(Desc).

%% Returns {Step, Description}.
%% Step: given, 'when', then, 'and', but.
remove_for_step(String) ->
Pattern = "^(Given|When|Then|And|But)\s+(.+)\s*",
{match, [Step1, Desc1]} = re:run(String, Pattern, [{capture, all_but_first, list}]),

Step2 = string:to_lower(Step1),
Step3 = list_to_atom(Step2),
Desc2 = strip(Desc1),
{Step3, Desc2}.

strip(String) ->
re:replace(String, "(^\s*|\s*$)", "", [global, {return, list}]).

Dùng hàm leex:file("tokenizer") (không cần viết thêm đuôi .xrl) để Leex tạo ra tập tin tokenizer.erl. Dịch tập tin này sẽ được module tokenizer.

Tokenize thử bằng module Leex vừa tạo:

{ok, Binary} = file:read_file("login.feature"),
Chars = binary_to_list(Binary),
{ok, Tokens, _} = tokenizer:string(Chars).

Sẽ thu được kết quả (and và when là từ khoá của Erlang, nên được biến đổi thành 'and' và 'when'):

{ok,[{feature_start,1,"Login"},
{scenario_start,2,"Correct username/password"},
{given,3,"correct username joe"},
{'and',4,"password secret"},
{'when',5,"login"},
{then,6,"login would be seccessful"}],
6}

Đến đây ta thu được mảng 1 chiều chứa các token. Đây đã là cấu trúc thể hiện bằng Erlang, nên thật ra đến đây đã có thể duyệt qua mảng để xử lí cần thiết. Tuy nhiên ta nếu dùng Yecc generate ra parser để biến đổi tiếp mảng này thành cấu trúc cây thì còn dễ xử lí hơn nữa!

Viết parser

Yecc chỉ làm việc được với đầu vào là mảng chứa tuple 3 phần tử như trên. Phần tử thứ 2 là để nếu tập tin login.feature ta viết sai cú pháp, thì Yecc sẽ báo đúng số dòng để ta sửa.

Yecc là parser generator thuộc loại LALR-1:

  • LA = Look Ahead: cho phép khai báo luật tạo cây dạng x y z, nghĩa là sau token x phải có y, sau y phải có z.
  • LR = Left-to-right, Rightmost derivation: biến đổi theo thứ tự từ trái sang, biến đổi token bên phải ngoài cùng trước đến khi nào không thể biến đổi được nữa.

Parser sinh ra bởi Yecc sẽ dựa vào luật tạo nút do ta khai báo để trồng mảng các token thành cây. Nút nonterminal (xem lại bước viết tokenizer) có thể chứa nút terminal và nút nonterminal khác. Biến đổi một nút là expand nút đó cho đến khi gặp tất cả các nút terminal.

Do đặc tính của DLS của Cucumber, ta cần biến đổi các token 'and' và but thành token given, 'when', hoặc then trước khi truyền mảng các token cho Yecc. Đây là bài tập dành cho độc giả.

Ta viết luật thành tập tin parser.yrl rồi dùng yecc:file("parser.yrl") để sinh ra parser thành tập tin mã nguồn parser.erl. Tập tin .yrl có 5 phần Nonterminals, Terminals, Rootsymbol, luật tạo nút, và Erlang code:

Nonterminals feature background scenarios scenario steps step.

% "and" and "but" have been converted to "given", "'when'", or "then"
Terminals feature_start background_start scenario_start given 'when' then.

Rootsymbol feature.

feature -> feature_start background scenarios : {remove_line(set_category('$1', feature)), '$2', '$3'}.
feature -> feature_start scenarios : {remove_line(set_category('$1', feature)), undefined, '$2'}.

background -> background_start steps : {remove_line(set_category('$1', background)), '$2'}.

scenarios -> scenario : ['$1'].
scenarios -> scenarios scenario : '$1' ++ ['$2'].

scenario -> scenario_start steps : {remove_line(set_category('$1', scenario)), '$2'}.

steps -> step : ['$1'].
steps -> steps step : '$1' ++ ['$2'].

step -> given : remove_line('$1').
step -> 'when' : remove_line('$1').
step -> then : remove_line('$1').

Erlang code.

set_category(Token, Category) ->
setelement(1, Token, Category).

remove_line(Token) ->
{Category, _Line, Desc} = Token,
{Category, Desc}.
  • Nút nonterminal là nút ta khai báo thêm.
  • Token luôn là nút terminal.
  • Rootsymbol là nút gốc của cây.
  • Ở từng dòng luật, phần bên trái luôn là nonterminal, phần ở giữa là thứ tự các nút nó chứa, phần bên phải là giá trị của nút. Những cái '$1', '$2' ở phần bên phải ứng với nút ở phần ở giữa, chú ý phải có dấu nháy đơn.

Chạy thử:

Tokens2 = [
{feature_start,1,"Login"},
{scenario_start,2,"Correct username/password"},
{given,3,"correct username joe"},
{given,4,"password secret"},
{'when',5,"login"},
{then,6,"login would be seccessful"}],
{ok, Structure} = parser:parse(Tokens2).

Sẽ thu được:

{ok,{{feature,"Login"},
undefined,
[{{scenario,"Correct username/password"},
[{given,"correct username joe"},
{given,"password secret"},
{'when',"login"},
{then,"login would be seccessful"}]}]}}

Đến đây cấu trúc Structure thu được rất dễ xử lí tiếp. Hãy so sánh thử với cấu trúc thu được nếu chỉ dùng tokenizer.

Tổng kết

Tiêu đề của 2 mục ở phần trước là viết tokenizer và parser, nhưng thật ra ta chỉ phải viết vài dòng code, còn lại chỉ là các dòng định nghĩa pattern. Chiêu thức dùng công cụ để generate ra tokenizer và parser này quả thật lợi hại!

Hãy tham khảo thêm bài hướng dẫn viết tokenizer và parser cho SQL bằng Leex và Yecc. Sau đó, tìm hiểu tiếp các công cụ phái sinh từ Lex và Yacc.

Phần trên trình bày cách tạo external DSL cho Erlang, nhưng nếu để ý thì sẽ thấy bước viết parser ứng với xử lí đối với internal DSL. Vì chỉ cần kết hợp {} và [] là có thể diễn tả cấu trúc bất kì, nên ta có workflow sau để tạo internal DSL trong Erlang:

  • Nghĩ ra ngôn ngữ có cách thể hiện là cấu trúc kết hợp tuple và mảng, nhưng dễ viết và ngắn gọn, tuy có thể khó xử lí được ngay.
  • Tự viết hàm biến đổi cấu trúc trên thành mảng các tuple tương thích với Yecc.
  • Viết luật tạo nút và truyền mảng cho Yecc, để thu được cây dễ xử lí hơn cấu trúc ban đầu.
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

Ngoc Dao

102 bài viết.
252 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
56 6
Làm thế nào để nâng cấp trang web mà không làm gián đoạn dịch vụ? Đây là câu hỏi phỏng vấn các công ty lớn thường hỏi khi bạn xin vào vị trí làm lậ...
Ngoc Dao viết 2 năm trước
56 6
White
32 0
Bài viết này giải thích sự khác khác nhau giữa hai ngành khoa học máy tính (computer science) và kĩ thuật phần mềm (software engineering), hi vọng ...
Ngoc Dao viết gần 2 năm trước
32 0
White
28 1
Nếu là team leader, giám đốc công ty hay tướng chỉ huy quân đội, vấn đề cơ bản bạn gặp phải là “hướng mọi người đi theo con đường bạn chỉ ra”. Thử...
Ngoc Dao viết gần 2 năm trước
28 1
Bài viết liên quan
White
2 2
Mở đầu Happy New Year Chúc mọi người năm mới vui vẻ, hạnh phúc. Như các bạn cũng biết gần đây XCode5 cùng iOS7 đã được giới thiệu. Đi cùng XCode...
Nghia Le Van viết gần 3 năm trước
2 2
White
11 4
GCC biên dịch một file .c thành file chạy trong 4 Stage. Preprocessing (tiền xử lý), Assembly Code Compiling (diên dịch sang mã Assembly), Machine ...
Phùng Văn Tú viết 1 năm trước
11 4
White
39 5
Dạo này Rust đang nổi lên như một thế lực khiến một hispter như mình không thể không để tâm. Sau vài ngày dig deeper vào Rust, mình cho rằng Rust l...
Thach Le viết 1 năm trước
39 5
{{like_count}}

kipalog

{{ comment_count }}

bình luận

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


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