Giáo trình Chương trình dịch - Nguyễn Thị Thanh Thoan

130 trang huongle 3110

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Chương trình dịch - Nguyễn Thị Thanh Thoan", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_chuong_trinh_dich_nguyen_thi_thanh_thoan.pdf

Nội dung text: Giáo trình Chương trình dịch - Nguyễn Thị Thanh Thoan

Mục tiêu: -Giới thiệu các khái niệm cơ bản, các giai đoạn chính khi biên dịch chương trình. -Giúp sinh viên hiểu cách cơ bản về cơ cấu và cách vạn hành trong các trình biên dịch của C, Pascal, nhờ đó sinh viên hiểu thấy đáo hơn về ngôn ngữ lập trình này và biết cách gỡ lỗi khi lập trình. Nguyễn Thị Thanh Thoan - Khoa CNTT
 Chương trình dịch (compiler) l{ một chương trình l{m nhiệm vụ đọc một chương trình được viết bằng một ngôn ngữ - ngôn ngữ nguồn (source language) - rồi dịch nó th{nh một chương trình tương đương ở một ngôn ngữ kh|c - ngôn ngữ đích (target languague).  Chương trình dịch ta còn gọi l{ trình biên dịch  Một phần quan trọng trong qu| trình dịch l{ ghi nhận lại c|c lỗi có trong chương trình nguồn để thông b|o lại cho người viết chương trình Nguyễn Thị Thanh Thoan - Khoa CNTT
Chương trình nguồn Trình biên dịch Chương trình đích (Source program) (Compiler) (Target program) Thông báo lỗi (Error messages ) Nguyễn Thị Thanh Thoan - Khoa CNTT
 Để tạo tra một chương trình đích có khả năng thực thi (excutable) thì ngo{i trình biên dịch ta phải có thêm một số chương trình kh|c nữa.  Sơ đồ sau mô tả ngữ cảnh của một trình biên dịch trong một hệ thống xử lí ngôn ngữ (language- processing system) Nguyễn Thị Thanh Thoan - Khoa CNTT
Chương trình nguồn khung (Skeletal source program) Bộ tiền xử lí (Preprocessor) Chương trình nguồn (Source program) Trình biên dịch (Compiler) Chương trình hợp ngữ đích (Target assembly program) Trình dịch hợp ngữ (Assembler) Mã máy tái khả định (Relocatable machine code) Thư viện/tập tin Trình tải/liên kết (Loader/link-editor) đối tượng (Library/object files) Mã máy tuyệt đối (Absolute machine code) Nguyễn Thị Thanh Thoan - Khoa CNTT
 Qu| trình biên dịch được chia th{nh nhiều giai đoạn  Qua mỗi giai đoạn chương trình nguồn được chuyển đổi từ dạng biểu n{y sang một dạng biểu diễn kh|c  Trong thục tế x}y dựng trình biên dịch, đôi khi c|c giai đoạn n{y được nhóm lại với nhau  C|c giai doạn biên dịch được minh hoạ trong hình vẽ dưới đ}y Nguyễn Thị Thanh Thoan - Khoa CNTT
Chương trình nguồn (Source program) Phân tích từ vựng (Lexical analyzer) Phân tích cú pháp (Syntax analyzer) Phân tích ngữ nghĩa (Semantic analyzer) Quản lí bảng kí tự Quản lí lỗi (Symbol-table manager) (Error handler) Sinh mã trung gian (Intermediate code generator) Tối ưu mã (Code optimizer) Sinh mã (Code generator) Nguyễn Thị Thanh Thoan - Khoa CNTT Chương trình đích (Target program)
 Giai đoạn ph}n tích từ vựng sẽ đọc chương trình nguồn từ tr|i sang phải (linear analysis/scanning) để t|ch ra thành các mã thông báo (token)  Trong qu| trình ph}n tích từ vựng c|c khoảng trắng (blank) sẽ bị bỏ qua. Nguyễn Thị Thanh Thoan - Khoa CNTT
 Ví dụ : Qu| trình ph}n tích từ vựng cho c}u lệnh g|n position := initial + rate * 60 sẽ t|ch th{nh c|c token như sau: 1. Định danh (identifier) position 2. Ký hiệu phép g|n := 3. Định danh initial 4. Ký hiệu phép cộng + 5. Định danh rate 6. Ký hiệu phép nh}n * 7. Số 60 Nguyễn Thị Thanh Thoan - Khoa CNTT
 Giai đoạn ph}n tích cú ph|p thực hiện công việc nhóm c|c token của chương trình nguồn th{nh c|c cụm từ văn phạm (grammatical phrase)  Thông thường c|c cụm từ văn phạm n{y được biểu diễn bằng c}y ph}n tích cú ph|p (parse tree) với : - Ngôn ngữ được định nghĩa bởi c|c luật sinh (production) - Ph}n tích cú ph|p dựa v{o luật sinh để x}y dựng c}y phân tích cú pháp. Nguyễn Thị Thanh Thoan - Khoa CNTT
 Ví dụ: Giả sử ngôn ngữ định nghĩa c}u lệnh g|n bởi c|c luật sinh sau : assig stmt id := expr expr expr + expr | expr * expr | (expr) | id | number  Lệnh g|n position := initial + rate * 60 được biểu diễn bằng parse tree như sau: Nguyễn Thị Thanh Thoan - Khoa CNTT
