Next: , Up: Concepts   [Contents][Index]


1.1 ¸À¸ì¤Èʸ̮¼«Í³Ê¸Ë¡

Bison¤¬¸À¸ì¤ò²òÀϤ¹¤ë¤¿¤á¤Ë¤Ï¡¢¤½¤Î¸À¸ì¤¬ ʸ̮¼«Í³Ê¸Ë¡¡Êcontext-free grammar¡Ë¤Çµ­½Ò¤µ¤ì¤Æ¤¤¤ëɬÍפ¬¤¢¤ê¤Þ¤¹¡£ ¤¹¤Ê¤ï¤Á¡¢1¸Ä°Ê¾å¤Îʸˡ¥°¥ë¡¼¥×¡Êsyntactic groupings¡Ë¤òÄê¤á¡¢ ¤½¤Îʸˡ¥°¥ë¡¼¥×¤òÉôÉʤ«¤éÁȤßΩ¤Æ¤ëµ¬Â§¤òÍ¿¤¨¤ëɬÍפ¬¤¢¤ê¤Þ¤¹¡£ ¤¿¤È¤¨¤Ð¡¢C¸À¸ì¤Ç¤Ï¡¢¤¢¤ë¼ï¤Î¥°¥ë¡¼¥×¤Ï¡Ö¼°¡×¤È¸Æ¤Ð¤ì¤Þ¤¹¡£ ¼°¤òºî¤ëµ¬Â§¤Î1¤Ä¤Ï¡¢ ¡Ö1¤Ä¤Î¼°¤È¤Ï¡¢Ê̤μ°¤Ë¥Þ¥¤¥Ê¥¹µ­¹æ¤òÉÕ¤±¤¿¤â¤Î¤Ç¤â¤è¤¤¡×¤«¤â¤·¤ì¤Þ¤»¤ó¡£ Ê̤ε¬Â§¤Ï¡¢¡Ö1¤Ä¤Î¼°¤È¤Ï¡¢À°¿ô¤Ç¤â¤è¤¤¡×¤«¤â¤·¤ì¤Þ¤»¤ó¡£ ¤³¤³¤«¤é²ò¤ë¤è¤¦¤Ë¡¢µ¬Â§¤Ï¤·¤Ð¤·¤ÐºÆµ¢Åª¤Ë¤Ê¤ê¤Þ¤¹¤¬¡¢ ºÆµ¢¤ò»Ï¤á¤ë¤¿¤á¤Î¾¯¤Ê¤¯¤È¤â1¸Ä¤Îµ¬Â§¤¬É¬ÍפǤ¹¡£

¤³¤Î¤è¤¦¤Êµ¬Â§¤ò¿Í´Ö¤¬ÆÉ¤á¤ë¤è¤¦¤Ëɽ¸½¤¹¤ë¡¢¤â¤Ã¤È¤â°ìÈÌŪ¤Ê·Á¼°Åª¤ÊÊýË¡¤Ï¡¢ ¥Ð¥Ã¥«¥¹-¥Ê¥¦¥¢µ­Ë¡¡ÊBackus-Naur form¡Ëά¤·¤Æ“BNF”¤Ç¤¹¡£ ¤³¤ì¤Ï¡¢Algol 60¸À¸ì¤òÄêµÁ¤¹¤ë¤¿¤á¤Ë³«È¯¤µ¤ì¤Þ¤·¤¿¡£ BNF¤Çɽ¸½¤µ¤ì¤¿Ç¤°Õ¤Î¸À¸ì¤Ï¡¢Ê¸Ì®¼«Í³¸À¸ì¤Ç¤¹¡£ Bison¤Ø¤ÎÆþÎϤϡ¢ËܼÁŪ¤Ë¤Ï¡¢µ¡³£²ÄÆÉ¤ÊBNF¤Ç¤¹¡£

