Ngữ pháp tổng hợp

Question

Có rất nhiều ngôn ngữ lập trình hỗ trợ việc bao gồm các ngôn ngữ mini. PHP được nhúng trong HTML. XML có thể được nhúng trong JavaScript. LINQ có thể được nhúng trong C#. Biểu thức chính quy có thể được nhúng trong Perl.

// JavaScript example 
var a = <node><child/></node> 

Nghĩ về điều đó, hầu hết các ngôn ngữ lập trình đều có thể được mô hình hóa thành các ngôn ngữ mini khác nhau. Java, ví dụ, có thể được chia thành một ít nhất bốn biệt mini-ngôn ngữ:

• Một langauge type-khai (gói chỉ thị, chỉ thị nhập khẩu, khai báo lớp)
• Một ngôn ngữ thành viên khai (bổ truy cập, khai báo phương thức, thành viên vars)
• Một ngôn ngữ statement (dòng điều khiển, thực hiện tuần tự)
• Một ngôn ngữ biểu thức (literals, bài tập, so sánh, số học)

có thể để thực hiện bốn ngôn ngữ khái niệm đó thành bốn ngữ pháp riêng biệt, chắc chắn sẽ cắt giảm rất nhiều tính spaghetti mà tôi thường thấy trong phân tích cú pháp phức tạp và triển khai trình biên dịch.

Tôi đã triển khai các trình phân tích cú pháp cho các loại ngôn ngữ khác nhau trước đây (sử dụng trình phân tích cú pháp gốc, JavaCC và tùy chỉnh đệ quy) và khi ngôn ngữ trở nên thực sự lớn và phức tạp, bạn thường kết thúc bằng một ngữ pháp huuuuuuge. việc triển khai trình phân tích cú pháp thực sự rất xấu.

Lý tưởng nhất là khi viết một trình phân tích cú pháp cho một trong các ngôn ngữ đó, thật tuyệt khi thực hiện nó như một bộ sưu tập các trình phân tích cú pháp có thể kết hợp, chuyển điều khiển qua lại giữa chúng.

Điều phức tạp là thường xuyên, ngôn ngữ có chứa (ví dụ: Perl) xác định dấu gửi cuối của riêng nó cho ngôn ngữ được chứa (ví dụ: biểu thức chính quy). Dưới đây là ví dụ tốt:

my $result ~= m|abc.*xyz|i; 

Trong mã này, mã perl chính xác định một điểm cuối không chuẩn "|" cho cụm từ thông dụng. Việc thực hiện trình phân tích cú pháp regex hoàn toàn khác biệt với trình phân tích cú pháp perl sẽ thực sự khó, vì trình phân tích cú pháp regex sẽ không biết cách tìm cụm từ biểu thức mà không tham khảo bộ phân tích cú pháp gốc.

