Phân Tích Văn Phạm và Cây Cú Pháp trong LR(0) - CSC1001. Môn Chương trình dịch (Phenika) | Đại học Trường Đại học Phenika.

lOMoAR cPSD| 59285474 Câu 1
a. Closure của các item trong văn phạm:
- Closure của item E → .A := B là {E → .A := B, A := .B, B → .A}
- Closure của item E → .B là {E → .B, B → .A}
- Closure của item A → .+B là {A → .+B, B → .A}
- Closure của item A → .id là {A → .id}
- Closure của item B → .A là {B → .A, A := .B, B → .A}
b. Đồ thị DFA của văn phạm:
- Trạng thái 0 là trạng thái bắt đầu.
- Trạng thái 1 là trạng thái chấp nhận.
- Các mũi tên biểu thị các chuyển đổi trạng thái. Ví dụ, từ trạng thái 0, nếu đọc được ký tự
E,thì chuyển sang trạng thái 1.
c. Bản phân tích cú pháp LR của văn phạm: lOMoAR cPSD| 59285474
d. Văn phạm trên có phải LR(0) hay không? Giải thích?
Văn phạm trên không phải là LR(0) vì có sự trùng lặp item trong bảng phân tích cú pháp LR.
Ví dụ, ở trạng thái 0, khi đọc được ký tự A, có thể chuyển sang trạng thái 3 hoặc trạng thái 4
tùy thuộc vào ngữ cảnh. Điều này vi phạm điều kiện cần của LR(0) là không có trùng lặp
item trong bảng phân tích cú pháp LR. Câu 2. void reduce(int p) { int k,ad; char src,*dest; switch(p) { case 1: dest="E+T"; src='E'; break; case 2: dest="T"; src='E'; lOMoAR cPSD| 59285474 break; case 3: dest="T*F"; src='T'; break; case 4: dest="F"; src='T'; break; case 5: dest="(E)"; src='F'; break; case 6: dest="i"; src='F'; break; default: dest="\0"; src='\0'; break; } for(k=0;k { pop() ; popb(); } pushb(src); switch(src) { case 'E':ad=0; break; case 'T':ad=1; break; case 'F':ad=2; break; default: ad=-1; break; } push(gotot[TOS()][ad]); }
Xâu (a+b)*c có được đoán nhận bởi văn phạm trên hay không?
Có, xâu (a+b)*c được đoán nhận bởi văn phạm trên.
2. Vẽ cây cú pháp của xâu phân tích ở câu 2 E lOMoAR cPSD| 59285474 | | | +---T | | | +---F | | | +---( | | | +---E | | | +---T | | | +---F | | | +---a E | +---T | | | +---F | | | +---b E +---F | +---c
3. Đưa xâu về dạng hậu tố abc+*
4. Tính FIRST và FOLLOW của các kí hiệu của văn phạm này. FIRST: E: {a, (, i} T: {a, (, i} F: {a, (, i} FOLLOW: E: {), $} T: {+, ), $} F: {+, ), $}