Phân tích cú pháp là gì?
Phân tích cú pháp là giai đoạn thứ hai của quá trình thiết kế trình biên dịch, trong đó chuỗi đầu vào nhất định được kiểm tra để xác nhận các quy tắc và cấu trúc của ngữ pháp chính thức. Nó phân tích cấu trúc cú pháp và kiểm tra xem đầu vào đã cho có đúng cú pháp của ngôn ngữ lập trình hay không.
Phân tích cú pháp trong quá trình thiết kế trình biên dịch xuất hiện sau giai đoạn phân tích Lexical. Nó còn được gọi là Cây phân tích cú pháp hoặc Cây cú pháp. Cây phân tích cú pháp được phát triển với sự trợ giúp của ngữ pháp được xác định trước của ngôn ngữ. Trình phân tích cú pháp cũng kiểm tra xem một chương trình nhất định có đáp ứng các quy tắc được ngụ ý bởi một ngữ pháp không có ngữ cảnh hay không. Nếu nó thỏa mãn, trình phân tích cú pháp sẽ tạo cây phân tích cú pháp của chương trình nguồn đó. Nếu không, nó sẽ hiển thị thông báo lỗi.
Trong hướng dẫn này, bạn sẽ học
- Tại sao bạn cần Trình phân tích cú pháp?
- Thuật ngữ phân tích cú pháp quan trọng
- Tại sao chúng ta cần Phân tích cú pháp?
- Kỹ thuật phân tích cú pháp
- Lỗi - Phương pháp khôi phục
- Ngữ pháp:
- Quy ước ký hiệu
- Ngữ pháp miễn phí theo ngữ cảnh
- Khai sinh ngữ pháp
- Syntax so với Lexical Analyzer
- Nhược điểm của việc sử dụng Trình phân tích cú pháp
Tại sao bạn cần Trình phân tích cú pháp?
- Kiểm tra xem mã có hợp lệ về mặt ngữ pháp không
- Trình phân tích cú pháp giúp bạn áp dụng các quy tắc cho mã
- Giúp bạn đảm bảo rằng mỗi dấu ngoặc nhọn mở có số dư đóng tương ứng
- Mỗi khai báo có một kiểu và kiểu đó phải tồn tại
Thuật ngữ phân tích cú pháp quan trọng
Các thuật ngữ quan trọng được sử dụng trong quá trình phân tích cú pháp:
- Câu: Một câu là một nhóm ký tự trên một số bảng chữ cái.
- Lexeme: Lexeme là đơn vị cú pháp cấp thấp nhất của một ngôn ngữ (ví dụ: tổng số, bắt đầu).
- Mã thông báo : Mã thông báo chỉ là một loại lexemes.
- Từ khóa và các từ dành riêng - Nó là một định danh được sử dụng như một phần cố định của cú pháp của một câu lệnh. Nó là một từ dành riêng mà bạn không thể sử dụng làm tên biến hoặc số nhận dạng.
- Các từ nhiễu - Các từ nhiễu là tùy chọn được chèn vào một câu lệnh để nâng cao khả năng đọc của câu.
- Nhận xét - Đây là một phần rất quan trọng của tài liệu. Nó chủ yếu hiển thị bằng, / * * / hoặc // Blank (dấu cách)
- Dấu phân cách - Nó là một phần tử cú pháp đánh dấu sự bắt đầu hoặc kết thúc của một số đơn vị cú pháp. Giống như một câu lệnh hoặc biểu thức, "begin"… '' end "hoặc {}.
- Bộ ký tự - ASCII, Unicode
- Số nhận dạng - Đó là một hạn chế về độ dài giúp bạn giảm khả năng đọc của câu.
- Các ký hiệu toán tử - + và - thực hiện hai phép tính số học cơ bản.
- Các yếu tố cú pháp của ngôn ngữ
Tại sao chúng ta cần Phân tích cú pháp?
Phân tích cú pháp cũng kiểm tra xem chuỗi đầu vào có được định dạng tốt hay không và nếu không, hãy từ chối nó.
Sau đây là các tác vụ quan trọng được trình phân tích cú pháp thực hiện trong thiết kế trình biên dịch:
- Giúp bạn phát hiện tất cả các loại lỗi Cú pháp
- Tìm vị trí đã xảy ra lỗi
- Mô tả rõ ràng và chính xác về lỗi.
- Khôi phục từ một lỗi để tiếp tục và tìm các lỗi khác trong mã.
- Không ảnh hưởng đến việc biên dịch các chương trình "đúng".
- Phân tích cú pháp phải từ chối các văn bản không hợp lệ bằng cách báo cáo lỗi cú pháp
Kỹ thuật phân tích cú pháp
Các kỹ thuật phân tích cú pháp được chia thành hai nhóm khác nhau:
- Phân tích cú pháp từ trên xuống,
- Phân tích cú pháp từ dưới lên
Phân tích cú pháp từ trên xuống:
Trong cấu trúc phân tích cú pháp từ trên xuống, cây phân tích cú pháp bắt đầu từ gốc và sau đó tiến dần về phía lá.
Hai loại phân tích cú pháp Từ trên xuống là:
- Phân tích cú pháp dự đoán:
Phân tích cú pháp dự đoán có thể dự đoán sản xuất nào nên được sử dụng để thay thế chuỗi đầu vào cụ thể. Trình phân tích cú pháp tiên đoán sử dụng điểm nhìn trước, điểm này hướng tới các ký hiệu đầu vào tiếp theo. Backtracking không phải là một vấn đề với kỹ thuật phân tích cú pháp này. Nó được gọi là LL (1) Parser
- Phân tích cú pháp đi xuống đệ quy:
Kỹ thuật phân tích cú pháp này phân tích cú pháp đệ quy đầu vào để tạo một cây prase. Nó bao gồm một số chức năng nhỏ, một cho mỗi chức năng không liên quan trong ngữ pháp.
Phân tích cú pháp từ dưới lên:
Trong phân tích cú pháp từ dưới lên trong thiết kế trình biên dịch, việc xây dựng cây phân tích cú pháp bắt đầu bằng phần còn lại, và sau đó nó xử lý theo hướng gốc của nó. Nó còn được gọi là phân tích cú pháp shift-giảm. Kiểu phân tích cú pháp này trong thiết kế trình biên dịch được tạo ra với sự trợ giúp của việc sử dụng một số công cụ phần mềm.
Lỗi - Phương pháp khôi phục
Các lỗi phổ biến xảy ra trong phân tích cú pháp trong phần mềm hệ thống
- Lexical : Tên của một số nhận dạng được nhập sai
- Cú pháp : dấu ngoặc đơn không cân đối hoặc dấu chấm phẩy bị thiếu
- Ngữ nghĩa : gán giá trị không tương thích
- Logic : Vòng lặp vô hạn và mã không thể truy cập được
Một trình phân tích cú pháp sẽ có thể phát hiện và báo cáo bất kỳ lỗi nào được tìm thấy trong chương trình. Vì vậy, bất cứ khi nào xảy ra lỗi, trình phân tích cú pháp. Nó sẽ có thể xử lý nó và tiếp tục phân tích cú pháp đầu vào còn lại. Một chương trình có thể có các loại lỗi sau ở các giai đoạn biên dịch khác nhau. Có năm phương pháp khôi phục lỗi phổ biến có thể được triển khai trong trình phân tích cú pháp
Khôi phục chế độ câu lệnh
- Trong trường hợp trình phân tích cú pháp gặp lỗi, nó sẽ giúp bạn thực hiện các bước sửa chữa. Điều này cho phép phần còn lại của đầu vào và trạng thái để phân tích cú pháp trước.
- Ví dụ, thêm một dấu chấm phẩy bị thiếu trong phương pháp khôi phục chế độ câu lệnh. Tuy nhiên, nhà thiết kế phân tích cú pháp cần phải cẩn thận trong khi thực hiện những thay đổi này vì một lần sửa sai có thể dẫn đến một vòng lặp vô hạn.
Phục hồi chế độ hoảng loạn
- Trong trường hợp trình phân tích cú pháp gặp lỗi, chế độ này sẽ bỏ qua phần còn lại của câu lệnh và không xử lý đầu vào từ đầu vào sai thành dấu phân cách, giống như dấu chấm phẩy. Đây là một phương pháp khôi phục lỗi đơn giản.
- Trong loại phương pháp khôi phục này, trình phân tích cú pháp từ chối từng ký hiệu đầu vào cho đến khi tìm thấy một nhóm mã thông báo đồng bộ hóa được chỉ định duy nhất. Việc đồng bộ hóa các mã thông báo thường sử dụng các dấu phân cách như hoặc.
Phục hồi cấp độ cụm từ:
- Trình biên dịch sửa chương trình bằng cách chèn hoặc xóa mã thông báo. Điều này cho phép nó tiếp tục phân tích cú pháp từ vị trí ban đầu. Nó thực hiện hiệu chỉnh trên đầu vào còn lại. Nó có thể thay thế một tiền tố của đầu vào còn lại bằng một số chuỗi, điều này giúp trình phân tích cú pháp tiếp tục quá trình.
Sản xuất lỗi
- Khôi phục lỗi tạo ra mở rộng ngữ pháp cho ngôn ngữ tạo ra cấu trúc sai. Sau đó, trình phân tích cú pháp thực hiện chẩn đoán lỗi về cấu trúc đó.
Chỉnh sửa toàn cầu:
- Trình biên dịch nên thực hiện ít thay đổi nhất có thể trong khi xử lý một chuỗi đầu vào không chính xác. Với chuỗi đầu vào không chính xác a và ngữ pháp c, các thuật toán sẽ tìm kiếm một cây phân tích cú pháp cho một chuỗi liên quan b. Giống như một số thao tác chèn, xóa và sửa đổi được tạo bằng các mã thông báo cần thiết để chuyển đổi từ a thành b là ít nhất có thể.
Ngữ pháp:
Ngữ pháp là một tập hợp các quy tắc cấu trúc mô tả một ngôn ngữ. Ngữ pháp chỉ định cấu trúc cho bất kỳ câu nào. Thuật ngữ này cũng đề cập đến việc nghiên cứu các quy tắc này và tệp này bao gồm hình thái học, âm vị học và cú pháp. Nó có khả năng mô tả nhiều cú pháp của các ngôn ngữ lập trình.
Quy tắc ngữ pháp biểu mẫu
- Biểu tượng không phải đầu cuối phải xuất hiện ở bên trái của ít nhất một sản phẩm
- Biểu tượng mục tiêu không bao giờ được hiển thị ở bên phải của :: = của bất kỳ sản phẩm nào
- Một quy tắc là đệ quy nếu LHS xuất hiện trong RHS của nó
Quy ước ký hiệu
Biểu tượng quy ước ký hiệu có thể được chỉ ra bằng cách đặt phần tử trong dấu ngoặc vuông. Nó là một chuỗi các trường hợp tùy ý của phần tử có thể được chỉ ra bằng cách đặt phần tử trong dấu ngoặc nhọn theo sau là biểu tượng dấu hoa thị, {…} *.
Đó là một lựa chọn thay thế có thể sử dụng biểu tượng trong quy tắc duy nhất. Nó có thể được đặt trong dấu ngoặc đơn ([,]) khi cần thiết.
Hai loại khu vực quy ước ký hiệu Thiết bị đầu cuối và Không thiết bị đầu cuối
1. danh nghĩa:
- Các chữ cái thường trong bảng chữ cái như a, b, c,
- Các ký hiệu toán tử như +, -, *, v.v.
- Các ký hiệu dấu câu như dấu ngoặc đơn, dấu thăng, dấu phẩy
- 0, 1,…, 9 chữ số
- Các chuỗi in đậm như id hoặc if, bất kỳ thứ gì đại diện cho một ký hiệu đầu cuối duy nhất
2.Nonterminals:
- Các chữ cái viết hoa như A, B, C
- Tên in nghiêng viết thường: biểu thức hoặc một số
Ngữ pháp miễn phí theo ngữ cảnh
CFG là một ngữ pháp đệ quy trái có ít nhất một sản phẩm thuộc loại này. Các quy tắc trong ngữ pháp không có ngữ cảnh chủ yếu là đệ quy. Trình phân tích cú pháp kiểm tra chương trình cụ thể có đáp ứng tất cả các quy tắc của ngữ pháp không theo ngữ cảnh hay không. Nếu nó đáp ứng, các trình phân tích cú pháp quy tắc này có thể tạo một cây phân tích cú pháp cho chương trình đó.
expression -> expression -+ termexpression -> expression - termexpression-> termterm -> term * factorterm -> expression/ factorterm -> factor factorfactor -> ( expression )factor -> id
Khai sinh ngữ pháp
Dẫn xuất ngữ pháp là một chuỗi các quy tắc ngữ pháp biến ký hiệu bắt đầu thành chuỗi. Một dẫn xuất chứng minh rằng chuỗi thuộc về ngôn ngữ của ngữ pháp.
Xuất phát ngoài cùng bên trái
Khi dạng thông tin đầu vào được quét và thay thế theo trình tự từ trái sang phải, nó được gọi là dẫn xuất ngoài cùng bên trái. Biểu mẫu thông tin gửi được dẫn xuất bởi phái sinh ngoài cùng bên trái được gọi là biểu mẫu thông tin gửi bên trái.
Nguồn gốc ngoài cùng bên phải
Quét dẫn xuất ngoài cùng bên phải và thay thế đầu vào bằng các quy tắc sản xuất, từ phải sang trái, trình tự. Nó được gọi là phái sinh bên phải. Biểu mẫu thông tin gửi có nguồn gốc từ phái sinh ngoài cùng bên phải được gọi là biểu mẫu thông tin gửi bên phải.
Syntax so với Lexical Analyzer
|
Trình phân tích cú pháp |
Lexical Analyzer |
|
Bộ phân tích cú pháp chủ yếu xử lý các cấu trúc đệ quy của ngôn ngữ. |
Bộ phân tích từ vựng giúp giảm bớt nhiệm vụ của bộ phân tích cú pháp. |
|
Bộ phân tích cú pháp hoạt động trên các mã thông báo trong một chương trình nguồn để nhận ra các cấu trúc có ý nghĩa trong ngôn ngữ lập trình. |
Trình phân tích từ vựng nhận dạng mã thông báo trong chương trình nguồn. |
|
Nó nhận đầu vào, dưới dạng mã thông báo, từ các máy phân tích từ vựng. |
Nó chịu trách nhiệm về tính hợp lệ của mã thông báo được cung cấp bởi trình phân tích cú pháp |
Nhược điểm của việc sử dụng Trình phân tích cú pháp
- Nó sẽ không bao giờ xác định xem một mã thông báo có hợp lệ hay không
- Không giúp bạn xác định xem một hoạt động được thực hiện trên một loại mã thông báo có hợp lệ hay không
- Bạn không thể quyết định rằng mã thông báo được khai báo và khởi tạo trước khi nó được sử dụng
Tóm lược
- Phân tích cú pháp là giai đoạn thứ hai của quá trình thiết kế trình biên dịch, sau phân tích từ vựng
- Trình phân tích cú pháp giúp bạn áp dụng các quy tắc cho mã
- Câu, Lexeme, Mã thông báo, Từ khóa và từ dành riêng, Từ nhiễu, Nhận xét, Dấu phân cách, Bộ ký tự, Số nhận dạng là một số thuật ngữ quan trọng được sử dụng trong Phân tích cú pháp trong xây dựng Trình biên dịch
- Phân tích cú pháp kiểm tra xem chuỗi đầu vào có được định dạng tốt hay không và nếu không, hãy từ chối nó
- Các kỹ thuật phân tích cú pháp được chia thành hai nhóm khác nhau: Phân tích cú pháp từ trên xuống, phân tích cú pháp từ dưới lên
- Từ vựng, Cú pháp, Ngữ nghĩa và lôgic là một số lỗi phổ biến xảy ra trong phương pháp phân tích cú pháp
- Ngữ pháp là một tập hợp các quy tắc cấu trúc mô tả một ngôn ngữ
- Biểu tượng quy ước ký hiệu có thể được chỉ ra bằng cách đặt phần tử trong dấu ngoặc vuông
- CFG là một ngữ pháp đệ quy trái có ít nhất một sản phẩm thuộc loại
- Dẫn xuất ngữ pháp là một chuỗi quy tắc ngữ pháp biến đổi ký hiệu bắt đầu thành chuỗi
- Trình phân tích cú pháp chủ yếu xử lý các cấu trúc đệ quy của ngôn ngữ trong khi trình phân tích từ vựng giúp giảm bớt nhiệm vụ của trình phân tích cú pháp trong DBMS
- Hạn chế của phương pháp phân tích cú pháp là nó sẽ không bao giờ xác định được mã thông báo có hợp lệ hay không