Thẻ Từ, Mẫu Từ Vựng Và Trị Từ Vựng (Từ Vị)

Cho Automat được biểu diễn bằng đồ thị hình 2.1. Tính: ε-CLOSURE(0). ε-CLOSURE(0) = {0, 1, 6, 2, 4, 7, 8}

2

a

3



Start

0



1





6



7



8

a

9

b

10

4

b



5





Suy ra:

Hình 2.1. NFA với ε - dịch chuyển

b) Hàm chuyển trạng thái mở rộng

1. δ*(q, ε) = ε-CLOSURE(q)

2. δ*(q, wa) = ε-CLOSURE(δ(δ*(q, w), a)

a. δ*(q, a) = ε-CLOSURE(δ(δ*(q, ε), a)

= ε-CLOSURE(δ(ε-CLOSURE(q), a))

b. δ*(q, a1a2…an-1an) =

= ε-CLOSURE(δ(ε-CLOSURE(δ(…ε-CLOSURE(δ(ε-CLOSURE(q), a1)), a2)…),an))

3. - δ (T, a) =  δ(q, a)

qT

- δ* (T, a) =  δ*(q, a)

qT

Ví dụ 2.9:

Cho Automat được biểu diễn bằng đồ thị hình 2.1. Tính: δ*(0, a).

δ*(0, a) = ε-CLOSURE(δ(ε-CLOSURE(0), a))

- ε-CLOSURE(0) = {0, 1, 6, 2, 4, 7, 8}

- δ(ε-CLOSURE(0), a) = δ(ε-CLOSURE(0), a)

= δ({0, 1, 6, 2, 4, 7, 8}, a)

= δ(0, a) δ(1, a) δ(6, a)  δ(2, a) δ(4, a) δ(7, a) δ(8, a)

=  {3}  {9}

={3, 9}

δ*(0, a) = ε-CLOSURE(δ(ε-CLOSURE(0), a))

= ε-CLOSURE({3, 9})

= ε-CLOSURE(3)  ε-CLOSURE(9)

= {3, 6, 1, 2, 4, 7, 8}{9}

= {1, 2, 3, 4, 6, 7, 8, 9}

3) Ngôn ngữ được đoán nhận bởi NFAε

L(M) = {w | δ*(q0, w) F }

2.2. Giai đoạn phân tích từ vựng

Có thể kết hợp xen kẽ giữa quá trình phân tích từ vựng và phân tích cú pháp. Tuy nhiên, có thể tách riêng giai đoạn phân tích từ vựng với giai đoạn phân tích cú pháp vì các lý do sau:

- Làm cho việc thiết kế và viết chương trình dịch đơn giản hơn.

- Làm cho giai đoạn phân tích từ vựng làm việc hiệu quả hơn, chuyên dùng hơn và rất có thể nó được dùng lại cho các ngôn ngữ nguồn khác.

- Nó phù hợp với kỹ thuật lập trình theo hướng Modul hoá. Vị trí, chức năng, nhiệm vụ của giai đoạn phân tích từ vựng

Giai đoạn phân tích từ vựng là giai đoạn đầu tiên của một quá trình dịch. Chức năng của giai đoạn phân tích từ vựng là phân tích chương trình nguồn về mặt từ vựng: Phân tích chương trình nguồn thành dãy các từ vị và thu chương trình nguồn về dòng các thẻ từ. Nhiệm vụ chủ yếu của giai đoạn này là đọc vào chương trình nguồn. Dựa vào các quy tắc sinh của văn phạm, bảng từ khoá, bảng các ký hiệu, … phân tích để nhận ra các từ vị (lexeme) trong chương trình nguồn và thay thế nó bằng các thẻ từ (token) tương ứng. Nói một cách khác, nếu coi giai đoạn phân tích từ vựng ứng với bộ phân tích từ vựng trong chương trình dịch thì đầu vào của bộ phân tích từ vựng là chương trình nguồn; đầu ra của bộ phân tích từ vựng là dòng các thẻ từ (token). Giai đoạn phân tích từ vựng là giai đoạn duy nhất trong quá trình dịch phải dò đọc chương trình nguồn. Vì vậy, một trong các yêu cầu chủ yếu đối với bộ phân tích từ vựng là phải đọc nhanh, phân tích nhanh chương trình nguồn. Ngoài ra, nó còn đảm nhận thêm một số nhiệm vụ khác như:

- Cắt bỏ các dấu cách thừa.

- Bỏ qua các dòng chú thích của người lập trình.

- Bỏ qua các dấu Tab, dấu xuống dòng.

- Phát hiện lỗi các lỗi từ vựng và liên hệ với bộ xử lý lỗi để sửa hoặc báo lỗi. Hình 2.2 mô tả vị trí của giai đoạn phân tích từ vựng.

Chương trình nguồn

Phân tích từ vựng

Phân tích cú pháp

Thẻ từ Cây phân tích

(Parse tree)

Yêu cầu thẻ từ mới

Bảng kí hiệu

Hình 2.2. Vị trí của giai đoạn phân tích từ vựng

Ta có thể coi chương trình nguồn là dãy các từ vị và quá trình phân tích từ vựng là quá trình dò đọc chương trình nguồn, nhận biết các từ vị và thay thế chúng bởi các thẻ từ.

Ví dụ 2.10:

Trong ngôn ngữ lập trình Pascal, với câu lệnh: if a > b then max := a;

thì sản phẩm chính của bộ PTTV là dãy thẻ từ sau: IF ID RELOP ID THEN ID ASSIGN ID SEMI

2.2.1. Thẻ từ, mẫu từ vựng và trị từ vựng (từ vị)

1) Khái niệm thẻ từ, mẫu từ vựng và trị từ vựng

