Khảo sát và xây dựng thử nghiệm chuyến trước của trình biên dịch dành cho ngôn ngữ ANSI C giản lược

a = c; Theo cây phân tích cú pháp (hình 4.6), inclusive_or_expr sẽ tiếp tục dẫn ra một nhánh khác để phát sinh biểu thức so sánh. Kết quả của các biểu thức so sánh đó (true hoặc false) sẽ dược lưu trữ trong các thuộc tính và lan truyền tổng hợp lên các nút trên. Theo thứ tự duyệt cây (trái trước), ta có thể thấy được : - op1 chính là kết quả của phép so sánh a>b - op2 chính là kết quả của phép so sánh b>c - op3 chính là kết quả của phép so sánh a>c - op12 là kết quả của a>b && b>c hay op1 && op2 - op123 là kết quả của (a>b && b>c || a>c) hay op12||op3 Để xác định giá trị của op123, ta chỉ cần tính lần lượt các giá trị op1, op2, op12, op3. Nhưng thực tế, chỉ cần op1 là false thì op12 chắc chắn là false, bất chấp giá trị của op2; op3 là true thì op123 chắc chắn là true, bất chấp giá trị của op12. Vì vậy, ta có thể tối ưu quá trình tính toán bằng cách đưa vào các luồng điều khiển, các chỉ thị rẽ nhánh như đã trình bày ở trên. Ứng với mỗi hành vi rút gọn, một hành động ngữ nghĩa được thực thi. Cây cú pháp duyệt theo thứ tự trái trước nên các thứ tự các hành vi được thực hiện theo thứ tự ACT01ACT02ACT03…ACT14. Bảng 4.4 mô tả chi tiết và kết quả phát sinh mã ba địa chỉ của các hành vi ngữ nghĩa. 83 Hình 4.16. Cây phân tích cú pháp của cấu trúc điều khiển Ví dụ 4.16 8 3 Chương 4 – Xây dựng chuyến trước của trình biên dịch 84 Thứ tự Hành vi ngữ nghĩa Mã 3 địa chỉ Chú thích ACT01 static int label = 0; genLabel(L_TEST, $$ = ++label); TST1: Thuộc tính yyint của test được gán bằng 1. ACT02 STACK_PUSH(AndOrStack, 0); Push 0 và AndOrStack AndOrStack : 0 ACT03 label = STACK_ITEM(AndOrStack,0) = tf_label(); if( $1 ) { falseLab = newLabel(L_FALSE, label); geniCodeIfx($1, NULL, falseLab); } IFFALSE op1 GOTO F1 Label = 1 TOP(AndOrStack)=1 AndOrStack : 1 ACT04 label = STACK_ITEM(AndOrStack,0); falseLab = newLabel(L_FALSE, label); geniCodeIfx($4, NULL, falseLab); IFFALSE op2 GOTO F1 label=TOP(AndOrStack) label = 1 ACT05 if( label = STACK_POP(AndOrStack)) { genGoto(L_TRUE, label); $$ = gen_false_true(label, NULL); } else $$ = $1; GOTO T1 F1: op12 = 0 GOTO E1 T1: op12 = 1 E1: AndOrStack : NULL label = 1 op12 được khởi tạo và xác định giá trị từ giá trị của op1 và op2. ACT06 STACK_PUSH(AndOrStack, 0); Push 0 vào AndOrStack. AndOrStack : 0 ACT07 label = STACK_ITEM(AndOrStack,0) = tf_label(); if( $1 ) { trueLab = newLabel(L_TRUE, label); geniCodeIfx($1, trueLab, NULL); } IFTRUE op12 GOTO T2 label = 2 (vì tf_label() được gọi lần thứ 2) TOP(AndOrStack)=2 AndOrStack : 2 Bảng 4.4. Mô tả các hành vi ngữ nghĩa và phát sinh mã ba địa chỉ của lệnh if 8 4 Chương 4 – Xây dựng chuyến trước của trình biên dịch 85 ACT08 STACK_PUSH(AndOrStack, 0); Push 0 vào AndOrStack. AndOrStack : 0 2 ACT09 if( label = STACK_POP(AndOrStack)) { genGoto(L_TRUE, label); $$ = gen_false_true(label, NULL); } else $$ = $1; AndOrStack : 2 label = 0  không phát sinh mã trung gian mà chỉ lan truyền op3 ACT10 label = STACK_ITEM(AndOrStack,0) trueLab = newLabel(L_TRUE, label); geniCodeIfx($4, trueLab, NULL); IFTRUE op3 GOTO T2 label = 2 ACT11 if(label = STACK_POP(AndOrStack)) { $$ = gen_false_true(label, NULL); } else $$ = $1; F2: op123 = 0 GOTO E2 T2: op123 = 1 E2: label = 2 AndOrStack : NULL op123 được khởi tạo và xác định giá trị từ giá trị của op12 và op3. ACT12 $$ = $1; //Lan truyền thuộc tính op123 đã được tính toán hoàn chỉnh là lan truyền lên. ACT13 $$ = $1; falseLab = newLabel(L_NEXT, $$); geniCodeIfx($2, NULL, falseLab); IFFALSE op123 GOTO EXIT1 ACT14 genLabel(L_NEXT, $3); EXIT1: Bảng 4.4. (tiếp theo) 8 5 86 Như vậy, sau quá trình duyệt cây phân tích cú pháp cũng như thực hiện các hành vi ngữ nghĩa, ta nhận được bộ mã 3-địa chỉ: op1 = a > b //Tính toán qua inclusive_or_expr TST1: IFFALSE op1 GOTO F1 op2 = b > c //Tính toán qua inclusive_or_expr IFFALSE op2 GOTO F1 GOTO T1 F1: op12 = 0 GOTO E1 T1: op12 = 1 E1: IFTRUE op12 GOTO T2 op3 = a > c //Tính toán qua inclusive_or_expr IFTRUE op3 GOTO T2 F2: op123 = 0 GOTO E2 T2: op123 = 1 E2: IFFALSE op123 GOTO EXIT1 a = c //Phát sinh mã qua statement EXIT1: Dịch lệnh switch-case: Câu lệnh switch được dùng để thay thế cho lệnh if trong trường hợp có quá nhiều điều kiện để chọn. Cú pháp : Chương 4 – Xây dựng chuyến trước của trình biên dịch 87 switch (E) { case V1: S1 case V2: S2 … case Vn-1: Sn-1 default: Sn } Công việc của trình biên dịch cần làm là phát sinh mã để: – Đánh giá biểu thức E. – Xác định giá trị Vj trong các trường hợp (case) sao cho Vj bằng giá trị biểu thức đã được đánh giá. Nếu không tìm thấy giá trị Vj nào thỏa mãn, biểu thức sẽ rơi vào trường hợp default (mặc định). – Thực thi những chỉ thị (Sj) kết hợp với giá trị được xác định. Mã trung gian cho trường hợp tổng quát theo đề nghị của Alho [1, 2]: Mã đánh giá giá trị biểu thức. goto test L1 : mã cho S1 goto next L2 : mã cho S2 goto next ... Ln-1: mã cho Sn-1 goto next Ln : mã cho Sn goto next test: if E = V1 goto L1 if E = V2 goto L2 ... if E = Vn-1 goto Ln-1 goto Ln next: Cách biểu diễn 1 Mã đánh giá giá trị biểu thức. if E != V1 goto L1 mã cho S1 goto next L1 : if E != V2 goto L2 mã cho S2 goto next L2 : ... Ln-2: if E = Vn-1 goto Ln-1 mã cho Sn-1 goto next Ln-1: mã cho Sn next: Cách biểu diễn 2 Chương 4 – Xây dựng chuyến trước của trình biên dịch 88 Nhưng thực tế trong một chương trình C, những mã ngắt (goto next) sau khi thực thi lệnh thích hợp chỉ được sử dụng khi người dùng gọi tường minh lệnh ngắt (break). Ta sẽ sử dụng cách biểu diễn thứ nhất để phát sinh mã cho trường hợp lệnh switch và mã phát sinh sẽ theo đúng như một chương trình C chuẩn. Một số các luật sinh cùng luật ngữ nghĩa : 1. selection_statement  SWITCH '(' expr ')' { STACK_PUSH(SwitchStack, new_stab($3, ++Case_label)); genGoto(L_SWITCH, Case_label); STACK_PUSH(BreakStack, ++Case_label); STACK_PUSH(BreakLabelStack, L_SWITCH); } compound_statement { gen_stab(STACK_POP(SwitchStack)); STACK_POP(BreakStack); STACK_POP(BreakLabelStack); } 2. statementlabeled_statement | jump_statement 3. compound_statement‟{„ statement_list „}‟ 4. statement_liststatement | statement_list statement 5. jump_statementBREAK „;‟ { genGoto(STACK_ITEM(BreakLabelStack,0), STACK_ITEM(BreakStack, 0); } Chương 4 – Xây dựng chuyến trước của trình biên dịch 89 6. labeled_statementCASE constant_expr ':' { add_case(STACK_ITEM(SwitchStack,0),$2, ++Case_label); genLabel(L_SWITCH, Case_label); } 7. labeled_statementDEFAULT ':' { add_default_case(STACK_ITEM(SwitchStack, 0), ++Case_label); genLabel(L_SWITCH, Case_label); } 8. constant_expr  conditional_expr Ví dụ 4.17: Dịch cấu trúc lệnh switch sau sang chỉ thị mã ba địa chỉ : switch(x) { case 1: y = 0; break; case 2: y = 1; default: y = x; } Ta xây dựng được cây phân tích cú pháp : 90 Hình 4.17. Cây phân tích cú pháp cho cấu trúc lệnh switch 9 0 91 Ta sẽ phát sinh mã kiểm tra giá trị biểu thức so với các trường hợp đưa ra ở cuối bộ mã (ACT06) vì khi đó, ta mới thu thập đủ thông tin về các nhãn, cũng như những giá trị hằng số cần cho việc so sánh. Những thông tin về các case sẽ được lưu trữ trong quá trình duyệt cây phân tích cú pháp. Ta có 2 cấu trúc chính như sau: – case_val : Trong đó, on_this là toán hạng lưu trữ thông tin của giá trị hằng số, go_here là thông tin về nhãn của trường hợp này. – stab (switch table): Trong đó : o table : bảng lưu trữ các trường hợp trong khi dịch (case_val) o cur : con trỏ tới các trường hợp. o op : toán hạng lưu trữ thông tin của biểu thức đã được tính toán. o def_label : nhãn cho trường hợp default. o stab_label : nhãn ở cuối và đầu và cuối lệnh switch ta đang xét. table cur 1 3 2 4 x def_label = 5 stab_label = 1 on_this go_here Hình 4.18. Mô tả cấu trúc một case_val Hình 4.19. Mô tả cấu trúc một switch table 92 Thứ tự Hành vi ngữ nghĩa Mã 3 địa chỉ Chú thích ACT01 STACK_PUSH(SwitchStack,new_stab($3, ++Case_label)); genGoto(L_SWITCH, Case_label); STACK_PUSH(BreakStack, ++Case_label); STACK_PUSH(BreakLabelStack, L_SWITCH); GOTO SW1 Case_label: biến toàn cục, khởi tạo là 0. BreakStack : 2 BreakLabelStack : SW Case_label = 2 ACT02 add_case(STACK_ITEM(SwitchStack,0),$2, ++Case_label); genLabel(L_SWITCH, Case_label); SW3: //Lệnh gán y = 0 Thủ tục add_case sẽ bổ sung vào stab (switch table) thông tin của case hiện tại Case_label = 3 ACT03 genGoto(STACK_ITEM(BreakLabelStack,0), STACK_ITEM(BreakStack, 0); GOTO SW2 Phát sinh mã cho lệnh break. Sử dụng thông tin lưu trữ đã lưu trữ trước đó trong BreakStack và BreakLabelStack. Bảng 4.5. Mô tả các hành vi ngữ nghĩa và phát sinh mã ba địa chỉ của lệnh switch 9 2 Chương 4 – Xây dựng chuyến trước của trình biên dịch 93 ACT04 add_case(STACK_ITEM(SwitchStack,0),$2, ++Case_label); genLabel(L_SWITCH, Case_label); SW4: //Lệnh gán y = 1 Bổ sung thông tin case hiện tại vào stab Case_label = 4 ACT05 add_default_case(STACK_ITEM(SwitchStack, 0), ++Case_label); genLabel(L_SWITCH, Case_label); SW5: //Lệnh gán y = x Bổ sung thông tin về trường hợp default khi đánh giá biểu thức. Case_label = 5 ACT06 gen_stab(STACK_POP(SwitchStack)); STACK_POP(BreakStack); STACK_POP(BreakLabelStack); GOTO SW2 SW1: IFTRUE x=1 GOTO SW3 IFTRUE x=2 GOTO SW4 GOTO SW5 SW2: Phát sinh mã đánh giá giá trị biểu thức và nhảy tới trường hợp thích hợp với đầy đủ các thông tin đã được lưu trữ trong stab. BreakStack : NULL BreakLabelStack : NULL Bảng 4.5. (tiếp theo) 9 3 Chương 4 – Xây dựng chuyến trước của trình biên dịch 94 Chỉ thị ba địa chỉ kết quả sau khi dịch chương trình : GOTO SW1 SW3: y = 0 GOTO SW2 SW4: y = 1 SW5: y = x GOTO SW2 SW1: IFTRUE x=1 GOTO SW3 IFTRUE x=2 GOTO SW4 GOTO SW5 SW2: Dịch lệnh while: Trình biên dịch phải tiếp tục thực hiện những câu lệnh nằm trong vòng lặp while trong khi biểu thức điều kiện còn chính xác (true). Vì vậy, việc đầu tiên mà ta cần làm là đánh giá biểu thức điều kiện để phát sinh mã ngắt phù hợp. Ví dụ 4.18: Đoạn mã nguồn sử dụng chỉ thị while: while (i < n) i++; table cur 1 3 2 4 x def_label = 5 stab_label = 1 Hình 4.20. Switch table khi đã lưu trữ đầy đủ thông tin để thực hiện hành vi ACT06 Chương 4 – Xây dựng chuyến trước của trình biên dịch 95 Mục đích của đoạn mã nguồn : biến i sẽ tự động tăng lên 1 đơn vị trong khi i còn bé hơn n. Như vậy, ta phải phát sinh mã để kiểm tra biểu thức điều kiện (i<n) . Nếu biểu thức điều kiện là true, lệnh i++ được thực hiện. Còn nếu biểu thức điều kiện là fasle, chương trình sẽ tiếp tục bằng câu lệnh tiếp theo sau cấu trúc while. Ta có thể mô hình hóa luồng điều khiển như sau : Hình 4.21. Phân bố mã cho các câu lệnh while Luật sinh: iteration_statement  WHILE '(' test ')' statement { genGoto(L_TEST, $3); genLabel(L_NEXT, $3); } Mã trung gian được phát sinh đối với Ví dụ 4.18 (với cấu trúc được phân bố như Hình 4.21): TST1: iTemp0 = (i < n) IFFALSE(iTemp0) GOTO : EXIT1 iTemp1 = i iTemp2 = i + 1 i = iTemp2 GOTO : TST1 EXIT1: Chương 4 – Xây dựng chuyến trước của trình biên dịch 96 Dịch lệnh do while: Thay vì kiểm tra biểu thức điều kiện trước khi thực hiện vòng lặp như while, do-while làm công việc này ở cuối vòng lặp. Điều này có nghĩa là vòng lặp do-while sẽ thực hiện ít nhất một lần. Từ đó, ta có mô hình phân bố mã cho do-while như sau: Hình 4.22. Phân bố mã cho các câu lệnh do-while Luật sinh cho trường hợp do-while : iteration_statement  DO { static int label; genLabel(L_DOTOP, ++label); } statement WHILE { genLabel(L_DOTEST, label); } '(' test ')' ';' 4.4.4. Khai báo Như đã biết, trong một chương trình, thông thường sẽ có 2 phần khai báo:  Khai báo biến (declaration)  Khai báo hàm (function_definition). Chương 4 – Xây dựng chuyến trước của trình biên dịch 97 Hình 4.23. Cấu trúc khai báo của một chương trình Tập luật sinh cho cấu trúc khai báo của một chương trình:  file  program | ε  program  program external_definition | external_definition  external_definition  function_definition | declaration Từ đó, mỗi khai báo trong chương trình đã được đơn giản hóa, xem như là một external_definition Hình 4.24. Cây phân tích cú pháp của một chương trình đơn giản file program program external_definition external_definition function_definition declaration Chương 4 – Xây dựng chuyến trước của trình biên dịch 98 Hình 4.25. Sự tương quan giửa khai báo và external_definition Dịch các khai báo bao gồm các công việc chính:  Ghi nhận thông tin khai báo về kiểu (int, short, long), dấu (signed, unsigned), thuộc tính lưu trữ (static, extern),...  Thực hiện các hành vi ngữ nghĩa trong hệ thống luật sinh để tiến hành tạo ra các đối tượng tương ứng với các thông tin trên, sau đó liên kết lại và thêm vào bảng danh biểu. Sau đây, ta sẽ tiến hành dịch từng loại khai báo cụ thể. 4.4.4.1. Khai báo biến Các biến trong chương trình bao gồm 2 loại: biến toàn cục và biến cục bộ (biến khai báo trong hàm). Khai báo biến có dạng như sau: type var_name; Trong đó:  type: Kiểu dữ liệu của biến (int, long, char, ...), các thuộc tính lưu trữ (static, extern),...  var_name: Tên biến.  num_ele: Số lượng phần tử nếu là khai báo mảng. Hệ thống luật sinh để phân tích kiểu, tên biến như trong 2 bảng sau: Chương 4 – Xây dựng chuyến trước của trình biên dịch 99 Luật sinh Luật ngữ nghĩa (mô tả vắn tắt) declaration_specifiers  declaration_specifiers_';' $$ = $1; declaration_specifiers_  storage_class_specifier $$ = $1; declaration_specifiers_  storage_class_specifier declaration_specifiers_ Kết hợp specifier và specifier  specifier declaration_specifiers_  type_specifier $$ = $1; declaration_specifiers_  type_specifier declaration_specifiers_ Kết hợp specifier và specifier  specifier storage_class_specifier  TYPEDEF Tạo Specifier mới, bật cờ typedef storage_class_specifier  EXTERN Tạo Specifier mới, bật cờ extern storage_class_specifier  STATIC Tạo Specifier mới, bật cờ static type_specifier  type_specifier2 $$ = $1; type_specifier2  CHAR Tạo Specifier mới, định kiểu CHAR type_specifier2  SHORT Tạo Specifier mới, định kiểu SHORT type_specifier2  INT Tạo Specifier mới, định kiểu INT type_specifier2  LONG Tạo Specifier mới, định kiểu LONG type_specifier2  SIGNED Tạo Specifier mới, bật cờ b_signed type_specifier2  UNSIGNED Tạo Specifier mới, bật cờ b_unsigned type_specifier2  VOID Tạo Specifier mới, định kiểu VOID type_specifier2  CONST Tạo Specifier mới, bật cờ b_const type_specifier2  struct_or_union_specifier $$ = $1; Struct sẽ được nói rõ trong phần sau type_specifier2  TYPE_NAME TYPE_NAME là kiễu dữ liệu typedef, được nói rõ hơn trong phần sau. Bảng 4.6. Hệ thống luật sinh nhận kiểu (tiếp theo) 9 9 Chương 4 – Xây dựng chuyến trước của trình biên dịch 100 Luật sinh Luật ngữ nghĩa (mô tả vắn tắt) declaration  declaration_specifiers init_declarator_list ';' Thêm chuỗi symlink quy định kiểu vào init_declarator_list init_declarator_list  init_declarator $$ = $1; init_declarator_list  init_declarator_list ',' init_declarator $3->next = $1 ; $$ = $3; init_declarator  declarator $$ = $1; declarator  declarator3 $$ = $1 ; declarator  pointer declarator3 Thêm declarator về pointer vào chuỗi symlink, truyền lên cho $$. Pointer sẽ được nói rõ trong phần sau declarator3  declarator2 $$ = $1 ; declarator2  identifier $$ = $1; identifier  IDENTIFIER $$ = newSymbol($1, NestLevel); declarator2  '(' declarator ')' $$ = $2; declarator2  declarator3 '[' ']' Tạo declarator dạng mảng (ARRAY) có 0 phần tử, thêm nó vào chuỗi symlink, truyền lên cho $$ declarator2  declarator3 '[' constant_expr ']' Tạo declarator dạng mảng (ARRAY) có constant_expr phần tử, thêm nó vào chuỗi symlink, truyền lên cho $$ Bảng 4.7. Hệ thống luật nhận tên biến và số lượng phần tử của mảng 1 0 0 Chương 4 – Xây dựng chuyến trước của trình biên dịch 101 Ví dụ 4.19: Khai báo toàn cục như sau: int x; Từ cây phân tích cú pháp, ta có sự lan truyền thuộc tính và thực thi các hành vi nhữ nghĩa như sau: Sơ đồ tổ chức các đối tượng lưu trữ: noun = V_INT noun = V_INT noun = V_INT noun = V_INT name = “x” name = “x” name = “x” name = “x” name = “x” name = “x” init_declarator_list init_declarator declarator declarator3 declarator2 indentifier IDENTIFIER indentifier = newSymbol(“x”) act act declaration_specifiers declaration_specifiers_ type_specifier type_specifier2 INT type_specifier2 = newLink(SPECIFIER) type_specifier2.noun = V_INT; „;‟ act act init_declarator_list.type = declaration_specifiers; init_declarator_list.etype = declaration_specifiers; declaration = reverseSyms(init_declarator_list); file program external_definition declaration act addSymChain (declaration); Hình 4.26. Sự lan truyền thuộc tính “int” và “x” Chương 4 – Xây dựng chuyến trước của trình biên dịch 102 4.4.4.2. Khai báo hàm Khai báo hàm có dạng: type function_name () { } Trong đó:  type: Kiểu trả về của khai báo hàm.  arg: Danh sách các tham số.  function_body: Phần khai báo thân hàm. Để nhận thông tin về khai báo hàm, hệ thống luật sinh sẽ tiến hành nhận từng phần khai báo. Hệ thống luật sinh chính gồm:  function_definition  function_declarator function_body  function_definition  declaration_specifiers function_declarator function_body Trong đó:  declaration_specifiers phân tích kiểu và thuộc tính lưu trữ. Hệ thống luật này đã được mô tả trong Bảng 4.6.  function_declarator phân tích tên hàm, tham số.  function_body phân tích thân hàm.. Hệ thống luật sinh được mô tả trong các bảng sau: Symbol Table symbol : “x” “_x” NULL name rname type etype next symlink : SPECIFIER NULL _class next select: noun b_unsigned V_INT 0 Hình 4.27. Sơ đồ tổ chức lưu trữ khai báo int x; Chương 4 – Xây dựng chuyến trước của trình biên dịch 103 Luật sinh Luật ngữ nghĩa (mô tả vắn tắt) function_declarator  declarator2_function_attributes $$ = $1; function_declarator  pointer declarator2_function_attributes Thêm declarator về pointer vào chuỗi symlink của $2, truyền $2 lên cho $$. declarator2_function_attributes  function_declarator2 $$ = $1; declarator2_function_attributes  function_declarator2 function_attribute Ghi nhận danh sách tham số và thuộc tính của hàm vào $1 function_declarator2  declarator2 '(' ')' Thêm declarator kiểu FUNCTION vào $1 function_declarator2  declarator2 '(' {ACT1} parameter_type_list ')' {ACT2} ACT1: level++, block++ ACT2: Thêm declarator kiểu FUNCTION vào $1, level--, block--, ghi nhận danh sách các tham số của hàm vào $1 function_declarator2  declarator2 '(' identifier_list ')' Báo lỗi khai báo dạng cũ và tạo symlink kiểu INT cho $1 identifier_list  identifier $$ = $1; identifier_list  identifier_list ',' identifier $3->next = $1; $$ = $3 ; identifier  IDENTIFIER $$ = newSymbol($1, NestLevel); parameter_type_list  parameter_list $$ = $1; parameter_list  parameter_declaration $$ = $1; parameter_list  parameter_list ',' parameter_declaration $3->next = $1 ; $$ = $3 ; parameter_declaration  type_specifier_list declarator Thêm kiểu cho declarator Thêm symbol $2 vào bảng SymbolTab type_specifier_list  type_specifier_list_ $$ = $1; type_specifier_list_  type_specifier $$ = $1; type_specifier_list_  type_specifier_list_ type_specifier Kết hợp specifier và specifier  specifier Bảng 4.8. Hệ thống luật phân tích tên hàm và tham số 1 0 3 Chương 4 – Xây dựng chuyến trước của trình biên dịch 104 Luật sinh Luật ngữ nghĩa (mô tả vắn tắt) function_body  compound_statement $$ = $1; compound_statement  start_block declaration_list end_block Ta tập trung vào declaration_list vì đây là khai báo cục bộ trong hàm. compound_statement  start_block declaration_list statement_list end_block Ta tập trung vào declaration_list vì đây là khai báo cục bộ trong hàm. declaration_list  declaration Kiểm tra $1 có nằm trong bảng danh biểu hay không, nếu có, báo lỗi trùng tên kiểu và biến. Ngược lại, thêm $1 vào bảng danh biểu. declaration_list  declaration_list declaration Kiểm tra $2 có nằm trong bảng danh biểu hay không, nếu có, báo lỗi trùng tên kiểu và biến. Ngược lại, thêm $2 vào bảng danh biểu Bảng 4.9. Hệ thống luật nhận các khai báo trong hàm Nhánh luật declaration đã được trình bày trong Bảng 4.7, nhánh luật statement_list thực hiện phân tích các câu lệnh trong thân hàm, ta sẽ không đề cập đến trong phần này. Ví dụ 4.20: Với khai báo hàm như sau: int inc(int x) { x++; } Trong phần thân hàm, không có khai báo biến cục bộ, do đó nhánh luật sinh function_body ta sẽ không đề cập ở đây. Từ cây phân tích cú pháp, ta có sự lan truyền thuộc tính và thực thi các hành vi nhữ nghĩa như trong hình sau: Chương 4 – Xây dựng chuyến trước của trình biên dịch 105 function_definition act declaration_specifiers declaration_specifiers_ type_specifier type_specifier2 INT type_specifier2 = newLink(SPECIFIER) type_specifier2.noun = V_INT; noun = V_INT noun = V_INT noun = V_INT noun = V_INT indentifier = newSymbol(“x”) act declarator declarator3 declarator2 indentifier IDENTIFIER name = “x” name = “x” name = “x” name = “x” type_specifier_list act type_specifier type_specifier2 INT type_specifier2 = newLink(SPECIFIER) type_specifier2.noun = V_INT; type_specifier_list_ noun = V_INT noun = V_INT noun = V_INT noun = V_INT parameter_type_list „)‟ „(‟ declarator2 indentifier IDENTIFIER act indentifier = newSymbol(“inc”) name = “inc” name=”inc” parameter_list parameter_declaration function_declarator2 function_declarator declarator2_function_attributes function_body act Phát sinh mã xử lý thân hàm act Thực hiên nối symlink $1 vào $2 Thêm danh biểu $2 vào bảng danh biểu Thêm các biến tham số vào bảng danh biểu Hình 4.28. Cây phân tích cú pháp và lan truyền thuộc tính cho ví dụ Ví dụ 4.20: 1 0 5 Chương 4 – Xây dựng chuyến trước của trình biên dịch 106 Sơ đồ tổ chức các đối tượng lưu trữ: Symbol Table symbol: “inc” “_inc” NULL name rname type etype next symlink: DEClARATOR _class next select: dcl_type func_Attrs FUNCTION symlink : SPECIFIER NULL _class next select: noun b_unsigned v_struct V_INT 0 NULL symlink : SPECIFIER NULL _class next select: noun b_unsigned v_struct V_INT 0 NULL symbol: “x” “_inc_PARM_1” NULL name rname type etype next symbol: “x” “_inc_PARM_1” NULL name rname type etype next symlink : SPECIFIER NULL _class next select: noun b_unsigned v_struct V_INT 0 NULL Hình 4.29. Sơ đồ tổ chức lưu trữ hàm inc trong Ví dụ 4.20: Chương 4 – Xây dựng chuyến trước của trình biên dịch 107 4.4.4.3. Struct Cấu trúc khai báo struct: struct tag_name { struct_emement_1; ... struct_emement_n; }; Trong đó:  struct: Từ khóa khai báo struct  tag_name: Tên struct.  [struct_emement_1... struct_emement_n]: Khai báo các thành phần của struct. Hệ thống luật sinh phân tích phần khai báo struct: Luật sinh Luật ngữ nghĩa (mô tả vắn tắt) struct_or_union_specifier  struct_or_union opt_stag {ACT1} '{' struct_declaration_list '}' {ACT2} ACT1: Thêm symbol mới quy định về struct $2 vào bảng StructTab ACT2: Tạo structdef, ghi nhận các fields của struct vào $2, tính toàn kích thước struct, tạo specifier  symlink struct_or_union_specifier  struct_or_union stag Tìm symbol có tên stag trong bảng StructTab, nếu có trả về Specifier quy định kiểu struct tương ứng, ngược lại báo lỗi và trả về NULL struct_or_union  STRUCT $$ = STRUCT ; struct_or_union  UNION $$ = UNION; opt_stag  stag $$ = $1; opt_stag  ε Tạo structdef mới với tên tag do compiler quy định stag  identifier Tìm trong bản StructTab và trả về structdef tương ứng. Nếu chưa có Structdef tương ứng thì tạo mới. identifier  IDENTIFIER $$ = newSymbol($1); Bảng 4.10. Hệ thống luật phân tích khai báo struct Chương 4 – Xây dựng chuyến trước của trình biên dịch 108 Bảng 4.10. (tiếp theo) Nhánh luật declarator đã được trình bày trong Bảng 4.7 sẽ tiến hành phân tích khai báo thành phần trong struct để trả về các danh biểu tương ứng. Ví dụ 4.21: Với khai báo struct: struct PS { int x; }; Từ bảng luật sinh, chương trình sẽ xây dựng cây phân tích cú pháp cùng các luật ngữ nghĩa như trong Hình 4.30 struct_declaration_list  struct_declaration $$ = $1; struct_declaration_list  struct_declaration_list struct_declaration Nối chuỗi các symbol. Truyền thuộc tính lên trên struct_declaration  type_specifier_list struct_declarator_list ';' Thêm kiểu vào danh sách các khai báo thành phần struct struct_declarator_list  struct_declarator $$ = $1; struct_declarator_list  struct_declarator_list ',' struct_declarator $3->next = $1 ; $$ = $3 ; struct_declarator  declarator $$ = $1; struct_declarator  ε Tạo symbol mới, truyền về cho $$ Chương 4 – Xây dựng chuyến trước của trình biên dịch 109 Hình 4.30. Cây phân tích cú pháp và quá trình lan truyền thuộc tính cho khai báo struct struct_or_union_specifier „;‟ „{„ struct_declaration_list „}„ name = “x” name = “x” name = “x” name = “x” name = “x” name = “x” struct_declarator_list struct_declarator declarator declarator3 declarator2 indentifier IDENTIFIER indentifier = newSymbol(“x”) act type_specifier_list type_specifier_list_ act type_specifier type_specifier2 INT type_specifier2 = newLink(SPECIFIER) type_specifier2.noun = V_INT; noun = V_INT noun = V_INT noun = V_INT noun = V_INT struct_declaration opt_stag stag indentifier IDENTIFIER indentifier = newSymbol(“PS”) act act Tìm „PS‟ trong bảng StructTab. Nếu tồn tại, trả rề structdef chứa PS, ngược lại stag = newSymbol(“PS”) name = “PS” struct_or_union STRUCT type = STRUCT act type = STRUCT act Thêm structdef stag vào bảng structTab act Thêm các thành phần vào stag. 1 0 9 Chương 4 – Xây dựng chuyến trước của trình biên dịch 110 Sơ đồ tổ chức lưu trữ: 4.4.4.4. Con trỏ Nhánh luật pointer là 1 phần trong hệ thống luật khai báo biến. Hệ thống luật sinh phân tích phần khai báo con trỏ bao gồm: Luật sinh Luật ngữ nghĩa (mô tả vắn tắt) pointer  unqualified_pointer $$ = $1; pointer  unqualified_pointer pointer $$ = $1 ; $$->next = $2 ; DCL_TYPE($2) = POINTER; unqualified_pointer  '*' $$ = newLink(DECLARATOR); DCL_TYPE($$) = POINTER; Bảng 4.11. Hệ thống luật dành cho khai báo con trỏ Ví dụ 4.22: Xây dựng cây cú pháp cho khai báo con trỏ kiểu integer: int *x; structdef: “PS” 2 tag size fields symbol : “x” “_x” NULL name rname type etype next symlink : SPECIFIER NULL _class next select: noun b_unsigned b_long V_INT 0 0 Struct Table Hình 4.31. Sơ đồ tổ chức lưu trữ cho kiểu dữ liệu struct Chương 4 – Xây dựng chuyến trước của trình biên dịch 111 Hình 4.32. Cây phân tích cú pháp cho khai báo con trỏ „*‟ pointer unqualified_pointer noun = V_INT noun = V_INT noun = V_INT noun = V_INT act declaration_specifiers declaration_specifiers_ type_specifier type_specifier2 INT type_specifier2 = newLink(SPECIFIER) type_specifier2.noun = V_INT; init_declarator_list init_declarator declarator file program external_definition declaration act addSymChain (declaration); „;‟ act act init_declarator_list.type = declaration_specifiers; init_declarator_list.etype = declaration_specifiers; declaration = reverseSyms(init_declarator_list); indentifier = newSymbol(“x”) act declarator3 declarator2 indentifier IDENTIFIER name = “x” name = “x” name = “x” dcl_type = POINTER act 1 1 1 Chương 4 – Xây dựng chuyến trước của trình biên dịch 112 Sơ đồ lưu trữ: 4.4.4.5. Typedef Khai báo typedef có dạng: typedef oldtype newtype; Trong đó:  oldtype: Kiểu dữ liệu cơ sở (int, short, long) hoặc là struct.  newtype: Tên kiểu dữ liệu mới. Hệ thống luật sinh phân tích typedef là một phần trong hệ thống luật phân tích kiểu như trong Bảng 4.6. Ví dụ 4.23: Với định nghĩa kiểu liệu integer : typedef int INT; Ta sẽ hình thành cây phân tích cú pháp để lan truyền các thông tin khai báo, phục vụ cho việc cập nhật bảng lưu trữ các thông tin typedef: symbol : “x” “_x” NULL name rname type etype next symlink : SPECIFIER NULL _class next select: noun b_unsigned V_INT 0 symlink: DECLARATOR _class next select: dcl_type num_elem POINTER 0 Symbol Table Hình 4.33 Sơ đồ lưu trữ cho khai báo int *x; Chương 4 – Xây dựng chuyến trước của trình biên dịch 113 Hình 4.34. Cây phân tích cú pháp cho khai báo typedef init_declarator_list init_declarator declarator declarator3 declarator2 indentifier IDENTIFIER indentifier = newSymbol(“x”) act name = “x” name = “x” name = “x” name = “x” name = “x” name = “x” storage_class_specifier b_typedef = 1 declaration_specifiers_ declaration_specifiers declaration_specifiers_ act type_specifier type_specifier2 INT type_specifier2 = newLink(SPECIFIER) type_specifier2.noun = V_INT; noun = V_INT noun = V_INT noun = V_INT TYPEDEF act storage_class_specifier.b_typedef = 1; file program external_definition declaration act addSymChain (declaration); „;‟ act act init_declarator_list.type = declaration_specifiers; init_declarator_list.etype = declaration_specifiers; declaration = reverseSyms(init_declarator_list); 1 1 3 Chương 4 – Xây dựng chuyến trước của trình biên dịch 114 Tổ chức lưu trữ Khi khai báo typedef, trình biên dịch sẽ tiến hành tạo ra một danh biểu tương ứng với kiểu dữ liệu mới và thêm vào bảng danh biểu khai báo biến (symbol table). Đồng thời cũng tiến hành thêm vào bảng Typedef để khi trình phân tích từ vựng cần kiểm tra xem lexeme có phải là một kiểu dữ liệu hay không. Symbol Table symbol: “INT” “” NULL name rname type etype next symlink: SPECIFIER _class next select: noun b_typedef V_INT 1 Typedef Table symbol: “INT” “” NULL name rname type etype next symlink: SPECIFIER _class next select: noun b_typedef V_INT 1 Hình 4.35. Tổ chức lưu trữ typedef Chương 5 – Tỗng kết 115 CHƢƠNG 5: TỔNG KẾT 5.1. KẾT QUẢ Xây dựng một trình biên dịch hoàn chỉnh là một công việc đòi hỏi có nhiều đầu tư về thời gian, nhân lực, cũng như một khối lượng kiến thức lớn. Do đó, khuôn khổ khóa luận tập trung chủ yếu vào việc thu thập và tích lũy các thông tin từ chương trình nguồn để tạo ra một dạng biễu diễn trung gian (mã 3-địa chỉ) tương đương. Với định hướng đó, nhóm sinh viên đã phần nào hoàn thành việc : - Nghiên cứu các kỹ thuật xây dựng trình biên dịch, đặc biệt là chuyến trước của trình biên dịch. - Khảo sát 2 công cụ hỗ trợ đắc lực cho việc phát sinh bộ phân tích từ vựng (FLEX) và bộ phân tích cú pháp (BISON). - Từ những kiến thức nghiên cứu được, nhóm sinh viên đã xây dựng thử nghiệm thành công chuyến trước của trình biên dịch cho ngôn ngữ ANSI C giản lược và hướng tới những họ vi xử lý hạn hẹp về tài nguyên. Với kết quả là bộ mã 3-địa chỉ, chương trình đã thành công trong việc phân tích mã nguồn một cách chi tiết, đầy đủ và chân thật nhất. - Giải quyết các bài toán nảy sinh trong thực tế, vốn không được đề cập trong tài liệu. 5.2. HẠN CHẾ Mặc dù đã cố gắng để có thể tích lũy một khối lượng lớn thông tin từ chương trình nguồn, chuyến trước của trình biên dịch mà nhóm sinh viên xây dựng vẫn chưa đáp ứng được một số cấu trúc của chương trình C chuẩn: - Chưa giải quyết được cấu trúc enum, union. - Chưa hỗ trợ dấu chấm động. - Chưa xử lý lỗi một cách chi tiết. 5.3. HƢỚNG PHÁT TRIỂN - Giải quyết những hạn chế một cách hoàn chỉnh. Chương 5 – Tỗng kết 116 - Tiếp tục phát triển chuyến trước để có thể thu thập nhiều thông tin hơn, hỗ trợ đắc lực cho việc xử lý lỗi cũng như sửa lỗi. - Từ bộ mã trung gian, ta hoàn toàn có cơ sở để tiếp tục nghiên cứu và phát sinh ra mã đích (mã hợp ngữ) cho một hệ thống xác định. Phụ lục 117 PHỤ LỤC PHỤ LỤC 1: Bảng xác định độ ƣu tiên của các toán tử. Độ ưu tiên Toán tử Mô tả Thứ tự kết hợp 1 ++ -- () [] . -> Dạng hậu tố (VD : a++, b--) Lời gọi hàm, thủ tục Truy xuất mảng Truy xuất cấu trúc thành phần Truy xuất cấu trúc thành phần qua con trỏ Trái sang phải 2 ++ -- + - ! ~ (type) * & Dạng tiền tố (VD : ++a, --b) Toán tử đơn (VD : -a, +b) Toán tử NOT logic và NOT bit. Ép kiểu dữ liệu (casting) Lấy giá trị tại địa chỉ (dereference) Lấy địa chỉ Phải sang trái 3 * / % Toán tử nhân, chia nguyên, chia dư Trái sang phải 4 + - Toán tử cộng, trừ 5 > Toán tử dịch trái, dịch phải 6 < <= > >= Toán tử so sánh lớn (nhỏ) 7 == != Toán tử so sánh bằng (không bằng) 8 & Toán tử and bit 9 ^ Toán tử xor bit 10 | Toán tử or bit 11 && Toán tử logic and 12 || Toán tử logic or 13 c?t:f Biểu thức điều kiện Phải sang trái 14 = += -= *= /= %= <<= >>= &= ^= |= Toán tử gán Gán bằng tổng/hiệu Gán bằng tích/thương/phần dư Gán bằng phép toán dịch trái, dịch phải Gán bằng phép and, xor, or bit. Phụ lục 118 PHỤ LỤC 2: Dịch chƣơng trình mẫu. int a1; unsigned int a2; char a3; unsigned char a4; long a5; unsigned long a6; int a7[5]; int a8[10]; int a9[5][5][5][5][5]; char a10[5][5][5]; typedef struct tagLienPhanSo { int ts; int msn; struct { int dum1,dum2,dum3; struct{ long dum4,dum5; }dumstruct; }dumdumstruct; struct tagLienPhanSo *mslps; } LienPhanSo; typedef LienPhanSo LPS; int Fibonacci(int n) { if (n==0 || n==1) return 1; return Fibonacci(n-1) + Fibonacci(n-2); } void TestScope() { char *add; { int add; } { int add; } { add[3] = 1; } } Phụ lục 119 int IsJustAPrototype(int dummy); int GetValue(int *p) { IsJustAPrototype((int)('c')); return p?*p:0; } char Calculation(int a1,long a2, char a3, short a4, unsigned int a5, unsigned long a6, unsigned char a7, unsigned short a8) { unsigned long sum; int a9, a10; { int a9, a10; a10 = (a1 + a2)>>a3; a9 = (a10>0) && (a10<100); sum += a9; } { a10 = 5; } sum -= a4 + (a5++)*(--a6)/a7; return sum; } void TestArrayPointer() { int *p1, *p2, *p3; int a1[10], a2[10][10], a3[5]; p3 = p1 - p2++; a1[3] = a2[1][1+a3[5]]; a8[1] = 8; a9[0][1][0][1][0] = 9; a5 = a8[0] + a9[0][1][0][1][0]; } void TestStruct() { LPS a; LienPhanSo b; struct tagLienPhanSo c; a.ts = b.msn; b.msn = c.mslps->ts; a.mslps->mslps->mslps->ts = 10; } Phụ lục 120 void TestSwitch() { int x; switch(x) { case 1: x = 2; case 2: x = 3; break; default: x = 0; } } void main(char **argv, int argc) { int i, j; int n[100]; for (i = 0; i<100;i++) for (j = i+1; j<100;j++) if ((n[i] < n[j]) && (GetValue(0) == 0)) { n[(i+j) % 100] = 'a'; } } Mã 3-địa chỉ : BEGIN FUNCTION : Fibonacci n = RECEIVE(Fibonacci) TST1: iTemp0 = (n == 0) IFTRUE(iTemp0) GOTO : T1 iTemp1 = (n == 1) IFTRUE(iTemp1) GOTO : T1 F1: iTemp2 = 0 GOTO : E1 T1: iTemp2 = 1 Phụ lục 121 E1: IFFALSE(iTemp2) GOTO : EXIT1 RETURN 1 EXIT1: iTemp3 = CAST(1) iTemp4 = n - iTemp3 SEND : iTemp4 iTemp5 = CALL(Fibonacci) iTemp6 = CAST(2) iTemp7 = n - iTemp6 SEND : iTemp7 iTemp8 = CALL(Fibonacci) iTemp9 = iTemp5 + iTemp8 RETURN iTemp9 END FUNCTION BEGIN FUNCTION : TestScope iTemp10 = add + 3 iTemp10 = 1 END FUNCTION BEGIN FUNCTION : GetValue p = RECEIVE(GetValue) iTemp11 = CAST(99) SEND : iTemp11 iTemp12 = CALL(IsJustAPrototype) IFFALSE(p) GOTO : QF1 iTemp13 = *(p) GOTO : QE1 QF1: iTemp13 = 0 QE1: RETURN iTemp13 END FUNCTION Phụ lục 122 BEGIN FUNCTION : Calculation a1 = RECEIVE(Calculation) a2 = RECEIVE(Calculation) a3 = RECEIVE(Calculation) a4 = RECEIVE(Calculation) a5 = RECEIVE(Calculation) a6 = RECEIVE(Calculation) a7 = RECEIVE(Calculation) a8 = RECEIVE(Calculation) iTemp14 = CAST(a1) iTemp15 = iTemp14 + a2 iTemp16 = iTemp15 >> a3 a10 = iTemp16 iTemp17 = (a10 > 0) IFFALSE(iTemp17) GOTO : F2 iTemp18 = (a10 < 100) IFFALSE(iTemp18) GOTO : F2 GOTO : T2 F2: iTemp19 = 0 GOTO : E2 T2: iTemp19 = 1 E2: a9 = iTemp19 iTemp20 = CAST(a9) iTemp21 = sum + iTemp20 sum = iTemp21 a10 = 5 iTemp22 = a5 iTemp23 = a5 + 1 a5 = iTemp23 iTemp24 = a6 - 1 a6 = iTemp24 iTemp25 = CAST(iTemp22) iTemp26 = iTemp25 * a6 Phụ lục 123 iTemp27 = CAST(a7) iTemp28 = iTemp26 / iTemp27 iTemp29 = CAST(a4) iTemp30 = iTemp29 + iTemp28 iTemp31 = sum - iTemp30 sum = iTemp31 RETURN sum END FUNCTION BEGIN FUNCTION : TestArrayPointer iTemp32 = p2 iTemp33 = p2 + 2 p2 = iTemp33 iTemp34 = p1 - iTemp32 iTemp35 = CAST(2) iTemp36 = iTemp34 / iTemp35 p3 = iTemp36 iTemp37 = &(a1) iTemp38 = iTemp37 + 6 iTemp39 = &(a2) iTemp40 = iTemp39 + 20 iTemp41 = &(a3) iTemp42 = iTemp41 + 10 iTemp43 = *(iTemp42) iTemp44 = CAST(1) iTemp45 = iTemp44 + iTemp43 iTemp46 = CAST(2) iTemp47 = iTemp46 * iTemp45 iTemp48 = iTemp40 + iTemp47 iTemp49 = *(iTemp38) iTemp50 = *(iTemp48) iTemp49 = iTemp50 iTemp51 = &(a8) iTemp52 = iTemp51 + 2 iTemp53 = *(iTemp52) iTemp53 = 8 iTemp54 = &(a9) iTemp55 = iTemp54 + 250 Phụ lục 124 iTemp56 = iTemp55 + 10 iTemp57 = *(iTemp56) iTemp57 = 9 iTemp58 = &(a8) iTemp59 = &(a9) iTemp60 = iTemp59 + 250 iTemp61 = iTemp60 + 10 iTemp62 = *(iTemp58) iTemp63 = *(iTemp61) iTemp64 = iTemp62 + iTemp63 a5 = iTemp64 END FUNCTION BEGIN FUNCTION : TestStruct iTemp65 = &(a) iTemp66 = iTemp65 + 0 iTemp67 = &(b) iTemp68 = iTemp67 + 2 iTemp69 = *(iTemp66) iTemp70 = *(iTemp68) iTemp69 = iTemp70 iTemp71 = &(b) iTemp72 = iTemp71 + 2 iTemp73 = &(c) iTemp74 = iTemp73 + 18 iTemp75 = iTemp74 + 0 iTemp76 = *(iTemp72) iTemp77 = *(iTemp75) iTemp76 = iTemp77 iTemp78 = &(a) iTemp79 = iTemp78 + 18 iTemp80 = iTemp79 + 18 iTemp81 = iTemp80 + 18 iTemp82 = iTemp81 + 0 iTemp83 = *(iTemp82) iTemp83 = 10 END FUNCTION Phụ lục 125 BEGIN FUNCTION : TestSwitch GOTO : SW1 SW3: x = 2 SW4: x = 3 GOTO : SW2 SW5: x = 0 GOTO : SW2 SW1: iTemp84 = (x == 1) IFTRUE(iTemp84) GOTO : SW3 iTemp85 = (x == 2) IFTRUE(iTemp85) GOTO : SW4 GOTO : SW5 SW2: END FUNCTION BEGIN FUNCTION : main argv = RECEIVE(main) argc = RECEIVE(main) i = 0 TST2: iTemp86 = (i < 100) IFFALSE(iTemp86) GOTO : EXIT2 GOTO : BDY2 INC2: iTemp87 = i iTemp88 = i + 1 i = iTemp88 GOTO : TST2 BDY2: iTemp89 = CAST(1) iTemp90 = i + iTemp89 Phụ lục 126 j = iTemp90 TST3: iTemp91 = (j < 100) IFFALSE(iTemp91) GOTO : EXIT3 GOTO : BDY3 INC3: iTemp92 = j iTemp93 = j + 1 j = iTemp93 GOTO : TST3 BDY3: TST4: iTemp94 = &(n) iTemp95 = CAST(2) iTemp96 = iTemp95 * i iTemp97 = iTemp94 + iTemp96 iTemp98 = &(n) iTemp99 = CAST(2) iTemp100 = iTemp99 * j iTemp101 = iTemp98 + iTemp100 iTemp102 = *(iTemp97) iTemp103 = *(iTemp101) iTemp104 = (iTemp102 < iTemp103) IFFALSE(iTemp104) GOTO : F3 SEND : 0 iTemp105 = CALL(GetValue) iTemp106 = (iTemp105 == 0) IFFALSE(iTemp106) GOTO : F3 GOTO : T3 F3: iTemp107 = 0 GOTO : E3 T3: iTemp107 = 1 E3: IFFALSE(iTemp107) Phụ lục 127 GOTO : EXIT4 iTemp108 = &(n) iTemp109 = i + j iTemp110 = CAST(100) iTemp111 = iTemp109 MOD iTemp110 iTemp112 = CAST(2) iTemp113 = iTemp112 * iTemp111 iTemp114 = iTemp108 + iTemp113 iTemp115 = *(iTemp114) iTemp115 = 97 EXIT4: GOTO : INC3 EXIT3: GOTO : INC2 EXIT2: END FUNCTION Thông tin bảng danh biểu: Symbol table Hash key 18 - Sym 00591F20, name 'TestSwitch', level 0 block 0 Hash key 29 - Sym 0055CF10, name 'GetValue', level 0 block 0 Hash key 37 - Sym 00583180, name 'TestStruct', level 0 block 0 Hash key 41 - Sym 0055C808, name 'add', level 2 block 3, local of 'TestScope' - Sym 0055C6A0, name 'add', level 2 block 2, local of 'TestScope' - Sym 0055C538, name 'add', level 1 block 1, local of 'TestScope' Hash key 44 - Sym 0055CDA8, name 'dummy', level 1 block 1, param of function 'IsJustAPrototype' Hash key 85 - Sym 00563FC8, name 'sum', level 1 block 1, local of 'Calculation' Phụ lục 128 Hash key 97 - Sym 005832E8, name 'a', level 1 block 1, local of 'TestStruct' Hash key 98 - Sym 00583450, name 'b', level 1 block 1, local of 'TestStruct' Hash key 99 - Sym 00583888, name 'c', level 1 block 1, local of 'TestStruct' Hash key 105 - Sym 00595760, name 'i', level 1 block 1, local of 'main' Hash key 106 - Sym 005958C8, name 'j', level 1 block 1, local of 'main' Hash key 110 - Sym 00595A30, name 'n', level 1 block 1, local of 'main' - Sym 00557E30, name 'n', level 1 block 1, param of function 'Fibonacci' Hash key 111 - Sym 00563320, name 'Calculation', level 0 block 0 Hash key 112 - Sym 005623A8, name 'p', level 1 block 1, param of function 'GetValue' Hash key 120 - Sym 00592088, name 'x', level 1 block 1, local of 'TestSwitch' Hash key 121 - Sym 0055CC40, name 'IsJustAPrototype', level 0 block 0 Hash key 126 - Sym 00557CC8, name 'Fibonacci', level 0 block 0 Hash key 128 - Sym 00576BA8, name 'TestArrayPointer', level 0 block 0 Hash key 146 - Sym 00577148, name 'a1', level 1 block 1, local of 'TestArrayPointer' - Sym 00563488, name 'a1', level 1 block 1, param of function 'Calculation' - Sym 00208158, name 'a1', level 0 block 0 Hash key 147 - Sym 005772B0, name 'a2', level 1 block 1, local of 'TestArrayPointer' - Sym 005635F0, name 'a2', level 1 block 1, param of function 'Calculation' - Sym 002086E8, name 'a2', level 0 block 0 Phụ lục 129 Hash key 148 - Sym 00577418, name 'a3', level 1 block 1, local of 'TestArrayPointer' - Sym 00563758, name 'a3', level 1 block 1, param of function 'Calculation' - Sym 00208C78, name 'a3', level 0 block 0 Hash key 149 - Sym 005638C0, name 'a4', level 1 block 1, param of function 'Calculation' - Sym 002092A0, name 'a4', level 0 block 0 Hash key 150 - Sym 00563A28, name 'a5', level 1 block 1, param of function 'Calculation' - Sym 00209868, name 'a5', level 0 block 0 Hash key 151 - Sym 00563B90, name 'a6', level 1 block 1, param of function 'Calculation' - Sym 005517F8, name 'a6', level 0 block 0 Hash key 152 - Sym 00563CF8, name 'a7', level 1 block 1, param of function 'Calculation' - Sym 00551CC8, name 'a7', level 0 block 0 Hash key 153 - Sym 00563E60, name 'a8', level 1 block 1, param of function 'Calculation' - Sym 0020E330, name 'a8', level 0 block 0 Hash key 154 - Sym 0056BD10, name 'a9', level 2 block 2, local of 'Calculation' - Sym 00564130, name 'a9', level 1 block 1, local of 'Calculation' - Sym 0055C3D0, name 'TestScope', level 0 block 0 - Sym 0020E908, name 'a9', level 0 block 0 Hash key 157 - Sym 005955F8, name 'argc', level 1 block 1, param of function 'main' Hash key 161 - Sym 00576D10, name 'p1', level 1 block 1, local of 'TestArrayPointer' Hash key 162 - Sym 00576E78, name 'p2', level 1 block 1, local of 'TestArrayPointer' Hash key 163 Phụ lục 130 - Sym 00576FE0, name 'p3', level 1 block 1, local of 'TestArrayPointer' Hash key 165 - Sym 00595328, name 'main', level 0 block 0 Hash key 176 - Sym 00595490, name 'argv', level 1 block 1, param of function 'main' Hash key 194 - Sym 0056BE78, name 'a10', level 2 block 2, local of 'Calculation' - Sym 0056BBA8, name 'a10', level 1 block 1, local of 'Calculation' - Sym 00554220, name 'a10', level 0 block 0 Hash key 209 - Sym 005579F8, name 'LienPhanSo', level 0 block 0 Hash key 239 - Sym 00557B60, name 'LPS', level 0 block 0 Typedef table Hash key 209 - Sym 005579F8, name 'LienPhanSo', level 0 block 0 Hash key 239 - Sym 00557B60, name 'LPS', level 0 block 0 StructTab table Hash key 13 - Sym 005565F8, name 'tagLienPhanSo', level 0 block 0 Hash key 64 - Sym 005569C8, name '__00020000', level 2 block 0 Hash key 66 - Sym 00556F00, name '__00030001', level 3 block 0 Quản lý bộ nhớ : Segment: data Item: - 'a1' type: int - 'a2' type: unsigned int - 'a3' type: char - 'a4' type: unsigned char - 'a5' type: long Phụ lục 131 - 'a6' type: unsigned long - 'a7' type: int [5] - 'a8' type: int [10] - 'a9' type: int [5] [5] [5] [5] [5] - 'a10' type: char [5] [5] [5] - 'Fibonacci' type: int function - 'TestScope' type: void function - 'IsJustAPrototype' type: int function - 'GetValue' type: int function - 'Calculation' type: char function - 'TestArrayPointer' type: void function - 'TestStruct' type: void function - 'TestSwitch' type: void function - 'main' type: void function Segment: code Item: - 'Fibonacci' type: int function - 'TestScope' type: void function - 'IsJustAPrototype' type: int function - 'GetValue' type: int function - 'Calculation' type: char function - 'TestArrayPointer' type: void function - 'TestStruct' type: void function - 'TestSwitch' type: void function - 'main' type: void function Segment: stack Item: - 'n', type: int , on func 'Fibonacci', stack offset 0 - 'add', type: char * , on func 'TestScope', stack offset 0 - 'add', type: int , on func 'TestScope', stack offset 2 - 'add', type: int , on func 'TestScope', stack offset 4 - 'p', type: int * , on func 'GetValue', stack offset 0 - 'a1', type: int , on func 'Calculation', stack offset 0 - 'a2', type: long , on func 'Calculation', stack offset 2 - 'a3', type: char , on func 'Calculation', stack offset 6 - 'a4', type: int , on func 'Calculation', stack offset 7 - 'a5', type: unsigned int , on func 'Calculation', stack offset 9 - 'a6', type: unsigned long , on func 'Calculation', stack offset 11 Phụ lục 132 - 'a7', type: unsigned char , on func 'Calculation', stack offset 15 - 'a8', type: unsigned int , on func 'Calculation', stack offset 16 - 'sum', type: unsigned long , on func 'Calculation', stack offset 18 - 'a9', type: int , on func 'Calculation', stack offset 22 - 'a10', type: int , on func 'Calculation', stack offset 24 - 'a9', type: int , on func 'Calculation', stack offset 26 - 'a10', type: int , on func 'Calculation', stack offset 28 - 'p1', type: int * , on func 'TestArrayPointer', stack offset 0 - 'p2', type: int * , on func 'TestArrayPointer', stack offset 2 - 'p3', type: int * , on func 'TestArrayPointer', stack offset 4 - 'a1', type: int [10] , on func 'TestArrayPointer', stack offset 6 - 'a2', type: int [10] [10] , on func 'TestArrayPointer', stack offset 26 - 'a3', type: int [5] , on func 'TestArrayPointer', stack offset 226 - 'a', type: struct , on func 'TestStruct', stack offset 0 - 'b', type: struct , on func 'TestStruct', stack offset 20 - 'c', type: struct , on func 'TestStruct', stack offset 40 - 'x', type: int , on func 'TestSwitch', stack offset 0 - 'argv', type: char * * , on func 'main', stack offset 0 - 'argc', type: int , on func 'main', stack offset 2 - 'i', type: int , on func 'main', stack offset 4 - 'j', type: int , on func 'main', stack offset 6 - 'n', type: int [100] , on func 'main', stack offset 8 Tham khảo 133 THAM KHẢO [1] Alfred. V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles, Techniques and Tools, 2 nd ed., Addison Wesley, 2007. [2] Alfred. V. Aho, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles, Techniques and Tools, 1st ed., Addison Wesley, 1986. [3] Allen I.Hollub, Compiler Design In C, Addison Wesley, 1990. [4] John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison Wesley, 2001. [5] John R. Levine, Flex & Bison, 1st ed., O‟Reilly Media, Inc., 2009. [6] Niklaus Wirth, Compiler Construction, Addision Wesley, 1996. [7] Charles Donnelly, Richard Stallman, Bison – The Yacc-compatible Parser Generator, Free Software Foundation, 2009. [8] Muchnick, Steven, Advanced Compiler Design and Implementation, Morgan Kaufmann Publishers, 1997 [9]