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.
14 trang |
Chia sẻ: haohao89 | Lượt xem: 2928 | Lượt tải: 1
Bạn đang xem nội dung tài liệu Giới thiệu về trình biên dịch, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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:
αAβ => αγβ
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) = a nếu a là kí hiệu kết thúc
FIRST(ε) = ε
FIRST(A) = 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