• Thứ Sáu, 16/09/2016 21:02 (GMT+7)

    Tự tạo bộ phân tích cú pháp bằng JavaCC

    Nguyễn Văn Sơn - Global CyberSoft VN
    (PCWorldVN) JavaCC là một bộ thư viện mã nguồn mở chạy trên nền Java VM được Sun Microsystems tạo ra nhằm hỗ trợ cho các lập trình viên trong quá trình phát triển phần mềm.

    Trong suốt sự nghiệp, hẳn các lập trình viên (LTV) không ít lần phải đối diện với các vấn đề xử lý chuỗi kí tự có cấu trúc phức tạp, hoặc với các bài toán hóc búa như viết một trình thông dịch, trong đó cần xử lý số lượng lớn các lệnh cấp cao do người dùng nhập vào, hoặc thậm chí tự sáng tạo cho riêng mình một ngôn ngữ lập trình mới với một tập hợp những câu lệnh có cú pháp được định trước. Để phục vụ mục đích đó, giải pháp thường được các LTV nghĩ đến đầu tiên là tự viết cho mình một thư viện xử lý chuỗi, kèm theo những thuật toán cắt nối phức tạp và các vấn đề đau đầu như việc tối ưu việc sử dụng bộ nhớ, tăng tốc độ xử lý.

    JavaCC là một bộ thư viện mã nguồn mở chạy trên nền Java VM (từ 1.2 về sau), được Sun Microsystems tạo ra đã giảm một gánh nặng cho các LTV khi tự động hóa hầu hết các công đoạn xử lý và tính toán trên. Một cách đơn giản, LTV chỉ cần định ra một tập hợp các mẫu cú pháp (grammar) theo cấu trúc xác định, và JavaCC sẽ giúp sinh mã nguồn trọn vẹn của một bộ phân tích và bóc tách cú pháp cho bạn (thường được gọi là analyzer và parser), ở dạng ngôn ngữ Java hoặc C/C++.

    Trong bài này, tôi sẽ mô tả cách thức sử dụng JavaCC để xử lý các chuỗi lệnh có cú pháp đơn giản, với hy vọng sẽ giúp các bạn có cái nhìn tổng quát về bộ thư viện tuyệt vời này và áp dụng hiệu quả cho nhu cầu thực tế của mình. Để thuận tiện, tôi sẽ áp dụng Java trong ví dụ kèm theo, trên hệ điều hành Windows.

    Thư viện JavaCC không cần thao tác cài đặt phức tạp, tất cả những gì bạn cần là tải bản JavaCC mới nhất được biên dịch sẵn tại javacc.java.net và giải nén tại một thư mục bạn làm việc. Tôi sẽ tạm đặt nó tại C:\JavaCC-6.0\. Để tiện việc chạy lệnh phân tích và sinh mã nguồn, tôi tạo một batch file có tên "javacc.bat" và bổ sung vào đường dẫn hệ thống (system path) cho nó. Batch file có nội dung như sau:

    java -cp c:\javacc-6.0\bin\lib\javacc.jar javacc %1

    Để kiểm tra xem thao tác cài đặt JavaCC vào hệ thống của bạn đúng hay không, bạn mở cửa sổ lệnh (command prompt) của Windows tại một thư mục bất kì, và nhập vào "javacc". Nếu nội dung hướng dẫn câu lệnh của JavaCC xuất hiện, tức là bạn đã cài đặt đúng. Ngược lại, bạn cần xem lại quá trình cài đặt.

    Giả định phần mềm chúng ta đang phát triển cho phép người dùng soạn các mã lệnh (tạm gọi là script) để điều khiển tự động một tác vụ nào đó. Cụ thể hơn, người dùng cần một tập các tác vụ sau được lặp lại nhiều lần:

    - Chọn một ô nhập (text field) trên màn hình
    - Gõ vào chuỗi "ABC"
    - Nhấn nút "Submit"

    Hãy hình dung trên cửa sổ soạn thảo của phần mềm, người dùng sẽ nhập các dòng script sau:

    [Screen01].[TextBoxA].Select
    [Screen01].[TextBoxA].EnterString("ABC 123")
    [Screen01].[ButtonSubmit].Click

    Yêu cầu là trình soạn thảo phải kiểm tra xem các lệnh trên có đúng cú pháp không và nếu đúng thì cần tách các thông tin để xử lý cho từng lệnh cụ thể. Đến lúc này, ta sẽ cần đến sức mạnh của JavaCC.

    Một trong những điểm có thể gọi là trái tim trong bộ parser của JavaCC là khả năng phân tích các chuỗi kí tự dựa trên các câu ngữ pháp (grammar) bạn cần tổ chức bằng các mẫu Regular expression (tạm gọi là Regex) mà JavaCC gọi là các Regex Production. Tức là, với các mẫu câu lệnh script trên, bạn cần hình dung và định ra một cấu trúc chung, tương tự như việc phân tích một câu văn có chủ ngữ, vị ngữ, động từ... Bộ parser tương lai của bạn hoạt động chính xác và nhanh hay không, hoàn toàn phụ thuộc vào sự hợp lý và tinh tế trong việc sử dụng regex cho các production này. Có hai dạng production trong JavaCC, một là Regex Production, được tổ chức trực tiếp bằng các từ khóa "TOKEN" mà bạn sẽ thấy bên dưới. Thứ hai là dạng BNF Production (Backus–Naur Form Production), cho phép bạn tổ chức các câu ngữ pháp regex trong các hàm Java.

    Để bắt đầu, ta soạn một tập tin văn bản có tên "Keywords.jj" (còn gọi là tập tin grammar) và mô tả các cú pháp lệnh dưới các dạng production ta muốn theo cấu trúc mà JavaCC quy định. JavaCC khuyến khích bạn đặt tên tệp tin grammar này có đuôi .jj, tuy nhiên thực tế bạn có thể đặt với đuôi bất kỳ và lưu tại thư mục bạn làm việc. Hãy xem đoạn ví dụ bên dưới:

    <Mã nguồn toàn bộ file grammar của ví dụ>
    options
    {
    IGNORE_CASE = true;
    //OUTPUT_LANGUAGE="c++";
    }
    
    PARSER_BEGIN(KeywordParser)
    
    public class KeywordParser
    {
    public static void main(String[] args) throws ParseException, TokenMgrError
    {
    KeywordParser parser = new KeywordParser( System.in ) ;
    parser.parseScript();
    }
    }
    PARSER_END(KeywordParser)
    
    SKIP: { "\n" | "\r" | "\r\n" | "\t" }
    
    TOKEN: 
    {	
    <KW_SELECT: "Select" > 
    |<KW_ENTER_STRING:	"EnterString"> 
    |<KW_CLICK: "Click"> 
    |<KW_PREFIX: <OBRACKET><IDENTIFIER><CBRACKET>( (<DOT>) <OBRACKET><IDENTIFIER><CBRACKET>)*>
    }
    
    TOKEN: 
    {
    <#DIGIT: (["0"-"9"])+>
    | <#ALPHABET:	(["a"-"z", "A"-"Z"])+>	
    | <IDENTIFIER:	<ALPHABET>(<ALPHABET>|<DIGIT>|<SPACE>)*>
    | <DOT:	".">
    | <OBRACKET: "[">
    | <CBRACKET: "]">	
    | <OQUOT: "(">
    | <CQUOT: ")">
    | <DQUOT: "\"">
    | <SPACE: " ">
    }
    
    /* main BNF production routine */
    void parseScript() : {} 
    { 
    ( statement() )* 
    <EOF> 
    }
    
    /* detail BNF productions routines */
    void statement() : {}
    {
    { System.out.println("\n=== Start a command ==="); }
    (
    <KW_PREFIX>	{ System.out.println("\tPrefix: " + token.image); }	
    <DOT>
    )
    (
    <KW_SELECT> { System.out.println("\tKeyword: " + token.image); }	
    | <KW_CLICK>	{ System.out.println("\tKeyword: " + token.image); }	
    | 
    ( 
    <KW_ENTER_STRING>	{ System.out.println("\tKeyword: " + token.image); }	
    <OQUOT><DQUOT>
    (
    <IDENTIFIER>	{ System.out.println("\tString: " + token.image); }	
    )
    <DQUOT><CQUOT>
    )
    )
    }
    
    

    Một số thành phần của tập tin grammar trên có ý nghĩa sau:

    - options: nơi thiết lập cấu hình chung cho bộ sinh mã nguồn JavaCC. Ví dụ, khi chỉ định "IGNORE_CASE = true", JavaCC sẽ cho phép phân tích các chuỗi kí tự không phân biệt chữ hoa hay thường. Có một số tùy chọn quan trọng bạn sẽ cần tham khảo, chẳng hạn OUTPUT_LANGUAGE chỉ thị sinh mã Java hay C++, hay UNICODE_INPUT cho phép hỗ trợ phân tích các chuỗi định dạng UNICODE, khi bạn cần hỗ trợ tiếng Việt hay Nhật.

    - PARSER_BEGIN và PARSER_END: JavaCC cần bạn định nghĩa một lớp Java (Java class) chính cho bộ parser, trong đó bạn có thể bổ sung mã Java cho các mục đích riêng, chẳng hạn như tổ chức và lưu trữ dữ liệu có được từ quá trình phân tích và bóc tách các chuỗi. JavaCC sẽ dùng tên class trên để đặt cho các tập tin chứa mã nguồn bộ parser sắp sinh ra.

    PARSER_BEGIN(parser_name)
    . . .
    class parser_name . . . {
    . . .
    }
    . . .
    PARSER_END(parser_name)


    - TOKEN: Nơi định nghĩa các thành phần trong một câu ngữ pháp, các kí tự đặc biệt, chuỗi cố định và các regex production phức tạp hơn. Bạn có thể tập hợp nhiều định nghĩa vào chung một nhóm token, cách nhau bởi dấu "|" (OR trong Java). Vài ví dụ:

    <DOT: ".">: định nghĩa kí tự đặc biệt dấu "."

    <#DIGIT: (["0"-"9"])+>: định nghĩa một chuỗi chỉ chứa các kí tự số từ 0-9, có ít nhất một số. Dấu thăng "#" chỉ định token này chỉ được dùng nội bộ trong các token khác, không dùng trong các hàm Java NBF production (trong đoạn mã nguồn trên, hàm parseScript là một BNF production).

    - SKIP: Nơi định nghĩa các token mà bạn muốn parser bỏ qua trong quá trình phân tích. Ví dụ các kí tự đặc biệt không cần thiết giữa các lệnh, các kí tự xuống dòng...

    - BNF Production: Là một hàm Java định nghĩa một câu có ngữ pháp phức tạp, đồng thời cho phép ta chèn mã nguồn Java giữa các thành phần để thực hiện các thao tác kiểm tra, lưu trữ dữ liệu hoặc thông báo lỗi. Ví dụ hàm “parseScript” như sau:

    void parseScript() : 
    {
    /* bạn có thể khai báo, khởi tạo các biến tùy ý nơi này */
    }
    {
    ( statement() )*
    <EOF>
    }

    Hàm “parseScript” sử dụng regex để mô tả nội dung tập tin script chứa các mã lệnh, trong đó đoạn (....)* chỉ định có thể không có lệnh nào, hoặc nhiều lệnh. Kí hiệu <EOF> được JavaCC định nghĩa sẵn, chỉ định việc kết thúc tập tin script.

    Tiếp tục, để hỗ trợ ba lệnh "Select", "EnterString" và "Click", bạn cần một hàm BNF khác được đặt tên "statement" trong mã ví dụ trên. Hàm "statement" này đại diện cho một cấu trúc lệnh tổng quát bao gồm 2 thành phần chính:

    - Prefix: tức là đoạn "[Screen01].[TextBoxA]". Được định nghĩa bằng token <KW_PREFIX> ở trên.

    - Keyword chính: tức là đoạn có chuỗi chính xác là "Select", "EnterString" và "Click", được định nghĩa bằng 3 token <KW_SELECT>, <KW_CLICK>, <KW_ENTER_STRING>. Giữa prefix và keyword chính được phân cách bởi dấu chấm, tức token <DOT>.


    Khi đã hoàn tất tập tin grammar, chúng ta sẽ tiến hành chạy bộ sinh mã của JavaCC bằng lệnh sau:

    javacc Keywords.jj

    Nếu thành công, bạn sẽ thấy kết quả như hình 1. Nếu gặp lỗi sai cấu trúc tập tin grammar, hoặc các production bạn không đúng, JavaCC sẽ thông báo cho bạn.

    Hình 1

    JavaCC sẽ sinh toàn bộ mã nguồn bộ parser cho bạn, trong các tập tin Java như trong hình 2. Với các mã này, bạn có thể nhúng vào phần mềm Java bạn đang phát triển để sử dụng chức năng parser mong muốn.

    Hình 2

    Trong ví dụ này, chúng ta sẽ kiểm tra khả năng bộ parser mình vừa sinh bằng các script được lưu tạm trong tập tin script.txt với nội dung:

    [Screen01].[TextBoxA].Select
    [Screen01].[TextBoxA].EnterString("ABC 123")
    [Screen01].[ButtonSubmit].Click

    Trước tiên, ta dùng Java để biên dịch các tập tin Java vừa sinh ở trên:

    javac *.java

    Nếu trong tập tin grammar trên có các lỗi liên quan đến mã Java mà bạn nhúng kèm, bước này sẽ thông báo cụ thể cho bạn.

    Cuối cùng, bạn chạy thử bộ parser mới để kiểm tra các lệnh trong script.txt:

    java KeywordParser < script.txt

    Kết quả phân tích được thể hiện trong hình bên dưới:

    Hình 3

    Như vậy, bằng các lệnh đơn giản được kèm trong tập tin grammar, bạn thấy được kết quả phân tích trong hình 3, các lệnh và tham số được tách đầy đủ rất nhanh và dễ dàng.

    Trên đây là ví dụ đơn giản thể hiện khả năng của JavaCC. Trên thực tế, bạn sẽ cần tìm hiểu rõ hơn về các thông số chỉ thị và các cách thức xử lý khi gặp các câu ngữ pháp phức tạp, ví dụ như câu lệnh IF...THEN...ELSE trong ngôn ngữ lập trình. Tất cả các thông tin đó đều được mô tả khá chi tiết cùng nhiều ví dụ cụ thể tại trang chủ của JavaCC.

    Hy vọng qua bài viết này, bạn có một cái nhìn tổng quát về cấu trúc một tập tin ngữ pháp của JavaCC cũng như cách thức chạy lệnh để sinh mã nguồn bộ parser riêng cho mình mà không cần bận tâm các vấn đề xử lý chuỗi phức tạp. Một lập trình viên thành thạo các ngôn ngữ lập trình và các kỹ thuật là điều cần có, nhưng khả năng vận dụng nhuần nhuyễn các thư viện hỗ trợ như JavaCC không chỉ giúp tạo nên những sản phẩm có giá trị thực tế, mà còn giúp tiết kiệm được rất nhiều thời gian và công sức trong quá trình phát triển phần mềm.

    Đôi điều về Regex

    Để làm chủ được bộ ngữ pháp của JavaCC, bạn cần thành thạo Java và regular expression. Dưới đây là vài chú ý về regular expression được dùng trong ví dụ trên:

    (...)+ : Một hoặc nhiều
    (...)* : Không hoặc nhiều
    (...)? hoặc […]: Tùy chọn và không bắt buộc
    (["0"-"9"])+ : Chuỗi chỉ chứa các kí tự dạng số, có ít nhất một kí tự.

    Về việc vận dụng JavaCC tại Global CyberSoft VN (GCS)

    Tại Global CyberSoft VN, chúng tôi đã phát triển thành công phần mềm eMonKey giúp tự động hóa việc kiểm thử phần mềm (software testing) trên nhiều platform khác nhau, bao gồm desktop, web và mobile. eMonKey áp dụng kỹ thuật keyword-driven, cho phép thu giữ (record) lại các tác vụ của người dùng trên phần mềm chỉ định được dạng các keyword, đồng thời cho phép người dùng soạn thảo và hiệu chỉnh các lệnh keyword đó, cuối cùng sẽ cho phép chạy lại (playback) các tác vụ đó trên phần mềm cần kiểm thử. Chức năng soạn thảo của eMonKey sử dụng JavaCC làm bộ phân tích cú pháp và bóc tách dữ liệu.

    Nguyễn Văn Sơn - Global CyberSoft VN
    Email: sonvn@gcs-vn.com

    Tham khảo: https://javacc.java.net/doc/javaccgrm.html