Khi nói đến bộ phân tích từ vựng, sẽ phải sử dụng các thuật ngữ thẻ từ (token),

mẫu từ vựng (pattern) và trị từ vựng - từ vị (lexeme) với nghĩa cụ thể như sau:

Thẻ từ (token) là dạng ngữ pháp của từ vị; hay nói một cách khác, thẻ từ là tập hợp xâu các ký tự kết thúc (từ vị) có chung nhau luật ngữ pháp sinh ra các từ vị đó và mỗi thẻ từ thường được đặt bởi một tên để định danh (phân biệt các thẻ từ với nhau).

Mỗi thẻ từ sẽ có một mẫu từ vựng (pattern) để xác định một từ vị là thuộc thẻ từ nào; hay nói cách khác, mẫu từ vựng của thẻ từ là luật ngữ pháp sinh ra các từ vị của thẻ từ đó.

Trị từ vựng – từ vị (lexeme) của một thẻ từ là một xâu các ký tự kết thúc của thẻ từ và nó phải thỏa mãn mẫu từ vựng của thẻ từ đó.

Nhờ vào thẻ từ, mẫu của thẻ từ, chương trình dịch trong giai đoạn phân tích từ vựng sẽ phân tích chương trình nguồn để xác định ra các trị từ vựng của các thẻ từ và trả về các thẻ từ cho giai đoạn phân tích cú pháp hoặc báo lỗi.

Ví dụ 2.11:

1. digit  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Thì:

+ digit là thẻ từ (token);

+ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 là mẫu từ vựng (pattern);

+ Mỗi chữ số: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 là một trị từ vựng – từ vị (lexeme) của thẻ từ digit.

2. letter  A | B | ...| Z | a | b |...| z Thì:

+ letter là tên của thẻ từ (token);

+ A | B | ...| Z | a | b |...| z là mẫu từ vựng (pattern);

+ Mỗi chữ cái La tinh: A, B, C, …, Z, a, b, c, …, z là một trị từ vựng – từ vị (lexeme) của thẻ từ letter.

3. id  (letter | _ )(letter | digit | _ )*

Thì:

+ id là tên thẻ từ (token);