¤¹¤Ù¤Æ¤Îʸ̮¼«Í³¸À¸ì¤òBison¤Ç°·¤¨¤ë¤ï¤±¤Ç¤Ï¤¢¤ê¤Þ¤»¤ó¡£ LALR(1)¤À¤±¤ò°·¤¨¤Þ¤¹¡£ ´Êñ¤ËÀâÌÀ¤¹¤ë¤È¡¢¤Á¤ç¤¦¤É1¸Ä¤Î¥È¡¼¥¯¥ó¤òÀèÆÉ¤ß¤¹¤ë¤³¤È¤Ë¤è¤Ã¤Æ¡¢ ÆþÎÏʸ»úÎó¤ÎǤ°Õ¤ÎÉôʬ¤ò²òÀϤǤ­¤ëɬÍפ¬¤¢¤ë¤È¤¤¤¦¤³¤È¤Ç¤¹¡£ ¸·Ì©¤ËÀâÌÀ¤¹¤ë¤È¡¢¤³¤ì¤ÏLR(1)ʸˡ¤ÎÀâÌÀ¤Ç¡¢ LALR(1)¤Ë¤Ï´Êñ¤ËÀâÌÀ¤Ç¤­¤Ê¤¤ÄɲäÎÀ©¸Â¤¬¤¢¤ê¤Þ¤¹¡£ ¤·¤«¤·¡¢LALR(1)¤Ë¤Ê¤ì¤Ê¤¤LR(1)ʸˡ¤Ï¡¢¸½¼Â¤Ë¤Ï¤Þ¤ì¤Ç¤¹¡£ ¤è¤ê¾Ü¤·¤¤ÀâÌÀ¤Ï See Mysterious Reduce/Reduce Conflicts¡£

¤¢¤ë¸À¸ì¤Ë¤Ä¤¤¤Æ¤Î·Á¼°Ê¸Ë¡Åª¤Êµ¬Â§¤Ç¤Ï¡¢ ʸˡŪ¤Êñ°Ì¤Þ¤¿¤Ï¥°¥ë¡¼¥×¤òµ­¹æ¡Êsymbol¡Ë¤È¸Æ¤Ó¤Þ¤¹¡£ ʸˡµ¬Â§¤Ë½¾¤Ã¤Æ¾®¤µ¤¤Éôʬ¤«¤éÁȤßΩ¤Æ¤é¤ì¤¿µ­¹æ¤ò Èó½ªÃ¼µ­¹æ¡Ênonterminal symbol¡Ë¤È¤¤¤¤¡¢ ½ªÃ¼µ­¹æ¡Êterminal symbol¡Ë¤Þ¤¿¤Ï¥È¡¼¥¯¥ó·¿¡Êtoken type¡Ë¤È¸Æ¤Ð¤ì¤ë ¤â¤Î¤Ëʬ²ò¤Ç¤­¤Þ¤¹¡£ Ëܽñ¤Ç¤Ï¡¢1¸Ä¤Î½ªÃ¼µ­¹æ¤ËÂбþ¤¹¤ëÆþÎϤΰìÉôʬ¤ò¥È¡¼¥¯¥ó¡Êtoken¡Ë¡¢ 1¸Ä¤ÎÈó½ªÃ¼µ­¹æ¤ËÂбþ¤¹¤ëÆþÎϤΰìÉôʬ¤ò¥°¥ë¡¼¥×¡Êgrouping¡Ë¤È¸Æ¤Ó¤Þ¤¹¡£

²¿¤¬½ªÃ¼µ­¹æ¤Ç²¿¤¬Èó½ªÃ¼µ­¹æ¤«¤ò¼¨¤¹¤¿¤á¤Ë¡¢ Îã¤È¤·¤ÆC¸À¸ì¤ò»È¤¤¤Þ¤¹¡£ C¤Î¥È¡¼¥¯¥ó¤Ï¡¢¼±Ê̻ҡ¢Äê¿ô¡Ê¿ôÃͤޤ¿¤Ïʸ»úÎó¡Ë¡¢¤µ¤Þ¤¶¤Þ¤ÊͽÌó¸ì¡¢ »»½Ñ±é»»»Ò¡¢¶èÀڤ국¹æ¤Ç¤¹¡£ C¸À¸ì¤Î½ªÃ¼µ­¹æ¤Ë¤Ï¡¢¡Ö¼±Ê̻ҡס¢¡Ö¿ôÃ͡ס¢¡Öʸ»úÎó¡×¡¢¤½¤·¤Æ¡¢ ͽÌó¸ì¡¢±é»»»Ò¡¢¶èÀڤ국¹æ¤Î¤½¤ì¤¾¤ì¤ËÂФ¹¤ëµ­¹æ¡¢ ¤¹¤Ê¤ï¤Á¡¢¡Öif¡×¡¢¡Öreturn¡×¡¢¡Öconst¡×¡¢¡Östatic¡×¡¢¡Öint¡×¡¢¡Öchar¡×¡¢ ¡Ö¥×¥é¥¹µ­¹æ¡×¡¢¡Ö³«¤­¥Ö¥ì¡¼¥¹¡×¡¢¡ÖÊĤ¸¥Ö¥ì¡¼¥¹¡×¡¢¡Ö¥«¥ó¥Þ¡×¡¢ ¤Ê¤É¤¬´Þ¤Þ¤ì¤Þ¤¹ ¡Ê¤³¤ì¤é¤Î¥È¡¼¥¯¥ó¤Ïʸ»ú¤Ëʬ²ò¤Ç¤­¤Þ¤¹¤¬¡¢ ¤½¤ì¤Ïʸˡ¤ÎÌäÂê¤Ç¤Ï¤Ê¤¯¡¢»ú¶ç²òÀϤÎÌäÂê¤Ç¤¹¡Ë¡£

