Phân tích cú pháp: Các kiểu phân tích cú pháp từ trên xuống và từ dưới lên của trình biên dịch

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 đã cho được kiểm tra để xác nhận các quy tắc và cấu trúc của ngữ pháp hì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 quy trình thiết kế trình biên dịch diễn ra sau giai đoạn phân tích từ vựng. Nó cũng đượ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 ngụ ý bởi ngữ pháp không ngữ cảnh hay không. Nếu đáp ứng, 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.

Phân tích cú pháp
Quy 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 mở có số dư cuối kỳ tương ứng
  • Mỗi khai báo có một loại và loại đó 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:

  • Kết án: Một câu là một nhóm ký tự trên một số bảng chữ cái.
  • Từ vựng: Từ vị là đơn vị cú pháp cấp thấp nhất của một ngôn ngữ (ví dụ: tổng, bắt đầu).
  • Token: Mã thông báo chỉ là một danh mục từ vựng.
  • Từ khóa và từ dành riêng – Nó là một mã định danh được sử dụng như một phần cố định trong cú pháp của câu lệnh. Đó 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 mã định danh.
  • Tiếng ồn từ – Các từ ồn ào là tùy chọn được chèn vào 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//Trống (dấu cách)
  • Dấu phân cách – Là thành phần cú pháp đánh dấu sự bắt đầu hoặc kết thúc của một đơn vị cú pháp nào đó. Giống như một câu lệnh hoặc biểu thức, “bắt đầu”…”kết thúc” hoặc {}.
  • Bộ ký tự – ASCII, Unicode
  • Định danh – Hạn chế về độ dài giúp bạn giảm khả năng đọc của câu.
  • Operabiểu tượng tor – + 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

Một phân tích cú pháp cũng kiểm tra xem chuỗi đầu vào có được định dạng đúng hay không và nếu không, hãy từ chối nó.

Phân tích cú pháp

Sau đây là các nhiệm vụ quan trọng được trình phân tích 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ả lỗi rõ ràng và chính xác.
  • Khôi phục lỗi để tiếp tục và tìm thêm lỗi trong mã.
  • Không ảnh hưởng đến việc biên soạn 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

Kỹ thuật phân tích cú pháp được chia thành hai nhóm khác nhau:

  • Phân tích 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 từ trên xuống, cây phân tích bắt đầu từ gốc và sau đó tiến tới các lá.

Hai loại phân tích từ trên xuống là:

  1. Phân tích dự đoán:

Phân tích dự đoán có thể dự đoán sản phẩm nào sẽ được sử dụng để thay thế chuỗi đầu vào cụ thể. Trình phân tích cú pháp dự đoán sử dụng điểm nhìn về phía trước, hướng tới các ký hiệu đầu vào tiếp theo. Quay lại không phải là vấn đề với kỹ thuật phân tích cú pháp này. Nó được gọi là Trình phân tích cú pháp LL(1)

  1. Phân tích cú pháp gốc đệ quy:

Kỹ thuật phân tích cú pháp này phân tích đệ quy dữ liệu đầu vào để tạo thành cây prase. Nó bao gồm một số hàm nhỏ, mỗi hàm dùng cho một hàm không kết thúc 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 bắt đầu bằng phần còn lại và sau đó xử lý về gốc của nó. Nó còn được gọi là phân tích cú pháp giảm ca. 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 thường gặp xảy ra khi phân tích cú pháp trong phần mềm hệ thống

  • từ vựng: Tên của một mã định danh được gõ sai
  • Cú pháp: dấu ngoặc đơn không cân bằng hoặc thiếu dấu chấm phẩy
  • 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 phải có khả năng 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 phải có khả năng xử lý lỗi đó 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 ở nhiều 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

Phục hồi 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 khắc phục. Đ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ụ: việc thêm dấu chấm phẩy bị thiếu sẽ có trong phương thức khôi phục chế độ câu lệnh. Tuy nhiên, người thiết kế phân tích cú pháp cần phải cẩn thận 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 đến dấu phân cách, như dấu chấm phẩy. Đây là phương pháp khôi phục lỗi đơn giản.
  • Trong loại phương pháp phục hồi này, trình phân tích cú pháp từ chối các ký hiệu đầu vào từng cái một 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. Các mã thông báo đồng bộ hóa 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ến hành phân tích cú pháp từ vị trí của nó. Nó thực hiện hiệu chỉnh trên đầu vào còn lại. Nó có thể thay thế 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.

