Xây dựng chương trình dịch

Xây dựngCHƯƠNG TRÌNH DỊCHPhạm Đăng Hảihaipd@soict.hut.edu.vn*1Chương 2: Phân tích từ vựngNhiệm vụ của bộ phân tích từ vựngBiểu diễn cấu trúc từ vựngPhân tích từ vựng của ngôn ngữ KPL2Mục đích & Nhiệm vụMục đích:Tìm chuỗi dài nhất các ký tự đầu vào, bắt đầu từ ký tự hiện tại tương ứng với một từ tố và trả về từ tố nàyNhiệm vụDuyệt từng ký tự của văn bản nguồnLoại bỏ các ký tự không cần thiết như dấu cách, chú thích,..Xây dựng từ vựng từ những ký tự đọc đượcNhận dạng từ tố và gửi tới pha tiếpNhận biết từ tố gồmNhận biết các từ khóa, tên do người dùng định nghĩaNhận biết các con số, hằng chuỗi, hằng ký tựNhận biết các ký tự đặc biệt (+,*,..), ký hiệu kép (:=,!=,..)1. Nhiệm vụ của bộ phân tích3Từ vựng và Từ tốTừ vựng (Lexeme)Là đơn vị nhỏ nhất trong ngôn ngữ lập trìnhĐược coi là ký hiệu của một bảng chữ của ngôn ngữĐược xây dựng từ các ký tự ASCIITừ tố (Token)Là thuật ngữ dùng chỉ các từ vựng có cùng ý nghĩa cú phápCó thể coi từ vựng là những từ cụ thể trong từ điển: “hôm nay”, “trời”, “đẹp”; còn từ tố là loại từ: “trạng từ”, “danh từ”, “tính từ”,..1. Nhiệm vụ của bộ phân tích4Từ tốVí dụ“pos”, “start”, “size”, “+”, “10”, “*”,”:=“, “;” là từ vựng“pos”, “start”, “size”,  các từ vựng thuộc lớp từ tố tên (ident)”:=“ từ vựng của từ tố gán (assign)“10”  từ vựng của từ tố số nguyên (number)“+”  từ vựng của từ tố cộng (plus)“*”  từ vựng của từ tố nhân (times) “;”  từ vựng của từ tố chấm phẩy (semicolone)1. Nhiệm vụ của bộ phân tíchpos := start + 10 * size;5Từ tốChú ý1. Nhiệm vụ của bộ phân tíchCác từ tố Ident, number, plus, assign,... do người viết trình dịch tự định nghĩa để dễ dàng cho việc mã hóa chương trình. Đây là việc số hóa ký hiệuMột từ tố có thể ứng với tập các từ vựng khác nhau nên cần thêm một số thông tin khác để biết được cụ thể đó là từ vựng nàoCác chuỗi “19”, “365” đều là chuỗi số, có từ tố “number”, nhưng khi sinh mã cần phải biết rõ giá trị là 19 hay 365 Bộ phân tích từ vựng không chỉ nhận dạng được các từ tố mà còn phải biết thuộc tính tương ứngTừ tố tác động đến bộ phân tích cú phápThuộc tính sử dụng trong bộ sinh mã6Thực hiệnThực hiện lặp dựa vào yêu cầu từ bộ ptcpBộ ptcp khi cần một từ tố sẽ gọi getToken()Nhận được y/cầu, bộ pttv sẽ đọc các ký tự cho tới khi xây dựng xong từ vựng và nhận ra từ tố hoặc gặp lỗiThường bộ pttv được chia thành 2 phần chính Đọc ký tựXây dựng từ vựng và nhận dạng từ tố1. Nhiệm vụ của bộ phân tíchPhân tích từ vựngPhân tích cú phápBảng ký hiệuChương trình nguồnTokengetToken()7Mẫu (Pattern)Là luật để mô tả một từ tố nào đóCơ sở phân biệt & nhận dạng các từ tố khác nhauChuỗi ký tự cùng thỏa mãn một luậtcó cùng một từ tốTừ tố là tên riêng của một luật mô tả, từ vựng là một trường hợp thỏa mãn luậtVí dụLuật mô tả của từ tố IdentBắt đầu là một chữ cáiTiếp theo là tổ hợp chữ cái, chữ sốLuật mô tả của từ tố assignBắt đầu bởi ký tự “:”, ngay sau đó là ký tự “=“Dùng văn phạm chính quy để mô tả1. Nhiệm vụ của bộ phân tích8Chương 2: Phân tích từ vựngNhiệm vụ của bộ phân tích từ vựngBiểu diễn cấu trúc từ vựngPhân tích từ vựng của ngôn ngữ KPL9Biểu thức chính quy (regular expression)Cho  là một bảng chữ.  là biểu thức chính quy biểu diễn tập  là biểu thức chính quy biểu diễn tập {}a  , a là biểu thức chính quy biểu diễn tập {a}Nếu r và s là các biểu thức chính quy biểu diễn các tập R và S tương ứng thì (r + s) [(r|s)], (rs), (r*) là các biểu thức chính quy biểu diễn các tập R  S, RS và R* tương ứng.Ngôn ngữ được xác định bởi biểu thức chính quy e, ký hiệu là L(e) là ngôn ngữ chính quy 2. Biểu diễn cấu trúc từ vựng10Biểu thức chính quy  Ví dụCho  ={a,b} một bảng chữ. e1 = a*+b*  L(e1)= {ε,a,aa,aaa,,b,bb,bbb}e2 = a*b*  L(e2)= {ε,a,b,aa,ab,bb,aaa,aab,..}e3 = a(a+b)* L(e3)={a,aa,ab,aaa,aab,aba,abb,..} Xâu dạng: bắt đầu là ký hiệu a, tiếp theo là tổ hợp bất kỳ của các ký hiệu a, bNếu a là một chữ cái, b là chữ số L(e3) là ngôn ngữ chứa các têne3 biểu thức chính quy sinh ra tên2. Biểu diễn cấu trúc từ vựng11Văn phạm chính quy và Ngôn ngữ chính quyVăn phạm chính quyVăn phạm mà mọi sản xuất có dạng Aa|aB hoặc Aa|BaDùng diễn tả từ vựng của NNLT| | “a” |”b” |”c” |.|”z”|”A”|”B”||”Z” ”0” | ”1” | ”2” | ”3” |”4” | ”5” |”6” | ”7” |”8” |”9”Văn phạm chính quy sinh ra ngôn ngữ chính quyNgôn ngữ chính quyĐược biểu diễn (mô tả) bởi biểu thức chính quyĐoán nhận bởi các Otomat hữu hạn2. Biểu diễn cấu trúc từ vựng12Ô tô mát hữu hạnGồm một tập các trạng thái QCó một trạng thái đầu q0  QCó một tập trạng thái kết thúc F QMột bộ chữ vào Một tập các hàm dịch chuyển :(Q x )  QHoạt độngÔ-tô-mát xuất phát từ trạng thái đầu, đọc từng ký hiệu của xâu vào, chuyển trạng thái dựa trên trạng thái hiện thời và ký hiệu đọc được.Sau khi đọc hết xâu vào mà ô-tô-mát ở trạng thái kết thúc, xâu được gọi là được đoán nhận bởi ô-tô-mát2. Biểu diễn cấu trúc từ vựng13Ô tô mát hữu hạnVí dụ = {a,b,c}Q = {q0, q1}q0 = q0 F = {q1}2. Biểu diễn cấu trúc từ vựngabcq0q1q0q0q1q0q1q1abcaabbcEndq0q1Xâu abcaabbc được đoán nhận14Ô tô mát hữu hạnBiểu diễn2. Biểu diễn cấu trúc từ vựngTrạng tháiTrạng thái đầuTrạng thái kết thúcppa(p,a) = qq1q0aabbccXâu trên bộ chữ {a,b,c} có lẻ ký hiệu a15Ô tô mát hữu hạnVí dụ2. Biểu diễn cấu trúc từ vựng1000q11010001(0+1)*101  Xâu nhị phân có hậu tố là 101Đoán nhận số nguyên hoặc số thực dấu phẩy tĩnhq1q2abq0a,b{a*b*}baq1q2Chữ sốq0Chữ sốChữ số16Chương 2: Phân tích từ vựngNhiệm vụ của bộ phân tích từ vựngBiểu diễn cấu trúc từ vựngPhân tích từ vựng của ngôn ngữ KPL17Các từ tố của KPLSố nguyênĐịnh danhTừ khóa: begin,end, if,then, while, do, call, const, var, procedure, program, type, function, of, integer, char, else, for, to, arrayHằng ký tự Dấu phép toán: số học: + - */ so sánh: = != =Dấu phân cách: ( ) . : ; (. .)Dấu phép gán: :=3. Phân tích từ vựng của ngôn ngữ KPL18Ô-tô-mát hữu hạn của bộ pttvSau mỗi từ tố được nhận biết, bộ từ vựng lại quay lại trạng thái s03. Phân tích từ vựng của ngôn ngữ KPL19Xây dựng từ vựngKhi bộ pttv - thủ tục nextToken() bắt đầu hoạt động, ô-tô-mát ở trạng thái khởi tạo (Trạng thái 0)Bộ pttv gọi liên tiếp nextChar() để đọc các ký hiệu trên văn bản nguồn cho tới khi gặp một ký tự không thuộc luật mô tả hiện tại Ô-to-mát không chuyển trạng thái đượcXâu đọc được là từ vựng mang ý nghĩa của từ tố đang phân tích và là trạng thái hiện tại của Ô-tô-mátĐọc thừa ra một ký tự Là ký tự trắng hoặc ký tự đầu của từ tố tiếp  Khi nextToken() được gọi, sẽ làm việc ngay với một ký tự có sẵn.3. Phân tích từ vựng của ngôn ngữ KPL20Xây dựng từ vựng//ch chứa ký tự đọc được từ văn bản nguồn bởi nextChar()switch(Ch) {case SPACE : while (Ch==SPACE) nextChar(); return;case LETTER: nextChar(); while (Ch==LETTER || Ch==DIGIT) nextChar(); return Ident; //Cũng có thể là từ khóa Phải kiểm tra case DIGIT: while (Ch==DIGIT) nextChar(); return number;case ‘+’: nextChar(); return plus;case ‘>‘ : nextChar(); if(Ch == ‘=‘) { nextChar(); return Geq;} else return Gtr;..}3. Phân tích từ vựng của ngôn ngữ KPL21Nhận dạng từ tốXây dựng xong từ vựng, cần nhận dạng từ tốLà tên trạng thái cuối cùng của Ô-tô-mátNếu Ô-tô-mát kết thúc ở trạng thái ident, cần kiểm tra đây có phải là từ khóaDùng kỹ thuật bảng chuyển đổi3. Phân tích từ vựng của ngôn ngữ KPLBEGINKW_BEGINCALLKW_CALL..VARKW_VARWHILEKW_WHILEChú ý: Với từ tố ident và number, cần phải ghi nhận giá trị từ vựng tương ứng22