Xem mẫu
- Chương 2: Phân tích từ vựng
1. Nhiệm vụ của bộ phân tích từ vựng
IT4073:NGÔN NGỮ và
2. Biểu thức chính quy
PHƯƠNG PHÁP DỊCH
3. Ô tô mát hữu hạn
Phạm Đăng Hải
haipd@soict.hut.edu.vn 4. Phân tích từ vựng của ngôn ngữ PL/0
9/18/2012 2
1. Nhiệm vụ của bộ phân tích 1. Nhiệm vụ của bộ phân tích
Mục đích & Nhiệm vụ Từ vựng và Từ tố
• Mục đích:
– Tìm chuỗi dài nhất các ký tự đầu vào, bắt đầu từ ký tự
• Từ vựng (Lexeme)
hiện tại tương ứng với một từ tố và trả về từ tố này – Là đơn vị nhỏ nhất trong ngôn ngữ lập trình
• Nhiệm vụ • Được coi là ký hiệu của một bảng chữ của ngôn ngữ
– Duyệt từng ký tự của văn bản nguồn – Được xây dựng từ các ký tự ASCII
• Loạ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 được
• Từ tố (Token)
– Nhận dạng từ tố và gửi tới pha tiếp – Là thuật ngữ dùng chỉ các từ vựng có cùng ý
Nhận biết từ tố gồm nghĩa cú pháp
– Nhận biết các từ khóa, tên do người dùng định nghĩa • Có thể coi từ vựng là những từ cụ thể trong từ điển:
– Nhận biết các con số, hằng chuỗi, hằng ký tự “hôm nay”, “trời”, “đẹp”; còn từ tố là loại từ: “trạng từ”,
– Nhận biết các ký tự đặc biệt (+,*,..), ký hiệu kép (:=,!=,..) “danh từ”, “tính từ”,..
9/18/2012 3 9/18/2012 4
- 1. Nhiệm vụ của bộ phân tích 1. Nhiệm vụ của bộ phân tích
Từ tố→Ví dụ Từ tố→Chú ý
pos := start + 10 * size; • Cá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ã
• “pos”, “start”, “size”, “+”, “10”, “*”,”:=“, “;” là từ vựng
hóa chương trình. Đây là việc số hóa ký hiệu
• “pos”, “start”, “size”, → các từ vựng thuộc lớp từ tố
• Một từ tố có thể ứng với tập các từ vựng khác nhau
tên (ident)
nên cần thêm một số thông tin khác để biết được
• ”:=“→ từ vựng của từ tố gán (assign) cụ thể đó là từ vựng nào
• “10” → từ vựng của từ tố số nguyên (number) – Cá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
• “+” → từ vựng của từ tố cộng (plus)
• Bộ phân tích từ vựng không chỉ nhận dạng được
• “*” → từ vựng của từ tố nhân (times) các từ tố mà còn phải biết thuộc tính tương ứng
• “;” → từ vựng của từ tố chấm phẩy (semicolon) – Từ tố tác động đến bộ phân tích cú pháp
– Thuộc tính sử dụng trong bộ sinh mã
9/18/2012 5 9/18/2012 6
1. Nhiệm vụ của bộ phân tích 1. Nhiệm vụ của bộ phân tích
Thực hiện Mẫu (Pattern)
Token • Là luật để mô tả một từ tố nào đó
Chương Phân tích Phân tích
trình nguồn từ vựng cú pháp – Cơ sở phân biệt & nhận dạng các từ tố khác nhau
getToken()
• Chuỗ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ật
Bảng ký hiệu
• Ví dụ
• Thực hiện lặp dựa vào yêu cầu từ bộ ptcp
– Luật mô tả của từ tố Ident
– Bộ ptcp khi cần một từ tố sẽ gọi getToken()
• Bắt đầu là một chữ cái
– Nhận được y/cầu, bộ pttv sẽ đọc các ký tự cho tới khi xây
• Tiếp theo là tổ hợp chữ cái, chữ số
dựng xong từ vựng và nhận ra từ tố hoặc gặp lỗi
– Luật mô tả của từ tố assign
• Thường bộ pttv được chia thành 2 phần chính
• Bắt đầu bởi ký tự “:”, ngay sau đó là ký tự “=“
– Đọc ký tự
– Xây dựng từ vựng và nhận dạng từ tố • Luật được mô tả bởi biểu thức chính quy
9/18/2012 7 9/18/2012 8
- 2. Biểu thức chính quy
Chương 2: Phân tích từ vựng Giới thiệu
• Ngô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)
1. Nhiệm vụ của bộ phân tích từ vựng • Từ: Được tạo nên từ một bộ chữ hữu hạn
Ví dụ:
2. Biểu thức chính quy – 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 ASCII
3. Ô tô mát hữu hạn • Một ngôn ngữ có thể là vô hạn, hoặc hữu hạn
• Một ngôn ngữ (có thể vô hạn) có thể được mô tả
4. Phân tích từ vựng của ngôn ngữ PL/0 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âu
– Chỉ xét xâu có thuộc ngôn ngữ không, chưa xét ý nghĩa
9/18/2012 9 9/18/2012 của xâu 10
2. Biểu thức chính quy 2. Biểu thức chính quy
Biểu thức chính quy (regular expression) Biểu thức chính quy→Ghi chú
Cho Σ là một bảng chữ của một ngôn ngữ. • Biểu thức (r + s) có thể được viết (r |s);
– ∅ là biểu thức chính quy biểu diễn ngôn ngữ ∅ • Biểu thức (r.s) thành (rs)
– ε là biểu thức chính quy biểu diễn ngôn ngữ {ε} • Có thể bỏ qua ký hiệu ε
– ( a | ) ⇔ (a | ε) // cũng có thể viết a?
– ∀a ∈ Σ, a là biểu thức chính quy biểu diễn tập {a}
• Có thể bỏ ngoặc đơn bởi định nghĩa thứ tự
– Nếu r và s là các biểu thức chính quy biểu diễn ưu tiên
các tập xâu R và S tương ứng thì (r + s), (r.s), (r*) – Phép đóng Kleene (*) ưu tiên hơn phép ghép(.)
là các biểu thức chính quy biểu diễn các tập xâu – Phép ghép(.) ưu tiên hơn phép hoặc (+)
R ∪ S, RS và R* tương ứng.
• Quy ước
Ngôn ngữ được xác định bởi biểu thức chính – [abcd] ⇔ (a|b|c|d)
quy e, ký hiệu là L(e) là ngôn ngữ chính quy – [a-f] ⇔ [abcdef]
9/18/2012 11 9/18/2012 [a-fA-F] ⇔ [abcdefABCDEF]
– 12
- 2. Biểu thức chính quy 2. Biểu thức chính quy
Biểu thức chính quy→Ví dụ Tính chất đại số của btcq
Cho Σ ={a,b} một bảng chữ. • 2 biểu thức chính quy là tương đương nếu
– e1 = a*+b* ⇒ L(e1) = {ε,a,aa,aaa,…,b,bb,..} cùng xác định một ngôn ngữ
– e2 = a*b* ⇒ L(e2) = {ε,a,b,aa,ab,bb,aaa,..} • Nếu r, s, t là các biểu thức chính quy
–r+s = s+r r+r=r
– e3 = a(a+b)*
– ( r + s) + t = r + s + t = r + (s + t)
⇒L(e3)={a,aa,ab,aaa,aab,aba,abb,..} – (r.s).t = r. s. t = r. (s. t)
• Xâu có dạng: bắt đầu là ký hiệu a, tiếp theo là tổ – r.ε = ε.r = r
hợp bất kỳ của các ký hiệu a, b –r+∅=∅+r=r
• Nếu a là một chữ cái, b là chữ số – r(s+t) = rs + ts (r+s)t = rt + st
⇒L(e3) là ngôn ngữ chứa các tên – r + r* = r* ; (r + ε)* = r* ; (r*)* = r*
⇒e3 biểu thức chính quy sinh mô tả một tên – rr* = r*r = r+
9/18/2012 13 – (r+s)* =(r*s*)*
9/18/2012 14
2. Biểu thức chính quy 2. Biểu thức chính quy
Văn phạm chính quy và Ngôn ngữ chính quy Ngôn ngữ chính quy →Văn phạm chính quy
• Văn phạm chính quy r là biểu thức chính qui cần chuyển
– Văn phạm mà mọi sản xuất có dạng 1. Thêm ký hiệu khởi đầu S và tạo san xuất S → r
A→a|aB hoặc A→a|Ba 2. Loại bỏ khỏi văn phạm các siêu ký hiệu của r
– Dùng diễn tả từ vựng của NNLT • ∀ 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” |”b” |”c” |….|”z”|”A”|”B”|…|”Z” A →r1B & B →r2
→”0” | ”1” | ”2” | ”3” |”4” | ”5” |”6” | ”7” |”8” |”9” • ∀ SX dạng A →r1+r2 : Thay bởi A →r1|r2
– Văn phạm chính quy sinh ra ngôn ngữ chính quy • ∀ SX dạng A →r1* r2: Thêm ký hiệu không
• Ngôn ngữ chính quy kết thúc B và thay thành 4 sản xuất
– Được biểu diễn (mô tả) bởi biểu thức chính quy A →r1B & A → r2 & B →r1B & B → r2
– Đoán nhận bởi các Otomat hữu hạn
9/18/2012 15 9/18/2012 16
- 2. Biểu thức chính quy 2. Biểu thức chính quy
Ví dụ Ví dụ
Chuyển đổi biểu thức e = a(a+b)* Chuyển đổi biểu thức e = a(a+b)* (tiếp)
1. Thêm S và sản xuất S→ a(a+b)* – Loại bỏ ký hiệu ε bởi tạo ra xâu mới
2. Loại bỏ các ký hiệu không thuộc bộ chữ B → aB|bB| ε thành B → aB|bB| a | b
– Xét r = a(a+b)* //r1 =a; r2 = (a+b)* A → aB|bB| ε thành A → aB|bB| a | b
Thêm A và các SX S→aA & A →(a+b)* Vai trò của A và B là tương đương. Thay ký
– Xét A →(a+b)* // r1 = a+b ; r2 = ε hiệu B bằng A và loại bỏ B
Thêm B và các SX
Kết quả: Văn phạm cuối
A→(a+b)B & A → ε &B→(a+b) & B → ε
– Áp dụng luật phân phối phải S → a |aA
A→aB+bB & A → ε & B→aB+bB & B → ε A → aA | bA | a | b
9/18/2012
A → aB|bB| ε và B → aB|bB| ε 17 9/18/2012 18
3. Ô tô mát hữu hạn
Chương 2: Phân tích từ vựng Mô tả
• Gồm một tập các trạng thái Q
– Có một trạng thái đầu q0 ∈ Q
1. Nhiệm vụ của bộ phân tích từ vựng – Có một tập trạng thái kết thúc F ⊆Q
• Một bộ chữ vào Σ
2. Biểu thức chính quy • Một tập các hàm dịch chuyển δ:(Q x Σ) → Q
Hoạt động
3. Ô tô mát hữu hạn – Ô-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
4. Phân tích từ vựng của ngôn ngữ PL/0 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át
9/18/2012 19 9/18/2012 20
- 3. Ô tô mát hữu hạn 3. Ô tô mát hữu hạn
Ví dụ Biểu diễn ô tô mát hữu hạn
• Σ = {a,b,c}
δ a b c
• Q = {q0, q1}
q0 q1 q0 q0 Trạng thái Trạng thái đầu Trạng thái kết thúc
• q0 = q0
q1 q0 q1 q1 a
• F = {q1} δ(p,a) = q p p
a b c a a b b c End b
a b
q0 q1
q0
1 c
c a
Xâu abcaabbc được đoán nhận Xâu trên bộ chữ {a,b,c} có lẻ ký hiệu a
9/18/2012 21 9/18/2012 22
3. Ô tô mát hữu hạn 3. Ô tô mát hữu hạn
Ô tô mát hữu hạn đơn định (OHĐ) Ví dụ
OHĐ(DFA: Deterministic Finite Automata) là M = (Σ, Q, δ,q0, F)
một hệ thống gồm q1
Σ = {a,b} b
a
M = (Σ, Q, δ,q0, F) • Q = {q0, q1, q2, q3} a a
– Σ: Bộ chữ vào • q0 = q0 q0 q2
– Q: Tập hữu hạn các trạng thái của bộ điều khiển • F = {q2}
•Q ∩ Σ = ∅ b b
δ a b
q3
– δ : Q x Σ→Q: Hàm dịch chuyển q0 q1 q3
• Hàm dich chuyển đơn định: q1 q3 q2 a,b
– q0 ∈ Q: Trạng thái ban đầu q2 q1 q3 L(M) = {ab}{ab}n≥0 = {ab}n(n>0)
– F ⊆ Q Tập các trạng thái cuối q3 q3 q3 = {ab,abab, ababab,..}
9/18/2012 23 9/18/2012 24
- 3. Ô tô mát hữu hạn 3. Ô tô mát hữu hạn
Hình trạng của FA Ô tô mát hữu hạn đơn định→Ví dụ
a
n m ≥0}
b {a b , n,ma,b
• Hì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 b a
q0 q1 q2
– x ∈ ∑* : Phân chưa xét của xâu vào
• Ký hiệu được đọc bởi đầu đọc là ký hiệu đầu của x
1 1
• Chuyển đổi hình trạng 0
– Nếu x = ay và ∃ δ(q,x) = p thì qx = qay ⇒ py
1 0 0 1
0 0 q1
qx ⇒ py : Là một bước biến đổi hình trạng
0
– Ví dụ: q0abaab ⇒q1baab ⇒q2aab ⇒q1ab ⇒q3b ⇒q3 0
• Hình trạng đầu : q0ω (ω: xâu cần đoán nhận) (0+1)*101 ⇔ Xâu nhị phân có hậu tố là 101
– Nếu q0ω ⇒* qn+1 ∈F: Xâu ω được đoán nhận Chữ số Chữ số
q0 Chữ số q2
• Ngôn ngữ được đoán nhận mở DFA M là L(M) q1
– L(M) = {ω | ω ∈ ∑* và q0ω ⇒* p ∈F} Đoán nhận số nguyên hoặc số thực dấu phẩy tĩnh
9/18/2012 25 9/18/2012 26
3. Ô tô mát hữu hạn 3. Ô tô mát hữu hạn
Ô tô mát hữu hạn không đơn định (OHK) Ví dụ
• OHK (NFA: Nondeterministic Finite Automata) M = ({a,b},{q0, q1, q2, q3,q4} δ,q0, {q2, q4}) a,b
là một hệ thống gồm a,b
δ a b q0 q1 q2
M = (Σ, Q, δ,q0, F) b b
q0 {q0,q3} {q0,q1}
– Σ, Q, q0, F: Định nghĩa như DFA a q0abaab ⇒
q1 ∅ {q2}
– δ : Q x (Σ∪ε)→2Q q2 {q2} {q2} q0baab ⇒
q3
• 2Q: Tập các tập con của Q, kể cả tập rỗng q0aab ⇒
q3 {q4} ∅
• Hàm dich chuyển không đơn định: Tại mỗi bước có a q3ab ⇒
q4 {q4} {q4} a,b
thể tồn tại nhiều lựa chọn q4 b ⇒
• Đoán nhận xâu: Quá trình chuyển đổi hình trạng. q4 q4
– Quá trình đoán nhận không đơn định
• Ngôn ngữ: L(M) = {ω | ω ∈ ∑* và ∃ q0ω ⇒* p ∈F} Đoán nhận xâu có 2 ký tự a, hoặc 2 ký tự b liên tiếp
9/18/2012 27 9/18/2012 28
- 3. Ô tô mát hữu hạn 3. Ô tô mát hữu hạn
DFA và NFA Lân cận rỗng: ε-Closure
• DFA và NFA tương đương nhau • Cho M = (Σ, Q, δ,q0, F) là NFA
– DFA và NFA cùng đoán nhận một lớp ngôn ngữ
• Cho p ∈ Q. ε-Closure(p) ={q ∈ Q | p ⇒* q}
• Ngôn ngữ chính quy
– Lân cận rỗng của p là các trạng thái q có thể đi
• Với mỗi NFA, tồn tại DFA tương đương
đến từ p với đường dẫn ε
a,b
a,b
q0 q1 q2 B ε q1 a
b b q0 q2
a a a,b
a
a b ε
q3 A D
ε-Closure(q0) = {q0,q1,q3} q3
a b b
q4 a,b C
9/18/2012 29 9/18/2012 30
3. Ô tô mát hữu hạn 3. Ô tô mát hữu hạn
Thuật toán tính lân cận rỗng Lân cận rỗng của tập
• Cho M = (Σ, Q, δ,q0, F) là NFA Nếu S ⊆ Q
• Thuật toán – ε-Closure{S} = ∪ ε-Closure{p} , ∀p ∈ S
1. ε-Clos0{p} = {p} – Nếu không tồn tại bước chuyển rỗng
2. Repeat • ε-Closure{S} = { S } ∀ S ⊆Q
ε-Closi+1{p} = ε a
q 1 q2
ε-Closi{p} ∪ {q∈Q |∃s∈Closi(p), δ(s, ε)=q}
3. Unil ε-Closi+1{p} = ε-Closi{p} q0
4. ε-Closure{p} = ε-Closi+1{p} b
ε q3 q4
Nhận xét: Do ε-Closi{p} ⊆ ε-Closi+1{p} ⊆ Q ε-Closure{q0}={q0,q1,q3}
Dãy đơn điệu tăng nên dãy hội tụ ε-Closure{q1,q3}={q1,q3}
9/18/2012 31 9/18/2012 32
- 3. Ô tô mát hữu hạn 3. Ô tô mát hữu hạn
Chuyển đổi NFA→DFA Ví dụ - 1
Cho NFA While Stack.NotEmpty() Do a
δ a b a,b a
M =(Σ, Q, δ,q0,F) 1. S = Stack.Pop()
q0 {q0,q1} {q1} q0 q1
2. For ∀ a ∈∑ do
Xây dựng DFA q1 {q0,q1} ∅ a
1. T = ∪δ(q,a) ;∀ q ∈ S
M’=(Σ, Q’, δ’,q’0,F’) 2. q’ = ε-Closure(T)
3. If q’ ∉ Q’ Then Q’ δ’ a b
Thuật toán
1.Q’ = Q’ ∪{ q’ } {q0} {q0} {q0,q1} {q1} A
• q’0 = ε-Closure({q0}) 2.Stack.Push(q’) a,b
{q0,q1} {q0,q1} {q0,q1} {q1} B
• Q’ ={q’0} 4. δ’(S,a) = q’ b
{q1} {q1} {q0,q1} ∅ C C
• F’ = { } For ∀ q’ ∈ Q D
∅ ∅ ∅ ∅ D b
• Stack.PUSH(q’0) 1. If q’ ∩F≠∅ Then b a
1. F’ = F’ ∪ {q’} a B a
9/18/2012 33 9/18/2012
A 34
3. Ô tô mát hữu hạn 3. Ô tô mát hữu hạn
Ví dụ - 2 Tối ưu hóa trạng thái OHĐ
ε • Nhiều DFA cùng đoán nhận một ngôn ngữ
b – Cần tìm DFA có ít trạng thái nhất
q1 a q2 ε q3 q4 ε q5 ε
ε • Dễ dàng biểu diễn trong máy tính
ε q8 • Trạng thái phân biệt
q0
ε – Hai trạng thái p và q là không phân biệt nếu
ε
c ∀ xâu w∈∑*, (pw,qw)⇒*(p’,q’)∈FxF∪(Q-F)x(Q-F)
q6 q7
b pw,qw cùng dẫn tới trạng thái cuối hoặc không
– Ví dụ: ε là xâu phân biệt giữa các trạng thái kết thúc và
q0 a b không kết thúc
q1 q3
• Nguyên tắc:
c
– Phân hoạch Q thành các nhóm t/thái không phân biệt
q2 – Thay thế nhóm bằng trạng thái duy nhất
9/18/2012 35 9/18/2012 36
- 3. Ô tô mát hữu hạn 3. Ô tô mát hữu hạn
Tối ưu hóa trạng thái OHĐ Ví dụ -1
1.Chia Q thành 2 nhóm F và Q - F a a
b q2 a q3
q1
2.Giả thiết đã tồn tại các nhóm A1, A2,…An a
• Xét nhóm Am = {qm1,..qmk } q0
• Xét a∈∑; pmi = δ(qmi, a) ; pmj = δ(qmj, a) b a
q4 a
q5
• 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ω) a
q1 a q3
• Nếu ∀ a ∈∑ pmi và pmj không phân biệt (∀ xâu ω) b
qmi và qmj không phân biệt (∀ xâu aω) q0 b
a
3.Thuật toán dừng khi không tạo thêm nhóm
q2 a
9/18/2012 37 9/18/2012 38
3. Ô tô mát hữu hạn 3. Ô tô mát hữu hạn
Ví dụ - 2 Xây dựng OHK từ biểu thức chính quy
a,b a,b • Sử dụng biểu thức chính quy mô tả NNCQ
q0 q1 q2 q3 – Trong chương trình dịch, mô tả từ vựng
a a, b a
– Ví dụ:
b Tên : a(a+b)* //a chữ cái, b: chữ số
q0 a q1 Số thực tĩnh: .b+| b+ . b+ //b: Chữ số
b b a • Ngôn ngữ chính quy được đoán nhận bởi FA
b – Cần xây dựng FA đoán nhận ngôn ngữ được
q2 q3 mô tả bởi các biểu thức chính quy
a a
q4
9/18/2012
a,b 39 9/18/2012 40
- 3. Ô tô mát hữu hạn 3. Ô tô mát hữu hạn
Thuật toán Thuật toán
Mr
ε : Là btcq ứng với FA r Là btcq ứng với FA Mr q0 F
Ms
s Là btcq ứng với FA Ms q0 F
q0
Mr
ε q0 F ε
∅ : Là btcq ứng với FA r+s q’0 F
ε Ms
q0 F ε
q0
Mr ε Ms
r.s q0 F q0 F
a∈∑: Là btcq ứng với FA
ε
a r* q’0 ε q0 Mr
F ε f
q0 q
ε
9/18/2012 41 9/18/2012 42
3. Ô tô mát hữu hạn 3. Ô tô mát hữu hạn
Ví dụ -1 Ví dụ - 2
Xây dựng DFA đoán nhận NNCQ được biểu Xây dựng DFA đoán nhận NNCQ được biểu
diễn bởi btcq (0+1)*011 diễn bởi btcq (01+010)*
1 q3 1
0
1
0 0 0 1 0
q0 q1 q2 q3
0 1 1
q0 q1 q2 q4
1
0 0
9/18/2012 43 9/18/2012 44
- 3. Ô tô mát hữu hạn 3. Ô tô mát hữu hạn
Thuật toán đoán nhận xâu của OHĐ Phương pháp phân tích bảng
• Phương pháp phân tích bảng 1 1
0
– Dựa trên giải thuật tổng quát để đoán nhận DFA 1 0 C 1
A B D
– Ưu điểm:
0
• Chương trình độc lập với DFA 0
• Dễ biến đổi, không cần sửa lại chương trình
– Nhược điểm: #include
• Khó khăn trong lập bảng #include
• Kích thước bảng lớn enum state {A,B,C,D};
int Delta[4][2]={A,B,C,B,A,D,C,B}; //Hàm dịch chuyển dạng bảng
• Phương pháp diễn giải
char c, str[100];
– Thực hiện như diễn giải sơ đồ int i, L;
– Dễ viết, nhưng c\trình gắn với đồ thị dich chuyển enum state q = A; //Automat ở trạng thái đầu
– Được sử dụng để xây dựng bộ phân tích từ vựng
9/18/2012 45 9/18/2012 46
3. Ô tô mát hữu hạn 3. Ô tô mát hữu hạn
Phương pháp phân tích bảng Phương pháp diễn giải
void main(){
printf("Nhap xau.. :"); fflush(stdin); gets(str); Chữ số Chữ số
q0 Chữ số q2
i = 0; L = strlen(str); c = str[i]-48; q1
while (i < L){
if(c == 0 || c == 1){ //Xâu vào chỉ gồm các ký hiệu 0,1 #include
q = Delta[q][c]; //Chuyển trạng thái mới #include
i++; //Dịch chuyển đầu đọc #include
c = str[i]-48; //Ký hiệu đọc được void main(){
} else { printf("Loi xau vao...\n"); break; } char c, str[100];
}
int i, L;
if(i==L) //Nếu đọc hết toàn bộ xâu vào
printf("Nhap xau.. :"); fflush(stdin); gets(str);
if (q == D) printf("\n Xau %s duoc doan nhan !\n\n",str);
i= 0; L = strlen(str);
else printf("\n Xau %s khong duoc doan nhan !\n\n",str);
}
9/18/2012 47 9/18/2012 48
- 3. Ô tô mát hữu hạn
Phương pháp phân tích bảng Chương 2: Phân tích từ vựng
if(isdigit(str[i])){ //Nếu ký hiệu đọc được là một chữ số
i=i+1; //Đọc ký hiệu tiếp trên xâu vào
while(isdigit(str[i])) i = i + 1; //Vẫn là chữ số, đọc tiếp 1. Nhiệm vụ của bộ phân tích từ vựng
if(i==L) printf("%s la so nguyen \n",str); //Đọc hết xâu vào
else if(str[i]!='.') printf("%s khong duoc doan nhan (%d)\n",str,i+1);
else { //Đã đọc được dãy số và dấu ‘.’
2. Biểu thức chính quy
i = i + 1;
while(isdigit(str[i])) i = i + 1; 3. Ô tô mát hữu hạn
if(i==L) printf("%s la so thuc dau phay tinh \n",str);
else printf("%s khong duoc doan nhan(%d)\n",str,i+1);
}
4. Phân tích từ vựng của ngôn ngữ PL/0
} else printf("%s khong duoc doan nhan (%d)\n",str,i+1);
}//main
9/18/2012 49 9/18/2012 50
3. Phân tích từ vựng của ngôn ngữ PL/0 mở rộng 3. Phân tích từ vựng của ngôn ngữ PL/0 mở rộng
Các từ vựng của PL/0 mở rộng Ô-tô-mát hữu hạn của bộ phân tích từ vựng
• Số nguyên
• Định danh
• Từ khóa:
begin, end, if, then, while, do, call, odd, to
const, var, procedure, program, else, for
• Dấu phép toán:
– Số học: +-*/
– So sánh: = < > =
• Dấu phân cách: ( ) .,; [ ]
• Dấu phép gán: :=
Sau mỗi từ tố được nhận biết, bộ từ vựng lại quay lại trạng thái 0
9/18/2012 51 9/18/2012 52
- 3. Phân tích từ vựng của ngôn ngữ PL/0 mở rộng 3. Phân tích từ vựng của ngôn ngữ PL/0 mở rộng
Các từ tố của PL/0 mở rộng Các từ tố của PL/0 mở rộng
• Mỗi từ tố là tên một trạng thái • Toán tử
– Từ tố là ident, cần kiểm tra xem từ vựng tương + (PLUS) - (MINUS)
ứng có phải là từ khóa không * (TIMES) / (SLASH)
• Các từ tố = (EQU) (NEQ)
– Số nguyên: NUMBER < (LSS) (GRT) >= (GEQ)
• Nếu từ vựng trùng từ khóa, từ vựng sẽ mang ý nghĩa ( (LPARENT) ) (RPARENT)
từ tố trùng với tên từ khóa
[ (LBRACK) ] (RBRACK)
• Ví dụ: Từ vựng Begin có từ tố BEGIN
Từ vựng Procedure có từ tố PROCEDURE . (PERIOD) , (COMMA)
; (SEMICOLON) := (ASSIGN)
• Các trường hợp khác: từ tố NONE
9/18/2012 53 9/18/2012 54
3. Phân tích từ vựng của ngôn ngữ PL/0 mở rộng 3. Phân tích từ vựng của ngôn ngữ PL/0 mở rộng
Các khai báo Xây dựng từ vựng
typedef enum {//Các loại Token được sử dụng trong PL/0 • Khi bộ pttv - thủ tục getToken() bắt đầu hoạt động,
NONE=0, IDENT, NUMBER, ô-tô-mát ở trạng thái khởi tạo (Trạng thái 0)
BEGIN, CALL, CONST, DO, ELSE, END, FOR, IF, ODD, • Bộ pttv gọi liên tiếp getCh() để đọc các ký hiệu trên
PROCEDURE, PROGRAM, THEN, TO, VAR, WHILE, văn bản nguồn cho tới khi gặp một ký tự không
PLUS, MINUS, TIMES, SLASH, EQU, NEQ, LSS, LEQ, thuộc luật mô tả hiện tại →Ô-to-mát không chuyển
GTR, GEQ, LPARENT, RPARENT, LBRACK, RBRACK,
PERIOD, COMMA, SEMICOLON, ASSIGN
trạng thái được
– Xâu đọc được là từ vựng mang ý nghĩa của từ tố đang
} TokenType;
phân tích và là trạng thái hiện tại của Ô-tô-mát
TokenType Token; //Token nhận dạng được
– Đọc thừa ra một ký tự
int Num; //Từ vựng khi Token là NUMBER • Là ký tự trắng hoặc ký tự đầu của từ tố tiếp → Khi getToken()
char Id[MAX_IDENT_LEN + 1]; //Từ vựng khi Token là IDENT được gọi, sẽ làm việc ngay với một ký tự có sẵn.
• Tại lần gọi getToken() đầu tiên để xác định từ tố thứ nhất, bộ
ptcp phải cũng cấp sẵn một ký tự → là ký tự trắng
9/18/2012 55 9/18/2012 56
- 3. Phân tích từ vựng của ngôn ngữ PL/0 mở rộng 3. Phân tích từ vựng của ngôn ngữ PL/0 mở rộng
Xây dựng từ vựng Nhận dạng từ tố
//ch chứa ký tự đọc được từ văn bản nguồn bởi hàm getCh() Xây dựng xong từ vựng, cần nhận dạng từ tố
switch(Ch) {
– Là tên trạng thái cuối cùng của Ô-tô-mát
case SPACE : while (Ch==SPACE) gettCh();
case LETTER: getCh(); – Nếu Ô-tô-mát kết thúc ở trạng thái IDENT, cần
while (Ch==LETTER || Ch==DIGIT) getCh(); kiểm tra đây có phải là từ khóa
return Ident; //Cũng có thể là từ khóa →Phải kiểm tra • Dùng kỹ thuật bảng chuyển đổi
case DIGIT: while (Ch==DIGIT) getCh(); return NUMBER;
case ‘+’: getCh(); return plus; BEGIN → BEGIN
Chú ý: Với từ tố
case ‘>‘ : getCh(); CALL → CALL
ident và number,
if(Ch == ‘=‘) { getCh(); return GEQ;}
else return GTR;
cần phải ghi …..
nhận giá trị từ VAR → VAR
…..
vựng tương ứng WHILE → WHILE
}
9/18/2012 57 9/18/2012 58
3. Phân tích từ vựng của ngôn ngữ PL/0 mở rộng
Bài tập
1. Xây dựng bộ phân tích cho PL/0
2. Tìm hiểu về Lex/JLex
9/18/2012 59
nguon tai.lieu . vn
