Trong bài viết này chúng ta sẽ xem xét cách để xây dựng một parser

1. Parser là gì?

Một compiler nhận vào một chuỗi, biến đổi chuỗi đó thành một cây cú pháp. Cây cú pháp là cây mà mỗi một node của cây đại diện cho một biểu thức, hoặc một dòng lệnh từ chương trình đầu vào.

Ví dụ sau thể hiện cây cú pháp cho biểu thức 1 + 2 + 3

TODO: tạo hình ảnh minh hoạ

Để có thể tạo ra được một parser cho một ngôn ngữ bất kỳ, chúng ta cần thực hiện các bước

• Định nghĩa các loại token mà Parser của chúng ta chấp nhận. Mỗi một ngôn ngữ khác nhau sẽ có những định nghĩa về token khác nhau.

  Ví dụ ngôn ngữ biểu thức ở trên, chúng ta hỗ trợ hai loại token

  • các số
  • các phép toán + , - , *, /

  Việc định nghĩa như này được gọi là quá trình lexing, chương trình để chuyển hoá chuỗi ký tự đầu vào thành các token được gọi là Lexer (hoặc có một số tài liệu gọi là Scanner)

• Định nghĩa các cú pháp cho ngôn ngữ lập trình của chúng ta. Các cú pháp cho ngôn ngữ lập trình là các cú pháp kiểu BNF (Backus Naur Form)

  Các cú pháp thường được biểu diễn như sau

  expression
  	: NUMBER '+' NUMBER
  	| NUMBER '-' NUMBER
  

  Với cú pháp trên, chúng ta biểu diễn các biểu thức expression dưới dạng phép toán +, hoặc - của 2 số bất kỳ

  Các cú pháp chúng ta định nghĩa được gọi là syntax của ngôn ngữ. Đầu vào của các syntax sẽ là các token đã được định nghĩa ở bước trước đó.

  Chương trình kiểm tra xem một chuỗi các token đầu vào có phù hợp với bất cứ cú pháp nào của ngôn ngữ hay không được gọi là Parser

2. Viết một parser đơn giản để parse JSON String

2.1. Định nghĩa cú pháp

Đầu tiên chúng ta định nghĩa các token của JSON string có thể nhận được

Với JSON string, chúng ta có các loại token sau

NUMBER              // 1234
STRING              // "hello world"
TRUE                // true
FALSE               // false
NULL                // null
COMMA               // ,
COLON               // :
OPEN_CURLY_BRACKET  // {
CLOSE_CURLY_BRACKET // }
OPEN_BRACKET        // [
CLOSE_BRACKET       // ]
SPACE               // \\s
EOF                 // ký tự kết thúc file

Syntax của JSON có thể được biểu diễn như sau

document
	: value EOF
	;

value
	: NUMBER                   // 10
  | STRING                   // "hello"
	| TRUE                     // true
	| FALSE                    // false 
  | NULL                     // null
  | object                   // { "name": "value" }
  | array                    // [ 1, 2, "name", { "a": "b" }]
	;

object
	: OPEN_CURLY_BRACKET object_member CLOSE_CURLY_BRACKET 
	;

object_member
	: STRING COLON value                          // "name": "value"
	| object_member COMMAN STRING COLON value     // đệ quy định nghĩa một list các member 
	; 

array
	: OPEN_BRACKET array_member CLOSE_BRACKET
	;

array_member
	: value
	| array_member COLON value
	;

2.2. Xây dựng Parser đơn giản

Từ cú pháp này chúng ta sẽ viết một class để parse JSON string như sau

Bài tập đầu tiên, chúng ta sẽ implement một JSON Parser chỉ cần parse được các số, các string, các từ khoá như true, false, và null