1
NGÔN NGỮ và
PHƯƠNG PHÁP DỊCH
Phạm Đăng Hải

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
2

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
3
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,

–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
C C
C
PC
PL0
PC
PC
129/4/2012
Chương 1: Những khái niệmcơ bản

• 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
6
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: >=, <=, /*, */

•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…

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
9
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

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ậy pos 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;
11
319/4/2012
Phân tích từ vựng →Ví dụ
Bộ PTTV trả về
3. Các giai đoạn chính củachương trình dịch

Tên
ident
pos1
Ý nghĩaTừ tốTừ vựng
329/4/2012
Phân tích cú pháp (Syntax Analysis)
3. Các giai đoạn chính củachương trình dịch
•Bộ ptcp phân tích chương trình nguồn
–Dựavàocáctừ tố nhận đượctừ pha pttv
•Kiểmtranhững từ tố có tuân theo quy tắc
cú pháp của ngôn ngữđượcdịch không
– Cú pháp thể hiệncấutrúcvănphạmcủa ngôn
ngữ, đượcmôtả dạng: đệ quy, BNF, sơđồ
•Kếtquả củabộ phân tích cú pháp:
– Cây phân tích cú pháp (nếucó)
• Có cây phân tích → chương trình đúng cú pháp
– Thông báo lỗinếungượclại
339/4/2012
Phântíchcúpháp→Ví dụ 1
3. Các giai đoạn chính củachương trình dịch
•Quytắc đinh nghĩamộtbiểuthức
1. Tênlàmộtbiểuthức
2. Con số là biểuthức
3. NếuE, E
1
, E
2
là biểuthứcthì
E
1

Phântíchcúpháp→ Cây phân tích (parse tree)
3. Các giai đoạn chính củachương trình dịch
<Statement>
<ident>
<Expr>
<Ident>
<Expr>
<Expression>
init
10
<Number>
pos
:=
*
<Expr><Expr>
+
<Ident>
size
pos := init + 10 * size
369/4/2012
Phântíchcúpháp→ Cây cú pháp (syntax tree)
3. Các giai đoạn chính củachương trình dịch
pos := init + 10 * size
init
10
pos
:=
*
+
size

3. Các giai đoạn chính củachương trình dịch
• Mã nguồn đượcchuyển sang chương trình tương
đương trong ngôn ngữ trung gian
– Mã trung gian là mã máy độclập, tương tự vớitậplệnh
trong máy.
• Ưu điểmcủa mã trung gian
–Thuậnlợikhicầnthayđổicáchbiểudiễnchương trình đích
–Cóthể tối ưu hóa mã độclậpvớimáyđích cho dạng biểu
diễn trung gian.
–Giảmthờigianthựcthichương trình đích vì mã trung gian
có thểđượctối ưu
• Ngôn ngữ trung gian
–Mã3 địachỉ (thường được dùng)
– Cây cú pháp, Ký pháp Ba Lan sau (hậutố),
14
409/4/2012
Sinh mã→Sinh mã trung gian→Mã 3 địachỉ
3. Các giai đoạn chính củachương trình dịch
•Mỗicâulệnh có nhiềunhất
– 3 toán hạng
– 2 toán tử, trong đócó1 toántử gán
•Chương trình dịch phảisinhrabiếntạm để
chứagiátrị tính toán sau mỗilệnh
Ví dụ: pos := init+int2Real(10) * size
Sinh ra mã 3 địachỉ
Temp1 := Int2Real(10)
Temp2 := Temp1 * Id 3
Temp3 := Id2 + Temp2
Id1:= Temp3
Id1, Id2, Id 3 là các