¼¡¤ÎÎã¤Ï¡¢¥È¡¼¥¯¥ó¤Ëʬ²ò¤µ¤ì¤¿C¤Î´Ø¿ô¤Ç¤¹¡£

int             /* ͽÌó¸ì ‘int’ */
square (x)      /* ¼±ÊÌ»Ò, ³«¤­¤«¤Ã¤³, */
                /* ¼±ÊÌ»Ò, ÊĤ¸¤«¤Ã¤³ */
     int x;     /* ͽÌó¸ì ‘int’, ¼±ÊÌ»Ò, ¥»¥ß¥³¥í¥ó */
{               /* ³«¤­¥Ö¥ì¡¼¥¹ */
  return x * x; /* ͽÌó¸ì ‘return’, ¼±ÊÌ»Ò, */
                /* ¥¢¥¹¥¿¥ê¥¹¥¯, ¼±ÊÌ»Ò, ¥»¥ß¥³¥í¥ó */
}               /* ÊĤ¸¥Ö¥ì¡¼¥¹ */

C¤ÎʸˡŪ¤Ê¥°¥ë¡¼¥×¤Ë¤Ï¡¢¼°¡¢Ê¸¡¢Àë¸À¡¢´Ø¿ôÄêµÁ¤¬´Þ¤Þ¤ì¤Þ¤¹¡£ ¤³¤ì¤é¤Ï¡¢C¤Îʸˡ¤Ç¡¢Èó½ªÃ¼µ­¹æ¡¢¡Ö¼°¡×¡¢¡Öʸ¡×¡¢¡ÖÀë¸À¡×¡¢ ¡Ö´Ø¿ôÄêµÁ¡×¤È¤·¤ÆÉ½¤µ¤ì¤Þ¤¹¡£ ´°Á´¤Êʸˡ¤Ç¤Ï¡¢¾åµ­¤Î4¤Ä¤Î°ÕÌ£¤òɽ¸½¤¹¤ë¤¿¤á¤Ë¡¢ ¤½¤ì¤¾¤ì¤ÎÈó½ªÃ¼µ­¹æ¤Ë¤Ä¤¤¤Æ¡¢¿ô½½¸Ä¤ÎÄɲäθÀ¸ì¹½ÃÛ¤¬É¬ÍפǤ¹¡£ ¾åµ­¤ÎÎã¤Ç¡¢´Ø¿ôÄêµÁ¤Ï¡¢Àë¸À¤Èʸ¤ò´Þ¤ß¤Þ¤¹¡£ ʸ¤ÎÃæ¤Ç¡¢¤½¤ì¤¾¤ì¤Î‘x’¤Ï¼°¤Ç¤¢¤ê¡¢ ‘x * x’¤â¼°¤Ç¤¹¡£

¤½¤ì¤¾¤ì¤ÎÈó½ªÃ¼µ­¹æ¤Ë¤Ï¡¢¤½¤ì¤¬¤è¤êñ½ã¤Ê¹½À®Í×ÁǤ«¤é¤É¤Î¤è¤¦¤Ëºî¤é¤ì¤ë¤« ¼¨¤¹¤¿¤á¤Ë¡¢Ê¸Ë¡µ¬Â§¤¬É¬ÍפǤ¹¡£ ¤¿¤È¤¨¤Ð¡¢C¤Îʸ¤Î1¤Ä¤Ç¤¢¤ëreturnʸ¤Ë¤Ä¤¤¤Æ¡¢ ʸˡµ¬Â§¤ò·Á¼°¤Ð¤é¤º¤Ë½ñ¤¯¤È¡¢¼¡¤Î¤è¤¦¤Ë¤Ê¤ê¤Þ¤¹¡£

