通常来说,语法分析器会构造一棵语法分析树抽象(不一定显示构造)。
处理文法的语法分析器大体上有三类:通用,自顶向下,自低向上。
通用语法分析算法如CYK和Earley可以用于分析任何文法,但是效率较低,不能用于编译器产品。
顾名思义,自顶向下是从语法树的顶点开始像底部构造语法树,而自底向上则完全相反。
自顶向下比较简单,不过用来分析C语言之类的简单语言,在一些辅助手段的辅助下已经足够用,lcc也是采用自顶向下的递归下降算法。
在自顶向下和自底向上的语法分析模型中,其输入都是从左向右扫描,每次一个词素。
语法分析的首要任务是识别语法错误,这里的语法错误实际上包括以下4类:
1,词法错误,如关键字拼写错误,没有在字符串文本中正确加上引号。
2,语法错误,少掉一个}等。
3,语义错误,给一个未定义的变量赋值等,或者返回值与实际类型不匹配等。
4,逻辑错误,如==写成了=。
编译器要一次尽可能的多检查出错误,那么在已经检查出错误之后就需要排除已知错误带来的干扰,才能正确的继续识别。
当然有些错误如包含了没有的头文件之类的错误是无法恢复的,也即是我们常见的fatal error。
当然编译器一般也会有个编译错误上界,即使对于普通错误,如果达到了错误上界,也会推出。因为错误太多,可能导致语法分析器无法正常工作。
对于lcc,错误退出逻辑在error.c中
/* fatal - issue fatal error message and exit */ int fatal(const char *name, const char *fmt, int n) { print("\n"); errcnt = -1; error("compiler error in %s--", name); fprint(stderr, fmt, n); exit(EXIT_FAILURE); return 0; } void error(const char *fmt, ...) { va_list ap; //每次出错,errcnt都会增加,超过errlimit之后,进程退出 if (errcnt++ >= errlimit) { errcnt = -1; error("too many errors\n"); exit(1); } va_start(ap, fmt); if (firstfile != file && firstfile && *firstfile) fprint(stderr, "%s: ", firstfile); fprint(stderr, "%w: ", &src); vfprint(stderr, NULL, fmt, ap); va_end(ap); }
一个lcc错误恢复的例子,忽略掉错误词素,获取新词素,decl.c的dclparam函数
if (t == '=') { error("illegal initialization for parameter `%s'\n", id); t = gettok(); (void)expr1(0); } return p;
推导,最左推导,最右推导:
推导就是将一个非终结符号替换成它的某个产生式体,最左推导,先推导句型的最左边非终结符号,最右推导相反。
二义性:对同一个句子有多个最左(右)推导,即有多颗不同的语法树。
左递归:顾名思义,就是一个一个文法中的某个非终结符号推导之后仍有可能得到这个非终结符号组成的产生式体。分立即左递归和环左递归。