Ngôn ngữ và phương pháp dịch

IT4073:NGÔN NGỮ và PHƯƠNG PHÁP 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 thức chính quyÔ tô mát hữu hạnPhân tích từ vựng của ngôn ngữ PL/02Mụ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 (semicolon)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ự “=“Luật được mô tả bởi biểu thức chính quy1. 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 thức chính quyÔ tô mát hữu hạnPhân tích từ vựng của ngôn ngữ PL/09Giới thiệu2. Biểu thức chính quyNgôn ngữ: Tập hợp của các câu/ xâu (string) Câu: Dãy hữu hạn của các từ/ký hiệu (symbol) Từ: Được tạo nên từ một bộ chữ hữu hạnVí dụ: Ngôn ngữ C là tập các câu lệnh tạo nên các chương trình C hợp lệBộ chữ cho ngôn ngữ C là tập các chữ cái ASCIIMột ngôn ngữ có thể là vô hạn, hoặc hữu hạnMột ngôn ngữ (có thể vô hạn) có thể được mô tả hữu hạn nhờ sử dụng biểu thức chính quy :Mỗi biểu thức đặc trưng cho một tập câu/xâuChỉ xét xâu có thuộc ngôn ngữ không, chưa xét ý nghĩa của xâu10Biểu thức chính quy (regular expression)Cho  là một bảng chữ của một ngôn ngữ.  là biểu thức chính quy biểu diễn ngôn ngữ  là biểu thức chính quy biểu diễn ngôn ngữ {}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 xâu R và S tương ứng thì (r + s), (r.s), (r*) là các biểu thức chính quy biểu diễn các tập xâu 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 thức chính quy11Biểu thức chính quyGhi chúBiểu thức (r + s) có thể được viết (r |s); Biểu thức (r.s) thành (rs)Có thể bỏ qua ký hiệu ( a | )  (a | ) // cũng có thể viết a?Có thể bỏ ngoặc đơn bởi định nghĩa thứ tự ưu tiênPhép đóng Kleene (*) ưu tiên hơn phép ghép(.) Phép ghép(.) ưu tiên hơn phép hoặc (+)Quy ước[abcd]  (a|b|c|d)[a-f]  [abcdef][a-fA-F]  [abcdefABCDEF]2. Biểu thức chính quy12Biể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,..}e2 = a*b*  L(e2) = {ε,a,b,aa,ab,bb,aaa,..}e3 = a(a+b)* L(e3)={a,aa,ab,aaa,aab,aba,abb,..} Xâu có 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 mô tả một tên2. Biểu thức chính quy13Tính chất đại số của btcq2 biểu thức chính quy là tương đương nếu cùng xác định một ngôn ngữ Nếu r, s, t là các biểu thức chính quyr + s = s + r r + r = r( r + s) + t = r + s + t = r + (s + t)(r.s).t = r. s. t = r. (s. t)r. = .r = r r +  =  + r = r r(s+t) = rs + ts (r+s)t = rt + str + r* = r* ; (r + )* = r* ; (r*)* = r*rr* = r*r = r+(r+s)* =(r*s*)*2. Biểu thức chính quy14Vă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 thức chính quy15Ngôn ngữ chính quy Văn phạm chính quyr là biểu thức chính qui cần chuyểnThêm ký hiệu khởi đầu S và tạo san xuất S  rLoại bỏ khỏi văn phạm các siêu ký hiệu của r SX dạng A r1.r2 : Thêm ký hiệu không kết thúc B và thay thành 2 SX: A r1B & B r2  SX dạng A r1+r2 : Thay bởi A r1|r2 SX dạng A r1* r2: Thêm ký hiệu không kết thúc B và thay thành 4 sản xuất A r1B & A  r2 & B r1B & B  r2 2. Biểu thức chính quy16Ví dụChuyển đổi biểu thức e = a(a+b)*Thêm S và sản xuất S a(a+b)*Loại bỏ các ký hiệu không thuộc bộ chữXét r = a(a+b)* //r1 =a; r2 = (a+b)* Thêm A và các SX SaA & A (a+b)*Xét A (a+b)* // r1 = a+b ; r2 =  Thêm B và các SX A(a+b)B & A   &B(a+b) & B  Áp dụng luật phân phối phải AaB+bB & A   & BaB+bB & B   A  aB|bB|  và B  aB|bB| 2. Biểu thức chính quy17Ví dụChuyển đổi biểu thức e = a(a+b)* (tiếp)Loại bỏ ký hiệu  bởi tạo ra xâu mới B  aB|bB|  thành B  aB|bB| a | b A  aB|bB|  thành A  aB|bB| a | b Vai trò của A và B là tương đương. Thay ký hiệu B bằng A và loại bỏ BKết quả: Văn phạm cuối S  a |aA A  aA | bA | a | b2. Biểu thức chính quy18Chương 2: Phân tích từ vựngNhiệm vụ của bộ phân tích từ vựngBiểu thức chính quyÔ tô mát hữu hạnPhân tích từ vựng của ngôn ngữ PL/019Mô tảGồ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át3. Ô tô mát hữu hạn20Ví dụ = {a,b,c}Q = {q0, q1}q0 = q0 F = {q1}3. Ô tô mát hữu hạnabcq0q1q0q0q1q0q1q1abcaabbcEndq0q1Xâu abcaabbc được đoán nhận21Biểu diễn ô tô mát hữu hạn3. Ô tô mát hữu hạnTrạ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 a22Ô tô mát hữu hạn đơn định (OHĐ)OHĐ(DFA: Deterministic Finite Automata) là một hệ thống gồm M = (, Q, ,q0, F): Bộ chữ vàoQ: Tập hữu hạn các trạng thái của bộ điều khiểnQ   =   : Q x Q: Hàm dịch chuyểnHàm dich chuyển đơn định:q0  Q: Trạng thái ban đầuF  Q Tập các trạng thái cuối3. Ô tô mát hữu hạn23Ví dụM = (, Q, ,q0, F) = {a,b}Q = {q0, q1, q2, q3}q0 = q0 F = {q2}3. Ô tô mát hữu hạnabq0q1q3q1q3q2q2q1q3q3q3q3q2q0aa,bbaq3q1bbaL(M) = {ab}{ab}n0 = {ab}n(n>0) = {ab,abab, ababab,..}24Hình trạng của FAHình trạng của một FA là một xâu dạng qx q Q : Trạng thái hiện tại của FA x  * : Phân chưa xét của xâu vàoKý hiệu được đọc bởi đầu đọc là ký hiệu đầu của xChuyển đổi hình trạngNếu x = ay và  (q,x) = p thì qx = qay  py qx  py : Là một bước biến đổi hình trạngVí dụ: q0abaab q1baab q2aab q1ab q3b q3Hình trạng đầu : q0 (: xâu cần đoán nhận)Nếu q0 * qn+1 F: Xâu  được đoán nhậnNgôn ngữ được đoán nhận mở DFA M là L(M)L(M) = { |   * và q0 * p F}3. Ô tô mát hữu hạn25Ô tô mát hữu hạn đơn địnhVí dụ3. Ô tô mát hữu hạn1000q11010001(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ĩnhab{anbm, n,m 0}q1q2q0a,bbaq1q2Chữ sốq0Chữ sốChữ số26Ô tô mát hữu hạn không đơn định (OHK)OHK (NFA: Nondeterministic Finite Automata) là một hệ thống gồm M = (, Q, ,q0, F), Q, q0, F: Định nghĩa như DFA : Q x ()2Q 2Q: Tập các tập con của Q, kể cả tập rỗngHàm dich chuyển không đơn định: Tại mỗi bước có thể tồn tại nhiều lựa chọnĐoán nhận xâu: Quá trình chuyển đổi hình trạng.Quá trình đoán nhận không đơn địnhNgôn ngữ: L(M) = { |   * và  q0 * p F}3. Ô tô mát hữu hạn27Ví dụM = ({a,b},{q0, q1, q2, q3,q4} ,q0, {q2, q4})3. Ô tô mát hữu hạnabq0{q0,q3}{q0,q1}q1{q2}q2{q2}{q2}q3{q4}q4{q4}{q4}Đoán nhận xâu có 2 ký tự a, hoặc 2 ký tự b liên tiếpa,bq4q0a,bbaq3q1q2baa,b q0abaab  q0baab  q0aab  q3ab  q4b  q428DFA và NFADFA và NFA tương đương nhau DFA và NFA cùng đoán nhận một lớp ngôn ngữ Ngôn ngữ chính quyVới mỗi NFA, tồn tại DFA tương đương3. Ô tô mát hữu hạna,bq4q0a,bbaq3q1q2baa,ba,bAbaCBDbbaa29Lân cận rỗng: -ClosureCho M = (, Q, ,q0, F) là NFACho p  Q. -Closure(p) ={q  Q | p * q}Lân cận rỗng của p là các trạng thái q có thể đi đến từ p với đường dẫn 3. Ô tô mát hữu hạnq0q3q1q2a-Closure(q0) = {q0,q1,q3}30Thuật toán tính lân cận rỗngCho M = (, Q, ,q0, F) là NFAThuật toán-Clos0{p} = {p}Repeat-Closi+1{p} = -Closi{p}  {qQ |sClosi(p), (s, )=q}Unil -Closi+1{p} = -Closi{p}-Closure{p} = -Closi+1{p} Nhận xét: Do -Closi{p}  -Closi+1{p}  Q Dãy đơn điệu tăng nên dãy hội tụ3. Ô tô mát hữu hạn31Lân cận rỗng của tậpNếu S  Q -Closure{S} =  -Closure{p} , p  SNếu không tồn tại bước chuyển rỗng-Closure{S} = { S }  S Q3. Ô tô mát hữu hạnq0q4q1q2aq3b-Closure{q0}={q0,q1,q3}-Closure{q1,q3}={q1,q3}32Chuyển đổi NFADFAWhile Stack.NotEmpty() DoS = Stack.Pop()For  a  doT = (q,a) ; q  Sq’ = -Closure(T)If q’  Q ThenQ’ = Q’ { q’ }Stack.Push(q’)’(S,a) = q’For  q’  QIf q’ F ThenF’ = F’  {q’}3. Ô tô mát hữu hạnCho NFA M =(, Q, ,q0,F) Xây dựng DFA M’=(, Q’, ’,q’0,F’)Thuật toán q’0 = -Closure({q0})Q’ ={q’0}F’ = { }Stack.PUSH(q’0)33Ví dụ - 13. Ô tô mát hữu hạnabq0{q0,q1}{q1}q1{q0,q1}Q’’ab{q0}{q0}{q0,q1}{q1}A{q0,q1}{q0,q1}{q0,q1}{q1}B{q1}{q1}{q0,q1}CDaq0q1aa,baDbCBAababaa,b34Ví dụ - 23. Ô tô mát hữu hạnaq0q1q3q2bcbq8bq0q1q3q4q5q7q6cq2a35Tối ưu hóa trạng thái OHĐNhiều DFA cùng đoán nhận một ngôn ngữCần tìm DFA có ít trạng thái nhấtDễ dàng biểu diễn trong máy tínhTrạng thái phân biệtHai trạng thái p và q là không phân biệt nếu  xâu w*, (pw,qw)*(p’,q’)FxF(Q-F)x(Q-F) pw,qw cùng dẫn tới trạng thái cuối hoặc khôngVí dụ:  là xâu phân biệt giữa các trạng thái kết thúc và không kết thúcNguyên tắc: Phân hoạch Q thành các nhóm t/thái không phân biệt Thay thế nhóm bằng trạng thái duy nhất3. Ô tô mát hữu hạn36Tối ưu hóa trạng thái OHĐChia Q thành 2 nhóm F và Q - FGiả thiết đã tồn tại các nhóm A1, A2,An Xét nhóm Am = {qm1,..qmk }Xét a; pmi = (qmi, a) ; pmj = (qmj, a)Nếu  a  để pmi và pmj phân biệt (bởi xâu ): qmi và qmj phân biệt (bởi xâu a)Nếu  a  pmi và pmj không phân biệt ( xâu ) qmi và qmj không phân biệt ( xâu a) Thuật toán dừng khi không tạo thêm nhóm3. Ô tô mát hữu hạn37Ví dụ3. Ô tô mát hữu hạnaq0q3aq2q1aq5aq4aabbq2q0q1q3bbaaaa38Xây dựng OHK từ biểu thức chính quySử dụng biểu thức chính quy mô tả NNCQTrong chương trình dịch, mô tả từ vựngVí dụ: Tên : a(a+b)* //a chữ cái, b: chữ số Số thực tĩnh: .b+| b+ . b+ //b: Chữ sốNgôn ngữ chính quy được đoán nhận bởi FACần xây dựng FA đoán nhận ngôn ngữ được mô tả bởi các biểu thức chính quy3. Ô tô mát hữu hạn39Thuật toán : Là btcq ứng với FA3. Ô tô mát hữu hạn : Là btcq ứng với FAa: Là btcq ứng với FAq0q0q0qa40Thuật toán3. Ô tô mát hữu hạnr Là btcq ứng với FA Mrq0FMrq0FMss Là btcq ứng với FA Msr + sq0FMrq0FMsq’0r.sq0FMrq0FMsr*q0FMrfq’041Ví dụXây dựng DFA đoán nhận NNCQ được biểu diễn bởi btcq (0+1)*0113. Ô tô mát hữu hạnq0q4q1q201011q31010042Thuật toán đoán nhận xâu của OHĐPhương pháp phân tích bảngDựa trên giải thuật tổng quát để đoán nhận DFAƯu điểm: Chương trình độc lập với DFADễ biến đổi, không cần sửa lại chương trìnhNhược điểm: Khó khăn trong lập bảngKích thước bảng lớnPhương pháp diễn giảiThực hiện như diễn giải sơ đồDễ viết, nhưng c\trình gắn với đồ thị dich chuyểnĐược sử dụng để xây dựng bộ phân tích từ vựng3. Ô tô mát hữu hạn43Chương 2: Phân tích từ vựngNhiệm vụ của bộ phân tích từ vựngBiểu thức chính quyÔ tô mát hữu hạnPhân tích từ vựng của ngôn ngữ PL/044Các từ tố của PL/0 mở rộngSố nguyênĐịnh danhTừ khóa: begin, end, if, then, while, do, call, const, var, procedure, program, else, for, toDấ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ữ PL/0 mở rộng45Ô-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ữ PL/0 mở rộng46Xâ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ữ PL/0 mở rộng47Xâ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ữ PL/0 mở rộng48Nhậ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ữ PL/0 mở rộngBEGIN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 ứng49