ADDF R2, R1
MOVF R1, Id1
Temp1 := 10.0 * Id 3
ID1:= Id2 + Temp1
15
439/4/2012
Xử lý lỗi
3. Các giai đoạn chính củachương trình dịch
Lỗicóthể gặp trong mọiphacủaCTD
• Phân tích từ vựng
–Gặpkýtự lạ. Ví dụ: @, $, trong NNLT C
• Phân tích cú pháp
– Không tuân theo cú pháp: VD while (a <> b)
• Phân tích ngữ nghĩa
– Gán giá trị cho hằng, tính toán vớitênthủ tục
•Sinhmã
–Kíchthước quá lớn
Ví dụ: int Arr[1000][1000]; → Lỗitrànô nhớ
449/4/2012
Xử lý lỗi
3. Các giai đoạn chính củachương trình dịch
•Gặplỗi, chương trình dịch cần thông báo
– Ghi nhậnkiểulỗi
– Ghi nhậnvị trí gây ra lỗi (dòng, cột, )
•Cóthể cầnhồiphụcsaukhigặplỗi
–Mục đích: cho phép tiến hành phân tích tiếptục,
tránh lãng phí
–Cóthể thông báo không chính xác
459/4/2012
Quá trình dịch mộtcâulệnh

• Câu:
–Tậphợpcáctừ
•Từ:
–Kýhiệu nào đó
•Ngữ pháp/cú pháp
– Cấu trúc quy định tạocâucủa trong ngôn ngữ
– Ngôn ngữ lậptrình→ cú pháp
17
499/4/2012
Khái niệmvănphạm và ngôn ngữ
4. Khái niệm ngôn ngữ
1. Bộ chữ
2. Xâu ký tự
3. Vănphạm
4. Suy dẫn
5. Câu
6. Ngôn ngữ
7. Đệ quy
8. Phân loạivănphạm
509/4/2012
Bộ chữ
4. Khái niệm ngôn ngữ
•Tậphữuhạnvàkhácrỗng mà các thành phần
đượcgọi là các ký hiệu
–Thường đượckýhiệu V (Vocabulary)
Ví dụ
–Bảng chữ cái a,b,c…là bộ chữ cái củamột ngôn
ngữ tự nhiên
–Bộ từđiểntiếngAnhlàbộ chữ cái trong ngôn
ngữ tiếng Anh

ada là xâu con củaxâumadam
539/4/2012
Xâu ký tự → Tính toán trên tậpxâu
4. Khái niệm ngôn ngữ
A, B là 2 tập xâu trên mộtbộ chữ
• Hợp: A ∪ B = {α| α ∈A hoặc α ∈B }
• Giao: A ∩ B = {α| α ∈A và α ∈B }
• Tích/Ghép: AB={x=αβ| α ∈A và β ∈B }
• Tích Descarter: AB={<α,β>| α ∈A và β ∈A }
• Lũythừa: A
n
= {ε} nếun = 0
A
n
= AA
n-1
= A
n-1
A nếun > 0
• Bao đóng: A
*
= lim(A
0
∪ A
1
∪ ∪ A
n
), n→∞
• Bao đóng dương : A
+

= {0, 1} {0, 1} = {00, 01, 10, 11}
–…
–A
n
= {Tậpcácsố nhị phân độ dài n}
–A
+
= {0, 1, 00, 01, 10, 11, 000, 001,…}
–A
*
= {ε, 0, 1, 00, 01, 10, 11, 000, 001,…}
19
559/4/2012
Vănphạm (Grammar)
4. Khái niệm ngôn ngữ
• V
T
: Tập các ký hiệukết thúc củamộtbảng chữ
–Cácphầntử củaV
T
thường đượckýhiệu: a, b, c,
• V
N
: Tập các k/hiệukhôngkết thúc củamộtbảng chữ
–Cácphầntử củaV
N
thường đượckýhiệu: A, B, C,
–V
T
∩V

T
, V
N
, P, S)
Trong đó
–V
T
={a, b, c}
–V
N
={S, A}
–P ={S →aSA, S→b, A →bA, A→c}
Ghi chú
–Chỉ cầnnhắctớitậpsảnxuất khi giớithiệu
vănphạm
579/4/2012
Suy dẫn (Derivation)
4. Khái niệm ngôn ngữ
Cho vănphạmG = (V
T
, V
N
, P, S)
•Gọi γ viếtraδ hay δ đượcsuydẫntrựctiếp
ra từ γ, và đượckýhiệu γ ⇒ δ nếutồntại
các xâu α, β, v, w thỏa mãn các điềukiện
– γ = αvβ
– δ = αwβ
–(v, w) ∈P {có thể viếtv→w ∈ P}
– α, β ∈ V

