Giáo trình môn Chương trình dịch - Đại học Thái Nguyên

76 trang Hùng Dũng 04/01/2024 220

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình môn Chương trình dịch - Đại học Thái Nguyên", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_mon_chuong_trinh_dich_dai_hoc_thai_nguyen.pdf

Nội dung text: Giáo trình môn Chương trình dịch - Đại học Thái Nguyên

Khoa công nghệ thông tin - Đại học Thái Nguyên Bộ môn công nghệ phần mềm GIÁO TRÌNH MÔN CHƯƠNG TRÌNH DỊCH (Compiler Construction) Thái nguyên, 2007
LỜI NÓI ĐẦU Môn học chương trình dịch là môn học của ngành khoa học máy tính. Trong suốt thập niên 50, trình biên dịch được xem là cực kỳ khó viết. Ngày nay, việc viết một chương trình dịch trở nên đơn giản hơn cùng với sự hỗ trợ của các công cụ khác. Cùng với sự phát triển của các chuyên ngành lý thuyết ngôn ngữ hình thức và automat, lý thuyết thiết kế một trình biên dịch ngày một hoàn thiện hơn. Có rất nhiều các trình biên dịch hiện đại, có hỗ trợ nhiều tính năng tiện ích khác nữa. Ví dụ: bộ visual Basic, bộ studio của Microsoft, bộ Jbuilder, netbean, Delphi Tại sao ta không đứng trên vai những người khổng lồ đó mà lại đi nghiên cứu cách xây dựng một chương trình dịch nguyên thuỷ. Với vai trò là sinh viên công nghệ thông tin ta phải tìm hiểu nghiên cứu xem một chương trình dịch thực sự thực hiện như thế nào? Mục đích của môn học này là sinh viên sẽ học các thuật toán phân tích ngữ pháp và các kỹ thuật dịch, hiểu được các thuật toán xử lý ngữ nghĩa và tối ưu hóa quá trình dịch. Yêu cầu người học nắm được các thuật toán trong kỹ thuật dịch. Nội dung môn học : Môn học Chương trình dịch nghiên cứu 2 vấn đề: - Lý thuyết thiết kế ngôn ngữ lập trình ( cách tạo ra một ngôn ngữ giúp người lập trình có thể đối thoại với máy và có thể tự động dịch được). - Cách viết chương trình chuyển đổi từ ngôn ngữ lập trình này sang ngôn ngữ lập trình khác. Học môn chương trình dịch giúp ta: - Nắm vững nguyên lý lập trình: Hiểu từng ngôn ngữ, điểm mạnh điểm yếu của nó => chọn ngôn ngữ thích hợp cho dự án của mình. Biết chọn chương trình dịch thích hợp (VD với pascal dưới Dos: chương trình dịch là turbo pascal. Đối với ngôn ngữ C: chọn turbo C hay bolean C? Bolean C tiện lợi, dễ dùng, turbo C sinh mã gọn, không phải lo vè vấn đề tương thích với hệ điều hành nhưng khoá dùng hơn). Phân biệt được công việc nào do chương trình dịch thực hiện và do chương trình ứng dụng thực hiện. - Vận dụng: thực hiện các dự án xây dựng chương trình dịch. Áp dụng vào các ngành khác như xử lý ngôn ngữ tự nhiên
Để viết được trình biên dịch ta cần có kiến thức về ngôn ngữ lập trình, cấu trúc máy tính, lý thuyết ngôn ngữ, cấu trúc dữ liệu, phân tích thiết kế giải thuật và công nghệ phần mềm. Những kiến thức của môn học cũng có thể được sử dụng trong các lĩnh vực khác như xử lý ngôn ngữ tự nhiên. Tài liệu tham khảo: 1. Giáo trình sử dụng: Dick Grune, Ceriel Jacobs, Parsing Techniques: A Practical Guide, 1998 2. Một số tài nguyên trực tuyến có thể được tìm thấy bằng việc sử dụng máy tìm kiếm, chẳng hạn như và 3. Bài giảng Lý thuyết và Thực hành Chương Trình Dịch của Lê Anh Cường, khoa Công Nghệ, ĐHQG Hà nội, 2004. 4. Giáo trình lý thuyết, thực hành môn học Chương trình dịch của Phạm Hồng Nguyên, Khoa Công Nghệ, ĐHQG Hà nội, 1998. 5. Ngôn ngữ hình thức của Nguyễn Văn Ba, ĐHBK Hà nội, 1994 6. Thực hành kỹ thuật biên dịch của Nguyễn Văn Ba, ĐHBK Hà nội, 1993 7. Compiler: principles techniques and tools của A.V. Aho, Ravi Sethi, D. Ulman, 1986 8. Bản dịch của tài liệu: Trình biên dịch: Nguyên lý, kỹ thuật và công cụ của Trần Đức Quang, 2000.
Chương 1: Tổng quan về ngôn ngữ lập trình và chương trình dịch 1. Ngôn ngữ lập trình và chương trình dịch. Con người muốn máy tính thực hiện công việc thì con người phải viết yêu cầu đưa cho máy tính bằng ngôn ngữ máy hiểu được. Việc viết yêu cầu gọi là lập trình. Ngôn ngữ dùng để lập trình gọi là ngôn ngữ lập trình. Có nhiều ngôn ngữ lập trình khác nhau. Dựa trên cơ sở của tính không phụ thuộc vào máy tính ngày càng cao người ta phân cấp các ngôn ngữ lập trình như sau: - Ngôn ngữ máy (machine languge) - Hợp ngữ (acsembly langguge) - Ngôn ngữ cấp cao (high level langguage) Ngôn ngữ máy chỉ gồm các số 0 và 1, khó hiểu đối với người sử dụng. Mà ngôn ngữ tự nhiên của con người lại dài dòng nhiều chi tiết mập mờ, không rõ ràng đối với máy. Để con người giao tiếp được với máy dễ dàng cần một ngôn ngữ trung gian gần với ngôn ngữ tự nhiên. Vì vậy ta cần có một chương trình để dịch các chương trình trên ngôn ngữ này sang mã máy để có thể chạy được. Những chương trình làm nhiệm vụ như vậy gọi là các chương trình dịch. Ngoài ra, một chương trình dịch còn chuyển một chương trình từ ngôn ngữ nay sang ngôn ngữ khác tương đương. Thông thường ngôn ngưc nguồn là ngôn ngữ bậc cao và ngôn ngữ đích là ngôn ngữ bậc thấp, ví dụ như ngôn ngữ Pascal hay ngôn ngữ C sang ngôn ngữ Acsembly. * Định nghĩa chương trình dịch: Chương trình dịch chương trình chương trình là một chương trình nguồn (ngôn chương trình đích (ngôn thực hiện việc chuyển ngữ bậc cao) dịch ngữ máy) đổi một chương trình hay đoạn chương trình từ ngôn ngữ này (gọi là ngôn ngữ nguồn) sang Lỗi ngôn ngữ khác (gọi là ngôn ngữ đích) tương Hình 1.1: Sơ đồ một chương trình dịch đương. Để xây dựng được chương trình dịch cho một ngôn ngữ nào đó, ta cần biết về đặc tả của ngôn ngữ lập trình, cú pháp và ngữ nghĩa của ngôn ngữ lập trình đó Để đặc tả ngôn ngữ lập trình, ta cần định nghĩa: - Tập các kí hiệu cần dùng trong các chương trình hợp lệ. - Tập các chương trình hợp lệ.
- Nghĩa của từng chương trình hợp lệ. Việc định nghĩa tập các kí hiệu cần dùng của ngôn ngữ là dế dàng, ta chỉ cần liệt kê là đủ. Việc xác định các chương trình hợp lệ thì khó khăn hơn. Thông thường ta dùng các luật của văn phạm để đặc tả. Việc thứ 3, định nghĩa ý nghĩa của chương trình hợp lệ là khó khăn nhất. Có 3 phương pháp để xác định nghĩa của chương trình hợp lệ. + Phương pháp 1: định nghã bằng phép ánh xạ. ánh xạ mỗi chương trình vào một câu trong ngôn ngữ mà ta có thể hiểu được. + Phương pháp 2: Xác định ý nghĩa của chương trình bằng một máy lý tưởng. Ý nghĩa của chương rình được đăc tả trong ngôn từ của máy lý tưởng. Máy lý tưởng là bộ thông dịch của ngôn ngữ. + Phương pháp 3: ý nghĩa cảu chương trình nguồn là sản phẩm xuất ra của trình biên dịch, khi nó dịch chương trình nguồn. 2. Phân loại chương trình dịch. Có thể phân thành nhiều loại tuỳ theo các tiêu chí khác nhau. - Theo số lần duyệt: Duyệt đơn, duyệt nhiều lần. - Theo mục đích: Tải và chạy, gỡ rối, tối ưu, chuyển đổi ngôn ngữ, chuyển đôỉ định dạng - Theo độ phức tạp của chương trình nguồn và đích: + Asembler (chương trình hợp dịch): Dịch từ ngôn ngữ asembly ra ngôn ngữ máy. + Preproccessor: (tiền xử lý) : Dịch từ ngôn ngữ cấp cao sang ngôn ngữ cấp cao khác (thực chất là dịch một số cấu trúc mới sang cấu trúc cũ). + Compiler: (biên dịch) dịch từ ngôn ngữ cấp cao sang ngôn ngữ cấp thấp. - Theo phương pháp dịch chạy: + Thông dịch: (diễn giải - interpreter) chương trình thông dịch đọc chương trình nguồn theo từng lệnh và phân tích rồi thực hiện nó. (Ví dụ hệ điều hành thực hiện các câu lệnh DOS, hay hệ quản trị cơ sở dữ liệu Foxpro). Hoặc ngôn ngữ nguồn không được chuyển sang ngôn ngữ máy mà chuyển sang một ngôn ngữ trung gian. Một chương trình sẽ có nhiệm vụ đọc chương trình ở ngôn ngữ trung gian này Chươngvà thực hiện từng câu lệnh. Ngôn ngữ trung gian được gọi là ngôn ngữ của CT ở NN trình một máy ảo, chương trình thôngCompiler dịch thực hiệntrung ngôn gian ngữ này gọi làInterpreter máy ảo. nguồn Kết quả Hình 1.2 Hệ thống thông dịch
Ví dụ hệ thông dịch Java. Mã nguồn Java được dịch ra dạng Bytecode. File đích này được một trình thông dịch gọi là máy ảo Java thực hiện. Chính vì vậy mà người ta nói Java có thể chạy trên mọi hệ điều hành có cài máy ảo Java. + Biên dịch: toàn bộ chương trình nguồn được trình biên dịch chuyển sang chương trình đích ở dạng mã máy. Chương trình đích này có thể chạy độc lập trên máy mà không cần hệ thống biên dịch nữa. - Theo lớp văn phạm: LL (1) (LL – Left to right, leftmost) LR(1) (LR – letf to right, right most) 1.3. Cấu trúc của chương trình dịch. 1.3.1. cấu trúc tĩnh (cấu trúc logic)
1) Phân tích từ vựng: đọc luồng kí tự tạo thành chương trình nguồn từ trái sang phải, tách ra thành các từ tố (token). - Từ vựng: Cũng như ngôn ngữ tự nhiên, ngôn ngữ lập trình cũng được xây dựng dựa trên bộ từ vựng. Từ vựng trong ngôn ngữ lập trình thường được xây dựng dựa trên bộ chữ gồm có: + chữ cái: A Z, a . . z + chữ số: 0 9 + các ký hiệu toán học: +, - , *, /, (, ), =, , !, %, / + các ký hiệu khác: [, ], . . . Các từ vựng được ngôn ngữ hiểu bao gồm các từ khóa, các tên hàm, tên hằng, tên biến, các phép toán, . . . Các từ vựng có những qui định nhất định ví dụ: tên viết bởi chữ cái đầu tiên sau đó là không hoặc nhiều chữ cái hoặc chữ số, phép gán trong C là =, trong Pascal là :=,v. . . Để xây dựng một chương trình dịch, hệ thống phải tìm hiểu tập từ vựng của ngôn ngữ nguồn và phân tích để biết được từng loại từ vựng và các thuộc tính của nó, Ví dụ: Câu lệnh trong chương trình nguồn viết bằng ngôn ngữ pascal: “a := b + c * 60” Chương trình phân tích từ vựng sẽ trả về: a là tên (tên (định danh )) := là toán tử gán b là tên (định danh) + là toán tử cộng c là định danh * là toán tử nhân 60 là một số Kết quả phân tích từ vựng sẽ là: (tên, a), phép gán, (tên, b) phép cộng (tên, c) phép nhân, (số, 60)
2). Phân tích cú pháp: Phân tích cấu trúc ngữ pháp của chương trình. Các từ tố được nhóm lại theo cấu trúc phân cấp. - Cú pháp: Cú pháp là thành phần quan trọng nhất trong một ngôn ngữ. Như chúng ta đã biết trong ngôn ngữ hình thức thì ngôn ngữ là tập các câu thỏa mãn văn phạm của ngôn ngữ đó. Ví dụ như câu = chủ ngữ + vị ngữ vị ngữ = động từ + bổ ngữ v.v. . . Trong ngôn ngữ lập trình, cú pháp của nó được thể hiện bởi một bộ luật cú pháp. Bộ luật này dùng để mô tả cấu trúc của chương trình, các câu lệnh. Chúng ta quan tâm đến các cấu trúc này bao gồm: 1) các khai báo 2) biểu thức số học, biểu thức logic 3) các lệnh: lệnh gán, lệnh gọi hàm, lệnh vào ra, . . . 4) câu lệnh điều kiện if 5) câu lệnh lặp: for, while 6) chương trình con (hàm và thủ tục) Nhiệm vụ trước tiên là phải biết được bộ luật cú pháp của ngôn ngữ mà mình định xây dựng chương trình cho nó. Với một chuỗi từ tố và tập luật cú pháp của ngôn ngữ, bộ phân tích cú pháp tự động đưa ra cây cú pháp cho chuỗi nhập. Khi cây cú pháp xây dựng xong thì quá trình phân tích cú pháp của chuỗi nhập kết thúc thành công. Ngược lại nếu bộ phân tích cú pháp áp dụng tất cả các luật hiện có nhưng không thể xây dựng được cây cú pháp của chuỗi nhập thì thông báo rằng chuỗi nhập không viết đúng cú pháp. Chương trình phải phân tích chương trình nguồn thành các cấu trúc cú pháp của ngôn ngữ, từ đó để kiểm tra tính đúng đắn về mặt ngữ pháp của chương trình nguồn. 3). Phân tích ngữ nghĩa: Phân tích các đặc tính khác của chương trình mà không phải đặc tính cú pháp. Kiểm tra chương trình nguồn để tìm lỗi cú pháp và sự hợp kiểu. Dựa trên cây cú pháp bộ phân tích ngữ nghĩa xử lý từng phép toán. Mỗi phép toán nó kiểm tra các toán hạng và loại dữ liệu của chúng có phù hợp với phép toán không.
VD: tên (biến) được khai báo kiểu real, 60 là số kiểu interge vì vậy trình biên dịch đổi thành số thực 60.0. - Ngữ nghĩa: của một ngôn ngữ lập trình liên quan đến: + Kiểu, phạm vi của hằng và biến + Phân biệt và sử dụng đúng tên hằng, tên biến, tên hàm Chương trình dịch phải kiểm tra được tính đúng đắn trong sử dụng các đại lượng này. Ví dụ kiểm tra không cho gán giá trị cho hằng, kiểm tra tính đúng đắn trong gán kiểu, kiểm tra phạm vi, kiểm tra sử dụng tên như tên không được khai báo trùng, dùng cho gọi hàm phải là tên có thuộc tính hàm, . . . 4) Sinh mã trung gian: Sinh chương trình rong ngôn ngữ trung gian nhằm: dễ sinh và tối ưu mã hơn dễ chuyển đổi về mã máy hơn. sau giai đoạn phân tích thì mã trung gian sinh ra như sau: temp1 := 60 temp2 := id3 * temp1 temp3 := id2 + temp 2 id1 := temp3 (1.2) (trong đó id1 là position; id2 là initial và id3 là rate) 5). Tối ưu mã: Sửa đổi chương trình trong ngôn ngữ trung gian hằm cải tién chương trình đích về hiệu năng. Ví dụ như với mã trung gian ở (1.2), chúng ta có thể làm tốt hơn đoạn mã để tạo ra được các mã máy chạy nhanh hơn như sau: temp1 := id3 * 60 id1 := id2 + temp1 (1.3) 6). Sinh mã: tạo ra chương trình đích từ chương trình trong ngôn ngữ trung gian đẫ tối ưu. Thông thường là sinh ra mã máy hay mã hợp ngữ. Vấn đề quyết định là việc gán các biến cho các thanh ghi. Chẳng hạn sử dụng các thanh ghi R1 và R2, các chỉ thị lệnh MOVF, MULF, ADDF, chúng ta sinh mã cho (1.3) như sau: MOVF id3, R2 MULF #60, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1 (1.4) Ngoài ra, chương trình dịch còn phải thực hiện nhiệm vụ: * Quản lý bảng ký hiệu: Để ghi lại các kí hiệu, tên đã sử dụng trong chương trình nguồn cùng các thuộc tính kèm theo như kiểu, phạm vi, giá trị để dùng cho các bước cần đến.
Tõ tè(token) + Thuéc tÝnh (kiÓu, ®Þa chØ lu tr÷) = B¶ng ký hiÖu (Symbol table). Trong quá trình phân tích từ vựng, các tên sẽ được lưu vào bảng ký hiệu, sau đó từ giai đoạn phân tích ngữ nghĩa các thông tin khác như thuộc tính về tên (tên hằng, tên biến, tên hàm) sẽ được bổ sung trong các giai đoạn sau. - Giai đoạn phân tích từ vựng: lưu trữ trị từ vựng vào bảng kí hiệu nếu nó chưa có. - Giai đoạn còn lại: lưu trữ thuộc tính của từ vựng hoặc truy xuất các thông tin thuộc tính cho từng giai đoạn. Bảng kí hiệu được tổ chức như cấu trúc dữ liệu với mỗi phần tử là một mẩu tin dùng để lưu trữ trị từ vựng và các thuộc tính của nó. - Trị từ vựng: tên từ tố. - Các thuộc tính: kiểu, tầm hoạt động, số đối số, kiểu của đối số VÝ dô: var position, initial, rate : real th× thuéc tÝnh kiÓu real cha thÓ x¸c ®Þnh. C¸c giai ®o¹n sau ®ã nh ph©n tÝch ng÷ nghÜa vµ sinh m· trung gian míi ®a thªm c¸c th«ng tin nµy vµo vµ sö dông chóng. Nãi chung giai ®o¹n sinh m· sÏ sö dông b¶ng ký hiÖu ®Ó gi÷ c¸c th«ng tin chi tiÕt vÒ danh biÓu. * Xử lý lỗi: Khi phát hiện ra lỗi trong quá trình dịch thì nó ghi lại vị trí gặp lỗi, loại lỗi, những lỗi khác có liên quan đến lỗi này để thông báo cho người lập trình. Mçi giai ®o¹n cã thÓ cã nhiÒu lçi, tïy thuéc vµo tr×nh biªn dÞch mµ cã thÓ lµ: - Dõng vµ th«ng b¸o lçi khi gÆp lçi dÇu tiªn (Pascal). - Ghi nhËn lçi vµ tiÕp tôc qu¸ tr×nh dÞch (C). + Giai ®o¹n ph©n tÝch tõ vùng: cã lçi khi c¸c ký tù kh«ng thÓ ghÐp thµnh mét token (vÝ dô: 15a, a@b, ) + Giai ®o¹n ph©n tÝch có ph¸p: Cã lçi khi c¸c token kh«ng thÓ kÕt hîp víi nhau theo cÊu tróc ng«n ng÷ (vÝ dô: if stmt then expr). + Giai ®o¹n ph©n tÝch ng÷ nghÜa b¸o lçi khi c¸c to¸n h¹ng cã kiÓu kh«ng ®óng yªu cÇu cña phÐp to¸n. * Giai đoạn phân tích có đầu vào là ngôn ngữ nguồn, đầu ra là ngôn ngữ trung gian gọi là kỳ trước (fron end). Giai đoạn tổng hợp có đầu vào là ngôn ngữ trung gian và đầu ra là ngô ngữ đích gọi là kỳ sau (back end).
Đối với các ngôn ngữ nguồn, ta chỉ cần quan tâm đến việc sinh ra mã trung gian mà không cần biết mã máy đích của nó. Điều này làm cho công việc đơn giản, không phụ thuộc vào máy đích. Còn giai đoạn sau trở nên đơn giản hơn vì ngôn ngữ trung gian thường thì gần với mã máy. Và nó còn thể hiện ưu điểm khi chúng ta xây dựng nhiều cặp ngôn ngữ. Ví dụ có n ngôn ngữ nguồn, muốn xây dựng chương trình dịch cho n ngôn ngữ này sang m ngôn ngữ đích thì chúng ta cần n*m chương trình dịch; còn nếu chúng ta xây dựng theo kiến trúc front end và back end thì chúng ta chỉ cần n+m chương trình dịch. 1.3.2. Cấu trúc động. Cấu trúc động (cấu trúc theo thời gian) cho biết quan hệ giữa các phần khi hoạt động. Các thành phần độc lập của chương trình có thể hoạt động theo 2 cách: lần lượt hay đồng thời. mỗi khi một phần nào đó của chương trình dịch xong toàn bộ chương trình nguồn hoặc chương trình trung gian thì ta gọi đó là một lần duyệt. * Duyệt đơn (duyệt một lần): một số thành phần của chương trình được thực hiện đồng thời. Bộ phân tích cú pháp đóng vai trò trung tâm, điều khiển cả chương trình. Nó gọi bộ phân tích từ vựng khi cần một từ tố tiếp theo và gọi bộ phân tích ngữ nghĩa khi muốn chuyển cho một cấu trúc cú pháp đã được phân tích. Bộ phân tích ngữ nghĩa lại đưa cấu trúc sang phần sinh mã trung gian để sinh ra các mã trong một Mã nguồn ngôn Phân tích ngữ trung gian cú pháp rồi đưa vào bộ tối ưu Phân tích từ vựng và sinh mã. Phân tích Phân tích từ vựng ngữ nghĩa Phân tích cú pháp Phân tích ngữ nghĩa Chương trình nguồn Sinh mã trung gian Sinh mã trung gian Tối ưu mã Sinh mã Tối ưu mã Chương trình đích Sinh mã đích mã đích
Chương trình dịch duyệt đơn Chương trình dịch duyệt nhiều lần * Duyệt nhiều lần: các thành phần trong chương trình được thực hiện lần lượt và độc lập với nhau. Qua mỗi một phần, kết quả sẽ được lưu vào thiết bị lưu trữ ngaòi để lại được đọc vào cho bước tiếp theo. Người ta chỉ muốn có một số ít lượt bởi vì mỗi lượt đều mất thời gian đọc và ghi ra tập tin trung gian. Ngược lại nếu gom quá nhiều giai đoạn vào trong một lượt thì phải duy trì toàn bộ chương trình trong bộ nhớ, vì 1 giai đoạn cần thông tin theo thứ tự khác với thứ tự nó được tạo ra. Dạng biểu diễn trung gian của chương trình lớn hơn nhiều so với ct nguồn hoặc ct đích, nên sẽ gặp vấn đề về bộ nhớ. Ưu và nhược điểm của các loại: Trong giáo trình này So sánh duyệt đơn duyệt nhiều lần chúng ta nghiên cứu các tốc độ tốt Kém giai đoạn của một bộ nhớ kém tốt chương trình dịch một độ phức tạp kém tốt cách riêng rẽ nhưng theo Các ứng dụng lớn Kém tốt thiết kế duyệt một lượt. 1.4. Môi trường biên dịch Chương trình dịch là 1 chương trình trong hệ thống liên hoàn giúp cho người lập trình có được một môi trường hoàn chỉnh để phát triển các ứng dụng của họ. Chương trình dịch trong hệ thống đó thể hiện trong sơ đồ sau:
Chương trình nguồn nguyên thủy Tiền xử lý Chương trình nguồn Chương trình dịch Chương trình đích hợp ngữ Assembler Mã máy định vị lại được Thư viện và Tải / Liên kết các file đối tượng định vị lại được Mã máy thật sự Hình 1.3: Hệ thống xử lý ngôn ngữ * Bộ tiền xử lý: Chuỗi kí tự nhập vào chương trình dịch là các kí tự của chương trình nguồn nhưng trong thực tế, trước khi là đầu vào của một chương trình dịch, toàn bộ file nguồn sẽ được qua một thậm chí một vài bọo tiền xử lý. Sản phẩm của các bộ tiền xử lý này mới là chương trình nguồn thực sự của chương trình dịch. Bộ tiền xử lý sẽ thực hiện các công việc sau: - Xử lý Macro: Cho phep người dùng định nghĩa các macro là cách viết tắt của các cấu trúc dài hơn. - Chèn tệp tin: Bổ sung nội dung của các tệp tin cần dùng trong chương trình. Ví dụ : Trong ngôn ngữ Pascal có khai báo thư viện
“Uses crt;” bộ tiền xử lý sẽ chền tệp tin crt vào thay cho lời khai báo. - Bộ xử lý hoà hợp: hỗ trợ những ngôn ngữ xưa hơn bằng các cấu trúc dữ liệu hoặc dòng điều khiển hiện đại hơn. - Mở rộng ngôn ngữ: gia tăng khả năng của ngôn ngữ bằng các macro có sẵn. * Trình biên dịch hợp ngữ: Dịch các mã lệnh hợp ngữ thành mã máy. * Trình tải/ liên kết: Trình tải nhận các max máy khả tải định vị, thay đổi các địa chỉ khả tải định vị, đặt các chỉ thị và dữ liệu trong bộ nhớ đã được sửa đổi vào các vik trí phù hợp. Trình liên kết cho phép tạo ra một hcương rình từ các tệp tin thư viện hoặc nhiều tệp tin mã máy khả tải định vị mà chúng là kết quả của những biên dịch khác nhau.
CHƯƠNG 2 PHÂN TÍCH TỪ VỰNG 1. Vai trò của bộ phân tích từ vựng. 1.1. Nhiệm vụ. Bộ phân tích từ vựng có nhiệm vụ là đọc các kí tự vào từ văn bản chương trình nguồn và phân tích đưa ra danh sách các từ tố (từ vựng và phân loại cú pháp của nó) cùng một số thông tin thuộc tính. Đầu ra của bộ phân tích từ vựng là danh sách các từ tố và là đầu vào cho phân tích cú pháp. Thực tế thì phân tích cú pháp sẽ gọi lần lượt mỗi từ tố từ bộ phân tích để xử lý, chứ không gọi một lúc toàn bộ danh sách từ tố của cả chương trình nguồn. Khi nhận được yêu cầu lấy một từ tố tiếp theo từ bộ phân tích cú pháp, bộ phân tích từ vựng sẽ đọc kí tự vào cho dến khi đưa ra được một từ tố. yêu cầu lấy từ tố tiếp theo chương trình nguồn Phân tích Phân tích từ vựng cú pháp từ tố Bảng ký hiệu Hinh 2.4: Sơ đồ phân tích từ tố 1.2. Quá trình phân tích từ vựng 1). Xóa bỏ kí tự không có nghĩa (các chú thích, dòng trống, kí hiệu xuống dòng, kí tự trống không cần thiết) Quá trình dịch sẽ xem xét tất cả các ký tự trong dòng nhập nên những ký tự không có nghĩa (khoảng trắng (blanks, tabs, newlines) hoặc lời chú thích phải bị bỏ qua. Khi bộ phân tích từ vựng bỏ qua các khoảng trắng này thì bộ phân tích cú pháp không bao giờ quan tâm đến nó nữa. 2). Nhận dạng các kí hiệu: nhận dạng các từ tố.
Ví dụ ghép các chữ số để được một số và sử dụng nó như một đơn vị trong suốt quá trình dịch. Đặt num là một token biểu diễn cho một số nguyên. Khi một chuỗi các chữ số xuất hiện trong dòng nhập thì bộ phân tích sẽ gửi cho bộ phân tích cú pháp num. Giá trị của số nguyên đã được chuyển cho bộ phân tích cú pháp như là một thuộc tính của token num. 3). Số hoá các kí hiệu: Do con số xử lý dễ dàng hơn các xâu, từ khoá, tên, nên xâu thay bằng số, các chữ số được đổi thành số thực sự biểu diễn trong máy. Các tên được cất trong danh sách tên, các xâu cất trong danh sách xâu, các chuỗi số trong danh sách hằng số. 1.2. Từ vị (lexeme), từ tố (token), mẫu (patter). * Từ vị: là một nhóm các kí tự kề nhau có thể tuân theo một quy ước (mẫu hay luật) nào đó. * Từ tố: là một thuật ngữ chỉ các từ vựng có cùng ý nghĩa cú pháp (cùng một luật mô tả). - Đối với ngôn ngữ lập trình thì từ tố có thể được phân vào các loại sau: + từ khoá + tên của hằng, hàm, biến + số + xâu ký tự + các toán tử + các ký hiệu. Ví dụ: position := initial + 10 * rate ; ta có các từ vựng position, :=, initial, +, 10, *, rate, ; trong đó position, initial, rate là các từ vựng có cùng ý nghĩa cú pháp là các tên. := là phép gán + là phép cộng * là phép nhân 10 là một con số ; là dấu chấm phẩy Như vậy trong câu lệnh trên có 8 từ vựng thuộc 6 từ tố. Phân tích cú pháp sẽ làm việc trên các từ tố chứ không phải từ vựng, ví dụ như là làm việc trên khái niệm một số chứ không phải trên 5 hay 2; làm việc trên khái niệm tên chứ không phải là a, b hay c. * Thuộc tính của từ tố: Một từ tố có thể ứng với một tập các từ vị khác nhau, ta buộc phải thêm một số thông tin nữa để khi cần có thể biết cụ thể đó là từ vị nào. Ví dụ: 15 và 267 đều là một chuỗi số có từ tố là num nhưng đến bộ sinh mã phải biết cụ thể đó là số 15 và số 267.
Thuộc tính của từ tố là những thông tin kết hợp với từ tố đó. Trong thực tế, một từ tố sẽ chứa một con trỏ trỏ đến một vị trí trên bảng kí hiệu có chứấcc thông tin về nó. Ví dụ: position := initial + 10 * rate ; ta nhận được dãy từ tố: * Mẫu (luật mô tả - patter): Để cho bộ phân tích từ vựng nhận dạng được các từ tố, thì đối với mỗi từ tố chúng ta phải mô tả đặc điểm để xác định một từ vựng có thuộc từ tố đó không, mô tả đó được gọi là mẫu từ tố hay luật mô tả. Token Trị từ vựng MÉu (luËt m« t¶) const const const if if if hoÆc quan hÖ ,>,> hoÆc >= (relation) = më ®Çu lµ ch÷ c¸i theo sau lµ ch÷ tªn (id) pi, count, d2 c¸i, ch÷ sè Sè (num) 3.1416, 0, 5 bÊt kú h»ng sè nµo X©u (literal) "hello" bÊt kú c¸c character n»m gi÷a " vµ " ngo¹i trõ " Ta có thể coi: từ vị giống các từ cụ thể trong từ điển như nhà, cửa từ tố gần giống khái niệm từ loại như danh từ động từ Các mẫu (luật mô tả) dùng để nhận dạng loại từ tố, giống như những quy định để nhận dạng một từ là danh từ hay động từ Trị từ vựng được so cùng với mẫu của từ tố là chuỗi kí tự và là đơn vị của từ vựng. Khi đọc chuỗi kí tự của chương trình nguồn bộ phân tích từ vựng sẽ so sánh chuỗi kí tự đó với mẫu của từ tố nếu phù hợp nó sẽ đoán nhận được từ tố đó và đưa từ tố vào bảng kí hiệu cùng với trị từ vưng của nó. 1.4. Cách lưu trữ tạm thời chươ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: 1. Cặp bộ đệm (buffer pairs)
* Cấu tạo: - Chia buffer thành 2 nửa, một 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ố. E = M * C * * 2 EOF * Hoạt động: - Đọc n kí tự vào nửa đầu của buffer, 2 con trỏ trùng nhau tại vị trí bắt đầu. - Con trỏ p2 tiến sang phải cho tới khi xác định được một từ tố có từ vị là chuỗi kí tự nằm giữa 2 con trỏ. Dời p1 lên trùng với p2, tiếp tục dò tìm từ tố mới. - khi p2 ở cuối nửa đầu của buffer thì đọc tiếp n kí tự vào nửa đầu thứ 2. Khi p2 nằm ở nửa cuối của buffer thì đọc tiếp n kí tự vào nửa đầu của buffer và p2 được dời về đầu của bộ đệm. - Nếu số kí tự trong chương trình nguồn còn lại ít hơn n thì một kí tự đặc biệt đượ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. * Giải thuật hình thức 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 thứ hai then begin Đọc vào nửa đầu. p2 := p2 + 1; end else p2 := p2 + 2 2. Phương pháp cầm canh. Phương pháp trên mỗi lần di chuyển p2 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 2 lần test. Khắc phục: - Mỗi lần chí đọc n-1 kí tự vào mỗi nửa buffer còn kí tự thứ n là kí tự đặc biệt (thường là EOF). Như vậy ta chỉ cần một lần test. E = M * EOF C * * 2 EOF EOF Giải thuật: 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 cuối then begin Đọc vào nửa đầu; Dời p2 vào đầu của nửa đầu end else /* eof ở giữa chỉ hết chơng trình nguồn */ kết thúc phân tích từ vựng end
2. XÁC ĐỊNH TỪ TỐ. 2.1. Biểu diễn từ tố Cách biểu diễn các luật đơn giản nhất là biểu diễn bằng lời. Tuy nhiên cách này thường gặp hiện tượng nhập nhằng ( cùng một lời nói có thể hiểu theo nhiều nghĩa khác nhau), phát biểu theo nhièu cách khác nhau khó đưa vào máy tính. Các từ tố khác nhau có các mẫu hay luật mô tả khác nhau. Các mẫu này là cơ sở để nhận dạng các từ tố. Ta cần thiết phải hình thức hoá các mẫu này để làm sao có thể lập trình được. Việc này có thể thực hiện được nhờ biểu thức chính qui và ôtômát hữu hạn. Ngoài ra ta có thể dùng cách biểu diễn trực quan của văn phạm phi ngữ cảnh là đồ thị chuyển để mô tả các loại từ tố. 2.1.1. Một số khái niệm về ngôn ngữ hình thức. 2.1.1.1. Kí hiệu, Xâu, ngôn ngữ. * Bảng chữ cái: là một tập Σ ≠ ∅ hữu hạn hoặc vô hạn các đối tượng. Mỗi phần tử a ∈Σ gọi là kí hiệu hoặc chữ cái (thuộc bảng chữ cái Σ ). * Xâu: Là một dãy liên tiếp các kí hiệu thuộc cùng một bảng chữ cái. - Độ dài xâu: là tổng vị trí của tất cả các kí hiệu có mặt trong xâu, kí hiệu là | w|. - Xâu rỗng: là từ có độ dài = 0 kí hiệu là ε hoặc ∧. Độ dài của từ rỗng = 0. - Xâu v là Xâu con của w nếu v được tạo bởi các ký hiệu liền kề nhau trong w. * Tập tất cả các từ trên bảng chữ cái Σ kí hiệu là Σ *. Tập tất cả các từ khác + * + rỗng trên bảng chữ cái Σ kí hiệu là Σ . Σ = Σ ∪ {ε } * Tiền tố: của một xâu là một xâu con bất kỳ nằm ở đầu xâu. Hậu tố của một xâu là xâu con nằm ở cuối xâu. (Tiền tố và hậu tố của một xâu khác hơn chính xâu đó ta gọi là tiền tố và hậu tố thực sự) * Ngôn ngữ: Một ngôn ngữ L là một tập các chuỗi của các ký hiệu từ một bộ chữ cái Σ nào đó. (Một tập con A ⊆ Σ * được gọi là một ngôn ngữ trên bảng chữ cái Σ ). - Tập rỗng được gọi là ngôn ngữ trống (hay ngôn ngữ rỗng). Ngôn ngữ rỗng là ngôn ngữ trên bất kỳ bảng chữ cái nào. (Ngôn ngữ rỗng khác ngôn ngữ chỉ gồm từ rỗng: ngôn ngữ ∅ không có phần tử nào trong khi ngôn ngữ {ε } có một phần tử là chuỗi rỗng ε ) * Các phép toán trên ngôn ngữ. * + Phép giao: L = L1 ∩ L2 = {x ∈Σ | x∈L1 hoặc x ∈L2} * + Phép hợp: L = L1 ∪ L2 = {x ∈Σ | x∈L1 và x ∈L2} + Phép lấy phần bù của ngôn ngữ L là tập CL = { x ∈Σ * | x ∉L} + Phép nối kết (concatenation) của hai ngôn ngữ L1/ Σ 1 và L2/Σ 2 là : L1L2 = {w1w2 | w1∈ L1 và w2 ∈ L2 }/ Σ 1 ∪ Σ 2
Ký hiệu Ln = L.L.L L (n lần). Li = LLi - 1. - Trường hợp đặc biệt : L0 = {ε }, với mọi ngôn ngữ L. + Phép bao đóng (closure) : + Bao đóng (Kleene) của ngôn ngữ L, ký hiệu L* là hợp của mọi tập tích trên L: L* = ∞ ∪Ii= 0 Li + Bao đóng dương (positive) của ngôn ngữ L, ký hiệu L+ được định nghĩa là + I hợp của mọi tích dương trên L : L: L = ∞∪i = 1 L 2.1.1.2. Văn phạm. * Định nghĩa văn phạm. (văn phạm sinh hay văn phạm ngữ cấu) - Là một hệ thống gồm bốn thành phần xác định G = (Σ , ∆ , P, S), trong đó: Σ : tập hợp các ký hiệu kết thúc (terminal). ∆ : tập hợp các biến hay ký hiệu chưa kết thúc (non terminal) (với Σ ∩ ∆ = ∅) P : tập hữu hạn các quy tắc ngữ pháp được gọi là các sản xuất (production), mỗi sản xuất biểu diễn dưới dạng α → β , với α , β là các chuỗi ∈ (Σ ∪ ∆ )*. S ⊂ ∆ : ký hiệu chưa kết thúc dùng làm ký hiệu bắt đầu (start) Quy ước: - Dùng các chữ cái Latinh viết hoa (A, B, C, ) để chỉ các ký hiệu trong tập biến ∆ . - Các chữ cái Latinh đầu bảng viết thường (a, b, c, ) chỉ ký hiệu kết thúc thuộc tập Σ - Xâu thường được biểu diễn bằng các chữ cái Latinh cuối bảng viết thường (x, y, z, ). * Phân loại Chosmky. - Lớp 0: là văn phạm ngữ cấu (Phrase Structure) với các luật sản xuất có dạng: α -> β với α ∈ V+, β ∈ V* - Lớp 1: là văn phạm cảm ngữ cảnh (Context Sensitive) với các luật sản xuất có dạng: α -> β với α ∈ V+, β ∈ V* , |α| α với A ∈ N, α ∈ V* - Lớp 3: là văn phạm chính qui (Regular Grammar) với luật sản xuất có dạng: A -> a, A -> Ba hoặc A-> a, A-> aB với A, B ∈ N và a ∈ T Các lớp văn phạm được phân loại theo thứ tự phạm vi biểu diễn ngôn ngữ giảm dần, lớp văn phạm sau nằm trong phạm vi của lớp văn phạm trước: Lớp 0 ∈ Lớp 1 ∈ Lớp 2 ∈ Lớp 3 2.1.1.3. Văn phạm chính quy và biểu thức chính quy. * Văn phạm chính quy: Ví dụ 1: Tên trong ngôn ngữ Pascal là một từ đứng đầu là chữ cái, sau đó có thể là không hoặc nhiều chữ cái hoặc chữ số.
Biểu diễn bằng BTCQ: tên -> chữ_cái (chữ_cái | chữ_số)* Biểu diễn bằng văn phạm chính qui: Tên -> chữ_cái A; A -> chữ_cái A | chữ_số A | ε * Biểu thức chính qui được định nghĩa trên bộ chữ cái ∑ như sau: - ε là biểu thức chính quy, biểu thị cho tập {ε } - a ∈ ∑, a là biểu thức chính quy, biểu thị cho tập {a} - Giả sử r là biểu thức chính quy biểu thị cho ngôn ngữ L(r), s là biểu thức chính quy, biểu thị cho ngôn ngữ L(s) thì: + (r)|(s) là biểu thứcchính quy biểu thị cho tập ngôn ngữ L(r) ∪ L(s) + (r)(s) là biểu thức chính quy biểu thị cho tập ngôn ngữ L(r)L((s) + (r)* là biểu thức chính quy biểu thị cho tập ngôn ngữ L(r)* Biểu thức chính quy sử dụng các ký hiệu sau: | là ký hiệu hoặc (hợp) ( ) là ký hiệu dùng để nhóm các ký hiệu * là lặp lại không hoặc nhiều lần + là lặp lại một hoặc nhiều lần ! là lặp lại không hoặc một lần Ví dụ 2: Viết biểu thức chính qui và đồ thị chuyển để biểu diễn các xâu gồm các chữ số 0 và 1, trong đó tồn tại ít nhất một xâu con “11” Biểu thức chính qui: (0|1)*11(0|1)* Biểu diễn biểu thức chính quy dưới dạng đồ thị chuyển: 0 0|1 0|1 start 1 1 1 0|1 0 2 2 start 1 1 1 0 2 2 0 Đồ thị chuyển đơn định Đồ thị chuyển không đơn định 2.1.1.3. Ôtômát hữu hạn. * Định nghĩa: Một Otomat hữu hạn đơn định là một hệ thống M = (∑, Q, δ , q0, F), trong đó: • ∑ là một bộ chữ hữu hạn, gọi là bộ chữ vào • Q là một tập hữu hạn các trạng thái • q0 ∈ Q là trạng thái đầu
• F ∈ Q là tập các trạng thái cuối δ là hàm chuyển trạng thái δ có dạng: • δ : Q x ∑ -> Q thì M gọi là ôtômát mát đơn định (kí hiệu ÔHĐ). • δ : Q x ∑ -> 2Q thì M gọi là ôtômát không đơn định (kí hiệu ÔHK). * Hình trạng: của một OHĐ là một xâu có dạng qx với q ∈ Q là trạng thái hiện thời và x ∈ ∑* là phần xâu vào chưa được đoán nhận. Ví dụ: ∑ = {0, 1}; Q = {q0, q1, q2}; q0 là trạng thái ban đầu; F={q2}. Hàm chuyển trạng thái được mô tả như bảng sau:(ÔHK) 0|1 δ 0 1 0|1 1 Q0 q0 q0, q1 start 1 q q q Q1 ∅ q2 0 1 2 Q2 q2 q2 Đồ thị chuyển không đơn định Hàm chuyển trạng thái ÔHĐ 0 0|1 1 δ 0 1 start 1 q q q Q0 q0 q1 0 1 2 Q1 q0 q2 0 Q2 q2 q2 Đồ thị chuyển đơn định 2.1.1. Biểu diễn từ tố bằng biểu thức chính quy. * Một số từ tố được mô tả bằng lời như sau: - Tên là một xâu bắt đầu bởi một chữ cái và theo sau là không hoặc nhiều chữ cái hoặc chữ số - Số nguyên bao gồm các chữ số - Số thực có hai phần: phần nguyên và phần thực là xâu các chữ số và hai phần này cách nhau bởi dấu chấm - Các toán tử quan hệ , >=, <>, = * Mô tả các mẫu từ tố trên bằng biểu thức chính qui: Tên từ tố → biểu thức chính quy biểu diễn từ tố đó. - chữ_cái → A|B|C| |Z|a|b|c| |z - chữ_số → 0|1||2|3|4|5|6|7|8|9
- Tên → chữ_cái (chữ_cái | chữ_số)* - Số nguyên → (chữ_số)+ - Số thực → (chữ_số)+.(chữ_số) - Toán tử quan hệ: + Toán tử bé hơn (LT): + Toán tử lớn hơn hoặc bằng (GE): >= + Toán tử bằng (EQ): = + Toán tử khác (NE): 3 ≠ 4 LT * = EQ 5 > = GE 6 7 ≠ 8 GT *
Để xây dựng một chương trình nhận dạng tất cả các loại từ tố này, chúng ta phải kết hợp các đồ thị này thành một đồ thị duy nhất: chữ_cái chữ_cái 2 0 1 tên * chữ_số chữ_số chữ_số chữ_số . ≠ 6 3 5 số thực * khác 4 số nguyên * 9 NE ≠ 10 LT * = 1 EQ 1 = > 1 1 GE 2 3 ≠ 14 GT * 2.1.3. Biểu diễn bởi OHĐ Với ví dụ trên chúng ta xây dựng ôtômát với các thông số như sau: Q = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14} F = {2,4,6,10,14} q0 = 0
hàm chuyển trạng thái được mô tả bởi bảng sau: ∂ chữ_cái chữ_số . khác 0 1 3 lỗi 7 11 12 lỗi 1 1 1 2 2 2 2 2 3 4 3 5 4 4 4 4 5 6 5 6 6 6 6 6 7 10 10 10 10 8 9 10 12 14 14 14 14 13 14 14 Các trạng thái ∈ F là trạng thái kết thúc Các trạng thái có dấu * là kết thúc trả về ký hiệu cuối cho từ tố tiếp theo 2.2. Viết chương trình cho đồ thị chuyển. 2.2.1. Lập bộ phân tích từ vựng bằng phương pháp diễn giải đồ thị chuyển. Đoạn chương trình mô tả việc nhận dạng từ tố bằng cách diễn giải đồ thị chuyển. Chúng sẽ sử dụng các hàm sau:. int IsDigit ( int c); // hàm kiểm tra một ký hiệu là chữ số int IsLetter ( int c); // hàm kiểm tra một ký hiệu là chữ cái int GetNextChar(); // hàm lấy ký tự tiếp theo enum Token {IDENT, INTEGER, REAL, LT, LE, GT, GE, NE, EQ, ERROR}; // hàm này trả về loại từ tố // từ vị nằm trong s Token GetNextToken(char *s) {int state=0; int i=0; while(1) { int c=GetNextChar(); switch(state) { case 0: if(IsLetter(c)) state=1;
else if(IsDigit(c)) state=3; else if(c==‘ ’) state=12; else return ERROR; s[i++]=c; break; case 1: if(IsLetter(c)||IsDigit(c)) state=1; else return ERROR; break; case 2: s[i]=0; GetBackChar(); return IDENT; case 3: if(IsLetter(c)) state=4; else if(IsDigit(c)) state=3; else if(c==‘.’) state=5; else return 4; s[i++]=c; break; case 4: s[i]=0; GetBackChar(); return INTEGER; case 5: if(IsDigit(c)) state=5; else state=6; s[i++]=0; break; case 6: s[i]=0; GetBackChar(); return REAL; case 7: if(c==‘=’) state=8; else if(c==‘>’) state=9; else state=10; s[i++]=c; break; case 8: s[i]=0; return LE; case 9: s[i]=0; return NE;
case 10: s[i]=0; GetBackChar(); return LE; case 11: s[i]=0; return EQ; case 12: if(c==‘=’) state=13; else state=14; s[i++]=c; break; case 13: s[i]=0; return GE; case 14: s[i]=0; return GT; } if(c==0) break; }// end while }// end function Nhận xét: Ưu điểm: chương trình dễ viết và trực quan đối với số lượng các loại từ tố là bé. Nhược điểm: gặp nhiều khó khăn nếu số lượng loại từ tố là lớn, và khi cần bổ sung loại từ tố hoặc sửa đổi mẫu từ tố thì chúng ta lại phải viết lại chương trình. Chú ý: Trong thực tế khi xây dựng bộ phân tích từ vựng, chúng ta phải nhận dạng các tên trong chương trình trình nguồn, sau đó dựa vào bảng lưu trữ để phân biệt cụ thể các từ khoá đối với các tên. 2.2.2. Lập bộ phân tích từ vựng bằng bảng. Để xây dựng chương trình bằng phương pháp này, điều cơ bản nhất là chúng ta phải xây dựng bảng chuyển trạng thái. Để tổng quát, thông tin của bảng chuyển trạng thái nên được lưu ở một file dữ liệu bên ngoài, như vậy sẽ thuận tiện cho việc chúng ta thay đổi dữ liệu chuyển trạng thái của ôtômát mà không cần quan tâm đến chương trình. Đối với các trạng thái không phải là trạng thái kết thúc thì chúng ta chỉ cần tra bảng một cách tổng quát sẽ biết được trạng thái tiếp theo, và do đó chúng ta chỉ cần thực hiện các trường hợp cụ thể đối với các trạng thái kết thúc để biết từ tố cần trả về là gì. Giả sử ta có hàm khởi tạo bảng trạng thái là: int InitStateTable(); Hàm phân loại ký hiệu đầu vào (ký hiệu kết thúc): int GetCharType(); Khi đó đoạn chương trình sẽ được mô tả như dưới đây: #define STATE_NUM 100
#define TERMINAL _NUM 100 #define STATE_ERROR –1 // trạng thái lỗi int table[STATE_NUM][TERMINAL_NUM] // ban đầu gọi hàm khởi tạo bảng chuyển trạng thái. InitStateTable(); int GetNextChar(); // hàm lấy ký tự tiếp theo enum Token {IDENT, INTEGER, REAL, LT, LE, GT, GE, NE, EQ, ERROR}; // hàm này trả về loại từ tố // từ vị nằm trong s Token GetNextToken(char *s) { int state=0; int i=0; while(1) { int c=GetNextChar(); int type=GetCharType(c); switch(state) { case 2: s[i]=0; GetBackChar(); return IDENT; case 4: s[i]=0; GetBackChar(); return INTEGER; case 6: s[i]=0; GetBackChar(); return REAL; case 8: s[i]=0; return LE; case 9: s[i]=0; return NE; case 10: s[i]=0; GetBackChar(); return LE; case 11: s[i]=0; return EQ; case 13: s[i]=0; return GE; case 14: s[i]=0; return GT; case STATE_ERROR: return ERROR; defaulf: state=table[state][type]; s[i++]=c; } if(c==0) break; }// end while }// end function
Nhận xét: Ưu điểm: + Thích hợp với bộ phân tích từ vựng có nhiều trạng thái, khi đó chương trình sẽ gọn hơn. + Khi cần cập nhật từ tố mới hoặc sửa đổi mẫu từ tố thì chúng ta chỉ cần thay đổi trên dữ liệu bên ngoài cho bảng chuyển trạng thái mà không cần phải sửa chương trình nguồn hoặc có sửa thì sẽ rất ít đối với các trạng thái kết thúc. Nhược điểm: khó khăn cho việc lập bảng, kích thước bảng nhiều khi là quá lớn, và không trực quan. 3. XÁC ĐỊNH LỖI TRONG PHÂN TÍCH TỪ VỰNG. Chỉ có rất ít lỗi được phát hiện trong lúc phân tích từ vựng, vì bộ phân tích từ vựng chỉ quan sát chương trình nguồn một cách cục bộ, không xét quan hệ cấu trúc của các từ với nhau. Ví dụ: khi bộ phân tích từ vựng gặp xâu fi trong biểu thức fi a= b then . . . thì bộ phân tích từ vựng không thể cho biết rằng fi là từ viết sai của từ khoá if hoặc là một tên không khai báo. Nó sẽ nghiễm nhiên coi rằng fi là một tên đúng và trả về một từ tố tên. Chú ý lỗi này chỉ được phát hiện bởi bộ phân tích cú pháp. Các lỗi mà bộ phân tích từ vựng phát hiện được là các lỗi về một từ vị không thuộc một loại từ tố nào, ví dụ như gặp từ vị 12xyz. Bé xö lý lçi ph¶i ®¹t môc ®Ých sau: - Th«ng b¸o lçi mét c¸ch râ rµng vµ chÝnh x¸c. - Phôc håi lçi mét c¸ch nhanh chãng ®Ó x¸c ®Þnh lçi tiÕp theo. - Kh«ng lµm chËm tiÕn tr×nh cña mét ch¬ng tr×nh ®óng. Khi gặp những lỗi có 2 cách xử lý: + Hệ thống sẽ ngừng hoạt động và báo lỗi cho người sử dụng. + Bộ phân tích từ vựng ghi lại các lỗi và cố gắng bỏ qua chúng để hệ thống tiếp tục làm việc, nhằm phát hiện đồng thời thêm nhiều lỗi khác. Mặt khác, nó còn có thể tự sửa (hoặc cho những gợi ý cho những từ đúng đối với từ bị lỗi). Cách khắc phục là: - Xoá hoặc nhảy qua kí tự mà bộ phân tích từ vựng không tìm thấy từ tố (panic mode). - Thêm kí tự bị thiếu. - Thay một kí tự sai thành kí tự đúng.
- Tráo 2 kí tự đứng cạnh nhau. 4. CÁC BƯỚC ĐỂ XÂY DỰNG BỘ PHÂN TÍCH TỪ VỰNG. Các bước tuần tự nên tiến hành để xây dựng được một bộ phân tích từ vựng tốt, hoạt động chính xác và dễ cải tiến, bảo hành, bảo trì. 1) Xác định các luật từ tố, các luật này được mô tả bằng lời. 2) Vẽ đồ thị chuyển cho từng mẫu một, trước đó có thể mô tả bằng biểu thức chính qui để tiện theo dõi và chỉnh sửa, và dễ dàng cho việc dựng đồ thị chuyển. 3) Kết hợp các luật này thành một đồ thị chuyển duy nhất. 4) Chuyển đồ thị chuyển thành bảng. 5) Xây dựng chương trình. 6) Bổ sung thêm phần báo lỗi để thành bộ phân tích từ vựng hoàn chỉnh. Bài tập 1. Phân tích các chương trình pascal và C sau thành các từ tố và thuộc tính tương ứng. a) pascal: Function max(i,j:integer): Integer; {Trả lại số lon nhất trong 2 số nguyên i, j } Begin If i>j then max:=i; Else max:=j; End; B) C: Int max(int i, int j) /* Trả lại số lon nhất trong 2 số nguyên i, j*/ {return i>j?i:j;} Hãy cho biết có bao nhiêu từ tố được đưa ra và chia thành bao nhiêu loại? 2. Phân tích các chương trình pascal và c sau thành các từ tố và thuộc tính tương ứng. a) pascal var i,j; begin for i= 0 to 100 do j=i; write(‘i=’, ‘j:=’,j); end; B) C: Int i,j: Main(void {
for (i=0; i=100;i++) printf(“i=%d;”,i,”j=%d”,j= =i); } 3. Mô tả các ngôn ngữ chỉ định bởi các biểu thức chính quy sau: a. 0(0|1)*0 b.((ε |0)1*)* 4. Viết biểu thức chính quy cho: tên, số nguyên, số thực, char, string trong pascal. Xây dựng đồ thị chuyển cho chúng. Sau đó, kết hợp chúng thành đồ thị chuyển duy nhất. 5. Dựng đồ thị chuyển cho các mô tả dưới đây. a. Tất cả các xâu chữ cái có 6 nguyên âm a, e, i, o, u, y theo thứ tự. Ví dụ: “abeiptowwrungfhy” b. tất cả các xâu số không có một số nào bị lặp. c. tất cả các xâu số có ít nhất một số nào bị lặp. d. tất cả các xâu gồm 0,1, không chứa xâu con 011. Bài tập thực hành Bài 1: Xây dựng bộ phân tích từ vựng cho ngôn ngữ pascal chuẩn. Bài 2: Xây dựng bộ phân tích từ vựng cho ngôn ngữ C chuẩn.
CHƯƠNG 3 PHÂN TÍCH CÚ PHÁP VÀ CÁC PHƯƠNG PHÁP PHÂN TÍCH CƠ BẢN. 1. MỤC ĐÍCH. Phân tích cú pháp nhận đầu vào là danh sách các từ tố của chương trình nguồn thành các thành phần theo văn phạm và biểu diễn cấu trúc này bằng cây phân tích hoặc theo một cấu trúc nào đó tương đương với cây. Chương yêu cầu trình nguồn từ tố Phân tích Phân tích Phân tích từ vựng cú pháp ngữ nghĩa từ tố Bảng ký hiệu Bộ phân tích cú pháp nhận chuỗi các token từ bộ phân tích từ vựng và tạo ra cây phân tích cú pháp. Trong thực tế còn một số nhiệm vụ thu nhập thông tin về token vào bảng ký hiệu, thực hiện kiểm tra kiểu về phân tích ngữ nghĩa cũng như sinh mã trung gian. Các phần này sẽ được trình bày trong các chương kế. 2. HOẠT ĐỘNG CỦA BỘ PHÂN TÍCH. 2.1.Văn phạm phi ngữ cảnh. 2.1.1. Định nghĩa. * Định nghĩa: Văn phạm PNC (như trên). * Dạng BNF (Backus – Naur Form) của văn phạm phi ngữ cảnh + Các ký tự viết hoa: biểu diễn ký hiệu không kết thúc, (có thể thay bằng một xâu đặt trong dấu ngoặc hoặc một từ in nghiêng). + Các ký tự viết chữ nhỏ và dấu toán học: biểu diễn các ký hiệu kết thúc (có thể thay bằng một xâu đặt trong cặp dấu nháy kép “ ” hoặc một từ in đậm). + ký hiệu -> hoặc = là: ký hiệu chỉ phạm trù cú pháp ở vế trái được giải thích bởi vế phải. + ký hiệu | chỉ sự lựa chọn. Ví dụ: = | | “(” “)” hoặc ToánHạng -> Tên | Số | ( BiểuThức
2.1.2. Đồ thị chuyển biểu diễn văn phạm phi ngữ cảnh: - Các vòng tròn với ký hiệu chu bên trong biểu thị cho trạng thái. cai Các chữ trên các cung biểu thị Start cho ký hiệu vào tiếp theo. Trạng chu cai khac 2 0 1 thái vẽ bằng một vòng tròn kép là * trạng thái kết thúc. chu cai Nếu trạng thái kết thúc có dấu * nghĩa là ký hiệu cuối không Hình 2.1: Đồ thị chuyển cho từ tố Tên thuộc xâu đoán nhận. 2.1.3. Cây suy dẫn. 2.1.3.1. Suy dẫn. Cho văn phạm G=(T,N,P,S). - Suy dẫn trực tiếp là một quan hệ hai ngôi ký hiệu => trên tập V* nếu αβγ là một xâu thuộc V* và β->δ là một sản xuất trong P, thì αβγ => αδγ. k k - Suy dẫn k bước, ký hiệu là => hay α =>β nếu tồn tại dãy α0, α1, . . . , αk sao cho: α = α0 => α1 => . . . => αk = β * - Xâu α suy dẫn xâu nếu k>=0 và ký hiệu là α =>β + - Xâu α suy dẫn không tầm thường xâu β nếu k>0 và ký hiệu là α =>β 2.1.3.2. C â y ph â n t í ch ( c â y suy dẫn ) * Định nghĩa: Cây phân tích trong một văn phạm phi ngữ cảnh G = (T,N,P,S) là một cây thỏa mãn các điều kiện sau: 1. Mọi nút có một nhãn, là một ký hiệu trong (T ∪ N ∪ {ε}) 2. Nhãn của gốc là S 3. Nếu một nút có nhãn X là một nút trong thì X ∈ N 4. Nếu nút n có nhãn X và các nút con của nó theo thứ tự trái qua phải có nhãn Y1, Y2, . . ., Yk thì X->Y1Y2 . . . Yk sẽ là một sản xuất ∈ P 5. Nút lá có nhãn thuộc T hoặc là ε * Suy dẫn trái nhất (nói gọn là suy dẫn trái), nếu ở mỗi bước suy dẫn, biến được thay thế là biến nằm bên trái nhất trong dạng câu. * Suy dẫn phải nhất: (nói gọn là suy dẫn phải), nếu ở mỗi bước suy dẫn, biến được thay thế là biến nằm bên phải nhất trong dạng câu. 2.1.3.3. Đệ qui
* Định nghĩa: Ký hiệu không kết thúc A của văn phạm gọi là đệ qui nếu tồn + + tại: A =>αAβ với α, β ∈ V  Nếu α = ε thì A gọi là đệ qui trái.  Nếu β = ε thì A gọi là đệ qui phải.  Nếu α,β ∉ ε thì A gọi là đệ qui trong. * Có 2 loại dệ quy trái :  Loại ttrực tiếp: có dạng A → Aα ( A ⇒+ Aα )  Loại gián tiếp: Gây ra do nhiều bước suy dẫn. (VÝ dô: S →Aa | b; A→Ac | Sd; S lµ ®Ö qui tr¸i v× S ⇒ Aa ⇒ Sda) * Loại bỏ đệ qui trái: (loại bỏ suy dẫn A =>+ Aα ) - Giả sử có luật đệ qui trái A->Aα | β chúng ta thay các luật này bằng các luật: A -> β A’ A’ -> α A’ | ε - Tổng quát hoá lên ta có: Nếu có các luật đệ qui trái: A -> Aα 1 | Aα 2 | . . .| Aα m | β 1 | β 2 | . . .| β n trong đó không β i nào bắt đầu bằng một A . Thay các sản xuất này bởi các sản xuất: A -> β 1A’ | β 2A’ | . . . | β nA’ A’ -> α 1A’ | α 2A’ | . . . | α mA’ | ε Ví dụ2: Xét văn phạm biểu thức số học sau: E -> E + T | T ; T -> T * F | F; F -> ( E ) | id Loại bỏ đệ qui trái trực tiếp cho các sản xuất của E rồi của T, ta được văn phạm mới không còn sản xuất có đệ qui trái như sau: E -> TE’; E’-> +TE’ | ε ; T -> FT’; T’ -> *FT’ | ε ;
F -> (E) | id Qui tắc này loại bỏ được đệ qui trái trực tiếp nằm trong các sản xuất nhưng không loại bỏ được đệ qui trái nằm trong các dẫn xuất có hai hoặc nhiều bước. Qui tắc này cũng không loại bỏ được đệ qui trái ra khỏi sản xuất A->A. Víi ®Ö qui tr¸i gi¸n tiÕp vµ nãi chung lµ ®Ö qui tr¸i, ta sö dông gi¶i thuËt sau: Input: Văn phạm không tuần hoàn hoặc e_sx (không có dạng Aị+A hoặc Ađe) Output: Văn phạm tương đương không đệ qui trái Phương pháp: 1. Sắp xếp các ký hiệu không kết thúc theo thứ tự A1, A2 An 2. For i:=1 to n do Begin for j:=1 to i-1 do Begin Thay luật sinh dạng Aiđ Aj bởi luật sinh Ajđ d 1g | d 2g | |d kg Trong đó Aj đd1g | d2g | |dky là các luật sinh hiện tại End Loại bỏ đệ qui trái trực tiếp trong số các Ai loại End; VÝ dô : Víi S → Aa | b; A→Ac | Sd. Sắp xếp các ký hiệu cha kết thúc theo thứ tự S,A Với i=1, không có đệ qui trái trực tiếp nên không có điều gì xảy ra. với i=2 , thay luật sinh AđSd được AđAc | Aad | bd. Loại bỏ đệ qui trái trực tiếp cho A, ta được: SđAa |b; AđbdA'; A'đ cA' | adA' | e * Phép thừa số hoá trái Thừa số hoá trái (left factoring) là một phép biến đổi văn phạm nhằm sinh ra một văn phạm thích hợp cho việc phân tích cú pháp không quay lui. Ý tưởng cơ bản là khi không rõ sản xuất nào trong trong hai sản xuất có cùng vế trái là A được dùng để khai triển A thì ta có thể viết lại các sản xuất này nhằm “hoãn lại quyết định”, cho đến khi có đủ thông tin để đưa ra được quyết định lựa chọn sản xuất nào. - Nếu có hai sản xuất A -> α β 1 | α β 2 thì ta không biết phải khai triển A theo α β 1 hay α β 2. Khi đó, thay hai sản xuất này bằng:
A -> α A’; A’ -> β 1 | β 2 Ví dụ: S -> iEtS | iEtSeS | a; E -> b Khi được thừa số hoá trái, văn phạm này trở thành: S -> iEtSS’ | a; S’ -> eS | ε ; E -> b vì thế khi cần khai triển S với ký hiệu xâu vào hiện tại là i, chúng ta có thể lựa chọn iEtSS’ mà không phải băn khoăn giữa iEtS và iEtSeS của văn phạm cũ. Gi¶i thuËt t¹o thõa sè ho¸ tr¸i (yÕu tè tr¸i) cho mét v¨n ph¹m: Input: Văn phạm G Output: Văn phạm tương đương với nhân tố trái. Ph ơng pháp: Với mỗi ký hiệu chưa kết thúc A, có các ký hiệu dẫn đầu các vế phải giống nhau, ta tìm một chuỗi a là chuỗi có độ dài lớn nhất chung cho tất cả các vế phải (a là nhân tố trái) Giả sử A → ab1| ab2| | abn | g Trong đó g không có chuỗi dẫn đầu chung với các vế phải khác. Biến đổi luật sinh thành A → a A' | g A' → b 1| b 2 | | b n 2.1.3.4. Nhập nhằng Một văn phạm G được gọi là văn phạm nhập nhằng nếu có một xâu α là kết quả của hai cây suy dẫn khác nhau trong G. Ngôn ngữ do văn phạm này sinh ra gọi là ngôn ngữ nhập nhằng. Ví dụ: Xét văn phạm G cho bởi các sản xuất sau: S -> S + S | S * S | ( S ) | a Với xâu vào là w = “a+a*a” ta có: Văn phạm này là nhập nhằng vì có hai cây đối với câu vào w như sau: S S S * S S + S S + S a a S * S a a a a
Chúng ta có ví dụ đối suy dẫn trái (đối với cây đầu tiên) là: S => S * S => S + S => S + S * S => a + S * S => a + a * S => a + a * a suy dẫn phải (đối với cây đầu tiên ) là: S => S * S => S * a => S + S * a => S + a * a => a + a * a. 2.2. các phương pháp phân tích. - Mọi ngôn ngữ lập trình đều có các luật mô tả các cấu trúc cú pháp. Một chương trình viết đúng phải tuân theo các luật mô tả này. Phân tích cú pháp là để tìm ra cấu trúc dựa trên văn phạm của một chương trình nguồn. - Thông thường có hai chiến lược phân tích: + Phân tích trên xuống (topdown): Cho một văn phạm PNC G = (Σ , ∆ , P, S) và một câu cần phân tích w. Xuất phát từ S áp dụng các suy dẫn trái, tiến từ trái qua phải thử tạo ra câu w. + Phân tích dưới lên (bottom-up): Cho một văn phạm PNC G = (Σ , ∆ , P, S) và một câu cần phân tích w. Xuất phát từ câu w áp dụng thu gọn các suy dẫn phải, tiến hành từ trái qua phải để đi tới kí hiệu đầu S. Theo cách này thì phân tích Topdown và LL(k) là phân tích trên xuống, phân tích Bottom- up và phân tích LR(k) là phân tích dưới lên. * Điều kiện để thuật toán dừng: + Phân tích trên xuống dừng khi và chỉ khi G kông có đệ quy trái. + Phân tích dưới lên dừng khi G không chứa suy dẫn A ⇒+ A và sản xuất A→ε . * Có các phương pháp phân tích. 1) Phương pháp phân tích topdown. 2) Phương pháp phân tích bottom up. 3) Phương pháp phân tích bảng CYK. 4) Phương pháp phân tích LL. 5) Phương pháp phân tích LR. Phương pháp 1 và 2: là các phương pháp cơ bản, kém hiệu quả. Phương pháp 5,6 là phương pháp phân tích hiệu quả. 2.3.1. phân tích topdown.
Phương pháp phân tích Top-down xây dựng cây phân tích cho một xâu vào bằng cách xuất phát từ ký hiệu bắt đầu làm gốc và sử dụng các luật sản xuất để đi từ gốc đến lá. - Đánh dấu thứ tự các lựa chọn của các sản xuất có cùng vế trái. Ví dụ nếu các sản xuất có dạng S -> aSbS | aS | c thì aSbS là lựa chọn thứ nhất, aS là lựa chọn thứ hai và c là lựa chọn thứ ba trong việc khai triển S. - Tại mỗi bước suy diễn, ta cần triển khai một ký hiệu không kết thúc A và văn phạm có các sản xuất có vế trái là A là A->α 1 | α 2 | . . .| α k Khi đó ta có k thứ tự lựa chọn, đánh dấu thứ tự lựa chọn các sản xuất sau đó khai triển A theo một lựa chọn, nếu quá trình phân tích là không thành công thì quay lui tại vị trí này và khai triển A theo lựa chọn tiếp theo. Phân tích Top-down là phương pháp phân tích có quay lui và tạo ra suy dẫn trái nhất. Ví dụ: Cho văn phạm S -> aSbS | aS | c Hãy phân tích xâu vào “aacbc” bằng thuật toán Top-down, vẽ cây phân tích trong quá trình phân tích quay lui. S S a S b S a S b S a S b S a S b S a S (2) * (1) a S S * b S S a S b S a S b S a S b S a S b S (4) c a S c a * S b S * (3)
S S b S a S b S a S a S a S b S (6) a S b S c * c * (5) S a S b S a S (7) a S *
S S S a S b S a S b S a S b S a S a S b S a S * (8) c a S a c S * 10 c (9) c 2.3.1.1. Mô tả thuật toán phân tích Top-down - Input: Văn phạm PNC G = (Σ , ∆ , P, S) không đệ quy trái, xâu w = a1, a2, an - Output: Cây phân tích từ trên xuống của xâu w (w ∈ L(G)), báo lỗi (w ∉ L(G)). - Method: Dùng một con trỏ chỉ đến xâu vào w. Ký hiệu trên xâu vào do con trỏ chỉ đến gọi là ký hiệu vào hiện tại. 1) Khởi tạo cây với gốc là S, con trỏ trỏ đến kí hiệu đầu tiên của xâu w là a1. 2) Nếu nút đang xét ∈ ∆ (là ký hiệu không kết thúc) A thì chọn sản xuất có vế trái là A trong P, giả sử sản xuất A → X1 Xk . + Nếu k > 0: lấy nút X1 làm nút đang xét. + Nếu k=0 (sản xuất rỗng) thì lấy nút ngay bên phải A làm nút đang xét. 3) Nếu nút đang xét ∈ Σ (là ký hiệu kết thúc) a thì đối sánh a với ký hiệu vào hiện tại. + Nếu trùng nhau: thì lấy nút ngay bên phải a làm nút đang xét, con trỏ dịch sang bên phải một ký hiệu trên xâu w. + Nếu không: quay lại nút trước đó và lặp lại b2 với thử lựa chọn tiếp theo. Thủ tục trên lặp lại sau hữu hạn bước và có 2 khả năng xảy ra: - Nếu gặp trường hợp đối sánh hết xâu vào và cây không còn nút nào chưa xét nữa thì ta được một cây phân tích. - Nếu đã quay lui hết tất cả các trường hợp mà không sinh được cây phân tích thì kết luận xâu vào không phân tích được bởi văn phạm đã cho.
* Điều kiện để một văn phạm phi ngữ cảnh phân tích được bởi thuật toán Top- down là văn phạm không có đệ qui trái. (Vì vậy ta phải thực hiện loại bỏ đệ quy trái trước khi phân tích văn phạm theo phương pháp topdown) * Độ phức tạp thuật toán là hàm số mũ n với n là độ dài xâu vào. 2.3.2. phân ttích bottom - up. Phương pháp phân tích Bottom-up về tư tưởng là ngược lại với phương pháp Top-down. - Xây dựng cú pháp cho xâu nhập bắt đầu từ lá lên tới gốc. Đây là quá trình rút gọn một xâu thành một kí hiệu mở đầu của văn phạm. Tại mỗi bước rút gọn, một xâu con bằng một xâu phải của một sản xuất nào đó thì xâu con này được thay thế bởi vế trái của sản xuất đó. (còn gọi là phương pháp gạt thu gọn - shift reduce parsing). Cã 2 vÊn ®Ò: x¸c ®Þnh handle vµ chän luËt sinh. * CÊu t¹o: - 1 STACK ®Ó lu c¸c ký hiÖu v¨n ph¹m. - 1 BUFFER INPUT ®Ó gi÷ chuçi cÇn ph©n tÝch w. - Dïng $ ®Ó ®¸nh dÊu ®¸y stack vµ cuèi chuçi nhËp. * Ho¹t ®éng: - Khëi ®Çu th× stack rçng vµ w n»m trong input buffer. Bé ph©n tÝch gạt lần lượt các ký hiệu đầu vào từ trái sang phải vào ngăn xếp đến khi nào đạt được một thu gọn thì thu gọn (thay thế vế phải xuất hiện trên đỉnh ngăn xếp bởi vế trái của sản xuất đó).Nếu có nhiều cách thu gọn tại một trạng thái thì lưu lại cho quá trình quay lui. Quá trình cứ tiếp tục, nếu dừng lại mà chưa đạt đến trạng thái kết thúc thì quay lại tại bước quay lui gần nhất. - Nếu quá trình đạt đến trạng thái ngăn xếp là $S và xâu vào là $ thì quá trình kết thúc và phân tích thành công. - Nếu đã xét hết tất cả các trường hợp, tức là không quay lui được nữa mà chưa đạt đến trạng thái kết thúc thì dừng lại và thông báo xâu vào không phân tích được bởi văn phạm đã cho. Ví dụ: S -> aABe; A -> Abc | b; B -> d; Phân tích câu vào “abbcde” quá trình phân tích Bottom-up như sau: Ngăn xếp Đầu vào Hành động $ abbcde$ gạt $a bbcde$ gạt $ab bcde$ thu gọn A -> b $aA bcde$ gạt $aAb cde$ thu gọn A -> b (2)
$aAA cde$ gạt $aAAc de$ gạt $aAAcd e$ thu gọn B -> d (1) $aAAcB e$ gạt $aAAcBe $ dừng, quay lui 1 (gạt) $aAAcde $ dừng, quay lui 2 (gạt) $aAbc de$ thu gọn A -> Abc $aA de$ gạt $aAd e$ thu gọn B -> d $aAB e$ gạt $aABe $ thu gọn S -> aABe $S $ chấp nhận Vẽ cây cho quá trình phân tích và quay lui trên, chúng ta có kết quả như sau: A A* B A A * a b b c d e a b b c d e Quá trình 1 Quá trình 2 S A A B a b b c d e (2c) Quá trình 3 Quá trình suy dẫn cũng có thể được viết lại như sau: Abbcde => aAbcde (A -> b) => aAde (A -> Abc) => aABe (B -> d) => S (S -> aABe) Nếu viết ngược lại chúng ta sẽ được dẫn xuất phải nhất: S =>rm aABe =>rm aAde =>rm aAbcde =>rm abbcde - Quá trình phân tích Bottom-up là quá trình sinh dẫn suất phải nhất
- Phân tích Bottom-up không phân tích được văn phạm có các sản xuất B->ε hoặc có suy dẫnA =>+ A * Handle của một chuỗi Handle của một chuỗi là một chuỗi con của nó và là vế phải của một sản xuất trong phép thu gọn nó thành ký hiệu vế trái của 1 sản xuất. Ví dụ: Trong ví dụ trên. Ngăn Đầu vào Hành động Handle Suy dẫn Tiền tố khả xếp phải tồn $ abbcde$ gạt $a bbcde$ gạt abbcde a $ab bcde$ thu gọn A -> b b abbcde ab $aA bcde$ gạt aAbcde aA $aAb cde$ thu gọn A -> b (2) b aAbcde aAb $aAA cde$ gạt $aAAc de$ gạt $aAAcd e$ thu gọn B -> d (1) d không phải là handle do áp dụng thu gọn này là không thành công $aAAcB e$ gạt $aAAcBe $ dừng, quay lui 1 (gạt) $aAAcde $ dừng, quay lui 2 (gạt) $aAbc de$ thu gọn A -> Abc Abc AAbcde $aA de$ gạt $aAd e$ thu gọn B -> d d AAde $aAB e$ gạt $aABe $ thu gọn S -> aABe $S $ chấp nhận Chú ý Handle là chuỗi mà chuỗi đó phải là một kết quả của suy dẫn phải từ S và phép thu gọn xảy ra trong suy dẫn đó. a a a $ i i+1 n Sản xuất A -> β Trên ngăn xếp chứa xâu y = α β , β là vế phải của một sản xuất W = a a a được bộ phân tích áp dụng để thu gọn và bước thu gọn này phải 1 2 n β β dẫn đến quá trình phân tích thành công thì là handle của chuỗi α β α v (v là phần chuỗi còn lại trên input buffer). Vậy nếu S =>*rm α Aw =>rm α β w thì β là handle của Stack suy dẫn phải α β w
Trong việc sử dụng ngăn xếp để phân tích cú pháp gạt thu gọn, handle luôn luôn xuất hiện trên đỉnh của ngăn xếp. * Tiền tố khả tồn (viable prefixes) Xâu ký hiệu trong ngăn xếp tại mỗi thời điểm của một quá trình phân tích gạt - thu gọn là một tiền tố khả tồn. Ví dụ: tại một thời điểm trong ngăn xếp có dữ liệu là α β và xâu vào còn lại là w thì α β w là một dạng câu dẫn phải và α β là một tiền tố khả tồn. 2.3.2.Phân tích LL. Tử tưởng của phương pháp phân tích LL là khi ta triển khai một ký hiệu không kết thúc, lựa chọn cẩn thận các sản xuất như thế nào đó để tránh việc quay lui mất thời gian.Tức là phải có một cách nào đó xác định dực ngay lựa chọn đúng mà không phải thử các lựa chọn khác. Thông tin để xác định lựa chọn dựa vào những gì đã biết trạng thái và kí hiệu kết thúc hiện tại. LL: là một trong các phương pháp phân tích hiệu quả, nó cũng thuộc chiến lược phân tích topdown nhưng nó hiệu quả ở chỗ nó là phương pháp phân tích không quay lui. - Bộ phân tích tất định: Các thuật toán phân tích có đặc điểm chung là xâu vào được quét từ trái sang phải và quá trình phân tích là hoàn toàn xác định, do đó ta gọi là bộ phân tích tất định. (Phân tích topdown và bottom – up có phải là phân tích tất định không? – không do quá trình phân tích là không xác định). L: left – to – right ( quét từ phải qua trái ) L : leftmosst – derivation (suy dẫn trái nhất); k là số ký hiệu nhìn trước để đưa ra quyết định phân tích. Giả sử ký hiệu không kết thúc A có các sản xuất: A -> α 1 | α 2 | . . . | α n thoả mãn tính chấ:t các xâu α 1, α 2, . . ., α n suy dẫn ra các xâu với ký hiệu tại vị trí đầu tiên là các ký hiệu kết thúc khác nhau, khi đó chúng ta chỉ cần nhìn vào ký hiệu đầu vào tiếp theo sẽ xác định được cần khai triển A theo α i nào. Nếu cần tới k ký hiệu đầu tiên thì mới phân biệt được các xâu α 1, α 2, . . ., α n thì khi đó để chọn luật sản xuất nào cho khai triển A chúng ta cần nhìn k ký hiệu đầu vào tiếp theo. Văn phạm LL(k) là văn phạm cho phép xây dựng bộ phân tích làm việc tất định nếu bộ phân tích này được phép nhìn k kí hiệu vào nằm ngay bên phải của vị trí vào hiện tại.
Ngôn ngữ sinh ra bởi văn phạm LL(k) là ngôn ngữ LL(k). Thông thường chúng ta xét với k=1. 2.3.2.1. First và follow. * First của một xâu: First(α ) cho chúng ta biết xâu α có thể suy dẫn đến tận cùng thành một xâu bắt đầu bằng ký hiệu kết thúc nào. Định nghĩa First( α ) First(α ) là tập chứa tất cả các ký hiệu kết thúc a mà a có thể là bắt đầu của một xâu được suy dẫn từ α + First(α ) = {a ∈ T | α =>* aβ } + ε ∈ First(α ) nếu α =>* ε Thuật toán tính First(X) với X là một ký hiệu văn phạm: 1. nếu X là ký hiệu kết thúc thì First(X) = {X} 2. nếu X -> ε là một sản xuất thì thêm ε vào First(X) 3. nếu X -> Y1 Yk là một sản xuất thì thêm First(Y1) vào First(X) trừ ε nếu First(Yt) chứa ε với mọi t=1, ,i với i AB; A -> aA | ε ; B -> bB | ε Hãy tính First của các ký hiệu S, A, B Kết quả: Fisrt(A) = {a, ε }; First(B) = {b,ε }; First(S) = {a,b,ε }
* Follow của một ký hiệu không kết thúc: Định nghĩa follow(A) A là kí hiệu không kết thúc. Follow(A) với A là ký hiệu không kết thúc là tập các ký hiệu kết thúc a mà chúng có thể xuất hiện ngay bên phải của A trong một số dạng câu. Nếu A là ký hiệu bên phải nhất trong một số dạng câu thì thêm $ vào Follow(A). + Follow(A) = {a∈T | ∃ S =>* α Aaβ } + $ ∈ Follow(A) khi và chỉ khi tồn tại suy dẫn S =>* α A Thuật toán tính Follow(A) với A là một ký hiệu không kết thúc 1. thêm $ vào Follow(S) với S là ký hiệu bắt đầu (chú ý là nếu ta xét một tập con với một ký hiệu E nào đó làm ký hiệu bắt đầu thì cũng thêm $ vào Follow(E)). 2. nếu có một sản xuất dạng B->α Aβ và β ≠ ε thì thêm các phần tử trong First(β ) trừ ε vào Follow(A). thật vậy: nếu a ∈ First(β ) thì tồn tại β =>*aγ , khi đó, do có luật B->α Aβ nên tồn tại S =>* α 1Bβ 1 => α 1α Aβ β 1=>α 1α Aaγ β 1 Theo định nghĩa của Follow thì ta có a ∈ Follow(A) 3. nếu có một sản xuất dạng B->α A hoặc B->α Aβ với ε ∈ First(B) thì mọi phần tử thuộc Follow(B) cũng thuộc Follow(A) thật vậy: nếu a ∈ Follow(B) thì theo định nghĩa Follow ta có S =>* α 1Baβ 1 =>* α 1α Aaβ 1 , suy ra a ∈ Follow(A) - Để tính Follow của các ký hiệu không kết thúc: lần lượt xét tất cả các sản xuất. Tại mỗi sản xuất, áp dụng các qui tắc trong thuật toán tính Follow để thêm các ký hiệu vào các tập Follow . Lặp lại và dừng khi nào gặp một lượt duyệt mà không bổ sung được ký hiệu nào vào các tập Follow. Ví dụ ở trên, ta tính được tập Follow cho các ký hiệu S, A, B như sau: Follow(S) = {$} Follow(A) = {b,$} Follow(B) = {} VÝ dô2: Víi v¨n ph¹m E →T E'; E' →+ T E' | ∈; T →F T'; T' →* F T' | ∈; F → (E) | id Theo ®Þnh nghÜa FIRST V× F →E) FIRST(F) = {(, id} F → (id) Tõ T → F T' v× ( ( FIRST(F) ( FIRST(T)= FIRST(F) Tõ E →T E' v× ( ( FIRST(T) ( FIRST(E)= FIRST(T) V× E' →ε ⇒ε ∈ FIRST(E')
MÆt kh¸c do E' ( +T E' mµ FIRST(+)={ +} ( FIRST(E')= {+, (} T¬ng tù FIRST(T')= { *, (} VËy ta cã FIRST(E)= FIRST(T)= FIRST(F)= { (, id} FIRST(E')= {+, ε } FIRST(T')= { *, ε } Tính follow : ĐÆt $ vµo trong FOLLOW(E). Áp dông luËt 2 cho luËt sinh F→ (E) ⇒ε ∈FOLLOW(E) ⇒FOLLOW(E)={$,ε } Áp dông luËt 3 cho E → TE' ⇒ε ,$ ∈ FOLLOW(E') ⇒ FOLLOW(E')={$,ε }. Áp dông luËt 2 cho E→TE' ⇒ mäi phÇn tö # ε cña FIRST(E') tøc + (FOLLOW(T). Áp dông luËt 3 cho E' E' → +TE' , E' → ε ⇒ FOLLOW(E') ⊂ FOLLOW(T) ⇒ ⇒ FOLLOW(T) = { +, ε , $ }. Ap dụng luËt 3 cho T→FT' th× FOLLOW(T') =FOLLOW(T)={+, $, ε }. Ap dông luËt 2 cho T→ FT' ⇒* ∈FOLLOW(F) Ap dông luËt 3 cho T' → * F T' ;T→ ε ' th× FOLLOW(T') ( FOLLOW(F)th× FOLLOW(F)= { *, +, $, )} VËy ta cã FOLLOW(E)= FOLLOW(E') = { $, )} FOLLOW(T)= FOLLOW(T') = { +,$, )} FOLLOW(F)= {*,+, $, )} 2.3.2.2. lập bảng phân tích LL(1). Bảng phân tích LL(1) là một mảng hai chiều: Một chiều chứa các ký hiệu không kết thúc, chiều còn lại chứa các ký hiệu kết thúc và $. Vị trí M(A,a) chứa sản xuất A->α trong bảng chỉ dẫn cho ta biết rằng khi cần khai triển ký hiệu không kết thúc A với ký hiệu đầu vào hiện tại là a thì áp dụng sản xuất A->α . Thuật toán xây dựng bảng LL(1): Input: Văn phạm G. Output: Bảng phân tích M. Phương pháp: 1. với mỗi sản xuất A->α , thực hiện bước 2 và bước 3 2. với mỗi ký hiệu kết thúc a ∈ First(α ), định nghĩa mục M(A,a) là A- >α
3. nếu ε ∈ First(α ) và với mỗi b ∈ Follow(A) thì định nghĩa mục M(A,b) là A->α (nếu ε ∈ First(α ) và $ ∈ Follow(A) thì thêm A->α vào M[A,$]) Đặt tất cả các vị trí chưa được định nghĩa trong bảng là “lỗi”. VÝ dô: E → T E'; E' → + T E' | ε ; T →F T'; T' → * F T' | ε ; F → (E) | id TÝnh FIRST(TE') = FIRST(T) = {(,id} ( M[E,id] vµ M[E,( ] Kí tự chưa kết Kí tự kết thúc thúc Id + * ( ) $ E E→ TE' E→ TE' E' E→ +TE' E→ ε E'→ ε T T→ FT' T→ FT' T' T'→ ε T'→ +FT' T' → ε T'→ ε F F→ id F→ (E) XÐt luËt sinh E → TE' chøa luËt sinh E →TE' XÐt luËt sinh E'→+ TE' TÝnh FIRST(+TE') = FIRST(+) = {+} ( M[E',+] chøa E'→+TE' LuËt sinh E' → ε v× ε ∈ FIRST(() = FIRST(() FOLLOW(E') = { ), $} ( E→ ε n»m trong M[E',)] vµ M[E',$] LuËt sinh T→FT' : FIRST(FT') = {*} LuËt sinh T' → ε: ε ∈ FIRST(α ) vµ FOLLOW(T')= {+, ), $} LuËt sinh F→ (E) ; FIRST(((E)) = {(} LuËt sinh F →id ; FIRST(id)={id} 2.3.2.3. văn phạm LL (k) và LL (1) Giải thuật trên có thể áp dụng bất kỳ văn phạm G nào để sinh ra bảng phân tích M. Tuy nhiên có những văn phạm ( đệ quy trái và nhập nhằng) thì trong bảng phân tích M có những ô chứa nhiềuhơn một luật sinh. Ví dụ: Văn phạm S → iEtSS’ | aS’ → eS | ε Ε → b Ký tù cha kÕt Ký tù kÕt thóc thóc A B e i t $
S S→ a S→ iEtSS' S' S → ε S'→ ε E E→ b * Định nghĩa: Văn phạm LL(1) là văn phạm xây dựng được bảng phân tích M có các ô chỉ được định nghĩa nhiều nhất là một lần. * Điều kiện để một văn phạm là LL(1) - Để kiểm tra văn phạm có phải là văn phạm LL(1) hay không ta lập bảng phân tích LL(1) cho văn phạm đó. Nếu có mục nào đó trong bảng được định nghĩa nhiều hơn một lần thì văn phạm đó không phải là LL(1), nếu trái lại thì văn phạm là LL(1). - Cách khác là dựa vào định nghĩa, một văn phạm là LL(1) phải thoả mãn điều kiện sau: nếu A -> α | β là hai sản xuất của văn phạm đó thì phải thoả mãn: a) không tồn tại một ký hiệu kết thúc a mà a ∈ First(α ) và a ∈ First(β ) b) không thể đồng thời ε thuộc First(α ) và First(β ). c) Nếu ε ∈ First(α ) thì Follow(A) và First(β ) không có phần tử nào trùng nhau. 2.3.2.4. Thuật toán phân tích LL(1) * Mô tả: Cơ sở của phân tích LL là dựa trên phương pháp phân tích topdown và máy ôtômát đẩy xuống. - Vùng đệm chứa xâu vào với cuối xâu là ký hiệu kết thúc xâu $.
- Ngăn xếp chứa các ký hiệu văn phạm thể hiện quá trình phân tích. Đáy ngăn xếp kí hiệu $. - Bảng phân tích M lµ mét m¶ng hai chiÒu M[A,a], trong ®ã A lµ ký hiÖu chøa kÕt thóc, a lµ ký hiÖu kÕt thóc hoÆc $. - Thành phần chính điều khiển phân tích. Mô hình của phân tích cú pháp LL Tại thời điểm hiện tại, giả sử X là ký hiệu trên đỉnh ngăn xếp và a là ký hiệu đầu vào. Các hành động điều khiển được thực hiện như sau: 1. nếu X = a = $, quá trình phân tích thành công 2. nếu X = a ≠ $, lấy X ra khỏi ngăn xếp và dịch con trỏ đầu vào đến ký hiệu tiếp theo 3. nếu X là một ký hiệu không kết thúc, xét mục M(X,a) trong bảng phân tích. Có hai trường hợp xảy ra: a) nếu M(A,a) = X -> Y1. . .Yk thì lấy X ra khỏi ngăn xếp và đẩy vào ngăn xếp Y1, . . ., Yk theo thứ tự ngược lại (để ký hiệu được phân tích tiếp theo trên đỉnh ngăn xếp phải là Y1, tạo ra dẫn xuất trái). b) nếu M(A,a) là lỗi thì quá trình phân tích gặp lỗi và gọi bộ khôi phục lỗi. * Thuật toán : - Input: Một xâu w và một bảng phân tích M của văn phạm G. - Output: Đưa ra suy dẫn trái nhất của w nếu w ∈ L(G), báo lỗi nếu w ∉ L(G). - Method: Ở trạng thái khỉ đầu ngăn xép được đặt các kí hiệu $S (S là đỉnh của cây phân tích còn xâu vào là w$ ) Đặt con trỏ ip trỏ đến kí tự đầu tiên của xâu w$ Repeat {Giả sử X là kí hiệu đỉnh của ngăn xếp, a là kí hiệu vào tiếp theo} If (X ∈Σ ) or (X = $) then If x=a then Pop X từ đỉnh ngăn xếp và loại bỏ a khỏi xâu vào Else error (); Else {X không phải là kí tự kết thúc}
If M[X,a] = X → Y1, Y2, Yk then Begin Pop X từ ngăn xếp; Push Yk, Yk-1, Y1 vào ngăn xếp, với Y1 ở đỉnh; Đưa ra sản xuất X → Y1, Y2, Yk ; End; Else Error(); Until X = $ {ngăn xếp rỗng} Ví dụ 2: Cho văn phạm: E->TE’; E’->+TE’ | ε ; T->FT’; T’->*FT’ | ε ; F- >(E) | id a) tính First và Follow cho các ký hiệu không kết thúc. b) tính First cho vế phải của các sản xuất. c) xây dựng bảng phân tích LL(1) cho văn phạm trên d) phân tích LL đối với xâu vào “id+id*id” Ký hiệu văn phạm First Follow E (, id ), $ E’ +, ε ), $ T (, id +, ), $ T’ *, ε +, ), $ F (, id +, *, ), $ Sản xuất First của vế phải E->TE’ (, id E’->+TE’ + T->FT’ (, id T’->*FT’ * F->(E) ( F->id Id Bảng phân tích LL(1)
Ký hiệu Ký hiệu đầu vào Vế trái Id + * ( ) $ E E->TE’ E->TE’ E’ E’->+TE’ E’->ε E’->ε T T->FT’ T->FT’ T’ T’->ε T’->*FT’ T’->ε T’->ε F F->id F->(E) Phân tích LL(1) cho xâu vào “id+id*id”: Ngăn xếp Xâu vào Đầu ra $E id+id*id$ E->TE’ $E’T id+id*id$ T->FT’ $E’T’F id+id*id$ F->id $E’T’id id+id*id$ rút gọn id $E’T’ +id*id$ T’->ε $E’ +id*id$ E’->+TE’ $E’T+ +id*id$ rút gọn + $E’T id*id$ T->FT’ $E’T’F id*id$ F->id $E’T’id id*id$ rút gọn id $E’T’ *id$ T’->*FT’ $E’T’F* *id$ rút gọn * $E’T’F id$ F->id $E’T’id id$ rút gọn id $E’T’ $ T’->ε $E’ $ E’->ε $ $ Từ bảng phân tích, chúng ta có suy dẫn trái như sau: E=>TE’=>FT’E’=>idT’E’=>idE’=>id+TE’=>id+FT’E’=>id+idT’E’=>id+id *FT’E’=> id+id*idT’E’=>id+id*idE’=>id=id*id .
2.3.4. Phân tích LR. LR là kỹ thuật phân tích cú pháp từ dưới lên khá hiệu quả, có thể được sử dụng để phân tích một lớp khá lớn các văn phạm phi ngữ cảnh. Kỹ thuật này gọi là phân tích cú pháp LR(k), trong đó: - L là Left to right chỉ việc quét xâu vào từ trái quá phải. - R là Right most parsing chỉ việc suy dẫn sinh ra là suy dẫn phải. - k là số ký hiệu nhìn trước để đưa ra quyết định phân tích. * Phân tích LR có nhiều ưu điểm: - Nhận biết được tất cả các cấu trúc của ngôn ngữ lập trình được tạo ra dựa theo các văn phạm phi ngữ cảnh. - LR là phương pháp phân tích cú pháp gạt - thu gọn không quay lui tổng quát nhất đã được biết đến nhưng lại có thể được cài đặt hiệu quả như những phương pháp gạt - thu gọn khác. - lớp văn phạm phân tích được nhờ phương pháp LR là một tập bao hàm thực sự của lớp văn phạm phân tích được bằng cách phân tích cú pháp dự đoán. - Phát hiện được lỗi cú pháp ngay khi có thể trong quá trình quét đầu vào từ trái sang. * Nhược điểm chủ yếu: ta phải thực hiện quá nhiều công việc để xây dựng được bộ phân tích LR cho một ngôn ngữ lập trình. 2.3.4.1. Thuật toán phân tích LR. Phân tích LR là một thể phân tích cú pháp gạt - thu gọn, nhưng điểm khác biệt so với phân tích Bottom-up là nó không quay lui. Tại mỗi thời điểm nó xác định được duy nhất hành động gạt hay thu gọn. * Mô hình: gồm các thành phần sau: - Stack lưu một chuỗi s0X1s1X2s2 Xmsm trong đó sm nằm trên đỉnh Stack. Xi là một ký hiệu văn phạm, si là một trạng thái tóm tắt thông tin chứa trong Stack bên dưới nó. - Bảng phân tích bao gồm 2 phần : hàm action và hàm goto.  action[sm, ai] có thể có một trong 4 giá trị : 1. shift s : đẩy s, trong đó s là một trạng thái. 2. reduce (A→ β ) :thu gọn bằng luật sinh A→ β . 3. accept : Chấp nhận 4. error : Báo lỗi  Goto lấy 2 tham số là một trạng thái và một ký hiệu văn phạm, nó sinh ra một trạng thái.
* Cấu hình (configuration) của một bộ phân tích cú pháp LR là một cặp thành phần, trong đó, thành phần đầu là nội dung của Stack, phần sau là chuỗi nhập chưa phân tích: (s0X1s1X2s2 Xmsm, ai ai+1 an $) * Hoạt động: Với sm là ký hiệu trên đỉnh Stack, ai là ký hiệu nhập hiện tại, cấu hình có được sau mỗi dạng bước đẩy sẽ như sau : 1. Nếu action [sm, ai] = Shift s : Thực hiện phép đẩy để được cấu hình mới : (s0X1s1X2s2 Xmsm ais, ai +1 an $) Phép đẩy làm cho s nằm trên đỉnh Stack, ai+1 trở thành ký hiệu hiện hành. 2. Nếu action [sm, ai] = Reduce(A → β ) thì thực hiện phép thu gọn để được cấu hình : (s0X1s1X2s2 Xm - ism - i As, ai ai +1 an $) Trong đó, s = goto[sm - i, A] và r là chiều dài số lượng các ký hiệu của β . Ở đây, trước hết 2r phần tử của Stack sẽ bị lấy ra, sau đó đẩy vào A và s. 3. Nếu action[sm, ai] = accept : quá trình phân tích kết thúc. 4. Nếu action[sm, ai] = error : gọi thủ tục phục hồi lỗi. Giải thuật phân tích cú pháp LR Input: Một chuỗi nhập w, một bảng phân tích LR với hàm action và goto cho văn phạm G. Output: Nếu w ∈ L(G), đưa ra một sự phân tích dưới lên cho w . Ngược lại, thông báo lỗi. Phương pháp: Khởi tạo s0 là trạng thái khởi tạo nằm trong Stack và w$ nằm trong bộ đệm nhập. Ðặt ip vào ký hiệu đầu tiên của w$; Repeat forever begin Gọi s là trạng thái trên đỉnh Stack và a là ký hiệu được trỏ bởi ip; If action[s, a] = Shift s' then begin Ðẩy a và sau đó là s' vào Stack; Chuyển ip tới ký hiệu kế tiếp; end else if action[s, a] = Reduce (A → β ) then begin Lấy 2 * | β | ký hiệu ra khỏi Stack; Gọi s' là trạng thái trên đỉnh Stack; Ðẩy A, sau đó đẩy goto[s', A] vào Stack; Xuất ra luật sinh A→ β ; end else if action[s, a] = accept then return else error ( ) end Ví dụ: Cho văn phạm:
(1) E -> E + T (2) E -> T (3) T -> T * F (4) T -> F (5) F -> ( E ) (6) F -> a Giả sử chúng ta đã xây dựng được bảng phân tích action và goto như sau: chú ý: các giá trị trong action được ký hiệu như sau: a) si có nghĩa là shift i b) rj có nghĩa là reduce theo luật (j) c) acc có nghĩa là accept d) khoảng trống biểu thị lỗi trạng Action goto thái a + * ( ) $ E T F 0 s5 S4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 S4 8 2 3 5 r6 r6 r6 r6 6 s5 S4 9 3 7 s5 S4 10 8 s6 s11 9 r1 s7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 Bảng phân tích cú pháp Chúng ta sử dụng thuật toán LR để phân tích xâu vào “a*a+a” đối với dữ liệu trên như sau: Ngăn xếp Đầu vào Hành động 0 id * id + id $ gạt 0 id 5 * id + id $ thu gọn F->id 0 F 3 * id + id $ thu gọn T->F 0 T 2 * id + id $ gạt 0 T 2 * 7 id + id $ gạt 0 T 2 * 7 id 5 + id $ thu gọn F->id 0 T 2 * 7 F 10 + id $ thu gọn T->T*F 0 T 2 + id $ thu gọn E->T 0 E 1 + id $ gạt 0 E 1 + 6 id $ gạt 0 E 1 + 6 id 5 $ thu gọn F->id 0 E 1 + 6 F 3 $ thu gọn T->F
0 E 1 + 6 T 9 $ thu gọn E->E+T 0 E 1 $ chấp nhận (accepted) Quá trình phân tích LR Một số đặc điểm của phân tích LR: - Một tính chất cơ bản đối với bộ phân tích cú phát LR là xác định được khi nào handle xuất hiện trên đỉnh ngăn xếp. - Ký hiệu trạng thái trên đỉnh ngăn xếp đã xác định mọi thông tin của quá trình phân tích vì nó chỉ đến tập mục có nghĩa của tiền tố khả tồn trong ngăn xếp. Dựa vào các mục này, chúng ta có thể xác định khi nào thì gặp một handle trên đỉnh ngăn xếp và thực hiện hành động thu gọn. - Một nguồn thông tin khác để xác định hành động gạt-thu gọn là k ký hiệu đầu vào tiếp theo. Thông thườn chúng ta xét k=0 hoặc 1. - Điểm khác biệt giữa phương pháp phân tích LR với phương pháp phân tích LL là: Để cho một văn phạm là LR(k), chúng ta phải có khả năng xác định được sự xuất hiện của vế phải của một sản xuất khi đã thấy tất cả quá trình dẫn xuất từ vế phải đó với thông tin thêm là k ký hiệu đầu vào tiếp theo. Điều kiện này rõ ràng là chính xác hơn so với điều kiện của văn phạm LL(k) là việc sử dụng một sản xuất chỉ dựa vào k ký hiệu đầu vào tiếp theo. Chính vì vậy mà quá trình phân tích LR ít có xung đột hơn, hay nói cách khác là văn phạm của nó rộng hơn LL rất nhiều. 2.3.4.2. Một số khái niệm. 1) Tiền tố khả tồn (viable prefixes) Xâu ký hiệu trong ngăn xếp tại mỗi thời điểm của một quá trình phân tích gạt - thu gọn là một tiền tố khả tồn. Ví dụ: tại một thời điểm trong ngăn xếp có dữ liệu là α β và xâu vào còn lại là w thì α β w là một dạng câu dẫn phải và α β là một tiền tố khả tồn. 2) Mục (Item) : Cho một văn phạm G. Với mỗi sản xuất A->xy, ta chèn dấu chấm vào tạo thành A->x .y và gọi kết quả này là một mục. Mục A->x.y cho biết qúa trình suy dẫn sử dụng sản xuất A->xy và đã suy dẫn đến hết phần x trong sản xuất, quá trình suy dẫn tiếp theo đối với phần xâu vào còn lại sẽ bắt đầu từ y. Ví dụ: Luật sinh A ( XYZ có 4 mục như sau : A→ •XYZ A→ X•YZ A→ XY•Z A→ XYZ• Luật sinh A → ε chỉ tạo ra một mục A → • 3) Mục có nghĩa (valid item) Một mục A->β 1.β 2 gọi là mục có nghĩa(valid item) đối với tiền tố khả tồn α β 1 nếu tồn tại một dẫn xuất: S =>*rm α Aw =>rm α β 1β 2w
Tập tất cả các mục có nghĩa đối với tiền tố khả tồn gọi là tập I. Một tập mục có nghĩa đối với một tiền tố khả tồn nói lên rất nhiều điều trong quá trình suy dẫn gạt - thu gọn: Giả sử quá trình gạt thu gọn đang ở trạng thái với ngăn xếp là x và phần ký hiệu đầu vào là v (*) ngăn xếp đầu vào $x v$ thế thì, quá trình phân tích tiếp theo sẽ phụ thuộc vào tập mục có nghĩa I của tiền tố khả tồn thuộc x. Với một mục [A->β 1.β 2] ∈ I, cho chúng ta biết x có dạng α β 1, và quá trình phân tích phần còn lại w của xâu đầu vào nếu theo sản xuất A->β 1β 2 sẽ được tiếp tục từ β 2 của mục đó. Hành động gạt hay thu gọn sẽ phụ thuộc vào β 2 là rỗng hay không. Nếu β 2 = ε thì phải thu gọn β 1 thành A, còn nếu β 2 ≠ ε thì việc phân tích theo sản xuất A->β 1β 2 đòi hỏi phải sử dụng hành động gạt. Nhận xét: - Mọi quá trình phân tích tiếp theo của trạng thái (*) đều phụ thuộc vào các mục có nghĩa trong tập các mục có nghĩa I của tiền tố khả tồn x. - Có thể có nhiều mục có nghĩa đối với một tiền tố x. Các mục này có thể có các hành động xung đột (bao gồm cả gạt và thu gọn), trong trường hợp này bộ phân tích sẽ phải dùng các thông tin dự đoán, dựa vào việc nhìn ký hiệu đầu vào tiếp theo để quyết định nên sử dụng mục có nghĩa nào với tiền tố x (tức là sẽ cho tương ứng gạt hay thu gọn). Nếu quá trình này cho những quyết định không xung đột (duy nhất) tại mọi trạng thái thì ta nói văn phạm đó phân tích được bởi thuật toán LR. - Tư tưởng của phương pháp phân tích LR là phải xây dựng được tập tất cả các mục có nghĩa đối với tất cả các tiền tố khả tồn. 4) Tập chuẩn tắc LR(0) LR(0) là tập các mục có nghĩa cho tất cả các tiền tố khả tồn. LR(0) theo nghĩa: LR nói lên đây là phương pháp phân tích LR, còn số 0 có nghĩa là số ký tự nhìn trước là 0. 5) Văn phạm gia tố( Augmented Grammar) (mở rộng) Văn phạm G - ký hiệu bắt đầu S, thêm một ký hiệu bắt đầu mới S' và luật sinh S' S để được văn phạm mới G' gọi là văn phạm gia tố. Ví dụ: cho văn phạm G gồm các sản xuất S -> aSb | a thì văn phạm gia tố của G, ký hiệu là G’ gồm các sản xuất S’-S, S->aSb | a với S’ là ký hiệu bắt đầu.
Ta xây dựng văn phạm gia tố của một văn phạm theo nghĩa, đối với văn phạm ban đầu, quá trình phân tích sẽ bắt đầu bởi các sản xuất có vế trái là S. Khi đó, chúng ta xây dựng văn phạm gia tố G’ thì mọi quá trình phân tích sẽ bắt đầu từ sản xuất S’->S Sử dụng hai phép toán: phép tính bao đóng closure(I) của một tập mục I và phép sinh ra tập mục cho các tiền tố khả tồn mới goto(I,X) như sau: 6) Phép toán closure Nếu I là một tập các mục của một văn phạm G thì closure(I) là tập các mục được xây dựng từ I bằng hai qui tắc sau: 1. khởi đầu mỗi mục trong I đều được đưa vào closure(I) 2. nếu [A -> α .Bβ ] ∈ closure(I) và B->γ là một sản xuất thì thêm [B -> .γ ] vào closure(I) nếu nó chưa có ở đó. Áp dụng qui tắc này đến khi không thêm được một mục nào vào closure(I) nữa. Trực quan: nếu [A -> α .Bβ ] là một mục có nghĩa đối với một tiền tố khả tồn xα thì với B->γ là một sản xuất ta cũng có [B->.γ ] là một mục có nghĩa đối với tiền tố khả tồn xα . Phép toán tính bao đóng của một mục là để tìm tất cả các mục có nghĩa tương đương của các mục trong tập đó. Theo định nghĩa của một mục là có nghĩa đối với một tiền tố khả tồn, chúng ta có suy dẫn S =>*rm xAy =>rm xα Bβ y sử dụng sản xuất B -> γ ta có suy dẫn S =>*rm xα γ β y. Vậy thì [B->.γ ] là một mục có nghĩa của tiền tố khả tồn xα Ví dụ: Xét văn phạm mở rộng của biểu thức: E' → E E → E + T | T T → T * F | F F → (E) | id Nếu I là tập hợp chỉ gồm văn phạm {E'→ • E} thì closure(I) bao gồm: E' → • E (Luật 1) E → • E + T (Luật 2) E → • T (Luật 2) T → • T * F (Luật 2) T → • F (Luật 2) F → • (E) (Luật 2) F → • id (Luật 2) E' → • E được đặt vào closure(I) theo luật 1. Khi có một E đi ngay sau một • , bằng luật 2 ta thêm các sản xuất E với các chấm nằm ở đầu trái ( E → • E + T và E → • T). Bây giờ lại có T đi theo sau một •, ta lại thêm T → • T * F và T → • F vào. Cuối cùng ta có Closure(I) như trên. Chú ý rằng : Nếu một B - luật sinh được đưa vào closure(I) với dấu chấm mục nằm ở đầu vế phải thì tất cả các B - luật sinh đều được đưa vào. * Phép toán goto goto(I,X) với I là một tập các mục và X là một ký hiệu văn phạm.
goto(I,X) được định nghĩa là bao đóng của tập tất cả các mục [A->α X.β ] sao cho [A->α .Xβ ] ∈ I. Trực quan: Nếu I là tập các mục có nghĩa đối với một tiền tố khả tồn γ nào đó thì goto(I,X) là tập các mục có nghĩa đối với tiền tố khả tồn γ X. gọi tập J=goto(I,X) thì cách tính tập J như sau: 1. nếu [A->α .Xβ ] ∈ I thì thêm [A->α X.β ] vào J 2. J=closure(J) Phép toán goto là phép phát triển để xây dựng tất cả các tập mục cho tất cả các tiền tố khả tồn có thể. Ví dụ : Giả sử I = {E' → E•, E → E • + T}. Tính goto (I, +) ? Ta có J = { E→ E + • T} ⇒ goto (I, +) = closure(I') bao gồm các mục : E E + • T (Luật 1) T • T * F (Luật 2) T • F (Luật 2) F • (E) (Luật 2) F • id (Luật 2) Tính Goto(I,+) bằng cách kiểm tra I cho các mục với dấu + ở ngay bên phải chấm. E’ → E• không phải mục như vậy nhưng E → E • + T thì đúng. Ta chuyển dấu chấm qua bên kia dấu + để nhận được E → E + • T và sau đó tính closure cho tập này. Như vậy, cho trước một văn phạm, ta có thể sử dụng hai phép toán trên để sinh ra tất cả các tiền tố khả tồn có thể và tập mục có nghĩa của từng tiền tố khả tồn. Với việc sử dụng phép tính closure và goto như trên, chúng ta xây dựng được tập các mục gọi là tập mục LR(0). Thuật toán xây dựng LR(0) như sau: Cho văn phạm G, văn phạm gia tố của nó là G’ Tập C là tập các tập mục LR(0) được tính theo thuật toán như sau: 1). C = {closure({[S’->.S]})} 2). Đối với mỗi mục I trong C và mỗi ký hiệu văn phạm X, tính goto(I,X). Thêm goto(I,X) vào C nếu không rỗng và không trùng với bất kỳ tập nào có trong C Thực hiện bước 2 đến khi nào không thêm được tập nào nữa vào C C là tập xác định tất cả các mục có nghĩa đối với tất cả các tiền tố khả tồn vì chúng ta xuất phát từ mục [S’ -> .S] và xây dựng các mục có nghĩa cho tất cả các tiền tố khả tồn.
Xây dựng tập C dựa trên hàm goto có thể được xem như một sơ đồ chuyển trạng thái của một DFA. Trong đó, I0 là trạng thái xuất phát, bằng cách xây dựng các trạng thái tiếp bằng chuyển trạng thái theo đầu vào là các ký hiệu văn phạm. Đường đi của các ký hiệu đầu vào chính là các tiền tố khả tồn. Các trạng thái chính là tập các mục có nghĩa của các tiền tố khả tồn đó. Ví dụ: Cho văn phạm G: E -> E + T | T; T -> T * F | F; F -> ( E ) | id Hãy tính LR(0) - Xét văn phạm G’ là văn phạm gia tố của G. Văn phạm G’ gồm các sản xuất sau: E’ -> E; E -> E + T | T; T -> T * F | F; F -> ( E ) | a Tính theo thuật toán trên ta có kết quả như sau: Closure({E'→ E}): Goto (I0, id) I5: F -> a. I0: E’ -> .E E -> .T T -> .F F -> .(E) F -> .a Goto (I0, E) I1: E’ -> E. Goto (I1, +) I6: E -> .E+T E -> E.+T E -> E+.T T -> .T*F T -> .F F -> .(E) F -> .a Goto (I0, T) I2: E -> T. Goto (I2, *) I7: T -> T*.F T -> T.*F F -> .(E) F -> .a
Sơ đồ chuyển trạng thái của DFA cho các tiền tố khả tồn: I E I + I T I * I 0 1 6 9 7 F I 3 ( I 4 a I 5 I I T * F I 10 2 7 ( I 4 a I F I 5 3 ( ( I I ) E I 11 4 8 + I 6 T I 2 F I a 3 a I 5
2.3.4.2. Văn phạm LR. Làm thế nào để xây dựng được một bảng phân tích cú pháp LR cho một văn phạm đã cho ? Một văn phạm có thể xây dựng được một bảng phân tích cú pháp cho nó được gọi là văn phạm LR. Có những văn phạm phi ngữ cảnh không thuộc lọai LR, nhưng nói chung là ta có thể tránh được những văn phạm này trong hầu hết các kết cấu ngôn ngữ lập trình điển hình. Sự khác biệt rất lớn giữa các văn phạm LL và LR: Ðối với văn phạm LR(k), ta phải có khả năng nhận diện được sự xuất hiện của vế phải của một sản xuất nào đó bằng cách xem tất cả những gì suy dẫn được từ vế phải qua k kí hiệu vào được nhìn vượt quá. Ðòi hỏi này ít khắt khe hơn so với các văn phạm LL(k). Đối với văn phạm LL(k): ta phải nhận biết được sản xuất nào được dùng chỉ với k kí hiệu đầu tiên mà vế phải của nó suy dẫn ra. Vì vậy, các văn phạm LR có thể mô tả được nhiều ngôn ngữ hơn so với các văn phạm LL. 2.3.4.3. Xây dựng bảng phân tích SLR. Phần này trình bày cách xây dựng một bảng phân tích cú pháp LR từ văn phạm. Chúng ta sẽ đưa ra 3 phương pháp khác nhau về tính hiệu quả cũng như tính dễ cài đặt. Phương pháp thứ nhất được gọi là "LR đơn giản" (Simple LR - SLR), là phương pháp "yếu" nhất nếu tính theo số lượng văn phạm có thể xây dựng thành công bằng phương pháp này, nhưng đây lại là phương pháp dễ cài đặt nhất. Ta gọi bảng phân tích cú pháp tạo ra bởi phương pháp này là bảng SLR và bộ phân tích cú pháp tương ứng là bộ phân tích cú pháp SLR, với văn phạm tương đương là văn phạm SLR. Phương pháp thứ 2 là phương pháp LR chuẩn ( canonical LR): phương pháp mạnh nhất nhưng tốn kém nhất. Phương pháp thứ 3: LR nhìn vượt (LALR – LookaheadLR) là phương pháp trung gian về sức mạnh và chi phí giữ 2 phương pháp trên. Phương pháp này làm việc với hầu hết các văn phạm. Trong phần này ta sẽ xem xét cách xây dựng các hàm action và goto của phân tích SLR từ ôtômát hữu hạn đơn định dùng để nhận dạng các tiền tố có thể có.
Cho văn phạm G, ta tìm văn phạm gia tố của G là G’, từ G’ xây dựng C là tập chuẩn các tập mục cho G’, xây dựng hàm phân tích Action và hàm nhẩy goto từ C bằng thuật toán sau. Input: Một văn phạm tăng cường G' Output: Bảng phân tích SLR với hàm action và goto Phương pháp: 1. Xây dựng C = { I0, I1, , In }, họ tập hợp các mục LR(0) của G'. 2. Trạng thái i được xây dựng từ Ii .Các action tương ứng trạng thái i được xác định như sau: 2.1 . Nếu A → α • aβ ∈ Ii và goto (Ii, a) = Ij thì action[i, a] = "shift j". Ở đây a là ký hiệu kết thúc. 2.2. Nếu A → α • ∈ Ii thì action[i, a] = "reduce (A → α )", ∀a ∈ FOLLOW(A). Ở đây A không phải là S' 2.3. Nếu S' → S • ∈ Ii thì action[i, $] = "accept". Nếu một action đụng độ được sinh ra bởi các luật trên, ta nói văn phạm không phải là SLR(1). Giải thuật sinh ra bộ phân tích cú pháp sẽ thất bại trong trường hợp này. 3. Với mọi ký hiệu chưa kết thúc A, nếu goto (Ii,A) = Ij thì goto [i, A] = j 4. Tất cả các ô không xác định được bởi 2 và 3 đều là “error” 5. Trạng thái khởi đầu của bộ phân tích cú pháp được xây dựng từ tập các mục chứa S’→ • S Ví dụ Ta xây dựng bảng phân tích cú pháp SLR cho văn phạm tăng cường G' trong ví dụ trên. E' → E E → E + T | T T → T * F | F F → (E) | id (0) E'→ E (1) E → E + T (2) E → T (3) T → T * F (4) T → F (5) F → (E) (6) F → id 1. C = { I0, I1, I11 } 2. FOLLOW(E) = {+, ), $} FOLLOW(T) = {*, +, ), $} FOLLOW(F) = {*, +, ), $} Dựa vào họ tập hợp mục C đã được xây dựng trong ví dụ 4.22, ta thấy: Trước tiên xét tập mục I0 : Mục F → • (E) cho ra action[0, (] = "shift 4", và mục F → • id cho action[0, id] = "shift 5". Các mục khác trong I0 không sinh được hành động nào.
Bây giờ xét I1 : Mục E'→ E • cho action[1, $] = "accept", mục E → E • + T cho action[1, +] = "shift 6". Kế đến xét I2: E → T • T → T • * F Vì FOLLOW(E) = {+, ), $}, mục đầu tiên làm cho action[2, $] = action[2,+] = "reduce (E → T)". Mục thứ hai làm cho action[2,*] = "shift 7". Tiếp tục theo cách này, ta thu được bảng phân tích cú pháp SLR: trạng Action goto thái a + * ( ) $ E T F 0 s5 S4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 S4 8 2 3 5 r6 r6 r6 r6 6 s5 S4 9 3 7 s5 S4 10 8 s6 s11 9 r1 s7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 Bảng phân tích xác định bởi giải thuật 4.7 gọi là bảng SLR(1) của văn phạm G, bộ phân tích LR sử dụng bảng SLR(1) gọi là bộ phân tích SLR(1) và văn phạm có một bảng SLR(1) gọi là văn phạm SLR(1). I : S' → • S 0 Mọi văn phạm SLR(1) đều không mơ hồ, Tuy nhiên có S → • L = R những văn phạm không mơ hồ nhưng không phải là S → • R SLR(1). L → • * R Ví dụ: Xét văn phạm G với tập luật sinh như sau: L → • id → → → S L = RI : LS → Rid • L * R L R → • L → id R → L 5 Ðây là một văn phạm không mơ hồ nhưng không I : S' → S • 1 phải là văn phạm SLR(1). I : S → L = • R Họ tập hợp các mục C6 bao gồm: R → • L I : S → L • = R 2 L → • * R R → L • L → • id I : S → R • 3 I : L → * R• 7 I : L → * • R 4 I : R → L• 8 R → • L L → • * R →• I : S → L = R• L id 9
Khi xây dựng bảng phân tích SLR cho văn phạm, khi xét tập mục I2 ta thấy mục đầu tiên trong tập này làm cho action[2, =] = "shift 6". Bởi vì = ∈ FOLLOW(R), nên mục thứ hai sẽ đặt action[2, =] = "reduce (R → L)" ⇒ Có sự đụng độ tại action[2, =]. Vậy văn phạm trên không là văn phạm SLR(1). 2.3.4.4. Xây dựng bảng phân tích LR chuẩn. * Mục LR(1) của văn phạm G là một cặp dạng [A → α• β , a], trong đó A → α β là luật sinh, a là một ký hiệu kết thúc hoặc $. * Thuật toán xây dựng họ tập hợp mục LR(1)  Giải thuật: Xây dựng họ tập hợp các mục LR(1) Input : Văn phạm tăng cường G’ Output: Họ tập hợp các mục LR(1). Phương pháp: Các thủ tục closure, goto và thủ tục chính Items như sau: Function Closure (I); begin Repeat For Mỗi mục [A → α • Bβ ,a] trong I, mỗi luật sinh B → γ trong G' và mỗi ký hiệu kết thúc b ∈ FIRST (β a) sao cho [B → • γ , b] ∉ I do Thêm [ B → • γ , b] vào I; Until Không còn mục nào có thể thêm cho I được nữa; return I; end; Function goto (I, X); begin Gọi J là tập hợp các mục [A → α X•β , a] sao cho [A → α• Xβ , a]∈ I; return Closure(J); end; Procedure Items (G'); begin
C := Closure ({[S' → •S, $]}) Repeat For Mỗi tập các mục I trong C và mỗi ký hiệu văn phạm X sao cho goto(I, X) ≠ ∅ và goto(I, X) ∉ C do Thêm goto(I, X) vào C; Until Không còn tập các mục nào có thể thêm cho C; end; Ví dụ: Xây dựng bảng LR chính tắc cho văn phạm gia tố G' có các luật sinh sau : S' S (1) S L = R3 (2) S R (3) L * R (4) L id (5) R L Trong đó: tập ký hiệu chưa kết thúc ={S, L, R} và tập ký hiệu kết thúc {=, *, id, $} I0 : S' → • S, $ Goto (I4,R) I7 : L → * R•, = | $ Closure (S' •S, $) S → • L = R, $ S → • R, $ Goto (I4, L) I8 : R→ L•, = | $ L → • * R, = | $ → • L → • id, = | $ Goto (I6,R) I9 : S L = R , $ R → • L, $ → • Goto (I6,L) I10 :R L , $ Goto (I0,S) I1 : S' → S •, $ → • Goto (I6,*) I11 :L * R, $ →• Goto (I0, L) I2 : S → L • = R, $ R L, $ R → L •, $ L → • * R, $ R → • id, $ Goto (I 0,R) I3: S → R •, $ Goto (I6, id) I12 :L → id •, $ Goto (I0,*) I4: L → * • R, = | $ → • R • L, = | $ Goto (I11,R) I13 :R * R , $ L → • * R, = | $ ≡ R → • id, = | $ Goto (I11,L) I10 Goto (I11,*) ≡ I11 Goto (I0,id) I5 : L → id •, = | $ ≡ Goto (I2,=) I6 : S → L = • R, $ Goto (I11,id) I12 R → • L, $ L → • * R, $ L → • id, $ * Thuật toán xây dựng bảng phân tích cú pháp LR chính tắc
 Giải thuật: Xây dựng bảng phân tích LR chính tắc Input: Văn phạm tăng cường G' Output: Bảng LR với các hàm action và goto Phương pháp: 1. Xây dựng C = { I0, I1, In } là họ tập hợp mục LR(1) 2. Trạng thái thứ i được xây dựng từ Ii. Các action tương ứng trạng thái i được xác định như sau: 2.1. Nếu [A → α • aβ ,b] ∈ Ii và goto(Ii,a) = Ij thì action[i, a]= "shift j". Ở đây a phải là ký hiệu kết thúc. 2.2. Nếu [A → α •, a] ∈ Ii , A ≠ S' thì action[i, a] = "reduce (A → α) 2.3. Nếu [S' → S•,$] ∈ Ii thì action[i, $] = "accept". Nếu có một sự đụng độ giữa các luật nói trên thì ta nói văn phạm không phải là LR(1) và giải thuật sẽ thất bại. 3. Nếu goto(Ii, A) = Ij thì goto[i,A] = j 4. Tất cả các ô không xác định được bởi 2 và 3 đều là "error" 5. Trạng thái khởi đầu của bộ phân tích cú pháp được xây dựng từ tập các mục chứa [S' → •S,$] Bảng phân tích xác định bởi giải thuật 4.9 gọi là bảng phân tích LR(1) chính tắc của văn phạm G, bộ phân tích LR sử dụng bảng LR(1) gọi là bộ phân tích LR(1) chính tắc và văn phạm có một bảng LR(1) không có các action đa trị thì được gọi là văn phạm LR(1). Ví dụ : Xây dựng bảng phân tích LR chính tắc cho văn phạm ở ví dụ trên Trạng Action Goto thái = * id $ S L R 0 s4 s5 1 2 3 1 acc 2 s6 r5 3 r2 4 s4 s5 8 7 5 r4 6 s11 s12 10 9 7 r3 8 r5 9 r1 10 r5 11 s11 s12 10 13
12 r4 13 r3 Hình 4.14 - Bảng phân tích cú pháp LR chính tắc Mỗi văn phạm SLR(1) là một văn phạm LR(1), nhưng với một văn phạm SLR(1), bộ phân tích cú pháp LR chính tắc có thể có nhiều trạng thái hơn so với bộ phân tích cú pháp SLR cho văn phạm đó. 2.3.4.5. Xây dựng bảng phân tích LALR. Phần này giới thiệu phương pháp cuối cùng để xây dựng bộ phân tích cú pháp LR - kỹ thuật LALR (Lookahead-LR), phương pháp này thường được sử dụng trong thực tế bởi vì những bảng LALR thu được nói chung là nhỏ hơn nhiều so với các bảng LR chính tắc và phần lớn các kết cấu cú pháp của ngôn ngữ lập trình đều có thể được diễn tả thuận lợi bằng văn phạm LALR. a. Hạt nhân (core) của một tập hợp mục LR(1) 1. Một tập hợp mục LR(1) có dạng {[A → α• β , a]}, trong đó A → α β là một luật sinh và a là ký hiệu kết thúc có hạt nhân (core) là tập hợp {A → α •β }. 2. Trong họ tập hợp các mục LR(1) C = {I0, I1, , In} có thể có các tập hợp các mục có chung một hạt nhân. Ví dụ : Trong ví dụ 4.25, ta thấy trong họ tập hợp mục có một số các mục có chung hạt nhân là : I4 và I11 I5 và I12 I7 và I13 I8 và I10 b. Thuật toán xây dựng bảng phân tích cú pháp LALR  Giải thuậ: Xây dựng bảng phân tích LALR Input: Văn phạm tăng cường G' Output: Bảng phân tích LALR Phương pháp: 1. Xây dựng họ tập hợp các mục LR(1) C = {I0, I1, , In } 2. Với mỗi hạt nhân tồn tại trong tập các mục LR(1) tìm trên tất cả các tập hợp có cùng hạt nhân này và thay thế các tập hợp này bởi hợp của chúng. 3. Ðặt C' = {I0, I1, , Im } là kết quả thu được từ C bằng cách hợp các tập hợp có cùng hạt nhân. Action tương ứng với trạng thái i được xây dựng từ Ji theo cách thức như giải thuật 4.9.
Nếu có một sự đụng độ giữa các action thì giải thuật xem như thất bại và ta nói văn phạm không phải là văn phạm LALR(1). 4. Bảng goto được xây dựng như sau Giả sử J = I1 ∪ I2 ∪ ∪ Ik . Vì I1, I2, Ik có chung một hạt nhân nên goto (I1,X), goto (I2,X), , goto (Ik,X) cũng có chung hạt nhân. Ðặt K bằng hợp tất cả các tập hợp có chung hạt nhân với goto (I1,X) ( goto(J, X) = K. Ví dụ : Với ví dụ trên, ta có họ tập hợp mục C' như sau C' = {I0, I1, I2, I3, I411, I512, I6, I713, I810, I9 } I0 : S' → • S, $ I512 = Goto (I0,id), Goto (I6,id) : closure (S' •S, $) : S → • L = R, $ L → id •, = | $ S → • R, $ L → • * R, = I6 = Goto(I2,=) : → • L → • id, = S L = R,$ →• R → • L, $ R L, $ L → • * R, $ →• I1 = Goto (I0,S) : S' → S •, $ L id, $ I2 = Goto (I0, L) : S → L • = R, I713 = Goto(I411, R) : $ L → * R•, = | $ R → L •, $ I810 = Goto(I411, L), Goto(I6, L): → • I3 = Goto (I 0,R) : S → R • R L , = | $ I411 = Goto (I0,*), Goto (I6,*) : I9 = Goto(I6, R) : → • L → * • R, = | $ S L = R , $ R → • L, = | $ L → • * R, = | $ R → • id, = | $ Ta có thể xây dựng bảng phân tích cú pháp LALR cho văn phạm như sau : Action Goto State = * id $ S L R 0 s411 s512 1 2 3 1 acc 2 s6
3 r2 411 810 713 512 r4 r4 6 s411 s512 810 9 713 r3 r3 810 r5 r5 9 r1 Hình - Bảng phân tích cú pháp LALR Bảng phân tích được tạo ra bởi giải thuật 4.10 gọi là bảng phân tích LALR cho văn phạm G. Nếu trong bảng không có các action đụng độ thì văn phạm đã cho gọi là văn phạm LALR(1). Họ tập hợp mục C' được gọi là họ tập hợp mục LALR(1). 2.4. Bắt lỗi. * Giai đoạn phân tích cú pháp phát hiện và khắc phục được khá nhiều lỗi. Ví dụ lỗi do các từ tố từ bộ phân tích từ vựng không theo thứ tự của luật văn phạm của ngôn ngữ. * Bộ bắt lỗi trong phần phân tích cú pháp có mục đích: + Phát hiện, chỉ ra vị trí và mô tả chính xác rõ rang các lỗi. + Phục hồi quá trìh phân tích sau khi gặp lỗi đủ nhanh để có thể phát hiện ra các lỗi tiếp theo. + Không làm giảm đáng kể thời gian xử lý các chương trình viết đúng. * Các chiến lược phục hồi lỗi. - Có nhiều chiến lược mà bộ phân tích có thể dùng để phục hồi quá trình phân tích sau khi gặp một lỗi cú pháp. Không có chiến lược nào tổng quát và hoàn hảo, có một số phương pháp dùng rộng rãi. + Phục hồi kiểu trừng phạt: Phương pháp đơn giản nhất và được áp dụng trong đa số các bộ phân tích. Mỗi khi phát hiện lỗi bộ phân tích sẽ bỏ qua một hoặc một số kí hiệu vào mà không kiểm tra cho đến khi nó gặp một kí hiệu trong tập từ tố đồng bộ. Các từ tố đồng bộ thường được xác định trước ( VD: end, ; ) Người thiết kế chương trình dịch phải tự chọn các từ tố đồng bộ. Ưu điểm: Đơn giản, không sợ bj vòng lặp vô hạn, hiệu quả khi gặp câu lệnh có nhiều lỗi.
+ Khôi phục cụm từ: Mỗi khi phát hienj lỗi, bộ phân tích cố gắng phân tích phần còn lại của câu lệnh. Nó có thể thay thế phần đầu của phần còn lại xâu này bằng một xâu nào đó cho phép bộ phân tích làm việc tiếp. Những việc này do người thiết kế chương trình dịch nghĩ ra. + Sản xuất lỗi: Người thiết kế phải có hiểu biết về các lỗi hường gặp và gia cố văn phạm của ngôn ngữ này tại các luật sinh ra cấu trúc lỗi. Dùng văn phạm này để khôi phục bộ phân tích. Nếu bọ phân tích dùng một luật lỗi có thể chỉ ra các cấu trúc lỗi phát hiện ở đầu vào. Ngoài ra ngừơi ta có cách bắt lỗi cụ thể hơn trong từng phương pháp phân tích khác nhau. 2.4.1. Khôi phục lỗi trong phân tích tất định LL. * Một lỗi được phát hiện trong phân tích LL khi: - Ký hiệu kết thúc nằm trên đỉnh ngăn xếp không đối sánh được với ký hiệu đầu vào hiện tại. - Mục M(A,a) trong bảng phân tích là lỗi (rỗng). * Khắc phục lỗi theo kiểu trừng phạt là bỏ qua các ký hiệu trên xâu vào cho đến khi xuất hiện một ký hiệu thuộc tập ký hiệu đã xác định trước gọi là tập ký hiệu đồng bộ. Xét một số cách chọn tập đồng bộ như sau: a) Đưa tất cả các ký hiệu trong Follow(A) vào tập đồng bộ hoá của ký hiệu không kết thúc A. Nếu gặp lỗi, bỏ qua các từ tố của xâu vào cho đến khi gặp một phần tử của Follow(A) thì lấy A ra khỏi ngăn xếp và tiếp tục quá trình phân tích. b) Đưa tất cả các ký hiệu trong First(A) vào tập đồng bộ hoá của ký hiệu không kết thúc A. Nếu gặp lỗi, bỏ qua các từ tố của xâu vào cho đến khi gặp một phần tử thuộc First(A) thì quá trình phân tích được tiếp tục. Ví dụ: với ví dụ trên, ta thử phân tích xâu vào có lỗi là “)id*+id” với tập đồng bộ hoá của các ký hiệu không kết thúc được xây dựng từ tập First và tập Follow của ký hiệu đó. Ngăn xếp Xâu vào Hành động $E )id*+id$ M(E,)) = lỗi, bỏ qua ‘)’ để găp id ∈ First(E) $E id*+id$ E->TE’ $E’T id*+id$ T->FT’ $E’T’F id*+id$ F->id $E’T’id id*+id$ rút gọn id
$E’T’ *+id$ T’->*FT’ $E’T’F* *+id$ rút gọn * $E’T’F +id$ M(F,+) = lỗi, bỏ qua. Tại đây xảy ra hai trường hợp(ta chọn a): a).bỏ qua + vì id ∈ First(F) b).bỏ qua F vì + ∈ Follow(F) $E’T’F id$ F->id $E’T’id id$ rút gọn id $E’T’ $ T’->ε $E’ $ E’->ε $ $ 2.4.2. Khôi phục lỗi trong phân tích LR. Một bộ phân tích LR sẽ phát hiện ra lỗi khi nó gặp một mục báo lỗi trong bảng action (chú ý sẽ không bao giờ bộ phân tích gặp thông báo lỗi trong bảng goto). Chúng ta có thể thực hiện chiến lược khắc phục lỗi cố gắng cô lập đoạn câu chứa lỗi cú pháp: quét dọc xuống ngăn xếp cho đến khi tìm được một trạng thái s có một hành động goto trên một ký hiệu không kết thúc A ngay sau nó. Sau đó bỏ đi không hoặc nhiều ký hiệu đầu vào cho đến khi gặp một ký hiệu kết thúc a thuộc Follow(A), lúc này bộ phân tích sẽ đưa trạng thái goto(s,A) vào ngăn xếp và tiếp tục quá trình phân tích.
Phương pháp phân tích bảng CYK (Cocke – Younger – Kasami) - Giải thuật làm việc với tất cả các VP PNC. Thời gian phân tích là: n3 (n là độ dài xâu vào cần phân tích), nếu văn phạm không nhập nhằng thì thờI gian phân tích là: n2. - Điều kiện của thuật toán là văn phạm PNC ở dạng chuẩn chômsky (CNF) và không có ε sản xuất (sản xuất A → ε ) và các kí hiệu vô ích. Giải thuật CYK: - Tạo một hình tam giác (mỗi chiều có độ dài là n , n là độ dài của xâu). Thực hiện giải thuật: Begin 1) For i:=1 to n do ∆ ij = { A | A → a là một sản xuất và a là kí hiệu thứ i trong w}; 2) For j:=2 to n do For i:=1 to (n – j +1) do Begin ∆ ij = ∅; For k:=1 to (j -1) do ∆ ij = ∆ ij ∪ { A | A → BC là một sản xuất; B ∈ ∆ ik C∈ ∆ i+k, j -k }; end; end; Ví dụ: Xét văn phạm chuẩn chômsky S → AB|BC; A → BA|a; B → CC|b; C → AB|a; (1) (2) (3) (4) (5) (6) (7) (8) Xâu vào w= baaba; i j b a a b a B A,C A,C B A,C S,A B S,C S,A ∅ B B ∅ S,A,C