1
NGÔN NGỮvà
PHƯƠNG PHÁP DỊCH
PhạmĐăng Hải
haipd@soict.hut.edu.vn
29/4/2012
Chương 1: Những khái niệmcơbản
1. Ngôn ngữlậptrìnhcấp cao và trình dịch
2. Đặctrưng của ngôn ngữlậptrìnhcấpcao
3. Các giai đoạn chính củachương trình dịch
4. Khái niệm ngôn ngữ
5. Vănphạm phi ngữcảnh
6. GiớithiệungônngữPL/0 mởrộng
39/4/2012
Sựcầnthiếtcủa ngôn ngữlậptrìnhbậccao
•Nhiềuloại máy tính
–Mỗiloạinhiềukiểu
•Mỗikiểu có ngôn ngữmáy riêng
– Ngôn ngữmáy là dãy nhịphân
1. Ngôn ngữlậptrìnhcấpcaovàtrìnhdịch
• Dùng ngôn ngữmáy
– Không phảidịch
–Phứctạp
– Không khảchuyển
•Cầnngônngữ
–Độclậpvớimáy
–Gầnvớingữtựnhiên
•Ví dụ: C, Pascal, basic..
Ngôn ngữ
bậccao
49/4/2012
Ngôn ngữlậptrìnhcấp cao (NNLTCC)
Chương trình viếtbằng NNLTCC
•Độclậpvới máy tính
•Gầnvới ngôn ngữtựnhiên
•Chương trình dễđọc, viếtvàbảotrì
•Muốnthựchiệnphảichuyển sang ngôn ngữ
–Máyhiểuđược(ngôn ngữmáy)
– Ngôn ngữtrung gian mà máy hiểuđược
ĐượcchuyểnđổibởiChương trình dịch
•Chương trình thựchiệnchậmhơn
1. Ngôn ngữlậptrìnhcấpcaovàtrìnhdịch
59/4/2012
Chương trình biên dịch (compiler)
•Chương trình dịch làm nhiệmvụdịch
chương trình nguồn(thường đượcviếtbằng
ngôn ngữlậptrìnhbậccao) sang các
chương trình đốitượng (chương trình đích)
1. Ngôn ngữlậptrìnhcấpcaovàtrìnhdịch
Compiler
Chương trình
nguồnChương trình
đích
Thông báo lỗi
•Chương trình đíchcóthểkhông thựchiện
được ngay mà cầnliênkết (link) đếnthưviện
để đượcchương trình thựchiện69/4/2012
Các bướcxửlý chương trình
1. Ngôn ngữlậptrìnhcấpcaovàtrìnhdịch
Chương trình
nguồn
loader
Mã máy
tuyệtđối
Mã đối
tượng
compiler
Mã thực
hiện
linker
Thưviện
Phase
dịch
2
79/4/2012
Thông dịch (interpreter)
• Làm nhiệmvụ“giảithích”
chương trình nguồn
– Phân tích câu lệnh tiếp
–Thựchiệncâulệnh
1. Ngôn ngữlậptrìnhcấpcaovàtrìnhdịch
Chương trình
nguồn
interpreter
Kếtquả
Dữliệu
•Chương trình thông dịch
có kích thướcnhỏhơn,
nhưng chạychậmhơn
89/4/2012
Dịch và thựchiệnchương trình nguồn
1. Ngôn ngữlậptrìnhcấpcaovàtrìnhdịch
Chương trình nguồn
Chương trình bằng
ngôn ngữtrung gian
compiler
interpreter
Kếtquả
Phase 2: Thựchiện
mã trung gian
Phase 1: Chuyểntừ
chương trình nguồn
sang NN trung gian
99/4/2012
Compiler >< interpreter
1. Ngôn ngữlậptrìnhcấpcaovàtrìnhdịch
•Compiler : Dịch trựctiếpramãmáy
•Interpreter : Trựctiếpthựchiệntừng lệnh mã nguồn
•Biếnthểcủa Interpreter : thông dịch mã trung gian
109/4/2012
Xây dựng chương trình dịch
•Viếttrựctiếptừngôn ngữmáy
–Khókhăn
•Sửdụng ngôn ngữbậccao
–Dễdàng thựchiện, hiệuquả
–Tăng tính khảchuyển,..
Chương trình bậccaođầutiên?
–Chiếnlượcchương trình mồi(bootstraps) trong
đóchương trình dịch đượcđặctrưng bởi
•Ngônngữnguồnđượcdịch S
•Ngônngữđích T
•Ngônngữcài đặtI
1. Ngôn ngữlậptrìnhcấpcaovàtrìnhdịch
ST
I
119/4/2012
Xây dựng chương trình dịch
Viếtchương trình dịch L cho máy M
• Dùng hợpngữcủaM viếtL’làtập con củaL
• Dùng L’ để viếtL
Nhưvậy, L đượcthựchiện qua L’ để ra M
1. Ngôn ngữlậptrìnhcấpcaovàtrìnhdịch
LM
L’ L’ M
M
LM
M
PL0 PC
CC
C
PC
PL0 PC
PC
129/4/2012
Chương 1: Những khái niệmcơbản
1. Ngôn ngữlậptrìnhcấp cao và trình dịch
2. Đặctrưng của ngôn ngữlậptrìnhcấpcao
3. Các giai đoạn chính củachương trình dịch
4. Khái niệm ngôn ngữ
5. Vănphạm phi ngữcảnh
6. GiớithiệungônngữPL/0 mởrộng
3
139/4/2012
Các thếhệngôn ngữlậptrình
•Được chia thành 5 thếhệ.
•Việc phân chia cấp cao hay thấpphụthuộc
mứcđộ trừutượng của ngôn ngữ
–Cấpthấp: gầnvớimáy
–Cấpcao: gầnvới ngôn ngữtựnhiên
2. Đặctrưng của ngôn ngữlậptrìnhcấpcao
149/4/2012
Các thếhệngôn ngữlậptrình
• Các ngôn ngữlậptrìnhbậcthấp
–Thếhệthứnhất : ngôn ngữmáy
–Thếhệthứhai : Assembly
•Thếhệthứba
–Dễhiểuhơn
•Câulệnh gần ngôn ngữtựnhiên
– Cho phép thựchiện các khai báo, Ví dụbiến
–Phầnlớn các NNLT cho phép lậptrìnhcấutrúc
–Vídụ: Fortran, Cobol, C, C++, Basic .
2. Đặctrưng của ngôn ngữlậptrìnhcấpcao
←Ngôn ngữbậccao
159/4/2012
Các thếhệngôn ngữlậptrình
• Ngôn ngữlậptrìnhthếhệthứtư
–Thường đượcsửdụng trong mộtlĩnh vựccụthể
–Dễlậptrình,xâydựng phầnmềm
–Cóthểkèm công cụtạo form, báo cáo
–Vídụ:SQL, Visual Basic, Oracle . . .
• Ngôn ngữlậptrìnhthếhệthứnăm
–Giảiquyết bài toán dựatrêncácràngbuộcđưaracho
chương trình (không phảigiảithuậtcủangườilậptrình)
–Việcgiải quyết bài toán do máy tính thựchiện
–Phầnlớn các ngôn ngữdùng để lậptrìnhlogic
•Giảiquyết các bài toán trong lĩnh vựctrítuệnhân tạo
2. Đặctrưng của ngôn ngữlậptrìnhcấpcao
169/4/2012
Các thành phầncủaNNLTCC
1. Từvựng và cú pháp
2. Kiểudữliệu
3. Các đạilượng
4. Các toán tửvà biểuthức
5. Các câu lệnh
6. Chương trình con
2. Đặctrưng của ngôn ngữlậptrìnhcấpcao
179/4/2012
Từvựng và cú pháp
Từvựng
–Chữcái: A..Z, a..z
–Chứsô: 0..9
–Dấu: dấuchứcnăng, dấu toán tử
•Dấuđơn: +, -, ; {, }
•Dấu kép: >=, <=, /*, */
–Từkhóa : từdành riêng cho ngôn ngữ
•Được dùng để khai báo, ra lệnh cho chương trình
Cú pháp
– Là các quy tắcđể
•Viếtracácđạilượng
•Viếtcáccâulệnh
2. Đặctrưng của ngôn ngữlậptrìnhcấpcao
189/4/2012
Kiểudữliệu
Các kiểucơbản
–Kiểusốnguyên int Interger
–Kiểusốthựcfloat Real
–Kiểukýtựchar Char
–Kiểu logic 0, 1 Boolean
Kiểudữliệucócấutrúc
–Kiểumảng [ ] Array
–Kiểuchuỗi*String
–Kiểubảnghi struct Record
–Kiểu con trỏ, &^
–Kiểu file FILE File
2. Đặctrưng của ngôn ngữlậptrìnhcấpcao
4
199/4/2012
Các đạilượng
Hằng
–Sốnguyên
•Cáchbiểudiễn (decimal,octal, hexadecimal,..)
–Sốthực
•Dấuphẩytĩnh
•Dấuphẩyđộng
–Hằng chuỗi
•C: “Hello”
• Pascal: ‘Hello’
Tên
–Nguyêntắcđặttên?
–Độ dài?
2. Đặctrưng của ngôn ngữlậptrìnhcấpcao
209/4/2012
Toán tửvà biểuthức
Toán tử
–Sốhọc: cộng (+), chia, chia dư(%, MOD),..
– Logic
•Quanhệ: bằng (=,==) khác (!=, <>), lớnhơn, (>),..
• Logic: Và (AND, &&), hoặc( OR, ||),..
– Xâu: ghép xâu ←Pascal
Biểuthức←Kếthợp các toán hạng bởitoántử
–Sốhọc: Trảvềmộtcon số
– Logic: Trảvềmộtgiátrịluậnlý
– Xâu: Trảvềmộtchuỗikýhiệu
2. Đặctrưng của ngôn ngữlậptrìnhcấpcao
219/4/2012
Các câu lệnh
Câu lệnh tuầntự
–Câulệnh gán: :=, =
–Câulệnh vào/ra, gọi hàm
–Câulệnh ghép, gộp: begin..end, { }
Câu lệnh rẽnhánh
–1 vào1 ra:
if…then, if()
– 1 vào 2 ra: if …then…else, if()…else…
– 1 vào, nhiềura: case …..of, switch() {}
Câu lệnh lặp
–Sốlầnlặpxácđịnh: For ..to/downto..do, for( ; ; )
–Kiểmtrađiềukiệntrước: While.. Do, while ()
–Kiểmtrađiềukiện sau: Repeat..Until, do..while()
2. Đặctrưng của ngôn ngữlậptrìnhcấpcao
229/4/2012
Chương trình con
Các dạng chương trình con
–Thủtục→Không trảvềgiá trị(void)
–Hàm→Trảvềmộtgiátrị
Vấnđề truyền tham số
– Truyềntheotrị: Không thay đổigiátrị
– Truyềntheobiến(địachỉ): thay đổigiátrị
Vấnđề Địaphương /toàn cục
–Địaphương: chỉtồntại trong chương trình con
– Roàn cục: Tồntại trong toàn bộchương trình
2. Đặctrưng của ngôn ngữlậptrìnhcấpcao
239/4/2012
Nhậnxét
Ngôn ngữlậptrìnhbậccaocó
nguyên tắcgiống nhau, cách thể
hiệncóthểkhác nhau
2. Đặctrưng của ngôn ngữlậptrìnhcấpcao
249/4/2012
Chương 1: Những khái niệmcơbản
1. Ngôn ngữlậptrìnhcấp cao và trình dịch
2. Đặctrưng của ngôn ngữlậptrìnhcấpcao
3. Các giai đoạn chính củachương trình dịch
4. Khái niệm ngôn ngữ
5. Vănphạm phi ngữcảnh
6. GiớithiệungônngữPL/0 mởrộng
5
259/4/2012
Các phase củachương trình dịch
Chương trình dịch gồm 3 phase chính
1. Phân tích từvựng
2. Phân tích cú pháp
– Phân tích ngữnghĩa
3. Sinh mã
3. Các giai đoạn chính củachương trình dịch
269/4/2012
Cấutrúcchương trình dịch
Phân tích từvựng
Chương trình nguồn
Phântíchcúpháp
Phân tích ngữnghĩa
Sinh mã trung gian
Tốiưumã
Sinh mã máy
Chương trình đích
Bảng
ký
hiệu
Xửlý
lỗi
279/4/2012
Bảng ký hiệu
3. Các giai đoạn chính củachương trình dịch
•Làcấutrúcdữliệu dùng chứatênvàthuộc
tính cầnthiếtcủa chúng
–Thuộctínhcungcấp thông tin
•Vịtrí, kiểu, phạmvịhoạtđộng…
–Nếulàtênchương trình con: sốtham số, kiểutrảvề
–Tênđượcxácđịnh bởibộphân tích từvựng
•Khichỉra đượcmột tên, tùy thuộcvàovịtrí
của tên trong chương trình
–Đưatênvàthuộc tính vào bảng ký hiệu
–Lấy thông tin của tên trong bảng ký hiệu
289/4/2012
Bảng ký hiệu→Ví dụ
pos = init + 10 * size;
3. Các giai đoạn chính củachương trình dịch
float pos, init, size; //var pos, init, size: real
Bảng ký hiệu
….
….
LoạiKiểuTên
….
varrealpos
Id1
varrealinitId2
varrealsizeId3
….
LoạiKiểuTên
Tên
Kiểu
299/4/2012
Phân tích từvựng (Lexical Analysis - Scanner)
3. Các giai đoạn chính củachương trình dịch
Là pha đầutiêncủachương trình dịch
•Duyệttừng ký tựcủachương trình nguồn
–Loạibỏcáckýtựthừa
•Dấu tab, khoảng trắng, chú thích..
•Xâydựng các từvựng từcáckýtựđọcđược
•Nhậndạng các từtốtừcác từvựng
–Từtố(token)là đơnvịcú pháp đượcxửlý
trong quá trình dịch nhưmộtthựcthểkhông
thểchia nhỏhơnnữa
• Chuyểncáctừtốcho pha tiếp
309/4/2012
Phân tích từvựng →Ví dụ
3. Các giai đoạn chính củachương trình dịch
BộPTTV thựchiện
•Đọctừng ký tự: bắtđầutừchữcái p
–Nhậndạng từvựng thuộcdạng tên, hoặctừkhóa (vì bắt
đầubởi1 chữcái)
–Đọctiếp(
o, s) tớikhigặpkýtựkhác chữcái, chữsố,
•Gặpdấutrắng →xây dựng xong từvựng pos
–Do pos không trùng vớitừkhóa. Vậypos là tên (ident)
–Trảlạichobộphân tích cú pháp từtốident
•Đọctiếpđượcdấu:rồidấu=và sau đódấucách
–Nhậndạng đượctừvựng := và trảvềtừtốgán (assign)
pos := init + 10 * size;