编译原理：TINY语言编译器词法分析源代码剖析（main.c、scan.c详细注释）

ゝ一纸荒年。 2023-07-15 11:30 19阅读 0赞

### 目录 ###

*   *  一、任务介绍
     *  二、分析步骤
     *  三、main.c注释
     *  四、scan.c注释

## 一、任务介绍 ##

本文取自编译原理课程第一次实验，要求找出TINY语言的词法分析器源代码并进行剖析。

## 二、分析步骤 ##

1.  解压实验压缩包。可以观察到，TINY语言编译器的源代码的结构为：一个main.c加若干.h头文件加若干.c文件。因此从main.c入手，开始分析。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTEyMTcw_size_16_color_FFFFFF_t_70]
2.  在main.c中，首先声明了全局头文件：  
    \#include “globals.h”
3.  注意到接下来的宏定义：  
    NO\_PARSE、NO\_ANALYZE、NO\_CODE，初始值为FALSE。  
    将NO\_PARSE设置为TRUE可以获得一个仅扫描的编译器，因此NO\_PARSE代表是否进行语法分析；将NO\_ANALYZE设置为TRUE可以获得一个仅解析的编译器，因此NO\_ANALYZE代表是否进行语义分析；将NO\_CODE设置为TRUE可以得到一个不生成代码的编译器，因此NO\_CODE代表是否生成代码。  
    分析到这里，已经可以确定该编译器源代码可以分为语法分析、语义分析、代码生成三个部分。
4.  接下来的导入头文件是由上一步的宏定义决定。通过if-else语句，实现对于不同的业务需求，导入不同的头文件，执行不同的函数调用。  
    ![在这里插入图片描述][20200316215334897.png]  
    之前已经得出NO\_PARSE代表是否进行语法分析，结合这里的if-else，可以确定语法分析与头文件scan.h相关。
5.  接下来分析主函数。我注意到一些细节：当用户没有给出输入参数时，程序打印输出，提示用法，这就刚好对应我在第11步时遇到的提示信息；如果输入参数没有后缀，程序将自动补全.tny，因此在调用TINY.exe时可以不指定输入参数的文件后缀。
6.  观察到接下来与宏相关的if-else语句，根据\#if NO\_PARSE时调用getToken()，而\#else时调用parse()，推测getToken()就是词法分析函数，parse()中必然包括类似功能或者parse()中调用了getToken()函数。查找parse()函数，发现它在parseu.c中。
7.  parse.c中应有词法分析与语法分析的相关实现，在这里只关心词法分析，注意到如下代码：  
    ![在这里插入图片描述][20200316215439816.png]  
    观察到这里调用了getToken()函数！考虑到在进行语法分析前必然要进行词法分析，因此可以确定stmt\_sequence()函数进行语法分析，而词法分析函数就是getToken()！
8.  getToken()函数在scan.c中被定义，因此可以确定，scan.c就是词法分析代码所在的文件。根据课程知识，词法分析需要自前向后扫描，通过状态转换图，依次得到每一个词素的词法单元。在scan.c中，首先定义了一个枚举类型StateType，推测为DFA的状态。  
    ![在这里插入图片描述][20200316215500477.png]
9.  继续分析，char tokenString\[MAXTOKENLEN+1\]为标识符或保留字，使用字符数组存储。\#define BUFLEN 256为源代码行的输入缓冲区的最大长度。每一行输入放进字符数组lineBuf\[BUFLEN\]中。
10. getNextChar()函数从lineBuf获取下一个非空字符，如果lineBuf已读完，则读取新行。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTEyMTcw_size_16_color_FFFFFF_t_70 1]
11. ungetNextChar()函数非常简单，实现回退一格。推测该函数用于区分包含I/不包含E，相当于JUMP。  
    ![在这里插入图片描述][20200316215605971.png]
