Các bước và sự tham gia của việc thực hiện một trình phân tích cú pháp (trong .Net - và trong trường hợp này là XPath 2.0)

Question

Trong việc thiếu các triển khai XPath 2.0 miễn phí tốt cho .Net xây dựng dựa trên LINQ to XML Tôi đã nghĩ về việc triển khai thực hiện của riêng mình (cũng cho kinh nghiệm). Nhưng chỉ để được rõ ràng (và không phải xây dựng một cái gì đó mà tồn tại) đó là những 2.0 triển khai XPath tôi đã tìm thấy:

• Saxon Net
• Query Machine - Tôi đã có vấn đề với điều này - ngoại lệ với các ví dụ
• XQSharp - có thể tốt, nhưng là thương mại (một nhà phát triển đơn lẻ ~ 300 $)

Bây giờ, tôi muốn một số ý tưởng về việc triển khai một số ngôn ngữ như XPath 2.0 khó khăn như thế nào. Tôi đã tìm thấy liên kết này có biểu thức EBNF cho biểu thức XPath 2.0: http://www.w3.org/TR/2007/REC-xpath20-20070123/#id-grammar và tôi đang nghĩ đến việc tạo nó trong F # với kết hợp fslex/fsyacc.

Nền của tôi (chủ quan): Tôi đã từng chơi với những công cụ này trước đây, nhưng chỉ cho một số biểu thức đơn giản và ngôn ngữ lập trình rất đơn giản. Hơn nữa, tôi đã đọc hầu hết các cuốn sách Dragon và thực hiện trình biên dịch hiện đại của Appel trong ML - nhưng thật không may, tôi đã không đưa lý thuyết vào thực tế trong khi đọc. Tôi đã nghiên cứu khoa học máy tính trong một năm, nơi tôi đã hoàn thành các khóa học với lý thuyết về ví dụ: finite automaton, CFL và các thuật toán nhưng tôi đã là nhà phát triển nhiều năm trước đại học (một vài năm với công việc chuyên nghiệp - back-end của các trang web chủ yếu).

Bây giờ, các bước phân tích và những gì tôi có xu hướng bao gồm:

1. Lex - Parsing - Giảm: FsLex/FsYacc. Lần đầu tiên tôi sẽ không bao gồm TẤT CẢ của Xpath 2.0 nhưng ít nhất tất cả những gì XPath 1.0 có thể làm + nhiều hơn một chút.
2. phân tích Sematic - Tôi không chắc chắn về bao nhiêu đó là
3. Tối ưu hóa này - Tôi không có xu hướng để trang trải này (ít nhất là không lúc đầu)
4. traversing thực tế, vv
5. ... ?

Bây giờ, câu hỏi bê tông ngoài trên:

1. Làm thế nào khó khăn là nó để thực hiện một phân tích cú pháp của kích thước này? dựa trên nền của tôi, tôi có thể làm được không?
2. Có bất kỳ bước quan trọng nào tôi đã bỏ lỡ liên quan đến XPath 2.0 nói riêng không?
3. Có công nghệ nào tôi đã bỏ lỡ hay không; Tôi có phải bao gồm nhiều hơn XPath 2.0 và XDocument, v.v. để có thể làm cho trình phân tích cú pháp không?

Để được rõ ràng: Tôi muốn thực hiện một XPath 2.0 biểu phân tích cú pháp và đi qua XDocument, vv với điều này phân tích cú pháp biểu hiện. Mà tôi đoán kết hợp là một công cụ truy vấn.

Cập nhật: Tôi tìm thấy điều này: http://www.w3.org/2007/01/applets/xpathApplet.html chứa mã để phân tích cú pháp và truyền tải.Tôi nghĩ rằng đó sẽ là một khởi đầu tốt đẹp hoặc tham khảo :-)

Câu trả lời của bạn sẽ được đánh giá cao.

Answer 1

Tôi đã triển khai hoàn toàn trình phân tích cú pháp XPath 2.0 trong XSLT 2.0 ba năm trước.

tôi sử dụng tôi LR Parsing Framework trong FXSL và điều này cũng không đến nỗi khó khăn. Ngữ pháp là khá lớn - 209 quy tắc, nếu tôi nhớ rõ. Tôi đã sử dụng sửa đổi YACC (do tôi thực hiện) mà tôi gọi là Yaccx để tạo các bảng phân tích cú pháp dưới dạng XML. Đây là đầu vào cho the general LR Parser, được viết bằng XSLT.

Đối với loại dự án bạn cần phân bổ ít nhất 6 tháng toàn thời gian, có thể 1 năm. Khó khăn là triển khai thư viện chức năng khổng lồ (F & O).

Ngoài ra, XPath không phải là ngôn ngữ độc lập - ngôn ngữ đó phải được lưu trữ bằng ngôn ngữ khác. Vì lý do này, tôi đã không sử dụng trình phân tích cú pháp này cho bất kỳ điều gì có ý nghĩa, vì tôi không có quyền truy cập, ảnh hưởng và khả năng thay đổi ngôn ngữ lưu trữ hiện có.

Vì vậy, hãy chuẩn bị cho tất cả những khó khăn này.

Answer 2

Để giải quyết câu hỏi cụ thể thứ ba của bạn, Sách Rồng không đề cập đến các thư viện phân tích cú pháp biểu thức phân tích cú pháp/phân tích cú pháp/phân tích cú pháp Packrat, hiện nay là rất tức giận, đặc biệt là khi nói đến các ngôn ngữ chức năng. Xem ví dụ FParsec.

Answer 3

Tôi là một trong những nhà phát triển của XQSharp, vì vậy tôi có kinh nghiệm trong lĩnh vực này. XQSharp thực sự đã bắt đầu cuộc sống của mình như là một triển khai XPath trước khi chúng tôi mở rộng nó để hỗ trợ XQuery.

Triển khai ban đầu của chúng tôi mất khoảng 6 tháng, mặc dù đây không phải là điều duy nhất chúng tôi đang làm việc vào thời điểm đó.

Sau thời gian này, chúng tôi đã triển khai tính năng hoàn chỉnh. Có nhiều lĩnh vực mà điều này không hoàn toàn phù hợp, nơi mà các phương thức .NET chuẩn không hoạt động hoàn toàn giống như các đặc tả yêu cầu. Một số ví dụ về điều này là với các giá trị chuyển đổi đến và từ các chuỗi, các biểu thức chính quy, rất nhiều công cụ unicode, các vấn đề với các biểu diễn .NET của XML (ví dụ: xử lý xml: base) và vân vân.

Có một vài lĩnh vực mà cần phải được thực hiện để thực hiện điều này:

Phân tích: Các phân tích cú pháp riêng của mình là đơn giản, và chủ yếu được tạo ra từ các EBNF trong spec. Tôi ước tính rằng điều này ban đầu đại diện cho một vài tuần làm việc.

Mô hình dữ liệu: Cách dữ liệu được trình bày. Để có một thực thi XPath đầy đủ, có rất nhiều kiểu dữ liệu mới (như xs: gDay) cần phải được thực hiện. Trong trường hợp của chúng tôi, chúng tôi có tất cả các mục của chúng tôi lấy được từ một loại cơ sở và tất cả các biểu thức của chúng tôi sẽ trả về các điều tra viên. Bạn cũng cần phải có khả năng xác định xem loại của một mục phù hợp với một loại XPath cụ thể hay không.Chúng tôi đã hỗ trợ nhập tĩnh và nhận thức giản đồ ngay từ đầu, mà không có các tính năng này, phần này có thể trở nên tầm thường, nhưng bạn vẫn đang xem xét công việc đáng giá vài tuần.

Biểu thức/Cây cú pháp trừu tượng Đây là mô hình của biểu thức. Chúng tôi đã sử dụng tài liệu ngữ nghĩa chính thức của XQuery để tạo ra một ánh xạ từ các cấu trúc XPath khác nhau (ví dụ các trục và các biến vị ngữ) đến một ngữ pháp lõi đơn giản hơn (kết thúc với một số lượng lớn let, cho if và các biểu thức sắp xếp!). Trong thực hiện ban đầu, tất cả các biểu thức này đã đánh giá các phương thức và do đó là biểu diễn cuối cùng của biểu thức. Trong trường hợp của chúng tôi, tất cả các biểu thức đều có phương thức kiểm tra kiểu, nhưng điều này có thể bị bỏ qua ban đầu (Mục đích chính của việc này là để tối ưu hóa). Tạo ra tất cả các biểu thức này một lần nữa mất vài tuần.

Chức năng Là người nhận xét trước đã chỉ ra thư viện hàm cho XPath là khá lớn. Toàn bộ thư viện XPath đã cho chúng tôi vài tháng để thực hiện.

Phân tích tĩnh Cần một lượng nhỏ phân tích tĩnh. Tham chiếu biến và các cuộc gọi hàm phải được ràng buộc với các biến và hàm chính xác. Hầu hết các cài đặt XPath đều dựa trên stack, và do đó một giai đoạn phân bổ stack được yêu cầu để gán con trỏ (hoặc chỉ mục) cho tất cả các biến. Phân tích tĩnh này mất một hoặc hai tuần. Cuốn sách Rồng nên thiết lập bạn rất độc đáo để giải quyết hầu hết những vấn đề này.

Có thể bạn đang xem xét giá trị công việc của một tháng khác cho tất cả các bit công việc bổ sung không rơi trực tiếp vào các danh mục này.

Sau tất cả công việc này, chúng tôi đã để lại phần lớn việc triển khai thực hiện chức năng của XPath; nhưng nó còn chậm để sử dụng trong thế giới thực (có thể chậm hơn 100 lần so với XPath 1 trong .NET). Vì vậy, sau này đến công việc vui vẻ - Tối ưu hóa.

Đưa công cụ lên tới 100% sự phù hợp và thêm tối ưu hóa có thể mất thêm 12-18 tháng nữa (mặc dù chúng tôi có thể đã đi quá ít với tối ưu hóa!), Nhưng đến thời điểm đó chúng tôi đã thực hiện chuyển đổi thành XQuery thực hiện. Lời khuyên của tôi là bắt đầu bằng cách giải quyết một tập hợp con của XPath (có thể chỉ có trục chuyển tiếp và thư viện hàm rất hạn chế) và bạn có thể cùng nhau thực hiện trong một hoặc hai tháng, nhưng việc thực thi XPath2 nghiêm trọng sẽ là một đầu tư lớn trong thời gian.

Đảm bảo rằng bạn sử dụng XPathNavigator cho biểu diễn nút của bạn, vì nó có các phương thức như SelectChildren, có thể tận dụng các chỉ mục trong các biểu diễn bên dưới (ví dụ XPathDocument).