intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

NGÔN NGỮ và PHƯƠNG PHÁP DỊCH - Chương 1: Những khái niệm cơ bản

Chia sẻ: Nam Trinhviet | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST
Báo xấu
319
lượt xem 31
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Ngôn ngữ lập trình cấp cao và trình dịch 2. Đặc trưng của ngôn ngữ lập trình cấp cao 3. Các giai đoạn chính của chương trình dịch 4. Khái niệm ngôn ngữ 5. Văn phạm phi ngữ cảnh 6. Giới thiệu ngôn ngữ PL/0 mở rộng 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 • Nhiều loại máy tính – Mỗi loại nhiều kiểu • Mỗi kiểu có ngôn ngữ máy riêng – Ngôn ngữ máy là dãy nhị phân...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: NGÔN NGỮ và PHƯƠNG PHÁP DỊCH - Chương 1: Những khái niệm cơ bản

  1. 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
  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 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
  3. 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: >=,
  4. 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
  5. 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
  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 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
  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 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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: := >=
  17. 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);
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2