Kiểm tra 2.2

Cho một văn phạm G, Mục LR(0) văn phạm là một luật sinh của G

• Với một dấu chấm mục tại vị trí nào đó trong vế phải.

• Với một dấu chấm mục tại vị trí nào đó trong vế trái.

• Với một dấu + mục tại vị trí nào đó trong vế trái.

• Với một dấu - mục tại vị trí nào đó trong vế phải.

Giả sử G là một văn phạm với ký hiệu bắt đầu S, ta thêm một ký hiệu bắt đầu mới S' và luật sinh dạng nào dưới đây để được văn phạm mới G' gọi là văn phạm tăng cường.

• A.  S->S’

• A.  S’->S

• A.  S->aS’b

• A.  S->aS’

: Giả sử I là một tập các mục của văn phạm G thì bao đóng closure(I) là tập các mục được xây dựng từ I theo qui tắc sau:

• Đầu tiên là tất cả các mục của I được thêm cho closure(I). Sau đó nếu A → x.By thuộc closure(I) và B → z là một luật sinh thì thêm B → . z vào closure(I) nếu nó

  chưa có trong đó. Lặp lại bước này cho đến khi không thể thêm vào closure(I)

  được nữa.

   

• Nếu A → x.By thuộc closure(I) và B → z là một luật sinh thì thêm B → . z vàoclosure(I) nếu nó chưa có trong đó.

• Nếu A → x.By thuộc closure(I) và tồn tại B → z thì thêm B → z vào closure(I).

• Nếu A → x.By thuộc closure(I) và tồn tại B → z thì loại A → x.By khỏiclosure(I).

Goto(I, X), trong đó I là một tập các mục và X là một ký hiệu văn phạm là bao đóng của tập hợp

• Các mục A → xX.y sao cho A → x.Xy thuộc I

• Các mục A → x.Xy sao cho A → xX.y thuộc I

• Các mục A → xX.y thuộc I

• Các mục A → x.Xy thuộc I

Phát biểu nào dưới đây sai

• Phân tích cú pháp từ trên xuống có thể được xem như một nỗ lực tìm kiếm mộtdẫn xuất trái nhất cho chuỗi nhập

•          Phân tích cú pháp từ trên xuống là một quá trình xây dựng cây phân tích cúpháp bắt đầu từ nút gốc và phát sinh dần xuống lá

• Một dạng tổng quát của kỹ thuật phân tích từ trên xuống, gọi là phân tích cúpháp đệ quy lùi

• Một dạng tổng quát của kỹ thuật phân tích từ trên xuống, gọi là phân tích cú

  pháp đệ quy tiến 

Khi sử dụng phương pháp SLR để xây dựng một bảng phân tích cú pháp LR thì đây là phương pháp nào?

• Dễ cài đặt nhất

• Khó cài đặt nhất

• Hiệu quả nhất

• Đệ quy

Một văn phạm tạo ra nhiều hơn một cây phân tích cú pháp cho cùng một chuỗi nhập thì được gọi là gì?

• Văn phạm phi ngữ cảnh

• Văn phạm mơ hồ

• Văn phạm LL(1)

• Văn phạm LR(1)

Phương pháp Xây dựng một bảng phân tích cú pháp LR gồm những phương pháp nào?

• Simple LR

• Canonical LR

• Lookahead-LR

• Ba phương pháp: Simple LR, Lookahead-LR, Canonical LR

Phân tích cú pháp dự đoán không đệ qui cần:

• Duy trì một Stack và không cần ngầm định qua các lời gọi đệ quy.

• Ngầm định qua các lời gọi đệ quy.

• Được thiết kế dựa trên sơ đồ dịch cho các ký hiệu chưa kết thúc trong văn phạm

• Các luật sinh dạng A->aA; A->b

Ðịnh nghĩa FIRST(x):

• Giả sử x là một chuỗi các ký hiệu văn phạm, FIRST(x) là tập hợp các ký hiệu

  kết thúc mà nó bắt đầu một chuỗi dẫn xuất từ x.

   

• Nếu X là kí hiệu chưa kết thúc thì FIRST(X) là {X}

• Giả sử x là một chuỗi các ký hiệu văn phạm, FIRST(x) là tập hợp các ký hiệukhông kết thúc mà nó bắt đầu một chuỗi dẫn xuất từ x.

• Nếu X là kí hiệu kết thúc thì FIRST(X) là {X}