Chuyển đổi một ngữ pháp vào LL (1) ngữ pháp: một số vấn đề

Question

này không chính xác bài tập về nhà nhưng nó có liên quan đến nghiên cứu của tôi:

Một ngữ pháp ví dụ như:

E -> E + E | E * E | -E | (E) | id

Sau khi loại bỏ sự mơ hồ nó trở thành (bắt đầu từ điều hành ưu tiên thấp nhất)

E->-F|F 
F->F+G|G 
G->G*H|H 
H->(E)|id 

Và sau khi loại bỏ các đệ quy trái và thanh toán trái (không cần thiết trong trường hợp này) các LL1 ngữ pháp cuối cùng là:

E->-F|F 
F->GF' 
F'->+GF'|e 
G->HG' 
B->*HG'|e 
H->(E)|id 

Mà cho một lỗi bảng phân tích cú pháp miễn phí mà hoạt động tốt. Bây giờ về vấn đề này tôi đang phải đối mặt, cho rằng ngữ pháp là như thế này:

E -> E + E | E * E | id = E | (E) | id

Bây giờ tôi không thể tạo ra một bảng phân tích cú pháp mà không có xung đột, có nghĩa là ngữ pháp cuối cùng của tôi không phải là LL1. Dưới đây là các bước:

sau khi loại bỏ sự mơ hồ:

E->id=F|F 
F->F+G|G 
G->G*H|H 
H->(E)|id 

Và sau khi loại bỏ các đệ quy trái và thanh toán trái, ngữ pháp trở thành:

E->id=F|F 
F->GF' 
F'->+GF'|e 
G->HG' 
B->*HG'|e 
H->(E)|id 

Nhưng có sự mâu thuẫn trong bảng Parser mà tôi không thể loại bỏ, có nghĩa là có một số bước mà tôi đã bỏ lỡ, hoặc có một số sai lầm trong các bước mà tôi không thể tìm thấy. Xin vui lòng cho tôi biết những gì tôi đã làm sai, và làm thế nào để sửa lỗi này. Tôi đã làm việc về vấn đề này trong một thời gian dài.

Answer 1

Hãy nói rằng:

E -> E+E|E*E|id=E|(E)|id 

sẽ trở thành:

E -> E+E|E*E|(E)|E' 
E' -> id=E|id 

sau đó bạn có thể đi với loại bỏ sự mơ hồ và trái đệ quy và nhận được:

E -> GF  FIRST(E) = FIRST(G) 
F -> +GF|e 
G -> HG'  FIRST(G) = FIRST(H) 
G' -> *HG'|e 
H -> (E)|E' FIRST(H) = {(} + FIRST(E') = {(, id} 
E' -> idE'' FIRST(E') = {id} 
E'' -> =E|e FIRST(E'') = {=} + {#} 

Tất nhiên, vấn đề là, bạn mất quyền ưu tiên của toán tử đã cho.

Các ngữ pháp sẽ không được LL (1) nếu cho bất kỳ không thuộc đầu cuối N, sẽ có bất kỳ yếu tố chung trong FIRST(N -> a) và FIRST(N -> b) cho N -> a, N -> b là tác phẩm khác nhau từ N.

Như bạn thấy, thêm một sản phẩm N -> id= trong bất kỳ nơi nào khác sẽ vi phạm quy tắc đó.

Bạn có thể tạo ngữ pháp LL(2) (nhưng điều này có thể không phải là điều bạn muốn), có thể có sản xuất id=E ở bất kỳ nơi nào. (FIRST2 bộ bao gồm các chuỗi gồm 2 phần tử).

Ngoài ra, nếu bạn nhìn vào ngữ pháp được trình bày thêm một lần nữa:

E -> E+E|E*E|id=E|(E)|id 

Đó là một khả năng rất cao, mà ưu tiên điều hành tôi đã thực hiện trong dung dịch trên là một trong những quyền cho ứng dụng thực tế. Kiểm tra nó ra!