Lỗi sản xuất

  • Phục hồi lỗi sản xuất mở rộng ngữ pháp cho ngôn ngữ tạo ra các cấu trúc lỗi. 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 sẽ thực hiện ít thay đổi nhất có thể trong khi xử lý chuỗi đầu vào không chính xác. Cho chuỗi đầu vào a và ngữ pháp c không chính xác, thuật toán sẽ tìm kiếm cây phân tích cú pháp cho chuỗi b có liên quan. 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 an thành b là càng ít càng tốt.

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 gán 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, âm vị học và cú pháp. Nó có khả năng mô tả nhiều cú pháp của ngôn ngữ lập trình.

Quy tắc ngữ pháp hình thức

  • Ký hiệu không kết thúc 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 có tính đệ 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 bao quanh phần tử trong dấu ngoặc vuông. Đó là một chuỗi tùy ý các trường hợp của phần tử có thể được chỉ ra bằng cách bao quanh phần tử trong dấu ngoặc nhọn theo sau là ký hiệu dấu hoa thị, { … }*.

Đó là sự lựa chọn thay thế có thể sử dụng ký hiệu 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 Terminal và Non-terminal

1.Thiết bị đầu cuối:

  • Các chữ cái viết thường trong bảng chữ cái như a, b, c,
  • Operacác ký hiệu tor như +,-, *, v.v.
  • Các ký hiệu chấm câu như dấu ngoặc đơn, dấu băm, dấu phẩy
  • 0, 1,…, 9 chữ số
  • Các chuỗi in đậm như id hoặc if, bất cứ thứ gì đại diện cho một ký hiệu đầu cuối duy nhất

2.Nonterminal:

  • Các chữ cái viết hoa như A, B, C
  • Tên in nghiêng chữ 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 dạng sản phẩm thuộc loại này. Các quy tắc trong ngữ pháp phi ngữ cảnh chủ yếu là đệ quy. Trình phân tích cú pháp kiểm tra xem chương trình cụ thể có đáp ứng tất cả các quy tắc của Ngữ pháp không ngữ cảnh hay không. Nếu đáp ứng được, các bộ phân tích cú pháp quy tắc này có thể tạo cây phân tích cú pháp cho chương trình đó.

expression -> expression -+ term
expression -> expression – term 
expression-> term
term  -> term * factor
term -> expression/ factor
term  -> factor factor
factor ->  ( expression )
factor -> id

Đạo hàm ngữ pháp

Đạo hàm ngữ pháp là một chuỗi 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ữ ngữ pháp.

Đạo hàm ngoài cùng bên trái

Khi dạng câu của đầu vào được quét và thay thế theo trình tự từ trái sang phải, nó được gọi là đạo hàm ngoài cùng bên trái. Dạng câu có nguồn gốc từ đạo hàm ngoài cùng bên trái được gọi là dạng câu bên trái.

Đạo hàm ngoài cùng bên phải

Quét đạo hàm ngoài cùng bên phải và thay thế đầu vào bằng quy tắc sản xuất, từ phải sang trái, tuần tự. Nó được gọi là đạo hàm ngoài cùng bên phải. Dạng câu có nguồn gốc từ đạo hàm ngoài cùng bên phải được gọi là dạng câu phải.

Cú pháp so với Trình phân tích từ vựng

Trình phân tích cú pháp Máy phân tích từ vựng
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.
Trình phân tích cú pháp hoạt động trên các mã thông báo trong chương trình nguồn để nhận dạng các cấu trúc có ý nghĩa trong ngôn ngữ lập trình. Bộ 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ừ 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

máy 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 liệu mã thông báo có hợp lệ hay không
  • Không giúp bạn xác định xem một thao tác được thực hiện trên loại mã thông báo có hợp lệ hay không
  • Bạn không thể quyết định mã thông báo đó được khai báo và khởi tạo trước khi nó được sử dụng

Tổng kết

  • 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, diễn ra 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, Từ vựng, Mã thông báo, Từ khóa và từ dành riêng, Từ ồn ào, Nhận xét, Dấu phân cách, Bộ ký tự, Mã định danh 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 đúng không và nếu không, hãy từ chối nó
  • 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à logic là một số lỗi thường gặp trong quá trình phân tích cú pháp
  • Ngữ pháp là 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
  • Đạo hàm ngữ pháp là một chuỗi quy tắc ngữ pháp biến ký hiệu bắt đầu thành chuỗi
  • 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ữ trong khi 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 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