Hướng dẫn thiết kế cho trình phân tích cú pháp và lexer?

Question

Tôi đang viết lexer (với re2c) và phân tích cú pháp (với Lemon) cho định dạng dữ liệu hơi phức tạp: CSV, nhưng với các loại chuỗi cụ thể tại những địa điểm cụ thể (ký tự chữ và số, ký tự chữ và số và dấu trừ) char ngoại trừ dấu ngoặc kép và dấu phẩy nhưng với dấu ngoặc ôm cân bằng, vv), các chuỗi bên trong dấu ngoặc và chuỗi trông giống như các cuộc gọi hàm với các dấu ngoặc mở và đóng có thể chứa các tham số.

Ảnh đầu tiên của tôi ở đó là một lexer với nhiều trạng thái, mỗi trạng thái cung cấp định dạng chuỗi cụ thể. Nhưng sau nhiều tin nhắn "không mong muốn đầu vào" vô ích từ lexer (mà đã nhận rất lớn) tôi nhận ra rằng có lẽ nó đã cố gắng để làm công việc của trình phân tích cú pháp. Tôi loại bỏ lần thử đầu tiên của tôi và đi với một lexer chỉ với một trạng thái, nhiều thẻ ký tự và một trình phân tích cú pháp kết hợp các thẻ vào các loại chuỗi khác nhau. Điều này hoạt động tốt hơn, tôi nhận được nhiều lỗi cú pháp hữu ích hơn từ trình phân tích cú pháp khi có điều gì đó tắt, nhưng nó vẫn cảm thấy không hoàn toàn đúng. Tôi đang nghĩ đến việc thêm một hoặc hai trạng thái vào lexer, nhưng khởi tạo các trạng thái từ trình phân tích cú pháp, trong đó có một "tổng quan" tốt hơn về loại chuỗi nào được yêu cầu trong một cá thể đã cho. Nói chung tôi cảm thấy một chút ngu ngốc: (

Tôi không có nền CS chính thức và nhút nhát một chút so với lý thuyết toán học nặng. Nhưng có thể có một hướng dẫn hoặc cuốn sách ở đâu đó giải thích những gì một lexer nên (và không nên) Làm thế nào để xây dựng các mẫu mã thông báo tốt, khi nào sử dụng các trạng thái lexer, khi nào và làm thế nào để sử dụng các quy tắc đệ quy (với một trình phân tích cú pháp LALR), làm thế nào để tránh các quy tắc không rõ ràng. Các "Lex và YACC mồi/HOWTO" là tốt đẹp, nhưng không đủ.Vì tôi chỉ muốn phân tích một định dạng dữ liệu, sách về xây dựng trình biên dịch (giống như cuốn sách rồng đỏ) nhìn một chút quá khổ với tôi

Hoặc có thể ai đó có thể cho tôi một số quy tắc đơn giản ở đây.

Answer 1

Điều bạn nên làm là viết một ngữ pháp cho ngôn ngữ của bạn. Một khi bạn đã có, ranh giới rất dễ dàng:

• Các lexer có trách nhiệm tham gia đầu vào của bạn và nói cho bạn mà terminal bạn có.
• Các phân tích cú pháp có trách nhiệm phù hợp với một loạt các thiết bị đầu cuối và thuộc đầu cuối đến một quy tắc sản xuất, liên tục, cho đến khi bạn có thể sở hữu một cây phân tích cú pháp hoặc một thất bại phân tích cú pháp.

Lexer không chịu trách nhiệm xác thực đầu vào ngoại trừ việc loại bỏ các ký tự không thể, và các số rất cơ bản khác. Trình phân tích cú pháp thực hiện tất cả những điều đó.

Hãy xem http://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html. Đây là trang giới thiệu CS về phân tích cú pháp.

Answer 2

Một phép thử tốt cho quyết định nếu một cái gì đó nên được thực hiện bởi một phân tích cú pháp hoặc lexer là tự hỏi mình một câu hỏi:

Liệu cú pháp có bất kỳ, lồng nhau, các yếu tố tự tương tự đệ quy?
(ví dụ: dấu ngoặc đơn lồng nhau, niềng răng, thẻ, biểu thức con, phần phụ, v.v.).

Nếu không, cụm từ thông dụng đơn giản là đủ và có thể được thực hiện bởi từ khóa.
Nếu có, nó sẽ được phân tích bởi một trình phân tích cú pháp, vì đó là ngữ pháp không có ngữ cảnh ở mức tối thiểu.

Lexer nói chung là tìm "từ" ngôn ngữ của bạn và phân loại chúng (đó là danh từ?một động từ? một tính từ? v.v.)
Trình phân tích cú pháp dành cho việc tìm kiếm các "câu" phù hợp, cấu trúc cho chúng một kết quả tìm kiếm nếu chúng là các câu phù hợp trong một ngôn ngữ nhất định.