Tìm hiểu thêm về phân tích cú pháp

Question

Tôi đã lập trình từ năm 1999 cho công việc và giải trí. Tôi muốn học những điều mới, và gần đây tôi đã tập trung vào phân tích cú pháp, vì phần lớn công việc của tôi là đọc, tích hợp và phân tích dữ liệu. Tôi cũng có một số lượng lớn các tác vụ lặp đi lặp lại mà tôi nghĩ rằng tôi có thể thể hiện bằng các ngôn ngữ cụ thể theo từng miền đơn giản nếu chi phí thấp. Tôi có một số câu hỏi về chủ đề này.

1. Hầu hết mã phân tích hiện tại của tôi không xác định ngữ pháp chính thức. Tôi thường hack một cái gì đó với nhau trong ngôn ngữ của tôi lựa chọn bởi vì đó là dễ dàng, tôi biết làm thế nào để làm điều đó và tôi có thể viết mã rất nhanh. Nó cũng dễ dàng cho những người khác mà tôi làm việc để duy trì. Những lợi thế và bất lợi của việc xác định ngữ pháp và tạo ra một trình phân tích cú pháp thực (như là làm gì với ANTLR hoặc YACC) để phân tích cú pháp so với hacks mà hầu hết các lập trình viên sử dụng để viết phân tích cú pháp?
2. Các công cụ tạo phân tích cú pháp tốt nhất để viết các trình phân tích cú pháp dựa trên ngữ pháp trong C++, Perl và Ruby là gì? Tôi đã xem xét ANTLR và không tìm thấy nhiều về việc sử dụng ANTLRv3 với mục tiêu C++, nhưng nếu không thì có vẻ thú vị. Các công cụ khác tương tự như ANTLR mà tôi nên đọc là gì?
3. Sách và bài viết kinh điển mà ai đó quan tâm đến việc tìm hiểu thêm về phân tích cú pháp là gì? Một khóa học trong trình biên dịch tiếc là không phải là một phần của giáo dục của tôi, vì vậy vật liệu cơ bản là rất hoan nghênh. Tôi đã nghe những điều tuyệt vời về các Dragon Book, nhưng những gì khác là ra khỏi đó?

Answer 1

Trên 1., tôi cho rằng lợi thế chính là khả năng bảo trì - thực hiện một chút thay đổi đối với ngôn ngữ chỉ có nghĩa là thực hiện một thay đổi tương đối nhỏ đối với ngữ pháp, chứ không phải là hacking thông qua các điểm khác nhau trong mã có thể có liên quan đến những gì bạn muốn thay đổi ... các đơn đặt hàng có năng suất tốt hơn và nguy cơ lỗi nhỏ hơn.

Trên 2. và 3., tôi không thể đề xuất nhiều hơn những gì bạn đã tìm thấy (tôi chủ yếu sử dụng Python và pyparsing và có thể nhận xét từ trải nghiệm trên nhiều khung phân tích cú pháp lấy nét bằng Python, nhưng đối với C++ tôi chủ yếu sử dụng tốt cũ yacc hoặc bison dù sao và bản sao cũ của tôi về cuốn Dragon Book - không phải là ấn bản mới nhất, thực sự - là tất cả những gì tôi giữ ở bên cạnh tôi cho mục đích ...).

Answer 2

Let's Build A Compiler là hướng dẫn từng bước về cách viết trình biên dịch đơn giản. Mã được viết bằng Delphi (Pascal), nhưng nó đủ cơ bản để dễ dàng dịch sang hầu hết các ngôn ngữ khác.

Answer 3

Trong perl, Parse :: RecDescent modules là nơi đầu tiên để bắt đầu. Thêm hướng dẫn vào tên mô-đun và Google sẽ có thể tìm thấy nhiều hướng dẫn để giúp bạn bắt đầu.

Answer 4

Dưới đây là quan điểm của tôi về các vấn đề (rất tốt) của bạn:

1. Tôi nghĩ rằng một phân tích cú pháp có lợi nhất từ ​​những tình huống không tầm thường nơi một ngữ pháp thực sự tồn tại. Bạn phải biết về cách phân tích cú pháp và ngữ pháp làm việc để nghĩ về kỹ thuật đó, và không phải mọi nhà phát triển đều làm.
2. lex/yacc là các công cụ Unix cũ hơn có thể sử dụng được cho bạn với tư cách là nhà phát triển C++. Có lẽ cả Bison nữa.
3. ANTRL và sổ tiếp viên của nó rất tốt. "Writing Compilers and Interpreters" có các ví dụ C++ mà bạn có thể thích.

Mẫu phiên dịch GoF là một kỹ thuật khác để viết "ngôn ngữ nhỏ". Hãy nhìn vào đó.

Answer 5

Xác định ngữ pháp sử dụng BNF, EBNF hoặc tương tự, dễ dàng hơn và sau này bạn sẽ có thời gian tốt hơn để duy trì ngữ pháp. Ngoài ra, bạn có thể tìm thấy rất nhiều ví dụ về định nghĩa ngữ pháp. Cuối cùng nhưng không kém phần quan trọng, nếu bạn định nói về ngữ pháp của bạn cho người khác trên thực địa, tốt hơn cả khi bạn đang nói cùng một ngôn ngữ (BNF, EBNF, vv).

Viết mã phân tích cú pháp của riêng bạn giống như phát minh lại bánh xe và dễ bị lỗi. Nó cũng ít bảo trì hơn. Tất nhiên, nó có thể linh hoạt hơn, và đối với các dự án nhỏ, nó cũng có thể là một lựa chọn tốt, nhưng sử dụng trình tạo phân tích cú pháp hiện có có ngữ pháp và rút ra mã phải bao gồm hầu hết các nhu cầu của chúng ta.

Đối với C++, tôi cũng đề xuất lex/yacc. Đối với Ruby, điều này trông giống như một lựa chọn phong nha: Coco/R(uby)

Answer 6

Thời gian vui nhộn: Tôi đã dành rất nhiều buổi sáng này tự hỏi về máy và phân tích cú pháp của tiểu bang và tìm hiểu cách tôi có thể tìm hiểu thêm về chúng.

Đối với 2, bạn có thể xem Ragel (rất tốt cho C++ và Ruby).

Answer 7

Tôi sẽ có một cái nhìn nghiêm túc về phân tích cú pháp dựa trên combinator đơn thuần (thường cũng đề cập đến phân tích từ vựng) trong Haskell. Tôi thấy nó khá mở mắt; thật tuyệt vời khi bạn có thể dễ dàng xây dựng trình phân tích cú pháp từ đầu bằng phương pháp này. Thật dễ dàng, trên thực tế, nó thường nhanh hơn để viết trình phân tích cú pháp của riêng bạn hơn là cố gắng sử dụng các thư viện hiện có.

Ví dụ nổi tiếng nhất có lẽ là Parsec có số user guide tốt giải thích cách sử dụng. Có một danh sách các cổng của thư viện này với các ngôn ngữ khác (bao gồm C++ và Ruby) được liệt kê trên Parsec page of the Haskell wiki, mặc dù tôi không quen thuộc với chúng và vì vậy tôi không thể nói chúng gần bằng cách sử dụng Parsec trong Haskell.

Nếu bạn muốn tìm hiểu cách thức hoạt động của nội bộ và cách viết của riêng bạn, tôi khuyên bạn nên bắt đầu với Chương 8 ("Hàm phân tích cú pháp") từ Graham Hutton's Programming in Haskell. Một khi bạn hiểu rằng chương tốt (có thể sẽ có một số bài đọc), bạn sẽ được thiết lập.

Answer 8

Dưới đây là hướng dẫn về một khép kín, hoàn toàn di động biên dịch-biên dịch mà có thể được sử dụng để thiết kế và thực hiện "chi phí thấp" DSL rất nhanh (10 trang!):

http://www.bayfronttechnologies.com/mc_tutorial.html

này trang web hướng dẫn bạn qua bài viết năm 1964 của Val Schorre về MetaII. Có, năm 1964. Và nó thật tuyệt vời. Đây là cách tôi đã học về các trình biên dịch vào năm 1970.