1. ¼³¸í ¹× algorithm
parser¶õ compiler¿¡¼ syntax analysis¸¦ ÇÏ´Â ºÎºÐÀÌ´Ù.
parserÀÇ ¿ªÇÒÀ» º¸¸é ´ÙÀ½°ú °°´Ù. lexical analyzer·ÎºÎÅÍ tokenÀ» ¹Þ¾ÆµéÀδÙ. ±×¸®°í source language¿¡ ´ëÇØ stringÀÌ grammar¿¡ ÀÇÇØ generateµÉ ¼ö ÀÖÀ½À» Áõ¸íÇϸç, compile½Ã ÀϹÝÀûÀ¸·Î ³ªÅ¸³ª´Â error¸¦ recoverÇÏ¿© processingÀ» ÁøÇà½ÃŲ´Ù.
parserÀÇ typeÀº 3°¡Áö·Î ±¸ºÐµÈ´Ù. universal parsing method´Â ¾î¶² grammarµµ parsingÇÒ ¼ö ÀÖÁö¸¸, ºñÈ¿À²ÀûÀ̶ó ÀϹÝÀûÀ¸·Î Àß »ç¿ëÇÏÁö ¾Ê´Â´Ù. ´ëÇ¥ÀûÀÎ ¹æ¹ýÀ¸·Î´Â top-down parsing°ú bottom-up parsingÀÌ ÀÖ´Ù. top-down parsingÀº parsing treeÀÇ rootºÎÅÍ leaves·Î È®Àå½ÃÅ°¸é¼ parsingÀ» ÇÑ´Ù. LL parsingÀ̶ó°íµµ ÇÑ´Ù. ÁÖ·Î hand made parser¿¡ »ç¿ëµÈ´Ù. bottom-up parsingÀº parsing treeÀÇ leaves¿¡¼ root·Î ¿Ã¶ó°¡´Â ¹æ¹ýÀÌ´Ù. ÀÌ parsingÀº º¹ÀâÇÏ¿© ±â°è³ª tool¿¡ ÀÇÇØ ÀÌ·ç¾îÁö¸ç, LR parsingÀ̶ó°íµµ ÇÑ´Ù. top-down°ú bottom-up ¸ðµÎ left-to-rightÀ̸ç, Çѹø¿¡ ÇϳªÀÇ input symbolÀ» Àд´Ù.
parsing¿¡ »ç¿ëµÇ´Â syntax´Â context-free grammar¸¦ ÀÌ¿ëÇÏ¿© Ç¥ÇöÇÏ°Ô µÈ´Ù.
p¡¦(»ý·«)
¨ç X ¡ë a ¡ë $ : parsingÀÌ ¿Ï·áµÇ¾î parsingÀ» ÁßÁöÇÑ´Ù.
¨è X ¡ë a ¡Á $ : X¸¦ stack¿¡¼ popÇÑ´Ù.
¨é X°¡ nonterminalÀÎ °æ¿ì : M[A , a]¸¦ ½ÇÇàÇÑ´Ù.
|