Tôi đang cố viết một công cụ biểu thức chính quy. Tôi muốn viết một trình phân tích cú pháp gốc đệ quy bằng tay. Ngữ pháp tự do ngữ cảnh mà không có sự đệ quy trái cho ngôn ngữ của các biểu thức thông thường (không phải ngôn ngữ có thể được mô tả bằng các cụm từ thông dụng) trông như thế nào? Có dễ nhất để xác định lại đường cú pháp, tức là thay đổi a+ thành aa* không? Cảm ơn trước!Ngữ pháp không có ngữ cảnh mô tả các biểu thức chính quy?
đệ quy trái:
Expression = Expression '|' Sequence
| Sequence
;
Sequence = Sequence Repetition
| <empty>
;
phải đệ quy:
Expression = Sequence '|' Expression
| Sequence
;
Sequence = Repetition Sequence
| <empty>
;
mơ hồ dạng:
Expression = Expression '|' Expression
| Sequence
;
Sequence = Sequence Sequence
| Repetition
| <empty>
;
Bài viết wikipedia trên Left Recursion cung cấp thông tin khá tốt về cách tắt tính năng này.
Nó không phải là tôi cần phải tái yếu tố ngữ pháp với đệ quy trái, mà đúng hơn là tôi đang cố gắng để cảm nhận về ngữ pháp sẽ trông như thế nào nói chung. Trong khi tôi đã đọc về chúng rất nhiều, tôi chưa bao giờ thực sự sử dụng một ngữ pháp ngữ cảnh tự do 'trong tự nhiên' để nói. – wkf
Bạn có thể nhìn vào source code for Plan 9 grep. Các tập tin grep.y có một yacc (LALR (1) nếu tôi nhớ lại chính xác) ngữ pháp cho các biểu thức thông thường. Bạn có thể bắt đầu từ ngữ pháp yacc và viết lại nó để phân tích cú pháp gốc đệ quy.
Ngay trên người đàn ông; bạn đã trả lời tất cả các câu hỏi của tôi tối nay. Cảm ơn! – wkf