+ (letter | _ )(letter | digit | _ )* là mẫu từ vựng (pattern);

+ A, X1B, max_1a23 là 3 trị từ vựng – từ v (lexeme) của thẻ từ id. Xét câu lệnh của Pascal:

If a = b then x := 0

else x := 1;

Ta có thể tách nhỏ câu lệnh thành các phần tử nhỏ nhất (nguyên tử):

Từ khoá if, khoảng trống, biến a, khoảng trống, dấu so sánh bằng (=), khoảng trống, biến b, từ khoá then, khoảng trống, biến x, khoảng trống, dấu gán (:=),

khoảng trống, con số 0, dấu xuống hàng, từ khoá else, khoảng trống, biến x, khoảng trống, dấu gán (:=) khoảng trống, con số 1, dấu chấm phẩy (;), dấu xuống hàng.

Mỗi phần tử nhỏ nhất (nguyên tử) không thể phân tách được nữa là một đơn vị từ vựng (lexical unit) hay trị từ vựng (từ vị) (lexeme).

Ví dụ 2.12:

Không thể tách chuỗi if thành i và f vì khi đó không còn tồn tại ý nghĩa của từ khóa if .

Dấu gán (:=) không thể tách ra thành hai dấu là dấu hai chấm (:) và dấu so sánh bằng (=) vì làm như thế sẽ đánh mất ý nghĩa của nó và tạo ra dấu hai chấm (:) cạnh dấu so sánh bằng (=) vô nghĩa.

Có thể nhóm một số trị từ vựng (từ vị) tuân theo một khuôn mẫu nào đó và có chức năng cú pháp giống nhau.

Ví dụ 2.13:

Các biến a, b và x có thể được nhóm lại vì chúng đều là tên của các đối tượng trong chương trình (identifier) và tuân theo quy ước đặt tên của ngôn ngữ đang xét. Tương tự, các toán tử so sánh cũng thường được nhóm lại. Các từ khóa if, then và else không được nhóm lại vì chức năng cú pháp của chúng không giống nhau.

Mỗi nhóm trị từ vựng (từ vị) được biểu diễn bằng một thẻ từ (token); khuôn mẫu của nó được gọi là mẫu từ vựng (pattern).

Thẻ từ (token) là một ký hiệu đại diện cho một loại trị từ vựng (từ vị), nghĩa là một tập các xâu ký tự có cùng chức năng cú pháp.

Một số ký hiệu thẻ từ cơ bản:

- Dùng ký hiệu ID làm thẻ từ cho các tên trong chương trình.

- Dùng ký hiệu RELOP làm thẻ từ cho các toán tử so sánh số học (=, <>,

>, >=, <, <=).

- Dùng ký hiệu IF làm thẻ từ cho từ khóa if, ký hiệu THEN cho từ khóa then, ký hiệu ELSE cho từ khóa else…

Các ngôn ngữ lập trình thường chia các thẻ từ thành năm loại chính:

- Từ khóa (keyword): IF, THEN, ELSE, ...

- Tên (identifier): max, min, ab1, ...

- Hằng (constant): 10, „Dai hoc SPKT Nam Dinh‟

- Toán tử (operator): +, -, *, /, >, <, ...

- Dấu phân cách (separator): ;, (, ), khoảng trống, ...

Một số ví dụ về cách dùng của các thuật ngữ này được trình bày trong bảng sau:

Token

Trị từ vựng (từ vị) minh họa	Mô tả của mẫu từ vựng
const	const	const
if	if	if
relop	<, <=, =, < >, >, >=	< hoặc <= hoặc = hoặc <> hoặc > hoặc >=
id	pi, count, d2	Mở đầu là chữ cái theo sau là chữ cái, chữ số
number	3.1416, 0, 5, 230	Bất kỳ hằng số nào
literal	“ hello ”	Mọi chữ cái nằm giữa “ và ”

Có thể bạn quan tâm!

