Giáo trình môn học Trình biên dịch - Chương 5: Biên dịch trực tiếp cú pháp

CHƯƠNG 5 BIÊN DỊCH TRỰC TIẾP CÚ PHÁP Có hai khái niệm về các luật ngữ nghĩa có liên quan đến luật sinh: định nghĩa trực tiếp cú pháp và lược đồ dịch. - Định nghĩa trực tiếp cú pháp. - Lược đồ dịch. Chuỗi nhập→ cây phân tích→ đồ thị phụ thuộc→ → đánh giá thứ tự các luật ngữ nghĩa. Hình 5.0. Khái niệm về dịch trực tiếp cú pháp Khái niệm tổng quan của biên dịch trực tiếp cú pháp 5.1. Định nghĩa trực tiếp cú pháp Là văn phạm phi ngữ cảnh mà trong đó mỗi ký hiệu văn phạm có tập thuộc tính. Tập thuộc tính này có hai loại: thuộc tính tổng hợp và thuộc tính kế thừa. Cây cú pháp có giá trị thuộc tính ở mỗi nút được gọi là cây phân tích chú thích. Dạng của định nghĩa trực tiếp cú pháp Mỗi luật sinh có dạng A → α đều có một tập luật ngữ nghĩa có dạng b:= f (c1, c2, , ck) với f là hàm số và: 1. b là thuộc tính tổng hợp của A và c1, c2, , ck là các thuộc tính của ký hiệu văn phạm của luật sinh, hoặc 2. b là thuộc tính kế thừa của một trong các ký hiệu văn phạm bên vế phải của luật sinh và c1, c2, , ck là các thuộc tính của các ký hiệu văn phạm của luật sinh. Thí dụ 5.1. Định nghĩa trực tiếp cú pháp ở bảng 5.1. Bảng 5.1. Định nghĩa trực tiếp cú pháp cho bảng tính đơn giản Luật sinh Luật ngữ nghĩa L → En Print (E.val) E → E1 + T E.val: = E1.val + T.val E → TE.val: = T.val E.val: = T.val T → T1* F T.val: = T.val x F.val T → FT.val: = F.val T.val: = F.val F → (E) F.val: = E.val F → digit F.val: = digit . lexval Thuộc tính tổng hợp Định nghĩa trực tiếp cú pháp dùng các thuộc tính tổng hợp gọi là định nghĩa thuộc tính S. Thuộc tính S của một nút có thể được từ các thuộc tính ở mỗi nút từ dưới lên. L Thí dụ 5.2. Định nghĩa thuộc tính S ở thí dụ 5.1 E.val = 19 E.val = 15 + T.val = 4 T.val = 15 F.val = 5 F.val = 3 n F.val = 4 T.val = 3 * digit.lexval = 4 digit.lexval = 5 digit.lexval = 3 Hình 5.1. Cây phân tích chú thích 3 * 5 + 4n Thuộc tính kế thừa Thuộc tính kế thừa là thuộc tính mà giá trị của nó ở một nút trên cây phân tích được xác định bởi thuộc tính cha mẹ và/hoặc anh chị của nút đó. Thí dụ 5.3. Sự khai báo được tạo bởi ký hiệu không kết thúc D trong định nghĩa trực tiếp cú pháp ở (bảng 5.2). Bảng 5.2. Định nghĩa trực tiếp cú pháp với thuộc tính kế thừa L.in. Luật sinh Luật ngữ nghĩa D → TL L.in: = T.type T → int T.type: = integer T → real T.type: = real L → L1, id L1.in: = L.in L → id Addtype (id.entry, L.in) Hình 5.2 là cây phân tích chú thích cho câu real id1, id2, id3. D T.type = real L.in = real L.in = real L.in = real , id3 real id2, id1 Hình 5.2. Cây phân tích với thuộc tính kế thừa in ở mỗi nút có nhãn L. Đồ thị phụ thuộc Các sự phụ thuộc trung gian: thuộc tính kế thừa và tổng hợp trên các nút của cây phân tích có thể được miêu tả bằng đồ thị có hướng được gọi là đồ thị phụ thuộc (dependency graph). Cây phụ thuộc của một cây phân tích cho trước, được xây dựng như sau: for với mỗi nút n trên cây phân tích do for với mỗi thuộc tính a của ký hiệu văn phạm tại nút n do - xây dựng nút trên đồ thị phụ thuộc cho a; for với mỗi nút n trên cây phân tích do for với mỗi luật ngữ nghĩa b:= f (c1, c2, , ck) tương ứng với luật sinh được dùng tại nút n for i := 1 to k do xây dựng cạnh đi từ nút của c1 đến nút b. Thí dụ 5.4. Khi ta dùng luật sinh E → E1 + E2 trên cây phân tích, chúng ta thêm các cạnh sau vào (H.5.3) chúng ta sẽ được đồ thị phụ thuộc. Luật sinh Luật ngữ nghĩa E → E1 + E2 E.val := E1.val + E2.val E val E1 E2 val+val Hình 5.3. Đồ thị phụ thuộc của cây phân tích cho E Ỉ E1+ E2 Thí dụ 5.5. (H.5.4) là đồ thị phụ thuộc cho cây phân tích của (H.5.2). Đánh giá thứ tự Trong sắp xếp logic topo, các thuộc tính phụ thuộc c1, c2, , ck trong luật ngữ nghĩa b:= f (c1, c2, , ck) được đánh giá trước f. T real 4 type in 5 6L 3 entry 7 9 L L 8 id2 2 entry in id1 10 1 entry id3 D Hình 5.4. Đồ thị phụ thuộc cho cây phân tích ở (H.5.2). Thí dụ 5.6. Mỗi một cạnh của đồ thị phụ thuộc ở (H.5.4.) đi từ số thấp đến số cao của các nút. Từ thứ tự logic topo chúng ta sẽ có chương trình. Chúng ta viết an cho thuộc tính liên quan đến nút được đánh số n. trên đồ thị phụ thuộc. a4 := real a5 := a4 addtype (id3.entry, a5); a7 := a5 addtype (id2.entry, a7); a9 := a7 addtype (id1.entry, a9); Một số phương pháp được đề nghị cho việc đánh giá các luật ngữ nghĩa 1. Phương pháp cây phân tích (parse-tree method) 2. Phương pháp cơ sở luật (rule-based method) 3. Phương pháp rõ ràng 5.2. Cấu trúc của cây phân tích Cây cú pháp: là dạng thu gọn của cây phân tích, được dùng để biểu diễn cho cấu trúc ngôn ngữ. Cây phân tích ở (H.5.1) sẽ được vẽ lại thành cây cú pháp. Xây dựng cây cú pháp cho biểu thức Chúng ta sẽ dùng các hàm để tạo các nút cho cây cú pháp của biểu thức với phép toán hai ngôi. Mỗi hàm trả về con trỏ chỉ đến nút mới được tạo ra. 1. mknode(op, left, right). 2. mkleaf(id, entry). 3. mkleaf(num, val). + ∗ 4 3 5 Thí dụ 5.7.Một chuỗi các hàm được gọi để tạo cây cú pháp cho biểu thức a – 4 + c ở (H.5.5). (1) p1 := mkleaf(id, entry a); (4) p4 := mkleaf(id, entry c); (2) p2 := mkleaf(num, 4); (5) p5 := mknode(‘+’, p3, p4)’ (3) p3 := mknode(‘-‘, p1, p2) + − id Num 4 id chỉ đến vị trí của c chỉ đến vị trí của a Hình 5.5. Cây cú pháp cho biểu thức a – 4 + c Định nghĩa trực tiếp cú pháp và cấu trúc cây cú pháp Thí dụ ở bảng 5.3 là định nghĩa thuộc tính S dùng để xây dựng cây cú pháp cho biểu thức số học cộng (+) và trừ (-). Bảng 5.3. Định nghĩa trực tiếp cú pháp cho cấu trúc cây cú pháp của biểu thức Luật sinh Các luật ngữ nghĩa E → E1 + T E. nptr: = mknode(‘+’, E1 .nptr, T. nptr) E → E1 – T E. nptr: = mknode(‘-‘, E1 .nptr, T.nptr) E → T E. nptr: = T. nptr T → (E) T. nptr: = E. nptr T → id T. nptr: = mkleaf(id, id, entry) T → num T. nptr: = mkleaf(num, num, val) Thí dụ 5.8. Cây phân tích chú thích dùng để miêu tả cây cú pháp cho biểu thức a - 4 + c được trình bày ở (H.5.6). E nptr E id − T E nptr T T id num nptr + nntr nptr + −− con trỏ chỉ đến c trong bảng danh biểunum 4 id con trỏ chỉ đến a trong bảng danh biểu Hình 5.6. Tổ chức của cây cú pháp cho biểu thức a – 4 + c Đồ thị có hướng không lặp vòng miêu tả biểu thức Đồ thị có hướng không lặp vòng (directed acyclic graph) gọi tắt là dag. ∗ + + ∗ a d− cb Hình 5.7. Dag cho biểu thức a + a * (b – c) + (b – c) * d. Bảng 5.4. Các lệnh để tạo DAG ở (H.5.7) Hàng Lệnh Hàng Lệnh 1 p1 := mkleaf(id, a) 8 p8 := mkleaf(id, b) 2 p2 := mkleaf(id, a) 9 p9 := mkleaf(id, c) 3 p3 := mkleaf(id, b) 10 p10 := mknode(’ −‘, p8, p5) 4 p4 := mkleaf(id, c) 11 p11 := mkleaf(id, d) 5 p5 := mknode(‘−‘, p3, p4) 12 p12 := mknode(‘*’, p10, p11) 6 p6 := mknode(‘*’, p2, p5) 13 p13 := mknode(‘+’, p7, p12) 7 p7 := mknode(‘+’, p1, p6) Mẫu tin tượng trưng cho nút được lưu chứa trong dãy như ở (H.5.8). Phép gán Dag i := i + 10 := + 1 id Chỉ đến danh biểu i 2 num 10 3 + 1 2 4 := 1 3 5 .... Biểu diễn cấu trúc dữ liệu i 10 Giải thuật 5.1. Phương pháp số trị cho việc tạo nút của dag. Giả sử mỗi nút là một phần tử của dãy ở (H.5.8). Nhập: nhãn op, nút 1 và nút r. Xuất: nút với ký hiệu Phương pháp 5.3. Đánh giá từ dưới lên cho định nghĩa thuộc tính S Thuộc tính tổng hợp trên stack của bộ phân tích. Bộ biên dịch cho định nghĩa thuộc tính S có thể được thực hiện dựa theo bộ sinh bộ phân tích cú pháp LR. Bảng 5.5. Stack của bộ phân tích có vùng lưu chứa các thuộc tính tổng hợp state val . . . X X.x Y Y.y Z Z.z . .. top Bảng 5.6. Hiện thực bảng tính bằng bộ phân tích cú pháp LR Luật sinh Đoạn mã L → En Print (val [top]) E → E1 + T val [ntop]: = val [top - 2] + val [top] E → T T → T1 * F val [ntop]: = val [top - 2] x val [top] T → F F → (E) val [ntop]: = val [top - 1] F → digit Bảng 5.7. Quá trình biên dịch cho chuỗi nhập 3 * 5 + 4n. Chuỗi nhập Trạng thái Trị val Luật áp dụng 3 * 5 + 4n − − * 5 + 4n 3 3 * 5 + 4n F 3 F Ỉ digit * 5 + 4n T 3 T Ỉ F 5 + 4n T * 3 − + 4n T * 5 3 − 5 + 4n T * F 3 – 5 F Ỉ digit + 4n T 15 T Ỉ T * F + 4n E 15 E Ỉ T 4n E + 15 − n E + 4 15 – 4 n E + F 15 – 4 F Ỉ digit n E + T 15 – 4 T Ỉ F n E 19 E Ỉ E + T En 19 L 19 L Ỉ En 5.4. Định nghĩa thuộc tính L Mô phỏng 5.1. Thứ tự đánh giá depth – first cho các thuộc tính trên cây phân tích procedure dfvisit (n: node); begin for với mỗi nút m là con của nút n, từ trái sang phải do begin đánh giá thuộc tính kế thừa của m dfvisit (m) end đánh giá thuộc tính tổng hợp của n end; Chúng ta trình bày lớp của định nghĩa trực tiếp cú pháp, được gọi là định nghĩa thuộc tính L như sau: thuộc tính L luôn được đánh giá theo thứ tự depth – first. Định nghĩa thuộc tính L bao gồm tất cả các định nghĩa trực tiếp cú pháp, được dựa trên cơ sở văn phạm LL (1). Định nghĩa thuộc tính L Định nghĩa trực tiếp cú pháp, được gọi là định nghĩa thuộc tính L, nếu mỗi thuộc tính kế thừa của xj với 1 < j ≤ n mà xj nằm ở vế phải luật sinh A → x1x2xn, chỉ phụ thuộc vào: 1. Các thuộc tính của các ký hiệu x1, x2, , xj-1 ở phía trái của xj trong luật sinh. 2. Thuộc tính kế thừa của ký hiệu A. Bảng 5.8. Định nghĩa trực tiếp cú pháp không phải thuộc tính L. Luật sinh Luật ngữ nghĩa L.i : = l (A.i) M.i := m (L.s) A.s : = f (M.s) R.i : = r (A.i) Q.i : = q (R.s) A.s : = f (Q.s) A → QR A → LM Lược đồ dịch Mô phỏng 5.2. Lược đồ dịch đơn giản cho biểu thức số học Trường hợp đơn giản nhất nếu hành vi chỉ cần thuộc tính tổng hợp. Như vậy chúng ta sẽ xây dựng lược đồ dịch bằng cách tạo ra hành vi là phép gán cho mỗi luật ngữ nghĩa và gắn hành vi này vào tận cùng của vế phải luật sinh. Thí dụ: ta có luật sinh và luật ngữ nghĩa sau: Luật sinh Luật ngữ nghĩa T Ỉ T1 * F T.val:= T1.val x F.val ta đưa luật ngữ nghĩa ‘nhúng’ vào luật sinh và được: T Ỉ T1 * F {T.val:= T1.val x F.val} Nếu các hành vi cần cả thuộc tính tổng hợp và kế thừa thì chúng ta phải lưu ý: E → TR R → addop T {print (addop. Lexeme)} R⏐∈ T → num {print (num. val)} 1. Thuộc tính kế thừa của một kýhiệu nằm ở vế phải luật sinh phải được tính trước trong hành vi đứng trước kýhiệu đó. 2. Hành vi không được tham khảo đến thuộc tính tổng hợp của ký hiệu nằm ở bên phải hành vi đó. 3. Thuộc tính tổng hợp của ký hiệu không kết thúc ở vế trái luật sinh chỉ có thể được tính sau tất cả các thuộc tính mà nó tham khảo tới. 5.5. Biên dịch từ trên xuống Loại bỏ đệ quy trái cho lược đồ dịch Mô phỏng 5.3. Lược đồ dịch với văn phạm có đệ quy trái. E → E1 + T {E.val := E1.val + T. val⏐} E → E1 – T {E.val := E1.val - T. val⏐} E → T {E.val := T. val⏐} T → E {T.val := E. val⏐} T → num {T.val := num. val⏐} ER.i = 9 T.val = 9 − T.val = 5 num. val = 5 + T.val = 5 num. val = 2 R.i = 4 num. val = 9 ∈ Hình 5.10. Đánh giá biểu thức 9 – 5 + 2. Mô phỏng 5.4. Lược đồ dịch chuyển đổi với văn phạm đệ quy trái. E → T R → + R → - R →∈ T → ( ) T → num {R.i := T.val⏐} R {E.val := R.s} T {R1.i := R.i + T.val⏐} R1 {R.s := R1.s} T {R1.i := R.i - T.val⏐} R1 {R.s := R1.s} {R.s := R.i} E {T.val := E.val⏐} {T.val := num.val⏐} Giả sử chúng ta có lược đồ dịch sau (với thuộc tính tổng hợp): A → A1Y {A.a := g (A1.a, Y.y} A → X {A.a := f (X.x)} (5.1) Sau khi loại bỏ đệ quy trái chúng ta có văn phạm tương đương; A → X {R.i := f (X.x)} R {A.a := R.s} R → Y {R1.i := g (R.i, Y.y)} (5.3) R1 {R.i := R1.s} R →∈ {R.s := R.i} Thí dụ 5.13. Định nghĩa trực tiếp cú pháp ở bảng 5.3. dùng để xây dựng cây cú pháp được chuyển thành lược đồ dịch. E → E1 + T {E.nptr := mknode (‘+’, E1.nptr, T.nptr)} E → E1 – T {E.nptr := mknode (‘-’, E1.nptr, T.nptr)} (5.9) E → T {E.nptr := T.nptr} A.a = g(g(f(X.x), Y1, y), Y2, y) A R.i = f(X.x)XY2A.a = g(f(X.x), Y1, y) Y1 Y1A.a = f(X.x) Y2 R.I = g(g(f(X.x), Y1, y), Y2,y) X ∈ Hình 5.11. Hai cách tính giá trị thuộc tính. Mô phỏng 5.5. Lược đồ dịch chuyển đổi cho cấu trúc cây cú pháp. E → T {Rj := T.nptr} R {E.nptr := R.s} R → + T {R1j := mknode (‘+’, Rj.T.nptr)} R1 {R.s := R1.s} R → − T {R1j := mknode (‘-’, Rj.T.nptr)} R1 {R.s := R1.s} R →∈ {R.s := Rj} T → ( E ) {T.nptr := E.nptr} T → id {T.nptr := mkleaf (id.id.entry)} T → num {T.nptr := mkleaf (num.num.val)} Hình 5.12. biểu diễn toàn bộ các hành vi trong mô phỏng 5.5. cho cấu trúc cây cú pháp của câu a – 4 + c. Thiết kế bộ dịch đoán nhận trước R T•nptr id − T•nptr num R + = id R ∈ i i s•nptr − + id num 4 id c E a Hình 5.12. Dùng các thuộc tính kế thừa để xây dựng cây cú pháp. Giải thuật 5.2: xây dựng trình biên dịch trực tiếp cú pháp đoán nhận trước. Nhập: cho lược đồ dịch trực tiếp cú pháp với văn phạm cơ sở phù hợp cho phân tích đoán nhận trước. Xuất: mã cho trình biên dịch trực tiếp cú pháp. Phương pháp: 1. Với mỗi ký hiệu không kết thúc A, xây dựng hàm, thông số là thuộc tính kế thừa của A, trả về giá trị của các thuộc tính tổng hợp của A. 2. Mã cho ký hiệu không kết thúc A sẽ quyết định luật sinh nào sẽ được dùng trên cơ sở ký hiệu nhập đang được đọc. 3. Mã cho mỗi luật sinh sẽ được tạo ra: i) Với mỗi token X với thuộc tính tổng hợp x, cất giá trị x vào biến X.x. Tạo ra lệnh gọi chương trình con để so trùng token X với ký hiệu nhập được đọc. ii) Với B, tạo ra phát biểu gán C1 = B (b1, b2, , bk), b1, b2, , bk là các biến chứa các thuộc tính kế thừa của B và C là biến chứa thuộc tính tổng hợp của B. iii) Với mỗi hành vi, hãy chép mã vào cho bộ phận tích, thay mỗi tham chiếu đến các thuộc tính bằng biến chứa các thuộc tính đó. Thí dụ 5.14. Văn phạm ở mô phỏng 5.5 là LL (1), nó phù hợp cho việc phân tích từ trên xuống. function E: ↑ nút cây cú pháp function R: (i: ↑ nút cây cú pháp): ↑ nút cây cú pháp; function T: ↑ nút cây cú pháp; Kết hợp hai luật sinh R ở mô phỏng 5.5. R → addop T {R1.i :=mknode (addop.lexeme, R.i, T.nptr)} R1 {R.s := R1.s} R →∈ {R.s := R.i} Mô phỏng 5.6. Thủ tục phân tích cú pháp cho các luật sinh R: R → addop TR |∈ Procedur R: begin if lookahead = addop then begin match (addop): T; R; end else begin /*không làm gì cả*/ end Mô phỏng 5.7. Cây cú pháp đệ quy đi xuống function R (i: ↑ nút cây cú pháp): ↑ nút cây cú pháp; var nptr. ll, sl, s: ↑ nút cây cú pháp; addoplexeme: char; begin if lookahead = addop then begin /* luật sinh R → addop TR*/ addoplexeme := lexval; match (addop); il := mknode (addoplexeme, i, nptr); sl := R (il); s := sl; end else s := i; /* luật sinh R →∈ */ return s end; 5.6. Đánh giá thuộc tính kế thừa từ dưới lên Loại bỏ hành vi được nhúng trong lược đồ dịch Ví dụ: chúng ta có lược đồ dịch E → TR R → + T {print (‘+’)} R ⏐ - T {print (‘−‘)} R⏐∈ T → num {print (num.val)} Tạo ra lược đồ dịch với việc dùng các ký hiệu đánh dấu không kết thúc mới N, M. E → TR R → + T MR ⏐- TNR ⏐∈ T → num {print (num.val)} M →∈ {print (‘+’) } N →∈ {print (‘−’) } Thuộc tính kế thừa trên stack của bộ phân tích Thí dụ 5.15. Quá trình đánh giá thuộc tính kế thừa bằng bộ phân tích từ dưới lên cho câu nhập real p, q, r ở (H.5.13). D → T {L.in := T.type} T → int {T.type := integer} T → real {T.type := real} L → {L1.in := L.in} L1, id {add type (id.entry, L.in)} L → id {add type (id.entry, L.in)} Dreal L L L p , q • in in in T r Hình 5.13. Tại mỗi nút L có L.in := T.type. Bảng 5.9. Bất cứ lúc nào vế phải của L được thu giảm thì T luôn ở trên vế phải đó. Nhập Trạng thái Luật được áp dụng Real p, q, r p, q, r p, q, r , q, r , q, r , q, r , r , r r - real T Tp TL TL, TL, q TL TL, TL, r TL D T → real L → id L → L, id L → L, id D → TL Bảng 5.10. Giá trị của T.type được dùng ở vị trí L.in. Đánh giá các thuộc tính kế thừa Thí dụ 5.16. Đây là ví dụ về trường hợp không thể đoán nhận trước vị trí của thuộc tính trong lược đồ dịch. Luật sinh Đoạn mã D Ỉ TL T Ỉ int T Ỉ real L Ỉ L, id L Ỉ id val [ntop] := integer val [ntop] := real addtype (val[top], val[top – 3]) addtype (val[top], val[top – 1]) Luật sinh Luật ngữ nghĩa S Ỉ aAC S Ỉ aABC C Ỉ c C.i:= A.s C.i := A.s C.i := g (C.i) (5.4) Luật sinh Luật ngữ nghĩa S Ỉ aAC S Ỉ bABMC C Ỉ c M Ỉ ∈ C.i := A.s M.i := A.s ; C.i := M.s C.i := g(C.i) M.S := M.i S S A B b b C s i A B M ∈ s i C i a) b) Hình 5.14. Sao chép thuộc tính thông qua ký hiệu M. a) Luật sinh chưa biến đổi; b) Luật sinh đã được biến đổi. Ký hiệu không kết thúc N cũng có thể được dùng để mô phỏng cho luật ngữ nghĩa mà nó không phải là luật sao chép. Ví dụ ta có luật sinh và luật ngữ nghĩa: Luật sinh Luật ngữ nghĩa S Ỉ aAC C.i := f(A.s) Luật sinh Luật ngữ nghĩa S Ỉ aANC N Ỉ ∈ N.i := A.s ; C.i := N.s N.s := f(N.i) (5.5) (5.6) Giải thuật 5.3. Phân tích từ dưới lên và sự biên dịch với các thuộc tính kế thừa. Nhập: định nghĩa thuộc tính L với văn phạm cơ sở LL (1). Xuất: bộ phân tích cú pháp tính các giá trị của tất cả các thuộc tính trên stack của bộ phân tích. Phương pháp: giả sử mỗi ký hiệu không kết thúc A có một thuộc tính kế thừa A.i và mỗi ký hiệu văn phạm X có một thuộc tính tổng hợp X.x. Với mỗi luật sinh A Ỉ X1 Xn, sẽ có n ký hiệu không kết thúc đánh dấu M1 Mn, sẽ thay luật trên thành luật sinh A ỈM1X1 MnXn. Để nhận thấy các thuộc tính có thể được tính trong quá trình phân tích từ dưới lên, hãy xét hai trường hợp. Trường hợp thứ nhất nếu ta thu giảm về ký hiệu Mj ta phải biết luật sinh A →Mj X1 MnXn mà Mj có trong đó. Chúng ta phải biết các vị trí của các thuộc tính mà thuộc tính kế thừa Xj.i cần để tính giá trị cho nó. A.i ở val[top – 2j + 2], X1.i ở val[top – 2j + 3], X1.s ở tại val[top – 2i + 4], X2.i ở val[top – 2j + 5] Trường hợp thứ hai sẽ xuất hiện khi ta thu giảm về một ký hiệu không kết thúc của văn phạm giả sử bằng luật sinh A →M1X1 MnXn, và giả sử ta chỉ tính A.s, còn A.i đã được sinh và nằm trên stack ở vị trí trên vị trí của A. Các thuộc tính cần thiết để tính A.s đã sẵn sàng trên stack, đã được biết, đó chính là các vị trí của các Xj trong quá trình thu giảm. Thay thế thuộc tính kế thừa bằng thuộc tính tổng hợp Chúng ta có thể tránh dùng thuộc tính kế thừa bằng việc thay đổi văn phạm cơ sở. Trong ngôn ngữ của Pascal cho phép khai báo một chuỗi các biến và sau đó là kiểu dữ liệu của chúng. Thí dụ: m, n: integer. D → L : T T → integer ⏐ char L → L, id ⏐ id D → id L L → ,id Ll:T T → integer ⏐ char