Giáo trình Xây dựng chương trình dịch - Chương III: Phân tích từ vựng

Nội dung text: Giáo trình Xây dựng chương trình dịch - Chương III: Phân tích từ vựng

1. CHƯƠNG III PHÂN TÍCH TỪ VỰNG Nội dung chính: Chương này trình bày các kỹ thuật xác định và cài đặt bộ phân tích từ vựng. Kỹ thuật đơn giản để xây dựng một bộ phân tích từ vựng là xây dựng các lược đồ - automata hữu hạn xác định (Deterministic Finite Automata - DFA) hoặc không xác định (Nondeterministic Finite Automata - NFA) – mô tả cấu trúc của các thẻ từ (token) của ngôn ngữ nguồn và sau đó dịch “thủ công” chúng sang chương trình nhận dạng các token. Một kỹ thuật khác nhằm tạo ra bộ phân tích từ vựng là sử dụng Lex – ngôn ngữ hành động theo mẫu (pattern). Trước tiên, người thiết kế trình biên dịch phải mô tả các mẫu được xác định bằng các biểu thức chính quy, sau đó sử dụng trình biên dịch của Lex để tự động tạo ra một bộ định dạng automata hữu hạn hiệu quả (bộ phân tích từ vựng). Các mô tả và cách thức hoạt động chi tiết của công cụ Lex được trình bày rõ hơn trong phần phụ lục A. Mục tiêu cần đạt: Sau khi học xong chương này, sinh viên phải nắm được các kỹ thuật tạo ra bộ phân tích từ vựng. Cụ thể, • Xây dựng các lược đồ cho các biểu thức chính quy mô tả ngôn ngữ cần được viết trình biên dịch. Sau đó chuyển đổi chúng sang một chương trình phân tích từ vựng. • Sử dụng công cụ có sẵn Lex để sinh ra bộ phân tích từ vựng. Kiến thức cơ bản: Sinh viên phải có các kiến thức về: • DFA và NFA. Các automata hữu hạn xác định và không xác định này được sử dụng để nhận dạng chính xác ngôn ngữ mà các biểu thức chính quy có thể biểu diễn. • Cách chuyển đổi từ NFA sang DFA nhằm làm đơn giản hóa quá trình cài đặt bộ phân tích từ vựng. Tài liệu tham khảo: [1] Automata and Formal Language. An Introduction – Dean Kelley – Prentice Hall, Englewood Cliffs, New Jersey 07632. [2] Compilers : Principles, Technique and Tools - Alfred V.Aho, Jeffrey D.Ullman - Addison - Wesley Publishing Company, 1986. [3] Compiler Design – Reinhard Wilhelm, Dieter Maurer - Addison - Wesley Publishing Company, 1996. [4] Design of Compilers : Techniques of Programming Language Translation - Karen A. Lemone - CRC Press, Inc, 1992. [5] Modern Compiler Implementation in C - Andrew W. Appel - Cambridge University Press, 1997. 48
2. Token Trị từ vựng minh họa Mô tả của mẫu từ vựng const const const if if if relation , >, >= hoặc > hoặc >= id pi, count, d2 Mở đầu là chữ cái theo sau là chữ cái, chữ số num 3.1416, 0, 5 Bất kỳ hằng số nào literal “ hello ” Mọi chữ cái nằm giữa “ và “ ngoại trừ “ Hình 3.2 - Các ví dụ về token 3. Thuộc tính của token Khi có nhiều mẫu từ vựng khớp với một trị từ vựng, bộ phân tích từ vựng trong trường hợp này phải cung cấp thêm một số thông tin khác cho các bước biên dịch sau đó. Do đó đối với mỗi token, bộ phân tích từ vựng sẽ đưa thông tin về các token vào các thuộc tính đi kèm của chúng. Các token có ảnh hưởng đến các quyết định phân tích cú pháp; các thuộc tính ảnh hưởng đến việc phiên dịch các thẻ từ. Token kết hợp với thuộc tính của nó tạo thành một bộ . Ví dụ 3.1: Token và giá trị thuộc tính đi kèm của câu lệnh Fortran : E = M * C 2 đưọc viết như một dãy các bộ sau: Chú ý rằng một số bộ không cần giá trị thuộc tính, thành phần đầu tiên là đủ để nhận dạng trị từ vựng. 4. Lỗi từ vựng Chỉ một số ít lỗi được phát hiện tại bước phân tích từ vựng, bởi vì bộ phân tích từ vựng có nhiều cách nhìn nhận chương trình nguồn. Ví dụ chuỗi fi được nhìn thấy lần đầu tiên trong một chương trình C với ngữ cảnh : fi ( a == f (x)) Bộ phân tích từ vựng không thể biết đây là lỗi không viết đúng từ khóa if hay một danh biểu chưa được khai báo. Vì fi là một danh biểu hợp lệ nên bộ phân tích từ vựng phải trả về một token và để một giai đoạn khác sau đó xác định lỗi. Tuy nhiên, trong một vài tình huống phải khắc phục lỗi để phân tích tiếp. Chiến lược đơn giản nhất là "phương thức hoảng sợ" (panic mode): Các ký tự tiếp theo sẽ được xóa ra khỏi chuỗi nhập còn lại 50
3. Phương pháp cặp bộ đệm này thường họat động rất tốt nhưng khi đó số lượng ký tự đọc trước bị giới hạn và trong một số trường hợp nó có thể không nhận dạng được token khi con trỏ p2 phải vượt qua một khoảng cách lớn hơn chiều dài vùng đệm. Giải thuật hình thức cho họat động của con trỏ p2 trong bộ đệm : if p2 ở cuối nửa đầu then begin Ðọc vào nửa cuối; p2 := p2 + 1; end else if p2 ở cuối của nửa cuối then begin Ðọc vào nửa đầu; Dời p2 về đầu bộ đệm ; end else p2 := p2 + 1 2. Khóa cầm canh (Sentinel) Phương pháp cặp bộ đệm đòi hỏi mỗi lần di chuyển p2 đều phải kiểm tra xem có phải đã hết một nửa buffer chưa nên kém hiệu quả vì phải hai lần kiểm tra. Ðể khắc phục điều này, mỗi lần chỉ đọc N-1 ký tự vào mỗi nửa buffer còn ký tự thứ N là một ký tự đặc biệt, thường là eof. Như vậy chúng ta đã rút ngắn một lần kiểm tra. E = M * eof C * * 2 eof p1 p2 Hình 3.4 - Khóa cầm canh eof tại cuối mỗi vùng đệm Giải thuật hình thức cho họat động của con trỏ p2 trong bộ đệm : p2 := p2 + 1; if p2↑ = eof then begin if p2 ở cuối của nửa đầu then begin Ðọc vào nửa cuối; p2 := p2 + 1; end else if p2 ở cuối của nửa sau then 52
4. Biểu thức chính quy được xây dựng trên một tập hợp các luật xác định. Mỗi biểu thức chính quy r đặc tả một ngôn ngữ L(r). Sau đây là các luật xác định biểu thức chính quy trên tập Alphabet ∑. 1. ε là một biểu thức chính quy đặc tả cho một chuỗi rỗng {ε }. 2. Nếu a ∈ ∑ thì a là biểu thức chính quy r đặc tả tập hợp các chuỗi {a} 3. Giả sử r và s là các biểu thức chính quy đặc tả các ngôn ngữ L(r) và L(s) ta có: a. (r) | (s) là một biểu thức chính quy đặc tả L(r) ∪ L(s) b. (r) (s) là một biểu thức chính quy đặc tả L(r)L(s). c. (r)* là một biểu thức chính quy đặc tả (L(r))* Quy ước: Toán tử bao đóng * có độ ưu tiên cao nhất và kết hợp trái. Toán tử ghép có độ ưu tiên thứ hai và kết hợp trái. Toán tử hợp | có độ ưu tiên thấp nhất và kết hợp trái. Ví dụ 3.3: Cho ∑ = { a, b} 1. Biểu thức chính quy a | b đặc tả {a, b} 2. Biểu thức chính quy (a | b) (a | b) đặc tả tập hợp {aa, ab, ba, bb}.Tập hợp này có thể được đặc tả bởi biểu thức chính quy tương đương sau: aa | ab | ba | bb. 3. Biểu thức chính quy a* đặc tả { ε, a, aa, aaa, } 4. Biểu thức chính quy (a | b)* đặc tả {(, a, b, aa,bb, }. Tập này có thể đặc tả bởi (a*b* )*. 5. Biểu thức chính quy a | a* b đặc tả {a, b, ab, aab, } Hai biểu thức chính quy cùng đặc tả một tập hợp ta nói rằng chúng tương đương và viết r = s. 4. Các tính chất đại số của biểu thức chính quy Biểu thức chính quy cũng tuân theo một số luật đại số và có thể dùng các luật này để biến đổi biểu thức thành những dạng tương đương. Bảng sau trình bày một số luật đại số cho các biểu thức chính quy r, s và t. Tính chất Mô tả r | s = s | r | có tính chất giao hoán r | (s | t) = (r | s ) | t | có tính chất kết hợp (rs) t = r (st) Phép ghép có tính chất kết hợp r (s | t) = rs | rt Phép ghép phân phối đối với phép | (s | t) r = sr | tr εr = r ε là phần tử đơn vị của phép ghép 54
5. 3. Lớp ký tự [abc] = a | b | c [a - z] = a | b | | z Sử dụng lớp ký hiệu chúng ta có thể mô tả danh biểu như là một chuỗi sinh ra bởi biểu thức chính quy : [A - Z a - z] [A - Z a - z 0 - 9]* IV. NHẬN DẠNG TOKEN Trong suốt phần này, chúng ta sẽ dùng ngôn ngữ được tạo ra bởi văn phạm dưới đây làm thí dụ minh họa : stmt Æ if expr then stmt | if expr then stmt else stmt | ε expr Æ term relop term | term term Æ id | num Trong đó các ký hiệu kết thúc if, then, else, relop, id, num được cho bởi định nghĩa chính quy sau: if Æ if then Æ then else Æ else relop Æ | > | >= id Æ letter (letter | digit) * num Æ digit + ( . digit +) ? (E (+ | -) ? digit +) ? Ðịnh nghĩa chính quy của các khoảng trắng ws (white space) delim Æ blank | tab | newline ws Æ delim+ Mục đích của chúng ta là xây dựng một bộ phân tích từ vựng có thể định vị được từ tố cho các token kế tiếp trong vùng đệm và tạo ra output là một cặp token thích hợp và giá trị thuộc tính của nó bằng cách dùng mẫu biểu thức chính quy cho các token như sau: Biểu thức chính quy Token Trị thuộc tính ws - - if if - then then - 56
6. letter or digit start letter other * 9 10 11 return( gettoken(), install_id() ) Hình 3.8 - Sơ đồ dịch cho các danh biểu và từ khóa Một kỹ thuật đơn giản để tách từ khóa ra khỏi các danh biểu là khởi tạo bảng ký hiệu lưu trữ thông tin về danh biểu một cách thích hợp. Ðối với các token cần nhận dạng trong văn phạm này, chúng ta cần nhập các chuỗi if, then và else vào bảng ký hiệu trước khi đọc các ký hiệu trong bộ đệm nguyên liệu. Ðồng thời ghi chú trong bảng ký hiệu để trả về token đó khi một trong các chuỗi này được nhận ra. Sử dụng các hàm gettoken( ) và install_id( ) tương ứng để nhận token và các thuộc tính trả về. Sơ đồ dịch nhận dạng token num: Một số vấn đề sẽ nảy sinh khi chúng ta xây dựng bộ nhận dạng cho các số không dấu. Trị từ vựng cho một token num phải là trị từ vựng dài nhất có thể được. Do đó, việc thử nhận dạng số trên các sơ đồ dịch phải theo thứ tự từ sơ đồ nhận dạng số dài nhất. digit digit digit start digit • digit E + or - digit other * 12 13 14 15 16 17 18 19 E digit digit digit start digit digit other * 20 21 • 22 23 24 digit start digit other * 25 26 27 Hình 3.9 - Sơ đồ dịch cho các số không dấu trong Pascal Có nhiều cách để tránh các đối sánh dư thừa trong các sơ đồ dịch trên. Một cách là viết lại các sơ đồ dịch bằng cách tổ hợp chúng thành một - một công việc nói chung là không đơn giản lắm. Một cách khác là thay đổi cách đáp ứng với thất bại trong qua trình duyệt qua một sơ đồ. Phương pháp được sử dụng ở đây là cho phép ta vượt qua nhiều trạng thái kiểm nhận và quay trở lại trạng thái kiểm nhận cuối cùng đã đi qua khi thất bại xảy ra. Sơ đồ dịch nhận dạng khoảng trắng ws (white space): Việc xử lý các khoảng trắng ws không hoàn toàn giống như các mẫu nói trên bởi vì không có gì để trả về cho bộ phân tích cú pháp khi tìm thấy các khoảng trắng trong 58
7. { while (1) { switch (state) { case 0 : c = nextchar ( ) ; / * c là ký hiệu đọc trước */ if ( c = = blank || c = = tab || c = = newline ) { state = 0; lexeme_beginning ++ ; / * dịch con trỏ đến đầu trị từ vựng */ } else if (c = = ‘ ’) state = 6; else state = fail ( ) ; break ; . . . / * các trường hợp 1- 8 ở đây */ [ case 9 : c = nextchar ( ) ; if (isletter (c)) state=10; else state = fail ( ) ; break ; case 10 : c = nextchar ( ) ; if (isletter (c)) state=10; else if (isdigit(c)) state = 10 ; else state = 11 ; break ; case 11 : retract (1) ; install_id ( ) ; return (gettoken ( )); . . . / * các trường hợp 12 - 24 ở đây */ case 25 : c = nextchar ( ) ; if (isdigit (c)) state=26; else state = fail ( ) ; break ; case 26 : c = nextchar ( ) ; if (isdigit (c)) state=26; else state = 27 ; break ; case 27 : retract (1) ; install_num ( ) ; return (NUM); 60
8. p2 {action 2 } . . . pn {action n } Trong đó pi là các biểu thức chính quy, action i là đoạn chương trình mô tả hành động của bộ phân tích từ vựng thực hiện khi pi tương ứng phù hợp với trị từ vựng. Trong lex các đoạn chương trình này được viết bằng C nhưng nói chung có thể viết bằng bất cứ ngôn ngữ nào. Các thủ tục phụ là sự cài đặt các hành động trong phần 2. Ví dụ 3.8: Sau đây trình bày một chương trình Lex nhận dạng các token của văn phạm đã nêu ở phần trước và trả về token được tìm thấy. %{ /* định nghĩa các hằng LT, LE, EQ, NE, GT, GE, IF, THEN, ELSE, ID, NUMBER, RELOP */ }% /* định nghĩa chính quy */ delim [\t\n] ws {delim}+ letter [A - Za - z] digit [0 - 9] id {letter}({letter}| {digit})* number {digit}+(\.{digit}+)?(E[+\-]?{digit}+)? %% {ws} {/* Không có action, không có return */} if {return(IF); } then {return(THEN); } else {return(ELSE); } {id} {yylval = install_id( ); return(ID) } {number} {yylval = install_num( ); return(NUMBER) } “ “ {yylval = NE; return(RELOP) } “> “ {yylval = GT; return(RELOP) } “>= “ {yylval = GE; return(RELOP) } %% 62
9. BÀI TẬP CHƯƠNG III 3.1. Xác định bộ chữ cái của các ngôn ngữ sau: a) Pascal b) C c) LISP 3.2. Hãy xác định các trị từ vựng có thể hình thành các token trong các đoạn chương trình sau: a) PASCAL function max (i, j :integer) : integer; { Trả về số nguyên lớn hơn trong 2 số i và j } begin i > j then max : = i else max : = j; end; b) C int max (i, j) int i, j; /* Trả về số nguyên lớn hơn trong 2 số i và j */ { return i > j ? i : j } c) FORTRAN 77 FUNCTION MAX (i, j) C Trả về số nguyên lớn hơn trong 2 số i và j IF ( I .GT. J) THEN MAX = I ELSE MAX = J END IF RETURN 64