Máy tạo phân tích cú pháp và Ragel ... Làm cho trình phân tích cú pháp D của riêng tôi

Question

Tôi mới đến với thế giới của trình biên dịch, và gần đây tôi đã nghe về một thứ gọi là trình tạo trình phân tích cú pháp. Từ những gì tôi (nghĩ) tôi đã hiểu, các trình tạo phân tích cú pháp lấy một tệp cú pháp và xuất ra một tệp mã nguồn có thể phân tích các tệp bằng cú pháp đã cho.

Một vài câu hỏi:

1. đã Tôi hiểu rằng một cách chính xác?

2. Nếu có, Ragel có phải là công cụ như vậy không?

3. Nếu có, Ragel có thể tạo trình phân tích cú pháp D thành mã nguồn D không?

Cảm ơn bạn!

Answer 1

1. Về cơ bản là nó. Trình tạo trình phân tích cú pháp chuyển đổi ngữ pháp thành tệp nguồn có thể được sử dụng để nhận biết các chuỗi là thành viên của language được định nghĩa bởi ngữ pháp. Thông thường, nhưng không phải lúc nào, trình tạo trình phân tích cú pháp yêu cầu một trình phân tích từ vựng để ngắt văn bản thành các thẻ trước khi nó hoạt động. Lex and Yacc là các ví dụ cổ điển về bộ phân tích cú pháp từ vựng và trình tạo phân tích cú pháp.

   Trình tạo trình phân tích cú pháp hiện đại cung cấp các tính năng bổ sung. Ví dụ: ANTLR có thể tạo mã để phân tích từ vựng, phân tích ngữ pháp và thậm chí là đi bộ cây cú pháp trừu tượng đã tạo. Elkhound tạo trình phân tích cú pháp sử dụng thuật toán phân tích cú pháp GLR. Điều này cho phép nó nhận ra nhiều ngôn ngữ hơn các thuật toán phân tích cú pháp không tổng quát. PEG Parsers không yêu cầu một máy phân tích từ vựng riêng biệt.

2. Ragel thực sự tạo ra một máy phân tích từ vựng dưới dạng một máy trạng thái hữu hạn. Nó có thể nhận ra một số regular language nhưng không nhận ra ngôn ngữ context-free. Điều này có nghĩa là nó không thể nhận ra hầu hết các ngôn ngữ lập trình, bao gồm D.

3. Ragel tạo mã D nếu bạn cần một bộ phân tích từ vựng nhanh.

Để hiểu đầy đủ về trình tạo trình phân tích cú pháp cho bạn, bạn sẽ cần một số lý thuyết ngôn ngữ chính thức và phân tích cú pháp. Có những nơi tồi tệ hơn để bắt đầu hơn The Dragon Book. Xem thêm: Learning to write a compiler.

Nếu bạn cảm thấy can đảm, hãy kiểm tra mã lexing và phân tích cú pháp được phân phối bằng trình biên dịch DMD -/dmd2/src/dmd/- lexer.c và parse.c.

Answer 2

Trong khi Ragel dựa trên cụm từ thông dụng, không phải chỉ trình tạo FSM regex. Nó cho phép đệ quy bằng cách sử dụng cú pháp gọi/trả lại bổ sung, cũng như các tính năng khác cho phép phân tích cú pháp các ngôn ngữ không thường xuyên. Vì vậy, trong khi Ragel tạo FSM, nó cho phép tạo nhiều FSM khác nhau và cung cấp các cơ chế để nhảy giữa chúng tại các điểm tùy ý hoặc sử dụng cú pháp chuyển tiếp máy đặc biệt. Nó cũng cho phép thực thi mã tùy ý ở trạng thái chuyển tiếp.

Một điều khác khiến cho Ragel trở nên độc đáo là nó trực tuyến. Nói cách khác, thật dễ dàng để sử dụng để quét dữ liệu từ một nguồn không đồng bộ, chẳng hạn như một ổ cắm không chặn. Nó cũng không sử dụng tài nguyên động, ngoại trừ việc gọi/trả lại, bạn có thể sử dụng bộ nhớ tĩnh, tự động hoặc động cho ngăn xếp; tuy nhiên bạn muốn.Không có trạng thái toàn cầu.

Ragel khá độc đáo. Không giống như hầu hết (tất cả?) Máy phát điện truyền thống, nó đã được thực hiện cho lập trình mạng.

Answer 3

thể là:

MySourceCode -> (Scanner) -> MyScannerDataFile MyScannerDataFile -> (Parser) -> MyParserDataFile MyParserDataFile -> (CodeGenerator) -> MyExecutableFile

hoặc:

MySourceCode -> (ScannerAndParser) -> MyScannerAndParserDataFile MyScannerAndParserDataFile -> (CodeGenerator) -> MyExecutableFile