12. 接下来定义了一个预留字的查找表，如if、then、else等，使用结构体实现。reservedLookup()函数使用最为简单的线性查找算法，通过刚刚定义的查找表，查找某一个标识符是否是保留字，从而可以区分保留字和用户自定义的ID。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTEyMTcw_size_16_color_FFFFFF_t_70 2]
13. getToken()函数基于状态转换实现，返回下一个词法单元。通过该函数中的状态转移，我们可以推测TINY函数的赋值符号为:=，\{\}内为注释，每一句以;结束，标识符只能由字母组成，支持+、-、\*、/、<等简单的运算符。
    
    通过这里的状态转换，我们可以确定程序中定义的各DFA状态的含义：
    
    > START：起始状态 INASSIGN：输入:之后，等待输入=，从而赋值状态
    
    > INCOMMENT：输入\{之后，进入注释状态，编译器忽略 注释内容，直至遇到\}结束
    
    > INNUM：输入数字之后，进入数字的匹配状态，遇到非数字结束
    
    > INID：输入字母之后，进入标识符的匹配状态，可能为用户自定义或预留符，遇到非字母结束 DONE：成功匹配到一个词法单元，完成匹配
14. 当成功匹配一个词素后结束状态转换循环，若匹配到的词法单元为ID，需要检查该词素是否为保留字。若全局变量TraceScan为TRUE，调用util.c中定义了printToken()函数，将一个词法单元及其词汇表打印到listing文件中。getToken()函数最终返回下一个词法单元，实现词法分析。
15. 回到main.c，在结束语法分析，循环调用getToken()以得到所有的词法单元之后，紧接着根据宏定义NO\_PARSE、NO\_PARSE与NO\_CODE的值，决定是否进行语法分析、语义分析与代码生成(可以细分为若干步)。至此，TINY语言编译器的源代码分析完成。

## 三、main.c注释 ##

//全局头文件
    #include "globals.h"
    #include <stdlib.h>
    
    //宏定义
    /* set NO_PARSE to TRUE to get a scanner-only compiler */
    //将NO_PARSE设置为TRUE以获得一个仅扫描的编译器：是否进行语法分析
    #define NO_PARSE FALSE
    
    /* set NO_ANALYZE to TRUE to get a parser-only compiler */
    //将NO_ANALYZE设置为TRUE以获得一个仅解析的编译器：是否进行语义分析
    #define NO_ANALYZE FALSE
    
    /* set NO_CODE to TRUE to get a compiler that does not * generate code */
     //将NO_CODE设置为TRUE可以得到一个不生成代码的编译器
    #define NO_CODE FALSE
    
    #include "util.h"
    #if NO_PARSE
    #include "scan.h"
    #else
    #include "parse.h"
    #if !NO_ANALYZE
    #include "analyze.h"
    #if !NO_CODE
    #include "cgen.h"
    #endif
    #endif
    #endif
    
    /* allocate global variables */
    int lineno = 0;
    FILE * source;
    FILE * listing;
    FILE * code;
    
    /* allocate and set tracing flags */
    int EchoSource = FALSE;
    int TraceScan = FALSE;
    int TraceParse = FALSE;
    int TraceAnalyze = TRUE;
    int TraceCode = FALSE;
    
    int Error = FALSE;
    
    main( int argc, char * argv[] )
    {  TreeNode * syntaxTree;
      char pgm[120]; /* source code file name */
      if (argc != 2)
        {  fprintf(stderr,"usage: %s <filename>\n",argv[0]);
          exit(1);
        }
      strcpy(pgm,argv[1]) ;
      //注意到，也正是因为该处理，读入文件时可以不写后缀名
      if (strchr (pgm, '.') == NULL)
         strcat(pgm,".tny");
     //以read方式打开文件
      source = fopen(pgm,"r");
      if (source==NULL)
      {  fprintf(stderr,"File %s not found\n",pgm);
        exit(1);
      }
      listing = stdout; /* send listing to screen */
      fprintf(listing,"\nTINY COMPILATION: %s\n",pgm);
    #if NO_PARSE
    	//词法分析--->本次关注的重点
    	//getToken返回下一个词法单元
      while (getToken()!=ENDFILE);
    #else
    	//词法分析+语法分析
    	//parse方法本身调用getToken
      syntaxTree = parse();
      if (TraceParse) { 
        fprintf(listing,"\nSyntax tree:\n");
        printTree(syntaxTree);
      }
    #if !NO_PARSE
    	//语义分析
      if (! Error)
      {  if (TraceAnalyze) fprintf(listing,"\nBuilding Symbol Table...\n");
        buildSymtab(syntaxTree);
        if (TraceAnalyze) fprintf(listing,"\nChecking Types...\n");
        typeCheck(syntaxTree);
        if (TraceAnalyze) fprintf(listing,"\nType Checking Finished\n");
      }
    #if !NO_CODE
    	//代码生成
      if (! Error)
      {  char * codefile;
        int fnlen = strcspn(pgm,".");
        codefile = (char *) calloc(fnlen+4, sizeof(char));
        strncpy(codefile,pgm,fnlen);
        strcat(codefile,".tm");
        code = fopen(codefile,"w");
        if (code == NULL)
        {  printf("Unable to open %s\n",codefile);
          exit(1);
        }
        codeGen(syntaxTree,codefile);
        fclose(code);
      }
    #endif
    #endif
    #endif
      fclose(source);
      return 0;
    }

