Tự động hóa dữ liệu và phân tích cú pháp kéo xuống
Phân tích cú pháp được sử dụng để lấy một chuỗi bằng cách sử dụng các quy tắc sản xuất của ngữ pháp. Nó được sử dụng để kiểm tra khả năng chấp nhận của một chuỗi. Trình biên dịch được sử dụng để kiểm tra xem một chuỗi có đúng cú pháp hay không. Một trình phân tích cú pháp lấy các đầu vào và xây dựng một cây phân tích cú pháp.
Trình phân tích cú pháp có thể có hai loại -
Top-Down Parser - Phân tích cú pháp từ trên xuống bắt đầu từ trên cùng với ký hiệu bắt đầu và dẫn xuất một chuỗi bằng cách sử dụng cây phân tích cú pháp.
Bottom-Up Parser - Phân tích cú pháp từ dưới lên bắt đầu từ dưới cùng với chuỗi và đến ký hiệu bắt đầu bằng cách sử dụng cây phân tích cú pháp.
Thiết kế trình phân tích cú pháp từ trên xuống
Để phân tích cú pháp từ trên xuống, PDA có bốn kiểu chuyển đổi sau:
Đặt thiết bị đầu cuối không phải thiết bị đầu cuối ở phía bên trái của sản phẩm ở trên cùng của ngăn xếp và đẩy chuỗi bên phải của nó.
Nếu biểu tượng trên cùng của ngăn xếp khớp với biểu tượng đầu vào đang được đọc, hãy bật nó lên.
Đẩy biểu tượng bắt đầu 'S' vào ngăn xếp.
Nếu chuỗi đầu vào được đọc đầy đủ và ngăn xếp trống, hãy chuyển đến trạng thái cuối cùng 'F'.
Thí dụ
Thiết kế trình phân tích cú pháp từ trên xuống cho biểu thức "x + y * z" cho ngữ pháp G với các quy tắc sản xuất sau:
P: S → S + X | X, X → X * Y | Y, Y → (S) | Tôi
Solution
Nếu PDA là (Q, ∑, S, δ, q 0 , I, F), thì phân tích cú pháp từ trên xuống là -
(x + y * z, I) ⊢ (x + y * z, SI) ⊢ (x + y * z, S + XI) ⊢ (x + y * z, X + XI)
⊢ (x + y * z, Y + XI) ⊢ (x + y * z, x + XI) ⊢ (+ y * z, + XI) ⊢ (y * z, XI)
⊢ (y * z, X * YI) ⊢ (y * z, y * YI) ⊢ (* z, * YI) ⊢ (z, YI) ⊢ (z, zI) ⊢ (ε, I)
Thiết kế trình phân tích cú pháp từ dưới lên
Để phân tích cú pháp từ dưới lên, PDA có bốn kiểu chuyển đổi sau:
Đẩy biểu tượng đầu vào hiện tại vào ngăn xếp.
Thay thế phía bên phải của sản phẩm ở trên cùng của ngăn xếp bằng phía bên trái của nó.
Nếu phần trên cùng của phần tử ngăn xếp khớp với ký hiệu đầu vào hiện tại, hãy bật nó lên.
Nếu chuỗi đầu vào được đọc đầy đủ và chỉ khi ký hiệu bắt đầu 'S' vẫn còn trong ngăn xếp, hãy bật nó và chuyển đến trạng thái cuối cùng là 'F'.
Thí dụ
Thiết kế trình phân tích cú pháp từ trên xuống cho biểu thức "x + y * z" cho ngữ pháp G với các quy tắc sản xuất sau:
P: S → S + X | X, X → X * Y | Y, Y → (S) | Tôi
Solution
Nếu PDA là (Q, ∑, S, δ, q 0 , I, F), thì phân tích cú pháp từ dưới lên là -
(x + y * z, I) ⊢ (+ y * z, xI) ⊢ (+ y * z, YI) ⊢ (+ y * z, XI) ⊢ (+ y * z, SI)
⊢ (y * z, + SI) ⊢ (* z, y + SI) ⊢ (* z, Y + SI) ⊢ (* z, X + SI) ⊢ (z, * X + SI)
⊢ (ε, z * X + SI) ⊢ (ε, Y * X + SI) ⊢ (ε, X + SI) ⊢ (ε, SI)