Tổng hợp bài giảng môn Chương trình dịch| Trường Đại học Bách Khoa Hà Nội

21/1/2010 Môn học sẽ nghiên cứu XÂY DỰNG
Cách thức làm việc của máy tính (tập
lệnh, thanh ghi, mode địa chỉ, các cấu trúc CHƯƠ CH NG TRÌNH DỊ D CH dữ liệu ệ được sử dụn ụ g khi g thực hi ự ện. . . ệ ) )
Cách thức làm việc của bộ xử lý ngôn ngữ và chương trình dịch
Nguyễn Thị Thu Hương - Khoa CNTT – ĐHBKHN
Tel (04) 38696121 - Mobi : 0903253796
Sinh mã máy cho những cấu trúc ngôn
Email :huongnt@it-hut.edu.vn,huongnt-fit@mail.hut.edu.vn ngữ cụ thể
Thế nào là một thiết kế ngôn ngữ tốt?
Tại sao cần nghiên cứu CT dịch? Những vấn đề chính
Rèn kỹ năng phát triển ứng dụng quy mô Bộ xử lý ngôn ngữ lớn
Cấu trúc của một trình biên dịch (1 pha) Văn phạm sản sinh Làm vi ệc ệ v ớ v i các các c ấu ấ trúc trúc d ữ d li ệu ệ phứ ph c ứ t ạp ạ BNF và sơ ồ đ cú pháp
Tìm hiểu sự tương tác giữa các giải thuật
Phân tích từ vựng và bảng ký hiệu
Bước chuẩn bị cho những
Phân tích cú pháp trên xuống có quay lui
dự án lớn trong tương lai.
Phân tích cú pháp tiền định Văn phạm LL(k) 1 21/1/2010 Những vấn đề chính Tài liệu tham khảo
Aho.A.V, Sethi.R., Ullman.J.D.
Compiler : Principles, Techniques and Tools.
Phân tích đệ quy trên dưới Addison Wesley.1986
Phân tích cú pháp cho ngôn ngữ KPL Bal.H. E.
Modern Compiler Design. Phân tích n gữ ng nghĩ ngh a ĩ John W ile iley & Sons I n Inc ( 2000) ( Stack calculator William Allan Wulf.
The Design of an Optimizing Compiler Sinh mã trung gian Elsevier Science Ltd (1980) Charles N. Fischer. Sinh mã đích Crafting a Compiler Tối ưu mã
Benjamin-Cummings Pub Co (1987) Tài liệu tham khảo Niklaus Wirth Compiler Construction. Addison Westley. 1996 Bài 1. Andrew.W.Appel
Modern Compiler Implementation in Java Bộ B x ử lý ngôn ng ữ Princet U on ni i vers tity.1998 Nguyễn Văn Ba
Giáo trình kỹ thuật biên dịch
Đại học Bách Khoa Hà Nội.1994 Vũ Lục Phân tích cú pháp
Đại học Bách Khoa Hà Nội.1990
Bài giảng về ngôn ngữ và phương pháp dịch www.sourceforge.net 2 21/1/2010
Ngôn ngữ lập trình cấp cao
Ngôn ngữ lập trình thế hệ thứ nhất và thứ hai
Các ngôn ngữ lập trình được chia thành 5 thế hệ.
Thế hệ thứ nhất : ngôn ngữ máy Việc ệ phân chia cấp ấ cao ca hay thấ th p ấ phụ ph Thế Th h ệ h th ứ th hai : Assembly Assembly
thuộc mức độ trừu tượng của ngôn ngữ
Các ngôn ngữ thuộc thế hệ thứ nhất và
Cấp thấp : gần với máy
thứ hai là ngôn ngữ lập trình cấp thấp
Cấp cao : gần với ngôn ngữ tự nhiên
Ngôn ngữ lập trình thế hệ thứ ba
Ngôn ngữ lập trình thế hệ thứ tư Dễ hiểu hơn
Thường được sử dụng trong một lĩnh vực
cụ thể (chẳng hạn thương mại)
Cho phép thực hiện các khai báo, chẳng hạ h n ạ b i biến ế
Dễ lập trình,xây dựng ph p ần mềm
Có thể kèm công cụ tạo form, báo cáo
Phần lớn các ngôn ngữ cho phép lập trình cấu trúc
Ví dụ :SQL, Visual Basic, Oracle (SQL
plus, Oracle Form, Oracle Report). . . .
Ví dụ: Fortran, Cobol, C, C++, Basic . . . . 3 21/1/2010
Ngôn ngữ lập trình thế hệ thứ năm
Đặc trưng của ngôn ngữ lập trình cấp cao
Giải quyết bài toán dựa trên các ràng buộc Độc lập với máy tính
đưa ra cho chương trình chứ không phải
Gần với ngôn ngữ tự nhiên
giải thuật của người lập trình. Chươ Ch ng trình dễ d đọc, đọ viết ế và bả b o ả trì Việc giải qu ế
y t bài toán do máy tính thực hiện
Muốn thực hiện chương trình phải dịch sang ngôn ngữ máy
Phần lớn các ngôn ngữ dùng để lập trình
logic, giải quyết các bài toán trong lĩnh vực
Chương trình thực hiện chậm hơn trí tuệ nhân tạo
Cú pháp và ngữ nghĩa của ngôn ngữ lập trình
Bộ xử lý ngôn ngữ (Language Processor)
Phần mềm dịch từ một ngôn ngữ nào đó
Cú pháp : Chính tả và văn phạm của
sang mã máy (có thể đồng thời thực thi) các cấu ấ trúc ngôn ngữ ng Ví d ụ d Compiler Assembler
Ngữ nghĩa : Ý nghĩa và hiệu quả của Interpreter các cấu trúc ngôn ngữ Compiler - Compiler 4 21/1/2010 Compiler & Interpreter Compiler (trình biên dịch)
Compiler : Dịch trực tiếp ra mã máy
Mục đích : Dịch chương trình từ ngôn ngữ
cấp cao (ngôn ngữ nguồn) sang ngôn ngữ cấp th p ấp p (n ( gôn n g gữ g đích). ) Interpreter T : rực tiế ti p thự hi c ệ hi n từ t ng lệnh ã m ồ ngu n
Bản thân compiler được viết trên một
ngôn ngữ gọi là ngôn ngữ thực hiện
Biến thể của Interpreter : thông dịch mã trung gian Compiler Interpreter 5 21/1/2010
Các công cụ liên quan đến trình biên dịch
Vị trí của trình biên dịch trong bộ xử lý ngôn ngữ
Trình thông dịch (Interpreter) Assembler Linker Loader
Bộ tiền xử lý (Preprocessor) Editor Debugger Profiler 6 21/1/2010
Các giai đoạn của trình biên dịch Bài 2.
Phân tích từ vựng (Lexical Analysis - Các giai đoạn chính Scanner)
Lần lượt xem xét từng ký tự của chương trình của chương trình dịch ồ ngu hâ n, p hó n n m chúng thà h n h n ữ h ng đơn vị
cú pháp gọi là từ tố (token)
Phân tích cú pháp (Syntax Analysis)
Dãy token do bộ phân tích từ vựng đưa ra
được kiểm tra xem có đúng cú pháp không? 1 3
Các thành phần chính của trình biên dịch
Các giai đoạn của trình biên dịch
Phân tích ngữ nghĩa (Semantic Analysis)
phân tích ý nghĩa từng lệnh của ngôn ngữ ngu g ồn.
Sinh mã trung gian (Intermediate Code
Generation)thường là mã 3 địa chỉ. Mã
trung gian không phụ thuộc máy nên dễ tối ưu. 2 4 1 21/1/2010
Các giai đoạn của trình biên dịch Pha 1:Phân tích từ vựng
Sinh mã đích: Sinh ra các lệnh máy để
Bộ từ vựng:Chương trình làm nhiệm vụ thực hiện thao tác. phân tích từ vựng g g Tối ố ư u ư mã: mã: T hự Th c ự h i hiện ệ vớ v i mã mã t rung trung gian
Các công việc của bộ từ vựn
và cả mã đích nhằm làm cho chương trình
Nhóm các ký tự thành từ tố hiệu quả hơn.
Từ tố :đơn vị cú pháp được xử lý trong quá
trình dịch như một thực thể không thể chia nhỏ hơn nữa
Nhóm các từ tố theo loại. 5 7 Một số loại từ tố Quá trình dịch một câu lệnh 6 8 2 21/1/2010 Pha 2: Phân tích cú pháp
Ví dụ: câu lệnh a = b + c
Trình biên dịch kiểm tra xem những từ tố
mà bộ từ vựng nhận biết được có kết hợp thành những câu g lệnh ệ đúng cú g phá p p p không
Do bộ phân tích cú pháp đảm nhận 9 11 Pha 2: Phân tích cú pháp
Văn phạm, ngôn ngữ, BNF,sơ đồ cú pháp
Đầu ra của bộ phân tích cú pháp: Cú pháp
Cây phân tích cú pháp (nếu có)
Cấu trúc văn phạm của một ngôn ngữ Thông báo lỗi ỗ nế n u ế ngượ ng c ượ lại ạ Bộ phân tích c ú cú pháp c ần ầ đưa đư ra ra phân tích
Việc xây dựng được cây phân tích cú
cho mỗi câu của ngôn ngữ (chương trình)
pháp chứng tỏ chương trình đúng về cú
BNF : Dạng chuẩn để mô tả văn phạm của pháp ngôn ngữ
Sơ đồ cú pháp:cách mô tả văn phạm trực
quan dưới dạng đồ thị định hướng 10 12 3 21/1/2010
Văn phạm, ngôn ngữ, BNF,sơ đồ cú pháp
Khái niệm và kỹ thuật phân tích cú pháp
Các luật của BNF cũng như văn phạm
hình thức sử dụng 2 loại ký hiệu ở vế phải
Bằng cách áp dụng liên tục các luật mô tả văn phạm Ký hiệu kết thúc : Nế N u ế b ộ b PTCP chuyể chuy n ể thành thành công t ừ xâu Từ tố củ ô a ng ữ n ng
vào thành ký hiệu đầu thì xâu vào đúng cú
Không xuất hiện ở vế trái pháp Ký hiệu không kết thúc
Ký hiệu trung gian của văn phạm để mô tả
Ngược lại, câu được xem xét không đúng cấu trúc ngôn ngữ cú pháp
Cần xuất hiện ở vế trái của ít nhất một luật Bao trong cặp <> 13 15
Văn phạm, ngôn ngữ, BNF,sơ đồ cú pháp
Khái niệm và kỹ thuật phân tích cú pháp Ký hiệu đầu :
Vấn đề quan trọng nhất khi xây dựng
Ký hiệu không kết thúc ở mức cao nhất
trình biên dịch là xây dựng một văn Xuấ Xu t ấ hi hiện ệ ở gố g c ố cây cây cú pháp phạm
Bao gồm đầy đủ các cấu trúc của một chương trình
Không thể tạo nên một luật nào khác 14 16 4 21/1/2010
Khái niệm và kỹ thuật phân tích cú pháp Pha 4: Sinh mã trung gian
Văn phạm phải không nhập nhằng
Chương trình với mã nguồn được
chuyển sang chương trình tương
đương trong ngôn ngữ trung gian ế
N u văn phạm nhập nhằng, xây dựng
bằng bộ sinh mã trung gian.
được nhiều hơn 1 cây cho mỗi câu được đưa ra phân tích
Mã trung gian là mã máy độc lập
tương tự với tập lệnh trong máy. 17 19
Ưu điểm của mã trung gian
Pha 3: Phân tích ngữ nghĩa
Duyệt cây cú pháp của chương
1.Thuận lợi khi cần thay đổi cách biểu
diễn chương trình đích.
trình để xem mọi cấu trúc ngữ
2.Có thể tối ưu hóa mã độc lập ậ với nghĩa có đ ú k ng hô không
máy đích cho dạng biểu diễn trung gian.
Chương trình đúng cả về cú pháp
và ngữ nghĩa mới sinh mã được
3.Giảm thời gian thực thi chương trình
đích vì mã trung gian có thể được tối ưu 18 20 5 21/1/2010 Ngôn ngữ trung gian
Các vấn đề thiết kế bộ sinh mã đích
Được người thiết kế trình biên dịch Input
quyết định, có thể là: Output Lựa chọn câu lệnh Cây cú pháp
Ký pháp Ba Lan sau (hậu tố) Cấp phát thanh ghi Mã 3 địa chỉ … Máy đích 21 23 Pha 5: Sinh mã đích
Vào: biểu diễn trung gian của chương trình nguồn Ra: chươ t ng rình đ ích Mã Assembly
Mã mô phỏng trên máy đích ảo 22 6 21/1/2010
Làm thế nào để sản sinh ra các xâu ? Bài 3.
Văn phạm phi ngữ cảnh có thể dùng để
sản sinh ra các xâu thuộc ngôn ngữ như Vă V n p h phạm sản s inh sinh sau: X = Ký hiệu đầu Wh W ile h
còn ký hiệu không kết thúc Y trong X do
Áp dụng một trong các sản xuất của,văn
phạm chẳng hạn Y -> w 1 2 Ví dụ Suy dẫn (Derivations) S -> +A | -A |A A -> B.B | B
Mỗi lần thực hiện việc thay thế là một bướ b c s uy suy dẫ d n ẫ . B -> BC | C
Nếu mỗi dạng câu có nhiều ký hiệu không C -> 0 | 1 | 2 |. . . .|9
kết thúc để thay thế có thể sử dụng bất cứ sản xuất nào.
Khi X chỉ chứa ký hiệu kết thúc, nó là xâu được sản sinh bởi văn phạm. 3 4 1 21/1/2010
Suy dẫn trái và suy dẫn phải
Cây suy dẫn(Cây phân tích cú pháp)
Cây suy dẫn có những đặc điểm sau
1) Mỗi nút của cây có nhãn là ký
Nếu giải thuật phân tích cú pháp chọn ký
hiệu kết thúc, ký hiệu không kết
hiệu không kết thúc cực trái hay cực phải thúc hoặc ε (xâu rỗng)
2) Nhãn của nút gốc là S (ký hiệu để thay th y ế, kết qu q ả của nó lad suy d y ẫn đầu) trái hoặc suy dẫn phải
3) Nút trong có nhãn là ký hiệu không kết thúc
4) Nút A có các nút con từ trái qua
phải là X1, X2, ... , Xk thì có một
sản xuất dạng A -> X1 X2 ... Xk
5)Nút lá có thể có nhãn ε chỉ khi tồn
tại sản xuất A -> ε và nút cha của
nút lá chỉ có một nút con duy nhất 5 6 Văn phạm nhập nhằng Khử nhập nhằng Văn phạm E -> E + T E -> E + E E -> T E -> E * E E -> ( E ) T > - T * F E -> ident T -> F
Cho phép đưa ra hai suy dẫn khác nhau cho F -> ( E )
xâu ident + ident * ident (chẳng hạn x + y * z) F -> ident Văn phạm là nhập nhằng
(Bằng cách thêm các ký hiệu không kết thúc và các sản xuất để
đảm bảo thứ tự ưu tiên) 7 8 2 21/1/2010 Đệ quy Khử đệ quy trái
Một sản xuất là đệ qui nếu X =>* ω1X ω2 E -> E + T | T
Có thể dùng để biểu diễn các quá trình lặp hay cấu trúc T -> T * F | F lồng nhau F -> ( E ) | ident
Đệ quy trực tiếp X =>ω X ω 1 2 Khử đệ ệ qu q y trái y bằng cách g thêm ký hiệu khôn ệ g g
Đệ quy trái X => b | Xa. X => X a => X a a => X a a a =>b a a a a a ...
kết thúc và sản xuất mới
Đệ quy phải X => b | a X. X => a X => a a X => a a a X =>... a a a a a b E -> T E'
Đệ quy giữa X => b | "(" X")". X =>(X) =>((X)) =>(((X))) =>(((... (b)...))) E' -> + T E' | ε
Đệ quy gián tiếp X =>* ω X ω 1 2 T -> F T' T' -> * F T' | ε F -> ( E ) | ident 9 10 3 21/1/2010
Công thức siêu ngữ Backus và các biến thể Bài 4
Siêu ngữ (metalanguage ):Ngôn ngữ sử
dụng các lệnh để mô tả ngôn ngữ khác BNF v BNF à và s ơ đồ cú p háp pháp
BNF (Backus Naur Form) là dạ d ng ạ siêu si cú
pháp để mô tả các ngôn ngữ lập trình
BNF được sử dụng rộng rãi để mô tả văn
phạm của các ngôn ngữ lập trình, tập lệnh
và các giao thức truyền thông. 1 2
Các biến thể của công thức siêu
Công thức siêu ngữ Backus và ngữ Backus các biến thể
Ký pháp BNF là một tập các luật ,vế trái
Mỗi ký hiệu không kết thúc được định
của mỗi luật là một cấu trúc cú pháp.
nghĩa bằng một hay nhiều luật.
Tên của cấu trúc cú pháp được gọi là ký Các luật có dạng hiệu ệ không kết ế thúc. N::=s
Các ký hiệu không kết thúc thường được
(N là ký hiệu không kết thúc, s là một xâu bao trong cặp <>.
gồm 0 hay nhiều ký hiệu kết thúc và không
Các ký hiệu kết thúc thường được phân
kết thúc. Các luật có chung vế trái được
cách bằng cặp nháy đơn hoặc nháy kép phân cách bằng | ) 3 4 1 21/1/2010 Ví dụ về BNF EBNF ::=’-’|
EBNF (Extended BNF ) được phát triển từ ký
::=|pháp BNF. EBNF có ký pháp tương tự BNF
nhưng được đơn giản hoá bằng cách sử dụng chữ số>’.’ mộ m t ộ số ký hiệu ệ đặc đặ biệt ệ :
::=|[] phần này là tuỳ chọn(có hoặc không) chữ số>
{} phần này có thể lặp lại một số lần tuỳ ý hoặc
::=’0’|’1’|’2’|’3’|’4’|’5’|’6’|’7’|’8’|’9’
không xuất hiện lần nào (Nếu lặp lại m hay n lần
, dùng n hay m là chỉ số trên hoặc dưới)
Không cần dùng ‘’ cho ký hiệu kết thúc 5 6 So sánh BNF và EBNF Sơ đồ cú pháp Ví dụ
Là công cụ để mô tả cú pháp của ngôn Trong EBNF
ngữ lập trình dưới dạng đồ thị ệ if>:: if> = IF ể thứ th c> ứ THEN ệ [ELSE ]
Mỗi sơ đồ cú pháp là một đồ thị định
hướng với lối vào và lối ra xác định. Trong BNF
Mỗi sơ đồ cú pháp có một tên duy nhất ::= ‘IF’ ‘THEN’ | ‘IF’ THEN ‘ELSE’ 7 8 2 21/1/2010
Ví dụ một sơ đồ cú pháp
Sơ đồ cú pháp của KPL (Tổng thể CT) 9 10 Sơ đồ cú pháp của KPL
Sơ đồ cú pháp của KPL (Khối)
(tham số, hằng không dấu) 11 12 3 21/1/2010
Sơ đồ cú pháp của KPL (Khai Sơ đồ cú pháp của KPL báo) (lệnh) 13 14
Sơ đồ cú pháp của KPL (biểu Sơ đồ cú pháp của KPL thức) (thừa số,điều kiện) 15 16 4 21/1/2010
Sơ đồ cú pháp của KPL(tên, số) 17 5