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ừ “ Bảng 2.1 - Các ví dụ về token 2. 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ộ <token, tokenval>.2 : Token và giá trị thuộc tính đi kèm của câu lệnh position := initial + rate*10 được viết như một dãy các bộ sau: < tên, con trỏ đến position trong bảng danh biểu > < phép_gán, > < tên, con trỏ đến initial trong bảng danh biểu > < toán _tử_cộng, > < tên, con trỏ đến rate trong bảng danh biểu > < toán _tử_nhân, > < số_nguyên, giá trị nguyên 10 > 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. 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 Trang 17 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 cho đến khi tìm ra một token hoàn chỉnh. Kỹ thuật này đôi khi cũng gây ra sự nhầm lẫn cho giai đoạn phân tích cú pháp, nhưng nói chung là vẫn có thể sử dụng được.
Một số chiến lược khắc phục lỗi khác là: 1. Xen thêm một ký tự bị mất. Thay thế một ký tự không đúng bằng một ký tự đúng. Chuyển đổi hai ký tự kế tiếp nhau.
Lƣu trữ tạm thời trƣơng trình nguồn Việc đọc từng kí tự trong chương trình nguồn tốn một thời gian đáng kể nên nó ảnh hưởng tới tốc độ chương trình dịch. Để giải quyết vấn đề này, thiết kế đọc vào một lúc một chuỗi kí tự lưu trữ vào vùng nhớ tạm buffer. Nhưng việc đọc như vậy gặp khó khăn do không thể xác định được một chuỗi như thế nào thì chứa chọn vẹn 1 từ tố. Và phải phân biệt được một chuỗi như thế nào thì chứa chọn vẹn một từ tố.Có 2 phương pháp giải quyết như sau: 2.
Cặp bộ đệm * Cấu tạo: - Chia buffer thành 2 nửa, mỗi nửa chứa N kí tự ( N = 1024, 4096, …). - Sử dụng 2 con trỏ dò tìm trong buffer: p1: (lexeme_ beginning) đặt tại vị trí đầu của một từ vị. p2: (forwar):di chuyển trên từng kí tự trong buffer để xác định từ tố. Mỗi lần đọc, N ký tự từ chương trình nguồn sẽ được đọc vào mỗi nửa bộ đệm bằng một lệnh đọc (read) của hệ thống.
Nếu số ký tự còn lại trong chương trình nguồn ít hơn N thì một ký tự đặc biệt eof được đưa vào buffer sau các ký tự vừa đọc để báo hiệu chương trình nguồn đã được đọc hết. Sử dụng hai con trỏ dò tìm trong buffer. Chuỗi ký tự nằm giữa hai con trỏ luôn luôn là trị từ vựng hiện hành. Khởi đầu, cả hai con trỏ đặt trùng nhau tại vị trí bắt đầu của mỗi trị từ vựng.
Con trỏ p1 (lexeme_beginning) - con trỏ bắt đầu trị từ vựng - sẽ giữ cố định tại vị trí này cho đến khi con trỏ p2 (forwar) - con trỏ tới - di chuyển qua từng ký tự trong buffer để xác định một token. Khi một trị từ vựng cho một token đã được xác định, con trỏ p1 dời lên trùng với p2 và bắt đầu dò tìm một trị từ vựng mới. Trang 18 E = M * C * * 2 EOF p1 p2 Hình 2.2 - Cặp hai nửa vùng đệm Khi con trỏ p2 tới ranh giới giữa 2 vùng đệm, nửa bên phải được lấp đầy bởi N ký tự tiếp theo trong chương trình nguồn. Khi con trỏ p2 tới vị trí cuối bộ đệm, nửa bên trái sẽ được lấp đầy bởi N ký tự mới và p2 sẽ được dời về vị trí bắt đầu bộ đệm.
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 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 2.3 - Khóa cầm canh eof tại cuối mỗi vùng đệm Trang 19 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 begin Ðọc vào nửa đầu; Dời p2 vào đầu của nửa đầu; end else /* EOF ở giữa vùng đệm chỉ hết chương trình nguồn */ kết thúc phân tích từ vựng; end 2. Tính chất và nhận dạng token 2. Đặc tả token a.
Chuỗi và ngôn ngữ Chuỗi là một tập hợp hữu hạn các ký tự. Ðộ dài chuỗi là số các ký tự trong chuỗi. Chuỗi rỗng ε là chuỗi có độ dài 0. Ngôn ngữ là tập hợp các chuỗi.
Ngôn ngữ có thể chỉ bao gồm một chuỗi rỗng ký hiệu là ∅. Các phép toán trên ngôn ngữ - Hợp 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 } - Bao đóng Kleen của L: L * = ∞ ∪ i = 0 Li (Ghép của 0 hoặc nhiều L) - Bao đóng dƣơng (positive closure) của L: L+ = ∞∪i = 1 Li (Ghép của 1 hoặc nhiều L) Ví dụ 2., 9 } Trang 20 1) L ∪ D là tập hợp các chữ cái và số. 2) LD là tập hợp các chuỗi 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 chuỗi 4 chữ cái.
4) L* là tâp hợp tất cả các chuỗi 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 chuỗi 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 chuỗi gồm một hoặc nhiều chữ số. Biểu thức chính quy (Regular Expression) Trong Pascal, một danh biểu là một phần tử của tập hợp L (L ∪ D)*. Chúng ta có thể viết: danhbiểu = letter (letter | digit)* - Ðây là một biểu thức chính quy.
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)* 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.4: 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. 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 rε = r Quan hệ giữa r và ε r* = ( r | ε )* * có hiệu lực như nhau r* * = r * Bảng 2.3 - Một số tính chất đại số của biểu thức chính quy e.