±àÒëÔ­Àí¾­µäËã·¨µÄ¿ÉÊÓ»¯ÊµÏÖ - ͼÎÄ

±àÒëÔ­Àí¾­µäËã·¨µÄ¿ÉÊÓ»¯ÊµÏÖ ±àÒëÔ­Àí¾­µäËã·¨µÄ¿ÉÊÓ»¯ÊµÏÖ

ÕªÒª

ÔÚ¼ÆËã»ú½ÌѧÖУ¬±àÒëÔ­ÀíÕâÃſγÌÔÚ¼ÆËã»ú¿ÆѧÖÐÕ¼Óзdz£ÖØÒªµÄµØλ£¬Ã¿¸ö¼ÆËã»úרҵµÄͬѧ¶¼ÐèҪѧϰËü¡£¶øͨ¹ýѧϰ±àÒëÔ­Àí£¬ÄܸüºÃµÄÁ˽â¸ß¼¶³ÌÐòÓïÑÔµÄÔËÐлúÖÆ£¬²¢Äܱàд³ö¸ü¼Ó¸ßЧµÄ³ÌÐò¡£µ«ÊDZàÒëÔ­ÀíÖеÄËã·¨±È½Ï³éÏó£¬Ñ§Ï°ÆðÀ´À§ÄÑ£¬¶ø±¾ÏµÍ³Äܹ»¶¯Ì¬ÑÝʾ±àÒëÔ­ÀíÖеĴʷ¨·ÖÎö½×¶ÎºÍÓï·¨·ÖÎö½×¶ÎµÄLL(1)ÎÄ·¨£¬¶ø´Ê·¨·ÖÎöÆ÷½«Êä³öÿ¸öµ¥´Ê¶ÔÓ¦µÄ¶þÔª×飬Õ⽫ÓÐÀûÓÚÎÒÃǶԴʷ¨·ÖÎöÆ÷µÄÀí½â£¬¶øLL(1)ÎÄ·¨µÄ¶¯Ì¬ÑÝʾʹÎÒÃÇÄܹ»¸üºÃµÄÀí½â²¢ÔËÓÃLL(1)ÎÄ·¨Öеĸ÷ÖÖËã·¨¡£ËùÒÔÕâÖÖËã·¨¿ÉÊÓ»¯¼¼ÊõÄܼÓÉîÈËÃǶԳÌÐòÐÐΪµÄÀí½âºÍÈÏʶ£¬×¼È·µØÁ˽âºÍ·ÖÎö³ÌÐòÖ´Ðйý³ÌËù·´Ó³µÄÂß¼­º¬ÒåºÍ¹¦ÄÜ¡£

±¾³ÌÐòÊÇÔÚvs2012ƽ̨ÏÂÓÃC#ÓïÑÔʵÏֵġ£±¾³ÌÐò½çÃæ¼ò½à£¬ÄÜʵÏÖ´Ê·¨·ÖÎöÆ÷µÄ¿ÉÊÓ»¯ºÍLL(1)ÎÄ·¨µÄÑÝʾ¡£

¹Ø¼ü´Ê£º´Ê·¨·ÖÎö;LL(1)ÎÄ·¨;¿ÉÊÓ»¯¼¼Êõ

I

±àÒëÔ­Àí¾­µäËã·¨µÄ¿ÉÊÓ»¯ÊµÏÖ

THE VISUAL IMPLEMENTATION of CLASSIC ALGORITHM

of COMPILATION PRINCIPLE

Abstract

In the computer course,Compilation principle plays a very important role in computer science, each student who learns computer science has to learn it. Through the study of these principles, we can be more easy to understand the operation mechanism of various high-level language, and we can produce more efficient code. But the compilation principle is abstract, it¡¯s very difficult to learn it. The system can dynamic demo the compilation principle of lexical analysis and LL (1) of grammar grammar analysis phase, and the lexical analyzer will output each word two tuples, which will help us to analysis of lexical understanding, LL (1) dynamic demo grammar enables us to better understand and use the LL (1) algorithms in the grammar. So this kind of algorithm visualization technology can help people to understand program behavior, understand the reflection accuratly and analysis of program execution logic meaning and function.

This procedure is used C# language under vs2012 platform. The program¡¯s interface is simple, and it achieves visual of lexical analyzer and the demo of LL(1) algorithms.

Key words: lexical analysis; LL (1); visualization technology

II

±àÒëÔ­Àí¾­µäËã·¨µÄ¿ÉÊÓ»¯ÊµÏÖ Ä¿Â¼

1 Ð÷ ÂÛ¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­.1

1.1±³¾° .................................................................................................................. 1 1.2±¾¿ÎÌâÑо¿µÄÄ¿µÄºÍÒâÒå .............................................................................. 1 1.3¹úÄÚÍâÑо¿ÏÖ×´ .............................................................................................. 2 1.4Ö÷Òª¹¤×÷ .......................................................................................................... 2 1.5 ±¾ÏµÍ³µÄÉè¼Æ˼Ïë ......................................................................................... 2 2 ´Ê·¨·ÖÎö¸ÅÊö¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­.¡­¡­.4

2.1 ´Ê·¨·ÖÎöÆ÷µÄ×÷Óà ......................................................................................... 4 2.2´Ê·¨·ÖÎöÖеÄÎÊÌâ .......................................................................................... 5 2.3 ´Ê·¨·ÖÎöÖеÄÊõÓï ......................................................................................... 5 2.4 ´Ê·¨´íÎó ......................................................................................................... 7 2.5 ´Ê·¨·ÖÎöÉú³É¹¤¾ß ......................................................................................... 8 3 ´Ê·¨·ÖÎöÆ÷¶¯Ì¬ÑÝʾµÄÉè¼ÆÓëʵÏÖ¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­..¡­¡­.10

3.1 ´Ê·¨·ÖÎöÆ÷ÃèÊöÓïÑÔ ................................................................................... 10

3.1.1 Lex˵Ã÷¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­..10 3.1.2 ³¬Ç°É¨Ãè²Ù×÷¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­.¡­¡­¡­¡­¡­¡­¡­.11 3.1.3 Lex±à³Ì¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­..12 3.2´Ê·¨·ÖÎöÆ÷¶¯Ì¬ÑÝʾµÄʼþʵÏÖ ................................................................ 12 4 Óï·¨·ÖÎö¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­.¡­¡­.¡­¡­.17

4.1 Óï·¨·ÖÎöµÄ»ù±¾¸ÅÄî ................................................................................... 17 4.2 Óï·¨·ÖÎöµÄÈÎÎñ ........................................................................................... 17 4.3 Óï·¨·ÖÎö»ù´¡ ............................................................................................... 17 5 LL(1)ÎÄ·¨¿ÉÊÓ»¯µÄÉè¼ÆÓëʵÏÖ¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­23

5.1 ³ÌÐò½çÃæµÄʵÏÖ ......................................... ...23 5.2 ³ÌÐò¹Ø¼ü¹¦ÄܵÄʵÏÖ¡£ ....................................... 25

III

±àÒëÔ­Àí¾­µäËã·¨µÄ¿ÉÊÓ»¯ÊµÏÖ 5.2.1 FIRSTºÍFOLLOW¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­..¡­¡­25 5.2.2 Ô¤²â·ÖÎö±íµÄ¹¹Ôì .................................. ...27

ÖÂл¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­29 ²Î¿¼ÎÄÏס­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­.30 ¸½Â¼¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­¡­.31 ¸½¼þ1 ¿ªÌⱨ¸æ ¸½¼þ2 ÒëÎļ°Ô­ÎÄÓ°Ó¡¼þ

IV