Phân tích từ vựng và cú pháp

Phân tích từ vựng và cú pháp tạo thành phần tiền xử lý của trình biên dịch, phân tách văn bản nguồn thành các mã thông báo (token) và nhận dạng cấu trúc ngữ pháp của nó dưới dạng cây phân tích hoặc cây cú pháp.

Definition

Phân tích từ vựng là giai đoạn nhóm các ký tự đầu vào thành các mã thông báo, và phân tích cú pháp (parsing) là giai đoạn xác định liệu và bằng cách nào các mã thông báo đó tạo thành một chương trình hợp lệ theo một ngữ pháp, tạo ra một cây cú pháp.

Scope

Chủ đề này bao gồm phân tích từ vựng, chuyển đổi luồng ký tự thành các mã thông báo bằng cách sử dụng ngôn ngữ chính quy và máy trạng thái hữu hạn, và phân tích cú pháp (parsing), nhận dạng cấu trúc cụm từ của một chương trình dựa trên ngữ pháp phi ngữ cảnh. Nó bao gồm phân tích cú pháp từ trên xuống (LL) và từ dưới lên (LR), các trình tạo bộ phân tích cú pháp, sự mơ hồ và phục hồi lỗi, và việc xây dựng cây cú pháp trừu tượng.

Core questions

• Ngôn ngữ chính quy và phi ngữ cảnh được sử dụng như thế nào để mô tả cấu trúc chương trình?
• Những đánh đổi giữa phân tích cú pháp LL và LR là gì?
• Sự mơ hồ và lỗi phân tích cú pháp được phát hiện và xử lý như thế nào?
• Một cây cú pháp trừu tượng được xây dựng từ một luồng mã thông báo như thế nào?

Key theories

Phân tích cú pháp LR

Knuth đã giới thiệu phân tích cú pháp LR, một kỹ thuật từ dưới lên phân tích xác định lớp ngữ pháp LR rộng trong thời gian tuyến tính, tạo thành cơ sở của nhiều trình tạo bộ phân tích cú pháp.

Phân tích cú pháp phi ngữ cảnh tổng quát

Thuật toán của Earley phân tích các ngữ pháp phi ngữ cảnh tùy ý, bao gồm cả những ngữ pháp mơ hồ, cung cấp một phương pháp tổng quát khi các bộ phân tích cú pháp xác định bị hạn chế là không đủ.

Nền tảng chính quy và phi ngữ cảnh của phần tiền xử lý

Cuốn sách Dragon Book hệ thống hóa việc sử dụng biểu thức chính quy và máy trạng thái hữu hạn để quét và ngữ pháp phi ngữ cảnh để phân tích cú pháp, bao gồm các thuật toán xây dựng LL và LR tiêu chuẩn.

Clinical relevance

Phân tích từ vựng và cú pháp là nền tảng không chỉ cho trình biên dịch mà còn cho trình thông dịch, trình kiểm tra cú pháp (linters), trình định dạng (formatters), môi trường phát triển tích hợp (IDEs) và bộ xử lý định dạng dữ liệu. Phân tích cú pháp mạnh mẽ với khả năng phục hồi lỗi tốt là điều cần thiết cho trải nghiệm của nhà phát triển đối với bất kỳ công cụ ngôn ngữ nào.

History

Hệ thống phân cấp ngôn ngữ hình thức của Chomsky vào cuối những năm 1950 đã cung cấp lý thuyết về ngôn ngữ chính quy và phi ngữ cảnh. Knuth đã hình thức hóa phân tích cú pháp LR vào năm 1965, và Earley đã đưa ra một thuật toán phi ngữ cảnh tổng quát vào năm 1970. Các trình tạo bộ phân tích cú pháp như yacc đã làm cho phân tích cú pháp LR trở nên thực tế, trong khi các công trình sau này đã khám phá ngữ pháp biểu thức phân tích cú pháp và bộ phân tích cú pháp dựa trên tổ hợp.

Debates

Bộ phân tích cú pháp được tạo ra so với bộ phân tích cú pháp viết tay

Các nhà thực hành tranh luận về việc sử dụng các trình tạo bộ phân tích cú pháp từ ngữ pháp hình thức, vốn ngắn gọn và có thể kiểm chứng, so với các bộ phân tích cú pháp đệ quy xuống cấp viết tay, vốn thường đưa ra thông báo lỗi tốt hơn và kiểm soát tốt hơn với chi phí mã hóa nhiều hơn.

Key figures

• Donald Knuth
• Jay Earley
• Alfred Aho
• Noam Chomsky

Seminal works

• knuth1965
• earley1970
• aho2006

Frequently asked questions

Sự khác biệt giữa bộ phân tích từ vựng (lexer) và bộ phân tích cú pháp (parser) là gì?

Bộ phân tích từ vựng nhóm các ký tự thô thành các mã thông báo như định danh và toán tử, trong khi bộ phân tích cú pháp sắp xếp các mã thông báo đó thành một cây cú pháp phân cấp theo ngữ pháp của ngôn ngữ.

Sự khác biệt giữa phân tích cú pháp LL và LR là gì?

Bộ phân tích cú pháp LL hoạt động từ trên xuống, dự đoán các sản xuất từ tiền tố đầu vào, trong khi bộ phân tích cú pháp LR hoạt động từ dưới lên, giảm các chuỗi con được nhận dạng; LR xử lý một lớp ngữ pháp lớn hơn nghiêm ngặt nhưng phức tạp hơn để xây dựng.