Từ 1 tới 8 trên tổng số 8 kết quả

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

  1. #1
    Ngày gia nhập
    10 2007
    Bài viết
    7

    Mặc định [ Solved ]Thuật toán: tiên đoán toán tử (predictive parse)

    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!!!!
    Đã được chỉnh sửa lần cuối bởi ngovan : 30-05-2008 lúc 10:05 PM.
    write it on your heart that every day is the best day of the year

  2. #2
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    469

    Trích dẫn Nguyên bản được gửi bởi ngovan Xem bài viết
    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 )
    Đã được chỉnh sửa lần cuối bởi Ada : 01-06-2008 lúc 07:42 AM.

  3. #3
    Ngày gia nhập
    10 2007
    Bài viết
    7

    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???
    write it on your heart that every day is the best day of the year

  4. #4
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    469

    Trích dẫn Nguyên bản được gửi bởi ngovan Xem bài viết
    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?

  5. #5
    Ngày gia nhập
    10 2007
    Bài viết
    7

    Code:
    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!!!!!!!!!!!!!
    Đã được chỉnh sửa lần cuối bởi ngovan : 01-06-2008 lúc 11:22 PM.
    write it on your heart that every day is the best day of the year

  6. #6
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    469

    Mặc định [ Solved ]Thuật toán: tiên đoán toán tử (predictive parse)

    Trích dẫn Nguyên bản được gửi bởi ngovan Xem bài viết
    Code:
    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ì.

  7. #7
    Ngày gia nhập
    10 2007
    Bài viết
    7

    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.
    write it on your heart that every day is the best day of the year

  8. #8
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    469

    Trích dẫn Nguyên bản được gửi bởi ngovan Xem bài viết
    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++.

Các đề tài tương tự

  1. Lập trình C các bạn cho tớ gợi ý về bài toán sau với :ứng dụng hàng đợi có ưu tiên vào cài đặt thuật toán dijkstra
    Gửi bởi vu thien phuong trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 03-09-2012, 05:32 PM
  2. Thuật toán đệ qui và khử đệ qui.In ra 100 so Fibonacci đầu tiên!!!
    Gửi bởi vietanh trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 26-02-2012, 12:17 AM
  3. Thuật toán tìm số lớn nhất và vị trí đầu tiên,cuối cùng của nó. help?
    Gửi bởi rong3sao trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 8
    Bài viết cuối: 09-10-2009, 04:41 PM
  4. giúp em thuật toán cộng 100 số TN đầu tiên
    Gửi bởi khongbiet00biet trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 10-03-2009, 09:44 PM
  5. [ Solved ]Thuật toán để tạo ra công thức bất kì
    Gửi bởi caibangbangchu trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 26
    Bài viết cuối: 19-11-2008, 12:18 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn