Đề tài Chương trình dịch

I. Giới thiệu chung về trình biên dịch Trình biên dịch (compiler) là một chương trình đọc một chương trình khác viết bằng một ngôn ngữ - gọi là ngôn ngữ nguồn- và chuyển đổi nó thành một chương trình tương đương viết bằng ngôn ngữ khác – gọi là ngôn ngữ đích. Sơ đồ tổng quan cho trình biên dịch: / Các thành phần chính của trình biên dịch / II. Các thành phần chính của trình biên dịch Bộ phân tích từ vựng Nhiệm vụ của bộ phân tích từ vựng là đọc các kí tự đầu vào và sảnh sinh ra các từ tố. Các từ tố này được bộ parser sử dụng để phân tích cú pháp. Mục đích sử dụng bộ phân tích từ vựng: Làm đơn giản hóa việc thiết kế chương trình dịch Cung cấp một cách thức thực thi hiệu quả. Làm tăng tính linh hoạt Sử dụng máy otomat hữ hạn để thực hiện bộ phân tích từ vựng Máy otomat hữu hạn là một bộ 5 (S,Σ,δ,s0,F ) trong đó: S là tập hữu hạn các trạng thái Σ là tập hữu hạn các kí tự (alphabet). δ là tập các ánh xạ từ SxΣ sang tập trạng thái s0 ∈ S là các trạng thái đầu F là tập các trạng thái kết thúc. Không có chuyển trạng thái 𝜖 Với mỗi trạng thái s và một kí tự đầu vào a, có tối đa một cạnh đi ra từ s có nhãn là a. / Code thực hiện máy otomat hữu hạn trong file scanner.c Token* getToken(void) { Token *token; int ln, cn; if (currentChar == EOF) // nếu là kí tự kết thúc file return makeToken(TK_EOF, lineNo, colNo); // trả về token kết thúc switch (charCodes[currentChar]) { case CHAR_SPACE: skipBlank(); return getToken(); // bỏ qua khoảng trắng, đọc token // tiếp theo case CHAR_LETTER: return readIdentKeyword(); // token là identifier case CHAR_DIGIT: return readNumber(); // token là số, gọi hàm đọc token số case CHAR_PLUS: // token là dấu ‘+’ token = makeToken(SB_PLUS, lineNo, colNo); // trả lại token là dấu ‘+’ readChar(); // đọc kí tự tiếp return token; case CHAR_MINUS: //token là dấu ‘-’ token = makeToken(SB_MINUS, lineNo, colNo); readChar(); return token; case CHAR_TIMES: // token là dấu ‘*’ token = makeToken(SB_TIMES, lineNo, colNo); readChar(); return token; case CHAR_SLASH:// token là dấu ‘/’ token = makeToken(SB_SLASH, lineNo, colNo); readChar(); return token; case CHAR_LT: // gặp dấu ‘<’ ln = lineNo; cn = colNo; readChar(); // kiểm tra nếu tiếp theo là dấu ‘=’ if ((currentChar != EOF) && (charCodes[currentChar] == CHAR_EQ)) { / readChar(); return makeToken(SB_LE, ln, cn); // token là dấu ‘<=’ } else return makeToken(SB_LT, ln, cn); // token là dấu ‘<’ case CHAR_GT: // gặp dấu ‘>’ ln = lineNo; cn = colNo; readChar(); // kiểm tra kí tự tiếp theo là dấu ‘=’ if ((currentChar != EOF) && (charCodes[currentChar] == CHAR_EQ)) { readChar(); return makeToken(SB_GE, ln, cn); // token là dấu ‘>=’ } else return makeToken(SB_GT, ln, cn); case CHAR_EQ: // token là dấu ‘=’ token = makeToken(SB_EQ, lineNo, colNo); readChar(); return token; case CHAR_EXCLAIMATION:// gặp dấu ‘!’ ln = lineNo; cn = colNo; readChar(); // kiểm tra kí tự tiếp là dấu ‘=’ if ((currentChar != EOF) && (charCodes[currentChar] == CHAR_EQ)) { readChar(); return makeToken(SB_NEQ, ln, cn); // token là dấu ‘!=‘ } else { // nếu kí tự tiếp không phải là dấu ‘=’, báo lỗi token = makeToken(TK_NONE, ln, cn); error(ERR_INVALIDSYMBOL, ln, cn); return token; } case CHAR_COMMA: // token là dấu ‘,’ token = makeToken(SB_COMMA, lineNo, colNo); readChar(); return token; case CHAR_PERIOD: // gặp dấu ‘.’ ln = lineNo; cn = colNo; readChar(); // kiểm tra kí tự tiếp theo là dấu ‘)’ if ((currentChar != EOF) && (charCodes[currentChar] == CHAR_RPAR)) { readChar(); return makeToken(SB_RSEL, ln, cn); // trả lai token là ‘.)’ } else return makeToken(SB_PERIOD, ln, cn); // trả lại token là dấu ‘.’ case CHAR_SEMICOLON: // gặp dấu ‘;’ token = makeToken(SB_SEMICOLON, lineNo, colNo); readChar(); return token; case CHAR_COLON: // gặp dấu ‘:’ ln = lineNo; cn = colNo; readChar(); // kiểm tra kí tự tiếp theo là dấu ‘=’ if ((currentChar != EOF) && (charCodes[currentChar] == CHAR_EQ)) { readChar(); return makeToken(SB_ASSIGN, ln, cn); // trả về token là dấu ‘:=’ } else return makeToken(SB_COLON, ln, cn); // token là dấu ‘:’ case CHAR_SINGLEQUOTE: return readConstChar(); // gặp dấu ‘’’ case CHAR_LPAR: // gặp dấu ‘(’ ln = lineNo; cn = colNo; readChar(); if (currentChar == EOF) // kết thúc file, trả lại token ‘(’ return makeToken(SB_LPAR, ln, cn); //nếu chưa kết thúc file, kiểm tra kí tự tiếp theo switch (charCodes[currentChar]) { case CHAR_PERIOD: // gặp dấu ‘.’ readChar(); return makeToken(SB_LSEL, ln, cn); // token trả về là ‘(.’ case CHAR_TIMES: // găp dấu ‘*’, kí tự là ’(*’ → tiếp theo là comment readChar(); skipComment(); // bỏ qua comment return getToken(); // đọc token tiếp theo default: return makeToken(SB_LPAR, ln, cn); // trả lại token là ‘(’ } case CHAR_RPAR: // gặp dấu ‘)’ token = makeToken(SB_RPAR, lineNo, colNo); readChar(); return token; default :// nếu không gặp các trường hợp trên, báo lỗi. token = makeToken(TK_NONE, lineNo, colNo); error(ERR_INVALIDSYMBOL, lineNo, colNo); readChar(); return token; } } Bộ phân tích cú pháp Định nghĩa: văn phạm phi ngữ cảnh G là một bộ 4 (N,T,P,S) trong đó T là tập hữu hạn các token N là tập hữu hạn các kí tự không kết thúc P là tập các sản xuất S là tập các kí tự đầu. Phép suy dẫn: phép suy dẫn một bước là phép suy dẫn có dạng: 𝛼𝐴𝛽 => 𝛼𝛾𝛽 Trong đó A →𝛾 là một sản xuất trong ngôn ngữ Suy dẫn => gọi là trái nhất =>lm nếu 𝛼 không chứa kí tự không kết thúc Suy dẫn => gọi là trái nhất =>lm nếu 𝛽 không chứa kí tự không kết thúc Ngôn ngữ L(G) sinh ra bởi G có dạng L(G) = {w ∈ T* | S =>+ w} Cho văn phạm phi ngữ cảnh G và xâu w w ∈ L(G) đúng hay sai? Phương pháp phân tích từ trên xuống Văn phạm Suy dẫn trái E → T + T E =>lm T + T T → (E) =>lm id + T T → - E =>lm id + id T → id Phương pháp suy dẫn trái sẽ không thể thực hiện được nếu có đệ quy trái. Do đó bước đầu tiên là ta phải thực hiện loại bỏ đệ quy trái. Ví dụ sản xuất: A → A𝛼 | 𝛽 | 𝛾 Khử đệ quy như sau: A → 𝛽 AR AR → 𝛼 AR | 𝜀 Phương pháp suy dẫn quay lui sẽ không hiệu quả khi có quá nhiều bước quay lui. Vói sản xuất dạng A → 𝛼1|𝛼2 ......|𝛼n nếu biêt trước một kí tự đầu vào, ta sẽ biết được nên chọn sản xuất nào và tránh được quay lui. Sử dụng bộ phân tích tiền định với văn phạm LL(1) để tránh quay lui Ta xét 2 khái niệm FIRST(𝛼) và FOLLOW(A) FIRST(𝛼) là tập các kí hiệu kết thúc được suy dẫn ra từ 𝛼 Cách tính FIRST(𝛼): FIRST(𝑎) = a nếu a là kí hiệu kết thúc FIRST(𝜀) = 𝜀 FIRST(A) = 𝐴→𝛼 𝛼 Với A → 𝛼 là một sản xuất. FIRST(X1 X2 …Xn ) = Nếu mọi j = 1,….,i-1: 𝜀 ∈ FIRST(Xj ) thì thêm FIRST(Xi ) (FIRST(Xi) không chứa 𝜀 ) vào FIRST(X1 X2… Xn) Nếu với mọi j = 1,2,…,n mà 𝜀 ∈ FIRST(Xj ) thì thêm 𝜀 vào FIRST(X1 X2 …Xn) FOLLOW(A) là tập các kí hiệu kết thúc theo sau kí hiệu không kết thúc A FOLLOW(A) = Với mỗi (B →𝛼A𝛽) thêm FIRT(𝛽)\(𝜀) vào FOLLOW(A) Với mỗi (B →𝛼A𝛽) mà 𝜀 ∈ FIRST(𝛽) thì thêm FOLLOW(B) vào FOLLOW(A) Với mỗi (B →𝛼A) thêm FOLLOW(B) vào FOLLOW(A) Nếu A là kí hiệu bắt đầu S, thêm $ vào FOLLOW(A). Văn phạm được gọi là LL(1) nếu thỏa mãn Các sản xuất không đệ quy trái Với mỗi sản xuất A → 𝛼1| 𝛼2…. |𝛼n Ta có FIRST(𝛼i)∩ FIRST(𝛼j) = ∅ với mỗi i ≠ j Nếu 𝛼i =>* 𝜀 thì 𝛼j ≠>* 𝜀 với mọi i ≠ j FIRST(𝛼i) ∩ FOLLOW(A) = ∅ với mọi ≠ j Sử dụng bảng phân tích tiền định để phân tích LL(1) ta sẽ tránh được đệ quy. Cách thức thực hiện đối với ngôn ngữ KPL: Xem trước một token để quyết định sản xuất sử dụng Token *currentToken; // Token vừa đọc Token *lookAhead; // Token xem trước void scan(void) { Token* tmp = currentToken; currentToken = lookAhead; lookAhead = getValidToken(); free(tmp); } Duyệt kí hiệu kết thúc void eat(TokenType tokenType) { if (lookAhead->tokenType == tokenType) { printToken(lookAhead); scan(); // chuyển đến token tiếp theo } else missingToken(tokenType, lookAhead->lineNo, lookAhead->colNo); } Duyệt kí hiệu không kết thúc void compileProgram(void) { assert("Parsing a Program ...."); eat(KW_PROGRAM); eat(TK_IDENT); eat(SB_SEMICOLON); compileBlock(); eat(SB_PERIOD); assert("Program parsed!"); } Với kí hiệu không kết thúc statement. Ta có FIRST(statement) = { TK_IDENT, KW_CALL, KW_BEGIN, KW_IF, KW_WHILE, KW_FOR, 𝜺} FOLLOW(statement) = {SB_SEMICOLON, KW_END, KW_ELSE} Input các sản xuất sử dụng TK_IDENT Statement ::= assignment KW_CALL Statement ::= Callst KW_BEGIN Statement ::= Groupst KW_IF Statement ::= IFst KW_WHILE Statement ::= Whilest KW_FOR Statement ::= Forst SB_SEMICOLON Statement ::= 𝜺 KW_END Statement ::= 𝜺 KW_ELSE Statement ::= 𝜺 Other error Thực hiện bằng code void compileStatement(void) { switch (lookAhead->tokenType) { case TK_IDENT: compileAssignSt(); break; case KW_CALL: compileCallSt(); break; case KW_BEGIN: compileGroupSt(); break; case KW_IF: compileIfSt(); break; case KW_WHILE: compileWhileSt(); break; case KW_FOR: compileForSt(); break; // Đọc câu lệnh rỗng, kiểm tra FOLLOW để quyết định sản xuất sử // dụng case SB_SEMICOLON: case KW_END: case KW_ELSE: break; // Báo lỗi default: error(ERR_INVALIDSTATEMENT, lookAhead->lineNo, lookAhead->colNo); break; } } Bộ phân tích ngữ nghĩa Mục đích của bộ phân tích ngữ nghĩa: tìm ra lỗi sau giai đoạn phân tích cú pháp Kiểm tra sự tương ứng về kiểu Kiểm tra sự tương ứng giữa việc sử dụng hàm, biến với khai báo của chúng. Xác định phạm vi ảnh hưởng của biến trong chương trình. Sau đây chúng ta xem xét cụ thể việc phân tích ngữ nghĩa trong KPL Việc đầu tiên là khởi tạo bảng kí hiệu SymTab. Bảng này có cấu trúc như sau: struct SymTab_ { Object* program; // chương trình chính Scope* currentScope; // lưu giữ phạm vi hiện tại ObjectNode *globalObjectList; // chứa các đối tượng toàn cục }; Khởi tạo chương trình bằng hàm compileProgram(void) , sau khi khởi tạo chuyển vào block chính void enterBlock(Scope* scope) { symtab->currentScope = scope; // thay đổi phạm vi của bảng symtab. } Chuyển vào chương trình chính bằng cách gọi enterBlock(program->progAttrs->scope). Như vậy việc chuyển chính là thay scope hiện tại của bảng symtab bằng scope của block chính. Mỗi đối tượng scope sẽ có 3 tham số chính struct Scope_ { ObjectNode *objList; // lưu các đối tượng thuộc cùng một phạm vi Object *owner; // đối tượng sở hữu phạm vi (hàm, thủ tục, chương trình) struct Scope_ *outer; // liên kết tới phạm vi bên ngoài }; Như vậy, khi thoát ra ngoài một block, chúng ta chỉ việc liên kết phạm vi đó tới phạm vi bên ngoài bằng hàm exitBlock() void exitBlock(void) { symtab->currentScope = symtab->currentScope->outer; // liên kết tới phạm vi bên ngoài } Mỗi đối tượng hằng, biến, kiểu, hàm, thủ tục, chương trình sau khi duyệt xong đều được đưa vào bảng kí hiệu. Các đối tượng có cùng phạm vi thì sẽ được đưa vào cùng một phạm vi. Thủ tục đưa vào bảng kí hiệu như sau addObject(&(symtab->currentScope->objList), obj); Riêng đối với các đối tượng là PARAMETER,ta còn phải đưa vào parameter List của hàm hay thủ tục chứa nó. if (obj->kind == OBJ_PARAMETER) { Object* owner = symtab->currentScope->owner; switch (owner->kind) { case OBJ_FUNCTION: addObject(&(owner->funcAttrs->paramList), obj); // đưa vào parameter List // của hàm break; case OBJ_PROCEDURE: addObject(&(owner->procAttrs->paramList), obj); // đưa vào parameter List //của thủ tục break; default: break; } } Mỗi khi duyệt đến hàm hay thủ tục, một phạm vi mới được tạo ra. Các khai báo cục bộ sẽ nằm ở trong phạm vi này. Do đó các biến khai báo trong phạm vi cục bộ có thể trùng tên với các biến bên ngoài phạm vi đó. Dựa vào bảng kí hiệu này để kiểm tra ngữ nghĩa của chương trình. Kiểm tra khai báo identifier trong phạm vi hiện tại void checkFreshIdent(char *name) { if (findObject(symtab->currentScope->objList, name) != NULL) // tìm trong phạm vi // hiện tại error(ERR_DUPLICATE_IDENT, currentToken->lineNo, currentToken->colNo); } Kiểm tra indentifier trong phạm vi hiện tại và cả phạm vi bên ngoài Object* checkDeclaredIdent(char* name) { Object* obj = lookupObject(name); // tìm kiêm trong các phạm vi có thể if (obj == NULL) error(ERR_UNDECLARED_IDENT,currentToken->lineNo, currentToken->colNo); return obj; } Ngoài ra còn các hàm kiểm tra các tham số khác, việc kiểm tra này ở cả phạm vi bên trong và bên ngoài Object* checkDeclaredConstant(char* name) ; // kiểm tra hằng đã khai báo hay chưa Object* checkDeclaredType(char* name); // kiểm tra kiểu đã khai báo hay chưa Object* checkDeclaredVariable(char* name) ; // kiểm tra biến đã khai báo hay chưa Object* checkDeclaredFunction(char* name) ; // kiểm tra hàm đã khai báo hay chưa Object* checkDeclaredProcedure(char* name) ; // kiểm tra thủ tục đã khai báo hay chưa Object* checkDeclaredLValueIdent(char* name) { // kiểm tra identifier trong lệnh gán Object* obj = lookupObject(name); Scope* scope; if (obj == NULL) // nếu chưa khai báo, báo lỗi. error(ERR_UNDECLARED_IDENT,currentToken->lineNo, currentToken->colNo); switch (obj->kind) { case OBJ_VARIABLE: // nếu là biến, ok case OBJ_PARAMETER: // nếu là parameter, ok break; case OBJ_FUNCTION: // nếu lệnh gán cho hàm thì phải kiểm tra lệnh gán //đó có nằm trong hàm đó hay không scope = symtab->currentScope; while ((scope != NULL) && (scope != obj->funcAttrs->scope)) scope = scope->outer; if (scope == NULL) // nếu không phải là 3 loại trên, báo lỗi error(ERR_INVALID_IDENT,currentToken->lineNo, currentToken->colNo); break; default: error(ERR_INVALID_IDENT,currentToken->lineNo, currentToken->colNo); } return obj; } Các hàm kiểm tra kiểu: void checkIntType(Type* type) { // kiểm tra kiểu INT if ((type != NULL) && (type->typeClass == TP_INT)) return; else error(ERR_TYPE_INCONSISTENCY, currentToken->lineNo, currentToken->colNo); } void checkCharType(Type* type) { // kiểm tra kiểu Char if ((type != NULL) && (type->typeClass == TP_CHAR)) return; else error(ERR_TYPE_INCONSISTENCY, currentToken->lineNo, currentToken->colNo); } void checkBasicType(Type* type) { // kiểm tra kiểu là INT hay CHAR if ((type != NULL) && ((type->typeClass == TP_INT) || (type->typeClass == TP_CHAR))) return; else error(ERR_TYPE_INCONSISTENCY, currentToken->lineNo, currentToken->colNo); } void checkArrayType(Type* type) { // kiểm tra kiểu mảng if ((type != NULL) && (type->typeClass == TP_ARRAY)) return; else error(ERR_TYPE_INCONSISTENCY, currentToken->lineNo, currentToken->colNo); } void checkTypeEquality(Type* type1, Type* type2) { // kiểm tra 2 biến cùng kiểu hay không if (compareType(type1, type2) == 0) error(ERR_TYPE_INCONSISTENCY, currentToken->lineNo, currentToken->colNo); } Sinh mã trung gian