Tài nguyên để lexing, tokenising và phân tích cú pháp trong python

Question

Mọi người có thể chỉ cho tôi các tài nguyên về lexing, phân tích cú pháp và tokenising bằng Python không?

Tôi đang thực hiện một chút hack vào một dự án mã nguồn mở (hotwire) và muốn thực hiện một vài thay đổi đối với mã mà lexes, parses and tokenises các lệnh được nhập vào đó. Vì nó là mã thực sự hoạt động nên nó khá phức tạp và khó có thể làm việc được.

Tôi chưa từng làm việc trên mã để lex/parse/tokenise trước đây, vì vậy tôi đã nghĩ một cách tiếp cận sẽ là làm việc thông qua một hướng dẫn hoặc hai về khía cạnh này. Tôi hy vọng sẽ học đủ để điều hướng xung quanh mã mà tôi thực sự muốn thay đổi. Có điều gì phù hợp không? (Lý tưởng là nó có thể được thực hiện vào một buổi chiều mà không cần phải mua và đọc cuốn sách rồng đầu tiên ...)

Edit: (7 Oct 2008) Không có câu trả lời nào dưới đây hoàn toàn đưa ra những gì tôi muốn. Với chúng tôi có thể tạo ra các trình phân tích cú pháp từ đầu, nhưng tôi muốn tìm hiểu cách viết trình phân tích cú pháp cơ bản của riêng tôi từ đầu, không sử dụng các công cụ tương tự và lex và yacc. Sau khi thực hiện điều đó, tôi có thể hiểu được mã hiện tại tốt hơn.

Vì vậy, ai đó có thể chỉ cho tôi một hướng dẫn mà tôi có thể xây dựng một trình phân tích cú pháp cơ bản từ đầu, chỉ sử dụng python?

Answer 1

Hãy nhìn vào các mô-đun chuẩn shlex và sửa đổi một bản sao của nó để phù hợp với cú pháp bạn sử dụng cho vỏ của bạn, đó là một điểm khởi đầu tốt

Nếu bạn muốn tất cả sức mạnh của một giải pháp hoàn chỉnh cho lexing/phân tích cú pháp, ANTLR cũng có thể tạo ra python.

Answer 2

Tôi đề xuất http://www.canonware.com/Parsing/, vì nó là con trăn thuần túy và bạn không cần phải học ngữ pháp, nhưng nó không được sử dụng rộng rãi và có ít tài liệu tương đối. Hạng nặng là ANTLR và PyParsing. ANTLR cũng có thể tạo ra các trình phân tích cú pháp java và C++, và các khung đi bộ AST nhưng bạn sẽ phải học những gì có giá trị cho một ngôn ngữ mới.

Answer 3

Tôi là người dùng hạnh phúc của PLY. Nó là một thực hiện tinh khiết-Python của Lex & Yacc, với rất nhiều nhỏ niceties mà làm cho nó khá Pythonic và dễ sử dụng. Kể từ khi Lex & Yacc là công cụ phân tích cú pháp phổ biến nhất được sử dụng cho hầu hết các dự án, PLY có lợi thế đứng trên vai của người khổng lồ. Rất nhiều kiến ​​thức tồn tại trực tuyến trên Lex & Yacc và bạn có thể tự do áp dụng nó vào PLY.

PLY cũng có một số documentation page tốt với một số ví dụ đơn giản để giúp bạn bắt đầu.

Để biết danh sách nhiều công cụ phân tích cú pháp Python, hãy xem this.

Answer 4

pygments là công cụ đánh dấu cú pháp mã nguồn được viết bằng python. Nó có lexers và formatters, và có thể là thú vị để peek tại nguồn.

Answer 5

Đối với các ngữ pháp trung bình, PyParsing thật tuyệt vời. Bạn có thể xác định ngữ pháp trực tiếp trong mã Python, không cần tạo mã:

>>> from pyparsing import Word, alphas 
>>> greet = Word(alphas) + "," + Word(alphas) + "!" # <-- grammar defined here 
>>> hello = "Hello, World!" 
>>>> print hello, "->", greet.parseString(hello) 
Hello, World! -> ['Hello', ',', 'World', '!'] 

(Ví dụ lấy từ trang chủ PyParsing).

Với các hành động phân tích cú pháp (các hàm được gọi khi quy tắc ngữ pháp nhất định được kích hoạt), bạn có thể chuyển đổi trực tiếp các cú pháp thành cây cú pháp trừu tượng hoặc bất kỳ biểu diễn nào khác.

Có nhiều chức năng trợ giúp đóng gói các mẫu định kỳ, như phân cấp toán tử, chuỗi được trích dẫn, lồng nhau hoặc nhận xét kiểu C.

Answer 6

Dưới đây là một vài điều để giúp bạn bắt đầu (khoảng từ đơn giản đến phức tạp nhất, ít nhất-to-nhất-mạnh mẽ):

http://en.wikipedia.org/wiki/Recursive_descent_parser

http://en.wikipedia.org/wiki/Top-down_parsing

http://en.wikipedia.org/wiki/LL_parser

http://effbot.org/zone/simple-top-down-parsing.htm

http://en.wikipedia.org/wiki/Bottom-up_parsing

http://en.wikipedia.org/wiki/LR_parser

http://en.wikipedia.org/wiki/GLR_parser

Khi tôi học được công cụ này, nó được trong một khóa học đại học 400 cấp học kỳ kéo dài. Chúng tôi đã thực hiện một số bài tập mà chúng tôi đã phân tích cú pháp bằng tay; nếu bạn muốn thực sự hiểu những gì đang xảy ra dưới mui xe, tôi muốn giới thiệu phương pháp tương tự.

Đây không phải là cuốn sách tôi đã sử dụng, nhưng nó khá tốt: Principles of Compiler Design.

Hy vọng điều đó đủ để giúp bạn bắt đầu :)

Answer 7

Câu hỏi này khá cũ, nhưng có lẽ câu trả lời của tôi sẽ giúp ai đó tìm hiểu kiến ​​thức cơ bản. Tôi thấy tài nguyên này rất tốt. Nó là một trình thông dịch đơn giản được viết bằng python mà không cần sử dụng bất kỳ thư viện bên ngoài nào. Vì vậy, điều này sẽ giúp bất cứ ai muốn hiểu được làm việc nội bộ của phân tích cú pháp, lexing, và tokenising:

"Một Intepreter đơn giản từ Scratch bằng Python:" Part 1, Part 2, Part 3, và Part 4.