longqzh's Blog

THE LITTLE C INTERPRETER

表达式剖析器（THE EXPRESSION PARSER)

   读取和分析表达式的这部分代码叫做表达式剖析器。毫无疑问，表达式剖析器是C解释器中单一的最重要的部分。因为C语言定义表达式的方式比其他语言更加粗鄙，所以用大量的代码组成的C源文件来实现表达式剖析器。

   有几种不同的方式来设计C的表达式剖析器。许多商业的编译器用一种由parser-generator创建的table-driven parser。尽管table-driven parser一般来说要快过其他方式，但却很难手工构建。为了开发简易的C解释器，在这里我们使用递归-继承剖析器（recursive-descent parser.）
  
   一个递归-继承剖析器本质上是一大堆处理表达式的互相递归的函数。如果是在编译器里，那么剖析器将被用来生成与源码相符的标准的目标代码。无论如何，在解释器中，剖析器的目的就是对给定的表达式求值。
  
将源代码变成他们的组成元素
 
   所有解释器的基础是一个读取源码然后返回下一个逻辑符号的特殊的函数。基于历史原因，这些逻辑标记一般与标记(token)相关联。一般而言，计算机语言，特别是C语言，依据标记来定义程序。你可以想象标记是一个不可见的程序单元。比如说，相等运算符==就是一个标记。这两个等于号分开后意义将彻底改变。同理,if 也是一个标记。在C语言中无论是i还是f都没有其他意思。
  
   在ANSI C标准中，标记被定义为属于下列几组：
   keywords    identifiers    constants   
   strings    operators    pinctuation
  
   keywords（关键字）是那些如while的构成C语言的标记。Identifier（识别符）是变量、函数、用户定义类型的名字。而Constants（常量）和 Strings（字符串）是不解自明的，就像operators（运算符）一样。最后Punctuation（标点符号）包括了几个项目，像分号，逗号，大括号，小括号等。
  
   在简易C解释器中，这个被称作get_token()的函数可以从源码中读取标记。

/*Get a token*/
get_token()
{
    register char *temp;
    token_type=0;tok=0;
    temp=token;
    *temp='\0';

    /* skip over white space*/
    while(iswhite(*prog)&&*prog)
        ++prog;

    if (*prog=='\r')
    {
        ++prog;
        ++prog;
        while (iswhite(*prog)&&*prog)
            ++prog;
    }

    if (*prog=='\0')
    {
        *token='\0';
        tok=FINISHED;
        return (token_type=DELIMITER);
    }

    if (strchr("{}",*prog))
    {
        *temp=*prog;
        temp++;
        *temp='\0';
        prog++;
        return (token_type=BLOCK);
    }

    /* look for comments*/
    if (*prog=='/')
        if (*(prog+1)=='*')
        {
            prog+=2;
            do
            {
                while(*prog!='*') prog++;
                prog++;
            }while (*prog!='/');
            prog++;
        }

    if (strchr("!<>=",*prog))
    {
        switch (*prog)
        {
            case '=':
                if (*(prog+1)=='=')
                {
                    prog++;prog++;
                    *temp=EQ;
                    temp++; *temp=EQ; temp++;
                    *temp='\0';
                }
                break;
            case '!':
                if (*(prog+1)=='=')
                {
                    prog++;prog++;
                    *temp=NE;
                    temp++; *temp=NE; temp++;
                    *temp='\0';
                }
                break;
            case '<':
                if (*(prog+1)=='=')
                {
                    prog++;prog++;
                    *temp=LE;temp++;*temp=LE;
                }
                else
                {
                    prog++;
                    *temp=LT;
                }
                temp++;
                *temp='\0';
                break;
            case '>':
                if (*(prog+1)=='=')
                {
                    prog++;prog++;
                    *temp=GE;temp++;*temp=GE;
                }
                else
                {
                    prog++;
                    *temp=GT;
                }
                temp++;
                *temp='\0';
                break;
        }
        if (*token) return(token_type=DELIMITER);
    }

    if (strchr("+-*^/%=;(),'",*prog))
    {
        *temp=*prog;
        prog++;
        temp++;
        *temp='\0';
        return (token_type=DELIMITER);
    }

    if (*prog=='"')
    {
        prog++;
        while (*prog!='"' && *prog!='\r')
            *temp++=*prog++;
        if (*prog=='\r') sntx_err(SYNTAX);
        prog++;*temp='\0';
        return (token_type=STRING);
    }

    if (isdigit(*prog))
    {
        while(!isdelim(*prog))
            *temp++=*prog++;
        *temp='\0';
        return(token_type=NUMBER);
    }

    if(isalpha(*prog))
    {
        while (!isdelim(*prog))
            *temp++=*prog++;
        token_type=TEMP;
    }

    *temp='\0';

    /*see if a string is a command or variable*/
    if (token_type==TEMP)
    {
        tok=look_up(token);
        if(tok) token_type=KEYWORD;
        else token_type=IDENTIFIER;
    }
    return token_type;
}