## 四、scan.c注释 ##

#include "globals.h"
    #include "util.h"
    #include "scan.h"
    
    //词法分析，自前向后扫描
    
    /* states in scanner DFA */
    //枚举类型，DFA状态
    typedef enum
       {  START,INASSIGN,INCOMMENT,INNUM,INID,DONE }
       StateType;
    
    /* lexeme of identifier or reserved word */
    //标识符或保留字的词汇，字符数组存储
    char tokenString[MAXTOKENLEN+1];
    
    /* BUFLEN = length of the input buffer for source code lines */
    //源代码行的输入缓冲区的长度
    #define BUFLEN 256
    
    static char lineBuf[BUFLEN]; /* holds the current line */
    static int linepos = 0; /* current position in LineBuf */
    static int bufsize = 0; /* current size of buffer string */
    static int EOF_flag = FALSE; /* corrects ungetNextChar behavior on EOF */
    
    /* getNextChar fetches the next non-blank character from lineBuf, reading in a new line if lineBuf is exhausted */
       //getNextChar从lineBuf获取下一个非空字符，如果lineBuf已耗尽，则读取新行
    static int getNextChar(void)
    {  if (!(linepos < bufsize)) //读取新行
      {  lineno++;
        if (fgets(lineBuf,BUFLEN-1,source))
        {  if (EchoSource) fprintf(listing,"%4d: %s",lineno,lineBuf);
          bufsize = strlen(lineBuf);
          linepos = 0;
          return lineBuf[linepos++];
        }
        else
        {  EOF_flag = TRUE;
          return EOF;
        }
      }
      else return lineBuf[linepos++]; //返回下一个字符
    }
    
    /* ungetNextChar backtracks one character in lineBuf */
       //回退
    static void ungetNextChar(void)
    {  if (!EOF_flag) linepos-- ;}
    
    /* lookup table of reserved words */
    //预留字查找表
    static struct
        {  char* str;
          TokenType tok;
        } reservedWords[MAXRESERVED]
       = { { "if",IF},{ "then",THEN},{ "else",ELSE},{ "end",END},
          { "repeat",REPEAT},{ "until",UNTIL},{ "read",READ},
          { "write",WRITE}};
    
    /* lookup an identifier to see if it is a reserved word */
    /* uses linear search */
    //查找标识符以查看它是否是保留字！最为简单的线性查找
    static TokenType reservedLookup (char * s)
    {  int i;
      for (i=0;i<MAXRESERVED;i++)
        if (!strcmp(s,reservedWords[i].str))
          return reservedWords[i].tok;
      return ID;
    }
    
    //scanner的主函数
    /****************************************/
    /* the primary function of the scanner */
    /****************************************/
    /* function getToken returns the * next token in source file */
     //返回下一个词法单元
    TokenType getToken(void)
    {   /* index for storing into tokenString */
    //索引
       int tokenStringIndex = 0;
       /* holds current token to be returned */
       //当前词法单元
       TokenType currentToken;
       /* current state - always begins at START */
       //当前状态—总是从头开始
       StateType state = START;
       /* flag to indicate save to tokenString */
       //标志，当前字符是否有效
       int save;
       while (state != DONE)//匹配到一个词素之后就结束
       {  int c = getNextChar();
         save = TRUE;
         switch (state)//状态转移
         {  case START:
             if (isdigit(c))
               state = INNUM;//数字
             else if (isalpha(c))
               state = INID;//id
             else if (c == ':')
               state = INASSIGN;//冒号
             else if ((c == ' ') || (c == '\t') || (c == '\n'))
               save = FALSE;
             else if (c == '{')
             {  save = FALSE;
               state = INCOMMENT;//注释
             }
             else
             {  state = DONE;
               switch (c)
               {  case EOF:
                   save = FALSE;
                   currentToken = ENDFILE;//结束
                   break;
    			   //枚举符号
                 case '=':
                   currentToken = EQ;
                   break;
                 case '<':
                   currentToken = LT;
                   break;
                 case '+':
                   currentToken = PLUS;
                   break;
                 case '-':
                   currentToken = MINUS;
                   break;
                 case '*':
                   currentToken = TIMES;
                   break;
                 case '/':
                   currentToken = OVER;
                   break;
                 case '(':
                   currentToken = LPAREN;
                   break;
                 case ')':
                   currentToken = RPAREN;
                   break;
                 case ';':
                   currentToken = SEMI;
                   break;
                 default:
                   currentToken = ERROR;
                   break;
               }
             }
             break;
    		 
    		//注释语句内
           case INCOMMENT:
             save = FALSE;
             if (c == EOF)
             {  state = DONE;
               currentToken = ENDFILE;
             }
    		 else if (c == '}') state = START;//直到遇到}为止
             break;
    		 
    		 //冒号之后，TINY的语法，赋值语句
           case INASSIGN:
             state = DONE;
             if (c == '=')
               currentToken = ASSIGN;//:=代表赋值
             else
             {  /* backup in the input */
               ungetNextChar();
               save = FALSE;//不保存，回退，出错
               currentToken = ERROR;
             }
             break;
    		 
    		 //数字
           case INNUM:
             if (!isdigit(c))
             {  /* backup in the input */
               ungetNextChar(); //回退，相当于老师上课讲的jump
               save = FALSE;//不保存现在的字符
               state = DONE;//完成一个词素的匹配
               currentToken = NUM;//类型为NUM
             }
             break;
    		 
    		 //ID只能是字符
           case INID:
             if (!isalpha(c))
             {  /* backup in the input */
               ungetNextChar();
               save = FALSE;//不是字符，代表ID结束，DONE
               state = DONE;
               currentToken = ID;
             }
             break;
    		 
           case DONE://错误情况
           default: /* should never happen */
             fprintf(listing,"Scanner Bug: state= %d\n",state); //打印到listing中
             state = DONE;
             currentToken = ERROR;
             break;
         }
    	 
    	 //save为true
         if ((save) && (tokenStringIndex <= MAXTOKENLEN))
           tokenString[tokenStringIndex++] = (char) c;
       	//匹配到了一个词素
         if (state == DONE)
         {  tokenString[tokenStringIndex] = '\0';
           if (currentToken == ID)
             currentToken = reservedLookup(tokenString);//检测是否为保留字
         }
       }
       
    	//全局变量
       if (TraceScan) { 
         fprintf(listing,"\t%d: ",lineno);
    	 //在util.c中，将一个词法单元及其词汇表打印到listing文件中，这个函数里面都是文件打印语句
         printToken(currentToken,tokenString);
       }
       return currentToken;
    } /* end getToken */

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTEyMTcw_size_16_color_FFFFFF_t_70]: /images/20230528/cf28200e29cb4cef96035de87b2a155d.png
[20200316215334897.png]: /images/20230528/58d26fe2daac45c1940c5c9dbcdfc908.png
[20200316215439816.png]: /images/20230528/cda23b69b9714717af3415d3cbc9effd.png
[20200316215500477.png]: /images/20230528/6dd424cad58941dab12b52b95e691743.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTEyMTcw_size_16_color_FFFFFF_t_70 1]: /images/20230528/deaf00683c194cfbb6058cc960a26a56.png
[20200316215605971.png]: /images/20230528/aca80bdbd07a48d8a411eab22d5b84e8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTEyMTcw_size_16_color_FFFFFF_t_70 2]: /images/20230528/bf5a579084314eacb8f84f9d854d529b.png