Bài giảng Chương trình dịch - Chương 2: Phân tích từ vựng

CHƯƠNG II

Phân tích từ vựng

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ữ

1

Vai trò của phân tích từ vựng

• Đâ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 đó

Token

Source

Lexical

Parser

program

analyzer

Get next token

Symbol

table

2

• 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

3

Một số khái niệm

• 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

4

• 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

relation <, <=, >, >=, =, <> < hoặc <= hoặc > hoặc >= hoặc = hoặc <>

id

pi, count, d2

3.1416, 0, 6.02E2 bất kì hằng số nào

các kí tự nằm giữa " và " ngoại trừ "

một kí tự, tiếp theo là các kí tự hoặc chữ số

num

literal "computer"

5

Đặc tả Token

• 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

6

• 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=0L

(Ghép của 0 hoặc nhiều L)

 i

Bao đóng dương (positive closure) của L: L⁺= _i=1L

(Ghép của 1 hoặc nhiều L)

7

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. L⁴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ố

8

Biểu thức chính qui

(regular expression)

• 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

9

• 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)

10

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,... }

11

Định nghĩa chính qui

(regular definition)

• Để 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

d₁→ r₁

d₂→ r₂

.........

d_n→ r_n

Trong đó d_ilà cá c tên, r_ilà các BTCQ trên tập

các kí hiệu {d₁, d₂, ....d_i-1}

12

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

13

• 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]*

14

Nhận dạng token

• 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

15

• 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⁺

16

• Mục đích của lexical analyzer tạo ra output là

các cặp <token, attribute-value>

Token

Regular Expression

Attribute-value

-

ws

-

if

then

if

then

else

id

pointer to table entry

num

pointer to table entry

<

<=

=

relop

LT

LE

EQ

NE

GT

<>

>

17

>=

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)

18

thông báo 1 token đã được nhận dạng

Ví dụ: Sơ đồ chuyển tiếp cho token các toán tử

quan hệ relop

start

<

=

0

1

return (relop, LE)

2

>

return (relop, NE)

return (relop, LT)

3

4

other

*

=

>

5

6

return (relop, EQ)

=

return (relop, GE)

7

other

*

8

return (relop, GT)

19

Ví dụ: Sơ đồ chuyển tiếp cho token các identifier và

letter or digit

keyword

start

*

letter

other

9

10

return (gettoken(), install_id())

11

• 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

20