±àÒëÔ­Àí10Ì×ÊÔ¾í¼°´ð°¸ ÏÂÔر¾ÎÄ

±àÒëÔ­ÀíÆÚÄ©ÊÔÌâ(2003Äê---2004ÄêµÚ¶þѧÆÚ) (A¾í)

Ò»¡¢Ñ¡ÔñÌ⣨±¾´óÌâ¹²20СÌ⣬ÿСÌâ1·Ö£¬¹²20·Ö£©

1¡¢»ã±à³ÌÐòÊǽ«______·­Òë³É______£»±àÒë³ÌÐòÊǽ«_______·­Òë³É__________¡£ a¡¢»ã±àÓïÑÔ³ÌÐò b¡¢»úÆ÷ÓïÑÔ³ÌÐò c¡¢¸ß¼¶ÓïÑÔ³ÌÐò d»ã±àÓïÑÔ»ò»úÆ÷ÓïÑÔ³ÌÐò

2¡¢ÃèÊöÒ»¸öÓïÑÔµÄÎÄ·¨ÊÇ___________¡£

a¡¢Î¨Ò»µÄ b¡¢²»Î¨Ò»µÄ c¡¢¸öÊýÓÐÏÞµÄ

3¡¢Éú³É·Ç0¿ªÍ·µÄÕýżÊý¼¯µÄÎÄ·¨ÊÇ______________¡£ a¡¢Z::=ABC c¡¢Z::=ABC|2|4|6|8 C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|¦Å B::=BA|B0|0 A::=1|2|3|4|5|6|7|8|9 A::=1|2|3|4|5|6|7|8|9 b¡¢Z::=ABC d¡¢Z::=ABC|2|4|6|8 C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|0 B::=BA|B0|¦Å A::=1|2|3|4|5|6|7|8|9 A::=1|2|3|4|5|6|7|8|9 4¡¢ÉèÓÐÎÄ·¨G[I]£º I¡úI0|I1|I a|Ic|a|b|c

ÏÂÁзûºÅ´®ÖÐÊǸÃÎÄ·¨µÄ¾ä×ÓµÄÓÐ___________________¡£ ¢Ùab0 ¢Úa0c01 ¢Ûaaa ¢Übc10 ¿ÉÑ¡ÏîÓÐ

a¡¢¢Ù b¡¢¢Ú¢Û¢Ü c¡¢¢Û¢Ü d¡¢¢Ù¢Ú¢Û¢Ü 5¡¢ÏÖÓÐǰ׺±íʾµÄ±í´ïʽÎÄ·¨G1£º

E::=-EE E::=-E E::=a|b|c

ÔòÎÄ·¨µÄ¾ä×Ó¡ªa-bcµÄËùÓпÉÄÜÓï·¨Ê÷ÓÐ______¿Ã¡£

a¡¢1 b¡¢2 c¡¢3 d¡¢4 6¡¢Ò»¸öÉÏÏÂÎÄÎÞ¹ØÎÄ·¨G°üÀ¨Ëĸö×é³É²¿·ÖÒÀ´ÎΪ£ºÒ»×é_____¡¢Ò»¸ö_____¡¢Ò»×é_____¡¢Ò»×é______¡£

a¡¢×Ö·û´® b¡¢×ÖĸÊý×Ö´® c¡¢²úÉúʽ d¡¢½áÊø·ûºÅ e¡¢¿ªÊ¼·ûºÅ f¡¢ÎÄ·¨ g¡¢·ÇÖÕ½á·ûºÅ h¡¢ÖÕ½á·ûºÅ

7¡¢Óï·¨·ÖÎöµÄ³£Ó÷½·¨ÊÇ_________£º

¢Ù×Ô¶¥ÏòÏ ¢Ú×Ôµ×ÏòÉÏ ¢Û×Ô×óÏòÓÒ ¢Ü×ÔÓÒÏò×ó ¿ÉÑ¡ÏîÓУº

a¡¢¢Ù¢Ú¢Û¢Ü b¡¢¢Ù¢Ú c¡¢¢Û¢Ü d¡¢¢Ù¢Ú¢Û 8¡¢ÏÂÁÐÎÄ·¨__________¶þÒåÎÄ·¨

