Khóa luận Tìm hiểu về trình biên dịch và xây dựng ngôn ngữ lập trình Tiếng Việt

h¹m Automat 7 2.1. Kh¸i niÖm v¨n ph¹m 7 2.2. Automat 8 3. Kh¸i qu¸t ch­¬ng tr×nh 9 Ch­¬ng 2: Bé ph©n tÝch tõ vùng 10 1. Vai trß vµ nhiÖm vô 10 2. M« h×nh ho¹t ®éng 10 3. Ph¸t hiÖn vµ xö lý lçi 10 4. BiÓu thøc chÝnh quy 10 5. Ph­¬ng ph¸p x©y dùng DFA( Determinstic Finite Automation) trùc tiÕp tõ biÓu thøc chÝnh quy 11 6. X©y dùng bé ph©n tÝch tõ vùng 12 6.1. X©y dùng vïng ®Öm nhËp 12 6.2. X©y dùng b¶ng danh hiÖu 12 6.3. S¬ ®å dÞch 13 Ch­¬ng 3: Bé ph©n tÝch có ph¸p 15 1. Giíi thiÖu chung vÒ bé ph©n tÝch có ph¸p 15 1.1. Vai trß vµ nhiÖm vô 15 1.2. Ph©n lo¹i v¨n ph¹m 15 1.3. C©y dÉn xuÊt 15 1.4. Kh¸i niÖm vÒ c©u, d¹ng c©u 15 1.5. ThiÕt kÕ v¨n ph¹m 15 1.5.1. V¨n ph¹m ®Ö quy tr¸i trùc tiÕp 15 1.5.2. V¨n ph¹m ®Ö quy tr¸i gi¸n tiÕp 16 1.5.3. V¨n ph¹m yÕu tè tr¸i 17 2. Bé ph©n tÝch có ph¸p ®o¸n nhËn tr­íc kh«ng ®Ö quy 18 2.1. Nguyªn t¾c ph©n tÝch 18 2.2. M« h×nh ho¹t ®éng 18 2.3. X©y dùng b¶ng ph©n tÝch 20 2.3.1. X¸c ®Þnh tËp First cña c¸c kÝ hiÖu ch­a kÕt thóc 20 2.3.2. X¸c ®Þnh tËp Follow cña c¸c kÝ hiÖu ch­a kÕt thóc 20 2.3.3. Gi¶i thuËt x©y dùng b¶ng ph©n tÝch 20 3.4. VÊn ®Ò xö lý lçi 21 3. Bé ph©n tÝch có ph¸p thø tù yÕu 25 3.1. Nguyªn t¾c ph©n tÝch 25 3.2. M« h×nh ho¹t ®éng 25 3.3. X©y dùng b¶ng ph©n tÝch 26 3.3.1. Quan hÖ thø tù yÕu 26 3.3.2. Ph­¬ng ph¸p x¸c ®Þnh quan hÖ thø tù yÕu cho c¸c kýhiÖu v¨n ph¹m 26 3.3.3. Gi¶i thuËt x©y dùng b¶ng ph©n tÝch 27 4. Bé ph©n tÝch có ph¸p LR 31 4.1. Nguyªn t¾c ph©n tÝch 31 4.2. M« h×nh ho¹t ®éng 31 4.3. X©y dùng b¶ng ph©n tÝch 35 Ch­¬ng 4. Bé xö lý ng÷ nghÜa 43 1. Tæng qu¸t 43 2. C¸c cÊu tróc lÖnh 44 2.1. CÊu tróc rÏ nh¸nh 44 2.2. CÊu tróc lÖnh Switch 45 2.3. C¸c cÊu tróc lÆp 46 2.3.1. LÖnh while 46 2.3.2. LÖnh do..while… 46 2.3.3. Khèi lÖnh for 47 Ch­¬ng 5: Giíi thiÖu ng«n ng÷ 48 1. Giíi thiÖu ng«n ng÷ C Sharp (C#) 49 2. Giíi thiÖu ng«n ng÷ lËp tr×nh tiÕng viÖt 49 2.1. TËp ký hiÖu 49 2.2. LuËt danh hiÖu 49 2.3. C¸c to¸n tö 49 2.4. C¸c lÖnh ch­¬ng tr×nh 50 2.4.1. LÖnh khai b¸o biÕn 50 2.4.2. C¸c lÖnh xö lý ®iÒu kiÖn rÏ nh¸nh 50 2.4.3. C¸c c©u lÖnh lÆp 51 KÕt luËn Tµi liÖu tham kh¶o Ch­¬ng 1: Tæng Quan vÒ tr×nh biªn dÞch 1. Giíi ThiÖu VÒ Tr×nh Biªn DÞch: Chóng ta ®· th­êng quen thuéc víi thuËt ng÷ th«ng dÞch vµ biªn dÞch. VÝ dô trong cuéc sèng chóng ta th­êng nghe nh÷ng ng­êi lµm th«ng dÞch viªn tiÕng Anh , tiÕng Ph¸p v..v.. lµ nh÷ng ng­êi nghe tõng c©u trong ng«n ng÷ kh¸c vµ dÞch l¹i tõng c©u cho ng­êi kh¸c. ë ®©y tr×nh biªn dÞch ®ãng vai trß nh­ mét ng­êi th«ng dÞch trong viÖc dÞch mét m· v¨n b¶n ch­¬ng tr×nh nguån cña mét ng«n ng÷ lËp tr×nh ra m· m¸y. C¬ chÕ th«ng dÞch cã thÓ lµ biªn dÞch hoÆc th«ng dÞch tïy theo mçi ng«n ng÷ lËp tr×nh. 1.1. C¬ chÕ Biªn DÞch: M· v¨n b¶n ch­¬ng tr×nh nguån ®­îc dÞch sang mét d¹ng m· trung gian sau ®ã m· trung gian sÏ ®­îc dÞch xuèng m· m¸y vµ m· m¸y sÏ ®­îc thùc thi bëi Control Process Unit (CPU). Tiªu biÓu cho lo¹i nµy lµ c«ng nghÖ Dot Net. Source Code (M· nguån) Front-End (Analysis) Immediate Code (M· trung gian) JIT (Just – In - Time) Back – End (Synthesis) Destination Code 1 (Native Code-m· m¸y) Destination Code 2 (Native Code-m· m¸y) Architecture 1 Architecture 2 M« H×nh Biªn DÞch Cña C«ng NghÖ Dot Net 2. C¬ chÕ Th«ng DÞch: M· v¨n b¶n ch­¬ng tr×nh nguån ®­îc dÞch sang mét d¹ng m· trung gian sau ®ã m· trung gian sÏ ®­îc thùc thi bëi mét phÇn mÒm. Tiªu biÓu cho lo¹i nµy lµ c«ng nghÖ Java. source code (Mã nguồn) Front – End (Analysis) Immediate Code (Mã Trung Gian) Compiler Process By JVM (Java Virtual Machine) M« H×nh Biªn DÞch Cña C«ng NghÖ Java C¸c ch­¬ng tr×nh biªn dÞch cã tiÒn xö lý lín cßn c¸c ch­¬ng tr×nh th«ng dÞch cã tiÒn xö lý nhá h¬n rÊt nhiÒu. C¸c ch­¬ng tr×nh ®­îc biªn dÞch ch¹y nhanh h¬n so víi c¸c ch­¬ng tr×nh ®­îc th«ng dÞch v× toµn bé ch­¬ng tr×nh nµy cã thÓ t­¬ng t¸c trùc tiÕp víi bé vi xö lý(CPU) vµ kh«ng cÇn chia bé nhí vµ tr×nh th«ng dÞch. C¸c ch­¬ng tr×nh th«ng dÞch th× m· lÖnh ch­¬ng tr×nh sÏ ®­îc th«ng dÞch (Interpreter) bëi mét phÇn mÒm nªn chiÕm CPU nhiÒu h¬n vµ ch¹y chËm h¬n. 2. Giíi ThiÖu V¨n Ph¹m Automat: 2.1. Kh¸i niÖm V¨n Ph¹m: V¨n ph¹m lµ mét tËp hîp c¸c ký hiÖu ®­îc s¾p xÕp theo mét tr×nh tù nhÊt ®Þnh cã nh÷ng ý nghÜa nhÊt ®Þnh. Mét v¨n ph¹m th­êng ®­îc bao gåm bëi c¸c tËp ký hiÖu Trong ®ã: + V lµ tËp c¸c ký hiÖu ch­a kÕt thóc (Variable). + T lµ tËp c¸c ký hiÖu kÕt thóc (Terminal). + S lµ ký hiÖu xuÊt ph¸t cña mét v¨n ph¹m (Start). + P lµ tËp luËt sinh (Production). ¸p dông luËt sinh S C©u cña ng«n ng÷. D¹ng cña luËt sinh: VÝ dô: Ta cã tËp luËt sinh: P: S aSb S l ( l lµ mét dÉn xuÊt rçng) hoÆc ta cã thÓ viÕt: S aSbú l (ú - hoÆc) víi: TËp ký hiÖu ch­a kÕt thóc V={S}. TËp ký hiÖu kÕt thóc T={a,b}. tõ S ® aSb => S ® aaSSbb tõ S ® l => S ® aabb => S ® an bn víi n ¹ 0 Nh­ vËy ta cã thÓ nãi lÖnh an bn ®­îc sinh ra bëi v¨n P. 2.2. Automat: Automat lµ m« h×nh trõu t­îng cña m¸y tÝnh sè. C¸c thµnh phÇn: Bé phËn ®äc d÷ liÖu(Data) tõ mét tËp tin vµo (mét chuçi c¸c ký hiÖu vµ kh«ng söa ®æi). ®äc mçi lÇn mét ký hiÖu. Vïng nhí t¹m, l­u ch÷ c¸c ký hiÖu(néi dung cã thÓ thay ®æi ®­îc). §¬n vÞ ®iÒu khiÓn: + Cã tr¹ng th¸i néi t¹i thuéc tËp tr¹ng th¸i h÷u h¹n. +Tr¹ng th¸i thay ®æi theo hµm chuyÓn tr¹ng th¸i. - Tr¹ng th¸i hiÖn t¹i cña ®¬n vÞ ®iÒu khiÓn. - Ký hiÖu hiÖn t¹i. - Th«ng tin hiÖn t¹i trong vïng nhí t¹m. - Sè tr¹ng th¸i <= 2* (Sè biÓu thøc con). - T¹i mét tr¹ng th¸i kh«ng cã nhiÒu c¹nh ra cã cïng nh·n (tøc lµ cã cïng ký hiÖu nhËp). - ChØ cã mét tr¹ng th¸i khëi ®Çu vµ mét tr¹ng th¸i kÕt thóc. ë tr¹ng th¸i kÕt thóc kh«ng cã c¹nh ra. - NÕu cã nhiÒu tr¹ng th¸i khëi ®Çu ta thªm nh÷ng c¹nh truyÒn rçng tíi ®ã sao cho chØ cã mét tr¹ng th¸i khëi ®Çu.T­¬ng tù nÕu cã nhiÒu tr¹ng th¸i kÕt thóc. 3. Kh¸i Qu¸t Ch­¬ng Tr×nh: Ch­¬ng tr×nh ®­îc x©y dùng hÕt søc ®¬n gi¶n, dùa trªn c¬ chÕ tr×nh th«ng dÞch .Ch­¬ng tr×nh sÏ th«ng dÞch ngay trªn m· nguån mµ kh«ng dÞch ra mét ng«n ng÷ trung gian nµo. Compile and Interpreter Soure Code (M· nguån) Tr×nh biªn dÞch ®­îc x©y dùng lµ mét tr×nh th«ng dÞch.Khi ch­¬ng tr×nh thùc thi, toµn bé v¨n b¶n ch­¬ng tr×nh nguån sÏ ®­îc n¹p vµo bé nhí.Tr×nh biªn dÞch ph©n biÖt ch÷ hoa vµ ch÷ th­êng.Trong qu¸ tr×nh biªn dÞch ch­¬ng tr×nh sÏ dõng l¹i ngay khi gÆp lçi. C¸c thµnh phÇn chÝnh cña ch­¬ng tr×nh: Bé ph©n tÝch tõ vùng Bé ph©n tÝch có ph¸p Bé xö lý ng÷ nghÜa C¸c nhiÖm vô c¬ b¶n cña tõng bé phËn: Bé ph©n tÝch tõ vùng N¹p toµn bé v¨n b¶n ch­¬ng tr×nh nguån vµo bé nhí. Ph©n tÝch v¨n b¶n ch­¬ng tr×nh nguån thµnh c¸c token riªng biÖt. B¸o lçi khi gÆp c¸c ký hiÖu kh«ng thuéc tËp ký hiÖu hoÆc c¸c token kh«ng tháa m·n luËt danh hiÖu. Bé ph©n tÝch có ph¸p Dùa vµo tËp luËt sinh cho tr­íc, bé ph©n tÝch có ph¸p sÏ ph©n tÝch c©u lÖnh nhËp xem cã tháa tËp luËt sinh hay kh«ng. B¸o lçi khi c©u lÖnh nhËp kh«ng ®óng có ph¸p (kh«ng tháa có ph¸p cña tËp luËt sinh). Bé xö lý ng÷ nghÜa §¸nh gi¸ biÓu thøc c©u lÖnh nhËp, xö lý ng÷ nghÜa c©u lÖnh nhËp ®óng có ph¸p (cho ta biÕt kÕt qu¶ cuèi cïng cña mét c©u lÖnh nhËp). Ch­¬ng 2: Bé Ph©n TÝch Tõ Vùng 1. Vai trß vµ nhiÖm vô: - Lµ pha ®Çu tiªn cña tr×nh biªn dÞch. Giao tiÕp trùc tiÕp víi v¨n b¶n ch­¬ng tr×nh nguån. - NhiÖm vô chÝnh lµ ph©n tÝch v¨n b¶n nguån thµnh c¸c token. - Bá qua c¸c ký tù kho¶ng tr¾ng, ghi chó. - TËp hîp c¸c th«ng tin tõ v¨n b¶n nguån cÇn cho qu¸ tr×nh tiÕp theo. 2. M« h×nh ho¹t ®éng: V¨n B¶n Ch­¬ng Tr×nh Nguån (Source Code) Bé Ph©n TÝch Tõ Vùng (Lexeme Analysis) Bé Ph©n TÝch Có Ph¸p (Syntax Analysis) B¶ng Danh HiÖu (Identify Table) Yªu cÇu Token kÕ tiÕp §Þnh nghÜa token M« H×nh Ho¹t §éng Cña Bé Ph©n TÝch Tõ Vùng 3. Ph¸t hiÖn vµ xö lý lçi: Cã thÓ sö dông c¸c c¬ chÕ sau: - B¸o sai vµ ng­ng ch­¬ng tr×nh. - B¸o sai vµ t×m vÞ trÝ thÝch hîp ®Ó tiÕp tôc qu¸ tr×nh ph©n tÝch. - B¸o sai thªm söa ®Ó tiÕp tôc qu¸ tr×nh ph©n tÝch. 4. BiÓu thøc chÝnh quy: Lµ tËp tuÇn tù c¸c ®Þnh nghÜa cã d¹ng: di ® ri - di lµ ký hiÖu ®Þnh nghÜa. - ri lµ biÓu thøc chÝnh quy dùa trªn tËp ký hiÖu(S). Mét sè ký hiÖu: - digit + - lÆp l¹i Ýt nhÊt mét lÇn. - digit ? - kh«ng cã hoÆc cã mét lÇn. - [ abc ] - a çb çc - [ a-z ] - a çb …çz 5. Ph­¬ng ph¸p x©y dùng DFA(Determinstic Finite Automation) trùc tiÕp tõ biÓu thøc chÝnh quy: biÓu thøc chÝnh quy ban ®Çu : r. - T¹o biÓu thøc chÝnh quy gia tè: r#. - X©y dùng c©y có ph¸p víi biÓu thøc chÝnh quy gia tè r#. -Nót l¸ a thuéc: S, l, #. -Nót trung gian: |, l, *. - §¸nh sè cho c¸c nót l¸: #, l (thÓ hiÖn cho vÞ trÝ). - X¸c ®Þnh gi¸ trÞ c¸c hµm: Nullable(N) , FirstPosition(N) , LastPosition(N), FollowPosition(p). - Nullable(N) tr¶ vÒ gi¸ trÞ True nÕu biÓu thøc chÝnh quy t­¬ng øng cã nót gèc l¸ N cã thÓ sinh ra chuçi rçng vµ ng­îc l¹i tr¶ vÒ gi¸ trÞ False. - FirstPos(N) lµ tËp c¸c vÞ trÝ cã thÓ so trïng víi ký hiÖu ®Çu cña chuçi ®­îc sinh ra bëi biÓu thøc chÝnh quy t­¬ng øng víi c©y biÓu thøc gèc N. - LastPos(N) lµ tËp c¸c vÞ trÝ cã thÓ so trïng víi ký hiÖu cuèi cña chuçi ®­îc sinh ra bëi biÓu thøc chÝnh quy t­¬ng øng víi c©y biÓu thøc gèc N. - FollowPos(p) lµ tËp c¸c vÞ trÝ cã thÓ so trïng víi ký hiÖu t­ong øng víi vÞ trÝ p trong chuçi. BiÓu thøc chÝnh quy Nullable() FirstPos() LastPos() FollowPos() A True Æ Æ a Î S (a ë vÞ trÝ i) False {i} {i} ç N1 N2 Nullable(N1)or Nullable(N2) FirstPos(N1)+ FirstPos(N2) LastPos(N1)+ LastPos(N2) · N1 N2 Nullable(N1) and Nullable(N2) If(Nullable(N1)) FirstPos(N1)+ FirstPos(N2) Else FirstPos(N1) If(Nullable(N2)) LastPos(N1)+ LastPos(N2) Else LastPos(N2) FollowPos(i)= FirstPos(N2). víi i Î LastPos(N1) * | N True FirstPos(N) LastPos(N) FollowPos(i)= FirstPos(N). víi i Î LastPos(N) - X©y dùng DFA theo gi¶i thuËt: Dstate = FirstPos(root) While (S ÎDstate && unmarked(S)) { marked(S); for (aÎS ) { U=U+ FollowPos(p); p ÎS,p ® a Dstate = Dstate + {U}; Dstate [S] [a] = U; } } 6. X©y dùng bé ph©n tÝch tõ vùng: 6.1. X©y dùng vïng ®Öm nhËp: Vïng ®Öm nhËp lµ mét cÊu tróc d÷ liÖu lµ n¬i ®Ó n¹p v¨n b¶n ch­¬ng tr×nh nguån vµo bé nhí, ta cã thÓ hiÖn thùc Vïng §Öm NhËp nh­ sau: - sö dông biÕn beginning trá ®Õn ®Çu chuçi ®ang ph©n tÝch. - khëi t¹o biÕn forward = beginning. - Sau mçi lÇn ®äc mét ký hiÖu t¨ng forward lªn 1. forward = forward +1; - kiÓm tra ®iÒu kiÖn ®¹t tíi danh giíi bé ®Öm: if (forward = end_of_left_buffer) { load_to_right_buffer; forward = forward +1; } else if (forward = end_of_right_buffer) { load_to_left_buffer; forward = head_left_buffer; } 6.2. X©y dùng b¶ng danh hiÖu: B¶ng Danh HiÖu (Identify Table) lµ mét cÊu tróc d÷ liÖu l­u tr÷ th«ng tin liªn quan ®Õn danh hiÖu nh­ néi dung cña danh hiÖu, lo¹i danh hiÖu (sè hay chuçi), kiÓu cña danh hiÖu( sè nguyªn hay sè thùc) v..v.. B¶ng danh hiÖu ph¶i ®­îc tæ chøc sao cho thao t¸c dß t×m cã hiÖu qu¶ nhanh nhÊt c¶ vÒ mÆtthêi gian vµ mÆt xö lý.TiÕt kiÖm vïng nhí,dÔ më réng khi cÇn thiÕt. Ta cã thÓ tæ chøc B¶ng Danh HiÖu theo b¶ng TuyÕn TÝnh hoÆc b¶ng B¨m hay mét d¹ng cÊu tróc d÷ liÖu kh¸c hiÖu qu¶ h¬n. C¸c thao t¸c trªn B¶ng Danh HiÖu: - Dß t×m mét danh hiÖu (position lookup) tr¶ vÒ vÞ trÝ cña danh hiÖu ®ã trong B¶ng Danh HiÖu nÕu t×m thÊy ng­îc l¹i nÕu kh«ng t×m thÊy tr¶ vÒ mét vÞ trÝ bÊt hîp lÖ. - Thªm danh hiÖu vµo B¶ng Danh HiÖu, më réng B¶ng Danh HiÖu nÕu ®Çy phÇn tö. - C¸c thao t¸c liªn quan ®Õn vÊn ®Ò tÇm vùc : Sau khi x©y dùng ®­îc b¶ng danh hiÖu th× c«ng viÖc ®Çu tiªn lµ ph¶i khëi t¹o b¶ng danh hiÖu. LÊp ®Çy c¸c tõ khãa theo ng«n ng÷ ®Þnh tr­íc øng víi mçi lo¹i tõ khãa øng víi mét lo¹i token. VÝ dô “if” t­¬ng øng víi lo¹i token “IF” víi mçi danh hiÖu th× lo¹i token t­¬ng øng lµ “ID”. 6.3. S¬ ®å dÞch ( Translation Diagram): i Tr¹ng th¸i b¾t ®Çu. i Tr¹ng th¸i kÕt thóc ( kh«ng cã c¹nh ra). - S¬ ®å chuyÓn tr¹ng th¸i cho biÕt c¸ch thøc biÕn ®æi t­¬ng øng víi ký hiÖu nhËp. - X©y dùng dùa trªn ®Æc t¶ tõ vùng (®Þnh nghÜa biÓu thøc chÝnh quy). VÝ dô: Ta ®Þnh nghÜa c¸c to¸n tö logic nh­ sau: Relation operator Comment > Greater than >= Greater or Equal < Lesser than <= Lesser á Equal == Equal != Not Equal ! Not = Assingment C¸c ký tù ch÷: Letter ® [a-z] [A-Z]. C¸c ký tù sè: Digit ® [0-9]. C¸c danh hiÖu: Identify ® Letter (letter êDigit)*. i 3 i 5 i 2 i 6 i 8 i 9 7 4 1 0 < = other > = = other = other Return (“<=”,“LE”) Return (“<”, “LT”) Return (“>=”, “GE”) Return(“<”, “GT”) Return (“= =”,“EQ”) Return(“=”, “AS”) i 14 13 i 12 i 11 10 ! other = Return (“!”, “NOT”) Return (“!=”, “NE”) Return (id, “ID”) other letter Letter |Digit Digit Translation Diagram Ch­¬ng 3: Bé Ph©n TÝch Có Ph¸p Trong ch­¬ng nµy giíi thiÖu mét sè bé ph©n tÝch có ph¸p qua ®ã ta cã thÓ nhËn ra ®iÓm m¹nh vµ ®iÓm yÕu cña tõng ph­¬ng ph¸p, vµ giíi thiÖu ph­¬ng ph¸p x©y dùng tõng bé ph©n tÝch có ph¸p. Bé ph©n tÝch có ph¸p ®o¸n nhËn tr­íc kh«ng ®Ö quy. Bé ph©n tÝch có ph¸p thø tù yÕu vµ bé ph©n tÝch có ph¸p LR (Bé ph©n tÝch nµy ®­îc sö dông ®Ó x©y dùng ch­¬ng tr×nh). 1. Giíi ThiÖu chung vÒ bé ph©n tÝch có ph¸p 1.1. Vai trß vµ nhiÖm vô: Lµ pha thø hai giao tiÕp víi bé ph©n tÝch tõ vùng. NhËn chuçi token, kiÓm chøng c¸c token ®­îc s¾p xÕp theo ®óng trËt tù có ph¸p ®· ®Þnh. KÕt hîp víi qu¸ tr×nh xö lý ng÷ nghÜa. B¸o lçi khi sai. KÕt qu¶ qu¸ tr×nh ph©n tÝch lµ c©y có ph¸p. 1.2. Ph©n lo¹i V¨n Ph¹m: V¨n ph¹n tuyÕn tÝnh: Lµ v¨n ph¹m mµ luËt sinh cã d¹ng: A ® x B hay A ® Bx hay A ® x V¨n ph¹m phi ng÷ c¶nh: Lµ v¨n ph¹m mµ luËt sinh cã d¹ng: A ® W víi W Î (V + T) 1.3. C©y dÉn xuÊt: - Nót gèc cã nh·n trïng víi ký hiÖu xuÊt ph¸t cña v¨n ph¹m. - Nót l¸ cã nh·n trïng víi ký hiÖu Î T + l ( l ký hiÖu rçng) - Nót trung gian cã nh·n trïng víi ký hiÖu thuéc V. - NÕu A ® x1x2…xn Î P th× nót cã nh·n A sÏ cã c¸c nót con lÇn l­ît lµ x1, x2 … n ( tõ tr¸i sang ph¶i ). 1.4. Kh¸i niÖm vÒ c©u, d¹ng c©u: - C©u: lµ chuçi c¸c ký hiÖu kÕt thóc (ÎT ). - D¹ng c©u: lµ chuçi c¸c ký hiÖu kÕt thóc vµ ch­a kÕt thóc (Î T + V). 1.5. ThiÕt kÕ v¨n ph¹m: Có ph¸p cña c¸c ng«n ng÷ lËp tr×nh cã thÓ ®­îc ®Æc t¶ bëi c¸c v¨n ph¹m phi ng÷ c¶nh. 1.5.1. V¨n ph¹m ®Ö quy tr¸i trùc tiÕp: V¨n ph¹m ®Ö quy tr¸i trùc tiÕp lµ v¨n ph¹m cã sù trïng l¾p gi÷a gi¸ trÞ vÕ tr¸i cña c©u dÉn xuÊt víi gi¸ trÞ ®Çu tiªn bªn ph¶i cña c©u dÉn xuÊt. VÝ dô: P: A ®AC | Aad | bd | l. (cã sù trïng l¾p gi¸ trÞ A) gi¶i thuËt khö ®Ö quy tr¸i trùc tiÕp: for (ÎP) { if (p = Aa1 | Aa2 | … | Aan | b1 | b2 | … | bm) then { replace p by A®b1A’ | b2A’ | … | bmA’ A’ ® a1A’ | a2A’ | … | anA’ l } } vÝ dô: ta cã tËp luËt sinh P: A ® AC | Aad | bd | l ta khö ®Ö quy tr¸i trùc tiÕp nh­ sau: P: A ® bdA’ | lA’ A’ ® CA’ | adA’ | l 1.5.2. V¨n ph¹m ®Ö quy tr¸i gi¸n tiÕp: V¨n ph¹m ®Ö quy tr¸i gi¸n tiÕp lµ v¨n ph¹m cã c©u dÉn xuÊt mµ vÕ tr¸i cña c©u dÉn xuÊt trïng víi gi¸ trÞ ®Çu tiªn cña vÕ ph¶i c©u dÉn xuÊt qua nhiÒu c©u dÉn xuÊt. VÝ dô: P: S ®Aa | b (1) A ® AC | Sd | l (2) (cã sù trïng l¾p gi¸ trÞ S). Gi¶i thuËt khö ®Ö quy tr¸i gi¸n tiÕp: - S¾p xÕp c¸c ký hiÖu ch­a kÕt thóc theo thø tù A1, A2 … An for (i = 1 to n) { for (j = 1 to i – 1) { if ( p: Ai ® Ajb) { Ai ® C1b | C2b | … | Cnb víi Aj ® C1 | C2 | … | Cn khö ®Ö quy tr¸i trùc tiÕp. } } } vÝ dô: Khö ®Ö quy tr¸i gi¸n tiÕp P: S ® Aa | b (1) A ® AC | Sd | l (2) Thay S ® Aa | b vµo (2) ta cã: S ® Aa | b A ®AC | Aad | bd | l Ta tiÕp tôc khö ®Ö quy tr¸i trùc tiÕp cña A ® AC | Aad | bd | l A ®bdA’ | lA’ A’ ® CA’ | adA’ | l S ® Aa | b (1) => P: A ®bdA’ | lA’ (2) A’® CA’ | adA’ | l (3) 1.5.3. V¨n ph¹m yÕu tè tr¸i: V¨n ph¹m yÕu tè tr¸i lµ v¨n ph¹m cã c©u dÉn xuÊt mµ cã sù trïng l¾p gi÷a vÕ tr¸i cña c©u dÉn xuÊt víi gi¸ trÞ cuèi cïng cña vÕ ph¶i c©u dÉn xuÊt. VÝ dô: P: D ® L : T ; D | L : T; (cã sù trïng l¾p D) T ® i | f L ® id , L | id (cã sù trïng l¾p L) - ThuËt to¸n khö trïng l¾p yÕu tè tr¸i nh­ sau: Thay A ® aB1 | aB2 | … | aBn bëi A ® aA’ A’ ® B1 | B2 | … | Bn ( ký hiÖu ®Çu cña B1, B2, … , Bn kh¸c nhau ). - Ta khö trïng l¾p yÕu tè tr¸i nh­ sau: P: D ® L : T ; D’ ( nhãmL:T; lµm thõa sè chung ) D’ ® D | l T ® i | f L ® id L’ ( nhãm id lµm thõa sè chung ) L’ ® , L | l 2. Bé Ph©n TÝch Có Ph¸p §o¸n NhËn Tr­íc Kh«ng §Ö Quy 2.1. Nguyªn t¾c ph©n tÝch: - Yªu cÇu v¨n ph¹m kh«ng ®Ö quy tr¸i trùc tiÕp hay gi¸n tiÕp. NÕu v¨n ph¹m ®Ö quy tr¸i th× khö ®Ö quy tr¸i. Yªu cÇu v¨n ph¹m kh«ng cã yÕu tè tr¸i. NÕu v¨n ph¹m cã yÕu tè tr¸i th× khö yÕu tè tr¸i. 2.2. M« h×nh ho¹t ®éng: Vïng §Öm NhËp Bé §iÒu KhiÓn Ch­¬ng Tr×nh Ph©n TÝch Có Ph¸p §o¸n NhËn Tr­íc XuÊt Stack B¶ng Ph©n TÝch M M« H×nh Ho¹t §éng Cña Bé Ph©n TÝch Có Ph¸p §o¸n NhËn Tr­íc Kh«ng §Ö Quy - Vïng §Öm NhËp: chøa v¨n b¶n ch­¬ng tr×nh cÇn ph©n tÝch. KÕt thóc vïng ®Öm nhËp chøa ký hiÖu $ ( $ ÎT ), ký hiÖu kÕt thóc. - Stack chøa d¹ng c©u cña v¨n ph¹m trong qu¸ tr×nh ph©n tÝch. §¸y Stack chøa ký hiÖu $. - B¶ng ph©n tÝch M lµ mét b¶ng hai chiÒu. M [A, a] = LuËt sinh A ®B ( a lµ ký hiÖu b¾t ®Çu cña c©u ®­îc dÉn xuÊt tõ B. B ® a...) M [A, a] = Æ ( lçi sai ). A Î V , a Î T. - Bé §iÒu khiÓn: T¹i mçi thêi ®iÓm bé ®iÒu khiÓn dùa trªn ký hiÖu ë ®Ønh Stack x vµ ký hiÖu nhËp a ®Ó quyÕt ®Þnh hµnh vi t­¬ng øng. NÕu x = a = $ B¸o thµnh c«ng (®o¸n nhËn ®­îc chuçi nhËp, chuçi nhËp ®óng có ph¸p víi v¨n ph¹m). kÕt thóc qu¸ tr×nh ph©n tÝch. NÕu x = a ¹ $. Lo¹i x khái Stack. §äc ký hiÖu nhËp kÕ tiÕp. NÕu x Î V (x lµ ký hiÖu ch­a kÕt thóc). Tra trong b¶ng M. nÕu: M [x, a] = x ®y1y2…yn lo¹i x khái Stack lÇn l­ît ®­a vµo Stack c¸c gi¸ trÞ yn, yn-1 … y1. nÕu: M [A, a] = Æ b¸o lçi sai. Gi¶i thuËt xö lý bé ®iÒu khiÓn: - n¹p chuçi nhËp kÕt thóc b»ng $ vµo ®Öm nhËp. - push ($); - push (S); // S lµ ký hiÖu xuÊt ph¸t cña v¨n ph¹m. - top_of_stack (x); - a = GetNextToken ( ); - while ( x ¹$ && a ¹$ ) { if ( x Î T && x = = a ) { pop (x); a = GetNextToken ( ); } else if ( x Î V ) { if ( M [x, a] = = x ® y1y2 … yn ) { pop (x); for ( i=n to 1 ) { push ( yi ); } } else { error ( ); } } else { error ( ); } } output (“success”) // ph©n tÝch thµnh c«ng. - kÕt xuÊt cña qu¸ tr×nh ph©n tÝch lµ c©y có ph¸p. 2.3. X©y dùng b¶ng ph©n tÝch M: Bé ph©n tÝch có ph¸p ®o¸n nhËn tr­íc kh«ng ®Ö quy cho c¸c v¨n ph¹m kh¸c nhau chØ kh¸c nhau ë b¶ng ph©n tÝch. 2.3.1. X¸c ®Þnh tËp First cña c¸c ký hiÖu ch­a kÕt thóc Gi¶i thuËt x¸c ®Þnh tËp First: i. First (A) = { A } nÕu A ÎT ii. nÕu A ®l th× First (A) = First (A) + { l} nÕu A ®y1y2 … yn th× First (A) = First (A) + ( First (y1) – { l } ); i = 1; while ( i < n && l € First (yi)) { First (A) = First (A) + ( First (yi+1) – { l } ); i ++; } 2.3.2. X¸c ®Þnh tËp Follow cña c¸c ký hiÖu ch­a kÕt thóc Gi¶i thuËt x¸c ®Þnh tËp Follow: i. Follow (S) = { $ } nÕu S lµ ký hiÖu xuÊt ph¸t cña v¨n ph¹m. ii. nÕu X ® aAB th× Follow (A) = Follow (A) +(First(B) - {l }) iii. nÕu X ® aA hay (X ® aAB vµ l Î First(B)) th× Follow (A) = Follow (A) + Follow(X) 2.3.3. Gi¶i thuËt x©y dùng b¶ng M: for ( A € V , a € T) { M [A, a] = {}; } for ( p = A ® B € P) { for ( a ÎT && a Î First(B)) M [A, a] = { A ®B } if (l Î First (B)) { for ( b Î (T + { $ }) && b Î Follow (A)) { M [A, b] = { A ® B}; } } } 2.3.4. VÊn ®Ò xö lý lçi: Trong qu¸ tr×nh ph©n tÝch nÕu gÆp lçi th× bá qua c¸c ký hiÖu kÕ tiÕp cho ®Õn khi gÆp ký hiÖu thuéc tËp ký hiÖu ®ång bé th× tiÕp tôc qu¸ tr×nh ph©n tÝch. VÝ dô: X©y dùng bé ph©n tÝch có ph¸p cho v¨n ph¹m sau: P: E ® E + T (1) E ® T (2) T ® T * F (3) T ® F (4) F ® id (5) F ® (E) (6) Ta thÊy v¨n ph¹m ®Ö quy tr¸i trùc tiÕp ë c©u dÉn xuÊt (1) (3). khö ®Ö quy tr¸i trùc tiÕp ta ®­îc: P: E ® TE’ E’ ® +TE’ E ® l T ® FT’ T’ ® *FT’ T’ ® l F ® id F ® (E) ¸p dông gi¶i thuËt x¸c ®Þnh tËp First cho c¸c ký hiÖu ch­a kÕt thóc ta cã: x Î V First ( x ) F Id, ( T’ *, l T id, ( E’ +, l E id, ( ¸p dông gi¶i thuËt x¸c ®Þnh tËp Follow cho c¸c ký hiÖu ch­a kÕt thóc ta cã: x Î V Follow ( x ) E ), $ E’ ), $ T +,), $ T’ +,), $ F +,*,), $ ¸p dông gi¶i thuËt x©y dùng b¶ng ph©n tÝch M ta cã: aÎT xÎV id + * ( ) $ E E ®TE’ E®TE’ E’ E’®+TE’ E’® l E’ ® l T T® FT’ E®TE T’ T’ ® l T ® *FT’ T’® l T’ ® l F F ® id F® (E) Sau khi x©y dùng ®­îc B¶ng Ph©n TÝch ta tiÕn hµnh ph©n tÝch c©u lÖnh nhËp sau: W = id * ( id + id ) xem c©u lÖnh nhËp nµy cã thuéc v¨n ph¹m P hay kh«ng nghÜa lµ cã ®óng víi có ph¸p v¨n ph¹m hay kh«ng. - N¹p chuçi cÇn ph©n tÝch vµo vïng ®Öm nhËp. - Khëi t¹o Stack: + Push ( $ ); (®¸y Stack lu«n chøa gi¸ trÞ $) + Push ( E ); (E lµ ký hiÖu xuÊt ph¸t cña v¨n ph¹m) Stack Vïng §Öm NhËp (Buffer) DÉn XuÊt $E Id * ( id + id ) $ E ® TE’ $E’T Id * ( id + id ) $ T ® lFT’ $E’T’F Id * ( id + id ) $ F ® id $E’T’id Id * ( id + id ) $ Reduce $E’T’ * ( id + id ) $ T’® FT’ $E’T’F* * ( id + id ) $ Reduce $E’T’F ( id + id ) $ F® (E) $E’T’)E( ( id + id ) $ Reduce $E’T’)E id + id ) $ E ® TE’ $E’T’)E’T id + id ) $ T ® FT’ $E’T’)E’T’F id + id ) $ F ® id $E’T’)E’T’id id + id ) $ Reduce $E’T’)E’T’ + id ) $ T’ ® l $E’T’)E’ + id ) $ E’®+TE’ $E’T’)E’T+ + id ) $ Reduce $E’T’)E’T id ) $ T ® FT’ $E’T’)E’T’F id ) $ F ® id $E’T’)E’T’id id ) $ Reduce $E’T’)E’T’ ) $ T’ ® l $E’T’)E’ ) $ E’ ® l $E’T’) ) $ Reduce $E’T’ $ T’ ® l $E’ $ E’ ® l $ $ Success Tõ b¶ng ph©n tÝch ta x©y dùng ®­îc c©y có ph¸p nh­ sau: E T E’ F T’ l id * F T’ ( E ) l T E’ F T’ + T E’ id l F T’ l id l S¬ §å C©y Có Ph¸p 3. Bé Ph©n TÝch Có Ph¸p Thø Tù YÕu 3.1. Nguyªn t¾c ph©n tÝch: §©y lµ d¹ng ph©n tÝch có ph¸p tõ d­íi lªn. XuÊt ph¸t tõ c©u nhËp, ¸p dông lÇn l­ît c¸c luËt sinh ®Ó thu gi¶m c©u nhËp vÒ ký hiÖu xuÊt ph¸t cña v¨n ph¹m cã nghÜa lµ qu¸ tr×nh ph©n tÝch b¾t ®Çu tõ c¸c nót l¸ cña c©y dÉn xuÊt ®i dÇn lªn ®Õn nót gèc (tõ d­íi lªn). Qu¸ tr×nh thu gi¶m ®­îc thùc hiÖn theo c¸ch thøc: - QuÐt chuçi nhËp tõ tr¸i sang ph¶i. X¸c ®Þnh chuçi con trïng víi vÕ ph¶i cña tËp mét luËt sinh. - Thay chuçi con t×m ®­îc bëi ký hiÖu vÕ tr¸i cña luËt sinh t­¬ng øng. 3.2. M« H×nh Ho¹t §éng: TËp luËt sinh §¬n vÞ ®iÒu khiÓn Bé Ph©n TÝch Có Ph¸p Thø Tù YÕu. B¶ng Ph©n TÝch Stack tr¹ng th¸i Stack nhËp (®Öm nhËp) XuÊt M« H×nh Bé Ph©n TÝch Có Ph¸p Thø Tù YÕu - Stack nhËp (vïng ®Öm nhËp): chøa chuçi nhËp, ký hiÖu tËn cïng lµ $. - Stack tr¹ng th¸i: chøa c¸c ký hiÖu v¨n ph¹m ®¸y stack lµ ký hiÖu $ (khëi ®Êu stack tr¹ng th¸i lµ rçng chØ chøa ký hiÖu $). - TËp luËt sinh: chøa c¸c luËt sinh cña v¨n ph¹m. - B¶ng ph©n tÝch: cho biÕt hµnh vi t­¬ng øng khi biÕt ký hiÖu trªn ®Ønh stack tr¹ng th¸i vµ ký hiÖu trªn ®Ønh stack nhËp: M [A, a] = action Action cã thÓ lµ Shift hoÆc Reduce. A: lµ ký hiÖu trªn ®Ønh Stack tr¹ng th¸i. A Î V + T + { $ } a: lµ ký hiÖu nhËp kÕ tiÕp. - §¬n vÞ ®iÒu khiÓn: tuú thuéc ký hiÖu trªn ®Ønh stack tr¹ng th¸i A vµ ký hiÖu trªn ®Ønh stack nhËp a mµ ®¬n vÞ ®iÒu khiÓn quyÕt ®Þnh hµnh vi Shift hay Reduce dùa theo b¶ng ph©n tÝch M M [A, a] = Shift : §Èy a sang stack tr¹ng th¸i. Cã nghÜa lµ lÊy a khái stack nhËp ®­a a sang stack tr¹ng th¸i. M [A, a] = Reduce: X¸c ®Þnh luËt sinh cã vÕ ph¶i trïng d¹ng c©u ë phÝa ®Ønhu Stack tr¹ng th¸i. Thay d¹ng c©u t­¬ng øng bëi ký hiÖu vÕ tr¸i cña luËt sinh. M [A, a] = {} (rçng) B¸o lçi sai. Hµnh vi Shift gióp hoµn chØnh vÕ ph¶i cña mét luËt sinh. Hµnh vi Reduce , khi mét luËt sinh ®­îc hoµn chØnh th× thay vÕ ph¶i bëi vÕ tr¸i. NÕu ®¹t ®Õn ®iÒu kiÖn stack tr¹ng th¸i chØ cã mét ký hiÖu lµ ký hiÖu xuÊt ph¸t cña v¨n ph¹m vµ ký hiÖu ®¸y stack nhËp lµ $ th× qu¸ tr×nh ph©n tÝch thµnh c«ng cã nghÜa lµ chuçi nhËp ®óng víi v¨n ph¹m cña ng«n ng÷ hay c©u lÖnh nhËp viÕt ®óng có ph¸p. 3.3. X©y dùng b¶ng ph©n tÝch : 3.3.1. Quan hÖ thø tù yÕu: Ta nãi hai ký hiÖu X, Y cã quan hÖ thø tù yÕu trong c¸c tr­êng hîp sau ®©y: - X = Y nÕu Z ® aXYb. - X < Y nÕu Z ® aXAb vµ Y Î First(A) - X > Y nÕu Z ® aABb vµ A ® CX vµ B ® Yb gi¶ sö X lµ ký hiÖu trªn ®Ønh stack tr¹ng th¸i Y lµ ký hiÖu trªn ®Ønh stack nhËp: - X = Y® cã nghÜa lµ cã tån t¹i luËt sinh cã vÕ ph¶i lµ aXYb vµ thùc hiÖn hµnh vi Shift Y sang stack tr¹ng th¸i ®Ó hoµn chØnh dÇn vÕ ph¶i cña luËt sinh. - X < Y ® cã nghÜa lµ cã tån t¹i luËt sinh cã vÕ ph¶i lµ aXAb vµ thùc hiÖn hµnh vi Shift Y sang stack tr¹ng th¸i ®Ó hoµn chØnh dÇn vÕ ph¶i cña luËt sinh. ( X ≤ Y thùc hiÖn hµnh vi Shift). - X > Y ® cã nghÜa lµ cã tån t¹i luËt sinh cã vÕ ph¶i lµ aABb vµ lóc nµy phÝa ®Ønh stack tr¹ng th¸i ®· cã ®Çy ®ñ vÕ ph¶i cña mét luËt sinh cã ký hiÖu vÕ tr¸i lµ A vµ lóc nµy thùc hiÖn hµnh vi thu gi¶m ( Reduce ) vÒ A. 3.3.2. Ph­¬ng ph¸p x¸c ®Þnh quan hÖ thø tù yÕu ¸p dông c¸c luËt sau ®©y cho ®Õn khi x¸c ®Þnh hÕt c¸c quan hÖ gi÷a c¸c ký hiÖu: a1: a1.a: $ ≤ S (S lµ ký hiÖu xuÊt ph¸t cña v¨n ph¹m). a1.b: X ≤ Y nÕu Z ® aXYb. a2: => X ≤ Z1 X ≤ Y X ® Z1Z2…Zn a3: a3.a: S > $ ( S lµ ký hiÖu xuÊt ph¸t cña v¨n ph¹m). a3.b: => Zn > Y X ≤ Y X ® Z1Z2…Zn a4 => X > Z1 a4.a: X > Y Y ® Z1Z2…Zn a4.b: => Zn > Y X > Y X ® Z1Z2…Zn Gi¶i thuËt x©y dùng B¶ng Ph©n TÝch M: khëi t¹o b¶ng hai chiÒu M lµ rçng. - for (A Î V + T + { $} ) { for ( a Î T + {$} ) { if ( A ≤ a ) { M [A, a] = M [A, a] + {$} ; } if ( A > a ) { M [A, a] = M [A, a] + {Reduce} ; } } } ViÖc x¸c ®Þnh d¹ng c©u phÝa ®Ønh stack trïng víi vÕ ph¶i cña mét luËt sinh (trong hµnh vi thu gi¶m) th­êng rÊt phøc t¹p. tr­êng hîp cã nhiÒu luËt sinh cã cïng vÕ ph¶i th× kh«ng x¸c ®Þnh ®­îc luËt sinh sö dông (trong hµnh vi thu gi¶m). tr­êng hîp phÇn tö trong B¶ng ph©n tÝch chøa nhiÒu hµnh vi th× kh«ng x¸c ®Þnh ®­îc nªn chän hµnh vi nµo. VÝ dô: X©y dùng bé ph©n tÝch có ph¸p cho v¨n ph¹m sau: P: A ® id = E E ® E + T E ® T T ® T * F T ® F F ® id F ® (E) ¸p dông ph­¬ng ph¸p x¸c ®Þnh quan hÖ thø tù yÕu ta cã: a1.a: $ ≤ A a1.b: id ≤ = = ≤ E E ≤ + + ≤ T T ≤ * * ≤ F ( ≤ E E ≤ ) a2: $ ≤ id. = ≤ T , = ≤ F , = ≤ id , = ≤ ( + ≤F , + ≤ id , + ≤ ( * ≤ id , * ≤ ( ( ≤ T , ( ≤ F , ( ≤ id , ( ≤ ( a3a: A > $ - a3b: T > + F > * T > ) a4b: E > $ , T > $ , F > $ , id > $ , ) > $ F > + , id > + , ) > + id > * , ) > * F > ) , id > ) , ) > ) ¸p dông gi¶i thuËt x©y dùng b¶ng ph©n tÝch ta cã B¶ng Ph©n TÝch sau: StacknhËp stack tr¹ng th¸i id = + * ( ) $ A Success E Shift Shift Reduce T Reduce Shift Reduce Reduce F Reduce Reduce Reduce Reduce Id Shift Reduce Reduce Reduce Reduce = Shift Shift + Shift Shift * Shift Shift ( Shift Shift ) Reduce Reduce Reduce Reduce $ Shift sö dông b¶ng ph©n tÝch ta ph©n tÝch chuçi nhËp sau: id = id * (id + id) Khëi t¹o stack tr¹ng th¸i víi ký hiÖu ®Çu tiªn t¹i phÇn tö 0 lµ $. N¹p chuçi nhËp vµo stack nhËp víi ký hiÖu kÕt thóc lµ $. Stack Tr¹ng Th¸i Stack NhËp Hµnh Vi (action) DÉn XuÊt $ id = id * ( id + id ) $ Shift $id = id * ( id + id ) $ Shift $id= id * ( id + id ) $ Shift $id=id * ( id + id ) $ Reduce F ® id $id=F * ( id + id ) $ Reduce T ®F $id=T * ( id + id ) $ Shift $id=T* ( id + id ) $ Shift $id=T* ( id + id ) $ Shift $id=T* (id + id ) $ Reduce F ® id $id=T* (F + id ) $ Reduce T ® F $id=T* (T + id ) $ Reduce E ® T $id=T* (E + id ) $ Shift $id=T* (E+ id ) $ Shift $id=T* (E+id ) $ Reduce F ® id $id=T* (E+F ) $ Reduce T ® F $id=T* (E+T ) $ Reduce E ® E + T $id=T* (E ) $ Shift $id=T* (E) $ Reduce F ® (E) $id=T*F $ Reduce T ® T * F $id=T $ Reduce E ® T $id=E $ Reduce A ® id = E $A $ Success Tõ B¶ng Ph©n TÝch Ta cã c©y có ph¸p nh­ sau: A = E T T * F ( E ) E F + T id F T id id F id S¬ §å C©y Có Ph¸p 4. Bé Ph©n TÝch Có Ph¸p LR Hai ch­¬ng tr­íc chóng ta ®· t×m hiÓu qu¸ tr×nh xö lý cña hai bé ph©n tÝch có ph¸p lµ bé ph©n tÝch có ph¸p ®o¸n nhËn tr­íc kh«ng ®Ö quy vµ bé ph©n tÝch có ph¸p thø tù yÕu vµ mçi bé ®Òu cã nh÷ng ®iÓm yÕu vÝ dô nh­ bé ph©n tÝch có ph¸p ®o¸n nhËn tr­íc kh«ng ®Ö quy chØ thÝch hîp víi lo¹i v¨n ph¹m nhá, Ýt ®Ö quy, nÕu ®Ö quy nhiÒu lÇn th× ta ph¶i khö ®Ö quy rÊt phøc t¹p. ë bé ph©n tÝch có ph¸p thø tù yÕu th× nÕu trong mét « ph©n tÝch chøa nhiÒu hµnh ®éng th× ta kh«ng biÕt nªn chän hµnh ®éng nµo… Trong ch­¬ng nµy chóng ta sÏ t×m hiÓu mét bé ph©n tÝch hiÖu qu¶ h¬n vµ ®©y còng lµ bé ph©n tÝch có ph¸p ®­îc sö dông ®Ó x©y dùng ch­¬ng tr×nh. 4.1. Nguyªn t¾c ph©n tÝch: T­¬ng tù Bé Ph©n TÝch Có Ph¸p Thø Tù YÕu. §©y lµ d¹ng ph©n tÝch có ph¸p tõ d­íi lªn. XuÊt ph¸t tõ c©u nhËp, ¸p dông lÇn l­ît c¸c luËt sinh ®Ó thu gi¶m c©u nhËp vÒ ký hiÖu xuÊt ph¸t cña v¨n ph¹m cã nghÜa lµ qu¸ tr×nh ph©n tÝch b¾t ®Çu tõ c¸c nót l¸ cña c©y dÉn xuÊt ®i dÇn lªn ®Õn nót gèc (tõ d­íi lªn). Qu¸ tr×nh thu gi¶m ®­îc thùc hiÖn theo c¸ch thøc: - QuÐt chuçi nhËp tõ tr¸i sang ph¶i. X¸c ®Þnh chuçi con trïng víi vÕ ph¶i cña tËp mét luËt sinh. - Thay chuçi con t×m ®­îc bëi ký hiÖu vÕ tr¸i cña luËt sinh t­¬ng øng. 4.2. M« H×nh Ho¹t §éng : Stack nhËp(®Öm nhËp) Stack tr¹ng th¸i TËp LuËt Sinh §¬n vÞ ®iÒu khiÓn Bé Ph©n TÝch Có Ph¸p LR XuÊt B¶ng Ph©n TÝch M« H×nh Bé Ph©n TÝch Có Ph¸p LR - Stack nhËp (vïng ®Öm nhËp): Chøa chuçi nhËp, ký hiÖu tËn cïng lµ $. - Stack tr¹ng th¸i: Chøa c¸c ký hiÖu v¨n ph¹m vµ ký hiÖu tr¹ng th¸i. Stack tr¹ng th¸i chøa ký hiÖu khëi ®Çu lµ m· tr¹ng th¸i 0. S0 X1 S1 X2 S2 … Xn Sn Tr¹ng th¸i khëi ®Çu ( 0 ). §Ønh cña stack (Top of stack). So - Tr¹ng th¸i khëi ®Çu ( zero ). Si - Ký hiÖu tr¹ng th¸i. Xi - Ký hiÖu v¨n ph¹m. ë ®Ønh stack lu«n lu«n lµ ký hiÖu tr¹ng th¸i. TËp luËt sinh: Chøa c¸c luËt sinh cña v¨n ph¹m. B¶ng ph©n tÝch: B¶ng ph©n tÝch gåm hai thµnh phÇn Action vµ Goto. Action cho biÕt hµnh vi t­¬ng øng khi biÕt tr¹ng th¸i trªn ®Ønh stack tr¹ng th¸i vµ ký hiÖu trªn ®Ønh stack nhËp: Action [S, a] = action S lµ ký hiÖu tr¹ng th¸i. a lµ ký hiÖu nhËp. action cã thÓ lµ Shift hoÆc Reduce. Goto cho biÕt qu¸ tr×nh chuyÓn tr¹ng th¸i khi trªn ®Ønh stack tr¹ng th¸i nhËn vµo mét ký hiÖu ch­a kÕt thóc. Goto [S, A] = S’ S lµ ký hiÖu tr¹ng th¸i. A lµ ký hiÖu ch­a kÕt thóc. S’ lµ tr¹ng th¸i ®­îc chuyÓn. (®ang ë tr¹ng th¸i S nhËn ký hiÖu A chuyÓn sang tr¹ng th¸i S’). - §¬n vÞ ®iÒu khiÓn: Tuú thuéc ký hiÖu tr¹ng th¸i (S) trªn ®Ønh stack tr¹ng th¸i vµ ký hiÖu nhËp a mµ ®¬n vÞ ®iÒu khiÓn quyÕt ®Þnh hµnh vi Shift hay Reduce dùa theo b¶ng ph©n tÝch. Action [S, a] = Shift S’ LÊy ký hiÖu nhËp a vµ ký hiÖu tr¹ng th¸i S’ ®­a vµo stack tr¹ng th¸i. ®Èy a sang stack tr¹ng th¸i. Cã nghÜa lµ lÊy a khái stack nhËp ®­a a sang stack tr¹ng th¸i. TiÕp tôc ®äc ký hiÖu nhËp kÕ tiÕp. Action [S, a] = Reduce A ® B LÊy khái stack r cÆp ký hiÖu (1 cÆp ký hiÖu gåm mét ký hiÖu tr¹ng th¸i vµ mét ký hiÖu v¨n ph¹m). r = |B| (sè ký hiÖu cña B hay chiÒu dµi cña B). §­a vµo Stack ký hiÖu A vµ ký hiÖu tr¹ng th¸i S’ = Goto [ S’’, A] (S’’ lµ ký hiÖu tr¹ng th¸i trªn ®Ønh Stack sau khi lo¹i bá r cÆp ký hiÖu tr¹ng th¸i vµ ký hiÖu v¨n ph¹m). Sau ®ã tra trong b¶ng Goto khi S’’ nhËn ký hiÖu A sÏ cho ta tr¹ng th¸i S’. Action [S, a] = accept ChÊp nhËn chuçi nhËp. Chuçi nhËp ®óng có ph¸p cña v¨n ph¹m. Action [S, a] = {} (trèng). B¸o lçi sai. Chuçi nhËp kh«ng ®óng có ph¸p cña v¨n ph¹m. - CÊu h×nh cña bé ph©n tÝch có ph¸p LR: Gi¶ sö néi dung stack tr¹ng th¸i vµ néi dung chuçi nhËp hiÖn t¹i nh­ sau: Néi dung hiÖn t¹i cña chuçi nhËp. Néi dung hiÖn t¹i cña stack tr¹ng th¸i. ai ai+1 … am $ S0 X1 S1 X2 S2 … Xn Sn §Ønh stack nhËp. §Ønh stack tr¹ng th¸i. NÕu thùc hiÖn hµnh vi Shift S’ th× ta sÏ cã néi dung stack tr¹ng th¸i vµ stack nhËp nh­ sau: Néi dung cña chuçi nhËp. Néi dung cña stack tr¹ng th¸i. S0 X1 S1 X2 S2 … Xn Sn ai S’ ai+1ai+2 … am $ §Ønh stack nhËp. §Ønh stack tr¹ng th¸i. NÕu thùc hiÖn hµnh vi Reduce A ® B th× ta sÏ cã néi dung stack tr¹ng th¸i vµ stack nhËp nh­ sau: Néi dung cña chuçi nhËp. Néi dung cña stack tr¹ng th¸i. ai ai+1 … am $ S0 X1 S1 X2 S2 … Xn-r Sn-r A S’ §Ønh stack nhËp. §Ønh stack tr¹ng th¸i. víi S’ = Goto [ Sn-r, A]. - Gi¶i thuËt ph©n tÝch ch­¬ng tr×nh: Push (So); Stack nhËp = “a1a2 … an$”; a = GetNextInput(); while (true) { get_top_of_stack(S); if ( Action [S, a] = Shift S’ ) { Push (a); Push (S’); a = GetNextInput(); } else if ( Action [S, a] = Reduce A® B ) { for ( i=1 to r = |B| ) { Pop (S); Pop (X); } get_top_of_stack(S’); Push (A); S’’ = Goto [S’, A]; Push (S’’); Output (A ® B); } else if ( Action [S, a] = Accept ) { return; } else { error (); } } //end while 4.3. X©y dùng b¶ng ph©n tÝch: Cã nhiÒu ph­¬ng ph¸p ®Ó x©y dùng b¶ng ph©n tÝch vµ ph­¬ng ph¸p SLR (Simple LR) ®­îc xem lµ dÔ cµi ®Æt nhÊt. Sau ®©y ta sÏ sö dông ph­¬ng ph¸p SLR ®Ó x©y dùng b¶ng ph©n tÝch. b­íc 1: X©y dùng v¨n ph¹m gia tè P’. b­íc 2: X¸c ®Þnh c¸c hµm Closure, Goto. b­íc 3: Tõ P’, hµm Closure, Goto x¸c ®Þnh tËp Canonical LR. b­íc 4: Tõ tËp Canonical LR x©y dùng DFA. b­íc 5: X©y dùng b¶ng ph©n tÝch SLR. VÝ Dô: X©y dùng b¶ng ph©n tÝch cho v¨n ph¹m sau: P: E ®E + T E ® T T ® T * F T ® F F ® (E) F ® id B­íc 1: x©y dùng v¨n ph¹m gia tè P’ - V¨n ph¹m gia tè lµ v¨n ph¹m ®­îc h×nh thµnh tõ mét luËt sinh ban ®Çu cña v¨n ph¹m cã thªm ký hiÖu dÊu ‘•’ ë vÕ ph¶i cña v¨n ph¹m vµ ®­îc ký hiÖu lµ LR(0) Item. -VÝ dô: V¨n ph¹m P: E ® E + T cã v¨n ph¹m gia tè nh­ sau: P: E ® •E + T E ®® E + •T E ® E + T• - T¹i vÞ trÝ dÊu ‘•’ ë vÕ ph¶i cña tËp luËt sinh cho ta biÕt ®· cã bao nhiªu ký hiÖu cña vÕ ph¶i ®· ®­îc ®­a lªn stack. C¸c ký hiÖu n»m tr­íc dÊu ‘•’ ®· ®­îc ®­a lªn stack. C¸c ký hiÖu n»m ngay sau dÊu ‘•’ sÏ ®­îc xö lý tiÕp theo. - V¨n ph¹m gia tè P’ ®­îc x©y dùng tõ v¨n ph¹m P b»ng c¸ch thªm vµo tËp luËt sinh mét luËt sinh khëi ®Çu S’ ® S (S lµ ký hiÖu xuÊt ph¸t cña v¨n ph¹m). -Ta cã P’: E’ ® E E ® E + T E ® T T ® T * F T ® F F ® (E) F ® id B­íc 2: X¸c ®Þnh c¸c hµm Closure , Goto - Gi¶ sö I lµ tËp c¸c LR (0) Item. Ta x¸c ®Þnh Closure (I) nh­ sau: - Closure (I) chøa I. - NÕu A ® a•Bb Î I vµ B ® C Î P th× thªm B Î •C vµo Closure cña I (nÕu B ® •C ch­a cã trong Closure cña I ). - Gi¶i thuËt x¸c ®Þnh tËp Closure (I): T = I; do { old_T = T; for ( item ÎT; item = A ® a•Bb ) { for ( B ® C Î P ) { T = T + { B ® •C }; } } } while (T # old_T); return T; VÝ dô: t×m Io = Closure (I) víi I = { E’ ® •E } Io = { E’ ® •E , E ® •E + T, E ® •T, T ® •T * F, T ® •F, F ® •id, F ® •(E) } - TiÕp theo ta x¸c ®Þnh Goto (I, X) nh­ sau: NÕu A ® a•XB Î I th× Goto (I, X) = Closure ({A ® aX•B }). - Gi¶i thuËt x¸c ®Þnh Goto (I, X) T = Ø; for ( item ÎT, item = A ® a•XB ) { T = T + { A ® aX•B }; } VÝ dô: gi¶ sö víi tËp Closure Io. Ta x¸c ®Þnh Goto (Io, E) = { E’ ® E• , E ® E• + T } B­íc 3: X¸c ®Þnh tËp Canonical LR Ta cã gi¶i thuËt x¸c ®Þnh nh­ sau: C = { Closure ({ S’ ® •S }) } do { old_C = C; for ( I Î C ) { for ( XÎV + T ) { if ( Goto [ I, X] # Ø) { C = C + { I }; } } } } while ( C # old_C ); return C; VÝ dô: Ta x©y dùng tËp Canonical LR cho v¨n ph¹m P nh­ sau: I X Closure() Goto[I,X] { E’ ® •E , E ® •E + T , E ® •T , T ® •T *F , T ® •F, F ® •id , F ® •(E) } Io Io E { E’ ® E• , E ® E• + T } I1 T { E ® T• , T ® T• * F } I2 F { T ®F• } I3 ( { F ® (•E) , E ® •E + T , E ® •T , T ® •T * F , T ® •F, F ® •id , F ® •(E) } I4 Id { F ® id• } I5 I1 + { E ® E + •T , T ® •T * F , T ® •F, F ® •id , F ® •(E) } I6 I2 * { T ® T * •F , F ® •id , F ® •(E) } I7 I4 E { F ® (E•) , E ® E• + T } I8 T { E ®T• , T ® T• * F } I2 F { T ® F• } I3 Id { F ® id• } I5 ( { F ® (•E) , E ® •E + T , E ® •T , T ® •T * F , T ® •F, F ® •id , F ® •(E) } I4 I6 T { E ® E + T• , T ® T •* F } I9 F { T ® F• } ( { F ® (•E) , E ® •E + T , E ® •T , T ® •T * F , T ® •F, F ® •id , F ® •(E) } I4 Id { F ® id• } I5 I7 F { T ® T * F• } I10 ( { F ®(•E) , E ® •E + T , E ® •T , T ® •T * F , T ® •F, F ® •id , F ® •(E) } I4 Id { F ® id• } I5 I8 ) { F ® (E)• } I11 + { E ® E + •T , T ®•T * F , T ®•F, F ® •id , F ® •(E) } I6 I9 * { T ® T *•F , F ®•id , F ® •(E) } I7 B­íc 4: X©y dùng DFA: - Ta ký hiÖu tr¹ng th¸i i t­¬ng øng víi phÇn tö Ii Î Canonical LR. Tr¹ng th¸i khëi ®Çu t­¬ng øng víi I cã chøa item S’® S . nÕu ë tr¹ng th¸i Ii nhËn vµo ký hiÖu X chuyÓn sang tr¹ng th¸i Ij: - Goto [ Ii , X ] = Ij th× ta ký hiÖu nh­ sau: X j i F ) T 11 10 9 0 1 < E + * 2 6 7 T 3 F E 4 8 ( 5 id B­íc 5: X©y dùng B¶ng Ph©n TÝch. - Ta ký hiÖu tr¹ng th¸i i t­¬ng øng víi phÇn tö Ii Î Canonical LR. - §èi víi B¶ng Action ta lµm nh­ sau: for ( a Î T ) { if ( A ® c•aB Î Ii ) vµ (Ij = Goto (Ii , a)) { Action [i , a] = Shift j; } } for ( A Î V , A # S’ ) { if ( A ® B• Î Ii ) { for (a ÎFollow (A)) { Action [i , a] = Reduce A ® B; } } } if (S’ ® S• Î Ii) { Action [i , a] = Accept; } - §èi víi B¶ng Goto: for ( AÎV ) { if (Ij = Goto [Ii , A]) { Goto [i , A] = j; } } ¸p dông gi¶i thuËt cho v¨n ph¹m P cho ta b¶ng ph©n tÝch sau: a S Action Goto id + * ( ) $ E T F 0 Shift 5 Shift 4 1 2 3 1 Shift 6 Accept 2 Reduce2 Shift 7 Reduce2 Reduce2 3 Reduce4 Reduce4 Reduce4 Reduce4 4 Shift 5 Shift 4 8 2 3 5 Reduce6 Reduce6 Reduce6 Reduce6 6 Shift 5 Shift 4 9 3 7 Shift 5 Shift 4 10 8 Shift 6 Shift11 9 Reduce1 Shift 7 Reduce1 Reduce1 10 Reduce3 Reduce3 Reduce3 Reduce3 11 Reduce5 Reduce5 Reduce5 Reduce5 ¸p dông b¶ng ph©n tÝch ta ph©n tÝch c©u lÖnh nhËp sau: W = id * ( id + id ) - Khëi t¹o stack tr¹ng th¸i víi ký hiÖu tr¹ng th¸i ®Çu tiªn t¹i phÇn tö 0 lµ 0. - N¹p chuçi nhËp vµo stack nhËp víi ký hiÖu kÕt thóc lµ $. Stack Tr¹ng Th¸i Chuçi NhËp Hµnh Vi DÉn XuÊt 0 id * ( id + id ) $ Shift 5 0id5 * ( id + id ) $ 0id5 * ( id + id ) $ Reduce 6 F ® id 0F3 * ( id + id ) $ Reduce 4 T ® F 0T2 * ( id + id ) $ Shift 7 0T2*7 ( id + id ) $ Shift 4 0T2*7(4 id + id ) $ Shift 5 0T2*7(4id5 + id ) $ Reduce 6 F ® id 0T2*7(4F3 + id ) $ Reduce 4 T ® F 0T2*7(4T2 + id ) $ Reduce 2 E ® T 0T2*7(4E8 + id ) $ Shift 6 0T2*7(4E8+6 id ) $ Shift 5 0T2*7(4E8+6id5 ) $ Reduce 6 F ® id 0T2*7(4E8+6F3 ) $ Reduce 4 T ® F 0T2*7(4E8+6T9 ) $ Reduce 1 E ® E + T 0T2*7(4E8 ) $ Shift 11 0T2*7(4E8)11 $ Reduce 5 F ® (E) 0T2*7F10 $ Reduce 3 T ® T * F 0T2 $ Reduce 2 E ® T 0E1 $ Accept Success Tõ b¶ng ph©n tÝch c©u lÖnh nhËp ta cã c©y có ph¸p nh­ sau: E T T * F ( E ) E F + T id F T id id F S¬ §å C©y Có Ph¸p Ch­¬ng 4: Bé Xö Lý Ng÷ NghÜa 1. Tæng qu¸t: Khi bé ph©n tÝch có ph¸p nhËn d¹ng ®­îc cÊu tróc cña mét c©u lÖnh th× gäi thùc hiÖn hµnh vi ng÷ nghÜa t­¬ng øng. VÝ dô: Xö lý ng÷ nghÜa c©u lÖnh nhËp: id * ( id + id ) Û 3 * ( 5 + 7 ) Ta sÏ sö dông mét stack ®Ó l­u tr÷ gi¸ trÞ. 0 id * ( id + id ) $ 0id9 * ( id + id ) $ 0F5 * ( id + id ) $ F ® id ( push(3) ® stack) 0T4 * ( id + id ) $ T ® F 0T4*20 ( id + id ) $ 0T4*20(6 id + id ) $ 0T4*20(6id9 + id ) $ 0T4*20(6F5 + id ) $ F ® id ( push(5) ® stack) 0T4*20(6T4 + id ) $ T ® F 0T4*20(6B3 + id ) $ B ® T 0T4*20(6B3+18 id ) $ 0T4*20(6B3+18id9 ) $ 0T4*20(6B3+18F5 ) $ F ® id ( push(7) ® stack) 0T4*20(6B3+18T35 ) $ T ® F 0T4*20(6B3 ) $ B ®B +T (stack[top-2] = stack[top-2] + stack[top-1]; top = top – 1;) 0T4*20(6A2 ) $ A ® B 0T4*20(6E23 ) $ E ® A 0T4*20(6E23)40 $ 0T4*20F37 $ F ® (E) 0T4 $ T ® T * F (stack[top-2] = stack[top-2] * stack[top-1]; top = top – 1;) 0B3 $ B ® T 0A2 $ A® B 0E1 $ KÕt qu¶ cuèi cïng sÏ ®­îc l­u t¹i Stack[0]. 2. C¸c cÊu tróc lÖnh 2.1. CÊu tróc rÏ nh¸nh: VÝ dô: if ( condition1 ) { statement; } else if ( condition2 ) { statement2; } else { statement3; } Ta sÏ hiÖn thùc vÊn ®Ò xö lý theo m« h×nh sau: §¸nh gi¸ biÓu thøc ®iÒu kiÖn 1 L1: Code V(Condition 1) §iÒu kiÖn sai,®¸nh gi¸ ®iÒu kiªn 2 Goto False L2 Thùc thi khèi lÖnh 1 Execute Code statement 1 Tho¸t khái khèi lÖnh if Goto Out §¸nh gi¸ biÓu thøc ®iÒu kiÖn 2 L2: Code V(Condition 2) §iÒu kiÖn sai,thùc thi khèi lÖnh 3 Goto False L thùc thi khèi lÖnh 2 Execute Code Statement 2 Tho¸t khái khèi lÖnh if Goto Out thùc thi khèi lÖnh 3 L: Execute Code statement 3 Out: 2.2. CÊu tróc lÖnh switch: VÝ dô: switch (expression) { case value 1: statement 1; case value 2: statement 2; case value n: statement n; default: default statement; } Ta hiÖn thùc xö lý nh­ sau: Khèi lÖnh mÆc ®Þnh Tho¸t khái khèi lÖnh switch E = e1® Thùc thi khèi lÖnh 1 Out L: en: e2: e1: Goto Out Execute default statement Execute Code statement n . . . Goto Out Execute Code statement 2 Goto Out Execute Code statement 1 §¸nh gi¸ biÓu thøc e ¬ V(Expression) 2.3. C¸c cÊu tróc lÆp 2.3.1. LÖnh While: VÝ dô: While ( Condition ) { satement; } §iÒu kiÖn sai tho¸t khái lÖnh While Out: L: TiÕp tôc ®¸nh gi¸ biÓu thøc Thùc thi khèi lÖnh §¸nh gi¸ biÓu thøc ®iÒu kiÖn 1 Goto L Execute Code statement Goto False Out Code V(Condition 1) 2.3.2. LÖnh do … while: VÝ dô: do { statement; } while ( Condition ) L: Out: §iÒu kiÖn tho¸t khái lÖnh While §¸nh gi¸ biÓu thøc ®iÒu kiÖn 1 TiÕp tôc thùc thi khèi lÖnh Thùc thi khèi lÖnh Goto L Goto False Out Code V(Condition 1) Execute Code statement 2.3.3. Khèi lÖnh for VÝ dô: For ( Init_statement; Condition; Control_statement ) { statement; } Out: L: TiÕp tôc ®¸nh gi¸ ®iÒu kiÖn Thùc thi khèi lÖnh trong th©n vßng lÆp Thùc thi khèi lÖnh trong th©n lÖnh for §iÒu kiÖn sai,tho¸t khái lÖnh for §¸nh gi¸ biÓu thøc ®iÒu kiÖn Thùc thi khèi lÖnh khëi t¹o Goto False L Execute Controen statement Execute Code statement Goto False Out Code V(Condition) Execute Init_statement Ch­¬ng 5 : Giíi ThiÖu Ng«n Ng÷ 1. Giíi thiÖu ng«n ng÷ C Sharp ( C # ) Bé Visual Studio.Net ra ®êi lµ mét b­íc nh¶y vät cña c«ng nghÖ lËp tr×nh so víi c¸c ng«n ng÷ lËp tr×nh tr­íc d©y, Visual Studio.Net kh«ng ngõng cung cÊp cho c¸c nhµ lËp tr×nh nh÷ng ph­¬ng ph¸p , c«ng cô cïng víi nh÷ng ®Æc ®iÓm míi mµ c¸c phiªn b¶n cña ng«n ng÷ lËp tr×nh tr­íc ®©y cßn thiÕu sãt. Ng«n ng÷ C Sharp lµ phiªn b¶n ®Çu tiªn võa ®­îc h·ng Microsoft giíi thiÖu trong bé Visual Studio.Net. Ng«n ng÷ C# kh¸ ®¬n gi¶n, chØ kho¶ng 80 tõ khãa vµ h¬n m­êi mÊy kiÓu d÷ liÖu ®· ®­îc x©y dùng s½n. tuy nhiªn ng«n ng÷ C# cã ý nghÜa cao khi nã thùc thi nh÷ng kh¸i niÖm lËp tr×nh hiÖn ®¹i.C# bao gåm tÊt c¶ nh÷ng hç trî cho cÊu tróc, thµnh phÇn component, lËp tr×nh h­íng ®èi t­îng.Nh÷ng tÝnh chÊt ®ã hiÖn diÖn trong mét ng«n ng÷ lËp tr×nh hiÖn ®¹i, h¬n n÷a nã ®­îc x©y dùng trªn nÒn t¶ng cña hai ng«n ng÷ m¹nh nhÊt lµ C++ vµ Java. Microsoft nãi r»ng C# mang ®Õn søc m¹nh cña ng«n ng÷ C++ víi sù dÔ dµng cña ng«n ng÷ Visual Basic.mÆc dï C# lo¹i bá mét sè ®Æc tÝnh nh­ lo¹i bá tÝnh ®a kÕ thõa trong C++, nh­ng bï l¹i nã tr¸nh ®­îc nh÷ng lçi mµ th­êng gÆp trong ng«n ng÷ C++ vµ tÊt c¶ m· nguån ®­îc viÕt trong khai b¸o mét líp, Vµ nh÷ng thµnh viªn cña líp ®­îc gäi duy nhÊt b»ng to¸n tö “.”.ngoµi ra, C# cã cã ®iÓm gièng ng«n ng÷ Java lµ c¶ hai cïng biªn dÞch ra m· trung gian: C# biªn dÞch ra MSIL cßn Java biªn dÞch ra bytecode. Sau ®ã chóng ®­îc thùc hiÖn b»ng c¸ch th«ng dÞch hoÆc biªn dÞch just-in-time trong tõng m¸y ¶o t­¬ng øng. Tuy nhiªn trong ng«n ng÷ C# nhiÒu hç trî ®­îc ®­a ra ®Ó biªn dÞch m· ng«n ng÷ trung gian sang m· m¸y.C# chøa nhiÒu kiÓu d÷ liÖu c¬ b¶n h¬n Java vµ còng cho phÐp nhiÒu sù më réng víi kiÓu d÷ liÖu gi¸ trÞ vµ tõ bá tÝnh ®a kÕ thõa trong mét líp. Trong ng«n ng÷ C#, nh÷ng cÊu tróc còng ®­îc hç trî, nh­ng kh¸i niÖm vÒ ng÷ nghÜa cña nã thay ®æi kh¸c víi C++. Trong C# mét cÊu tróc ®­îc giíi h¹n, lµ kiÓu d÷ liÖu nhá gän, vµ khi t¹o thÓ hiÖn th× nã yªu cÇu Ýt h¬n vÒ hÖ ®iÒu hµnh vµ bé nhí so víi mét líp. Mét cÊu tróc th× kh«ng thÓ kÕ thõa tõ mét líp hay ®­îc kÕ thõa nh­ng mét cÊu tróc cã thÓ thùc thi mét giao diÖn. Tãm l¹i C# lµ mét ng«n ng÷ rÊt míi mÎ vµ cã ®Çy ®ñ c¸c ®Æc tÝnh h¬n h¼n c¸c ng«n ng÷ lËp tr×nh kh¸c: lµ ng«n ng÷ ®¬n gi¶n, lµ ng«n ng÷ hiÖn ®¹i, lµ ng«n ng÷ h­íng ®èi t­îng, lµ ng«n ng÷ m¹nh mÏ vµ mÒm dÎo, lµ ng«n ng÷ cã Ýt tõ khãa, lµ ng«n ng÷ h­íng module vµ C# sÏ trë nªn phæ biÕn. 2. Giíi thiÖu ng«n ng÷ lËp tr×nh tiÕng viÖt 2.1. TËp ký hiÖu: C¸c ký tù ch÷ c¸i: tõ a … b vµ tõ A … Z C¸c ký tù sè: tõ 0 … 9 C¸c ký tù ®Æc biÖt: + - * / % & > < = ( ) {} ! _ , “ ; 2.2. C¸c kiÓu d÷ liÖu: Ta sö dông c¸c ký tù ch÷ vµ c¸c ký tù sè ®Ó ®¹t tªn cho mét danh hiÖu. C¸c danh hiÖu ph¶i ®­îc b¾t ®Çu bëi ký tù ch÷ (Kh«ng ®­îc b¾t ®Çu b»ng nh÷ng ký tù sè). indentify ® letter (letter½digit)* C¸c danh hiÖu kh«ng ®­îc chøa ký tù kho¶ng tr¾ng, kh«ng ®­îc chøa c¸c ký tù ®Æc biÖt. vÝ dô: +, - , : , { v..v.. Ch­¬ng tr×nh ph©n biÖt ch÷ hoa ch÷ th­êng, cã thÓ ®Æt tªn hµm, tªn biÕn b»ng tiÕng viÖt theo chuÈn Unicode. 2.3. C¸c to¸n tö : To¸n tö Ký HiÖu VÝ Dô Céng + x+3 Trõ - x-3 Nh©n * x*3 Chia / x/3 Chia lÈy d­ % 7%3 (kÕt qu¶ 2) G¸n = x=3 So s¸nh b»ng = = nÕu (x = = 3) th× … Lín h¬n > nÕu (x > 3) th× … Nhá h¬n < nÕu(x < 3) th× … Kh¸c != nÕu (x 3) th× … Lín h¬n hoÆc b»ng >= nÕu (x >= 3) th× … Nhá h¬n hoÆc b»ng <= nÕu (x <= 3) th× … To¸n tö logic Vµ, hoÆc NÕu (x > 3 vµ y < 3 hoÆc x = 3) th× … Ch­¬ng tr×nh sÏ ®­îc thùc thi b¾t ®Çu tõ hµm ‘chÝnh ()’. T­¬ng tù hµm ‘main ()’ trong ng«n ng÷ C. 2.4. C¸c lÖnh ch­¬ng tr×nh: 2.4.1. LÖnh khai b¸o biÕn: Ch­¬ng tr×nh hÕt søc ®¬n gi¶n, chØ cã hai kiÓu d÷ liÖu ®ã lµ kiÓu sè nguyªn vµ kiÓu sè thùc. VÝ dô: khai b¸o biÕn1, biÕn2 sè nguyªn ; khai b¸o biÕn3 sè thùc; 2.4.2. C¸c lÖnh xö lý ®iÒu kiÖn rÏ nh¸nh: - LÖnh nÕu … th× t­¬ng ®­¬ng c©u lÖnh if … then … else: Dïng xö lý lÖnh khi biÓu thøc so s¸nh cña lÖnh ‘nÕu’ tr¶ vÒ gi¸ trÞ kh¸c kh«ng (gi¸ trÞ ®óng).khi ®ã khèi lÖnh n»m trong khèi lÖnh ‘nÕu’ sÏ ®­îc thùc thi. VÝ dô: nÕu(x > 3) th× { hiÓn thÞ (“x lµ sè lín h¬n 3”); } - LÖnh nÕu … th× … kh¸c: Lµ lÖnh ‘nÕu’ më réng. Khi biÓu thøc cña c©u lÖnh ‘nÕu’ tr¶ vÒ gi¸ trÞ kh¸c kh«ng (gi¸ trÞ ®óng) th× khèi lÖnh sau mÖnh ®Ò ‘th×’ sÏ d­îc thùc hiÖn ng­îc l¹i khèi lÖnh sau mÖnh ®Ò ‘kh¸c’ sÏ ®­îc thùc thi. VÝ dô: nÕu (x % 2 = = 0) th× { hiÓn thÞ (“x lµ sè ch½n”); } kh¸c { hiÓn thÞ(“x lµ sè lΔ); } - LÖnh lùa chän … nÕu lµ … t­¬ng ®­¬ng c©u lÖnh switch … case … Lùa chän gi¸ trÞ trong mÖnh ®Ò ‘lùa chän’ vµ thùc thi khèi lÖnh tr­¬ng øng trong mÖnh ®Ò ‘nÕu lµ’. VÝ dô: Lùa chän (x) { nÕu lµ 3: hiÓn thÞ (“x b»ng 3”); tho¸t; nÕu lµ 4: hiÓn thÞ (“x b»ng 4”); tho¸t; nÕu lµ 5: hiÓn thÞ (“x b»ng 5”); tho¸t; } 2.4.3. C¸c c©u lÖnh lÆp: - LÖnh trong khi … t­¬ng ®­¬ng c©u lÖnh while … do: NÕu ®iÒu kiÖn mÖnh ®Ò ‘trong khi’ cßn ®óng th× thùc hiÖn khèi lÖnh trong vßng lÆp ‘trong khi’ cho ®Õn khi ®iÒu kiÖn trong mÖnh ®Ò ‘trong khi’ kh«ng cßn ®óng n÷a. VÝ dô: x = 10; trong khi (x>0) { x = x - 1; } - LÖnh thùc thi … cho ®Õn khi … t­¬ng ®­¬ng c©u lÖnh repeat … until … Thùc thi khèi lÖnh sau mÖnh ®Ò ‘thùc thi’ cho ®Õn khi ®iÒu kiÖn trong mÖnh ®Ò ‘cho ®Õn khi’ ®­îc tháa m·n. VÝ dô: x = 10; thùc thi { x = x -1; } cho ®Õn khi (x = 0); - LÖnh kho¶ng … t­¬ng ®­¬ng víi c©u lÖnh for … C©u lÖnh ®Çu tiªn ®­îc thùc thi trong mÖnh ®Ò ‘kho¶ng’ lµ lÖnh khëi t¹o cho vßng lÆp ‘kho¶ng’ vµ c©u lÖnh nµy chØ ®­îc thùc thi mét lÇn duy nhÊt tr­íc khi thùc hiÖn lÖnh lÆp. TiÕp theo c©u lÖnh khëi t¹o cña vßng lÆp lµ c©u lÖnh ®¸nh gi¸ biÓu thøc ®iÒu kiÖn. NÕu gi¸ trÞ tr¶ vÒ lµ ®óng th× khèi lÖnh tiÕp theo sÏ ®­îc thùc thi. Sau khi thùc thi xong khèi lÖnh trong th©n vßng lÆp ‘kho¶ng’ th× c©u lÖnh ®iÒu khiÓn väng lÆp sÏ ®­îc thùc thi. Vµ sau ®ã biÓu thøc ®iÒu kiÖn cña vßng lÆp ‘kho¶ng’ l¹i tiÕp tôc ®­îc ®¸nh gi¸ vµ vßng lÆp l¹i tiÕp tôc. Vßng lÆp ‘kho¶ng’ sÏ dõng l¹i khi gi¸ trÞ tr¶ vÒ cña biÓu thøc ®iÒu kiÖn lµ False. VÝ dô: khai b¸o i sè nguyªn; kho¶ng (i = 1;i < 10; i = i+1_ { hiÓn thÞ (“i =” + i + “\n”); } - LÖnh gäi ch­¬ng tr×nh con: Ch­¬ng tr×nh con khi ®­îc gäi sÏ t¹o t­¬ng øng víi mét b¶n ghi ho¹t ®éng. Trªn b¶ng ghi ho¹t ®éng sÏ thiÕt lËp mét sè th«ng sè nh­ ®iÓm trë vÒ, gi¸ trÞ tr¶ vÒ, c¸c tham sè h×nh thøc. Khi ch­¬ng tr×nh con kÕt thóc th× b¶ng ghi ho¹t ®éng còng ®­îc hñy bæ. Cã hai kiÓu truyÒn tham sè ®ã lµ truyÒn trÞ vµ truyÒn tham chiÕu. NÕu tham sè h×nh thøc ®­îc truyÒn trÞ th× tham sè thùc t­¬ng øng sÏ kh«ng bÞ thay ®æi khi ch­¬ng tr×nh con kÕt thóc nÕu nh­ tham sè h×nh thøc ®­îc truyÒn tham chiÕu th× tham sè thùc sÏ bÞ thay ®æi khi ch­¬ng tr×nh con kÕt thóc. VÝ dô: hµm chÝnh { khai b¸o a, b sè nguyªn; a = b = 10; tÝnh_tham_chiÕu(a, b); hiÓn thÞ (“a = “ + a +”, b = “ + b + “.\n”); // a = 11 , b = 10 } hµm tÝnh_tham_chiÕu (sè nguyªn & a, sè nguyªn b) { a = a + 1; b = b + 1; } KÕt LuËn Cã thÓ nãi r»ng hiÖn nay c«ng nghÖ th«ng tin ®· cã nh÷ng øng dông m¹nh mÏ trong cuéc sèng. X©y dùng ng«n ng÷ lËp tr×nh míi lµ xuÊt ph¸t tõ nhu cÇu thùc tÕ ph¸t triÓn cña khoa häc, mét ng«n ng÷ lËp tr×nh ®­îc viÕt b»ng tiÕng ViÖt sÏ gióp c¸c nhµ lËp tr×nh rÊt nhiÒu trong viÖc n¾m b¾t ®­îc ch­¬ng tr×nh mét c¸ch hiÖu qu¶, nhanh chãng mµ kh«ng gÆp trë ng¹i trong khi “ vèn ” tiÕng Anh cßn h¹n chÕ. Víi nh÷ng kiÕn thøc ®· ®­îc lÜnh héi ë nhµ tr­êng, cïng sù gióp ®ì tËn t×nh cña thÇy gi¸o NguyÔn C«ng NhËt, còng nh­ sù ®éng viªn, khÝch lÖ cña b¹n bÌ ®· gióp em hoµn thµnh ®Ò tµi nµy. Nh­ng do vèn kiÕn thøc vµ kû thuËt x©y dùng ng«n ng÷ lËp tr×nh cßn h¹n hÑp, do ®ã kh«ng thÓ tr¸nh khái thiÕu sãt. Em rÊt mong nhËn ®­îc sù gãp ý ch©n thµnh cña quý thÇy c« gi¸o còng nh­ c¸c b¹n ®Ó ch­¬ng tr×nh hoµn thiÖn h¬n vµ sím ®­îc øng dông vµo thùc tiÔn. Em xin ch©n thµnh c¶m ¬n! Tµi liÖu tham kh¶o TrÇn V¨n C¶nh - Ch­¬ng tr×nh dÞch, Khoa CNTT, §¹i häc vinh Aho, Sethi, Ullman - Tr×nh Biªn DÞch: Nguyªn lý, Kü thuËt vµ C«ng cô, NXB thèng kª, 2000 - 2001. Ph­¬ng Lan, Ph¹m H÷u Khang - Kü thuËt lËp tr×nh øng dông C#.Net, NXB Lao ®éng - X· héi , 2002. Hoµng §øc H¶i - Kü thuËt lËp tr×nh C#.Net, NXB Lao ®éng - X· héi, 2002.