¡Öʸ¡×¤Ï¡¢¥­¡¼¥ï¡¼¥É¡Öreturn¡×¡¢¡Ö¼°¡×¡¢¡Ö¥»¥ß¥³¥í¥ó¡×¤«¤é ºî¤ë¤³¤È¤¬¤Ç¤­¤ë¡£

C¤Î³Æ¼ï¤Îʸ¤Ë¤Ä¤¤¤Æ¡¢¡Öʸ¡×¤Ë¤Ï¿¤¯¤Î¾¤Îµ¬Â§¤¬¤¢¤ë¤Ç¤·¤ç¤¦¡£

1¤Ä¤ÎÈó½ªÃ¼µ­¹æ¤¬¡¢¸À¸ì¤ÎÁ´ÂΤòɽ¸½¤¹¤ë¤è¤¦¤Ë¡¢ ÆÃÊ̤ʤâ¤Î¤È¤·¤Æ¼±Ê̤µ¤ì¤ëɬÍפ¬¤¢¤ê¤Þ¤¹¡£ ¤³¤ì¤ò³«»Ïµ­¹æ¡Êstart symbol¡Ë¤È¸Æ¤Ó¤Þ¤¹¡£ ¥³¥ó¥Ñ¥¤¥é¤Ç¤Ï¡¢¤³¤ì¤Ï´°Á´¤ÊÆþÎÏ¥×¥í¥°¥é¥à¤ò°ÕÌ£¤·¤Þ¤¹¡£ C¸À¸ì¤Ç¤Ï¡¢Èó½ªÃ¼µ­¹æ¡ÖÄêµÁ¤ÈÀë¸À¤Îʤӡפ¬¡¢¤³¤ÎƯ¤­¤ò¤·¤Þ¤¹¡£

¤¿¤È¤¨¤Ð¡¢‘1 + 2’¤ÏÍ­¸ú¤ÊC¤Î¼°¤Ç¡¢ C¤Î¥×¥í¥°¥é¥à¤ÎÍ­¸ú¤Ê°ìÉôʬ¤Ç¤¹¤¬¡¢ C¥×¥í¥°¥é¥àÁ´ÂΤȤ·¤Æ¤Ï̵¸ú¤Ç¤¹¡£ ¤·¤¿¤¬¤Ã¤Æ¡¢C¤Îʸ̮¼«Í³Ê¸Ë¡¤Ç¤Ï¡¢¡Ö¼°¡×¤Ï³«»Ïµ­¹æ¤Ç¤Ê¤¤¤È¤ï¤«¤ê¤Þ¤¹¡£

Bison¹½Ê¸²òÀÏ´ï¤Ï¡¢ÆþÎϤȤ·¤Æ¥È¡¼¥¯¥ó¤ÎÎó¤òÆÉ¤ß¡¢ ʸˡµ¬Â§¤ò»È¤Ã¤Æ¥È¡¼¥¯¥ó¤ò¥°¥ë¡¼¥×¤Ë¤·¤Þ¤¹¡£ ¤â¤·ÆþÎϤ¬Í­¸ú¤Ç¤¢¤ì¤Ð¡¢ºÇ½ªÅª¤Ê·ë²Ì¤È¤·¤Æ¡¢¥È¡¼¥¯¥ó¤ÎÎóÁ´ÂΤ¬ ʸˡ¤Î³«»Ïµ­¹æ¤Ç¤¢¤ë1¤Ä¤Î¥°¥ë¡¼¥×¤Îµ­¹æ¤Ë´Ô¸µ¤µ¤ì¤Þ¤¹¡£ ¤â¤·¤ï¤ì¤ï¤ì¤¬C¤Îʸˡ¤ò»È¤¦¤Ê¤é¤Ð¡¢ÆþÎÏÁ´ÂÎ¤Ï ¡ÖÄêµÁ¤ÈÀë¸À¤ÎÎó¡×¤ÎɬÍפ¬¤¢¤ê¤Þ¤¹¡£ ¤â¤·¤½¤¦¤Ç¤Ê¤±¤ì¤Ð¡¢¹½Ê¸²òÀϴ郎ʸˡ¥¨¥é¡¼¤òÊó¹ð¤·¤Þ¤¹¡£