Next: Grammar in Bison, Up: Concepts [Contents][Index]
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¤Îʸˡ¤ò»È¤¦¤Ê¤é¤Ð¡¢ÆþÎÏÁ´ÂÎ¤Ï ¡ÖÄêµÁ¤ÈÀë¸À¤ÎÎó¡×¤ÎɬÍפ¬¤¢¤ê¤Þ¤¹¡£ ¤â¤·¤½¤¦¤Ç¤Ê¤±¤ì¤Ð¡¢¹½Ê¸²òÀϴ郎ʸˡ¥¨¥é¡¼¤òÊó¹ð¤·¤Þ¤¹¡£