assig stmt | := id Expr | | position + Expr | Expr id | | * initial Expr Expr | | id Number | | rate 60 positionNguyễn Thị:= Thanh initial Thoan - Khoa+ rateCNTT * 60
 Cấu trúc ph}n cấp của một chương trình thường được diễn tả bởi quy luật đệ qui Ví dụ: Định nghĩa đệ qui một biểu thức số học như sau 1) Định danh (identifier/id) l{ một biểu thức (expression/expr) 2) Số (number) l{ một biểu thức. 3) Nếu expr1 v{ expr2 l{ c|c biểu thức thì: expr1 + expr2 expr1 * expr2 (expr1) cũng l{ những biểu thức. Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ: Nhiều ngôn ngữ lập trình định nghĩa c|c c}u lệnh (statement) theo c|ch như sau : 1) Nếu id1 l{ một định danh v{ expr2 l{ một biểu thức thì id1 := expr2 l{ một lệnh (stmt). 2) Nếu expr1 l{ một biểu thức v{ stmt2 l{ một lệnh thì while (expr1) do stmt2 If (expr1) then stmt2 đều l{ c|c lệnh. Nguyễn Thị Thanh Thoan - Khoa CNTT
 Giai đoạn ph}n tích ngữ nghĩa sẽ thực hiện việc kiểm tra xem chương trình nguồn có chứa lỗi về ngữ nghĩa hay không  Tập hợp thông tin về c|c kiểu dữ liệu cho giai đoạn sinh m~ về sau  Sử dụng cấu trúc ph}n cấp của giai đoạn ph}n tích cú ph|p để x|c định c|c to|n tử, to|n hạng của c|c biểu thức v{ c}u lệnh  Một phần quan trọng trong giai đoạn ph}n tích ngữ nghĩa l{ kiểm tra kiểu (type checking) v{ ép chuyển đổi kiểu Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ: Trong c}u lệnh position := initial + rate * 60 Giả sử c|c biến rate, initial v{ position được khai b|o l{ real, 60 l{ số integer vì vậy trình biên dịch sẽ đổi số nguyên 60 th{nh số thực 60.0 bằng h{m inttoreal := := position + position + initial initial * * rate 60 rate inttoreal Nguyễn Thị Thanh Thoan - Khoa CNTT 60
 Sau khi ph}n tích cấu trúc v{ ngữ nghĩa, một số trình biên dịch sẽ tạo ra một dạng biểu diễn trung gian của chương trình nguồn  M~ trung gian có 2 đặc tính quan trọng: Dễ tạo v{ dễ d{ng chuyển đổi th{nh chương trình đích  M~ trung gian có c|ch biểu diễn. Thông thường người ta sử dụng dạng "m~ m|y 3 địa chỉ" (three-address code), tương tự như dạng hợp ngữ cho một m|y m{ trong đó mỗi vị trí bộ nhớ có thể đóng vai trò như một thanh ghi. Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ: Lệnh position := initial + rate * 60 khi chuyển sang dạng m~ trung gian three-address code có dạng: temp1 := inttoreal (60) temp2 := id3 * temp1 temp3 := id2 + temp2 id1 := temp3  Ta dùng id1, id2, id3 thay thế cho position, initial v{ rate để nhấn mạnh rằng tên của một nhận dạng sẽ bị thay đổi khi ta biên dịch chương trình Nguyễn Thị Thanh Thoan - Khoa CNTT
 Giai đoạn tối ưu m~ cố gắng tối ưu m~ trung gian để thu được m~ m|y thực hiện nhanh hơn Ví dụ: M~ trung gian nêu trên có thể tối ưu th{nh: temp1 := id3 * 60.0 id1 := id2 + temp1 Nguyễn Thị Thanh Thoan - Khoa CNTT
 Giai đoạn cuối cùng của biên dịch l{ sinh m~ đích, thường l{ m~ m|y hoặc m~ hợp ngữ.  Vị trí c|c vùng nhớ g|n cho c|c biến được chương trình sử dụng.  Sau đó, c|c lệnh trung gian được dịch lần lượt th{nh chuỗi c|c chỉ thị m~ m|y. Vấn đề quyết định l{ việc g|n c|c biến cho c|c thanh ghi. Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ: Sử dụng c|c thanh ghi (chẳng hạn R1, R2) cho việc sinh m~ đích như sau: MOVF id3, R2 MULF #60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1 Nguyễn Thị Thanh Thoan - Khoa CNTT
 Một nhiệm vụ quan trọng của trình biên dịch l{ ghi lại c|c định danh được sử dụng trong chương trình nguồn v{ thu thập c|c thông tin về c|c thuộc tính kh|c nhau của mỗi định danh  C|c thuộc tính cung cấp thông tin về vị trí bộ nhớ được cấp ph|t cho một định danh, kiểu v{ phạm vi của định danh  Nếu định danh l{ tên của một thủ tục thì thuộc tính l{ c|c thông tin về số lượng v{ kiểu của c|c đối số, phương ph|p truyền đối số v{ kiểu trả về của thủ tục (nếu có) Nguyễn Thị Thanh Thoan - Khoa CNTT
 Bảng ký hiệu (symbol table) l{ một cấu trúc dữ liệu m{ mỗi phần tử l{ một bản ghi dùng để lưu trữ một định danh, c|c trường l{ c|c thuộc tính của định danh  Trong qu| trình ph}n tích từ vựng, tên c|c định danh được tìm thấy v{ nó được đưa v{o bảng ký hiệu nhưng thường thì c|c thuộc tính của nó chưa x|c định được trong giai đoạn n{y  C|c thuộc tính kh|c của c|c định danh sẽ được bổ sung trong c|c giai đoạn biên dịch tiếp theo Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ: Trong Pascal c}u lệnh khai b|o biến Var position, initial, rate: real; Sau khi ph}n tích từ vựng bảng quản lí kí tự có dạng như sau: SYMBOL TABLE 1 position 2 initial 3 rate 4 Nguyễn Thị Thanh Thoan - Khoa CNTT
 Mỗi giai đoạn biên dịch có thể gặp nhiều lỗi, ví dụ:  Giai đoạn ph}n tích từ vựng gặp lỗi khi c|c ký tự không thể ghép th{nh một token.  Giai đoạn ph}n tích cú ph|p gặp lỗi khi c|c token không thể kết hợp với nhau theo đúng cấu trúc ngôn ngữ  Giai đoạn ph}n tích ngữ nghĩa gặp lỗi khi c|c to|n hạng có kiểu không đúng yêu cầu của phép to|n  Sau khi ph|t hiện ra lỗi, tùy thuộc v{o trình biên dịch m{ có c|c c|ch xử lý lỗi kh|c nhau: Qu| trình biên dịch có thể dừng lại hoặc tiếp tục Nguyễn Thị Thanh Thoan - Khoa CNTT
position := initial + rate * 60 Phân tích từ vựng id1 := id2 + id3 * 60 Phân tích cú pháp := id1 + id2 * id3 60 Nguyễn Thị Thanh Thoan - Khoa CNTT
Phân tích ngữ nghĩa := id1 + id2 * id3 Inttoreal | 60 Sinh mã trung gian temp1 := inttoreal (60) temp2 := id3 * temp1 temp3 := id2 + temp2 id1 := temp3 Nguyễn Thị Thanh Thoan - Khoa CNTT
Tối ưu mã temp1 := id3 * 60.0 id1 := id2 + temp1 Sinh mã MOVF id3, R2 MULF #60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1 Nguyễn Thị Thanh Thoan - Khoa CNTT
Mục tiêu: Nắm được vai trò của giai đoạn ph}n tích từ vựng, sử dụng c|c kh|i niệm biểu thức chính qui (regular expression) và ô- tô- m|t hứu hạn (finite automata) trong việc biểu diễn v{ nhận biết ngôn ngữ Nguyễn Thị Thanh Thoan - Khoa CNTT
 Đ}y là giai đoạn đầu tiên của quá trình biên dịch  Nhiệm vụ chính: Đọc từng kí tự vào (input characters) từ chương trình nguồn và nhóm lại thành các token phục vụ cho giai đoạn phân tích cú pháp sau đó Nguyễn Thị Thanh Thoan - Khoa CNTT
 Ph}n tích từ vựng giúp cho c|c giai đoạn biên dịch tiếp theo dễ d{ng hơn, ví dụ: Giai đoạn ph}n tích cú ph|p không phải quan t}m đến c|c khoảng trắng cũng như c|c lời chú trích vì nó đ~ được loại bỏ khi khi ph}n tích từ vựng  Giảm đ|ng kể thời gian đọc chương trình nguồn v{ nhóm th{nh c|c token nhờ một số chương trình xử lí chuyên dụng Nguyễn Thị Thanh Thoan - Khoa CNTT
 Token: Một token l{ một tập hợp c|c x}u kí tự có một nghĩa x|c định, ví dụ identifier token l{ tập hợp tất cả c|c identifier. Token chính l{ c|c kí hiệu kết thúc (terminal) trong định nghĩa văn phạm của một ngôn ngữ, ví dụ: C|c từ kho|, định danh, to|n tử, hằng, x}u kí tự, dấu ngoặc đơn, dấu phẩy, dấu chấm phẩy  Pattern: Pattern của một token l{ c|c qui tắc kết hợp c|c kí tự để tạo lên token đó  Lexeme: L{ một chuỗi c|c kí tự thoả m~n pattern của một token Nguyễn Thị Thanh Thoan - Khoa CNTT
 Bảng sau đưa ra c|c ví dụ về token, pattern v{ lexeme Token Lexeme Thông tin mô tả của pattern const const const if if if relation , >=, =, hoặc >= hoặc = hoặc <> id pi, count, d2 một kí tự, tiếp theo là các kí tự hoặc chữ số num 3.1416, 0, 6.02E2 bất kì hằng số nào literal "computer" các kí tự nằm giữa " và " ngoại trừ " Nguyễn Thị Thanh Thoan - Khoa CNTT
 X}u kí tự (string): L{ một chuỗi c|c kí tự từ một bảng chữ c|i. Kí hiệu x}u rỗng l{   Một số kh|i niệm liên quan đến x}u kí tự: Tiền tố (prefix), hậu tố (suffix), x}u con (substring), tiền tố thực sự (proper prefix)  Ngôn ngữ (language): L{ tập hợp c|c x}u kí tự được x}y dựng từ một bảng chữ c|i Nguyễn Thị Thanh Thoan - Khoa CNTT
 C|c phép to|n trên ngôn ngữ: Giả sử L v{ M l{ hai ngôn ngữ khi đó Hợp (union)của L v{ M: LM={s|s L hoặc s M } Ghép (concatenation) của L v{ M: LM = { st | s L và t M } i Bao đóng Kleen (kleene closure) L: L* = i=0 L (Ghép của 0 hoặc nhiều L) + i Bao đóng dương (positive closure) của L: L = i=1 L (Ghép của 1 hoặc nhiều L) Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ: L = {A, B, , Z, a, b, , z } và D = { 0, 1, , , 9 } 1. L  D l{ tập hợp c|c chữ c|i v{ chữ số 2. LD l{ tập hợp c|c x}u bao gồm một chữ c|i v{ một chữ số 3. L4 l{ tập hợp tất cả c|c x}u 4 chữ c|i 4. L * l{ t}p hợp tất cả c|c x}u của c|c chữ c|i bao gồm cả chuỗi rỗng 5. L(L  D)* l{ tập hợp tất cả c|c x}u mở đầu bằng một chữ c|i theo sau l{ chữ c|i hay chữ số 6. D+ l{ tập hợp tất cả c|c x}u gồm một hoặc nhiều chữ số Nguyễn Thị Thanh Thoan - Khoa CNTT
 Mỗi biểu thức chính qui (BTCQ) r dùng để đặc tả một ngôn ngữ L(r). Ví dụ: Trong pascal mọi identifier được đặc tả bởi biểu thức chính qui letter(letter|digit)*  Hai BTCQ r v{ s được gọi l{ tương đương (kí hiệu r=s) nếu chúng đặc tả chung một ngôn ngữ Ví dụ: (a|b)=(b|a)  Một BTCQ được x}y dựng từ những BTCQ đơn giản bằng c|ch sử dụng c|c luật Nguyễn Thị Thanh Thoan - Khoa CNTT
 Sau đ}y l{ c|c luật định nghĩa c|c BTCQ trên một bảng chữ c|i  1.  l{ một BTCQ đặc tả {} (tập hợp chứa x}u rỗng) 2. Nếu a  thì a l{ BTCQ đặc tả {a} 3. Giả sử r v{ s l{ c|c BTCQ đặc tả c|c ngôn ngữ L(r) v{ L(s), khi đó: a) (r)|(s) l{ một BTCQ đặc tả L(r)L(s) b) (r)(s) l{ một BTCQ đặc tả L(r)L(s) c) (r)* l{ một BTCQ đặc tả (L(r))* d) (r) l{ một BTCQ đặc tả L(r) Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ: Cho = { a, b}. 1. BTCQ a | b đặc tả {a, b} 2. BTCQ (a | b) (a | b) đặc tả {aa, ab, ba, bb}.Tập hợp n{y có thể được đặc tả bởi BTCQ tương đương sau: aa | ab | ba | bb 3. BTCQ a* đặc tả {, a, aa, aaa, } 4. BTCQ (a | b)* đặc tả {a, b, aa,bb, }. Tập hợp n{y có thể đặc tả bởi (a*b* )* 5. BTCQ a | a* b đặc tả {a, b, ab, aab, } Nguyễn Thị Thanh Thoan - Khoa CNTT
 Để thuận tiện về mặt kí hiệu, ta dùng định nghĩa chính qui (ĐNCQ) để đặt tên cho c|c BTCQ  Một ĐNCQ l{ một d~y c|c định nghĩa có dạng d1 r1 d2 r2 dn rn Trong đó di là các tên, ri l{ c|c BTCQ trên tập c|c kí hiệu {d1, d2, di-1} Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ: ĐNCQ của c|c định danh trong pascal l{ letter A | B | | Z | a | b | | z digit 0 | 1 | | 9 id letter (letter | digit)* Ví dụ: ĐNCQ của c|c số không dấu trong pascal như 3254, 23.243E5,16.264E-3 là digit 0 | 1 | | 9 digits digit digit* optional_fraction . digits | e optional_exponent ( E ( + | - | e ) digits) | e num digits optional_fraction optional_exponent Nguyễn Thị Thanh Thoan - Khoa CNTT
 C|c kí hiệu tắt được sử dụng trong c|c BTCQ +: Một hoặc nhiều ?: Không hoặc một  Ví dụ: ĐNCQ cho tập số không dấu được viết lại như sau digit 0 | 1 | | 9 digits digit + optional_fraction (. digits) ? optional_exponent ( E ( + | - ) ? digits) ? num digits optional_fraction optional_exponent  Sử dụng c|c tập kí tự [abc]=a | b | c, [a-z]=a | b | z ta có thể đặc tả c|c định danh bởi BTCQ [A - Z a - z] [A - Z a - z 0 - 9]* Nguyễn Thị Thanh Thoan - Khoa CNTT
 L{m thế n{o để nhận dạng được token? Ta sẽ xét 1 ví dụ mang tính chất minh hoạ Ví dụ: Cho ngữ ph|p (grammar) stmt if expr then stmt | if expr then stmt else stmt |  expr term relop term | term term id | num Nguyễn Thị Thanh Thoan - Khoa CNTT
 Trong đó c|c kí hiệu kết thúc (token) if, then, else, relop, id sinh ra tập c|c x}u kí tự theo c|c ĐNCQ sau: if if then then else else relop | > | >= id letter (letter | digit) * num digit + ( . digit +) ? (E (+ | -) ? digit +) ?  C|c kí tự khoảng trắng (loại bỏ khi ph}n tích từ vựng) được định nghĩa bởi ĐNCQ sau: delim blank | tab | newline ws delim+ Nguyễn Thị Thanh Thoan - Khoa CNTT
 Mục đích của lexical analyzer tạo ra output l{ c|c cặp Regular Expression Token Attribute-value ws - - if if - then then - else else - id id pointer to table entry num num pointer to table entry relop NE > relop GT >= Nguyễn Thị Thanh Thoanrelop - Khoa CNTT GE
 Sơ đồ chuyển tiếp (transition diagram): L{ bước trung gian minh hoạ tiến trình chuyển đổi trạng th|i khi bộ ph}n tích từ vựng đọc lần lượt từng kí tự  Ta phải x}y dựng c|c sơ đồ chuyển tiếp để nhận biết từng loại token  Một sơ đồ chuyển tiếp bao gồm c|c trạng th|i (states) được vẽ bằng hình tròn, có 1 trạng th|i bắt đầu (start state). C|c trạng th|i được nối với nhau bởi c|c mũi tên ta gọi l{ c|c cạnh (edges)  Trạng th|i được biểu diễn bởi vòng tròn kép l{ trạng th|i được chấp nhận (accepting state) thông b|o 1 token đ~ được nhận dạng Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ: Sơ đồ chuyển tiếp cho token c|c to|n tử quan hệ relop Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ: Sơ đồ chuyển tiếp cho token các identifier và keyword  Chú ý: - Các từ khoá là các từ được bảo vệ và được lưu trữ sẵn trong symbol-table - Thủ tục gettoken() tra cứu lexeme trong symbol-table nếu là 1 keyword thì token tương ứng được trả về còn ngược lại token id được trả về - Thủ tục install_id() tra cứu lexeme trong symbol-table nếu là 1 keyword thì trả lại giá trị 0, nếu là một biến đ~ có thì trả lại một con trỏ tới vị trí trong symbol-table. Nếu lexeme không có thì tạo một phần tử mới trong symbol-table và trả về con trỏ tới thành phần mới vừa được tạo Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ: Sơ đồ chuyển tiếp cho token c|c unsigned numbers trong pascal Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ: Sơ đồ chuyển tiếp cho token c|c ws Nguyễn Thị Thanh Thoan - Khoa CNTT
 Một số công cụ có sẵn cho phép x}y dựng một bộ ph}n tích từ vựng dựa trên c|c biểu thức chính qui  Một trong số những công cụ đó l{ Lex compiler (một công cụ có sẵn của Unix)  Sơ đồ sau chỉ rõ c|ch tạo một bộ ph}n tích từ vựng bằng c|ch sử dụng Lex Nguyễn Thị Thanh Thoan - Khoa CNTT
Nguyễn Thị Thanh Thoan - Khoa CNTT
 Một bộ nhận dạng ngôn ngữ (recognizer for a language) l{ một chương trình nhận đầu v{o l{ một x}u kí tự x, trả lời "Yes" nếu x thuộc ngôn ngữ v{ trả lời "No" nếu ngược lại  Ô- tô- m|t hữu hạn l{ một sơ đồ chuyển tiếp được kh|i qu|t ho|, đóng vai trò l{ recognizer cho c|c biểu thức chính qui  Một Ô- tô- m|t hữu hạn có thể l{ deterministic finite automata (DFA) hoặc nondeterministic finite automata (NFA) Nguyễn Thị Thanh Thoan - Khoa CNTT
 "Nondeterministic" nghĩa l{ khi một kí tự được đọc v{o thì sơ đồ chuyển tiếp có thể chuyển đến nhiều hơn một trạng th|i tiếp theo  Cả hai DFA v{ NFA đều có khả năng nhận dạng c|c biểu thức chính qui  DFA có thể nhận dạng nhanh hơn nhưng cũng có kích thước lớn hơn NFA tương đương Nguyễn Thị Thanh Thoan - Khoa CNTT
 Một NFA l{ một mô hình to|n học bao gồm: - Một tập hợp trạng th|i S - Một trạng th|i bắt đầu s0 S - Một tập hợp c|c trạng th|i chấp nhận (hoặc trạng th|i kết thúc) FS - Một tập hợp kí tự v{o của bảng chữ c|i  - Một h{m chuyển đổi trạng th|i move: S x ({}) S (Một phép chuyển đổi (sk, ) sj nghĩa l{ chuyển từ sk sang sj mặc dù không có kí tự n{o được đọc v{o)  NFA được biểu diễn trực tiếp bằng sơ đồ chuyển tiếp Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ: NFA nhận biết BTCQ (a|b)*abb được mô tả dưới đ}y trong đó tập S={0, 1, 2, 3}, ={a, b}, s0=0 v{ trạng th|i kết thúc l{ 3 (vòng tròn kép) a st 0 a 1 b 2 b 3  H{mar chuyển đổi trạng th|i theo bảng dưới đ}y t b Trạng Kí tự vào thái a b 0 {0, 1} {0} 1 - {2} Nguyễn2 Thị Thanh Thoan- - Khoa CNTT {3}
Ví dụ: NFA nhận biết biểu thức chính qui aa* | bb* a 1 a 2  st 0 b ar  t 3 b 4 Nguyễn Thị Thanh Thoan - Khoa CNTT
 DFA l{ một trường hợp đặc biệt của NFA, DFA có thêm c|c dặc diểm sau: - Không có chuyển đổi trạng th|i ứng với kí tự rỗng  - Từ một trạng th|i s khi có một kí tự x được đọc v{o, DFA sẽ chuyển sang một trạng th|i s' duy nhất Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ: DFA nhận biết BTCQ (a|b)*abb a b a st 0 1 2 3 a b b ar a t b Nguyễn Thị Thanh Thoan - Khoa CNTT
Mục tiêu: -Nắm được vai trò của giai đoạn ph}n tích cú ph|p - Văn phạm phi ngữ cảnh (context- free grammar),cách phân tích cú ph|p từ dưới lên- từ trên xuống (top-down and bottom-up parsing) -Bộ ph}n tích cú ph|p LR Nguyễn Thị Thanh Thoan - Khoa CNTT
 Đ}y l{ giai đoạn thứ 2 của qu| trình biên dịch  Nhiệm vụ chính: Nhận chuỗi c|c token từ bộ ph}n tích từ vựng v{ x|c định chuỗi đó có được sinh ra bởi văn phạm của ngôn ngữ nguồn không Par Sou Lexi Token ser Pars Rest Get rce cal e of next pro anal Sy tree front Nguyễn Thị Thanhtoke Thoan - Khoa CNTT gra yzer mbn end m ol tabl e
 C|c phương ph|p ph}n tích cú ph|p (PTCP) chia l{m hai loại: Ph}n tích từ trên xuống (top- down parsing) v{ ph}n tích từ dưới lên (bottom- up parsing)  Trong qu| trình biên dịch xuất hiện nhiều lỗi trong giai đoạn PTCP do đó bộ ph}n tích cú ph|p phải ph|t hiện v{ thông b|o lỗi chính x|c cho người lập trình đồng thơi không l{m chậm những chương trình được viết đúng Nguyễn Thị Thanh Thoan - Khoa CNTT
 Để định nghĩa cấu trúc của ngôn ngữ lập trình ta dùng văn phạm phi ngữ cảnh (Context-free grammars) hay gọi tắt l{ một văn phạm  Một văn phạm bao gồm: - C|c kí hiệu kết thúc (terminals): Chính là các token - C|c kí hiệu chưa kết thúc (nonterminals): Là các biến kí hiệu tập c|c x}u kí tự - C|c luật sinh (productions): X|c định c|ch thức hình th{nh c|c x}u từ c|c kí hiệu kết thúc v{ chưa kết thúc - Một kí tự bắt đầu (start symbol) Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ 3.1: Văn phạm sau định nghĩa c|c biểu thức số học đơn giản E E A E | (E) | -E | id A + | - | * | / |  Trong đó E, A l{ c|c kí tự chưa kết thúc (E còn l{ kí tự bắt đầu), c|c kí tự còn lại l{ c|c kí tự kết thúc Nguyễn Thị Thanh Thoan - Khoa CNTT
 Dẫn xuất (derivation): Ta nói A  nếu A  là một luật sinh ( đọc l{ dẫn xuất hoặc suy ra)  Nếu 1 2 n thì ta nói rằng 1 dẫn xuất n  Kí hiệu: * l{ dẫn xuất 0 bước, + l{ dẫn xuất 1 bước  Cho văn phạm G với kí tự bắt đầu l{ S, L(G) l{ ngôn ngữ được sinh bởi G. Mọi x}u trong L(G) chỉ chứa c|c kí hiệu kết thúc của G Nguyễn Thị Thanh Thoan - Khoa CNTT
 Ta nói một x}u w L(G) nếu v{ chỉ nếu S + w, w được gọi l{ một c}u (sentence) của văn phạm G  Một ngôn ngữ được sinh bởi văn phạm phi ngữ cảnh được gọi l{ ngôn ngữ phi ngữ cảnh (context- free language)  Hai văn phạm được gọi l{ tương đương nếu sinh ra cùng một ngôn ngữ  Nếu S * ( có thể chứa kí hiệu chưa kết thúc) thí ta nói l{ một dạng c}u (sentence form) của G. Một c}u l{ một dạng c}u không chứa kí hiệu chưa kết thúc Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ 3.2: Xâu –(id+id) l{ một c}u của văn phạm trong ví dụ 3.1 vì E -E -(E) -(E+E) -(id+E) (id+id)  Một dẫn xuất được gọi l{ tr|i nhất (leftmost) nếu tại mỗi bước kí hiệu chưa kết thúc ngo{i cùng bên tr|i được thay thế, kí hiệu lm. Nếu S *lm thì được gọi l{ dạng c}u tr|i  Tương tự ta có dẫn xuất phải nhất (rightmost) hay còn gọi l{ dẫn xuất chính tắc, kí hiệu rm Nguyễn Thị Thanh Thoan - Khoa CNTT
 C}y ph}n tích cú ph|p (parse tree) l{ dạng biểu diễn hình học của dẫn xuất. Ví dụ parse tree cho biểu thức –(id+id) là: E - E ( E ) E + E | | Nguyễnid Thị Thanh Thoan - Khoa CNTT id
 Tính mơ hồ của văn phạm (ambiguity): Một văn phạm sinh ra nhiều hơn một parse tree cho một c}u được gọi l{ văn phạm mơ hồ. Nói c|ch kh|c một văn phạm mơ hồ sẽ sinh ra nhiều hơn một dẫn xuất tr|i nhất hoặc dẫn xuất phải nhất cho cùng một c}u.  Loại bỏ sự mơ hồ của văn phạm: Ta xét ví dụ văn phạm sau Stmt if expr then stmt | if expr then stmt else stmt | other Nguyễn Thị Thanh Thoan - Khoa CNTT
 Văn phạm trên l{ mơ hồ vì với cùng một c}u lệnh "if E1 then if E2 then S1 else S2" sẽ có hai parse tree: Nguyễn Thị Thanh Thoan - Khoa CNTT
 Ðể loại bỏ sự mơ hồ n{y ta đưa ra qui tắc "Khớp mỗi else với một then chưa khớp gần nhất trước đó". Với qui tắc n{y, ta viết lại văn phạm trên như sau : Stmt matched_stmt | unmatched_stmt matched_stmt if expr then matched_stmt else matched_stmt | other unmatched_stmt if expr then Stmt | if expr then matched_stmt else unmatched_stmt Nguyễn Thị Thanh Thoan - Khoa CNTT
 Loại bỏ đệ qui tr|i: Một văn phạm được gọi l{ đệ qui tr|i (left recursion) nếu tồn tại một dẫn xuất có dạng A + A (A l{ 1 kí hiệu chưa kết thúc, l{ một x}u).  C|c phương ph|p ph}n tích từ trên xuống không thể xử lí văn phạm đệ qui tr|i, do đó cần phải biến đổi văn phạm để loại bỏ c|c đệ qui tr|i  Ðệ qui tr|i có hai loại : Loại trực tiếp: Có dạng A + A Loại gi|n tiếp: G}y ra do dẫn xuất của hai hoặc nhiều bước Nguyễn Thị Thanh Thoan - Khoa CNTT
 Với đệ qui tr|i trực tiếp: Ta nhóm c|c luật sinh thành A A 1 | A 2 | | A m | 1 | 2 | | n Thay luật sinh trên bởi c|c luật sinh sau: A 1A' | 2A' | | nA' A' 1A' | 2A' | | mA' |  Ví dụ 3.3: Thay luật sinh A A |  bởi A A' A' A' |  Nguyễn Thị Thanh Thoan - Khoa CNTT
 Với đệ qui tr|i gi|n tiếp: Ta dùng thuật to|n sau 1. Sắp xếp c|c ký hiệu không kết thúc theo thứ tự A1, A2, , An 2. for i:=1 to n do begin for j:=1 to i -1 do begin Thay luật sinh dạng Ai Aj bởi luật sinh Ai 1 | 2 | | k trong đó Aj 1 | 2 | | k l{ tất cả c|c luật sinh hiện tại end; Loại bỏ đệ qui tr|i trực tiếp trong số c|c luật sinh Ai end; Nguyễn Thị Thanh Thoan - Khoa CNTT
 Tạo ra nh}n tố tr|i (left factoring) l{ một phép biến đổi văn phạm rất có ích để có được một văn phạm thuận tiện cho việc ph}n tích dự đo|n  Ý tưởng cơ bản l{ khi không rõ luật sinh n{o trong hai luật sinh khả triển có thể dùng để khai triển một ký hiệu chưa kết thúc A, chúng ta có thể viết lại c|c A- luật sinh nhằm "ho~n" lại việc quyết định cho đến khi thấy đủ yếu tố cho một lựa chọn đúng. Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ 3.3: Ta có hai luật sinh stmt if expr then stmt else stmt | if expr then stmt Sau khi đọc token if, ta không thể ngay lập tức quyết định sẽ dùng luật sinh n{o để mở rộng stmt  C|ch tạo nh}n tố tr|i: Giả sử có luật sinh A 1 | 2 | | n |  ( l{ tiền tố chung d{i nhất của c|c luật sinh,  không bắt đầu bởi ) Luật sinh trên được biến đổi th{nh: A A' |  A' 1 | 2 | | n Nguyễn Thị Thanh Thoan - Khoa CNTT
 Ph}n tích cú ph|p (PTCP) từ trên xuống được xem như một cố gắng tìm kiếm một dẫn xuất tr|i nhất cho chuỗi nhập. Nó cũng có thể xem như một cố gắng x}y dựng c}y ph}n tích cú ph|p bắt đầu từ nút gốc v{ ph|t sinh dần xuống l|  PTCP từ trên xuống đơn giản hơn PTCP từ dưới lên nhưng bị giới hạn về mặt hiệu quả  Có một số kĩ thuật PTCP từ trên xuống như: PTCP đệ qui lùi, PTCP đo|n trước, PTCP đo|n trước đệ qui. Ta sẽ xét trường hợp PTCP đo|n trước đệ qui Nguyễn Thị Thanh Thoan - Khoa CNTT
 PTCP đo|n trước không đệ qui (nonrecursive predictive parsing) hoạt động theo mô hình sau: INPUT a + b $ X Predictiv OUTPUT Y e STA Z parsing CK $ Parsing programtable Nguyễn Thị Thanh Thoan - Khoa CNTT M
 INPUT l{ bộ đệm chứa chuỗi cần ph}n tích, kết thúc bởi ký hiệu $  STACK chứa một chuỗi c|c ký hiệu văn phạm với ký hiệu $ nằm ở đ|y STACK. Khởi đầu STACK chứa kí hiệu bắt đầu S trên đỉnh  Parsing table M l{ một mảng hai chiều dạng M[A,a], trong đó A l{ ký hiệu chưa kết thúc, a l{ ký hiệu kết thúc hoặc $.  Bộ ph}n tích cú ph|p được điều khiển bởi Predictive parsing program Nguyễn Thị Thanh Thoan - Khoa CNTT
 Predictive parsing program hoạt động như sau: Chương trình xét ký hiệu X trên đỉnh Stack v{ ký hiệu nhập hiện h{nh a 1. Nếu X = a = $ thì qu| trình PTCP kết thúc th{nh công 2. Nếu X = a $, đẩy X ra khỏi Stack v{ đọc ký hiệu nhập tiếp theo. 3. Nếu X l{ ký hiệu chưa kết thúc thì chương trình truy xuất đến phần tử M[X,a] trong Parsing table M: - Nếu M[X,a] l{ một luật sinh có dạng X UYV thì đẩy X ra khỏi đỉnh Stack v{ đẩy V, Y, U v{o Stack (với U trên đỉnh Stack), đồng thời bộ xuất ra OUTPUT luật sinh X UYV - Nếu M[X,a] = error, gọi chương trình phục hồi lỗi. Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ 3.4: Xét văn phạm E E+T | T T T*F | F F (E) | id Loại bỏ đệ qui tr|i ta thu được E TE' E' +TE' |  T FT' T' *FT' |  F (E) | id Giả sử x}u input nhập v{o l{ id+id*id Nguyễn Thị Thanh Thoan - Khoa CNTT
 Parsing table M cho văn phạm trên như sau Non- Input symbol termin al id + * ( ) $ E E TE' E TE' E' E' E'  E'  +TE' T T FT' T FT' T' T'  T' T'  T'  *FT' F F id F (E) Nguyễn Thị Thanh Thoan - Khoa CNTT
STACK INPUT OUTPUT $ E id + id * id $ $ E' T id + id * id $ E T E' $ E' T' F id + id * id $ T F T' $ E' T' id id + id * id $ F id $ E' T' + id * id $ $ E' + id * id $ T'  $ E' T + + id * id $ E' + T E' $ E' T id * id $ $ E' T' F id * id $ T F T' $ E' T' id id * id $ F id $ E' T' * id $ $ E' T' F * * id $ T' * F T' $ E' T' F id $ $ E' T' id id $ F id $ E' T' Nguyễn Thị Thanh Thoan - Khoa CNTT$ $ E' $ T'  $ $ E' 
 Hàm FIRST và FOLLOW: L{ c|c h{m x|c định c|c tập hợp cho phép x}y dựng bảng ph}n tích M v{ phục hồi lỗi  Nếu l{ một x}u thì FIRST( ) l{ tập hợp c|c ký hiệu kết thúc m{ nó bắt đầu một chuỗi dẫn xuất từ . Nếu *  thì  thuộc FIRST( )  Nếu A l{ một kí hiệu chưa kết thúc thì FOLLOW(A) l{ tập c|c kí hiệu kết thúc m{ nó xuất hiện ngay bên phải A trong một dạng c}u . Nếu S * A thì $ thuộc FOLLOW(A) Nguyễn Thị Thanh Thoan - Khoa CNTT
 Qui tắc tính c|c tập hợp FOLLOW 1. Đặt $ v{o FOLLOW(S) (S l{ kí hiệu bắt đầu) 2. Nếu A B thì mọi phần tử thuộc FIRST() ngoại trừ  đều thuộc FOLLOW(B) 3. Nếu A B hoặc A B và  *  thì mọi phần tử thuộc FOLLOW(A) đều thuộc FOLLOW(B) Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ 3.5: Xét văn phạm E TE' E' +TE' |  T FT' T' *FT' |  F (E) | id Khi đó: FIRST(E) = FIRST(T) = FIRST(F) = { (, id } FIRST(E') = {+,  } FIRST(T') = {*,  } FOLLOW(E) = FOLLOW(E') = { $, ) } FOLLOW(T) = FOLLOW(T') = { +, ), $ } FOLLOW(F) = {*,+, ), $ } Nguyễn Thị Thanh Thoan - Khoa CNTT
 Thuật giải x}y dựng Parsing table M của văn phạm G: 1. Với mỗi luật sinh A của văn phạm, thực hiện bước 2 v{ 3 2. Với mỗi ký hiệu kết thúc a FIRST( ), thêm A vào M[A,a] 3. Nếu  FIRST( ) thì đưa luật sinh A vào M[A,b] với mỗi ký hiệu kết thúc b FOLLOW(A). Nếu  FIRST( ) và $ FOLLOW(A) thì đưa luật sinh A vào M[A,$]. 4. Ô còn trống trong bảng tương ứng với lỗi (error). Nguyễn Thị Thanh Thoan - Khoa CNTT
 Giới thiệu một kiểu ph}n tích cú ph|p từ dưới lên tổng qu|t gọi l{ ph}n tích cú ph|p Shift –Reduce  Một phương ph|p tổng qu|t hơn của kỹ thuật Shift - Reduce l{ ph}n tích cú ph|p LR (LR parsing) sẽ được thảo luận  Shift –Reduce parsing sẽ cố gắng x}y dựng một parse tree cho một x}u nhập v{o từ nút l| lên nút gốc. Nói c|ch kh|c ta "reducing" từng bước x}u nhập v{o đến khi thu được kí hiệu bắt đầu của văn phạm Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ 3.6: Cho văn phạm : S a A B e A A b c | b B d Câu abbcde có thể thu gọn về S theo c|c bước sau: a b b c d e a A b c d e a A d e a A B e S Đảo ngược lại qu| trình trên ta thu được dẫn xuất phải nhất: S rm aABe rm aAde rm aAbcde rm abbcde Nguyễn Thị Thanh Thoan - Khoa CNTT
 Handles: Handle của một right-sentential form  là một luật sinh A , một x}u sao cho =  và S * rm A rm . Đôi khi ta còn gọi  l{ một handle, xâu  bên phải  chỉ chứa c|c kí hiệu kết thúc  Nếu một văn phạm l{ không mơ hồ thì với mỗi right- sentential form có duy nhất một handle của nó Ví dụ 3.7: Trong dẫn xuất S rm aABe rm aAde rm aAbcde rm abbcde c|c handle được gạch ch}n Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ 3.8: Xét văn phạm mơ hồ E E + E | E * E | (E) | id Với cùng một biểu thức id+id*id sẽ có hai dẫn xuất phải nhất (c|c handle được gạch ch}n). Cùng một right sentence form E+E*id3 trong trường hợp đầu id3 l{ handle còn trường hợp thứ 2 handle l{ E+E E rm E + E E rm E * E rm E + E * E rm E * id3 rm E + E * id3 rm E + E * id3 rm E + id2 * id3 rm E + id2 * id3 rm id1 + id2 * id3 rm id1 + id2 * id3 Nguyễn Thị Thanh Thoan - Khoa CNTT
 Biểu diễn stack của shift- reduce parsing STACK INPUT ACTION $ id1 + id2 * id3 shift $ id1 $ reduce by E id $ E + id2 * id3 $ shift $ E + + id2 * id3 $ shift $ E + id2 id2 * id3 $ reduce by E id $ E + E * id3 $ shift $ E + E * * id3 $ shift $ E + E id3 $ reduce by E id * id3 $ reduce by E E * $ E + E * E $ E $ E + E $ reduce by E E + Nguyễn Thị Thanh Thoan - Khoa CNTT $ E $ E accept
 LR(k) l{ một kỹ thuật ph}n tích cú ph|p từ dưới lên hiệu quả, có thể sử dụng để ph}n tích một lớp rộng c|c văn phạm phi ngữ cảnh. - L(Left-to-right): Duyệt chuỗi nhập từ tr|i sang phải - R(Rightmost derivation): X}y dựng chuỗi dẫn xuất phải nhất đảo ngược - k:Số lượng ký hiệu lookahead tại mỗi thời điểm, dùng để đưa ra quyết định ph}n tích. Khi không đề cập đến k, chúng ta hiểu ngầm l{ k = 1 Nguyễn Thị Thanh Thoan - Khoa CNTT
 Ưu điểm của LR: - Có thể nhận biết hầu như tất cả c|c ngôn ngữ lập trình được tạo ra bởi văn phạm phi ngữ cảnh - Phương ph|p ph}n tích cú ph|p LR l{ phương ph|p tổng qu|t của phương ph|p shift-reduce không quay lui - Lớp văn phạm có thể dùng phương ph|p LR l{ một lớp rộng lớn hơn lớp văn phạm có thể sử dụng phương ph|p dự đo|n - Có thể x|c định lỗi cú ph|p nhanh ngay trong khi duyệt dòng nhập từ tr|i sang phải  Nhược điểm của LR: - X}y dựng LR parser kh| phức tạp Nguyễn Thị Thanh Thoan - Khoa CNTT
 Mô hình của LR parser a a a $ INPUT 1 i n s m LR OUTPUT X m parsing s STA m-1 Xm-1 actionprogram goto CK Parsing table so Nguyễn Thị Thanh Thoan - Khoa CNTT
 STACK lưu chuỗi s0 X1 s1 X2 s2 Xm sm trong đó sm nằm trên đỉnh STACK một ký hiệu văn phạm, si l{ một trạng th|i tóm tắt thông tin chứa trong STACK bên dưới nó  Parsing table bao gồm 2 phần : H{m action và hàm goto - action[sm, ai] có thể có một trong 4 gi| trị : 1. shift s: Đẩy s, trong đó s l{ một trạng th|i 2. reduce: Thu gọn bằng luật sinh A  3. accept: Chấp nhận 4. error: B|o lỗi - goto lấy 2 tham số l{ một trạng th|i v{ một ký hiệu văn phạm, nó sinh ra một trạng th|i Nguyễn Thị Thanh Thoan - Khoa CNTT
 Cấu hình (configuration) của một bộ ph}n tích cú ph|p LR l{ một cặp th{nh phần (s0 X1 s1 X2 s2 Xm sm, ai ai+1 an $). Cấu hình biểu diễn right- sentential form X1 X2 Xmai ai+1 an  Sự thay đổi cấu hình theo h{m action như sau: - Nếu action[sm, ai] = shift s, cấu hình chuyển th{nh (s0 X1 s1 X2 s2 Xm sm ai s, ai+1 an $), trong đó s=action[sm, ai] - Nếu action[sm, ai] = reduce A , cấu hình chuyển th{nh (s0 X1 s1 X2 s2 Xm-r sm-r A s, ai ai+1 an $), trong đó s=goto[sm-r, A], r=||=|Xm-r+1 Xm| - Nếu action[sm, ai] = accept, quá trình phân tích thành công - Nếu action[sm, ai] = error, gọi thủ tục phục hồi lỗi Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ 3.9: Xét văn phạm cho các phép toán số học + và * (1) E E + T Stat Action Goto (2) E T e id + * ( ) $ E T F (3) T T * F 0 s5 S4 1 2 3 (4) T F 1 s6 acc (5) F (E) 2 r2 s7 r2 r2 (6) F id 3 r4 r4 r4 r4 4 s5 s4 8 2 3 Ý nghĩa : 5 r6 r6 r6 r6 si : shift si 6 s5 s4 9 3 rj : reduce by 7 s5 s4 10 production j acc: accept 8 s6 s11 blank: error 9 r1 s7 r1 r1 Nguyễn10 Thị Thanh Thoan r- 3Khoa CNTTr3 r3 r3 11 r5 r5 r5 r5
• Với chuỗi nhập id*id+id quá trình phân tích như sau: STACK INPUT ACTION (1) 0 id * id + id $ shift (2) 0 id 5 * id + id $ reduce by F id (3) 0 F 3 * id + id $ reduce by T F (4) 0 T 2 * id + id $ shift (5) 0 T 2 * 7 id + id $ shift (6) 0 T 2 * 7 id + id $ reduce by F id (7) 5 + id $ reduce by T T * F (8) 0 T 2 * 7 F + id $ reduce by E T (9) 10 + id $ shift (10) 0 T 2 id $ shift (11) 0 E 1 $ reduce by F id (12) 0 E 1 + 6 $ reduce by T F (13) 0 E 1 + 6 id 5 $ reduce by E E + T Nguyễn Thị Thanh Thoan - Khoa CNTT (14) 0 E 1 + 6 F $ accept 3 0 E 1 + 6 T 9 0 E 1
 Có 3 phương ph|p x}y dựng một bảng ph}n tích cú ph|p LR từ văn phạm l{ Simple LR (SLR), Canonical LR và Lookahead- LR (LALR), c|c phương ph|p kh|c nhau về tính hiệu quả cũng như tính dễ c{i đặt  Phương ph|p SLR, l{ phương ph|p yếu nhất nếu tính theo số lượng văn phạm có thể x}y dựng th{nh công, nhưng đ}y lại l{ phương ph|p dễ c{i đặt nhất  Một văn phạm có thể x}y dựng được SLR parser được gọi l{ một văn phạm SLR Nguyễn Thị Thanh Thoan - Khoa CNTT
 Một mục LR(0) (hoặc item) của một văn phạm G l{ một luật sinh của G với một dấu chấm tại vị trí n{o đó trong vế phải Ví dụ 3.10: Luật sinh A XYZ có 4 mục như sau: A .XYZ A X.YZ A XY.Z A XYZ.  Luật sinh A  chỉ tạo ra một mục A . Nguyễn Thị Thanh Thoan - Khoa CNTT
 Văn phạm tăng cường (Augmented Grammar): G l{ một văn phạm với ký hiệu bắt đầu S, thêm một ký hiệu bắt đầu mới S' v{ luật sinh S' S để được văn phạm mới G' gọi l{ văn phạm tăng cường  Phép to|n bao đóng (Closure): Giả sử I l{ một tập c|c mục của văn phạm G thì bao đóng closure(I) l{ tập c|c mục được x}y dựng từ I như sau: 1. Tất cả c|c mục của I được thêm v{o closure(I). 2. Nếu A .B closure(I) và B  l{ một luật sinh thì thêm B . v{o closure(I) nếu nó chưa có trong đó. Lặp lại bước n{y cho đến khi không thể thêm v{o closure(I) được nữa Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ 3.11: Xét văn phạm tăng cường E' E E E + T | T T T * F | F F (E) | id Nếu I= {E' · E} thì closure(I) bao gồm c|c mục sau: E' · E E · E + T E · T T · T * F T · F F · (E) F · id Nguyễn Thị Thanh Thoan - Khoa CNTT
 Phép to|n goto: Nếu I l{ một tập c|c mục v{ X l{ một ký hiệu văn phạm thì goto(I, X) l{ bao đóng của tập hợp c|c mục A X. sao cho A .X I  Cách tính goto(I, X): 1. Tạo một tập I' =  2. Nếu A .X I thì đưa A X. v{o I', tiếp tục qu| trình n{y cho đến khi xét hết tập I. 3. goto(I, X) = closure(I') Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ 3.12: Giả sử I = {E' E., E E . + T} Ta có I' = { E E + . T} goto (I, +) = closure(I') bao gồm c|c mục : E E + . T T . T * F T . F F . (E) F . id Nguyễn Thị Thanh Thoan - Khoa CNTT
 Giải thuật x}y dựng họ tập hợp c|c mục LR(0) (kí hiệu l{ C) của văn phạm G' procedure Item (G') begin C := {closure({ S' .S}) }; repeat For Với mỗi tập c|c mục I C v{ mỗi ký hiệu văn phạm X sao cho goto (I, X)  và goto(I, X) C thì thêm goto(I, X) vào C; until Không còn tập hợp mục n{o có thể thêm v{o C; end; Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ 3.13: X}y dựng họ tập hợp c|c mục trong ví dụ 3.11 closure({E' E}) E' · E goto (I0, F id · I0: E · E + T id) I5: E E + · T E · T goto (I1, T · T * F T · T * F +) I6: T · F T · F F · (E) F · (E) F · id F · id T T* · F E' E · F · (E) goto (I0, E E · + T goto (I2, F · id E) I1: E T · *) I7: F (E ·) T T · * F E E · + T goto (I0, T F · E E + T · T) I2: F (· E) goto (I4, E) I8: T T · * F E · E + T T T * F · goto E · T goto F (E) · (I0,F) I3: T · T * F (I6,T) I9: goto (I0, ( T · F goto ) I4: F · (E) (I7,F) I10: Nguyễn Thị Thanh Thoan - Khoa CNTT F · id goto (I8,) ) I11:
 X}y dựng SLR parsing table 1. X}y dựng họ tập hợp c|c mục của G': C = { I0, I1, , In } 2. Trạng th|i i được x}y dựng từ Ii .C|c action tương ứng trạng th|i i x|c định như sau: a) Nếu A .a Ii và goto (Ii, a) = Ij thì action[i, a] = "shift j", a l{ ký hiệu kết thúc b) Nếu A . Ii thì action[i, a] = "reduce (A )", với mọi a FOLLOW(A), A S' c) Nếu S' S · Ii thì action[i, $] = "accept". Nếu một action đụng độ được sinh ra bởi c|c luật trên, ta nói văn phạm không phải l{ SLR(1). Giải thuật thất bại 3. Nếu goto (Ii,A)=Ij thì goto [i, A] = j, A l{ kí hiệu chưa kết thúc 4. C|c ô không x|cNguyễn định Thị Thanh được Thoan - Khoabởi CNTT 2 v{ 3 đều l{ “error” 5. Trạng th|i khởi đầu của bộ ph}n tích cú ph|p được x}y dựng từ tập c|c mục chứa S’ · S
 LR chính tắc (canonical LR) l{ kĩ thuật chung nhất để x}y dựng LR parsing table cho một văn phạm  Một mục LR(1) (item) l{ một cặp [A ., a] trong đó A  l{ một luật sinh, a- l{ kí tự lookahead l{ một kí hiệu kết thúc hoặc $  Nếu   thì a không có ý nghĩa nhưng nếu = thì việc reduce theo luật A chỉ được thực hiện nếu kí tự đọc v{o tiếp theo l{ a Nguyễn Thị Thanh Thoan - Khoa CNTT
 Phép to|n bao đóng (Closure): Giả sử I l{ một tập c|c mục LR(1) của văn phạm G thì bao đóng closure(I) l{ tập c|c mục được x}y dựng từ I như sau: 1. Tất cả c|c mục của I được thêm v{o closure(I). 2. Nếu [A .B, a] closure(I), B  l{ một luật sinh và b FIRST(a) thì thêm [B ., b] vào closure(I) nếu nó chưa có trong đó. Lặp lại bước n{y cho đến khi không thể thêm v{o closure(I) được nữa  Phép to|n goto: Nếu I l{ một tập c|c mục v{ X l{ một ký hiệu văn phạm thì goto(I, X) l{ bao đóng của tập hợp c|c mục [A X., a] sao cho [A .X, a] I Nguyễn Thị Thanh Thoan - Khoa CNTT
 Giải thuật x}y dựng họ tập hợp c|c mục LR(1) (kí hiệu l{ C) của văn phạm G' procedure Item (G') begin C := {closure({[ S' .S, $]})}; repeat For Với mỗi tập c|c mục I C v{ mỗi ký hiệu văn phạm X sao cho goto (I, X)  và goto(I, X) C thì thêm goto(I, X) vào C; until Không còn tập hợp mục n{o có thể thêm v{o C; end; Nguyễn Thị Thanh Thoan - Khoa CNTT
Ví dụ 3.14: X}y dựng họ tập hợp c|c mục LR(1) cho văn phạm dưới đ}y S' S (1) S CC (2) C cC (3) C d closure({S' S}) S' · S, $ goto (I0, d C d ·, c/d I0: S · CC, $ ) I4: C · cC, c/d S CC ·, $ C · d, c/d goto (I2, S' S ·, $ C) I5: C c · C, $ goto (I0, C · cC, $ S) I1: S C ·C, $ goto (I2, C · d, $ C · cC, $ c) I6: goto (I0, C · d, $ C d ·, $ C) I2: C c ·C, c/d C cC ·, c/d C · cC, c/d goto (I2, Nguyễn Thị Thanh Thoan - Khoa CNTT C · d, c/d d) I7: C cC ·, $ goto (I0, c) I3: goto (I3, C) I8: goto (I6,C) I9:
 X}y dựng canonical LR parsing table 1. X}y dựng họ tập hợp c|c mục LR(1) của G': C = {I0, I1, , In } 2. Trạng th|i i được x}y dựng từ Ii .C|c action tương ứng trạng th|i i x|c định như sau: a) Nếu [A .a, b] Ii và goto (Ii, a) = Ij thì action[i, a] = "shift j", a l{ ký hiệu kết thúc b) Nếu [A ., a] Ii thì action[i, a] = "reduce (A .)", A S' c) Nếu [S' S ·, $] Ii thì action[i, $] = "accept". Nếu một action đụng độ được sinh ra bởi c|c luật trên, ta nói văn phạm không phải l{ LR(1). Giải thuật thất bại 3. Nếu goto (Ii,A)=Ij thì goto [i, A] = j, A l{ kí hiệu chưa kết thúc 4. C|c ô không x|c định được bởi 2 v{ 3 đều l{ “error” 5. Trạng th|i khởiNguyễn đầu Thị củaThanh Thoan bộ -ph}n Khoa CNTT tích cú ph|p được x}y dựng từ tập c|c mục chứa [S’ · S, $]
• Canonical LR parsing table cho văn phạm trong ví dụ 3.14 State Action Goto c d $ S C 0 s3 s4 1 2 1 acc 2 s6 s7 5 3 s3 s4 8 4 r3 r3 5 r1 6 s6 s7 9 7 r3 8 r2 r2 9 r2 Nguyễn Thị Thanh Thoan - Khoa CNTT
 LALR l{ phương ph|p canonical parsing trong đó c|c trạng th|i được nhóm lại với nhau nhờ đó bảng ph}n tich cấu trúc có kích thước nhỏ hơn (có thể so s|nh với SLR)  Hạt nh}n (core) của một tập hợp mục LR(1) có dạng {[A ., a]}, trong đó A  l{ một luật sinh v{ a l{ ký hiệu kết thúc có hạt nh}n (core) l{ tập hợp {A .}.  Trong họ tập hợp c|c mục LR(1) C = {I0, I1, , In} có thể có c|c tập hợp c|c mục có chung một hạt nh}n. Nguyễn Thị Thanh Thoan - Khoa CNTT
 X}y dựng LALR parsing table 1. X}y dựng họ tập hợp c|c mục LR(1) của G': C = {I0, I1, , In } 2. Nhóm c|c mục có cùng core trong C được C' = {J0, J1, , Jm } 3. Trạng th|i i được x}y dựng từ Ji .C|c action tương ứng trạng th|i i x|c định tương tự như canonical LR Nếu một action đụng độ được sinh ra bởi c|c luật trên, ta nói văn phạm không phải l{ LALR(1). Giải thuật thất bại 3. X}y dựng bảng goto : Giả sử J = I1 I2 .  Ik . Vì I1, I2, Ik có chung hạt nh}n nên goto (I1,X), goto (I2,X), , goto (Ik,X) cũng có chung hạt nh}n. Ðặt K bằng hợp tất cả c|c tập hợp có chung hạt nh}n với goto (I1,X) khi đó goto(J, X) =K. Nguyễn Thị Thanh Thoan - Khoa CNTT
• LALR parsing table cho văn phạm trong ví dụ 3.14 State Action Goto c d $ S C 0 s36 s47 1 2 1 acc 2 s36 s47 5 36 s36 s47 89 47 r3 r3 r3 5 r1 89 r2 r2 r2 Nguyễn Thị Thanh Thoan - Khoa CNTT
 Giống như Lex, Yacc (yet another compiler compiler) l{ c}u lệnh sẵn có của UNIX v{ l{ một công cụ hữu hiệu cho phép x}y dựng bộ ph}n tích cú ph|p một c|ch tự động  Yacc được tạo bởi S. C. Johnson v{o những năm đầu của thập kỉ 70  Yacc sử dụng phương ph|p LALR Nguyễn Thị Thanh Thoan - Khoa CNTT
Yacc Yacc y.tab.c specifi cation compil er y.tab.ctransl C a.out ate.y compil er inp a.out output ut Nguyễn Thị Thanh Thoan - Khoa CNTT
Mục tiêu: • Nắm được c|ch định nghĩa hệ thống kiểu trong c|c ngôn ngữ lập trình • C|ch kiểm tra kiểu trong qu| trình biên dịch Nguyễn Thị Thanh Thoan - Khoa CNTT
 Kiểu của một ngôn ngữ lập trình được kí hiệu bởi c|c biểu thức kiểu (type expression).  Biểu thức kiểu được định nghĩa như sau: 1. Kiểu cơ sở l{ một biểu thức kiểu: boolean, char, integer, real, type_error, void 2. Một tên kiểu l{ một biểu thức kiểu 3. Mỗi kiểu dữ liệu có cấu trúc l{ một biểu thức kiểu, c|c cấu trúc bao gồm: Nguyễn Thị Thanh Thoan - Khoa CNTT
a. Mảng (array): Nếu T l{ một biểu thức kiểu thì array(I, T) l{ một biểu thức kiểu. Một mảng có tập chỉ số I v{ c|c phần tử có kiểu T b. Tích (product): Nếu T1, T2 l{ biểu thức kiểu thì tích Đề- c|c T1* T2 l{ biểu thức kiểu c. Bản ghi (record): L{ cấu trúc bao gồm một bộ c|c tên trường, kiểu trường d. Con trỏ (pointer): Nếu T l{ một biểu thức kiểu thì pointer(T) l{ một biểu thức kiểu T e. Hàm (function): H{m l{ một |nh xạ c|c phần tử của tập x|c định (domain) D lên tập gi| trị (range) R. Một h{m l{ một biểu thức kiểu D R Nguyễn Thị Thanh Thoan - Khoa CNTT
 Trong phần n{y chúng ta mô tả một bộ kiểm tra kiểu cho một ngôn ngữ đơn giản trong đó kiểu của mỗi một định danh được khai b|o trước khi sử dụng  Bộ kiểm tra kiểu (type checker) l{ một lược đồ dịch, nó tổng hợp kiểu của mỗi biểu thức từ kiểu của c|c biểu thức con của nó Nguyễn Thị Thanh Thoan - Khoa CNTT
 Định nghĩa một ngôn ngữ đơn giản: Văn phạm sau sinh ra một chương trình, biểu diễn bởi một ký hiệu chưa kết thúc P chứa một chuỗi c|c khai b|o D v{ một biểu thức đơn giản E P D ; E D D ; D | id : T T char | integer | array[num] of T | T E literal | num | id | E mod E | E [E] | E  Ví dụ 5.1: Chương trình sau sinh bởi văn phạm trên key: integer; key mod 1999 Nguyễn Thị Thanh Thoan - Khoa CNTT
 Ta có lược đồ dịch để lưu trữ kiểu của một định danh P D ; E D D ; D D id : T {addtype(id.entry, T.type) } T char {T.type := char } T integer {T.type := integer } T T1 {T.type := pointer(T1.type) } T array[num] of T1 {T.type := array(1 num.val, T1.type) } Nguyễn Thị Thanh Thoan - Khoa CNTT
 Lược đồ dịch cho kiểm tra kiểu của biểu thức: E literal {E.type := char } E num {E.type := integer } E id {E.type := lookup(id.entry) } E E1 mod E2 {E.type := if E1.type = integer and E2.type = integer then integer else type_error } E E1[E2] {E.type := if E2.type =integer and E1.type = array(s,t) then t else type_error } E E1 { E.type := if E1.type = pointer(t) then t else type_error } Nguyễn Thị Thanh Thoan - Khoa CNTT
 C|c c}u lệnh cấu tạo lên ngôn ngữ không có gi| trị, do đó ta g|n cho chúng kiểu void  Lược đồ dịch cho kiểm tra kiểu của c|c lệnh: S id := E { S.type := if id.type = E.type then void else type_error } S if E then S1 {S.type := if E.type = boolean then S1.type else type_error } S while E do S1 {S.type := if E.type = boolean then S1.type else type_error } S S1 ; S2 {S.type := if S1.type = void and S2.type = void then void else type_error } Nguyễn Thị Thanh Thoan - Khoa CNTT
 Việc ghép một h{m với một đối (argument) có thể diễn đạt bởi luật sinh: E E ( E )  Lược đồ dịch kiểm tra kiểu cho một h{m: E E1 (E2) {E.type := if E2.type = s and E1.type = s -> t then t else type_error }  Nếu có nhiều đối có kiểu tương ứng T1, T2, , Tn được coi như một đối duy nhất có kiểu T1*T2* *Tn Nguyễn Thị Thanh Thoan - Khoa CNTT
 Xét biểu thức x + i trong đó x có kiểu real v{ i có kiểu integer. Trình biên dịch có thể thực hiện việc chuyển đổi kiểu để hai to|n hạng có cùng kiểu khi phép to|n cộng xảy ra  Bộ kiểm tra kiểu trong trình biên dịch có thể thêm c|c phép to|n biến đổi kiểu v{o trong biểu diễn trung gian của chương trình nguồn  Chẳng hạn ký hiệu hậu tố của x + i có thể là: x i inttoreal real+ (inttoreal đổi số nguyên i th{nh số thực, real+ thực hiện phép cộng c|c số thực) Nguyễn Thị Thanh Thoan - Khoa CNTT
 Ép kiểu (coercion): Việc chuyển một kiểu dữ liệu sang một kiểu kh|c được gọi l{ ẩn (implicit) nếu nó được l{m tự động bởi compiler v{ được gọi l{ hiện (explicit) nếu được giải quyết bởi người lập trình Ví dụ 5.2: H{m ord() trong pascal chuyển kiểu kí tự sang số nguyên, phép chuyển đổi l{ hiện Lệnh a:=b; trong đó a kiểu real, b kiểu integer khi thực hiện compiler sẽ thực hiện ép kiểu biến b sang kiểu real trước khi thực hiện lệnh g|n, phép chuyển đổi l{ ẩn Nguyễn Thị Thanh Thoan - Khoa CNTT