Xem mẫu
- Chương 1: Những khái niệm cơ bản
1. Ngôn ngữ lập trình cấp cao và trình dịch
NGÔN NGỮ và 2. Đặc trưng của ngôn ngữ lập trình cấp cao
PHƯƠNG PHÁP DỊCH 3. Các giai đoạn chính của chương trình dịch
4. Khái niệm ngôn ngữ
Phạm Đăng Hải
5. Văn phạm phi ngữ cảnh
haipd@soict.hut.edu.vn
6. Giới thiệu ngôn ngữ PL/0 mở rộng
9/4/2012 2
1. Ngôn ngữ lập trình cấp cao và trình dịch 1. Ngôn ngữ lập trình cấp cao và trình dịch
Sự cần thiết của ngôn ngữ lập trình bậc cao Ngôn ngữ lập trình cấp cao (NNLTCC)
• Nhiều loại máy tính Chương trình viết bằng NNLTCC
– Mỗi loại nhiều kiểu
• Độc lập với máy tính
• Mỗi kiểu có ngôn ngữ máy riêng
– Ngôn ngữ máy là dãy nhị phân • Gần với ngôn ngữ tự nhiên
• Dùng ngôn ngữ máy • Chương trình dễ đọc, viết và bảo trì
– Không phải dịch
– Phức tạp • Muốn thực hiện phải chuyển sang ngôn ngữ
– Không khả chuyển – Máy hiểu được (ngôn ngữ máy)
• Cần ngôn ngữ – Ngôn ngữ trung gian mà máy hiểu được
Ngôn ngữ
bậc cao
– Độc lập với máy
Được chuyển đổi bởi Chương trình dịch
– Gần với ngữ tự nhiên
• Chương trình thực hiện chậm hơn
9/4/2012
• Ví dụ: C, Pascal, basic.. 3 9/4/2012 4
1. Ngôn ngữ lập trình cấp cao và trình dịch 1. Ngôn ngữ lập trình cấp cao và trình dịch
Chương trình biên dịch (compiler) Các bước xử lý chương trình
• Chương trình dịch làm nhiệm vụ dịch
Chương trình Mã máy
chương trình nguồn (thường được viết bằng
nguồn tuyệt đối
ngôn ngữ lập trình bậc cao) sang các
chương trình đối tượng (chương trình đích) Phase
compiler loader
Chương trình Chương trình dịch
nguồn Compiler đích
Thông báo lỗi Mã đối Mã thực
linker
• Chương trình đích có thể không thực hiện tượng hiện
được ngay mà cần liên kết (link) đến thư viện
Thư viện
để được chương trình thực hiện
9/4/2012 5 9/4/2012 6
1
- 1. Ngôn ngữ lập trình cấp cao và trình dịch 1. Ngôn ngữ lập trình cấp cao và trình dịch
Thông dịch (interpreter) Dịch và thực hiện chương trình nguồn
• Làm nhiệm vụ “giải thích” Chương trình nguồn
Chương trình chương trình nguồn
nguồn – Phân tích câu lệnh tiếp Phase 1: Chuyển từ
compiler
– Thực hiện câu lệnh chương trình nguồn
Dữ liệu sang NN trung gian
interpreter
Chương trình bằng
ngôn ngữ trung gian
Kết quả • Chương trình thông dịch Phase 2: Thực hiện
có kích thước nhỏ hơn, mã trung gian
interpreter
nhưng chạy chậm hơn
Kết quả
9/4/2012 7 9/4/2012 8
1. Ngôn ngữ lập trình cấp cao và trình dịch 1. Ngôn ngữ lập trình cấp cao và trình dịch
Compiler >< interpreter Xây dựng chương trình dịch
• Compiler : Dịch trực tiếp ra mã máy • Viết trực tiếp từ ngôn ngữ máy
– Khó khăn
• Sử dụng ngôn ngữ bậc cao
– Dễ dàng thực hiện, hiệu quả
• Interpreter : Trực tiếp thực hiện từng lệnh mã nguồn
– Tăng tính khả chuyển,..
Chương trình bậc cao đầu tiên?
– Chiến lược chương trình mồi (bootstraps) trong
• Biến thể của Interpreter : thông dịch mã trung gian đó chương trình dịch được đặc trưng bởi
• Ngôn ngữ nguồn được dịch S
S T
• Ngôn ngữ đích T
• Ngôn ngữ cài đặt I I
9/4/2012 9 9/4/2012 10
1. Ngôn ngữ lập trình cấp cao và trình dịch
Xây dựng chương trình dịch Chương 1: Những khái niệm cơ bản
Viết chương trình dịch L cho máy M
• Dùng hợp ngữ của M viết L’ là tập con của L 1. Ngôn ngữ lập trình cấp cao và trình dịch
• Dùng L’ để viết L 2. Đặc trưng của ngôn ngữ lập trình cấp cao
Như vậy, L được thực hiện qua L’ để ra M 3. Các giai đoạn chính của chương trình dịch
L M L M
4. Khái niệm ngôn ngữ
L’ L’ M M
M 5. Văn phạm phi ngữ cảnh
PL0 PC PL0 PC
C C PC PC
6. Giới thiệu ngôn ngữ PL/0 mở rộng
C
9/4/2012 11 9/4/2012 12
2
- 2. Đặc trưng của ngôn ngữ lập trình cấp cao 2. Đặc trưng của ngôn ngữ lập trình cấp cao
Các thế hệ ngôn ngữ lập trình Các thế hệ ngôn ngữ lập trình
• Các ngôn ngữ lập trình bậc thấp
– Thế hệ thứ nhất : ngôn ngữ máy
• Được chia thành 5 thế hệ. – Thế hệ thứ hai : Assembly
• Việc phân chia cấp cao hay thấp phụ thuộc • Thế hệ thứ ba ←Ngôn ngữ bậc cao
mức độ trừu tượng của ngôn ngữ – Dễ hiểu hơn
– Cấp thấp : gần với máy • Câu lệnh gần ngôn ngữ tự nhiên
– Cấp cao : gần với ngôn ngữ tự nhiên – Cho phép thực hiện các khai báo, Ví dụ biến
– Phần lớn các NNLT cho phép lập trình cấu trúc
– Ví dụ: Fortran, Cobol, C, C++, Basic .
9/4/2012 13 9/4/2012 14
2. Đặc trưng của ngôn ngữ lập trình cấp cao 2. Đặc trưng của ngôn ngữ lập trình cấp cao
Các thế hệ ngôn ngữ lập trình Các thành phần của NNLTCC
• Ngôn ngữ lập trình thế hệ thứ tư
– Thường được sử dụng trong một lĩnh vực cụ thể 1. Từ vựng và cú pháp
– Dễ lập trình,xây dựng phần mềm
– Có thể kèm công cụ tạo form, báo cáo
2. Kiểu dữ liệu
– Ví dụ :SQL, Visual Basic, Oracle . . . 3. Các đại lượng
• Ngôn ngữ lập trình thế hệ thứ năm
4. Các toán tử và biểu thức
– Giải quyết bài toán dựa trên các ràng buộc đưa ra cho
chương trình (không phải giải thuật của người lập trình)
5. Các câu lệnh
– Việc giải quyết bài toán do máy tính thực hiện
– Phần lớn các ngôn ngữ dùng để lập trình logic 6. Chương trình con
• Giải quyết các bài toán trong lĩnh vực trí tuệ nhân tạo
9/4/2012 15 9/4/2012 16
2. Đặc trưng của ngôn ngữ lập trình cấp cao 2. Đặc trưng của ngôn ngữ lập trình cấp cao
Từ vựng và cú pháp Kiểu dữ liệu
Từ vựng Các kiểu cơ bản
– Chữ cái: A..Z, a..z – Kiểu số nguyên int Interger
– Chứ sô: 0..9 – Kiểu số thực float Real
– Dấu: dấu chức năng, dấu toán tử – Kiểu ký tự char Char
• Dấu đơn: +, -, ; {, }
– Kiểu logic 0, 1 Boolean
• Dấu kép: >=,
- 2. Đặc trưng của ngôn ngữ lập trình cấp cao 2. Đặc trưng của ngôn ngữ lập trình cấp cao
Các đại lượng Toán tử và biểu thức
Hằng Toán tử
– Số nguyên
– Số học: cộng (+), chia, chia dư(%, MOD),..
• Cách biểu diễn (decimal,octal, hexadecimal,..)
– Số thực – Logic
• Dấu phẩy tĩnh • Quan hệ: bằng (=,==) khác (!=, ), lớn hơn, (>),..
• Dấu phẩy động • Logic: Và (AND, &&), hoặc ( OR, ||),..
– Hằng chuỗi – Xâu: ghép xâu ←Pascal
• C: “Hello” Biểu thức ← Kết hợp các toán hạng bởi toán tử
• Pascal: ‘Hello’
– Số học: Trả về một con số
Tên
– Logic: Trả về một giá trị luận lý
– Nguyên tắc đặt tên ?
– Xâu: Trả về một chuỗi ký hiệu
– Độ dài?
9/4/2012 19 9/4/2012 20
2. Đặc trưng của ngôn ngữ lập trình cấp cao 2. Đặc trưng của ngôn ngữ lập trình cấp cao
Các câu lệnh Chương trình con
Câu lệnh tuần tự Các dạng chương trình con
– Câu lệnh gán: :=, =
– Thủ tục→ Không trả về giá trị (void)
– Câu lệnh vào/ra, gọi hàm
– Câu lệnh ghép, gộp: begin..end, { } – Hàm → Trả về một giá trị
Câu lệnh rẽ nhánh Vấn đề truyền tham số
– 1 vào 1 ra :if…then, if() – Truyền theo trị: Không thay đổi giá trị
– 1 vào 2 ra: if …then…else, if()…else…
– 1 vào, nhiều ra: case …..of, switch() {}
– Truyền theo biến (địa chỉ): thay đổi giá trị
Câu lệnh lặp Vấn đề Địa phương /toàn cục
– Số lần lặp xác định: For ..to/downto..do, for( ; ; ) – Địa phương: chỉ tồn tại trong chương trình con
– Kiểm tra điều kiện trước: While.. Do, while ()
– Roàn cục: Tồn tại trong toàn bộ chương trình
– Kiểm tra điều kiện sau: Repeat..Until, do..while()
9/4/2012 21 9/4/2012 22
2. Đặc trưng của ngôn ngữ lập trình cấp cao
Nhận xét Chương 1: Những khái niệm cơ bản
1. Ngôn ngữ lập trình cấp cao và trình dịch
Ngôn ngữ lập trình bậc cao có 2. Đặc trưng của ngôn ngữ lập trình cấp cao
nguyên tắc giống nhau, cách thể 3. Các giai đoạn chính của chương trình dịch
4. Khái niệm ngôn ngữ
hiện có thể khác nhau
5. Văn phạm phi ngữ cảnh
6. Giới thiệu ngôn ngữ PL/0 mở rộng
9/4/2012 23 9/4/2012 24
4
- 3. Các giai đoạn chính của chương trình dịch
Cấu trúc chương trình dịch
Các phase của chương trình dịch
Chương trình dịch gồm 3 phase chính Chương trình nguồn
1. Phân tích từ vựng Phân tích từ vựng
2. Phân tích cú pháp
– Phân tích ngữ nghĩa Phân tích cú pháp
3. Sinh mã Bảng
ký Phân tích ngữ nghĩa Xử lý
hiệu lỗi
Sinh mã trung gian
Tối ưu mã
Sinh mã máy
Chương trình đích
9/4/2012 25 9/4/2012 26
3. Các giai đoạn chính của chương trình dịch 3. Các giai đoạn chính của chương trình dịch
Bảng ký hiệu Bảng ký hiệu→Ví dụ
• Là cấu trúc dữ liệu dùng chứa tên và thuộc float pos, init, size; //var pos, init, size: real
tính cần thiết của chúng
Tên Kiểu Loại
– Thuộc tính cung cấp thông tin
…. ….
• Vị trí, kiểu, phạm vị hoạt động…
– Nếu là tên chương trình con: số tham số, kiểu trả về
Id3 size real var
Kiểu Tên
– Tên được xác định bởi bộ phân tích từ vựng Id2 init real var
Id1 pos real var
• Khi chỉ ra được một tên, tùy thuộc vào vị trí
…. ….
của tên trong chương trình
Bảng ký hiệu
– Đưa tên và 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 pos = init + 10 * size;
9/4/2012 27 9/4/2012 28
3. Các giai đoạn chính của chương trình dịch 3. Các giai đoạn chính của chương trình dịch
Phân tích từ vựng (Lexical Analysis - Scanner) Phân tích từ vựng →Ví dụ
pos := init + 10 * size;
Là pha đầu tiên của chương trình dịch
• Duyệt từng ký tự của chương trình nguồn Bộ PTTV thực hiện
– Loại bỏ các ký tự thừa • Đọc từng ký tự: bắt đầu từ chữ cái p
• Dấu tab, khoảng trắng, chú thích.. – Nhận dạng từ vựng thuộc dạng tên, hoặc từ khóa (vì bắt
đầu bởi 1 chữ cái)
• Xây dựng các từ vựng từ các ký tự đọc được – Đọc tiếp (o, s) tới khi gặp ký tự khác chữ cái, chữ số,
• Nhận dạng các từ tố từ các từ vựng • Gặp dấu trắng → xây dựng xong từ vựng pos
– Từ tố (token) là đơn vị cú pháp được xử lý – Do pos không trùng với từ khóa. Vậy pos là tên (ident)
trong quá trình dịch như một thực thể không – Trả lại cho bộ phân tích cú pháp từ tố ident
thể chia nhỏ hơn nữa • Đọc tiếp được dấu : rồi dấu = và sau đó dấu cách
• Chuyển các từ tố cho pha tiếp – Nhận dạng được từ vựng := và trả về từ tố gán (assign)
9/4/2012 29 9/4/2012 30
5
- 3. Các giai đoạn chính của chương trình dịch 3. Các giai đoạn chính của chương trình dịch
Phân tích từ vựng →Ví dụ Phân tích cú pháp (Syntax Analysis)
pos := init + 10 * size; • Bộ ptcp phân tích chương trình nguồn
Bộ PTTV trả về
– Dựa vào các từ tố nhận được từ pha pttv
Từ vựng Từ tố Ý nghĩa
• Kiểm tra những từ tố có tuân theo quy tắc
1 pos ident Tên Từ tố:
cú pháp của ngôn ngữ được dịch không
2 := assign Phép gán assign, ident,
plus,.. – Cú pháp thể hiện cấu trúc văn phạm của ngôn
3 init ident Tên
do người ngữ, được mô tả dạng: đệ quy, BNF, sơ đồ..
4 + plus Dấu cộng
viết CTD tự • Kết quả của bộ phân tích cú pháp:
5 10 number Con số đặt ra để
6 * times Dấu nhân – Cây phân tích cú pháp (nếu có)
dễ dàng
ident • Có cây phân tích → chương trình đúng cú pháp
7 size Tên mã hóa
8 ; semicolon Chấm phẩy c/trình – Thông báo lỗi nếu ngược lại
9/4/2012 31 9/4/2012 32
3. Các giai đoạn chính của chương trình dịch 3. Các giai đoạn chính của chương trình dịch
Phân tích cú pháp →Ví dụ 1 Phân tích cú pháp →Ví dụ 2
• Quy tắc đinh nghĩa một biểu thức • Quy tắc đinh nghĩa một lệnh
1. Tên là một biểu thức 1. Nếu Id là một Tên, E là một biểu thức thì
Luật cơ sở
2. Con số là biểu thức Id := E là một câu lệnh
3. Nếu E, E1, E2 là biểu thức thì Luật đệ quy 2. Nếu E là một biểu thức, S là một lệnh thì
E1+E2, E1* E2, (E) là biểu thức If E Then S, While E Do S là câu lệnh
• Kiểm định: init +10 * size là biểu thức? Kiểm định: pos := init + 10 * size là câu lệnh?
– Theo (2): 10 là biểu thức
– Theo bộ phân tích từ vựng: pos là một tên
– Theo (1): size là biểu thức
– Theo ví dụ 1: init + 10 * size là một biểu thức
– Theo (3) 10 * size là biểu thức
– Vậy theo luật (1) pos := init+10*size là một lệnh
– Theo (1): init là biểu thức
Ptcp thường được biểu diễn bởi cây phân tích/cây cú pháp
9/4/2012
– Theo (3): init + 10 * size là biểu thức 33 9/4/2012 34
3. Các giai đoạn chính của chương trình dịch 3. Các giai đoạn chính của chương trình dịch
Phân tích cú pháp → Cây phân tích (parse tree) Phân tích cú pháp → Cây cú pháp (syntax tree)
pos := init + 10 * size • Các nút trong là các toán tử
• Các toán hạng là các nút con của toán tử
:=
pos := init + 10 * size
pos + :=
pos +
*
init *
init
10 size
10 size
9/4/2012 35 9/4/2012 36
6
- 3. Các giai đoạn chính của chương trình dịch 3. Các giai đoạn chính của chương trình dịch
Phân tích ngữ nghĩa (Semantic Analysis) Sinh mã (Code Generation)
• Kiểm tra lỗi ngữ nghĩa của chương trình • Được thực hiện khi chương trình nguồn
– Lệnh pos := init+10*size đúng cú pháp
đúng cả về cú pháp và ngữ nghĩa
– Nếu pos là hằng số
→ pos := init+10*size sai ngữ nghĩa • Thường gồm 3 giai đoạn
• Kiểm tra kiểu toán hạng có phù hợp toán tử – Sinh mã trung gian
– % (MOD) đòi hỏi toán hạng nguyên – Tối ưu mã
– Một số toán tử chấp nhận toán hạng khác kiểu – Sinh mã đích
• Vấn đề chuyển kiểu tự động (nguyên → thực)
• Ví dụ pos := init+int2Real(10) * size
• Lấy thông tin về kiểu của danh biểu (tên)
– Thông tin dùng cho giai đoạn sinh mã
9/4/2012 37 9/4/2012 38
3. Các giai đoạn chính của chương trình dịch 3. Các giai đoạn chính của chương trình dịch
Sinh mã→Sinh mã trung gian Sinh mã→Sinh mã trung gian→Mã 3 địa chỉ
• Mã nguồn được chuyển sang chương trình tương • Mỗi câu lệnh có nhiều nhất
đương trong ngôn ngữ trung gian – 3 toán hạng
– Mã trung gian là mã máy độc lập, tương tự với tập lệnh – 2 toán tử, trong đó có 1 toán tử gán
trong máy.
• Chương trình dịch phải sinh ra biến tạm để
• Ưu điểm của mã trung gian
– Thuận lợi khi cần thay đổi cách biểu diễn chương trình đích
chứa giá trị tính toán sau mỗi lệnh
– Có thể tối ưu hóa mã độc lập với máy đích cho dạng biểu Ví dụ: pos := init+int2Real(10) * size
diễn trung gian. Sinh ra mã 3 địa chỉ
– Giảm thời gian thực thi chương trình đích vì mã trung gian
Temp1 := Int2Real(10) Id1, Id2, Id 3 là các
có thể được tối ưu
Temp2 := Temp1 * Id 3 con trỏ, trỏ tới các
• Ngôn ngữ trung gian
Temp3 := Id2 + Temp2 phần tử size, init, pos
– Mã 3 địa chỉ (thường được dùng) trong bảng ký hiệu
– Cây cú pháp, Ký pháp Ba Lan sau (hậu tố),..
Id1:= Temp3
9/4/2012 39 9/4/2012 40
3. Các giai đoạn chính của chương trình dịch 3. Các giai đoạn chính của chương trình dịch
Sinh mã→Tối ưu mã trung gian Sinh mã→Sinh mã đích
• Mục đích: • Mục đích: Tạo chương trình thực thi
– Tối ưu về kích thước, tốc độ • Thực hiện:
– Các biến được cấp ô nhớ cụ thể
Ví dụ
– Các câu lệnh trung gian được thay bằng chuỗi
– Int2Real() được thay bằng số thực tại thời
mã máy tương đương
điểm dịch
– Các biến được ấn định cho các thanh ghi
– Temp3 chỉ dùng 1 lần làm nơi lưu tạm thời dữ
liệu trước khi chuyển cho Id1 Ví dụ
• Có thể thay Id1 trực tiếp cho Temp3 MOVF Id3, R2
Temp1 := 10.0 * Id 3
– Kết quả MULF #10.0, R2
Temp1 := 10.0 * Id 3 MOVF Id2, R1
ADDF R2, R1 ID1:= Id2 + Temp1
Id1 := Id2 + Temp1
MOVF R1, Id1
9/4/2012 41 9/4/2012 42
7
- 3. Các giai đoạn chính của chương trình dịch 3. Các giai đoạn chính của chương trình dịch
Xử lý lỗi Xử lý lỗi
Lỗi có thể gặp trong mọi pha của CTD
• Phân tích từ vựng • Gặp lỗi, chương trình dịch cần thông báo
– Gặp ký tự lạ. Ví dụ: @, $,.. trong NNLT C – Ghi nhận kiểu lỗi
• Phân tích cú pháp – Ghi nhận vị trí gây ra lỗi (dòng, cột,..)
– Không tuân theo cú pháp: VD while (a b)
• Có thể cần hồi phục sau khi gặp lỗi
• Phân tích ngữ nghĩa
– Gán giá trị cho hằng, tính toán với tên thủ tục – Mục đích: cho phép tiến hành phân tích tiếp tục,
• Sinh mã tránh lãng phí
– Kích thước quá lớn – Có thể thông báo không chính xác
Ví dụ: int Arr[1000][1000]; → Lỗi tràn ô nhớ
9/4/2012 43 9/4/2012 44
3. Các giai đoạn chính của chương trình dịch
Ghi chú
Quá trình dịch một câu lệnh
Position := Initial+Rate*60
• Phân chia thành từng pha nhằm mục đích
nghiên cứu để chọn giải pháp thích hợp
[Phan Thị Tươi, 1998]
• Trong cài đặt, kết hợp các pha thành các
modul chương trình. Thường gồm 2 phần
– Phần đầu: Modul liên quan tới phân tích từ
vựng, phân tích cú pháp, phân tích ngữ nghĩa và
sinh mã trung gian
– Phần sau: Tối ưu mã, sinh mã đích, xử lý lỗi
• Cơ sở đề ra ngôn ngữ lập trình là lý thuyết
ngôn ngữ và văn phạm
9/4/2012 45 9/4/2012 46
4. Khái niệm ngôn ngữ
Chương 1: Những khái niệm cơ bản Giới thiệu
• Ngôn ngữ (tự nhiên/nhân tạo):
1. Ngôn ngữ lập trình cấp cao và trình dịch – Tập hợp các câu có cấu trúc quy định
2. Đặc trưng của ngôn ngữ lập trình cấp cao • Câu:
– Tập hợp các từ
3. Các giai đoạn chính của chương trình dịch
• Từ:
4. Khái niệm ngôn ngữ – Ký hiệu nào đó
5. Văn phạm phi ngữ cảnh • Ngữ pháp/cú pháp
6. Giới thiệu ngôn ngữ PL/0 mở rộng – Cấu trúc quy định tạo câu của trong ngôn ngữ
– Ngôn ngữ lập trình → cú pháp
9/4/2012 47 9/4/2012 48
8
- 4. Khái niệm ngôn ngữ 4. Khái niệm ngôn ngữ
Khái niệm văn phạm và ngôn ngữ Bộ chữ
1. Bộ chữ • Tập hữu hạn và khác rỗng mà các thành phần
2. Xâu ký tự được gọi là các ký hiệu
– Thường được ký hiệu V (Vocabulary)
3. Văn phạm
Ví dụ
4. Suy dẫn
– Bảng chữ cái a,b,c…là bộ chữ cái của một ngôn
5. Câu ngữ tự nhiên
6. Ngôn ngữ – Bộ từ điển tiếng Anh là bộ chữ cái trong ngôn
7. Đệ quy ngữ tiếng Anh
8. Phân loại văn phạm – Các từ khóa, tên, ký hiệu.. là bộ chữ của một
ngôn ngữ lập trình
9/4/2012 49 9/4/2012 50
4. Khái niệm ngôn ngữ 4. Khái niệm ngôn ngữ
Xâu ký tự Xâu ký tự
• Độ dài xâu
Khái niệm
– Số ký hiệu trong xâu đó
– Là dãy liên tiếp, hữu hạn các ký của một bộ chữ
– Thường được ký hiệu |α| hay l(α)
– Thường được ký hiệu α, β, γ,.. – Ví dụ: l(α) = 5 l(β)= 4
– Xâu rỗng: xâu không chứa ký hiệu nào l(γ) = 12 l(ε) = 0
• Thường được ký hiệu ε • Ghép xâu
Ví dụ – Ghép 2 xâu α, β là việc viết các ký tự của α rồi đến β
– α : Madam → Xâu trên bảng chữ cái a, b, c,.. • Xâu con
– β : Hôm nay trời đẹp → Xâu trong tiếng Việt – Xâu v là xâu con của w nếu xâu v được tạo nên từ dãy
các ký hiệu liên tiếp của xâu w
– γ : while (a > b) a = a – b; → Xâu trong NNLT • v là tiền tố w nếu v nằm ở đầu, nếu nằm ở cuối, v là hậu tố
• Ví dụ: ada là xâu con của xâu madam
9/4/2012 51 9/4/2012 52
4. Khái niệm ngôn ngữ 4. Khái niệm ngôn ngữ
Xâu ký tự → Tính toán trên tập xâu Xâu ký tự → Tính toán trên xâu
A, B là 2 tập xâu trên một bộ chữ • Tính chất
• Hợp: A ∪ B = {α| α ∈A hoặc α ∈B } – A+ = A A* = A* A
• Giao: A ∩ B = {α| α ∈A và α ∈B } – A* = A+ ∪ {ε}
• Tích/Ghép: AB={x=αβ| α ∈A và β ∈B } • Ví dụ: Cho A = {0, 1}
– A0 = {ε}
• Tích Descarter: AB={| α ∈A và β ∈A } – A1 = {0, 1}
• Lũy thừa: An = {ε} nếu n = 0 – A2 = {0, 1} {0, 1} = {00, 01, 10, 11}
An = AAn-1 = An-1A nếu n > 0 – …..
– An = {Tập các số nhị phân độ dài n}
• Bao đóng: A* = lim(A0 ∪ A1 ∪.. ∪ An), n→∞ – A+ = {0, 1, 00, 01, 10, 11, 000, 001,…}
• Bao đóng dương : A+ = lim(A1 ∪ A2 ∪.. ∪ An) – A* = {ε, 0, 1, 00, 01, 10, 11, 000, 001,…}
9/4/2012 53 9/4/2012 54
9
- 4. Khái niệm ngôn ngữ 4. Khái niệm ngôn ngữ
Văn phạm (Grammar) Văn phạm → Ví dụ
G = (VT, VN, P, S)
Cho văn phạm
• VT: Tập các ký hiệu kết thúc của một bảng chữ
– Các phần tử của VT thường được ký hiệu: a, b, c,..
G1 = (VT, VN, P, S)
• VN: Tập các k/hiệu không kết thúc của một bảng chữ Trong đó
– Các phần tử của VN thường được ký hiệu: A, B, C,.. – VT ={a, b, c}
– VT∩VN = ∅ ; V = VT∪VN: Bộ chữ của văn phạm
– VN ={S, A}
• S: Ký hiệu bắt đầu. S ∈VN
– P ={S →aSA, S→b, A →bA, A→c}
• P: Tập hữu hạn các cặp (α,β) được gọi là các quy
tắc hay các sản xuất. Thường được viết α→β Ghi chú
– α ∈ V* VN V* //→Phải có ít nhất một ký hiệu không k/thúc – Chỉ cần nhắc tới tập sản xuất khi giới thiệu
– β ∈ V* // → Có thể chứa xâu rỗng văn phạm
9/4/2012 55 9/4/2012 56
4. Khái niệm ngôn ngữ 4. Khái niệm ngôn ngữ
Suy dẫn (Derivation) Suy dẫn
Cho văn phạm G = (VT, VN, P, S) Cho văn phạm G = (VT, VN, P, S)
• Gọi γ viết ra δ hay δ được suy dẫn trực tiếp • Gọi δ được suy dẫn ra từ γ, nếu tồn tại dãy
ra từ γ, và được ký hiệu γ ⇒ δ nếu tồn tại các xâu α0, α1, α2,…, αn thỏa mãn điều kiện
các xâu α, β, v, w thỏa mãn các điều kiện
– γ = αvβ
γ = α0 ⇒ α1 ⇒ α2 ⇒ …. ⇒ αn = δ
Do v→w là một sản xuất của P.
– δ = αwβ Thay v trong γ bằng w, sẽ được δ • Nếu n ≥ 1, áp dụng ít nhất 1 bước suy dẫn,
– (v, w) ∈P {có thể viết v→w ∈ P} ký hiệu: γ ⇒+ δ
– α, β ∈ V*, v ∈V*VNV*, w∈ V* • Nếu n ≥ 0, có thể không áp dụng bước nào,
• Ví dụ với văn phạm G1 ký hiệu: γ ⇒* δ
– aSc ⇒ abc {α=a, β=c, v=S,w=b, S →b ∈P }
9/4/2012 57 9/4/2012 58
4. Khái niệm ngôn ngữ 4. Khái niệm ngôn ngữ
Suy dẫn → Ví dụ Câu
Xét văn phạm G1 Cho văn phạm G = (VT, VN, P, S)
• abA ⇒ abbA {α=ab, β=ε, v=A,w=bA, A →bA ∈P }
• Một xâu δ được suy ra từ ký hiệu khởi đầu
• abA ⇒ abbA ⇒ abbbA ⇒ abbbbA ⇒ abbbbc
{α0= abA, α1= abbA,… α4= abbbbc}
S, được gọi là dạng câu hay dạng cú pháp
– δ là một dạng câu nếu S ⇒* δ
Vậy
abA ⇒* abbbbc • Câu là một dạng cú pháp chỉ bao gồm toàn
abA ⇒+ abbbbc ký hiệu kết thúc
abA ⇒* abA //← Áp dụng 0 bước suy dẫn – δ là một câu nếu S ⇒* δ và δ∈ VT*
abA ⇒+ abA //← Sai, do áp dụng ít nhất 1 suy dẫn
9/4/2012 59 9/4/2012 60
10
- 4. Khái niệm ngôn ngữ 4. Khái niệm ngôn ngữ
Câu → Ví dụ Ngôn ngữ
Ví dụ văn phạm G1 Cho văn phạm G = (VT, VN, P, S)
S⇒aSA ⇒abA ⇒abc • Ngôn ngữ L được sinh ra từ văn phạm G, ký
S⇒aSA ⇒abA ⇒abbA⇒abbc hiệu L(G) là tập tất cả các câu của văn phạm
S⇒aSA ⇒abA ⇒abbA ⇒abbbA⇒abbbc – L(G) = {δ | δ∈ VT* và S ⇒* δ }
Dạng câu: aSA, abA, abc, abbA, abbc,… • Ví dụ văn phạm G1
Câu: abc, abbc, abbbc, abbbbc,… – L(G1) = {b, abc, abbc, abbbc,… aabbcc,…}
• G2= ({a,b}, {S,A}, {S →aA, A →a, A →b},S)
aabbcc có phải là một câu?
– L(G2) = {aa, ab}
9/4/2012 61 9/4/2012 62
4. Khái niệm ngôn ngữ 4. Khái niệm ngôn ngữ
Quy ước Ngôn ngữ→Ví dụ
Nếu A→α1 Cho văn phạm G = (VT, VN, P, S)
A→α2 – VT = {Mơ, Mận, thì, uống, nhanh, đẹp}
….. – VN={,,,}
A→αn – S : Câu
Được viết gọn lại thành A→α1| α2| …| αn –P={ →,
Ví dụ: → Mơ | Mận,
→ uống | thì,
G1=({a,b,c},{S,A},{S →aSA|b, A →bA|c},S)
→ nhanh | đẹp }
G2= ({a,b}, {S,A}, {S →aA, A →a|b}, S) L(G) = {Mơ uống nhanh, Mơ thì nhanh, Mơ thì đẹp,
Mơ uống đẹp, Mận thì nhanh,…}
9/4/2012 63 9/4/2012 64
4. Khái niệm ngôn ngữ 4. Khái niệm ngôn ngữ
Đệ quy Văn phạm tương đương
Cho văn phạm G = (VT, VN, P, S)
A ∈VN //← A là một ký hiệu không kết thúc Hai văn phạm là tương đương, nếu chúng
• A được gọi là đệ quy nếu tồn tại cùng sinh ra một ngôn ngữ
A⇒+αAβ, với α, β ∈V*
G1 = (1VT, 1VN, P1, S1)
• Nếu α=ε, (A⇒+Aβ) thì gọi là đệ quy trái
– Nếu A⇒Aβ: Đệ quy trái trực tiếp (Sản xuất: A → Aβ) G2 = (2VT, 2VN, P2, S2)
• Nếu β =ε, (A⇒+ αA) thì gọi là đệ quy phải
– Nếu A⇒ αA : Đệ quy phải trực tiếp (Sản xuất: A → αA) L(G1) = L(G2) ⇒ G1⇔G2
• Nếu α,β ≠ ε, (A⇒+ αAβ) thì gọi là đệ quy trong
– Nếu A⇒ αAβ: Đệ quy trong trực tiếp (Sản xuất:A→ αAβ)
Ví dụ, định nghĩa Tên
9/4/2012
→|| 65 9/4/2012 66
11
- 4. Khái niệm ngôn ngữ 4. Khái niệm ngôn ngữ
Phân loại văn phạm Phân loại văn phạm
Phân thành 4 loại [Chomsky,1957] Được sử dụng
1. Văn phạm ngữ cấu (pharse structure grammar) trong biểu diễn
1. Ràng buộc: Không có ràng buộc ngoài đ/nghĩa cấu trúc từ vựng
2. Văn Phạm cảm ngữ cảnh (context sensitive)
• Ràng buộc: Nếu α→β thì l(α) ≤l(β); S →ε được chấp
nhận khi S không là vế phải của SX bất kỳ 1 2 3 4
3. Văn phạm phi ngữ cảnh (context free grammar)
• Ràng buộc: Vế trái của các sản xuất là một ký hiệu
không kết thúc
Thường được dùng
4. Văn phạm chính quy (regular grammar)
biểu diễn cú pháp của
Ràng buộc: SX có dạng A →a|aB hoặc A →a|Ba
9/4/2012 67 9/4/2012
ngôn ngữ lập trình 68
5. Văn phạm phi ngữ cảnh
Chương 1: Những khái niệm cơ bản Văn phạm phi ngữ cảnh
1. Ngôn ngữ lập trình cấp cao và trình dịch • Cây suy dẫn
2. Đặc trưng của ngôn ngữ lập trình cấp cao
• Suy dẫn trái, suy dẫn phải
3. Các giai đoạn chính của chương trình dịch
• Văn phạm đơn nghĩa
4. Khái niệm ngôn ngữ
5. Văn phạm phi ngữ cảnh
• Sản xuất đệ quy
6. Giới thiệu ngôn ngữ PL/0 mở rộng • Vấn đề phân tích cú pháp
9/4/2012 69 9/4/2012 70
5. Văn phạm phi ngữ cảnh 5. Văn phạm phi ngữ cảnh
Cây suy dẫn Cây suy dẫn→Ví dụ
• G = (VT, VN,P, S) là văn pham phi ngữ cảnh Văn phạm: E→ E+E | E*E | (E) | a
• Cây suy dẫn D cho VP G là cây có thứ tự, trong đó Xét xâu: ω = a + a * a
– Mỗi một nút có nhãn là ký hiệu trong tập VT∪VN ∪ {ε} E Thay thế các biến trái nhất:
– Nhãn của nút gốc là S (Start Symbol)
– Các nút lá có nhãn là một ký hiệu kết thúc hoặc ε
E * E E⇒E*E ⇒E+E*E ⇒a+E*E ⇒a+a*E ⇒a+a*a
Thay thế các biến phải nhất:
– Nếu A là nút trong của D và X1,X2,.., Xn là các hậu duệ trực E + E a
tiếp của A theo tự trái qua phải thì E⇒E*E ⇒E*a ⇒E+E*a ⇒E+a*a ⇒a+a*a
A → X1X2..Xn là một sản xuất của P a a Khá E
c nh
– Nếu n=0 (X= ε) thì X là hậu duệ đơn và duy nhất của A và au?
A → ε là một sản xuất trong P, Thay thế các biến trái nhất: E + E
– Biên (kết quả) của cây suy dẫn là một từ thu được bằng E⇒E+E⇒a+E⇒a+E*E⇒a+a*E⇒a+a*a
a E * E
cách nối các nút lá lại theo thứ tự từ trái qua phải Thay thế các biến phải nhất:
• Rõ ràng, nếu α là biên của D thì S ⇒* α E⇒E+E ⇒E+E*E ⇒E+E*a ⇒E+a*a ⇒a+a*a a a
9/4/2012 71 9/4/2012 72
12
- 5. Văn phạm phi ngữ cảnh 5. Văn phạm phi ngữ cảnh
Suy dẫn trái Suy dẫn phải
Cho văn phạm G = (VT, VN, P, S) Cho văn phạm G = (VT, VN, P, S)
• Gọi δ được suy dẫn trực tiếp ra từ bên trái của γ, và • Gọi δ được suy dẫn trực tiếp ra từ bên phải của γ,
được ký kiệu γ ⇒L δ nếu tồn tại các xâu x, α, β thỏa và được ký kiệu γ ⇒R δ nếu tồn tại các xâu y, α, β
mãn các điều kiện thỏa mãn các điều kiện
– γ = xAα ⇒ xβα = δ – γ = αAy ⇒ αβy = δ
Luôn thay ký hiệu không kết Luôn thay ký hiệu không kết
– A→ β ∈P, và – A→ β ∈P, và
– α, β ∈V*, x∈V * thúc bên trái nhất của xâu – α, β ∈V*, y∈V * thúc bên phải nhất của xâu
T T
• Gọi δ được suy dẫn ra từ bên trái của γ nếu tồn tại • Gọi δ được suy dẫn ra từ bên phải của γ nếu tồn tại
dãy các xâu α0, α1, α2,…,αn thỏa mãn dãy các xâu α0, α1, α2,…, αn thỏa mãn:
γ = α0 ⇒L α1 ⇒L α2 ⇒L …. ⇒L αn = δ γ = α0 ⇒R α1 ⇒R α2 ⇒R …. ⇒R αn = δ
– Nếu n ≥ 1, dùng ít nhất một suy dẫn, ký hiệu: γ ⇒L+ δ – Nếu n ≥ 1, dùng ít nhất một suy dẫn, ký hiệu: γ ⇒R+ δ
– Nếu n ≥ 0, có thể không suy dẫn nào, ký hiệu: γ ⇒L* δ
9/4/2012 73
– Nếu n ≥ 0, có thể không suy dẫn nào, ký hiệu: γ ⇒R* δ
9/4/2012 74
5. Văn phạm phi ngữ cảnh 5. Văn phạm phi ngữ cảnh
Văn phạm đơn nghĩa Văn phạm đơn nghĩa→Ví dụ 1
Văn phạm PNC G=(VT,VN,P,S) đơn nghĩa nếu Văn phạm: E→ E+E | E*E | (E) | a
– Với mỗi câu ω ∈ L(G) chỉ có đúng một suy dẫn Xâu: ω = a + a * a là biên của 2 cây suy dẫn
trái (hoặc một suy dẫn phải) ⇔ Chỉ có đúng một
⇒ Văn pham nhập nhằng
cây suy dẫn
E E
Ngược lại, nếu có nhiều hơn một suy dẫn trái,
E * E E + E
hoặc một suy dẫn phải hoặc có nhiều cây suy
dẫn ⇒ Văn phạm nhập nhằng E + E a a=2 a *
E E
Nếu ω ∈ L(G) có nhiều hơn 2 cây suy dẫn a a a a
⇒ Có thể phân tích cú pháp theo nhiều hơn 2 cách
⇒ Nhiều hơn 2 cách hiểu E=8 E=6
9/4/2012 75 9/4/2012 76
5. Văn phạm phi ngữ cảnh 5. Văn phạm phi ngữ cảnh
Văn phạm đơn nghĩa →Ví dụ 2 Văn phạm đơn nghĩa →Ví dụ 2
G=(VT,VN,P,S)
VT = {if, then, else}
if then else
VN={, }
S: if then
P = { →if then
if then if then else
→if then else }
Xét dạng câu
if then if then else if then
if then else
9/4/2012 77 9/4/2012 78
13
- 5. Văn phạm phi ngữ cảnh 5. Văn phạm phi ngữ cảnh
Văn phạm đơn nghĩa→Khử nhập nhằng Sản xuất đệ quy
Đưa thêm các ký hiệu không kết thúc và các • Sản xuất là đệ quy có dạng:
sản xuất để được các văn phạm tương đương A →αAβ, α,β∈V*
• Dùng để biểu diễn các quá trình lặp hay cấu
E→ E+E | E*E | (E) | a
trúc lồng nhau
E→ E+T | E*T | T
Luôn thực hiện từ trái qua • Đệ quy trái: A → b|Aa
phải trừ khi gặp biểu thức A ⇒ Aa ⇒ Aaa ⇒ Aaaa ⇒ baaaa ...
T →(E) | a trong ngoặc • Đệ quy phải: A → b|aA
E→ E+T | T A ⇒ aA ⇒ aaA ⇒ aaaA ⇒ aaaab ...
Phép nhân có độ ưu tiên cao
hơn phép cộng khi không T→ T*F | F • Đệ quy giữa A → b|aAb
gặp biểu thức trong ngoặc F →(E) | a VD: A → b|{A}
A ⇒ {A}⇒ {{A}} ⇒ {{{A}}} ⇒ {{{b}}}
9/4/2012 79 9/4/2012 80
5. Văn phạm phi ngữ cảnh 5. Văn phạm phi ngữ cảnh
Sản xuất đệ quy →Khử đệ quy trái Vấn đề phân tích cú pháp (1/4)
Khử đệ quy trái bằng cách thêm ký hiệu không • Cho văn phạm G = (VT, VN, P, S)
kết thúc và sản xuất mới để được văn phạm L(G) = {ω| ω∈ V*T và S ⇒*ω}
tương đương • Nhiệm vụ của phân tích cú pháp là xem xét
một xâu có thuộc ngôn ngữ được sản sinh
E→ TE’ bởi văn phạm không
E→ E+T | T E’ →+TE’ | ε
Cho x ∈ V*T; S ⇒*x ?
T→ T*F | F T→ FT’
• Nếu xâu x được đoán nhận, cần chỉ ra các
F →(E) | a T’→ *FT’ | ε
sản xuất đã sử dụng để sinh ra
F →(E) | a
– Cấu trúc lên cây suy dẫn
9/4/2012 81
• Tồn tại 2 phương pháp trên xuống/dưới lên 82
9/4/2012
5. Văn phạm phi ngữ cảnh 5. Văn phạm phi ngữ cảnh
Vấn đề phân tích cú pháp (2/4) Vấn đề phân tích cú pháp (3/4)
• Trên xuống (Top-down) Xét văn phạm: E→ E+T | T
– Xuất phát từ ký hiệu khởi đầu S đi dần tới nút T→ T*F | F
lá (xâu cần phân tích), bằng cách áp dụng liên F →(E) | a
tục các sản xuất Xâu cần phân tích ω: a+a*a
• Dưới lên (Bottom-up) Top-Down
– Xâu cần phân tích được xem xét từ trái qua E ⇒ E+T ⇒ T+T ⇒ F+T ⇒ a+T ⇒ a+T*F ⇒
phải và tìm cách thu gọn về ký hiệu khưởi đầu a+F*F ⇒ a+a*F ⇒ a+a*a
S bằng cách áp dụng các sản xuất Bottop-Up
a+a*a ⇐ F+a*a ⇐ T+a*a ⇐ E+a*a ⇐ E+F*a ⇐
E+T*a ⇐ E+T*F ⇐ E+T ⇐ E
9/4/2012 83 9/4/2012 84
14
- 5. Văn phạm phi ngữ cảnh
Vấn đề phân tích cú pháp (4/4) Chương 1: Những khái niệm cơ bản
• Phân tích quay lui
– Tại mỗi bước có nhiều sản xuất để lựa chọn 1. Ngôn ngữ lập trình cấp cao và trình dịch
– Nếu lựa chọn nhầm thực hiện quay lui
2. Đặc trưng của ngôn ngữ lập trình cấp cao
Phân tích quay lui tăng thời gian thực hiện
• Phân tích tất định 3. Các giai đoạn chính của chương trình dịch
– Tại mỗi bước xác định duy nhất một sản xuất 4. Khái niệm ngôn ngữ
– Yêu cầu văn phạm cần có tính chất nhất định 5. Văn phạm phi ngữ cảnh
– Các kỹ thuật
• Trên xuống: Phân tích LL(k), Đệ quy trên xuống,..
6. Giới thiệu ngôn ngữ PL/0 mở rộng
• Dưới lên: Thao tác trước, Phân tích LR(k),..
9/4/2012 85 9/4/2012 86
6. Giới thiệu ngôn ngữ PL/0 mở rộng 6. Giới thiệu ngôn ngữ PL/0 mở rộng
Dạng chuẩn BNF Ký pháp BNF
• Siêu ngữ (metalanguage) Là một tập các luật thỏa mãn:
– Ngôn ngữ sử dụng các lệnh để mô tả ngôn – Vế trái của mỗi luật là một cấu trúc cú pháp.
ngữ khác – Tên cấu trúc cú pháp là ký hiệu không kết thúc.
– Ký hiệu không kết thúc được bao trong cặp
• Dạng chuẩn BNF
– Ký hiệu kết thúc được phân cách bằng cặp nháy
– Backus-Normal-Form/Backus-Naur-Form đơn hoặc nháy kép
– Là dạng siêu cú pháp để mô tả các ngôn ngữ – Mỗi ký hiệu không kết thúc được định nghĩa bằng
lập trình một hay nhiều luật.
– BNF được sử dụng rộng rãi để mô tả văn – Các luật có dạng N ::= s
phạm của các ngôn ngữ lập trình, tập lệnh và • N là ký hiệu không kết thúc,
các giao thức truyền thông. • s là một xâu gồm 0 hay nhiều ký hiệu kết thúc và
không kết thúc.
9/4/2012 87
– Các luật có chung vế trái được phân cách bằng |
9/4/2012 88
6. Giới thiệu ngôn ngữ PL/0 mở rộng 6. Giới thiệu ngôn ngữ PL/0 mở rộng
Ký pháp BNF→Ví dụ Ký pháp EBNF (Extended BNF )
Được phát triển từ BNF, có ký pháp tương tự
• Mô tả cách viết một số nguyên, thực dấu
nhưng được đơn giản hoá bằng cách dùng một
phẩy tĩnh
số ký hiệu đặc biệt :
::=’-’| – Không cần dùng ‘ ’ cho ký hiệu kết thúc
::=|’.’
– Dùng { } phần bên trong có thể lặp lại một số lần
::=| • Nếu lặp lại m hay n lần , dùng m hay n là chỉ số trên
hoặc dưới
::=’0’|’1’|’2’|’3’|’4’|’5’|’6’|’7’|’8’|’9’
– Dùng ( | ) cho biết có thể lựa chọn 1 trong các ký
9/4/2012 89
hiệu nằm bên trong
9/4/2012 90
15
- 6. Giới thiệu ngôn ngữ PL/0 mở rộng 6. Giới thiệu ngôn ngữ PL/0 mở rộng
Ký pháp EBNF → Ví dụ Sơ đồ cú pháp
• S→a {b} ⇔ S→a |ab|abb|…. • Là công cụ để mô tả cú pháp của ngôn ngữ lập
trình dưới dạng đồ thị
• S→ [a]α ⇔ S→ α |a α • Mỗi sơ đồ cú pháp là một đồ thị định hướng với lối
• S→ (a|b|c)α ⇔ S→ aα | bα | cα vào và lối ra xác định.
• Mỗi sơ đồ cú pháp có một tên duy nhất
Trong BNF BNF >< EBNF
::= ‘IF’ ‘THEN’ | ‘IF’
THEN ‘ELSE’
Trong EBNF
::= IF THEN [ELSE
]
9/4/2012 91 9/4/2012 92
6. Giới thiệu ngôn ngữ PL/0 mở rộng 6. Giới thiệu ngôn ngữ PL/0 mở rộng
Ngôn ngữ PL/0 Ngôn ngữ PL/0
• Được giới thiệu bởi Niklaus Wirth năm 1975 Đặc trưng cơ bản (tiếp)
– Trong quyển Algorithms + Data Structures = Programs • Hỗ trợ kiểu dữ liệu cơ bản kiểu nguyên
• Là ngôn ngữ lập trình phục vụ giáo dục – Nếu hằng số nguyên có hơn 6 chữ ⇒ Báo lỗi số quá lớn
– Tựa Pascal, chứa đặc trưng của một NNLT cấp cao – PL/0 mở rộng có cấu trúc mảng một chiều các số nguên
Đặc trưng cơ bản • Biểu thức số học, biểu thức so sánh
• Từ vựng: • Cho phép định nghĩa hằng (const), biến (var)
– Chữ cái: a..z, A..Z ; Chữ số: 0..9 • Câu lệnh gán (:=) , gộp (begin end), gọi thủ tục
– Dấu đơn: + - * / % ( ) [ ] > < = , ; . (call), rẽ nhánh (if..else), lặp (while, for)
– Dấu kép: := >=
- Statement
Expression
Ident := Expression
+
[ Expression ]
Term
CALL Ident ( Expression ) -
+
,
Term
BEGIN Statement END
-
Statement ;
ELSE Statement Term
Factor
IF Condition THEN Statement
WHILE Condition DO Statement *
Factor
FOR Ident := Expression TO
/
Expression DO Statement
9/4/2012 97 9/4/2012 98
6. Giới thiệu ngôn ngữ KPL (Kyoto Programming Language)
Factor
Ident Ví dụ viết trên ngôn ngữ PL/0 mở rộng
Program Example2;
Number
Var a,b,c;
Procedure gcd(a; b; var d);
( Expression )
Begin
Condition While a b do
ODD Expression if a > b then a = a – b
= else b = b – a;
d = b;
>
End;
>=
Expression Expression Begin
< Readln(a); Readln(b);
nguon tai.lieu . vn