Hoặc, cho phép nói rằng tôi đã có một ngôn ngữ cho phép sự bao gồm các biểu thức LINQ, nhưng thay vì kết thúc với một dấu chấm phẩy (như C# không), tôi muốn uỷ quyền cho các biểu thức LINQ xuất hiện trong dấu ngoặc vuông:

var linq_expression = [from n in numbers where n < 5 select n] 

Nếu tôi đã xác định ngữ pháp LINQ trong ngữ pháp ngôn ngữ gốc, tôi có thể dễ dàng viết một sản xuất rõ ràng cho một "LinqExpression" bằng cách sử dụng cú pháp lookahead để tìm khung giá đỡ. Nhưng sau đó ngữ pháp của cha mẹ tôi sẽ phải hấp thụ toàn bộ đặc điểm kỹ thuật của LINQ. Và đó là một kéo. Mặt khác, một trình phân tích cú pháp Linq con riêng biệt sẽ có một thời gian rất khó khăn để tìm ra nơi dừng lại, vì nó sẽ cần phải thực hiện lookahead cho các loại token ngoài.

Và điều đó sẽ loại trừ khá nhiều bằng cách sử dụng các giai đoạn lexing/phân tích cú pháp riêng biệt, vì trình phân tích cú pháp LINQ sẽ xác định toàn bộ các quy tắc mã thông báo khác với trình phân tích cú pháp gốc. Nếu bạn đang quét tìm một mã thông báo tại một thời điểm, làm thế nào để bạn biết khi nào cần chuyển quyền kiểm soát trở lại trình phân tích từ vựng của ngôn ngữ gốc?

Các bạn nghĩ sao?Các kỹ thuật tốt nhất hiện nay có sẵn để thực hiện các ngữ pháp ngôn ngữ riêng biệt, tách rời và tổng hợp cho việc bao gồm các ngôn ngữ nhỏ trong ngôn ngữ mẹ lớn hơn là gì?

Answer 1

Phân tích cú pháp là một khía cạnh của sự cố, nhưng tôi nghi ngờ rằng sự liên kết giữa các trình thông dịch thực thi khác nhau có liên quan đến từng ngôn ngữ nhỏ có thể khó giải quyết hơn. Để hữu ích, mỗi khối cú pháp độc lập phải làm việc nhất quán với bối cảnh tổng thể (hoặc hành vi cuối cùng sẽ không thể dự đoán được, và do đó không sử dụng được).

Không phải là tôi hiểu những gì họ đang thực sự làm, nhưng một nơi rất thú vị để tìm cảm hứng nhiều hơn là FoNC. Họ dường như (tôi đoán) để được hướng vào một hướng cho phép tất cả các loại động cơ tính toán khác nhau tương tác liền mạch.

Answer 2

Tôi đang giải quyết vấn đề chính xác này. Tôi sẽ chia sẻ suy nghĩ của tôi:

Ngữ pháp khó gỡ lỗi. Tôi đã sửa lỗi một vài trong Bison và ANTLR và nó không được đẹp. Nếu bạn muốn người dùng chèn DSL như ngữ pháp vào trình phân tích cú pháp của bạn, thì bạn phải tìm cách nào đó để làm cho nó không bị thổi phồng. Cách tiếp cận của tôi là không cho phép các DSL tùy ý, nhưng chỉ cho phép những người theo hai quy tắc sau:

• Các loại mã thông báo (mã định danh, chuỗi, số) giống nhau giữa tất cả các DSL trong một tệp.
• Unbalanced ngoặc đơn, dấu ngoặc, hoặc khung không được phép

Lý do cho sự hạn chế đầu tiên là bởi vì phân tích cú pháp hiện đại phá vỡ phân tích vào một giai đoạn từ vựng và sau đó áp dụng quy tắc ngữ pháp truyền thống của bạn. May mắn thay, tôi tin rằng một tokenizer phổ quát duy nhất là đủ tốt cho 90% DSL bạn muốn tạo, ngay cả khi nó không chứa các DSL bạn đã tạo mà bạn muốn nhúng.

Hạn chế thứ hai cho phép các ngữ pháp được tách biệt hơn với nhau. Bạn có thể phân tích cú pháp theo hai giai đoạn bằng cách nhóm các dấu ngoặc đơn (dấu ngoặc ôm, dấu ngoặc vuông) và sau đó phân tích đệ quy từng nhóm. Ngữ pháp của DSL nhúng của bạn không thể thoát qua các dấu ngoặc đơn được chứa trong.

Một phần khác của giải pháp là cho phép macro. Ví dụ: regex("abc*/[^.]") có vẻ ổn với tôi. Bằng cách này, macro "regex" có thể phân tích cú pháp regex thay vì xây dựng một ngữ pháp regex thành ngôn ngữ chính. Bạn không thể sử dụng các dấu phân tách khác nhau cho regex của bạn, chắc chắn, nhưng bạn có được một thước đo nhất quán trong tâm trí của tôi.

Answer 3

Nếu bạn nghĩ về nó, đây thực sự là cách phân tích cú pháp gốc đệ quy. Mỗi quy tắc và tất cả các quy tắc nó phụ thuộc vào hình thức một ngữ pháp nhỏ. Bất cứ điều gì cao lên không quan trọng. Ví dụ, bạn có thể viết một ngữ pháp Java với ANTLR và tách tất cả các "ngôn ngữ nhỏ" khác nhau thành các phần khác nhau của tệp.

Điều này không phổ biến vì lý do những "ngôn ngữ nhỏ" này thường chia sẻ nhiều quy tắc. Tuy nhiên, nó chắc chắn sẽ là tốt đẹp nếu các công cụ như ANTLR cho phép bạn bao gồm các ngữ pháp riêng biệt từ các tệp khác nhau. Điều này sẽ cho phép bạn tách chúng một cách hợp lý. Lý do điều này có lẽ không được triển khai có thể là vấn đề "mỹ phẩm", hoàn toàn liên quan đến các tệp ngữ pháp, chứ không phải phân tích cú pháp chính nó. Nó cũng sẽ không làm cho mã của bạn ngắn hơn (mặc dù nó có thể dễ dàng hơn một chút để làm theo). Vấn đề kỹ thuật duy nhất này sẽ giải quyết là xung đột tên.

Answer 4

Bạn có thể muốn nghe this podcast.Phân tích cú pháp ít máy quét được "phát minh" để giúp giải quyết vấn đề soạn thảo các ngữ pháp khác nhau (vấn đề là bạn nhanh chóng nhận thấy rằng bạn không thể viết trình thông báo/trình quét "phổ quát").

Answer 5

Hãy xem SGLR, Phân tích LR tổng hợp không cần quét. Dưới đây là một số tham chiếu và URL. Các kỹ thuật phân tích cú pháp này làm cho thành phần của việc phân tích các bảng rất đơn giản. Đặc biệt kết hợp với SDF.

Martin Bravenboer và Eelco Visser. Thiết kế Syntax Embeddings và Assimilations cho các thư viện ngôn ngữ. Trong mô hình Công nghệ phần mềm: Hội thảo và Hội nghị chuyên đề tại mô hình năm 2007, khối lượng 5002 của LNCS, 2008.

MetaBorg và MetaBorg in action

Answer 6

Perl 6 có thể được xem như là một tập hợp các DSL đặc biệt làm cho các chương trình bằng văn bản.

Thực tế, việc triển khai Rakudo được xây dựng theo cách chính xác thời trang này.

Thậm chí chuỗi là DSL với các tùy chọn bạn có thể bật hoặc tắt.

Q 
:closure 
:backslash 
:scalar 
:array 
:hash 
"{ 1 + 3 } \n $a @a<> %a<>" 

qq"{1+2}" eq ｢3｣ 

qq:!closure"{1+2}" eq ｢{1+2}｣ 

Về cơ bản nó phải được thực hiện từ văn phạm tiếng composable để làm việc này:

sub circumfix:«:-) :-)» (@_) { say @_ } 

:-) 1,2,3 :-) 

---

Trong Perl 6 văn phạm chỉ là một loại lớp, và thẻ là một loại phương pháp.

role General-tokens { 
    token start-of-line { ^^ } 
    token end-of-line { $$ } 
} 
grammar Example does General-tokens { 
    token TOP { 
    <start-of-line> <stuff> <end-of-line> 
    } 
    token stuff { \N+ } 
} 

role Other { 
    token start-of-line { <alpha> ** 5 } 
} 
grammar Composed-in is Example does Other { 
    token alpha { .. } 
} 

say Composed-in.parse: 'abcdefghijklmnopqrstuvwxyz'; 

｢abcdefghijklmnopqrstuvwxyz｣ 
start-of-line => ｢abcdefghij｣ 
    alpha => ｢ab｣ 
    alpha => ｢cd｣ 
    alpha => ｢ef｣ 
    alpha => ｢gh｣ 
    alpha => ｢ij｣ 
stuff => ｢klmnopqrstuvwxyz｣ 
end-of-line => ｢｣ 

Lưu ý rằng tôi đã không cho thấy một lớp hành động, đó là thuận tiện cho việc chuyển các phân tích cây vì nó được xây dựng.