• Chương trình dịch - 2
• Phân Tích Ngữ Nghĩa (Semantic Analysis)
• Nhắc Lại Một Số Kiến Thức Về Văn Phạm – Ngôn Ngữ - Automat
• Kỹ Thuật Sử Dụng Automat Để Phân Tích Từ Vựng
• Mô Tả Quá Trình Đoán Nhận Xâu
• Biểu Diễn Automat Bằng Đồ Thị

Xem toàn bộ 224 trang tài liệu này.

Bảng 2.1. Các ví dụ về token

2) Thuộc tính của thẻ từ (token)

Khi có nhiều mẫu từ vựng khớp với một trị từ vựng (từ vị), 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ụ 2.14:

Token và giá trị thuộc tính đi kèm của câu lệnh Pascal: E := M * C + 2 được viết như một dãy các bộ sau:

< id, con trỏ trong bảng ký hiệu của E >

< assign_op, >

< id, con trỏ trong bảng ký hiệu của M >

< mult_op, >

< id, con trỏ trong bảng ký hiệu của C>

< add_op, >

< num, giá trị nguyên 2 >

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 biết trị từ vựng.

3) Mô tả thẻ từ (token)

Các thẻ từ (token) khác nhau có các mẫu khác nhau. Các mẫu này là cơ sở để nhận biết thẻ từ. Như vậy, cần thiết phải hình thức hoá các mẫu này để sao cho có thể lập trình được. Việc này có thể thực hiện được nhờ định nghĩa chính quy.

a) Định nghĩa chính quy (Regular Definitions)

Định nghĩa chính quy là một dãy các định có dạng: d1  r1 ;

d2  r2 ;

...

dn  rn .

Trong đó: di là một tên;

ri là một biểu thức chính quy.

Ví dụ 2.15:

+ relop < | <= | > | >= | <> ;

+ digit  0 | 1 |...| 9 ;

+ digits  digit(digit)* .

b) Mô tả thẻ từ (token) bằng định nghĩa chính quy

Có thể sử dụng định nghĩa chính quy có thể biểu diễn thẻ từ. Chẳng hạn, một số thẻ từ được phát biểu bằng lời như sau:

- Tập các phép toán quan hệ là tập các phép toán <, <=, >, >=, <>.

- Tập hợp các tên trong Pascal là một tập hợp các xâu các ký tự bắt đầu bằng một chữ cái, sau đó là không, một hoặc nhiều các chữ cái hoặc chữ số.

Khi đó, sử dụng định nghĩa chính quy. Ta có thể mô tả các thẻ từ trên như:

- Mô tả thẻ từ các phép toán quan hệ (relop): relop < | <= | > | >= | <>

- Mô tả thẻ từ các tên (id):

+ letter  A | B | ...| Z | a | b |...| z ;

+ digit  0 | 1 | ...| 9 ;

*

+ id  (letter| _ ) (letter | digit | _ ) .

2.2.2. Nhận biết thẻ từ (token)

a) Nhận biết bằng định nghĩa chính quy

Trong phần này, ta sẽ sử dụng ngôn ngữ được tạo ra bởi văn phạm dưới đây làm ví dụ minh họa:

stmt  if expr then stmt | if expr then stmt else stmt | ε expr  term relop term | term

term  id | number

Trong đó các ký hiệu kết thúc if, then, else, relop, id, number được cho bởi định nghĩa chính quy sau:

if  if ;

then  then; else  else ;

relop < | <= | = | <> | > | >= ;

*

id  letter (letter | digit) ;

digit  0 | 1 |...| 9 ;

*

digits  digit(digit) ;

sign  + | - | ε ;

optional_fraction  . digits | ε ;

number  (sign)(digits)(optional_fraction) ;

delim  blank | tab | newline ;

ws  delim+.

Mục đích là xây dựng một bộ phân tích từ vựng có thể xác định được từ vị (lexeme) cho các thẻ từ (token) và tạo ra một cặp thích hợp token và giá trị thuộc tính của nó bằng cách dùng mẫu (patten) - biểu thức chính quy cho các token như sau: