Hãy để tôi bắt đầu bằng cách nói - Tôi đã rất ngạc nhiên khi viết ngữ pháp cho trình phân tích cú pháp Earley dễ dàng như thế nào. Tôi đã sử dụng các biểu thức chính quy trong hơn một thập kỷ. Và tôi đã quen với việc phân tích mọi thứ bằng cách sử dụng các biểu thức chính quy. Nó mong manh, không phải lúc nào cũng có thể, v.v. Nhưng nó nhanh và phần lớn nó phục vụ mục đích
Làm quen với các thuật toán phân tích cú pháp đã thay đổi thái độ này mãi mãi
Đây là một bài viết dài. Vì vậy, tôi đã sử dụng meme He Man để giúp bạn giải trí trong suốt hành trình. Tôi hứa với bạn một vũ khí toàn năng ở cuối bài viết
Tận hưởng cuộc hành trình ;-] Lý do viết trình phân tích cú pháp
Tôi đang làm việc trên một trình quét HTML khai báo. Cú pháp của trình cạp phụ thuộc vào DSL tùy chỉnh, đây là phần mở rộng của đặc tả bộ chọn CSS3
Dưới đây là một ví dụ về tệp kê khai cạp được sử dụng để khai báo nội dung cần phân tích cú pháp cũng như cách xác thực và định dạng dữ liệu kết quả
selector: body
properties:
title: title
articles:
selector: article {0,}
properties:
body: .body::property[innerHTML]
summary: .body p {0,}[0]
imageUrl: img::attribute[src]
title: .title::text[]::test[/foo/]::format[upperCase]
Có rất nhiều thứ đang diễn ra ở đó không phải là một phần của thông số CSS
- Một biểu thức định lượng [
expression -> "1+2+3"
1] - Một biểu thức truy cập [
expression -> "1+2+3"
2] - Một lời gọi hàm XPath-esque [
expression -> "1+2+3"
3]
Tôi cần một cách để phân tích nó
Chọn đúng công cụ cho công việcSuy nghĩ đầu tiên của tôi là sử dụng các biểu thức thông thường. Trên thực tế, tôi đã sử dụng các biểu thức chính quy để viết nguyên mẫu của trình phân tích cú pháp. Xét cho cùng, trong giai đoạn đầu của quá trình thiết kế chương trình, bạn cần có khả năng nhanh chóng tạo nguyên mẫu cho giải pháp;
Điều này không có nghĩa là regrec không thể được sử dụng làm trình phân tích cú pháp. Các biểu thức chính quy có thể được sử dụng để phân tích các ngôn ngữ thông thường;
Nhân tiện, nếu thuật ngữ “không có ngữ cảnh” hoặc “ngôn ngữ thông thường” không có nhiều ý nghĩa, tôi khuyên bạn nên đọc Sức mạnh thực sự của biểu thức chính quy [đọc trong 5 phút]
Tuy nhiên, đối với các bản phát hành sản xuất, tôi cần một trình phân tích cú pháp chặt chẽ, có thể mở rộng
Tôi đã bắt đầu tìm kiếm các trình phân tích cú pháp trong JavaScript và tôi đã tìm thấy Jison và PEG. js. Tuy nhiên, cả hai thuật toán đều không hỗ trợ đệ quy trái. Tôi muốn một trình phân tích cú pháp hỗ trợ đệ quy trái
Chiếc xe tăng giống cá mập, với bộ hàm cực mạnh
Tôi không đùa với bạn - Tôi thậm chí còn không biết đệ quy trái là gì tại thời điểm đưa ra quyết định này. Tuy nhiên, tôi thấy thật kỳ lạ khi người ta nhấn mạnh rằng các thuật toán này không hỗ trợ nó. Tuy nhiên, đó là một linh cảm tốt - như tôi đã học được sau này, đệ quy trái cho phép giữ cho ngữ pháp của trình phân tích cú pháp đơn giản và nó có thể hiệu quả hơn rất nhiều
Tóm lại, trên trang thứ hai của Google tìm kiếm “Trình phân tích cú pháp JavaScript”, tôi đã tìm thấy http. //gần đây. js. org/, triển khai thuật toán phân tích cú pháp Earley
Tác giả mô tả nó như là
Trình phân tích cú pháp Earley thật tuyệt vời, bởi vì chúng sẽ phân tích cú pháp bất kỳ thứ gì bạn cung cấp cho chúng. Tùy thuộc vào thuật toán được chỉ định, các trình phân tích cú pháp phổ biến như lex/yacc, flex/bison, Jison, PEGjs và Antlr sẽ bị hỏng tùy thuộc vào ngữ pháp bạn đưa ra. Và khi ngắt, ý tôi là các vòng lặp vô hạn gây ra bởi đệ quy trái, sự cố hoặc từ chối biên dịch một cách ngoan cố do "lỗi giảm ca"
– Tốt hơn Earley còn hơn không [http. //cứng123. github. io/earley. html]
Nó giống như một kỹ năng mà tôi muốn học
Ai cần tất cả các trình phân tích cú pháp khác khi có He-Man
Vì vậy, tôi tiếp tục đọc
Thành lậpCài đặt gói
expression -> "1+2+3"
4$ npm install nearley
expression -> "1+2+3"
5 bao gồm gói chính [API trình phân tích cú pháp] và một số chương trình CLI$ ls -1 ./node_modules/.bin
nearley-railroad
nearley-test
nearley-unparse
nearleyc
Các chương trình này là
expression -> "1+2+3"
6 được sử dụng để tạo sơ đồ đường sắtexpression -> "1+2+3"
7 được sử dụng để kiểm tra đầu vào tùy ý dựa trên ngữ pháp đã biên dịchexpression -> "1+2+3"
8 được sử dụng để tạo các chuỗi ngẫu nhiên thỏa mãn ngữ phápexpression -> "1+2+3"
9 được sử dụng để biên dịch ngữ pháp Nearley thành tập lệnh JavaScript
Để cung cấp các chương trình này cho shell của bạn, hãy thêm
expression -> "1+2+3"
20 vàoexpression -> "1+2+3"
21 [expression -> "1+2+3"
22] của bạn hoặc cài đặtexpression -> "1+2+3"
23 với tùy chọnexpression -> "1+2+3"
24
Chúng tôi sẽ chỉ sử dụng
expression -> "1+2+3"
9 và expression -> "1+2+3"
26Trình phân tích cú pháp cần một ngữ pháp để phân tích cú pháp đầu vào
Thuật toán Earley phân tích cú pháp một chuỗi dựa trên ngữ pháp ở Dạng Backus-Naur [BNF]. Một ngữ pháp BNF bao gồm một tập hợp các quy tắc sản xuất, là các phần mở rộng của các phần tử không đầu cuối
Một ngữ pháp để phân tích đầu vào “1+2+3” là
expression -> "1+2+3"
Theo thuật ngữ giáo dân, ngữ pháp này nói. khớp “1+2+3” thành “biểu thức”
Một nonterminal là một cấu trúc của ngôn ngữ. Một nonterminal có tên [
expression -> "1+2+3"
27] và danh sách các quy tắc sản xuất. Một quy tắc sản xuất xác định những gì để phù hợp. Một quy tắc sản xuất bao gồm một loạt các chuỗi hoặc không phải đầu cuối khác [expression -> "1+2+3"
28 là một quy tắc sản xuất bao gồm một đầu cuối duy nhất]kiểm tra ngữ phápGhi chú.
expression -> "1+2+3"
29 là một tên tùy ý. Nó không có ý nghĩa ngữ nghĩa
Để kiểm tra nó, hãy biên dịch ngữ pháp bằng cách sử dụng
expression -> "1+2+3"
9expression -> "1+2+3"
2Hướng dẫn
expression -> "1+2+3"
26 sử dụng kết quả expression -> "1+2+3"
62 để phân tích cú pháp đầu vàoexpression -> "1+2+3"
6hoan hô. chương trình của chúng tôi đã phân tích một chuỗi ký tự “1+2+3”
Bảng phân tích từng phầnĐiều quan trọng là phải hiểu đầu ra của
expression -> "1+2+3"
26, vì đây là công cụ bạn sẽ sử dụng để gỡ lỗi ngữ phápEarley hoạt động bằng cách tạo ra một bảng phân tích từng phần, tôi. e. cột thứ n của bảng chứa tất cả các cách có thể để phân tích cú pháp
expression -> "1+2+3"
64, các ký tự expression -> "1+2+3"
65 đầu tiên của expression -> "1+2+3"
66expression -> "1+2+3"
2Trong ví dụ trên, “Biểu đồ. 0” là cột đầu tiên. Nó cho thấy rằng chúng ta có một
expression -> "1+2+3"
27 không đầu cuối duy nhất có thể bằng với expression -> "1+2+3"
68Theo mình hiểu thì
expression -> "1+2+3"
69 chỉ là biến tạm thời dùng để biểu diễn cấu trúc terminal để tránh lặp lại. Thêm về điều đó sau
expression -> "1+2+3"
20 là một điểm đánh dấu được sử dụng để biểu thị khoảng cách chúng tôi đã phân tích cú pháp. Hiện tại, chúng tôi đang ở đầu chuỗiKhi chúng tôi tiến hành, chúng tôi tiếp tục khớp ký tự đầu cuối theo ký tự
expression -> "1+2+3"
7Nếu toàn bộ thiết bị đầu cuối được khớp, chương trình sẽ tạo mã thông báo cho trận đấu
expression -> "1+2+3"
8Để mở rộng hiểu biết của bạn, hãy thêm một thiết bị đầu cuối khác vào quy tắc sản xuất
expression -> "1+2+3"
27 và sử dụng expression -> "1+2+3"
26 để kiểm tra các đầu vào khác nhau, e. gexpression -> "1+2+3"
1Nhiều quy tắc sản xuất [mở rộng không đầu cuối] được phân tách bằng ký tự thanh dọc [
expression -> "1+2+3"
23]
Nếu bạn vẫn cảm thấy lạc lõng với chủ đề này, thì bài viết Better Earley than never sẽ đưa bạn qua một hành trình tương đương ghi lại từng bước
hậu xử lýNếu bạn để ý kỹ, bạn sẽ nhận thấy rằng kết quả của chương trình [“1+2+3”] được chứa trong một mảng, chính mảng này được chứa trong một mảng
$ npm install nearley
0Có hai lý do cho việc này
Lý do đầu tiên là mỗi quy tắc sản xuất của một nonterminal là một danh sách. Trong ví dụ ban đầu, danh sách này chứa một thiết bị đầu cuối duy nhất “1+2+3”. Chúng tôi có thể đã viết nó như là
$ npm install nearley
1Ghi chú. khoảng trắng bao quanh các đầu cuối và đầu cuối không có ý nghĩa gì trong khai báo ngữ pháp
Ngữ pháp này tương đương với ví dụ ban đầu. Tuy nhiên, kết quả lại khác
$ npm install nearley
2Điều này là do thuật toán Earley hoạt động trên các ký tự. Bên trong,
expression -> "1+2+3"
5 chuyển đổi các chuỗi dài hơn một ký tự thành quy tắc trình phân tích cú pháp được khai báo dưới dạng một chuỗi ký hiệu [chuỗi ký tự] bao gồm chuỗi gốc. Nếu quy tắc trình phân tích cú pháp này phù hợp, chuỗi ký hiệu kết quả sẽ được nối lại thành chuỗi ban đầuMẹo. Hãy xem tệp ngữ pháp đã biên dịch [
expression -> "1+2+3"
25] để hiểu rõ hơn về định dạng bên trong của các quy tắc trình phân tích cú pháp
Chúng ta có thể sử dụng bộ xử lý hậu kỳ để tự làm việc này
Nghiêm túc mà nói, bộ xử lý hậu kỳ là gì?Bộ hậu xử lý là một hàm JavaScript được sử dụng để xử lý kết quả của quy tắc sản xuất. Bộ xử lý hậu kỳ có thể định dạng kết quả hoặc có thể từ chối kết quả khớp. Quy tắc hậu xử lý được khai báo sau quy tắc sản xuất được bao quanh bởi
expression -> "1+2+3"
26 , e. g$ npm install nearley
3Một bộ xử lý hậu kỳ được gọi với 3 tham số. Tham số đầu tiên là danh sách tất cả các trận đấu. Trong ví dụ trên, đó là.
expression -> "1+2+3"
27, expression -> "1+2+3"
28, expression -> "1+2+3"
29, expression -> "1+2+3"
28, expression -> "1+2+3"
71Kết quả của hậu xử lý trở thành giá trị của quy luật sản xuất. Trong ví dụ trên, trình phân tích cú pháp được thực thi với đầu vào “1+2+3” sẽ tạo ra
$ npm install nearley
4Sử dụng một nonterminal bên trong một nonterminalChúng ta sẽ quay lại với hai tham số còn lại ở phần sau của bài viết. Nếu bạn cảm thấy thiếu kiên nhẫn, hãy tham khảo tài liệu chính thức
Hãy quay lại định nghĩa về nonterminal mà tôi đã đưa ra trước đó
Một nonterminal là một cấu trúc của ngôn ngữ. Một nonterminal có tên và danh sách các quy tắc sản xuất. Một quy tắc sản xuất xác định những gì để phù hợp. Một quy tắc sản xuất bao gồm một loạt các chuỗi hoặc chuỗi không đầu cuối khác
Điều đó có nghĩa là chúng ta có thể khai báo một nonterminal để khớp các số và một nonterminal để khớp các ký hiệu toán học
$ npm install nearley
5Hy vọng rằng, điều này là tự giải thích
mẫu đệ quyĐúng như vậy,
expression -> "1+2+3"
72 nonterminal từ ví dụ trước chỉ có thể phân tích cú pháp các số có một chữ số. Tuy nhiên, chúng ta có thể tham khảo chính ______372 trong quy tắc sản xuấtMột lần hoặc nhiều hơn
$ npm install nearley
6Điều này chỉ đơn giản là nói với trình phân tích cú pháp rằng
expression -> "1+2+3"
72 là một trong số expression -> "1+2+3"
75 hoặc expression -> "1+2+3"
72 là một trong số expression -> "1+2+3"
75 theo sau bởi expression -> "1+2+3"
72Không hoặc nhiều hơn
Tương tự như trên, chúng ta có thể triển khai bộ định lượng bằng 0 hoặc nhiều hơn
Để khớp với không có gì, chúng tôi sử dụng quy tắc epsilon. Một quy tắc epsilon được biểu thị bằng cách sử dụng
expression -> "1+2+3"
79$ npm install nearley
7Điều này nói với trình phân tích cú pháp rằng một
expression -> "1+2+3"
72 không là gì hoặc một trong số expression -> "1+2+3"
81 theo sau bởi expression -> "1+2+3"
72Đây là những ví dụ về cấu trúc lặp lại đệ quy BNF
Bộ ký tự và bộ định lượngNếu bạn đang nghĩ về
expression -> "1+2+3"
75 và các bộ định lượng thì bạn thật may mắn. expression -> "1+2+3"
5 hỗ trợ bộ ký tự và bộ định lượng [expression -> "1+2+3"
85]Ghi chú. Đây là tính năng cụ thể của
expression -> "1+2+3"
5.expression -> "1+2+3"
5 biên dịch bộ ký tự và bộ định lượng thành BNF
Do đó, ví dụ một hoặc nhiều lần ở trên có thể được viết lại thành
$ npm install nearley
8Ví dụ không hoặc nhiều hơn ở trên có thể được viết lại thành
$ npm install nearley
9Tóm tắtPhân tích cú pháp theo nghĩa đen “1+2+3” đã dạy chúng tôi
- một nonterminal là gì
- thiết bị đầu cuối là gì
- quy luật sản xuất là gì
- cách gỡ lỗi ngữ pháp
- bộ hậu xử lý
expression -> "1+2+3"
5 là gì - bộ ký tự là gì
- định lượng là gì
- cấu trúc lặp lại đệ quy BNF là gì
Tôi biết bạn đang nghĩ gì. tất cả điều này để phân tích một chuỗi ký tự “1+2+3”?
expression -> "1+2+3"
89Phân tích cú pháp [và đánh giá] các biểu thức toán họcĐây là một ngữ pháp để phân tích bất kỳ biểu thức toán học hợp lệ nào bao gồm các hành động cộng, trừ, nhân và chia
$ ls -1 ./node_modules/.bin
nearley-railroad
nearley-test
nearley-unparse
nearleyc
0Bạn đã biết tất cả các thành phần tạo nên ngữ pháp này. Hiểu nó chỉ là vấn đề biên soạn ngữ pháp và sử dụng
expression -> "1+2+3"
26 để gỡ lỗi một số biểu thức, e. g. expression -> "1+2+3"
12 sản lượng expression -> "1+2+3"
27Khớp cái này bằng biểu thức chính quy của bạn. mơ hồ
Khi tôi giới thiệu về bộ xử lý hậu kỳ, tôi đã nói về cách kết quả được chứa trong một mảng các mảng
$ npm install nearley
0Tôi đã giải thích một cấp độ lồng nhau - đó là vì quy tắc sản xuất là một danh sách
Tuy nhiên, sau khi hỗ trợ xử lý danh sách, chúng ta vẫn còn lại kết quả phân tích cú pháp là một mảng
$ npm install nearley
4Đây là cách
expression -> "1+2+3"
14 thông báo cho bạn về sự mơ hồ ngữ pháp. Nếu có nhiều hơn một kết quả, điều đó có nghĩa là ngữ pháp không rõ ràng, tôi. e. có nhiều hơn một tuyến đường để phân tích cú pháp đầu vào. Đây là một dấu hiệu xấuSự mơ hồ sẽ đưa ra các vấn đề về hiệu suất [cần phân tích nhiều tuyến đường để hoàn thành phân tích cú pháp]. Nó cũng sẽ dẫn đến việc khó bắt lỗi – các tuyến khác nhau có thể tạo ra các kết quả phân tích cú pháp khác nhau
Đây là một ví dụ về một ngữ pháp mơ hồ
$ ls -1 ./node_modules/.bin
nearley-railroad
nearley-test
nearley-unparse
nearleyc
3Cung cấp một đầu vào khớp với bộ ký tự thứ nhất và thứ hai, đầu ra của trình phân tích cú pháp là
$ ls -1 ./node_modules/.bin
nearley-railroad
nearley-test
nearley-unparse
nearleyc
4Điều này là do cả
expression -> "1+2+3"
15 và expression -> "1+2+3"
16 khớp với chuỗi “foobar” để hoàn thànhBất cứ khi nào bạn gặp phải sự mơ hồ, hãy sử dụng chương trình
expression -> "1+2+3"
26 để theo dõi lộ trình phân tích cú pháp và xem trình phân tích cú pháp phân kỳ ở đâuVí dụ trên có thể được khắc phục bằng cách đảm bảo rằng mẫu đầu tiên xuất hiện chính xác một lần
$ ls -1 ./node_modules/.bin
nearley-railroad
nearley-test
nearley-unparse
nearleyc
5Từ chối một trận đấuKhi tôi thực sự giới thiệu các chức năng của bộ xử lý sau, tôi đã nói rằng chức năng của bộ xử lý sau được gọi với ba tham số
- Tham số đầu tiên là danh sách các mã thông báo phù hợp
- Thứ hai là chỉ mục tại đó quy tắc được tìm thấy
- Thứ ba là một giá trị trọng điểm được sử dụng để từ chối trận đấu
Khi tôi đọc tài liệu về
expression -> "1+2+3"
5 lần đầu tiên, nó khiến tôi bối rối – khi nào thì tôi muốn từ chối một kết quả khớp hợp lệ? Hãy xem xét ví dụ này
$ ls -1 ./node_modules/.bin
nearley-railroad
nearley-test
nearley-unparse
nearleyc
6Ghi chú. Đây là một quy tắc sản xuất duy nhất. Không có
expression -> "1+2+3"
19
Bộ chọn CSS có thể bao gồm
- một bộ chọn loại [tùy chọn]
- bộ chọn id [tùy chọn]
- nhiều bộ chọn lớp [tùy chọn]
- nhiều bộ chọn giá trị thuộc tính [tùy chọn]
- nhiều bộ chọn hiện diện và [tùy chọn]
- nhiều đại cử tri lớp giả [tùy chọn]
Chú ý mô hình? . Điều này có nghĩa là bộ chọn CSS phải có ít nhất một trong các thành phần trên, nhưng không bắt buộc
Nỗ lực đầu tiên và ngây thơ của tôi là
Ghi chú. Chỉ sử dụng chữ viết tắt cho mục đích định dạng
$ ls -1 ./node_modules/.bin
nearley-railroad
nearley-test
nearley-unparse
nearleyc
7Điều này đảm bảo rằng có ít nhất một bộ chọn. Vấn đề là [bạn đã đoán ra. ] điều này có thể tạo ra nhiều hơn một kết quả [ngữ pháp mơ hồ]
Đây là nơi lính canh từ chối xuất hiện
Chúng tôi có thể lọc ra các kết quả
expression -> "1+2+3"
79 [khi một bộ định lượng không khớp với bất kỳ thứ gì, nó sẽ tạo ra expression -> "1+2+3"
79 ; hãy nhớ cách chúng tôi đã viết các bộ định lượng bằng BNF]. Và nếu không có trận đấu nào, chúng tôi sẽ trả về từ chối trọng tài để từ chối trận đấu$ ls -1 ./node_modules/.bin
nearley-railroad
nearley-test
nearley-unparse
nearleyc
8chức năng trợ giúpGhi chú. Trình phân tích cú pháp này vẫn có thể tạo ra các kết quả không rõ ràng nếu một trong các phần tử không đầu cuối được sử dụng trong biểu thức hợp nhất với nhau;
Sẽ không tốt cho khả năng đọc mã để viết các chức năng của bộ xử lý sau mỗi quy tắc sản xuất. Sử dụng cú pháp
$ npm install nearley
02 để khai báo hàm trợ giúp. Trên thực tế, ví dụ mã trên đã sử dụng hàm $ npm install nearley
03 được xác định trước$ ls -1 ./node_modules/.bin
nearley-railroad
nearley-test
nearley-unparse
nearleyc
9Phân tích cú pháp và mã thông báoGhi chú. Tất cả mã được viết giữa
$ npm install nearley
02 được đưa lên đầu tệp ngữ pháp được tạo. Do đó, nơi bạn viết chúng không quan trọng. Tuy nhiên, tôi muốn xác định tất cả các trình trợ giúp ở đầu tệp
Bây giờ bạn đã biết cách phân tích cú pháp một chuỗi, làm thế nào để bạn mã hóa nó?
Đáp án đơn giản. một bộ xử lý hậu kỳ có thể trả lại bất cứ thứ gì. Giống như chúng ta đã sử dụng bộ xử lý sau để chuyển đổi chuỗi thành số trong ví dụ về máy tính, chúng ta có thể trả về các đối tượng mô tả mã thông báo và ủy quyền logic toán học cho bất kỳ chương trình nào hiểu các mã thông báo đó, e. g
expression -> "1+2+3"
0Tiền thưởng. ngữ pháp IDECó các plugin cho các IDE khác nhau cho phép tô sáng cú pháp Nearley
- Người dùng Atom có thể viết ngữ pháp gần với plugin này của Bojidar Marinov
- Người dùng Sublime Text có thể viết ngữ pháp gần với cú pháp này bằng liam4
- Người dùng Vim có thể sử dụng plugin này của Andrés Arana
Tôi đã hứa với bạn một vũ khí toàn năng. bạn có nó. Bây giờ bạn có kỹ năng phân tích hoàn toàn bất kỳ chuỗi nào
Vũ khí toàn năng của phân tích cú pháp. Trình phân tích bộ chọn CSS
Lúc đầu, tôi đã nói rằng tôi đã bắt đầu tìm hiểu về phân tích cú pháp vì tôi cần xây dựng trình phân tích cú pháp bộ chọn CSS. Tôi đã xây dựng nó bằng cách sử dụng
expression -> "1+2+3"
5 và tôi khá chắc chắn rằng đó là trình phân tích bộ chọn CSS toàn diện nhất có sẵn cho JavaScriptGặp gỡ Scalpel, trình phân tích cú pháp bộ chọn CSS
Nếu bạn đang tìm kiếm thêm ví dụ về việc sử dụng thuật toán Earley để phân tích ngữ pháp phi ngữ cảnh, tôi khuyến khích bạn xem qua mã nguồn của Scalpel