, α
1
, α
2
,…, α
n
thỏamãnđiềukiện
γ = α
0
⇒ α
1
⇒ α
2
⇒ …. ⇒ α
n
= δ
•Nếun ≥ 1, áp dụng ít nhất1 bướcsuydẫn,
ký hiệu: γ ⇒
+
δ
•Nếun ≥ 0, có thể không áp dụng bước nào,
ký hiệu: γ ⇒
*
δ
599/4/2012
Suy dẫn → Ví dụ
4. Khái niệm ngôn ngữ
Xét vănphạmG
1
• abA ⇒ abbA {α=ab, β=ε, v=A,w=bA, A

, V
N
, P, S)
•Mộtxâuδ đượcsuyratừ ký hiệukhởi đầu
S, đượcgọilàdạng câu hay dạng cú pháp
– δ là mộtdạng câu nếuS ⇒
*
δ
•Câulàmộtdạng cú pháp chỉ bao gồm toàn
ký hiệukết thúc
– δ là mộtcâunếuS ⇒
*
δ và δ∈ V
T
*
21
619/4/2012
Câu → Ví dụ
4. Khái niệm ngôn ngữ
Ví dụ vănphạmG
1
S⇒aSA ⇒abA ⇒abc
S⇒aSA ⇒abA ⇒abbA⇒abbc
S⇒aSA ⇒abA ⇒abbA ⇒abbbA⇒abbbc
Dạng câu: aSA, abA, abc, abbA, abbc,…
Câu: abc, abbc, abbbc, abbbbc,…
aabbcc có phảilàmột câu?
629/4/2012
Ngôn ngữ
4. Khái niệm ngôn ngữ

2
…
A→α
n
Đượcviếtgọnlại thành A→α
1
| α
2
| …| α
n
Ví dụ:
G
1
=({a,b,c},{S,A},{S →aSA|b, A →bA|c},S)
G
2
= ({a,b}, {S,A}, {S →aA, A →a|b}, S)
22
649/4/2012
Ngôn ngữ→Ví dụ
4. Khái niệm ngôn ngữ
Cho vănphạmG = (V
T
, V
N
, P, S)
–V
T
= {Mơ, Mận, thì, uống, nhanh, đẹp}
–V

⇒
Aβ: Đệ quy trái trựctiếp(Sảnxuất: A
→
Aβ)
•Nếu β =ε, (A
⇒
+
αA) thì gọilàđệ quy phải
–Nếu A
⇒
αA : Đệ quy phải trựctiếp(Sảnxuất: A
→
αA)
•Nếu α,β ≠ ε, (A
⇒
+
αAβ) thì gọilàđệ quy trong
–Nếu A
⇒
αAβ: Đệ quy trong trựctiếp(Sảnxuất:A
→
αAβ)
Ví dụ, định nghĩaTên
<Tên>→<Chữ cái>|<Tên><Chữ cái>|<Tên><Chữ số>
669/4/2012
Vănphạmtương đương
4. Khái niệm ngôn ngữ
Hai vănphạmlàtương đương, nếu chúng
cùng sinh ra một ngôn ngữ
G

1
) = L(G
2
) ⇒ G
1
⇔G
2
23
679/4/2012
Phân loạivănphạm
4. Khái niệm ngôn ngữ
Phân thành 4 loại [Chomsky,1957]
1. Vănphạmngữ cấu(pharse structure grammar)
1. Ràng buộc: Không có ràng buộc ngoài đ/nghĩa
2. VănPhạmcảmngữ cảnh (context sensitive)
• Ràng buộc: Nếu α→β thì l(α) ≤l(β); S →εđượcchấp
nhận khi S không là vế phảicủaSX bấtkỳ
3. Vănphạmphi ngữ cảnh (context free grammar)
• Ràng buộc: Vế trái củacác sảnxuấtlàmộtkýhiệu
không kếtthúc
4. Vănphạm chính quy (regular grammar)
Ràng buộc: SX có dạng A →a|aB hoặc A →a|Ba
689/4/2012
Phân loạivănphạm
4. Khái niệm ngôn ngữ
1
2
3
4
Đượcsử dụng

