Việc nhận dạng các số có thuộc về máy quét hoặc trong trình phân tích cú pháp không?

Question

Khi bạn nhìn vào mô tả EBNF của một ngôn ngữ, bạn thường thấy một định nghĩa cho các số nguyên và số thực:

integer ::= digit digit* // Accepts numbers with a 0 prefix 
real  ::= integer "." integer (('e'|'E') integer)? 

(Các định nghĩa đã được thực hiện một cách nhanh chóng, tôi đã có thể làm cho một sai lầm trong họ).

Mặc dù chúng xuất hiện trong ngữ pháp không có ngữ cảnh, nhưng các số thường được ghi nhận trong giai đoạn phân tích từ vựng. Chúng được bao gồm trong định nghĩa ngôn ngữ để làm cho nó hoàn chỉnh hơn và nó là tùy thuộc vào người thực hiện để nhận ra rằng họ thực sự nên có trong máy quét?

Answer 1

Nhiều công cụ tạo trình phân tích cú pháp phổ biến - chẳng hạn như ANTLR, Lex/YACC - phân tích cú pháp riêng biệt thành hai giai đoạn: đầu tiên, chuỗi đầu vào được mã hóa. Thứ hai, các thẻ được kết hợp thành các sản phẩm để tạo ra một cây cú pháp cụ thể.

Tuy nhiên, có các kỹ thuật thay thế không yêu cầu mã thông báo: kiểm tra backtracking recursive-descent parsers. Đối với một trình phân tích cú pháp như vậy, các mã thông báo được định nghĩa theo cách tương tự với các thẻ không phải là mã thông báo. pyparsing là trình tạo trình phân tích cú pháp cho các trình phân tích cú pháp như vậy.

Lợi thế của kỹ thuật hai bước là nó thường tạo ra các trình phân tích cú pháp hiệu quả hơn - với mã thông báo, thao tác chuỗi ít hơn nhiều, tìm kiếm chuỗi và quay ngược lại.

Theo "The Definitive ANTLR Reference" (Terence Parr),

Sự khác biệt duy nhất giữa [lexers và phân tích cú pháp] là phân tích cú pháp nhận cấu trúc ngữ pháp trong một dòng tokens trong khi lexer nhận cấu trúc trong một dòng ký tự.

Answer 2

Cú pháp ngữ pháp cần phải hoàn chỉnh để chính xác, do đó, tất nhiên nó bao gồm các chi tiết về định dạng chính xác của số nhận dạng và chính tả của toán tử.

Có, kỹ sư biên dịch quyết định nhưng nhìn chung nó khá rõ ràng. Bạn muốn lexer xử lý tất cả các chi tiết mức ký tự một cách hiệu quả.

Có câu trả lời dài hơn tại Is it a Lexer's Job to Parse Numbers and Strings?