[ Solved ]Thuật toán: tiên đoán toán tử (predictive parse)

[ngovan]

mình đang có một bài tập liên quan tới thuật toán :xây dựng bảng tiên đoán M trong chương trình phân tích cú pháp bằng phương pháp tiên đoán(LL).BẠn nào biết có thể chỉ cho mình thuật toán được không .Thankkkk!!!!

[Ada]

mình đang có một bài tập liên quan tới thuật toán :xây dựng bảng tiên đoán M trong chương trình phân tích cú pháp bằng phương pháp tiên đoán(LL).BẠn nào biết có thể chỉ cho mình thuật toán được không .Thankkkk!!!!

Lập bảng phân tích cho văn phạm LL(1)

Ký hiệu

A, B là ký hiệu không kết thúc; a, b là ký hiệu kết thúc; w, v là chuỗi ký hiệu bất kỳ; ε là chuỗi rỗng; A → w là luật của văn phạm.



Thuật toán

1. Dựng các tập Fi (first-set)

1.1. Với mọi A → w, khởi trị Fi(A) := Ø và Fi(w) := Ø
1.2. Với mọi B → w, xác định các Fi(w):
1.2.1. Fi(a v) = { a } với mọi a
1.2.2. Fi(A v) = Fi(A) với mọi A với Fi(A) không chứa ε.
1.2.3. Fi(A v) = Fi(A) \ { ε } ∪ Fi(v) với mọi A với Fi(A) chứa ε.
1.2.4. Fi(ε) = { ε }
1.3. Với mọi A → w, Fi(A) := Fi(A) ∪ Fi(w)
1.4. Lặp các bước 1.2 và 1.3 đến khi mọi Fi ngừng thay đổi.



2. Dựng các tập Fo (follow-set)

2.1. Với mọi A, khởi trị Fo(A) := Ø
2.2. Với mọi B → w A v, bổ sung Fo(A):
2.2.1. Nếu Fi(v) chứa a, Fo(A) := Fo(A) ∪ {a}
2.2.2. Nếu Fi(v) chứa ε, Fo(A) := Fo(A) ∪ Fo(B)
2.3. Lặp bước 2.2 đến khi mọi Fo ngừng thay đổi.



3. Dựng bảng phân tích T (parse table)

3.1. Với mọi A mọi a, khởi trị T[A,a] := Ø
3.2. Với mọi A → w mọi a, nếu Fi(w) chứa a, hoặc Fi(w) chứa ε và Fo(A) chứa a, thì
T[A,a] := T[A,a] ∪ {A → w}

(Sau khi dựng bảng T, mọi ô T[A,a] của bảng chỉ chứa nhiều nhất 1 luật. Bộ phân tích cú pháp LL(1)sẽ chọn luật T[A,a] khi thấy ký hiệu A trên đỉnh stack của nó đồng thời thấy ký hiệu a từ văn bản vào.)


( Nguồn: http://en.wikipedia.org/wiki/LL_parser )

[ngovan]

cảm ơn Ada dã giúp.mình cũng biết thuật toán như thế.mình đã xem những chương trình mẩu toàn thấy người ta viết bằng java ,mình thì chưa biết gì về java cả ,nên cũng chẳng hiểu gì.mình đang viết chương trình bằng C nhưng tới hàm first và follow để tạo bảng tiên đoán thì pó tay.có thể giúp mình được không???

[Ada]

cảm ơn Ada dã giúp.mình cũng biết thuật toán như thế.mình đã xem những chương trình mẩu toàn thấy người ta viết bằng java ,mình thì chưa biết gì về java cả ,nên cũng chẳng hiểu gì.mình đang viết chương trình bằng C nhưng tới hàm first và follow để tạo bảng tiên đoán thì pó tay.có thể giúp mình được không???

Vì sao bó tay? Bạn có thể nói rõ hơn không?

[ngovan]

foreach terminal T1...Tn
          nullable (T)=false
          foreach production X->Y1,y1....Yn
          foreach Y1 in Y1 to Yk ,

           then nullable (X)=true 
           foreach i in 1 to k ,foreach j in 1to k
        if foreach Y1 in Yi-1 to Yk,nullable (Yk)=true then first then first (Y1 )subnet of First(X)
        if foreach Yk in Yi+1 to Yj-1,nullable (Yx)=true
        then follow(X) subnet ò follow (Y1)
       if foreach Y(x) in Yi-1 to Yj-1,nullable (X)=true
            then first (Yi) subnet of follow (Yi)

 
foreach Yx in Y1 in Y

bạn có thể giải thích rõ hơn dùm mình đoạn mã trên đươc ko?minh tai trên mạng về,nhưng khó hiểu quá
Với lại minh ko biết đoạn code vể chương trình kiểm tra lỗi.
nếu được bạn có thể code dùm mình về first,follow và kiêm ta xử lý lỗi được ko??.thank!!!!!!!!!!!!!

[Ada]

foreach terminal T1...Tn
          nullable (T)=false
          foreach production X->Y1,y1....Yn
          foreach Y1 in Y1 to Yk ,

           then nullable (X)=true 
           foreach i in 1 to k ,foreach j in 1to k
        if foreach Y1 in Yi-1 to Yk,nullable (Yk)=true then first then first (Y1 )subnet of First(X)
        if foreach Yk in Yi+1 to Yj-1,nullable (Yx)=true
        then follow(X) subnet ò follow (Y1)
       if foreach Y(x) in Yi-1 to Yj-1,nullable (X)=true
            then first (Yi) subnet of follow (Yi)

 
foreach Yx in Y1 in Y

bạn có thể giải thích rõ hơn dùm mình đoạn mã trên đươc ko?minh tai trên mạng về,nhưng khó hiểu quá
Với lại minh ko biết đoạn code vể chương trình kiểm tra lỗi.
nếu được bạn có thể code dùm mình về first,follow và kiêm ta xử lý lỗi được ko??.thank!!!!!!!!!!!!!

Đoạn mã gì đâu. Chỉ là 1 đoạn giả mã thôi. Không có định nghĩa ký hiệu, chính tả lộn tùng phèo, đoạn giữa thiếu lung tung. Bạn đừng để ý làm gì.

[ngovan]

vậy ah.theo bạn thì bài này viết bằng VB được ko? hay là viêt bằng C thì hay hơn.

[Ada]

vậy ah.theo bạn thì bài này viết bằng VB được ko? hay là viêt bằng C thì hay hơn.

Mình nghĩ là viết bằng ngôn ngữ nào cũng được. VB mình không biết. Viết bằng C thì sẽ hơi mệt vì ngôn ngữ C mức thấp, bạn phải tự cài đặt các khái niệm trừu tượng cơ bản như tập hợp. Theo mình tốt hơn cả là bạn viết bằng một ngôn ngữ hướng đối tượng như C# hay C++.