–Mỗimột nút có nhãn là ký hiệu trong tập V
T
∪V
N
∪ {ε}
–NhãncủanútgốclàS (Start Symbol)
– Các nút lá có nhãn là mộtkýhiệukết thúc hoặc
ε
–Nếu A là nút trong củaD vàX
1
,X
2
, , X
n
là các hậuduệ trực
tiếpcủa A theo tự trái qua phảithì
A → X
1
X
2
X
n
là mộtsảnxuấtcủaP
–Nếu n=0 (X= ε) thì X là hậuduệđơnvàduynhấtcủaA và
A → ε là mộtsảnxuất trong P,
–Biên(kếtquả) củacâysuydẫnlàmộttừ thu đượcbằng
cách nốicácnútlálạitheothứ tự từ trái qua phải
• Rõ ràng, nếu α là biên củaD thìS ⇒
*
α

Thay thế các biến trái nhất:
E⇒E+E⇒a+E⇒a+E*E⇒a+a*E⇒a+a*a
Thay thế các biến phảinhất:
E⇒E+E ⇒E+E*E ⇒E+E*a ⇒E+a*a ⇒a+a*a
K
h
á
c
n
h
a
u
?
5. Vănphạm phi ngữ cảnh
25
739/4/2012
Suy dẫntrái
Cho vănphạmG = (V
T
, V
N
, P, S)
•Gọi δ đượcsuydẫn trựctiếp ra từ bên trái của γ, và
đượckýkiệu γ ⇒
L
δ nếutồntại các xâu x, α, β thỏa
mãn các điềukiện
– γ = xAα ⇒ xβα = δ
– A→ β ∈P, và
– α, β ∈V

= δ
–Nếun ≥ 1, dùng ít nhấtmộtsuydẫn, ký hiệu: γ ⇒
L
+
δ
–Nếun ≥ 0, có thể không suy dẫn nào, ký hiệu: γ ⇒
L
*
δ
Luôn thay ký hiệukhôngkết
thúc bên trái nhất củaxâu
5. Vănphạm phi ngữ cảnh
749/4/2012
Suy dẫnphải
Cho vănphạmG = (V
T
, V
N
, P, S)
•Gọi δ đượcsuydẫn trựctiếp ra từ bên phải của γ,
và đượckýkiệu γ ⇒
R
δ nếutồntại các xâu y, α, β
thỏa mãn các điềukiện
– γ = αAy ⇒ αβy = δ
– A→ β ∈P, và
– α, β ∈V
*
, y∈V
T

+
δ
–Nếun ≥ 0, có thể không suy dẫn nào, ký hiệu: γ ⇒
R
*
δ
Luôn thay ký hiệukhôngkết
thúc bên phảinhất củaxâu
5. Vănphạm phi ngữ cảnh
759/4/2012
Vănphạm đơn nghĩa
Vănphạm PNC G=(V
T
,V
N
,P,S) đơn nghĩanếu
–Vớimỗicâu ω∈L(G) chỉ có đúng mộtsuydẫn
trái (hoặcmộtsuydẫnphải) ⇔ Chỉ có đúng một
cây suy dẫn
Ngượclại, nếucónhiềuhơnmộtsuydẫntrái,
hoặcmộtsuydẫnphảihoặc có nhiều cây suy
dẫn ⇒ Vănphạmnhậpnhằng
Nếu ω∈L(G) có nhiềuhơn 2 cây suy dẫn
⇒ Có thể phân tích cú pháp theo nhiềuhơn 2 cách
⇒ Nhiềuhơn2 cáchhiểu
5. Vănphạm phi ngữ cảnh