Luận văn:Nghiên cứu ứng dụng LEX/YACC để hỗ trợ phát sinh mã nguồn trong lập trình ứng dụng

Chia sẻ: Nhung Thi | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST

Báo xấu

178
lượt xem 31
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nghiên cứu ứng dụng LEX/YACC để hỗ trợ phát sinh mã nguồn trong lập trình ứng dụngNghiên cứu ứng dụng LEX/YACC để hỗ trợ phát sinh mã nguồn trong lập trình ứng dụngNghiên cứu ứng dụng LEX/YACC để hỗ trợ phát sinh mã nguồn trong lập trình ứng dụng

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn:Nghiên cứu ứng dụng LEX/YACC để hỗ trợ phát sinh mã nguồn trong lập trình ứng dụng

1 Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG Ngư i hư ng d n khoa h c: PGS.TS. VÕ TRUNG HÙNG TR N VĂN KHÁNH Ph n bi n 1: PGS.TSKH. TR N QU C CHI N NGHIÊN C U NG D NG LEX/YACC Ph n bi n 2:TS.TRƯƠNG CÔNG TU N Đ H TR PHÁT SINH MÃ NGU N TRONG L P TRÌNH NG D NG Lu n văn s ñư c b o v trư c H i ñ ng ch m Chuyên ngành : KHOA H C MÁY TÍNH Lu n văn t t nghi p Th c sĩ K thu t h p t i Đ i h c Mã s : 60.48.01 Đà N ng vào ngày 18 tháng 6 năm 2011 TÓM T T LU N VĂN TH C SĨ K THU T Có th tìm hi u lu n văn t i: Đà N ng – Năm 2011 - Trung tâm Thông tin - H c li u, Đ i h c Đà N ng - Trung tâm H c li u, Đ i h c Đà N ng
2 3 M Đ U th ng v cách cài ñ t, qui trình s d ng và minh h a qua m t s bài 1. Tính c p thi t toán c th . Trong công ngh thông tin, cùng v i s phát tri n các thi t b 3. Ý nghĩa c a ñ tài ph n c ng là s hình thành và phát tri n c a các k thu t l p trình. Câu Phân tích, ñánh giá hi u qu trong l p trình ng d ng b ng cách h i “làm th nào ñ l p trình nhanh và hi u qu nh t cho m t bài toán s d ng công c Lex/Yacc. Cung c p tài li u v công c Lex/Yacc c th nào ñó?” luôn là cơ s ñ các phương pháp, k thu t và ngôn m t cách h th ng và ñ y ñ nh t có th ñ ph c v cho vi c phát ng l p trình ra ñ i. M t trong nh ng k thu t ra ñ i s m, t n t i và tri n ng d ng sau này. Góp ph n thúc ñ y vi c ng d ng công c phát tri n cho ñ n t n bây gi ñó là k thu t t ñ ng sinh mã ngu n. Lex/Yacc trong l p trình ng d ng t i Vi t Nam. Giúp cho h c sinh, T ñ ng sinh mã ngu n là m t ý tư ng táo b o và mang l i sinh viên có th tham kh o d dàng v Lex/Yacc trong h c t p cũng hi u qu cao trong l p trình. Thay vì l p trình viên ph i tr c ti p vi t như l p trình sau này. mã ñ gi i quy t m t bài toán c th nào ñó thì h ch c n ñ c t theo 4. Phương pháp nghiên c u m t h qui ư c nh t ñ nh (các ngôn ng ñ c t ) và trên cơ s ñó, máy Khi th c hi n ñ tài, chúng tôi ñã k t h p gi a phương pháp tính s t ñ ng s n sinh ra mã ngu n tương ng. M t trong nh ng nghiên c u lý thuy t và phương pháp nghiên c u th c nghi m. V m t ngôn ng , công c như v y là Lex/Yacc. lý thuy t, chúng tôi ti n hành nghiên c u t ng quan v chương trình Lex/Yacc có ch c năng phát sinh mã ngu n trong lĩnh v c t o d ch, các b phân tích t v ng và cú pháp, các b phân tích và phát sinh các chương trình d ch và sau này ñư c m r ng sang nhi u lĩnh v c mã ngu n Lex/Yacc. V m t th c nghi m, chúng tôi ti n hành m t s khác. Đ cài ñ t m t trình biên d ch, chúng ta ch c n cung c p các công c h tr phân tích t v ng và cú pháp và áp d ng chúng trên m t ñ t t ng pháp, Lex/Yacc s t ñ ng sinh ra mã ngu n C ho c s bài toán tiêu bi u v i Lex/Yacc. Pascal. Vi c này cho phép ti t ki m r t nhi u th i gian cũng như h n 5. Đ i tư ng và ph m vi nghiên c u ch l i (bugs) trong mã ngu n. Đ i tư ng nghiên c u chính c a ñ tài là chương trình d ch, các Hi n nay, các trư ng ph thông và các trư ng ñ i h c trong ngôn ng ñ c t , các công c phát sinh t ñ ng mã ngu n. Tuy nhiên, nư c h u h t ñã ñưa ngôn ng l p trình b c cao như C/C++, Pascal,... chúng tôi gi i h n ph m vi nghiên c u c a mình trên Lex/Yacc và phát vào gi ng d y. V n ñ ñ t ra là làm th nào ñ gi m chi phí v sinh mã ngu n trong ngôn ng l p trình C/C++. nghiên c u, ti p c n và tăng hi u qu s d ng các ngôn ng l p trình 6. C u trúc lu n văn b c cao. V i công c này, h c sinh, sinh viên các trư ng có ñi u ki n Báo cáo c a lu n văn t t nghi p này ñư c t ch c thành 3 ti p c n và s d ng có hi u qu các công c l p trình c a mình. chương. Trong chương 1, chúng tôi trình bày các k t qu nghiên c u Hi n nay chưa có m t nghiên c u mang tính h th ng v t ng quan v chương trình d ch, .... Chương 2 chúng tôi trình bày m t công c Lex/Yacc nư c ta (ñã có m t s trư ng gi i thi u v cách h th ng v Lex/Yacc. Trong chương cu i, chúng tôi nêu m t s ví Lex/Yacc trong môn h c Chương trình d ch nhưng chưa ñ y ñ ). Vì d qua Lex/Yacc và trang web gi i thi u v Lex/Yacc. v y, vi c nghiên c u ng d ng công c Lex/Yacc ñ nâng cao hi u qu trong l p trình ng d ng là v n ñ c p thi t. 2. M c ñích c a ñ tài Nghiên c u ng d ng Lex/Yacc ñ tăng hi u qu khi l p trình ng d ng. Sau khi nghiên c u, s trình bày l i m t cách h
4 5 Chương 1. NGHIÊN C U T NG QUAN Chương trình ngu n Chương này trình bày các v n v liên quan ñ n khái ni m chương trình d ch, c u trúc c a m t trình biên d ch và b phân tích t Phân tích t v ng v ng và phân tích cú pháp. 1.1. Chương trình d ch Phân tích cú pháp 1.1.1. Khái ni m Chương trình d ch, hay còn g i là trình biên d ch, ñơn gi n là Phân tích ng nghĩa m t chương trình làm nhi m v ñ c m t chương trình ngu n ñư c Qu n lý X lý l i vi t b ng m t ngôn ng (g i là ngôn ng ngu n và thư ng là các b ng ký ngôn ng l p trình b c cao) r i d ch nó thành m t chương trình ñích Sinh mã trung gian tương ñương m t ngôn ng khác (g i là ngôn ng ñích và ña s các trư ng h p thì nó là ngôn ng máy). M t ph n quan tr ng trong quá T i ưu mã trình d ch là ghi nh n l i các l i có trong chương trình ngu n ñ thông báo l i cho ngư i vi t chương trình. Sinh mã ñích Chương trình ngu n Trình biên d ch Chương trình ñích Chương trình ñích Hình 1.2 Các giai ño n c a m t trình biên d ch Hình 1.1 Mô hình c a m t trình biên d ch Phân tích t v ng: ñ c t ng ký t g p l i thành token. Ví d , chúng ta có m t chương trình ngu n vi t b ng ngôn ng Token có th là m t danh bi u, t khóa, m t ký hi u,... Chu i ký t l p trình b c cao (Pascal, C...). Đ có th th c hi n ñư c chương t o thành m t token g i là tr t v ng c a token ñó. trình này trên máy tính thì ph i s d ng m t trình biên d ch Phân tích cú pháp và phân tích ng nghĩa: xây d ng c u (Compiler) ñ chuy n nó sang chương trình ñích là ngôn ng máy trúc phân c p cho chu i các token, bi u di n b i cây cú pháp và ki m (d ng mã nh phân). tra ngôn ng theo cú pháp. 1.1.2. Qui trình d ch Sinh mã trung gian: sau khi phân tích ng nghĩa, m t s Qui trình thông thư ng c a m t trình biên d ch ñư c trình trình biên d ch s t o ra m t d ng bi u di n trung gian c a chương bày như sau: trình ngu n. Chúng ta có th xem d ng bi u di n này như m t chương trình dành cho m t máy tr u tư ng. Chúng có hai ñ c tính quan tr ng: d sinh và d d ch thành chương trình ñích. D ng bi u di n trung gian có r t nhi u lo i. Thông thư ng, ngư i ta s d ng d ng "mã máy 3 ñ a ch " (three-address code), tương t như d ng
6 7 h p ng cho m t máy mà trong ñó m i v trí b nh có th ñóng vai Giai ño n phân tích t v ng thư ng g p l i khi các ký t không th ghép thành m t token. Giai ño n phân tích cú pháp g p l i trò như m t thanh ghi. Mã máy 3 ñ a ch là m t dãy các l nh liên khi các Token không th k t h p v i nhau theo ñúng c u trúc ngôn ti p, m i l nh có th có t i ña 3 ñ i s . ng . Giai ño n phân tích ng nghĩa báo l i khi các toán h ng có ki u T i ưu mã: giai ño n t i ưu mã c g ng c i thi n mã trung không ñúng yêu c u c a phép toán hay các k t c u không có nghĩa gian ñ có th có mã máy th c hi n nhanh hơn. ñ i v i thao tác th c hi n m c dù chúng hoàn toàn ñúng v m t cú pháp. Sinh mã: giai ño n cu i cùng c a biên d ch là sinh mã ñích, 1.2. Phân tích t v ng thư ng là mã máy ho c mã h p ng . Các v trí vùng nh ñư c ch n 1.2.1. Khái ni m l a cho m i bi n ñư c chương trình s d ng. Sau ñó, các ch th Phân tích t v ng là giai ño n ñ u tiên c a m i trình biên d ch. trung gian ñư c d ch l n lư t thành chu i các ch th mã máy. V n ñ Nó có ch c năng là phân tích chương trình ngu n. Nhi m v ch y u quy t ñ nh là vi c gán các bi n cho các thanh ghi. c a nó là ñ c các ký hi u nh p r i t o ra m t chu i các Token ñư c Qu n lý b ng ký hi u: m t nhi m v quan tr ng c a trình s d ng b i b phân tích cú pháp. S tương tác này ñư c th hi n biên d ch là ghi l i các ñ nh danh ñư c s d ng trong chương trình như hình sau: ngu n và thu th p các thông tin v các thu c tính khác nhau c a m i Token ñ nh danh. Nh ng thu c tính này có th cung c p thông tin v v trí Chương B phân B phân lưu tr ñư c c p phát cho m t ñ nh danh, ki u c a ñ nh danh và n u trình ngu n tích cú tích t v ng ñ nh danh là tên c a m t th t c thì thu c tính là các thông tin v s pháp lư ng và ki u c a các ñ i s , phương pháp truy n ñ i s và ki u tr L y token k v c a th t c n u có. B ng ký hi u (symbol table) là m t c u trúc d li u mà m i B ng ký hi u ph n t là m t m u tin dùng ñ lưu tr m t ñ nh danh, bao g m các Hình 1.3 Giao di n c a b phân tích t v ng trư ng lưu gi ký hi u và các thu c tính c a nó. C u trúc này cho Trong ñó b phân tích t v ng ñư c thi t k như m t th t c phép tìm ki m, truy xu t danh bi u m t cách nhanh chóng. ñư c g i b i b phân tích cú pháp, tr v m t token khi ñư c g i. Trong quá trình phân tích t v ng, danh bi u ñư c tìm th y và B ng ký hi u (symbol table) là m t c u trúc d li u mà m i ph n t nó ñư c ñưa vào b ng ký hi u nhưng nói chung các thu c tính c a nó là m t m u tin dùng ñ lưu tr m t ñ nh danh, bao g m các trư ng có th chưa xác ñ nh ñư c trong giai ño n này. lưu gi ký hi u và các thu c tính c a nó. C u trúc này cho phép tìm X lý l i: M i giai ño n có th g p nhi u l i, tuy nhiên sau khi ki m, truy xu t danh bi u m t cách nhanh chóng. phát hi n ra l i, tùy thu c vào trình biên d ch mà có các cách x lý 1.2.2. ng d ng l i khác nhau, ch ng h n : 1.2.2.1. M t s v n ñ liên quan ñ n giai ño n phân - D ng và thông báo l i khi g p l i ñ u tiên (Pascal). tích t v ng - Ghi nh n l i và ti p t c quá trình d ch (C).
8 9 1.2.2.2. Đ c t th t (Specification of Token) 1.3.2. ng d ng 1.2.3. M t s phương pháp, công c hi n có 1.3.2.1. L i và các chi n lư c ph c h i l i c a giai 1.3. Phân tích cú pháp ño n phân tích cú pháp 1.3.1. Khái ni m 1.3.2.2. Phân tích cú pháp t trên xu ng M i ngôn ng l p trình ñ u có các quy t c di n t c u trúc cú 1.3.3. M t s phương pháp, công c hi n có pháp c a các chương trình có ñ nh d ng ñúng. Các c u trúc cú pháp . này ñư c mô t b i văn ph m phi ng c nh. B phân tích cú pháp có Chương 2. NGHIÊN C U CÔNG C LEX/YACC ch c năng là phân tích cú pháp chương trình ngu n. Nhi m v ch Chương này trình bày nh ng k t qu nghiên c u v vi c s y u c a nó là nh n chu i các Token t b phân tích t v ng và xác d ng công c Lex và Yacc. Ph n ñ u gi i thi u m i liên h gi a công nh n r ng chu i này có th ñư c sinh ra t văn ph m c a ngôn ng c Lex, Yacc v i trình biên d ch và các ph n ti p theo ñư c s d ng ngu n b ng cách t o ra cây phân tích cú pháp cho chu i. B phân ñ mô t m t cách chi ti t v Lex và Yacc. tích cú pháp cũng có cơ ch ghi nh n các l i cú pháp theo m t 2.1. Gi i thi u phương th c linh ho t và có kh năng ph c h i ñư c các l i thư ng Công c Lex và Yacc ñư c s d ng ñ phân tích t v ng và g p ñ có th ti p t c x lý ph n còn l i c a chu i ñ u vào. phân tích cú pháp. Lex và yacc có m i liên h qua l i v i nhau, tìm B ng ký hi u (symbol table) là m t c u trúc d li u mà m i hi u Hình 2.1. Intput ph n t là m t m u tin dùng ñ lưu tr m t ñ nh danh, bao g m các trư ng lưu gi ký hi u và các thu c tính c a nó. C u trúc này cho phép tìm ki m, truy xu t danh bi u m t cách nhanh chóng. Lexical Analyzer Lex Chương trình Token Cây phân ngu n tích cú pháp Syntax Analyzer Yacc B phân tích t B phân tích v ng cú pháp Code Generator L y token k Output B ng ký hi u Hình 2.1 M i liên h gi a Lex và Yacc Hình 1.10 Giao di n c a b phân tích cú pháp trong trình biên d ch. Trong ñó, Input là xâu ký t ñ u vào. Lexical Analyzer là b phân tích t v ng ñư c công c Lex phân tích. B phân tích này có
10 11 ch c năng chuy n xâu ký t ñ u vào thành các Token. Syntax Lex không là m t ngôn ng ñ y ñ , nhưng khá t t cho vi c Analyzer là b phân tích cú pháp ñư c công c Yacc phân tích. B phát sinh mã ñang ñ i di n cho m t ñ c tính ngôn ng m i mà có th phân tích này có ch c năng nh n các Token t b phân tích cú pháp phù h p nh ng ngôn ng l p trình khác nhau, g i là ngôn ng ch và phân tích t o thành cây cú pháp. Code Generator có ch c năng (host languages). Ch có ch c năng ngôn ng chung có th sinh mã sinh mã t cây cú pháp ñư c cung c p b i b phân tích cú pháp. ñ ch y trên máy tính khác nhau, Lex có th vi t mã trong nh ng Output là ño n mã ñư c sinh ra. ngôn ng ch khác nhau. Ngôn ng ch ñư c s d ng cho sinh mã 2.2. LEX ñích b i Lex và cũng cho nh ng ño n chương trình thêm b i ngư i 2.2.1. Gi i thi u s d ng. Nh ng thư vi n th c thi tương thích cho nh ng ngôn ng Lex là m t b l p chương trình ñư c thi t k ñ x lý t ch khác nhau cũng ñư c cung c p. Đi u này làm Lex có th tương v ng c a nh ng dòng ký t ñ u vào. Nó ch p nh n ngôn ng b c thích ñ i v i nh ng môi trư ng và ngư i s d ng khác nhau. M i cao, ñ t t ñ nh hư ng cho vi c so kh p chu i ký t , và sinh ra ng d ng có th tr c ti p k t h p t i ph n c ng và thao tác v i ngôn chương trình ñích ph c v vi c ñoán nh n bi u th c chính quy. Bi u ng ch thích h p. Hi n nay, ngôn ng ch ñư c h tr như là C. th c chính quy ñư c ch ñ nh b i ngư i dùng t ngu n ñ c t ñư c Lex tích h p trên UNIX, GCOS, OS/ 370, nhưng Lex phát sinh mã cho b i Lex. Lex vi t mã ñoán nh n nh ng bi u th c dòng ñư c b t c v i trình biên d ch t n t i thích h p. nh p vào và phân chia dòng ñư c nh p vào trong nh ng chu i so 2.2.2. Các ch c năng kh p v i bi u th c. T p tin ngu n Lex là s t p h p nh ng bi u th c 2.2.2.1. Ngu n Lex (Lex Source) chính quy và các ño n chương trình. Khi m i bi u th c xu t hi n Khuôn d ng chung c a ngu n Lex g m ba ph n như sau: trong ñ u vào t i chương trình ñư c vi t b i Lex, ño n tương ng {definitions} %% ñư c th c thi. {rules} %% Ngư i s d ng cung c p b sung thêm mã ngoài bi u th c {user subroutines} cho kh p m u v i thao tác c a nó c n hoàn thành, bao g m mã ñư c Ph n ñ nh nghĩa (definitions): ñ t ph n ñ u chương trình, vi t b i b sinh mã khác. Chương trình ñoán nh n nh ng bi u th c dùng ñ ñ nh nghĩa các cú pháp c a công th c, các bi n, các ki u,… ñư c phát sinh trong ngôn ng l p trình m c ñích chung ñư c g i Ph n lu t (rules): ph n này ñư c ñ t trong c p d u %%, trình như nh ng ño n chương trình c a ngư i s d ng. Như v y, m t ngôn bày n i dung các lu t. ng b c cao ñư c cung c p ñ vi t nh ng bi u th c d ng chu i s Ph n chương trình con (user subroutines): ñ t ph n cu i ñư c so kh p v i bi u th c ñư c sinh ra thì không có s khác bi t. chương trình, trình bày các hàm, các th t c con, … Đi u này tránh b t bu c ngư i s d ng mu n s d ng m t ngôn ng 2.2.2.2. Nh ng bi u th c chính quy Lex (Lex Regular thao tác chu i cho vi c phân tích ñ u vào ñ vi t nh ng chương trình Expressions) x lý trong chu i như th và thư ng không thích h p trình bày ngôn 2.2.2.3. Nh ng ho t ñ ng Lex (Lex Actions) ng d ng chu i.
12 13 2.2.2.4. Nh ng ñ nh nghĩa ngu n Lex (Lex Source ư c lư ng ñ bao g m b phân tích t v ng như m t ph n c a ñ c t Definitions) t p. Nó có th h u ích ñ n bao g m các chương trình t t khác. Như 2.2.2.5. Tóm lư c c a ngu n ñ nh d ng (Summary of v y, m i ñ c t t p g m có ba ph n: ph n khai báo, lu t(ng pháp) và Source Format) chương trình. Nh ng ph n ñư c tách ra b i hai d u “%%''. Nói cách 2.2.3. Cách s d ng khác, m t ñ c t ñ y ñ v t p 2.2.4. Nh n xét declarations %% 2.3. YACC rules %% 2.3.1. Gi i thi u programs Yacc cung c p m t công c chung ñ v n d ng c u trúc trên Ph n khai báo có th tr ng r ng. Hơn n a, n u ph n chương ñ u vào t i m t chương trình máy tính. Yacc chu n b s d ng ñ t t trình b b sót, hai d u %% cũng có th b b sót. Như v y, ñ c t c a quá trình ñư c nh p vào, ñi u này bao g m nh ng lu t ñang mô Yacc nh nh t h p l là t c u trúc ñư c nh p vào, mã s ñư c kéo theo khi nh ng lu t ñư c %% ñoán nh n, và m t m c th p thông thư ng ñ làm ñ u vào cơ b n. rules Yacc sau ñó phát sinh m t hàm ñ ki m soát quá trình ñư c nh p nh ng ch tr ng, nh ng b ng, và nh ng dòng m i ñư c l ñi ch có vào. Ch c năng này, g i là b phân tích, l nh do ngư i s d ng cung ñi u chúng có th không xu t hi n trong nh ng tên ho c nh ng ký hi u c p là th t c ñ u vào b c th p (b phân tích t v ng) ñ thu nh t ñư c lưu tr nhi u ñ c tính. Nh ng chú d n có th xu t hi n m i nơi nh ng m c cơ b n (g i là nh ng Token) t dòng ñư c nh p vào. là m t tên thì h p l , chúng ñư c bao b i c p /*. . . */, như trong C. Nh ng token này ñư c t ch c theo nh ng lu t c u trúc ñư c nh p 2.3.2.2. Nh ng ho t ñ ng (Actions) vào, g i là nh ng lu t ng pháp, khi m t trong s lu t này ñã ñư c 2.3.2.3. S phân tích t v ng (Lexical Analysis) ñoán nh n, r i s d ng mã ñư c cung c p cho lu t này, m t ho t 2.3.2.4. B phân tích làm vi c như th nào (How the ñ ng ñư c kéo theo, nh ng ho t ñ ng có nh ng kh năng tr l i Parser Works) nh ng giá tr và làm s d ng nh ng giá tr c a ho t ñ ng khác. 2.3.2.5. S nh p nh ng và nh ng xung ñ t (Ambiguity Yacc ñư c vi t trong m t ng pháp linh ho t, nh ng ho t and Conflicts) ñ ng và th t c con ñ u ra, cũng như trong C. Hơn n a, nhi u quy 2.3.2.6. M c ưu tiên (Precedence) ư c cú pháp c a Yacc ñi theo sau C. 2.3.3. Cách s d ng 2.3.2. Các ch c năng 2.3.4. Nh n xét 2.3.2.1. Nh ng ñ c t cơ b n (Basic Specifications) Nh ng tên tham chi u t i nh ng Token ho c nh ng ký hi u chưa k t thúc. Yacc yêu c u nh ng tên token như ñã ñư c khai báo. Ngoài ra, nh ng lý do ñư c bàn lu n Trong m c 2.3.2.3, nó thư ng
14 15 Chương 3. NGHIÊN C U NG D NG LEX/YACC chu n ñ c t Lex và t ñ ng sinh ra chương trình trong mã ngu n Chương này t p trung nghiên c u quy trình v n d ng Lex và ñư c ch n (thư ng là C/C++) nh m ki m tra tính ñúng ñ n và th c Yacc và ñưa ra ví d v cách s d ng. Đ s d ng Lex và Yacc thi các qui t c tính toán. Mô t vi t d ng các c p bi u th c thông chúng ta c n cài ñ t các công c h tr biên d ch và phát sinh mã thư ng và mã C, g i là các quy t c. Flex t o ra k t qu là m t t p tin ngu n tương ng v i t ng giai ño n. mã ngu n C (m c ñ nh v i tên g i là lex.yy.c). T p tin này ñư c biên 3.1. Cài ñ t các ng d ng d ch và liên k t v i thư vi n –lfl ñ s n xu t m t th c thi. Khi th c Hi n t i có r t nhi u ng d ng h tr x lý cho Lex và Yacc, tuy thi ñư c ch y, nó phân tích ñ u vào c a các bi u th c thông thư ng nhiên trong th nghi m c a mình chúng tôi ñã cài ñ t các công c sau: và khi bi u th c nh p vào ñúng ñ n thì s th c thi các ño n mã 3.1.1. Bison C/C++ tương ng. Bison là m t b phân tích cú pháp theo tiêu chu n ñ c t c a Flex là ph n m m ñư c cung c p b i Đ i h c California và Yacc. Nó s phát sinh t ñ ng m t chương trình x lý tương ng v i phiên b n ñ u tiên ñư c c p phép vào năm 1990 theo tiêu chu n mã các t p tin ñ u vào thi t k cho Yacc. ngu n m . Sau ñó, mã ngu n này ñư c ti p t c phát tri n và phân Bison ñư c vi t b i Robert Corbett và Richard Stallman ph i mi n phí b i Vern Paxson thu c Đ i h c Berkeley. Chúng ta có trong d án mã ngu n m ñ xây d ng b phân tích cú pháp theo tiêu th t i Flex t i http://www.gnu.org/software/flex/. chu n ñ c t c a Yacc. Chúng ta có th t i ph n m m mã ngu n m 3.1.3. Dev-C++ này t i trang http://www.gnu.org/software/bison/. Dev-C++ là m t môi trư ng phát tri n tích h p (IDE) khá ñ y ñ T p tin ñ u vào c n th c hi n theo các quy ư c c a Yacc và các tính năng dành cho các ngôn ng l p trình C/C++. Nó s d ng tên t p tin ñư c ñ t tùy ý nhưng có ph n m r ng là .y (ví d : calc.y). MinGW c a GCC (GNU Compiler Collection) làm trình biên d ch Không gi ng như Yacc g c, các t p tin ñư c t o ra không có tên c các t p tin chương trình. Dev-C++ cũng có th ñư c s d ng k t h p ñ nh, nhưng thay vào ñó là nó s d ng các ti n t c a t p tin ñ u vào. v i Cygwin hay b t kỳ trình biên d ch GCC khác. Hơn n a, n u chúng ta c n ph i ñ t mã l nh C++ trong t p tin ñ u M t s tính năng chính c a Dev-C++ là: vào thì có th k t thúc tên c a t p tin b ng ph n m r ng gi ng như - H tr các trình biên d ch d a GCC. c a C++ (ví d : .ypp ho c .y++), sau ñó Bison s theo ph n m r ng - Tích h p s a l i (b ng cách s d ng GDB). c a chúng ta ñ ñ t tên cho t p tin xu t (.cpp ho c .c++ ). Ví d , m t - Qu n lý d án. mô t ng pháp t p tin có tên parse.yxx s cho b phân tích cú pháp - Tùy ch nh các ch ñ so n th o và phát hi n l i cú pháp t o ra trong m t t p tin v i tên tương ng parse.tab.cxx. trong chương trình. 3.1.2. Flex - Duy t các l p (Class Browser). Flex là m t công c ñ t o ra các b ki m tra nh m công - Nhanh chóng t o ra các c a s , giao di n ñi u khi n, thư vi n nh n các m u t v ng trong t p tin ñ u vào ñư c ñ c t theo tiêu tĩnh và ñ ng (các t p tin DLL). chu n c a Lex. Flex ñ c các t p tin ñ u vào cho trư c vi t theo tiêu - H tr các m u cho vi c t o ra các lo i d án c a riêng b n.
16 17 - Cho phép t o ra các Makefile. bas.exe có th th c thi ñư c. T ph n chính chúng g i yyparse ñ ch y - Ch nh s a và biên d ch t p tin mã ngu n. trình biên d ch. Hàm yyparse t ñ ng g i yylex ñ thu ñư c m i token. - H tr CVS. C th các bư c như sau: Chúng ta có th t i Dev-C++ t http://www.bloodshed.net/devcpp.html. Bư c 1: So n th o ph n ñ t t Yacc trên công c Notepad và 3.2. Qui trình v n d ng LEX/YACC lưu l i tên t p v i ph n m r ng .y (ví d bas.y), b vào thư m c bin Quy trình chung ñ s d ng Yacc và Lex khi phát sinh ng c a Bison v a cài ñ t trên. d ng ñư c th hi n qua sơ ñ sau: Bư c 2: So n th o ph n ñ t t Lex trên công c Notepad và (yyparse) source lưu l i tên t p v i ph n m r ng .l (ví d bas.l), b vào thư m c bin bas.y yacc y.tab.c c a Flex v a cài ñ t trên. Bư c 3: Th c hi n biên d ch trên môi trư ng Win v i Command y.tab.h gcc bas.exe Prompt như sau: T c a s h ñi u hành Win, ch n Start → Programs → Accessories → Command Prompt, h p tho i Command Prompt bas.l lex lex.yy.c Compiled xu t hi n, chuy n d u nh t con tr v thư m c g c C:\>. (yylex) output Bư c 3.1. Th c hi n l nh biên d ch cho t p Yacc. Chuy n Hình 3.1 Minh h a quy trình v n d ng và cách ñ t tên v i Lex và Yacc con tr v thư m c bin c a Bison ñã ñư c cài ñ t C:\>bison\bin và Đây là các bư c mà chúng ta s th c hi n khi mu n vi t m t th c hi n theo cú pháp: trình biên d ch trong ngôn ng l p trình C/C++. Đ u tiên, chúng c n Bison {options} source-file mô t t t c m u ñang so kh p nh ng lu t cho Lex (bas.l) và lu t ng Trong ñó: Bison là công c ñ t t Yacc. pháp cho Yacc (bas.y). Nh ng l nh ñ t o ra trình biên d ch v i tên source-file là tên c a t p ñư c ñ t t b i ngu n bas.exe. Các l nh th c hi n như sau: Yacc, v i ph n ñuôi m r ng .y. bison –d bas.y # sinh ra y.tab.h, y.tab.c Flex bas.l # t p ñư c sinh ra lex.yy.c options là nh ng tùy ch n có th ñư c ch rõ t p tin gcc lex.yy.c y.tab.c –o bas.exe # biên d ch t o t p .exe ñư c sinh ra t dòng l nh, ñư c cho b i b ng sau: Yacc ñ c s mô t ng pháp trong bas.y và phát sinh m t b B ng 3.1 Mô t các tùy ch n (options) phân tích cú pháp (b phân tích), mà bao g m hàm yyparse, trong Tuỳ ch n (options) Mô t t p y.tab.c. Đư c bao g m trong t p bas.y là token khai báo. Tuỳ -o Tên t p ñư c sinh ra. ch n -d gây ra yacc ñ phát sinh nh ng ñ nh nghĩa cho nh ng token -c S d ng tên t p thích h p lex.yy và ñ t chúng trong t p y.tab.h. Lex ñ c s mô t m u trong bas.l, -d Bao g m ph n tên t p m r ng v i ñuôi .h t p thư bao g m t p y.tab.h, và phát sinh m t b phân tích t v ng, mà bao vi n và ñuôi .c t p chương trình m t ñ nh cho C và g m hàm yylex, trong t p lex.yy.c. C++ … … Cu i cùng, gcc (GNU Compiler Collection) liên k t ñ t o ra
18 19 Yacc sinh ra t p thư vi n v i tên ph n m r ng .h và t p chương | (côngth c) | côngth c + côngth c trình x lý v i tên ph n m r ng .c. | côngth c - côngth c | côngth c * côngth c Bư c 3.2. Th c hi n l nh biên d ch cho t p Lex. Chuy n con | côngth c / côngth c tr v thư m c bin c a Flex ñã ñư c cài ñ t C:\>Flex\bin và th c Đ tri n khai ng d ng b ng Lex/Yacc, trư c h t chúng ta ph i hi n theo cú pháp: ñ c t các bi u th c chính qui miêu t các token ñư c dùng ñ xây FLex source-file d ng công th c và ñ c t cú pháp c a công th c và tính giá tr công Trong ñó: Flex là công c ñ t t Lex. th c. Ti p ñó, dùng các công c như Bison ho c Ayacc, Lex ho c source-file là tên c a t p ñư c ñ t t b i ngu n Lex, Flex và công c sinh mã cygwin ñ phát sinh chương trình th c thi. v i ph n ñuôi m r ng .l. T p ñư c Lex sinh ra v i C th các bư c tri n khai như sau: tên ph n m r ng .c. Bư c 1: S d ng h so n th o b t kỳ ñ t o t p tin calc.y Bư c 3.3. Th c hi n liên k t Lex và Yacc b ng cách s d ng ch a n i dung theo ngôn ng ñ c t Yacc ñ ñ c Dev-C++ ñã ñư c cài ñ t trên ñ sinh ra t p ñích th c thi t cú pháp c a công th c và tính giá tr công th c ñư c v i ph n ñuôi m r ng .exe, theo cú pháp sau: như sau: gcc lexname.c yaccname.c –o %{ #include Trong ñó:gcc là t p h tr biên d ch các t p chương trình c a Dev-C++. void yyerror(char *); int yylex(void); lexname.c là t p Lex v a ñư c sinh ra trên. int sym[26]; %} yaccname.c là t p Yacc v a ñư c sinh ra trên. %token INTEGER VARIABLE %left '+' '-' -o là tên t p ñích ñư c sinh ra v i ph n m r ng .exe. %left '*' '/' 3.3. ng d ng th nghi m %% program: 3.3.1. Phát bi u bài toán program statement '\n' | /* NULL */ Xây d ng m t chương trình cho phép tính toán m t bi u th c s ; statement: h c nh p vào t bàn phím (dư i d ng 1 xâu ký t ) và in ra k t qu expression { printf("%d\n", $1); } sau khi tính toán bi u th c ñó. Ví d : nh p vào xâu “2+(3+4)*2” và | VARIABLE '=' expression { sym[$1] ; = $3; } k t qu tr v là 16. expression: INTEGER 3.3.2. Các bư c tri n khai | VARIABLE { $$ = sym[$1]; } | expression '+' expression { $$ = $1 + $3; } V m t hình th c, ta có th ñ nh nghĩa cú pháp c a công th c | expression '-' expression { $$ = $1 - $3; } m c ñơn gi n như sau: | expression '*' expression { $$ = | expression '/' expression { $$ = $1 * $3; $1 / $3; } } h ngs = chu i t 1 t i n ký s th p phân | '(' expression ')' { $$ = $2; } toánt = + | - | * | / ; d u ngăn = ( | ) %% côngth c = h ngs void yyerror(char *s)
20 21 { fprintf(stderr, "%s\n", s); Ph n m m này s t ñ ng phát sinh ra 2 t p. T p thư vi n y.tab.h } và t p chương trình y.tab.c trong C v i n i dung như sau: int main(void) { y.tab.h có n i dung: yyparse(); /* Tokens. */ } #ifndef YYTOKENTYPE Bư c 2: S d ng h so n th o b t kỳ ñ t o t p tin calc.l # define YYTOKENTYPE enum yytokentype ch a n i dung theo ngôn ng ñ c t Lex ñ ñ c t { các bi u th c chính qui miêu t các token ñư c INTEGER = 258, VARIABLE = 259 dùng ñ xây d ng công th c như sau: }; /* calculator #1 */ #endif %{ #if ! defined YYSTYPE && ! defined #include "y.tab.h" YYSTYPE_IS_DECLARED #include typedef int YYSTYPE; void yyerror(char *); # define YYSTYPE_IS_TRIVIAL 1 %} %% # define yystype YYSTYPE /* obsolescent; will be [a-z] { withdrawn */ yylval = *yytext - 'a'; # define YYSTYPE_IS_DECLARED 1 return VARIABLE; #endif } extern YYSTYPE yylval; [0-9]+ { yylval = atoi(yytext); và t p chương trình x lý y.tab.c có n i dung như trong ph l c 1. return INTEGER; } Bư c 3.2: Th c hi n l nh biên d ch cho t p Lex: [-+()=/*\n] { return *yytext; } Flex calc.l [ \t] ; /* skip whitespace */ Lúc này Flex s sinh ra m t t p lex.yy.c có n i dung như sau: #define YY_FLEX_MAJOR_VERSION 2 . yyerror("Unknown character"); #define YY_FLEX_MINOR_VERSION 5 %% int yywrap(void) #include { /* cfront 1.2 defines "c_plusplus" instead of return 1; "__cplusplus" */ } #ifdef c_plusplus #ifndef __cplusplus Trong n i dung c a t p tin calc.l có ch a khai báo #include #define __cplusplus "y.tab.h" và ñây là thư vi n ñư c t ñ ng sinh ra t t p calc.y thông #endif #endif qua công c x lý c a Yacc (trong trư ng h p này chúng tôi s d ng … ph n m m Bison). N i dung ñ y ñ c a t p lex.yy.c ñư c trình bày trong ph l c 2. Bư c 3: s d ng các công c ñ sinh mã t ñ ng như sau: Bư c 3.3. S d ng trình biên d ch gcc c a Dev-Cpp ñ th c Bư c 3.1. Th c hi n l nh biên d ch cho t p Yacc: hi n liên k t Lex và Yacc ñ sinh ra t p th c thi bison –d calc.y v i ph n m r ng là .exe:
22 23 gcc y.tab.c lex.yy.c –o calc.exe 1. Đ c và ghi nh n giá tr a, ghi giá tr a vào P. V y P = "a". Lúc này máy tính s s n sinh ra t p th c thi calc.exe và khi th c 2. Đ c toán t "*". Đưa toán t này vào stack S: S = "*" hi n nó thì ta có th nh p vào m t bi u th c và máy s cho k t qu là 3. Đ c d u ngo c m "(", ñưa d u ngo c này vào stack: S = giá tr c a bi u th c ñó. "*(". Ví d 3.1: ñ tính giá tr bi u th c 6+2+4 ta th c hi n như sau: 4. Đ c h ng t b, ñưa b vào P: P= "a b" 5. Đ c toán t "+", ñ t "+" vào stack: S ="*(+" 6. Đ c h ng t "c", ñưa c vào cu i P: P="a b c" 7. Đ c d u ngo c ñóng ")". L n lư t l y các toán t cu i stack ra kh i stack ñ t vào cu i P cho ñ n khi g p d u ngo c m "(" trong stack thì gi i phóng nó: S= "*"; P="a b c +" Ví d 3.2: ñ tính giá tr bi u th c (4*3-8/2)*5+7 ta th c hi n 8. Đ c toán t "-". Cu i stack S có toán t "*" có m c ưu tiên như sau: l n hơn toán t "-", ta l y toán t "*" ra kh i stack, ñ t vào cu i P, ñ t toán t "-" vào stack: S="-"; P=" a b c + * " 9. Đ c h ng t d, ñưa d vào cu i P. P="a b c + * d" 10. Đ c toán t "^", ñưa toán t "^" vào cu i stack: S="-^" 11. Đ c h ng s 5, ñưa 5 vào cu i P: P="a b c + * d 5" 3.4. Đánh giá 12. Đã ñ c h t bi u th c Q, l n lư t l y các ph n t cu i trong Vi c tính giá tr c a m t bi u th c có th th c hi n b ng nhi u stack ñ t vào P cho ñ n h t. P="a b c + * d 5 ^ -". cách khác nhau. Ví d , ta có th s d ng k thu t Kí pháp Ba Lan do Thu t toán chuy n t ký pháp trung t sang ký pháp ti n t ho c nhà Lô-gíc toán Jan Łukasiewicz ñ xu t kho ng năm 1920. h u t r t g n v i cách x lý các phép tính trong máy tính b m tay Vi c tính giá tr m t bi u th c vi t dư i d ng phép toán sau r t (hay máy tính b túi). M t bi u th c ch g m các phép toán hai ngôi thu n ti n như trên, tuy nhiên, theo thói quen thông thư ng, vi c b t kỳ luôn có th ñư c tính b ng máy tính b m tay mà không c n nh p bi u th c ñó vào l i không d , ngư i ta thư ng nh p vào m t dùng d u ngo c. Các phép toán trư c n u có ñ ưu tiên (ưu tiên b i công th c dư i d ng thông thư ng (phép toán gi a) r i dùng chương toán t ho c b i d u ngo c) th p hơn m t phép toán sau ñư c ñ y trình chuy n ñ i nó sang d ng phép toán sau. Chúng ta hãy xét bi u vào m t hàng ch (stack), ch khi nào các phép toán ưu tiên hơn th c trong ví d trên Q=a*(b+c)-d^5 sau ñư c tính xong, các phép toán trư c m i ñư c x lý. Kí hi u bi u th c ghi dư i d ng phép toán sau là P. Trong quá Vi c l p trình theo k thu t này r t ph c t p và t n nhi u th i trình chuy n ñ i ta dùng m t stack S ñ lưu các ph n t trong P chưa gian. Ngoài ra, ngư i s d ng ph i t vi t mã l nh r t nhi u nên t n s d ng ñ n. Khi ñ c t trái sang ph i bi u th c Q là l n lư t có: nhi u th i gian và d sai sót khi xét các trư ng h p.
24 25 Chúng ta so sánh như v y ñ th y r ng vi c ng d ng Lex/Yacc trong K T LU N trư ng h p này, cũng như trong m t s trư ng h p khác, là r t có l i. 3.5. Xây d ng Website gi i thi u v Lex/Yacc Hi n nay, các trư ng ph thông và các trư ng ñ i h c trong 3.5.1. Gi i thi u nư c h u h t ñã ñưa ngôn ng l p trình b c cao như C/C++, Pascal..., Vi c s d ng Lex/Yacc thư ng ñư c gi i thi u trong m t s môn vào gi ng d y. V n ñ ñ t ra là làm th nào ñ gi m chi phí v h c như Chương trình d ch, K thu t l p trình, ...nhưng chưa ñư c trình nghiên c u, ti p c n và tăng hi u qu s d ng các ngôn ng l p trình bày m t cách ñ y ñ nh t v lý thuy t cũng như trong ng d ng. b c cao. Trong quá trình tìm hi u và nghiên c u g p nhi u khó khăn v T ñ ng sinh mã ngu n là m t ý tư ng táo b o và mang l i hi u lý thuy t và nh t là trong tri n khai ng d ng ñ i v i công c này. qu cao trong l p trình. Thay vì l p trình viên ph i tr c ti p vi t mã M c ñích xây d ng Website là nh m gi i thi u ñ y ñ các tính ñ gi i quy t m t bài toán c th nào ñó thì h ch c n ñ c t theo năng c a Lex/Yacc và giúp ti p c n, n m b t ñ y ñ v quy trình v n m t h qui ư c nh t ñ nh (các ngôn ng ñ c t ) và trên cơ s ñó, máy d ng chúng trong môi trư ng Win. tính s t ñ ng s n sinh ra mã ngu n tương ng. M t trong nh ng 3.5.2. Thi t k Website ngôn ng , công c như v y là Lex/Yacc. 3.5.3. Website gi i thi u công c Lex/Yacc Qua quá trình tìm hi u và nghiên c u ng d ng công c Đ tìm hi u v công c Lex/Yacc và quy trình v n d ng nó trên Lex/Yacc ñ phát sinh mã ngu n trong l p trình ng d ng ñã cho trang web ñư c trình bày bao hàm các n i dung t giao di n trang th y k t qu tương ñ i t t. Công c này ñã cho th y nh ng ưu ñi m, ch như sau: s ti n l i, có kh năng ng d ng trong th c ti n Vi t Nam. V i công c này, h c sinh, sinh viên các trư ng có ñi u ki n ti p c n và s d ng có hi u qu các công c l p trình c a mình. Lex/Yacc có ch c năng phát sinh mã ngu n trong lĩnh v c t o các chương trình d ch và sau này ñư c m r ng sang nhi u lĩnh v c khác. Đ cài ñ t m t trình biên d ch, chúng ta ch c n cung c p các ñ t t ng pháp, Lex/Yacc s t ñ ng sinh ra mã ngu n C. Vi c này cho phép ti t ki m r t nhi u th i gian cũng như h n ch l i (bugs) trong mã ngu n. Như v y, sau m t th i gian ti n hành nghiên c u, tác gi ñã cơ b n hoàn thành các n i dung mà ñ cương ñ tài ñã ñ t ra. S n ph m ñ tài này có th ñư c ng d ng t t trong vi c tìm hi u, nghiên c u và tri n khai trong l p trình ng d ng ñ c bi t là trong d y và h c Hình 3.2 Trang ch c a Website gi i thi u v Lex/Yacc b c ph thông và ñ i h c nư c ta.