get_token()函数用到了以下的全局变量和枚举类型：

extern char *prog;
extern char *p_buf;
extern char token[80];
extern char token_type;
extern char tok;


enum tok_types {DELIMITER,IDENTIFIER,NUMBER,
                KEYWORD,TEMP,STRING,BLOCK};
				
enum double_ops {LT=1,LE,GT,GE,EQ,NE};

enum error_msg{
    SYNTAX,UNBAL_PARENS,NO_EXP,EQUALS_EXPECTED,
    NOT_VAR,PARAM_ERR,SEMI_EXPECTED,
    UNBAL_BRACES,FUNC_UNDEF,TYPE_EXPECTED,
    NEST_FUNC,RET_NOCALL,PAREN_EXPECTED,
    WHILE_EXPECTED,QUOTE_EXPECTED,NOT_TEMP,
    TOO_MANY_LVARS};

   在源码中当前位置由prog指定。p_buf指针无法被解释器所改变而且经常指向正在被解析的程序的开头。get_token()函数开始跳过所有的空白，包括回车和空行。直到没有C标记包含空格，所以的空格必须被跳过。当然get_token()函数也要跳过注释。接下来，将每个标记的字符串表现形式归类到token,它的类型用token_type表达，而且，如果标记是一个关键字，它的内部表示将通过look_up()函数分配给tok。如你所见的get_token()函数，它将C的双字关系运算符转换成对应的枚举值。虽然不是技术需要，但这一步可以简化parser剖析器的实现。最后，如果parser剖析器遇到语法错误，将会调用sntx_err()函数。sntx_err()函数如下：
   

/*Display an error message*/
void sntx_err(int error)
{
    char *p,*temp;
    int linecount=0;
    register int i;

    static char *e[]={
        "Syntax error",
        "unbalanced parentheses",
        "no expression present",
        "equals sign expected",
        "not a variable",
        "parameter error",
        "semicolon expected",
        "unbalanced braces",
        "function undefined",
        "type specifier expected",
        "too many nested function calls",
        "return without call",
        "parentheses expected",
        "while expected",
        "closing quoto expected",
        "not a string",
        "too many local variable"
    };
    printf ("%s",e[error]);
    p=p_buf;
    while (p!=prog)
    {
        p++;
        if (*p=='\r')
            linecount++;
    }
    printf (" in line %d\n",linecount);
    temp=p;
    for (i=0;i<20 && p>p_buf && *p!='\n';i++,p--);
    for (i=0;i<30 && p<=temp;i++,p++)
        printf ("%c",*p);
    longjmp (e_buf,1);
}

   值得注意的是sntx_err()也会显示出错语句的行号，最后要注意的是sntx_err()调用longjmp()结束。因为语法错误会在嵌套或递归程序中频繁地出现，最简单的控制错误的方法就是跳到一个安全的地方。