E::=EiT|T T::=T+F|iF|F F::=E*|(

¿ÉÑ¡ÏîÓУº a¡¢ÊÇ b¡¢²»ÊÇ c¡¢ÎÞ·¨Åжϡ£ 9¡¢ËضÌÓïÊÇÖ¸_______µÄ¶ÌÓï¡£ ¢ÙÖÁÉÙ°üº¬Ò»¸ö·ûºÅ ¢ÚÖÁÉÙ°üº¬Ò»¸ö·ÇÖÕ½á·ûºÅ ¢ÛÖÁÉÙ°üº¬Ò»¸öÖÕ½á·ûºÅ

¢Ü³ý×ÔÉíÍâ²»ÔÙ°üº¬ÆäËüÖÕ½á·ûºÅ ¢Ý³ý×ÔÉíÍâ²»ÔÙ°üº¬ÆäËü·ÇÖÕ½á·ûºÅ ¢Þ³ý×ÔÉíÍâ²»ÔÙ°üº¬ÆäËü¶ÌÓï

¢ß³ý×ÔÉíÍâ²»ÔÙ°üº¬ÆäËüËضÌÓï

¿ÉÑ¡ÏîÓУº

a¡¢¢Ù¢Ü b¡¢¢Ù¢Ý c¡¢¢Ù¢Þ d¡¢¢Ú¢Ü e¡¢¢Û¢Ý f¡¢¢Û¢ßg¡¢¢Ú¢ß 10¡¢LR£¨K£©ÎÄ·¨ÊÇ_________¡£

a¡¢´Ó×óµ½ÓÒ·ÖÎö£¬¹²¾­¹ýK²½µÄÒ»ÖÖ±àÒë·½·¨¡£

b¡¢´Ó×óµ½ÓÒ·ÖÎö£¬Ã¿´ÎÏòÇ°Ô¤²âK²½µÄÒ»ÖÖ±àÒë·½·¨¡£

c¡¢´Ó×óµ½ÓÒ·ÖÎö£¬Ã¿´ÎÏòòËƾä±úµÄ·ûºÅ´®ºó¿´K¸öÊäÈë·ûºÅµÄÒ»ÖÖ±àÒë·½·¨¡£ d¡¢´Ó×óµ½ÓÒ·ÖÎö£¬Ã¿´Î×ßK²½µÄÒ»ÖÖ±àÒë·½·¨¡£ 11¡¢ÔÚ±àÒëÖвúÉúÓï·¨Ê÷ÊÇΪÁË____________¡£

a¡¢Óï·¨·ÖÎö b¡¢ÓïÒå·ÖÎö c¡¢´Ê·¨·ÖÎö d¡¢²úÉúÄ¿±ê´úÂë 12¡¢ÎÄ·¨µÄ¶þÒåÐÔºÍÓïÑԵĶþÒåÐÔÊÇÁ½¸ö____________¸ÅÄî¡£ a¡¢²»Í¬ b¡¢Ïàͬ c¡¢ÎÞ·¨ÅжÏ

13¡¢ÏÂÊöÕý¹æ±í´ïʽÖÐ________Óë(a*+b)*(c+d)µÈ¼Û¡£ ¢Ù a*£¨c+d£©+b£¨c+d£© ¢Ú a*£¨c+d£©*+b£¨c+d£©* ¢Û a*£¨c+d£©+b*£¨c+d£©

¢Ü £¨a+b£©*c+£¨a+b£©*d ¢Ý £¨a*+b£©*c+£¨a*+b£©*d

¿ÉÑ¡ÏîÓÐ:a¡¢¢Ù b¡¢¢Ú c¡¢¢Û d¡¢¢Ü e¡¢¢Ý f¡¢¢Ü¢Ý g¡¢¢Û¢Ü¢Ý

14¡¢_______ÕâÑùµÄÓïÑÔ£¬ËûÃÇÄܱ»È·¶¨µÄÓÐÏÞ×Ô¶¯»úʶ±ð£¬µ«²»ÄÜÓÃÕý¹æ±í´ïʽ±íʾ£º a¡¢´æÔÚ b¡¢²»´æÔÚ c¡¢ÎÞ·¨Åж¨ÊÇ·ñ´æÔÚ

15¡¢LL£¨K£©ÎÄ·¨________¶þÒåÐԵġ£

a¡¢¶¼ÊÇ b¡¢¶¼²»ÊÇ c¡¢²»Ò»¶¨¶¼ÊÇ

16¡¢ÏÂÃæµÄÎÄ·¨ÊÇ__________¡£S::=aAa|aBb|bAb|bBa A::=x B::=x

¿ÉÑ¡ÏîÓУºa¡¢LR£¨1£©ÎÄ·¨ b¡¢LALR£¨1£©ÎÄ·¨ c¡¢¶¼²»ÊÇ d¡¢aºÍb 17¡¢±àÒë¹ý³ÌÖУ¬±È½Ï³£¼ûµÄÖмäÓïÑÔÓÐ___________¡£ ¢Ù²¨À¼±íʾ ¢ÚÄ沨À¼±íʾ ¢ÛÈýԪʽ ¢ÜËÄԪʽ

¢ÝÊ÷Ðαíʾ

¿ÉÑ¡ÏîÓУºa¡¢¢Ù¢Û¢Ü b¡¢¢Ú¢Û¢Ü c¡¢¢Û¢Ü¢Ù¢Ý d¡¢¢Ú¢Û¢Ü¢Ý 18¡¢-a-£¨b*c/£¨c-d£©+£¨-b£©*a£©µÄÄ沨À¼±íʾÊÇ___________¡£ a¡¢abc*cd-b-a*+/-- b¡¢a-bc*cd-b-a*+/-

c¡¢a-bc*cd-/b-a*+- d¡¢a-bc*/cd-b-a*+-

19¡¢ÔÚ±àÒë³ÌÐòÖа²ÅÅÖмä´úÂëÉú³ÉµÄÄ¿µÄÊÇ_______________¡£ ¢Ù±ãÓÚ½øÐд洢¿Õ¼äµÄ×éÖ¯ ¢ÚÀûÓÚÄ¿±ê´úÂëÓÅ»¯ ¢ÛÀûÓÚ±àÒë³ÌÐòµÄÒÆÖ² ¢ÜÀûÓÚÄ¿±ê´úÂëµÄÒÆÖ²

¢ÝÀûÓÚÌá¸ßÄ¿±ê´úÂëµÄÖÊÁ¿

¿ÉÑ¡ÏîÓУº

a¡¢¢Ú¢Ü b¡¢¢Ù¢Ú¢Û c¡¢¢Û¢Ü¢Ù d¡¢¢Ú¢Û¢Ü¢Ý 20¡¢´úÂëÓÅ»¯µÄÖ÷ҪĿ±êÊÇ_____________¡£

¢ÙÈçºÎÌá¸ßÄ¿±ê³ÌÐòµÄÔËÐÐËÙ¶È ¢ÚÈçºÎ¼õÉÙÄ¿±ê³ÌÐòÔËÐÐËùÐèµÄ¿Õ¼ä¡£ ¢ÛÈçºÎЭµ÷¢ÙºÍ¢Ú

¢ÜÈçºÎʹÉú³ÉµÄÄ¿±ê´úÂ뾡¿ÉÄܼò¶Ì ¿ÉÑ¡ÏîÓУº

a¡¢¢Ú¢Ü b¡¢¢Ù¢Ú¢Û c¡¢¢Û¢Ü¢Ù d¡¢¢Ú¢Û¢Ü ¶þ¡¢¼ò´ðÌ⣺£¨Ã¿Ð¡Ìâ5·Ö£¬¹²35·Ö£©

1¡¢ Ö¤Ã÷ÏÂÃæÎÄ·¨ÊǶþÒåÐԵġ£S::=ibtSeS|ibtS|a

2¡¢ ÏÖÓÐÎÄ·¨S::=SaA|A A::=AbB|B B::=cSd|e

Çë֤ʵÊÇÎÄ·¨µÄÒ»¸ö¾äÐÍ£¬²¢Ð´³ö¸Ã¾äÐ͵ÄËùÓжÌÓï¡¢ËضÌÓïÒÔ¼°¾ä±ú¡£ 3¡¢ Çó³öÏÂÁÐÎÄ·¨Ëù²úÉúÓïÑÔ¶ÔÓ¦µÄÕý¹æʽ¡£

S::=bS|aA A::=aA|bB B::=aA|bC|b C::=bS|aA

4¡¢ ½«±í´ïʽ((a*d+c)/d+e)*f+g·Ö±ð±íʾÈýԪʽ¡¢ËÄԪʽ¡¢Ä沨À¼Ê½ÐòÁÐ 5¡¢ Ïû³ýÏÂÁÐÎÄ·¨µÄ×óµÝ¹é¡£

S::=SaP|Sf|P P::=QbP|Q Q::=cSd|e 6¡¢ ¸ø³öÓëÏÂͼµÄNFAµÈ¼ÛµÄÕý¹æÎÄ·¨¡£

¦Å S2 S3 ¦Å a S1 b S0

7¡¢ ÊÔ¶Ô»ù±¾¿éÓ¦ÓÃDAG½øÐÐÓÅ»¯£¬Ð´³öÓÅ»¯ºóµÄËÄԪʽÐòÁС£ Èý¡¢ÎÊ´ðÌ⣺

1¡¢ ÒÑÖªÎÄ·¨G A::=aABe|a B::=Bb|d

£¨1£© ¸ø³öÓëÉÏÊöÎÄ·¨µÈ¼ÛµÄLL£¨1£©ÎÄ·¨G¡¯¡£ £¨2£© ¹¹ÔìÔ¤²â·ÖÎö±í²¢¸ø³öÊäÈë´®aade#·ÖÎö¹ý³Ì¡££¨10·Ö£©

2¡¢ ÉèÒѸøÎÄ·¨G: E::=E+T E::=T T::=T*F T::=F F::=P¡üF F::=P P::=(E) P::=i ¹¹Ôì´ËÎÄ·¨µÄËã·ûÓÅÏȾØÕó¡££¨10·Ö£© 3¡¢ ÓÐÕý¹æʽb*abb*(abb*)*

£¨1£© ¹¹Ôì¸ÃÕý¹æʽËù¶ÔÓ¦µÄNFA£¨»­³ö״̬ת»»Í¼£©¡£ £¨2£© ½«ËùÇóµÄNFAÈ·¶¨»¯¡££¨»­³öÈ·¶¨»¯µÄ״̬ת»»Í¼£©¡£

£¨3£© ½«ËùÇóµÄNFA×îС»¯¡££¨»­³ö×îС»¯ºóµÄ״̬ת»»Í¼£©¡££¨10·Ö£©

4¡¢ ÈôÓÐÎÄ·¨G£¨S£©µÄ²úÉúʽÈçÏ£ºS::=L=R S::=R L::=*R L::=i R::=L,¹¹Ôìʶ±ðËùÓÐÏîÄ¿¼¯¹æ·¶×åµÄDFA¡££¨15·Ö£©

£¨1£© ÅжϸÃÎÄ·¨ÊÇ·ñÊÇLR£¨0£©ÎÄ·¨£¬ËµÃ÷ÀíÓÉ¡£ £¨2£© ÅжϸÃÎÄ·¨ÊÇ·ñÊÇSLR£¨1£©ÎÄ·¨£¬ËµÃ÷ÀíÓÉ¡£ £¨3£© ÅжϸÃÎÄ·¨ÊÇ·ñÊÇLR£¨1£©ÎÄ·¨£¬ËµÃ÷ÀíÓÉ¡£ £¨4£© ÅжϸÃÎÄ·¨ÊÇ·ñÊÇLALR£¨1£©ÎÄ·¨£¬ËµÃ÷ÀíÓÉ¡£

×° ¶© Ïß

»ªÖпƼ¼´óѧÎä²ý·ÖУ

¡¶±àÒëÔ­Àí¡·ÊÔ¾íA

רҵ°à¼¶£º_________ѧºÅ£º_________ÐÕÃû£º__________×Ü·Ö

Ò»¡¢µ¥ÏîÑ¡ÔñÌâ(¹²10СÌ⣬ÿСÌâ2·Ö) £¨Ìâ·Ö 20·Ö£©

1£®ÓïÑÔÊÇ

A£®¾ä×ӵļ¯ºÏ B£®²úÉúʽµÄ¼¯ºÏ C£®·ûºÅ´®µÄ¼¯ºÏ D£®¾äÐ͵ļ¯ºÏ 2£®±àÒë³ÌÐòÇ°Èý¸ö½×¶ÎÍê³ÉµÄ¹¤×÷ÊÇ A£®´Ê·¨·ÖÎö¡¢Óï·¨·ÖÎöºÍ´úÂëÓÅ»¯ B£®´úÂëÉú³É¡¢´úÂëÓÅ»¯ºÍ´Ê·¨·ÖÎö

C£®´Ê·¨·ÖÎö¡¢Óï·¨·ÖÎö¡¢ÓïÒå·ÖÎöºÍÖмä´úÂëÉú³É D£®´Ê·¨·ÖÎö¡¢Óï·¨·ÖÎöºÍ´úÂëÓÅ»¯

3£®Ò»¸ö¾äÐÍÖгÆΪ¾ä±úµÄÊǸþäÐ͵Ä×î×ó

A£®·ÇÖÕ½á·ûºÅ B£®¶ÌÓï C£®¾ä×Ó D£®Ö±½Ó¶ÌÓï 4£®ÏÂÍÆ×Ô¶¯»úʶ±ðµÄÓïÑÔÊÇ

A£®0ÐÍÓïÑÔ B£®1ÐÍÓïÑÔ

µÃ·Ö C£®2ÐÍÓïÑÔ D£®3ÐÍÓïÑÔ

5£®É¨ÃèÆ÷ËùÍê³ÉµÄÈÎÎñÊÇ´Ó×Ö·û´®ÐÎʽµÄÔ´³ÌÐòÖÐʶ±ð³öÒ»¸ö¸ö¾ßÓжÀÁ¢º¬ÒåµÄ×îСÓï·¨µ¥Î»¼´

A£® ×Ö·û B£®µ¥´Ê C£®¾ä×Ó D£®¾äÐÍ 6£®¶ÔÓ¦ChomskyËÄÖÖÎÄ·¨µÄËÄÖÖÓïÑÔÖ®¼äµÄ¹ØϵÊÇ A£®L0?L1?L2?L3 B£®L3?L2?L1?L0 C£®L3=L2?L1?L0 D£®L0?L1?L2=L3 7£®´Ê·¨·ÖÎöµÄÈÎÎñÊÇ

A£®Ê¶±ðµ¥´Ê B£®·ÖÎö¾ä×ӵĺ¬Òå C£®Ê¶±ð¾ä×Ó D£®Éú³ÉÄ¿±ê´úÂë 8£®³£ÓõÄÖмä´úÂëÐÎʽ²»º¬

A£®ÈýԪʽ B£®ËÄԪʽ C£®Ä沨À¼Ê½ D£®Óï·¨Ê÷

9£® ´úÂëÓÅ»¯µÄÄ¿µÄÊÇ

A£®½Úʡʱ¼ä B£®½ÚÊ¡¿Õ¼ä

C£®½Úʡʱ¼äºÍ¿Õ¼ä D£®°Ñ±àÒë³ÌÐò½øÐеȼ۽»»» 10£®´úÂëÉú³É½×¶ÎµÄÖ÷ÒªÈÎÎñÊÇ A£®°Ñ¸ß¼¶ÓïÑÔ·­Òë³É»ã±àÓïÑÔ B£®°Ñ¸ß¼¶ÓïÑÔ·­Òë³É»úÆ÷ÓïÑÔ

C£®°ÑÖмä´úÂë±ä»»³ÉÒÀÀµ¾ßÌå»úÆ÷µÄÄ¿±ê´úÂë D£®°Ñ»ã±àÓïÑÔ·­Òë³É»úÆ÷ÓïÑÔ

¶þ¡¢Ìî¿ÕÌ⣨±¾´óÌâ¹²5СÌ⣬ÿСÌâ2·Ö£©£¨Ìâ·Ö 10·Ö£©

1£®±àÒë³ÌÐòÊ×ÏÈҪʶ±ð³öÔ´³ÌÐòÖÐÿ¸ö( )£¬È»ºóÔÙ·ÖÎöÿ¸ö( )²¢·­ÒëÆäÒâÒå¡£

2£®±àÒëÆ÷³£ÓõÄÓï·¨·ÖÎö·½·¨ÓÐ( )ºÍ( )Á½ÖÖ¡£ 3£®Í¨³£°Ñ±àÒë¹ý³Ì·ÖΪ·ÖÎöÇ°¶ËÓë×ۺϺó¶ËÁ½´ó½×¶Î¡£´Ê·¨¡¢Óï·¨ºÍÓïÒå·ÖÎöÊǶÔÔ´³ÌÐòµÄ( )£¬Öмä´úÂëÉú³É¡¢´úÂëÓÅ»¯ÓëÄ¿±ê´úÂëµÄÉú³ÉÔòÊǶÔÔ´³ÌÐòµÄ( )¡£ 4£®³ÌÐòÉè¼ÆÓïÑԵķ¢Õ¹´øÀ´ÁËÈÕ½¥¶à±äµÄÔËÐÐʱ´æ´¢¹ÜÀí·½°¸£¬Ö÷Òª·ÖΪÁ½´óÀ࣬¼´£º( )·½°¸ºÍ( )·½°¸¡£

5£®¶Ô±àÒë³ÌÐò¶øÑÔ£¬ÊäÈëÊý¾ÝÊÇ( )£¬Êä³ö½á¹ûÊÇ( )¡£

Èý¡¢Ãû´Ê½âÊÍÌâ(¹²5СÌ⣬ÿСÌâ4·Ö) £¨Ìâ·Ö 20·Ö£© 1£®´Ê·¨·ÖÎö 2£®LL(1)ÎÄ·¨ 3£®Óï·¨Ê÷

4£®LR(0)·ÖÎöÆ÷ 5£®ÓïÑÔºÍÎÄ·¨

µÃ·Ö µÃ·Ö ËÄ¡¢¼ò´ðÌâ(¹²4СÌ⣬ÿСÌâ5·Ö) £¨Ìâ·Ö 20·Ö£©

1£®±àÒë³ÌÐòºÍ¸ß¼¶ÓïÑÔÓÐʲôÇø±ð? 2£®±àÒë³ÌÐòµÄ¹¤×÷·ÖΪÄǼ¸¸ö½×¶Î? 3£®¼òÊö×Ô϶øÉϵķÖÎö·½·¨¡£ 4£®¼òÊö´úÂëÓÅ»¯µÄÄ¿µÄºÍÒâÒå¡£

µÃ·Ö

Îå¡¢×ÛºÏÓ¦ÓÃÌâ(¹²3СÌ⣬ÿСÌâ10·Ö) £¨Ìâ·Ö 30·Ö£©

1£®Ö¤Ã÷ÏÂÊöÎÄ·¨G£º

S?aSbS|aS|d

ÊǶþÒåÐÔÎÄ·¨¡£

µÃ·Ö 2£®¶ÔÓÚÎÄ·¨G[S]£ºS?AB£¬A?Aa|bB£¬B?a|SbÇó¾äÐÍbaSbµÄÈ«²¿¶ÌÓï¡¢Ö±½Ó¶ÌÓïºÍ¾ä±ú£¿

¾äÐÍbaSbµÄÓï·¨Ê÷ÈçͼÎå(2)Ëùʾ¡£

A S

B b

B S b

a

ͼÎå(2) ¾äÐÍbaSbµÄµÄÓï·¨Ê÷

3£®ÉèÓзÇÈ·¶¨µÄÓÐ×ÔÏÞ¶¯»úNFA M=({A£¬B£¬C}£¬{0£¬1}£¬?£¬{A}£¬{C})£¬ÆäÖУº ? (A£¬0)={C} ? (A£¬1)={A£¬B} ? (B£¬1)={C} ? (C£¬1)={C}¡£Çë»­³ö״̬ת»»¾àÕóºÍ״̬ת»»Í¼¡£

²Î¿¼´ð°¸

Ò»¡¢µ¥ÏîÑ¡ÔñÌâ(¹²10СÌ⣬ÿСÌâ2·Ö£¬¹²20·Ö)

1£®ÓïÑÔÊÇ

A£®¾ä×ӵļ¯ºÏ B£®²úÉúʽµÄ¼¯ºÏ C£®·ûºÅ´®µÄ¼¯ºÏ D£®¾äÐ͵ļ¯ºÏ 2£®±àÒë³ÌÐòÇ°Èý¸ö½×¶ÎÍê³ÉµÄ¹¤×÷ÊÇ A£®´Ê·¨·ÖÎö¡¢Óï·¨·ÖÎöºÍ´úÂëÓÅ»¯

B£®´úÂëÉú³É¡¢´úÂëÓÅ»¯ºÍ´Ê·¨·ÖÎö

C£®´Ê·¨·ÖÎö¡¢Óï·¨·ÖÎö¡¢ÓïÒå·ÖÎöºÍÖмä´úÂëÉú³É D£®´Ê·¨·ÖÎö¡¢Óï·¨·ÖÎöºÍ´úÂëÓÅ»¯

3£®Ò»¸ö¾äÐÍÖгÆΪ¾ä±úµÄÊǸþäÐ͵Ä×î×ó

A£®·ÇÖÕ½á·ûºÅ B£®¶ÌÓï C£®¾ä×Ó D£®Ö±½Ó¶ÌÓï 4£®ÏÂÍÆ×Ô¶¯»úʶ±ðµÄÓïÑÔÊÇ

A£®0ÐÍÓïÑÔ B£®1ÐÍÓïÑÔ

C£®2ÐÍÓïÑÔ D£®3ÐÍÓïÑÔ

5£®É¨ÃèÆ÷ËùÍê³ÉµÄÈÎÎñÊÇ´Ó×Ö·û´®ÐÎʽµÄÔ´³ÌÐòÖÐʶ±ð³öÒ»¸ö¸ö¾ßÓжÀÁ¢º¬ÒåµÄ×îСÓï·¨µ¥Î»¼´

A£® ×Ö·û B£®µ¥´Ê C£®¾ä×Ó D£®¾äÐÍ

6£®¶ÔÓ¦ChomskyËÄÖÖÎÄ·¨µÄËÄÖÖÓïÑÔÖ®¼äµÄ¹ØϵÊÇ A£®L0?L1?L2?L3 B£®L3?L2?L1?L0 C£®L3=L2?L1?L0 D£®L0?L1?L2=L3 7£®´Ê·¨·ÖÎöµÄÈÎÎñÊÇ

A£®Ê¶±ðµ¥´Ê B£®·ÖÎö¾ä×ӵĺ¬Òå C£®Ê¶±ð¾ä×Ó D£®Éú³ÉÄ¿±ê´úÂë 8£®³£ÓõÄÖмä´úÂëÐÎʽ²»º¬

A£®ÈýԪʽ B£®ËÄԪʽ C£®Ä沨À¼Ê½ D£®Óï·¨Ê÷ 9£® ´úÂëÓÅ»¯µÄÄ¿µÄÊÇ

A£®½Úʡʱ¼ä B£®½ÚÊ¡¿Õ¼ä

C£®½Úʡʱ¼äºÍ¿Õ¼ä D£®°Ñ±àÒë³ÌÐò½øÐеȼ۽»»» 10£®´úÂëÉú³É½×¶ÎµÄÖ÷ÒªÈÎÎñÊÇ A£®°Ñ¸ß¼¶ÓïÑÔ·­Òë³É»ã±àÓïÑÔ B£®°Ñ¸ß¼¶ÓïÑÔ·­Òë³É»úÆ÷ÓïÑÔ

C£®°ÑÖмä´úÂë±ä»»³ÉÒÀÀµ¾ßÌå»úÆ÷µÄÄ¿±ê´úÂë D£®°Ñ»ã±àÓïÑÔ·­Òë³É»úÆ÷ÓïÑÔ

¶þ¡¢Ìî¿ÕÌ⣨±¾´óÌâ¹²5СÌ⣬ÿСÌâ2·Ö£¬¹²10·Ö£©

1£®±àÒë³ÌÐòÊ×ÏÈҪʶ±ð³öÔ´³ÌÐòÖÐÿ¸ö(µ¥´Ê)£¬È»ºóÔÙ·ÖÎöÿ¸ö(¾ä×Ó)²¢·­ÒëÆäÒâÒå¡£ 2£®±àÒëÆ÷³£ÓõÄÓï·¨·ÖÎö·½·¨ÓÐ(×Ôµ×ÏòÉÏ)ºÍ(×Ô¶¥ÏòÏÂ)Á½ÖÖ¡£

3£®Í¨³£°Ñ±àÒë¹ý³Ì·ÖΪ·ÖÎöÇ°¶ËÓë×ۺϺó¶ËÁ½´ó½×¶Î¡£´Ê·¨¡¢Óï·¨ºÍÓïÒå·ÖÎöÊǶÔÔ´³ÌÐòµÄ(·ÖÎö)£¬Öмä´úÂëÉú³É¡¢´úÂëÓÅ»¯ÓëÄ¿±ê´úÂëµÄÉú³ÉÔòÊǶÔÔ´³ÌÐòµÄ(×ÛºÏ)¡£

4£®³ÌÐòÉè¼ÆÓïÑԵķ¢Õ¹´øÀ´ÁËÈÕ½¥¶à±äµÄÔËÐÐʱ´æ´¢¹ÜÀí·½°¸£¬Ö÷Òª·ÖΪÁ½´óÀ࣬¼´(¾²Ì¬´æ´¢·ÖÅä)·½°¸ºÍ(¶¯Ì¬´æ´¢·ÖÅä)·½°¸¡£

5£®¶Ô±àÒë³ÌÐò¶øÑÔ£¬ÊäÈëÊý¾ÝÊÇ(Ô´³ÌÐò)£¬Êä³ö½á¹ûÊÇ(Ä¿±ê³ÌÐò)¡£

Èý¡¢Ãû´Ê½âÊÍÌâ(¹²5СÌ⣬ÿСÌâ4·Ö£¬¹²20·Ö)

1£®´Ê·¨·ÖÎö

´Ê·¨·ÖÎöµÄÖ÷ÒªÈÎÎñÊÇ´Ó×óÏòÓÒɨÃèÿÐÐÔ´³ÌÐòµÄ·ûºÅ£¬°´ÕÕ´Ê·¨¹æÔò ´Ó¹¹³ÉÔ´³ÌÐòµÄ×Ö·û´®ÖÐʶ±ð³öÒ»¸ö¸ö¾ßÓжÀÁ¢ÒâÒåµÄ×îСÓï·¨µ¥Î»£¬ ²¢×ª»»³ÉͳһµÄÄÚ²¿±íʾ(token)£¬Ë͸øÓï·¨·ÖÎö³ÌÐò¡£ 2£®LL(1)ÎÄ·¨

ÈôÎÄ·¨µÄÈκÎÁ½¸ö²úÉúʽA ? ? | ?¶¼Âú×ãÏÂÃæÁ½¸öÌõ¼þ£º £¨1£©FIRST(? ) ? FIRST(? ) = ?£»

£¨2£©Èô? ?* ? £¬ÄÇôFIRST(? ) ? FOLLOW( A ) = ?¡£

ÎÒÃÇ°ÑÂú×ãÕâÁ½¸öÌõ¼þµÄÎÄ·¨½Ð×öLL(1)ÎÄ·¨£¬ÆäÖеĵÚÒ»¸öL´ú±í´Ó×ó ÏòÓÒɨÃèÊäÈ룬µÚ¶þ¸öL±íʾ²úÉú×î×óÍƵ¼£¬1´ú±íÔÚ¾ö¶¨·ÖÎöÆ÷µÄÿ²½ ¶¯×÷ʱÏòÇ°¿´Ò»¸öÊäÈë·ûºÅ¡£³ýÁËûÓй«¹²×óÒò×ÓÍ⣬LL(1)ÎÄ·¨»¹ÓÐÒ» ЩÃ÷ÏÔµÄÐÔÖÊ£¬Ëü²»ÊǶþÒåµÄ£¬Ò²²»º¬×óµÝ¹é¡£

3£®Óï·¨Ê÷

¾ä×ÓµÄÊ÷½á¹¹±íʾ·¨³ÆΪÓï·¨Ê÷(Óï·¨·ÖÎöÊ÷»òÓï·¨ÍƵ¼Ê÷)¡£

¸ø¶¨ÎÄ·¨G=(VN£¬VT£¬P£¬S)£¬¶ÔÓÚGµÄÈκξäÐͶ¼Äܹ¹ÔìÓëÖ®¹ØÁªµÄ Óï·¨Ê÷¡£Õâ¿ÃÊ÷¾ßÓÐÏÂÁÐÌØÕ÷£º (1)¸ù½ÚµãµÄ±ê¼ÇÊÇ¿ªÊ¼·ûºÅS¡£

(2)ÿ¸ö½ÚµãµÄ±ê¼Ç¶¼ÊÇVÖеÄÒ»¸ö·ûºÅ¡£ (3)ÈôÒ»¿Ã×ÓÊ÷µÄ¸ù½ÚµãΪA£¬ÇÒÆäËùÓÐÖ±½Ó×ÓËïµÄ±ê¼Ç´Ó×óÏòÓÒµÄÅÅÁÐ ´ÎÐòΪA1A2¡­AR£¬ÄÇôA?A1A2¡­ARÒ»¶¨ÊÇPÖеÄÒ»Ìõ²úÉúʽ¡£ (4)ÈôÒ»±ê¼ÇΪAµÄ½ÚµãÖÁÉÙÓÐÒ»¸ö³ýËüÒÔÍâµÄ×ÓËÔòA?VN¡£ (5)ÈôÊ÷µÄËùÓÐÒ¶½ÚµãÉϵıê¼Ç´Ó×óµ½ÓÒÅÅÁÐΪ×Ö·û´®w£¬ÔòwÊÇÎÄ·¨G µÄ¾äÐÍ£»ÈôwÖнöº¬ÖÕ½á·ûºÅ£¬ÔòwΪÎÄ·¨GËù²úÉúµÄ¾ä×Ó¡£ 4£®LR(0)·ÖÎöÆ÷

ËùνLR(0)·ÖÎö£¬ÊÇÖ¸´Ó×óÖÁÓÒɨÃèºÍ×Ôµ×ÏòÉϵÄÓï·¨·ÖÎö£¬ÇÒÔÚ·ÖÎöµÄ ÿһ²½£¬Ö»Ðë¸ù¾Ý·ÖÎöÕ»µ±Ç°ÒÑÒƽøºÍ¹éÔ¼³öµÄÈ«²¿ÎÄ·¨·ûºÅ£¬²¢ÖÁ¶àÔÙ ÏòÇ°²é¿´0¸öÊäÈë·ûºÅ£¬¾ÍÄÜÈ·¶¨Ïà¶ÔÓÚijһ²úÉúʽ×󲿷ûºÅµÄ¾ä±úÊÇ·ñ ÒÑÔÚ·ÖÎöÕ»µÄ¶¥²¿Ðγɣ¬´Ó¶øÒ²¾Í¿ÉÒÔÈ·¶¨µ±Ç°ËùÓ¦²ÉÈ¡µÄ·ÖÎö¶¯×÷ (ÊÇ Òƽø»¹ÊÇ°´Ä³Ò»²úÉúʽ½øÐйéÔ¼µÈ)¡£

5£®ÓïÑÔºÍÎÄ·¨

ÎÄ·¨¾ÍÊÇÓïÑԽṹµÄ¶¨ÒåºÍÃèÊö£¬ÊÇÓÐÇî·Ç¿ÕµÄ²úÉúʽ¼¯ºÏ¡£ ÎÄ·¨G¶¨ÒåΪËÄÔª×éµÄÐÎʽ£º

G=(VN£¬VT£¬P£¬S)

ÆäÖУºVN ÊÇ·Ç¿ÕÓÐÇºÏ£¬³ÆΪ·ÇÖÕ½á·ûºÅ¼¯ºÏ£»VT ÊÇ·Ç¿ÕÓÐÇºÏ£¬ ³ÆΪÖÕ½á·ûºÅ¼¯ºÏ£»PÊDzúÉúʽµÄ¼¯ºÏ(·Ç¿Õ)£»SÊÇ¿ªÊ¼·ûºÅ(»òʶ±ð·ûºÅ)¡£ ÕâÀVN¡ÉVT=?£¬S?VN¡£V=VN¡ÈVT£¬³ÆΪÎÄ·¨GµÄ×Öĸ±í£¬ËüÊdzöÏÖ ÎÄ·¨²úÉúʽÖеÄÒ»ÇзûºÅµÄ¼¯ºÏ¡£

ÎÄ·¨GËùÃèÊöµÄÓïÑÔÓÃL(G)±íʾ£¬ËüÓÉÎÄ·¨GËù²úÉúµÄÈ«²¿¾ä×Ó×é³É£¬¼´

L(G)={x| S?*x£¬ÆäÖÐSΪÎÄ·¨¿ªÊ¼·ûºÅ£¬ÇÒx?VT } ¼òµ¥µÄ˵£¬ÎÄ·¨ÃèÊöµÄÓïÑÔÊǸÃÎÄ·¨Ò»Çоä×ӵļ¯ºÏ¡£

?

ËÄ¡¢¼ò´ðÌâ(¹²4СÌ⣬ÿСÌâ5·Ö£¬¹²20·Ö)

1£®±àÒë³ÌÐòºÍ¸ß¼¶ÓïÑÔÓÐʲôÇø±ð?

Óûã±àÓïÑÔ»ò¸ß¼¶ÓïÑÔ±àдµÄ³ÌÐò£¬±ØÐëÏÈËÍÈë¼ÆËã»ú£¬¾­¹ýת»»³ÉÓûúÆ÷ ÓïÑÔ±íʾµÄÄ¿±ê³ÌÐò£¨Õâ¸ö¹ý³Ì¼´±àÒ룩£¬²ÅÄÜÓɼÆËã»úÖ´ÐС£Ö´ÐÐת»»¹ý³Ì µÄ³ÌÐò½Ð±àÒë³ÌÐò¡£»ã±à³ÌÐòÊÇָûÓбàÒë¹ýµÄ»ã±àÓïÑÔÔ´Îļþ¡£±àÒë³ÌÐòת »»¹ýµÄ½ÐÄ¿±ê³ÌÐò£¬Ò²¾ÍÊÇ»úÆ÷ÓïÑÔ¡£

±àÒë³ÌÐòµÄ¹¤×÷Çé¿öÓÐÈýÖÖ£º»ã±àÐÍ¡¢½âÊÍÐͺͱàÒëÐÍ¡£»ã±àÐͱàÒë³ÌÐòÓÃÀ´ ½«»ã±àÓïÑÔ±àдµÄ³ÌÐò£¬°´ÕÕÒ»Ò»¶ÔÓ¦µÄ¹Øϵ£¬×ª»»³ÉÓûúÆ÷ÓïÑÔ±íʾµÄ³ÌÐò¡£ ½âÊÍÐͱàÒë³ÌÐò½«¸ß¼¶ÓïÑÔ³ÌÐòµÄÒ»¸öÓï¾ä£¬ÏȽâÊͳÉΪһ×é»úÆ÷ÓïÑÔµÄÖ¸Á È»ºóÁ¢¼´Ö´ÐУ¬Ö´ÐÐÍêÁË£¬È¡ÏÂÒ»×éÓï¾ä½âÊͺÍÖ´ÐУ¬Èç´Ë¼ÌÐøµ½Íê³ÉÒ»¸ö³ÌÐò Ö¹¡£ÓýâÊÍÐͱàÒë³ÌÐò£¬Ö´ÐÐËٶȺÜÂý£¬µ«¿ÉÒÔ½øÐÐÈ˺ͼÆËã»úµÄ\¶Ô»°\£¬Ëæʱ

¿ÉÒÔÐ޸ĸ߼¶ÓïÑԵijÌÐò¡£BASICÓïÑÔ¾ÍÊǽâÊÍÐ͸߼¶ÓïÑÔ¡£±àÒëÐͱàÒë³ÌÐò½« ¼¶ÓïÑÔ±àдµÄ³ÌÐò£¬Ò»´Î¾Í»á²¿·­Òë³É»úÆ÷ÓïÑÔ±íʾµÄ³ÌÐò£¬¶øÇÒ¹ý³Ì½øÐкܿ죬 ÔÚ¹ý³ÌÖУ¬²»ÄܽøÐÐÈË»ú¶Ô»°Ð޸ġ£FORTRANÓïÑÔ¾ÍÊDZàÒëÐ͸߼¶ÓïÑÔ¡£ 2£®±àÒë³ÌÐòµÄ¹¤×÷·ÖΪÄǼ¸¸ö½×¶Î?

´Ê·¨·ÖÎö¡¢Óï·¨·ÖÎöºÍÓïÒå·ÖÎöÊǶÔÔ´³ÌÐò½øÐеķÖÎö(³ÆΪ±àÒë³ÌÐòµÄÇ°¶Ë)£¬ ¶øÖмä´úÂëÉú³É¡¢´úÂëÓÅ»¯ºÍ´úÂëÉú³ÉÈý¸ö½×¶ÎºÏ³ÆΪ¶ÔÔ´³ÌÐò½øÐÐ×ÛºÏ(³ÆΪ ±àÒë³ÌÐòµÄºó¶Ë)£¬ËüÃÇ´ÓÔ´³ÌÐòµÄÖмä±íʾ½¨Á¢ÆðºÍÔ´³ÌÐòµÈ¼ÛµÄÄ¿±ê³ÌÐò¡£ 3£®¼òÊö×Ô϶øÉϵķÖÎö·½·¨¡£

Ëùν×Ô϶øÉÏ·ÖÎö·¨¾ÍÊÇ´ÓÊäÈë´®¿ªÊ¼£¬Öð²½½øÐС°¹éÔ¼¡±£¬Ö±ÖÁ¹éÔ¼µ½ÎÄ·¨µÄ ¿ªÊ¼·ûºÅ£»»òÕß˵´ÓÓï·¨Ê÷µÄÄ©¶Ë¿ªÊ¼£¬²½²½ÏòÉÏ¡°¹éÔ¼¡±£¬Ö±µ½¸ù½Úµã¡£ 4£®¼òÊö´úÂëÓÅ»¯µÄÄ¿µÄºÍÒâÒå¡£

´úÂëÓÅ»¯ÊǾ¡Á¿Éú³É¡°ºÃ¡±µÄ´úÂëµÄ±àÒë½×¶Î¡£Ò²¾ÍÊÇÒª¶Ô³ÌÐò´úÂë½øÐÐ Ò»Öֵȼ۱任£¬ÔÚ±£Ö¤±ä»»Ç°ºó´úÂëÖ´Ðнá¹ûÏàͬµÄÇ°ÌáÏ£¬¾¡Á¿Ê¹Ä¿ ±ê³ÌÐòÔËÐÐʱËùÐèÒªµÄʱ¼ä¶Ì£¬Í¬Ê±ËùÕ¼ÓõĴ洢¿Õ¼äÉÙ¡£

Îå¡¢×ÛºÏÓ¦ÓÃÌâ(¹²3СÌ⣬ÿСÌâ10·Ö£¬¹²30·Ö)

1£®Ö¤Ã÷ÏÂÊöÎÄ·¨G£º

S?aSbS|aS|d

ÊǶþÒåÐÔÎÄ·¨¡£ ½â£º

Ò»¸öÎÄ·¨£¬Èç¹û´æÔÚij¸ö¾ä×ÓÓв»Ö»Ò»¿ÃÓï·¨·ÖÎöÊ÷ÓëÖ®¶ÔÓ¦£¬ÄÇô³ÆÕâ¸ö ÎÄ·¨ÊǶþÒåÐÔÎÄ·¨¡£

¾ä×ÓaadbdÓÐÁ½¿ÃÓï·¨Ê÷¡£ÈçÏÂͼ£º

ÓÉ´Ë¿ÉÖª£¬S?aSbS|aS|d¶¨ÒåµÄÎÄ·¨ÊǶþÒåÐÔÎÄ·¨¡£ 2£®¶ÔÓÚÎÄ·¨G[S]£ºS?AB£¬A?Aa|bB£¬B?a|SbÇó¾äÐÍbaSbµÄÈ«²¿¶ÌÓï¡¢Ö±½Ó¶ÌÓïºÍ¾ä±ú£¿ ¾äÐÍbaSbµÄÓï·¨Ê÷ÈçͼÎå(2)Ëùʾ¡£

b

A S

B a S d

d a S d

b a

S b S S a S S S d

(1) (2) B S b

a

ͼÎå(2) ¾äÐÍbaSbµÄµÄÓï·¨Ê÷

½â£º

baSbΪ¾äÐÍbaSbµÄÏà¶ÔÓÚSµÄ¶ÌÓbaΪ¾äÐÍbaSbµÄÏà¶ÔÓÚAµÄ¶ÌÓSbΪ¾äÐÍbaSbµÄÏà¶ÔÓÚBµÄ¶ÌÓÇÒΪֱ½Ó¶ÌÓaΪ¾äÐÍbaSbµÄÏà¶ÔÓÚBµÄ¶ÌÓÇÒΪֱ½Ó¶ÌÓïºÍ¾ä±ú¡£

3£®ÉèÓзÇÈ·¶¨µÄÓÐ×ÔÏÞ¶¯»úNFA M=({A£¬B£¬C}£¬{0£¬1}£¬?£¬{A}£¬{C})£¬ÆäÖУº ? (A£¬0)={C} ? (A£¬1)={A£¬B} ? (B£¬1)={C} ? (C£¬1)={C}¡£Çë»­³ö״̬ת»»¾àÕóºÍ״̬ת»»Í¼¡£ ½â£º

״̬ת»»¾àÕóΪ£º

? A B C

״̬ת»»Í¼Îª£º

1 1 AB0 C ? ? 1 A£¬B C C 1 1 C10 2001Äê±àÒëÔ­ÀíÊÔÌâ

1£®£¨10·Ö£©´¦ÓÚ/* ºÍ */Ö®¼äµÄ´®¹¹³É×¢½â£¬×¢½âÖмäûÓÐ*/¡£»­³ö½ÓÊÜÕâÖÖ

×¢½âµÄDFAµÄ״̬ת»»Í¼¡£ 2£®£¨10·Ö£©ÎªÓïÑÔ

L £½ {ambn | 0 ? m ? 2n}£¨¼´aµÄ¸öÊý²»³¬¹ýbµÄ¸öÊýµÄÁ½±¶£©

дһ¸öLR£¨1£©ÎÄ·¨£¬²»×¼³¬¹ý6¸ö²úÉúʽ¡££¨Èô³¬¹ý6¸ö²úÉúʽ£¬²»¸ø·Ö¡£ÈôËùдÎÄ·¨²»ÊÇLR£¨1£©ÎÄ·¨£¬×î¶à¸ø5·Ö¡££© 3£®£¨10·Ö£©¹¹ÔìÏÂÃæÎÄ·¨µÄLL£¨1£©·ÖÎö±í¡£ D ? TL

T ? int | real L ? id R

R ? , id R | ? 4£®£¨15·Ö£©¾ÍÏÂÃæÎÄ·¨ S ? ( L) | a L ? L ? S | S ? ¸ø³öÒ»¸öÓï·¨ÖƵ¼¶¨Ò壬ËüÊä³öÅä¶ÔÀ¨ºÅµÄ¸öÊý¡£ ? ¸ø³öÒ»¸ö·­Òë·½°¸£¬ËüÊä³öÿ¸öaµÄǶÌ×Éî¶È¡£ Èç¾ä×Ó(a, (a, a) )£¬µÚһСÌâµÄÊä³öÊÇ2£¬µÚ¶þСÌâµÄÊä³öÊÇ1 2 2¡£ 5£®£¨10·Ö£©PascalÓïÑÔforÓï¾äµÄº¬Òå¼û½Ì²ÄµÚ222ҳϰÌâ7.13¡£ÇëΪ¸ÃÓï¾äÉè¼ÆÒ»ÖÖºÏÀíµÄÖмä´úÂë½á¹¹¡£Äã¿ÉÒÔ°´µÚ215ҳͼ7.17µÄ·½Ê½»òÕßµÚ219ҳͼ7.19µÄ·½Ê½Ð´³öÄãµÄÉè¼Æ£¬²»ÐèҪд²úÉúÖмä´úÂëµÄÓï·¨ÖƵ¼¶¨Òå¡£ 6£®£¨5·Ö£©Ò»¸öCÓïÑÔ³ÌÐòÈçÏ£º

func(i1,i2,i3) long i1,i2,i3; {

long j1,j2,j3;

printf(\ printf(\}

main() {

long i1,i2,i3; func(i1,i2,i3); }

¸Ã³ÌÐòÔÚijÖÖ»úÆ÷µÄLinuxÉϵÄÔËÐнá¹ûÈçÏ£º

Addresses of i1,i2,i3 = 27777775460,27777775464,27777775470 Addresses of j1,j2,j3 = 27777775444,27777775440,27777775434

´ÓÉÏÃæµÄ½á¹û¿ÉÒÔ¿´³ö£¬func º¯ÊýµÄ3¸öÐÎʽ²ÎÊýµÄµØÖ·ÒÀ´ÎÉý¸ß£¬¶ø3¸ö¾Ö²¿±äÁ¿µÄµØÖ·ÒÀ´Î½µµÍ¡£ÊÔ˵Ã÷Ϊʲô»áÓÐÕâ¸öÇø±ð¡£

7£®£¨15·Ö£©Ò»¸öCÓïÑÔ³ÌÐò¼°ÆäÔÚijÖÖ»úÆ÷linux²Ù×÷ϵͳÉϵıàÒë½á¹ûÈçÏ¡£¸ù¾ÝËùÉú³ÉµÄ»ã±à³ÌÐòÀ´½âÊͳÌÐòÖÐËĸö±äÁ¿µÄ×÷ÓÃÓò¡¢Éú´æÆÚºÍÖóõÖµ·½Ê½µÈ·½ÃæµÄÇø±ð¡£

static long aa = 10; short bb = 20;

func() {

static long cc = 30; short dd = 40; }

.file \ .version \gcc2_compiled.: .data

.align 4

.type aa,@object .size aa,4 aa:

.long 10 .globl bb .align 2

.type bb,@object .size bb,2 bb:

.value 20 .align 4

.type cc.2,@object .size cc.2,4 cc.2:

.long 30 .text

.align 4 .globl func

.type func,@function func:

pushl ?p

movl %esp,?p subl $4,%esp

movw $40,-2(?p)

.L1:

leave ret .Lfe1:

.size func,.Lfe1-func .ident \(GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)\ 8£®£¨10·Ö£©CÓïÑÔÊÇÒ»ÖÖÀàÐÍÓïÑÔ£¬µ«Ëü²»ÊÇÇ¿ÀàÐÍÓïÑÔ£¬ÒòΪ±àÒëʱµÄÀàÐͼì²é²»Äܱ£Ö¤Ëù½ÓÊܵijÌÐòûÓÐÔËÐÐʱµÄÀàÐÍ´íÎó¡£ÀýÈ磬±àÒëʱµÄÀàÐͼì²éÒ»°ã²»Äܱ£Ö¤ÔËÐÐʱûÓÐÊý×éÔ½½ç¡£ÇëÄãÔÙ¾ÙÒ»¸öÕâÑùµÄÀý×Ó˵Ã÷CÓïÑÔ²»ÊÇÇ¿ÀàÐÍÓïÑÔ¡£ 9£®£¨10·Ö£©Èç¹ûÔÚA»úÆ÷ÉÏÎÒÃÇÓÐCÓïÑÔ±àÒëÆ÷CCA£¬Ò²ÓÐËüµÄÔ´ÂëSA£¨ÓÃCÓïÑÔд³É£©¡£ÈçºÎÀûÓÃËüͨ¹ý¾¡Á¿ÉٵŤ×÷À´µÃµ½B»úÆ÷µÄCÓïÑÔ±àÒëÆ÷CCB¡£ 10£®£¨5·Ö£©±í´ïʽ(?x.(?yz.(x + y) + z) 3) 4 5ºÍ(?x.(?yz.(x + y) + z) 3 5) 4ÓÐͬÑùµÄ½á¹û¡£ÔÚ³éÏó»úFAMÉÏ£¬ÄÄÒ»¸ö±í´ïʽ¶ÔÓ¦µÄÄ¿±ê´úÂëµÄÖ´ÐÐЧÂʸߣ¿ÎªÊ²Ã´£¿

2001Äê±àÒëÔ­ÀíÊÔÌâ²Î¿¼´ð°¸

1£®

others start 1 / 2 * 2 * others 4 *

/ 5

2£®LR£¨1£©ÎÄ·¨ S ? AB | aABb A ? aaAb | ? B ? Bb | ?

3£® int D D?TL T T?int L R

LR£¨1£©ÎÄ·¨ S ? AB A ? aaAb | ab | ? B ? Bb | ?

id

¶þÒåÎÄ·¨ S ? AASb | ? A ? a | ?

real

D?TL T?real

, $

L?id R

R ?, id R R ? ?

4£® S? ? S print(S.num) S ? (L) S.num := L.num +1 S ? a S.num := 0 L ? L1,S L.num := L1.num + S.num L ? S L.num := S.num S? ? {S.depth := 0} S S ? {L.depth := S.depth +1} (L) S ? a {print(S.depth)} L ? {L1.depth := L.depth} L1, {S.depth := L.depth} S L ? { S.depth := L.depth} S

5£® t1 := initial t2 := final if t1 > t2 goto L1 v := t1 L2: stmt if v = t2 goto L1 v := v + 1 goto L2 L1:

6£®ÓÉÓÚʵ²Î±í´ïʽÊÇ·´Ðò½øÈë»î¶¯¼Ç¼£¬¶ø¾Ö²¿±äÁ¿ÊÇ˳ÐòÔڻ¼Ç¼ÖзÖÅä¡£

7£®aaÊǾ²Ì¬Íⲿ±äÁ¿£¬¶øbbÊÇÍⲿ±äÁ¿£¬ËüÃǶ¼·ÖÅäÔÚ¾²Ì¬Êý¾ÝÇø£¨ÓÉ.dataαָÁʼ£©£¬µ«ÊÇbbÓÉαָÁî.globlÖ¸Ã÷Ϊȫ¾ÖµÄ£¬ÓÃÀ´½â¾öÆäËüÎļþÖжÔbbµÄÍⲿÒýÓ㬶øaaÖ»ÄÜÓɱ¾ÎļþÒýÓá£ccÊǾ²Ì¬¾Ö²¿±äÁ¿£¬Í¬aaºÍbbÒ»Ñù£¬ËüµÄÉú´æÆÚÊÇÕû¸ö³ÌÐò²¢·ÖÅäÔÚ¾²Ì¬Êý¾ÝÇø¡£ÓÉÓÚccÔÚÔ´³ÌÐòÖеÄ×÷ÓÃÓòÊǺ¯ÊýfuncµÄÌ壬¶øÔÚÄ¿±êÎļþÖУ¬ËüµÄ×÷ÓÃÓòÖÁÉÙÒÑÊÇÕû¸öÎļþÁË£¬Îª±ÜÃâͬԴÎļþÖÐÍⲿ±äÁ¿ºÍÆäËüº¯ÊýµÄ¾²Ì¬¾Ö²¿±äÁ¿µÄÃû×Ö³åÍ»£¬ËùÒÔÒª¶ÔËü½øÐиÄÃû£¬³ÉÁËcc.2¡£ÓÉÓÚcc²»ÊÇÈ«¾ÖµÄ£¬Òò´Ëcc.2Ç°ÃæûÓÐαָÁî.globl¡£ddÊÇ×Ô¶¯±äÁ¿£¬Æä×÷ÓÃÓòÊǺ¯ÊýfuncµÄÌ壬ÆäÉú´æÆÚÊǸú¯Êý¼¤»îÆڼ䣬Òò´ËËü·ÖÅäÔÚÕ»Çø£¬²¢ÇÒÖóõÖµÊÇÓÃÔËÐÐʱµÄ¸³ÖµÀ´ÊµÏÖ¡£

8£®ÀýÈçÁªºÏÌåµÄÀàÐͼì²éÒ»°ãÒ²²»¿ÉÄÜÔÚ±àÒëʱÍê³É£¬ËäÈ»ÏÂÃæÀý×ÓÊǿɾ²Ì¬ÅжÏÀàÐÍ´íÎóµÄ¡£ union U { int u1; int *u2;} u; int ?p; u.u1 = 10; p = u.u2; ?p = 0;

9£® ? ÐÞ¸ÄÔ´ÂëSA µÄ´úÂëÉú³É²¿·Ö£¬ÈÃËü²úÉúB»úÆ÷µÄ´úÂ룬³Æ½á¹û³ÌÐòΪSB¡£

? ½«SBÌá½»¸øCCA½øÐбàÒ룬µÃµ½Ò»¸ö¿ÉÖ´ÐгÌÐò¡£ ? ½«SBÌá½»¸øÉÏÊö¿ÉÖ´ÐгÌÐò½øÐбàÒ룬µÃµ½ËùÐèµÄ±àÒëÆ÷CCB¡£

10£®µÚÒ»¸ö±í´ïʽÔÚÖ´ÐÐ?yz.(x + y) + z) 3ʱ³öÏÖ²ÎÊý¸öÊý²»×ãµÄÇé¿ö£¬Òò´ËÓÐFUNVALµÄÖµ½øÈëÕ»¶¥£¬È»ºó·¢ÏÖ²ÎÊý¸öÊý²»×㣬ÓÖ°ÑËü×ö³ÉFANVALµÄÇé¿ö¡£¶øµÚ¶þ¸ö±í´ïʽִÐеÄÊÇ(?yz.(x + y) + z) 3 5£¬²»»á³öÏÖ²ÎÊý¸öÊý²»×ãµÄÇé¿ö¡£Òò´ËµÚ¶þ¸ö±í´ïʽµÄÖ´ÐÐЧÂʱȵÚÒ»¸ö±í´ïʽµÄ¸ß¡£

¡¶±àÒëÔ­Àí¡·¿¼ÊÔÊÔÌâ

£¨ËùÓд𰸱ØÐëдÔÚ´ðÌâÖ½ÉÏ£©

(2006.12.25)

Ò»¡¢(5¡Á6·Ö)»Ø´ðÏÂÁÐÎÊÌ⣺

1£®Ê²Ã´ÊÇS-ÊôÐÔÎÄ·¨£¿Ê²Ã´ÊÇL-ÊôÐÔÎÄ·¨£¿ËüÃÇÖ®¼äÓÐʲô¹Øϵ£¿ 2£®Ê²Ã´ÊǾä±ú£¿Ê²Ã´ÊÇËضÌÓ

3£®»®·Ö³ÌÐòµÄ»ù±¾¿éʱ£¬È·¶¨»ù±¾¿éµÄÈë¿ÚÓï¾äµÄÌõ¼þÊÇʲô£¿ 4£®ÔËÐÐʱµÄDISPLAY±íµÄÄÚÈÝÊÇʲô£¿ËüµÄ×÷ÓÃÊÇʲô£¿ 5£®¶ÔÏÂÁÐËÄԪʽÐòÁÐÉú³ÉÄ¿±ê´úÂ룺

A:=B*C D:=E+F G:=A+D H:=G*2

ÆäÖУ¬HÊÇ»ù±¾¿é³ö¿ÚµÄ»îÔ¾±äÁ¿£¬ R0ºÍR1ÊÇ¿ÉÓüĴæÆ÷

¶þ¡¢(8·Ö)Éè?={0£¬1}ÉϵÄÕý¹æ¼¯SÓɵ¹ÊýµÚ¶þ¸ö×Ö·ûΪ1µÄËùÓÐ×Ö·û´®×é³É£¬Çë¸ø³ö¸Ã×Ö¼¯¶ÔÓ¦µÄÕý¹æʽ£¬²¢¹¹ÔìÒ»¸öʶ±ð¸ÃÕý¹æ¼¯µÄDFA¡£ Èý¡¢(6·Ö)дһ¸öÎÄ·¨Ê¹ÆäÓïÑÔΪL(G)={ anbmambn | m,n¡Ý1}¡£ ËÄ¡¢(8·Ö)¶ÔÓÚÎÄ·¨G(E):

E?T|E+T T?F|T*F F?(E)|i

1. д³ö¾äÐÍ(T*F+i)µÄ×îÓÒÍƵ¼²¢»­³öÓï·¨Ê÷¡£

2. д³öÉÏÊö¾äÐ͵ĶÌÓֱ½Ó¶ÌÓï¡¢¾ä±úºÍËضÌÓï¡£ Îå¡¢(12·Ö)ÉèÎÄ·¨G(S)£º

S?SiA|AA?A?B|BB?)A*|(

1£®¹¹Ôì¸÷·ÇÖÕ½á·ûµÄFIRSTVTºÍLASTVT¼¯ºÏ£»

2£®¹¹ÔìÓÅÏȹØϵ±íºÍÓÅÏȺ¯Êý¡£

Áù¡¢(9·Ö)ÉèijÓïÑÔµÄdo-whileÓï¾äµÄÓï·¨ÐÎʽΪ S ? do S(1) While E

ÆäÓïÒå½âÊÍΪ£º

Õë¶Ô×Ô϶øÉϵÄÓï·¨·ÖÎöÆ÷£¬°´ÈçÏÂÒªÇó¹¹Ôì¸ÃÓï¾äµÄ·­Òëģʽ£º (1) д³öÊʺÏÓï·¨ÖƵ¼·­ÒëµÄ²úÉúʽ£» (2) д³öÿ¸ö²úÉúʽ¶ÔÓ¦µÄÓïÒ嶯×÷¡£

Æß¡¢(8·Ö)½«Óï¾ä if (A0) then while C>0 do C:=C+D; ·­Òë³ÉËÄԪʽ¡£ °Ë¡¢(10·Ö) ÉèÓлù±¾¿éÈçÏ£º

T1:=S+R T2:= 3 T3:= 12/T2 T4:=S/R A:=T1-T4 T5:=S+R B:=T5

T6:=T5*T3 B:=T6

(1)»­³öDAGͼ£»

(2)ÉèA,BÊdzö»ù±¾¿éºóµÄ»îÔ¾±äÁ¿£¬Çë¸ø³öÓÅ»¯ºóµÄËÄԪʽÐòÁС£ ¾Å¡¢(9·Ö) ÉèÒѹ¹Ôì³öÎÄ·¨G(S)£º

(1) S ? BB (2) B ? aB (3) B? b

µÄLR·ÖÎö±íÈçÏÂ

S(1)µÄ´úÂë EµÄ´úÂë Õæ ¼Ù

״̬ 0 1 2 3 4 5 6 a s3 s6 s3 r3 s6 ACTION b s4 s7 s4 r3 s7 GOTO # acc r1 S 1 B 2 5 8 9 7 8 9 r2 r2 r3 r2

¼Ù¶¨ÊäÈ봮Ϊabab£¬Çë¸ø³öLR·ÖÎö¹ý³Ì(¼´°´ÕÕ²½Öè¸ø³ö״̬£¬·ûºÅ£¬ÊäÈë´®µÄ±ä»¯¹ý³Ì)¡£

£¨END£©

¡¶±àÒëÔ­Àí¡·¿¼ÊÔÊÔÌâ

£¨ËùÓд𰸱ØÐëдÔÚ´ðÌâÖ½ÉÏ£©

(2006.12.25)

Ò»¡¢»Ø´ðÏÂÁÐÎÊÌ⣺(30·Ö)

1£®Ê²Ã´ÊÇS-ÊôÐÔÎÄ·¨£¿Ê²Ã´ÊÇL-ÊôÐÔÎÄ·¨£¿ËüÃÇÖ®¼äÓÐʲô¹Øϵ£¿ ½â´ð£º

S-ÊôÐÔÎÄ·¨ÊÇÖ»º¬ÓÐ×ÛºÏÊôÐÔµÄÊôÐÔÎÄ·¨¡£ £¨2·Ö£©

L-ÊôÐÔÎÄ·¨ÒªÇó¶ÔÓÚÿ¸ö²úÉúʽA?X1X2¡­Xn£¬Æäÿ¸öÓïÒå¹æÔòÖеÄÿ¸öÊôÐÔ»òÕßÊÇ×ÛºÏÊôÐÔ£¬»òÕßÊÇXjµÄÒ»¸ö¼Ì³ÐÊôÐÔ£¬ÇÒ¸ÃÊôÐÔ½öÒÀÀµÓÚ£º

£¨1£© ²úÉúʽXjµÄ×ó±ß·ûºÅX1,X2¡­Xj-1µÄÊôÐÔ£»

£¨2£© AµÄ¼Ì³ÐÊôÐÔ¡£ £¨2·Ö£© S-ÊôÐÔÎÄ·¨ÊÇL-ÊôÐÔÎÄ·¨µÄÌØÀý¡£ £¨2·Ö£©

2£®Ê²Ã´ÊǾä±ú£¿Ê²Ã´ÊÇËضÌÓ

Ò»¸ö¾äÐ͵Ä×î×óÖ±½Ó¶ÌÓï³ÆΪ¸Ã¾äÐ͵ľä±ú¡££¨3·Ö£©ËضÌÓïÊÇÕâÑùµÄÒ»¸ö¶ÌÓËüÖÁÉÙ°üº¬Ò»¸öÖÕ½á·û²¢ÇÒ²»°üº¬¸üСµÄËضÌÓï¡££¨3·Ö£©

3£®»®·Ö³ÌÐòµÄ»ù±¾¿éʱ£¬È·¶¨»ù±¾¿éµÄÈë¿ÚÓï¾äµÄÌõ¼þÊÇʲô£¿ ½â´ð£º

£¨1£©³ÌÐòµÚÒ»¸öÓï¾ä£¬»ò

£¨2£©ÄÜÓÉÌõ¼þתÒÆÓï¾ä»òÎÞÌõ¼þתÒÆÓï¾äתÒƵ½µÄÓï¾ä£¬»ò £¨3£©½ô¸úÔÚÌõ¼þתÒÆÓï¾äºóÃæµÄÓï¾ä¡£

4£®(6·Ö)ÔËÐÐʱµÄDISPLAY±íµÄÄÚÈÝÊÇʲô£¿ËüµÄ×÷ÓÃÊÇʲô£¿

´ð£ºDISPLAY±íÊÇǶÌײã´ÎÏÔʾ±í¡£Ã¿µ±½øÈëÒ»¸ö¹ý³Ìºó£¬ÔÚ½¨Á¢ËüµÄ»î¶¯¼Ç¼ÇøµÄͬʱ½¨Á¢Ò»ÕÅǶÌײã´ÎÏÔʾ±ídiaplay.¼Ù¶¨ÏÖÔÚ½øÈëµÄ¹ý³Ì²ã´ÎΪi£¬ÔòËüµÄdiaplay±íº¬ÓÐi+1¸öµ¥Ôª£¬×Ô¶¥ÏòÏÂÿ¸öµ¥ÔªÒÀ´Î´æ·Å×ÅÏÖÐв㡢ֱ½ÓÍâ²ã¡¢¡­¡¢Ö±ÖÁ×îÍâ²ã(Ö÷³ÌÐò£¬0²ã)µÈÿ²ã¹ý³ÌµÄ×îл¼Ç¼µÄÆðʼµØÖ·¡£Í¨¹ýDISPLAY±í¿ÉÒÔ·ÃÎÊÆäÍâ²ã¹ý³ÌµÄ±äÁ¿¡£

5£®(6·Ö)¶ÔÏÂÁÐËÄԪʽÐòÁÐÉú³ÉÄ¿±ê´úÂ룺 A:=B*C D:=E+F G:=A+D H:=G*2

ÆäÖУ¬HÊÇ»ù±¾¿é³ö¿ÚµÄ»îÔ¾±äÁ¿£¬ R0ºÍR1ÊÇ¿ÉÓüĴæÆ÷ ´ð£º

LD R0£¬ B

MUL R0£¬ C LD R1£¬ E ADD R1£¬ F ADD R0£¬ R1 MUL R0£¬ 2 ST R0£¬ H

¶þ¡¢Éè?={0£¬1}ÉϵÄÕý¹æ¼¯SÓɵ¹ÊýµÚ¶þ¸ö×Ö·ûΪ1µÄËùÓÐ×Ö·û´®×é³É£¬Çë¸ø³ö¸Ã×Ö¼¯¶ÔÓ¦µÄÕý¹æʽ£¬²¢¹¹ÔìÒ»¸öʶ±ð¸ÃÕý¹æ¼¯µÄDFA¡£(8·Ö)

´ð£º

¹¹ÔìÏàÓ¦µÄÕý¹æʽ£º(0|1)*1(0|1) (3·Ö) NFA: (2·Ö)

1 1

? ? ? ? 1 0 1 2 3 4

0 0 È·¶¨»¯£º(3·Ö) I I0 I1 {0,1,2} {1,2} {1,2,3} {1,2,4} {1,2,3,4} {1,2} {1,2} {1,2,4} {1,2} {1,2,4} {1,2,3} {1,2,3} {1,2,3,4} {1,2,3} {1,2,3,4}

0

1 0 1 0 0 0 1 2 3 4

0 1 1 1

Èý¡¢Ð´Ò»¸öÎÄ·¨Ê¹ÆäÓïÑÔΪL(G)={ anbmambn | m,n¡Ý1}¡£(6·Ö)

´ð£ºÎÄ·¨G(S):

S ? aSb | B B ? bBa | ba

ËÄ¡¢¶ÔÓÚÎÄ·¨G(E): (8·Ö)

E?T|E+T

T?F|T*F F?(E)|i

1. д³ö¾äÐÍ(T*F+i)µÄ×îÓÒÍƵ¼²¢»­³öÓï·¨Ê÷¡£

2. д³öÉÏÊö¾äÐ͵ĶÌÓֱ½Ó¶ÌÓï¡¢¾ä±úºÍËضÌÓï¡£

´ð£º 1. (4·Ö)

E?T?F?(E) ?(E+T) ?(E+F) ?(E+i) ?(T+i) ?(T*F+i)

2. (4·Ö)

¶ÌÓ(T*F+i), T*F+i, T*F, i Ö±½Ó¶ÌÓT*F, i ¾ä±ú£ºT*F ËضÌÓT*F, i

Îå¡¢ÉèÎÄ·¨G(S)£º(12·Ö)

S?SiA|AA?A?B|BB?)A*|(E T F ( E ) E + T T F T * F i

3£®¹¹Ôì¸÷·ÇÖÕ½á·ûµÄFIRSTVTºÍLASTVT¼¯ºÏ£» 4£®¹¹ÔìÓÅÏȹØϵ±íºÍÓÅÏȺ¯Êý¡£(12·Ö) ´ð£º(6·Ö)

FIRSTVT(S)={ i£¬+£¬)£¬( } FIRSTVT(A)={ +£¬)£¬( } FIRSTVT(B)={ )£¬( }

LASTVT(S)={ i£¬+£¬*£¬( } LASTVT(A)={ +£¬*£¬( } LASTVT(B)={ *£¬( }

ÓÅÏȹØϵ±í: (3·Ö) i + ( ) i > < < < + > > < < ( > > ) < < < * > > ÓÅÏȺ¯Êý: (3·Ö)

* > > > f g i 2 1 + 6 4 ( 6 6 ) 1 6 * 6 1 Áù¡¢ÉèijÓïÑÔµÄdo-whileÓï¾äµÄÓï·¨ÐÎʽΪ (9·Ö) S ? do S(1) While E

ÆäÓïÒå½âÊÍΪ£º

Õë¶Ô×Ô϶øÉϵÄÓï·¨·ÖÎöÆ÷£¬°´ÈçÏÂÒªÇó¹¹Ôì¸ÃÓï¾äµÄ·­Òëģʽ£º (1) д³öÊʺÏÓï·¨ÖƵ¼·­ÒëµÄ²úÉúʽ£» (2) д³öÿ¸ö²úÉúʽ¶ÔÓ¦µÄÓïÒ嶯×÷¡£ ´ð£º(1). ÊʺÏÓï·¨ÖƵ¼·­ÒëµÄÎÄ·¨(3·Ö) G(S): R? do

U?R S(1) While S?U E (2). (6·Ö) R? do

{ R.QUAD:=NXQ }

U?R S(1) While { U.QUAD:=R.QUAD;

BACKPATCH(S.CHAIN, NXQ) }

S?U E

{ BACKPATCH(E.TC, U.QUAD); S.CHAIN:=E.FC }

´ð°¸¶þ£º

(1) S ? do M1 S(1) While M2 E

M ?¦Å (3·Ö)

(2) M ?¦Å { M.QUAD := NXQ } (6·Ö)

EµÄ´úÂë ¼Ù

S(1)µÄ´úÂë Õæ

S ? do M1 S(1) While M2 E {

BACKPATCH(S(1).CHAIN, M2.QUAD); BACKPATCH(E.TC, M1.QUAD);

S.CHAIN:=E. FC

Æß¡¢(8·Ö)½«Óï¾ä

if (A0) then while C>0 do C:=C+D ·­Òë³ÉËÄԪʽ¡£(8·Ö) ´ð£º

100 (j<£¬ A£¬ X£¬ 102) 101 (j£¬ -£¬ -£¬ 109) 102 (j>£¬ B£¬ 0£¬ 104) 103 (j£¬ -£¬ -£¬ 109) 104 (j>£¬ C£¬ 0£¬ 106) 105 (j£¬ -£¬ -£¬ 109) 106 (+£¬ C£¬ D£¬ T1) 107 (:=£¬ T1£¬ -£¬ C) 108 (j£¬ -£¬ -£¬ 104) 109

(¿ØÖƽṹ3·Ö£¬ÆäËû5·Ö)

°Ë¡¢(10·Ö) ÉèÓлù±¾¿éÈçÏ£º

}

T1:=S+R T2:= 3 T3:= 12/T2 T4:=S/R A:=T1-T4 T5:=S+R B:=T5

T6:=T5*T3 B:=T6

(1)»­³öDAGͼ£»

(2)ÉèA,BÊdzö»ù±¾¿éºóµÄ»îÔ¾±äÁ¿£¬Çë¸ø³öÓÅ»¯ºóµÄËÄԪʽÐòÁС£

´ð£º(1) DAGÈçÓÒͼ£º(6·Ö) n7 A n8 T6,B

_ *

n3 T1,T5, B n6 T4 + n1 S / n2 R n4 T2 3 n5 4 T3

(2) ËÄԪʽÐòÁУº(4·Ö) T1:=S+R T4:=S/R A:=T1-T4 B:=T1*4

¾Å¡¢(9·Ö) ÉèÒѹ¹Ôì³öÎÄ·¨G(S)£º

(1) S ? BB (2) B ? aB (3) B? b

µÄLR·ÖÎö±íÈçÏÂ

״̬ 0 1 2 3 4 5 6 7 8 9 a s3 s6 s3 r3 s6 r2 ACTION b s4 s7 s4 r3 s7 r2 # acc r1 r3 r2 S 1 GOTO B 2 5 8 9

¼Ù¶¨ÊäÈ봮Ϊabab£¬Çë¸ø³öLR·ÖÎö¹ý³Ì(¼´°´ÕÕ²½Öè¸ø³ö״̬£¬·ûºÅ£¬ÊäÈë´®µÄ±ä»¯¹ý³Ì)¡£ ´ð£º

²½Öè ״̬ ·ûºÅ ÊäÈë´® 0 0 # abab# 1 03 #a bab# 2 034 #ab ab# 3 038 #aB ab# 4 02 #B ab# 5 026 #Ba b# 6 0267 #Bab # 7 0269 #BaB #

8 9

025 01 #BB #S # #

acc

¡¶±àÒëÔ­Àí¡·¿¼ÊÔÊÔÌâ

£¨ËùÓд𰸱ØÐëдÔÚ´ðÌâÖ½ÉÏ£©

(2006.12.25)

Ò»¡¢(5¡Á6·Ö)»Ø´ðÏÂÁÐÎÊÌ⣺

1£®Ê²Ã´ÊÇS-ÊôÐÔÎÄ·¨£¿Ê²Ã´ÊÇL-ÊôÐÔÎÄ·¨£¿ËüÃÇÖ®¼äÓÐʲô¹Øϵ£¿ 2£®Ê²Ã´ÊǾä±ú£¿Ê²Ã´ÊÇËضÌÓ

3£®»®·Ö³ÌÐòµÄ»ù±¾¿éʱ£¬È·¶¨»ù±¾¿éµÄÈë¿ÚÓï¾äµÄÌõ¼þÊÇʲô£¿ 4£®ÔËÐÐʱµÄDISPLAY±íµÄÄÚÈÝÊÇʲô£¿ËüµÄ×÷ÓÃÊÇʲô£¿ 5£®¶ÔÏÂÁÐËÄԪʽÐòÁÐÉú³ÉÄ¿±ê´úÂ룺

A:=B*C D:=E+F G:=A+D H:=G*2

ÆäÖУ¬HÊÇ»ù±¾¿é³ö¿ÚµÄ»îÔ¾±äÁ¿£¬ R0ºÍR1ÊÇ¿ÉÓüĴæÆ÷

¶þ¡¢(8·Ö)Éè?={0£¬1}ÉϵÄÕý¹æ¼¯SÓɵ¹ÊýµÚ¶þ¸ö×Ö·ûΪ1µÄËùÓÐ×Ö·û´®×é³É£¬Çë¸ø³ö¸Ã×Ö¼¯¶ÔÓ¦µÄÕý¹æʽ£¬²¢¹¹ÔìÒ»¸öʶ±ð¸ÃÕý¹æ¼¯µÄDFA¡£ Èý¡¢(6·Ö)дһ¸öÎÄ·¨Ê¹ÆäÓïÑÔΪL(G)={ anbmambn | m,n¡Ý1}¡£ ËÄ¡¢(8·Ö)¶ÔÓÚÎÄ·¨G(E):

E?T|E+T T?F|T*F F?(E)|i

1. д³ö¾äÐÍ(T*F+i)µÄ×îÓÒÍƵ¼²¢»­³öÓï·¨Ê÷¡£

2. д³öÉÏÊö¾äÐ͵ĶÌÓֱ½Ó¶ÌÓï¡¢¾ä±úºÍËضÌÓï¡£ Îå¡¢(12·Ö)ÉèÎÄ·¨G(S)£º

S?SiA|AA?A?B|BB?)A*|(

5£®¹¹Ôì¸÷·ÇÖÕ½á·ûµÄFIRSTVTºÍLASTVT¼¯ºÏ£» 6£®¹¹ÔìÓÅÏȹØϵ±íºÍÓÅÏȺ¯Êý¡£

Áù¡¢(9·Ö)ÉèijÓïÑÔµÄdo-whileÓï¾äµÄÓï·¨ÐÎʽΪ S ? do S(1) While E

ÆäÓïÒå½âÊÍΪ£º

Õë¶Ô×Ô϶øÉϵÄÓï·¨·ÖÎöÆ÷£¬°´ÈçÏÂÒªÇó¹¹Ôì¸ÃÓï¾äµÄ·­Òëģʽ£º (1) д³öÊʺÏÓï·¨ÖƵ¼·­ÒëµÄ²úÉúʽ£» (2) д³öÿ¸ö²úÉúʽ¶ÔÓ¦µÄÓïÒ嶯×÷¡£

Æß¡¢(8·Ö)½«Óï¾ä if (A0) then while C>0 do C:=C+D; ·­Òë³ÉËÄԪʽ¡£ °Ë¡¢(10·Ö) ÉèÓлù±¾¿éÈçÏ£º

T1:=S+R T2:= 3 T3:= 12/T2 T4:=S/R A:=T1-T4 T5:=S+R B:=T5

T6:=T5*T3 B:=T6

(1)»­³öDAGͼ£»

(2)ÉèA,BÊdzö»ù±¾¿éºóµÄ»îÔ¾±äÁ¿£¬Çë¸ø³öÓÅ»¯ºóµÄËÄԪʽÐòÁС£ ¾Å¡¢(9·Ö) ÉèÒѹ¹Ôì³öÎÄ·¨G(S)£º

(1) S ? BB (2) B ? aB (3) B? b

µÄLR·ÖÎö±íÈçÏÂ

S(1)µÄ´úÂë EµÄ´úÂë Õæ ¼Ù

״̬ 0 1 2 3 4 5 6 7 8 9

a s3 s6 s3 r3 s6 r2 ACTION b s4 s7 s4 r3 s7 r2 GOTO # acc r1 r3 r2 S 1 B 2 5 8 9 ¼Ù¶¨ÊäÈ봮Ϊabab£¬Çë¸ø³öLR·ÖÎö¹ý³Ì(¼´°´ÕÕ²½Öè¸ø³ö״̬£¬·ûºÅ£¬ÊäÈë´®µÄ±ä»¯¹ý³Ì)¡£

£¨END£©

¡¶±àÒëÔ­Àí¡·¿¼ÊÔÊÔÌâ

£¨ËùÓд𰸱ØÐëдÔÚ´ðÌâÖ½ÉÏ£©

(2006.12.25)

¶þ¡¢»Ø´ðÏÂÁÐÎÊÌ⣺(30·Ö)

1£®Ê²Ã´ÊÇS-ÊôÐÔÎÄ·¨£¿Ê²Ã´ÊÇL-ÊôÐÔÎÄ·¨£¿ËüÃÇÖ®¼äÓÐʲô¹Øϵ£¿ ½â´ð£º

S-ÊôÐÔÎÄ·¨ÊÇÖ»º¬ÓÐ×ÛºÏÊôÐÔµÄÊôÐÔÎÄ·¨¡£ £¨2·Ö£©

L-ÊôÐÔÎÄ·¨ÒªÇó¶ÔÓÚÿ¸ö²úÉúʽA?X1X2¡­Xn£¬Æäÿ¸öÓïÒå¹æÔòÖеÄÿ¸öÊôÐÔ»òÕßÊÇ×ÛºÏÊôÐÔ£¬»òÕßÊÇXjµÄÒ»¸ö¼Ì³ÐÊôÐÔ£¬ÇÒ¸ÃÊôÐÔ½öÒÀÀµÓÚ£º

£¨3£© ²úÉúʽXjµÄ×ó±ß·ûºÅX1,X2¡­Xj-1µÄÊôÐÔ£»

£¨4£© AµÄ¼Ì³ÐÊôÐÔ¡£ £¨2·Ö£© S-ÊôÐÔÎÄ·¨ÊÇL-ÊôÐÔÎÄ·¨µÄÌØÀý¡£ £¨2·Ö£©

2£®Ê²Ã´ÊǾä±ú£¿Ê²Ã´ÊÇËضÌÓ

Ò»¸ö¾äÐ͵Ä×î×óÖ±½Ó¶ÌÓï³ÆΪ¸Ã¾äÐ͵ľä±ú¡££¨3·Ö£©ËضÌÓïÊÇÕâÑùµÄÒ»¸ö¶ÌÓËüÖÁÉÙ°üº¬Ò»¸öÖÕ½á·û²¢ÇÒ²»°üº¬¸üСµÄËضÌÓï¡££¨3·Ö£©

3£®»®·Ö³ÌÐòµÄ»ù±¾¿éʱ£¬È·¶¨»ù±¾¿éµÄÈë¿ÚÓï¾äµÄÌõ¼þÊÇʲô£¿ ½â´ð£º

£¨1£©³ÌÐòµÚÒ»¸öÓï¾ä£¬»ò

£¨2£©ÄÜÓÉÌõ¼þתÒÆÓï¾ä»òÎÞÌõ¼þתÒÆÓï¾äתÒƵ½µÄÓï¾ä£¬»ò £¨3£©½ô¸úÔÚÌõ¼þתÒÆÓï¾äºóÃæµÄÓï¾ä¡£

4£®(6·Ö)ÔËÐÐʱµÄDISPLAY±íµÄÄÚÈÝÊÇʲô£¿ËüµÄ×÷ÓÃÊÇʲô£¿

´ð£ºDISPLAY±íÊÇǶÌײã´ÎÏÔʾ±í¡£Ã¿µ±½øÈëÒ»¸ö¹ý³Ìºó£¬ÔÚ½¨Á¢ËüµÄ»î¶¯¼Ç¼ÇøµÄͬʱ½¨Á¢Ò»ÕÅǶÌײã´ÎÏÔʾ±ídiaplay.¼Ù¶¨ÏÖÔÚ½øÈëµÄ¹ý³Ì²ã´ÎΪi£¬ÔòËüµÄdiaplay±íº¬ÓÐi+1¸öµ¥Ôª£¬×Ô¶¥ÏòÏÂÿ¸öµ¥ÔªÒÀ´Î´æ·Å×ÅÏÖÐв㡢ֱ½ÓÍâ²ã¡¢¡­¡¢Ö±ÖÁ×îÍâ²ã(Ö÷³ÌÐò£¬0²ã)µÈÿ²ã¹ý³ÌµÄ×îл¼Ç¼µÄÆðʼµØÖ·¡£Í¨¹ýDISPLAY±í¿ÉÒÔ·ÃÎÊÆäÍâ²ã¹ý³ÌµÄ±äÁ¿¡£

5£®(6·Ö)¶ÔÏÂÁÐËÄԪʽÐòÁÐÉú³ÉÄ¿±ê´úÂ룺 A:=B*C D:=E+F G:=A+D H:=G*2

ÆäÖУ¬HÊÇ»ù±¾¿é³ö¿ÚµÄ»îÔ¾±äÁ¿£¬ R0ºÍR1ÊÇ¿ÉÓüĴæÆ÷ ´ð£º

LD R0£¬ B

MUL R0£¬ C LD R1£¬ E ADD R1£¬ F ADD R0£¬ R1 MUL R0£¬ 2 ST R0£¬ H

¶þ¡¢Éè?={0£¬1}ÉϵÄÕý¹æ¼¯SÓɵ¹ÊýµÚ¶þ¸ö×Ö·ûΪ1µÄËùÓÐ×Ö·û´®×é³É£¬Çë¸ø³ö¸Ã×Ö¼¯¶ÔÓ¦µÄÕý¹æʽ£¬²¢¹¹ÔìÒ»¸öʶ±ð¸ÃÕý¹æ¼¯µÄDFA¡£(8·Ö)

´ð£º

¹¹ÔìÏàÓ¦µÄÕý¹æʽ£º(0|1)*1(0|1) (3·Ö) NFA: (2·Ö)

1 1

? ? ? ? 1 0 1 2 3 4

0 0 È·¶¨»¯£º(3·Ö) I I0 I1 {0,1,2} {1,2} {1,2,3} {1,2,4} {1,2,3,4} {1,2} {1,2} {1,2,4} {1,2} {1,2,4} {1,2,3} {1,2,3} {1,2,3,4} {1,2,3} {1,2,3,4}

0

1 0 1 0 0 0 1 2 3 4

0 1 1 1

Èý¡¢Ð´Ò»¸öÎÄ·¨Ê¹ÆäÓïÑÔΪL(G)={ anbmambn | m,n¡Ý1}¡£(6·Ö)

´ð£ºÎÄ·¨G(S):

S ? aSb | B B ? bBa | ba

ËÄ¡¢¶ÔÓÚÎÄ·¨G(E): (8·Ö)

E?T|E+T

T?F|T*F F?(E)|i

1. д³ö¾äÐÍ(T*F+i)µÄ×îÓÒÍƵ¼²¢»­³öÓï·¨Ê÷¡£

2. д³öÉÏÊö¾äÐ͵ĶÌÓֱ½Ó¶ÌÓï¡¢¾ä±úºÍËضÌÓï¡£

´ð£º 1. (4·Ö)

E?T?F?(E) ?(E+T) ?(E+F) ?(E+i) ?(T+i) ?(T*F+i)

2. (4·Ö)

¶ÌÓ(T*F+i), T*F+i, T*F, i Ö±½Ó¶ÌÓT*F, i ¾ä±ú£ºT*F ËضÌÓT*F, i

Îå¡¢ÉèÎÄ·¨G(S)£º(12·Ö)

S?SiA|AA?A?B|BB?)A*|(E T F ( E ) E + T T F T * F i

7£®¹¹Ôì¸÷·ÇÖÕ½á·ûµÄFIRSTVTºÍLASTVT¼¯ºÏ£» 8£®¹¹ÔìÓÅÏȹØϵ±íºÍÓÅÏȺ¯Êý¡£(12·Ö) ´ð£º(6·Ö)

FIRSTVT(S)={ i£¬+£¬)£¬( } FIRSTVT(A)={ +£¬)£¬( } FIRSTVT(B)={ )£¬( }

LASTVT(S)={ i£¬+£¬*£¬( } LASTVT(A)={ +£¬*£¬( } LASTVT(B)={ *£¬( }

ÓÅÏȹØϵ±í: (3·Ö) i + ( ) i > < < < + > > < < ( > > ) < < < * > > ÓÅÏȺ¯Êý: (3·Ö)

* > > > f g i 2 1 + 6 4 ( 6 6 ) 1 6 * 6 1 Áù¡¢ÉèijÓïÑÔµÄdo-whileÓï¾äµÄÓï·¨ÐÎʽΪ (9·Ö) S ? do S(1) While E

ÆäÓïÒå½âÊÍΪ£º

Õë¶Ô×Ô϶øÉϵÄÓï·¨·ÖÎöÆ÷£¬°´ÈçÏÂÒªÇó¹¹Ôì¸ÃÓï¾äµÄ·­Òëģʽ£º (1) д³öÊʺÏÓï·¨ÖƵ¼·­ÒëµÄ²úÉúʽ£» (2) д³öÿ¸ö²úÉúʽ¶ÔÓ¦µÄÓïÒ嶯×÷¡£ ´ð£º(1). ÊʺÏÓï·¨ÖƵ¼·­ÒëµÄÎÄ·¨(3·Ö) G(S): R? do

U?R S(1) While S?U E (2). (6·Ö) R? do

{ R.QUAD:=NXQ }

U?R S(1) While { U.QUAD:=R.QUAD;

BACKPATCH(S.CHAIN, NXQ) }

S?U E

{ BACKPATCH(E.TC, U.QUAD); S.CHAIN:=E.FC }

´ð°¸¶þ£º

(1) S ? do M1 S(1) While M2 E

M ?¦Å (3·Ö)

(2) M ?¦Å { M.QUAD := NXQ } (6·Ö)

EµÄ´úÂë ¼Ù

S(1)µÄ´úÂë Õæ

S ? do M1 S(1) While M2 E {

BACKPATCH(S(1).CHAIN, M2.QUAD); BACKPATCH(E.TC, M1.QUAD);

S.CHAIN:=E. FC

Æß¡¢(8·Ö)½«Óï¾ä

if (A0) then while C>0 do C:=C+D ·­Òë³ÉËÄԪʽ¡£(8·Ö) ´ð£º

100 (j<£¬ A£¬ X£¬ 102) 101 (j£¬ -£¬ -£¬ 109) 102 (j>£¬ B£¬ 0£¬ 104) 103 (j£¬ -£¬ -£¬ 109) 104 (j>£¬ C£¬ 0£¬ 106) 105 (j£¬ -£¬ -£¬ 109) 106 (+£¬ C£¬ D£¬ T1) 107 (:=£¬ T1£¬ -£¬ C) 108 (j£¬ -£¬ -£¬ 104) 109

(¿ØÖƽṹ3·Ö£¬ÆäËû5·Ö)

°Ë¡¢(10·Ö) ÉèÓлù±¾¿éÈçÏ£º

}

T1:=S+R T2:= 3 T3:= 12/T2 T4:=S/R A:=T1-T4 T5:=S+R B:=T5

T6:=T5*T3 B:=T6

(1)»­³öDAGͼ£»

(2)ÉèA,BÊdzö»ù±¾¿éºóµÄ»îÔ¾±äÁ¿£¬Çë¸ø³öÓÅ»¯ºóµÄËÄԪʽÐòÁС£

´ð£º(1) DAGÈçÓÒͼ£º(6·Ö) n7 A n8 T6,B

_ *

n3 T1,T5, B n6 T4 + n1 S / n2 R n4 T2 3 n5 4 T3

(2) ËÄԪʽÐòÁУº(4·Ö) T1:=S+R T4:=S/R A:=T1-T4 B:=T1*4

¾Å¡¢(9·Ö) ÉèÒѹ¹Ôì³öÎÄ·¨G(S)£º

(4) S ? BB (5) B ? aB (6) B? b

µÄLR·ÖÎö±íÈçÏÂ

״̬ 0 1 2 3 4 5 6 7 8 9 a s3 s6 s3 r3 s6 r2 ACTION b s4 s7 s4 r3 s7 r2 # acc r1 r3 r2 S 1 GOTO B 2 5 8 9

¼Ù¶¨ÊäÈ봮Ϊabab£¬Çë¸ø³öLR·ÖÎö¹ý³Ì(¼´°´ÕÕ²½Öè¸ø³ö״̬£¬·ûºÅ£¬ÊäÈë´®µÄ±ä»¯¹ý³Ì)¡£ ´ð£º

²½Öè ״̬ ·ûºÅ ÊäÈë´® 0 0 # abab# 1 03 #a bab# 2 034 #ab ab# 3 038 #aB ab# 4 02 #B ab# 5 026 #Ba b# 6 0267 #Bab # 7 0269 #BaB #

8 9

025 01 #BB #S # #

acc