reader函数读入输入的.y文件, 把它翻译成内部格式, 比如把名字翻译成整数, 记录各个规则的各项目等(以calc.y为例子,比自带的calc.y简化了)
%{ # include <stdio.h> # include <ctype.h>
int regs[26]; int base;
%}
%start list
%token DIGIT LETTER
%left '+' '-' %left '*' '/' %left UMINUS /* supplies precedence for unary minus */
%% /* beginning of rules section */
list : /* empty */ | list stat '\n' | list error '\n' { yyerrok ; } ;
stat : expr { printf("%d\n",$1);} | LETTER '=' expr { regs[$1] = $3; } ;
expr : '(' expr ')' { $$ = $2; } | expr '+' expr { $$ = $1 + $3; } | expr '-' expr { $$ = $1 - $3; } | expr '*' expr { $$ = $1 * $3; } | expr '/' expr { $$ = $1 / $3; } | '-' expr %prec UMINUS { $$ = - $2; } | LETTER { $$ = regs[$1]; } | number ;
number: DIGIT { $$ = $1; base = ($1==0) ? 8 : 10; } | number DIGIT { $$ = base * $1 + $2; } ;
%% /* start of programs */
int main (void) { while(!feof(stdin)) { yyparse(); } return 0; }
static void yyerror(const char *s) { fprintf(stderr, "%s\n", s); }
int yylex(void) { /* lexical analysis routine */ /* returns LETTER for a lower case letter, yylval = 0 through 25 */ /* return DIGIT for a digit, yylval = 0 through 9 */ /* all other characters are returned immediately */
int c;
while( (c=getchar()) == ' ' ) { /* skip blanks */ }
/* c is now nonblank */
if( islower( c )) { yylval = c - 'a'; return ( LETTER ); } if( isdigit( c )) { yylval = c - '0'; return ( DIGIT ); } return( c ); }
|
reader代码如下:
void reader(void) { write_section(banner); create_symbol_table(); read_declarations(); read_grammar(); free_symbol_table(); free_tags(); pack_names(); check_symbols(); pack_symbols(); pack_grammar(); free_symbols(); print_grammar(); print_ritem(); }
|
重点有以下几个函数:
read_declarations();
读取声明部分,也就是第一个%%之前的部分, 除了一些和选项,它主要:
调用copy_text把 %{ %}中的内容复制到calc.c中;
调用copy_union生成union的定义;
调用declare_tokens把%token, %left, %right, %nonassoc声明的终结符插入到符号表中,
记录其相应的优先级(操作符的优先级依次递增)、结合性和相应的值(如果给出了的话)等
read_grammar();
读取规则部分,这是yacc输入文件内容的第二部分,也是最重要的一部分。
它记录每条规则的左边文法符号是什么,右边文法符号都有哪些,它调用
copy_action复制相应的C语言动作代码,以便当规约成功的时候执行相应的代码。
这个框架对任何输入都是一样的。
copy_action在读入C代码时把$开头的符号翻译为对值栈的引用
read_grammar函数涉及的数据,initialize_grammar函数中有体现 (有些变量保留了几个槽位是有意义的):
1. pitem
即production item, 记录产生式右边都是什么文法符号(是符号本身,即类型是bucket **),每条规则用NULL结束
对于calc.y它的内容如下,其中前4个槽没有使用(开头第
5个空是因为
list的第一条规则是空规则)
2. plhs
即production left hand side
类型也是bucket**
对于calc.y它的内容如下,其中前3个槽没有使用
3. rprec
规则的优先级,用于解决冲突,具体到解决冲突的时候再看
默认情况下规则的优先级等于该产生式最后一个终结符的优先级,
但是可以用%prec改变, calc.y中的就指定了一条规则的优先级为一元减的优先级
| '-' expr %prec UMINUS
{ $$ = - $2; }
4. rassoc
同上
有了上面这几个数组,文法规则部分就完全记录了
check_symbols();
该函数做一些检查,并且把未声明而直接使用的符号当终结符.
pack_symbols();
到调用该函数之前,所有的符号都只在符号表中,该函数为每个符号准备一个位置
有四个数组保存符号的属性,包括符号名,符号值,符号的优先级,符号的结合性
分别是
symbol_name symbol_value symbol_prec symbol_assoc
终结符在前,对应calc.y的内容为
关键字error是在建符号表的时候就保留的,$end和$accept是内部使用的。
$end的值是0,当词法分析器yylex输入结束时返回0.
终结符和非终结符的值是不相关的,非终结符从256开始依次增加(256以下给单个字符使用),
某个终结符也可以显示的指定某个值(比如%token IF 259),这样在安排的时候会跳过该值
pack_grammar
static void pack_grammar(void) { int i; Value_t j; Assoc_t assoc; Value_t prec2;
ritem = (short *)MALLOC((unsigned)nitems * sizeof(short)); NO_SPACE(ritem);
rlhs = (short *)MALLOC((unsigned)nrules * sizeof(short)); NO_SPACE(rlhs);
rrhs = (short *)MALLOC((unsigned)(nrules + 1) * sizeof(short)); NO_SPACE(rrhs);
rprec = (short *)REALLOC(rprec, (unsigned)nrules * sizeof(short)); NO_SPACE(rprec);
rassoc = REALLOC(rassoc, nrules); NO_SPACE(rassoc);
ritem[0] = -1; /* -1: 第一条规则(由yacc加上的 $accept: goal $end) */ ritem[1] = goal->index; /* goal */ ritem[2] = 0; /* $end */ ritem[3] = -2; /* -2:第二条规则,即用户的第一条规则 */ rlhs[0] = 0; rlhs[1] = 0; rlhs[2] = start_symbol; /* $accept */ rrhs[0] = 0; rrhs[1] = 0; rrhs[2] = 1; /* ritem[1] 就是 goal */
j = 4; /* rlhs[i]: ritem[j], ritem[j+1], -i * 这样就记录好所有的规则 */ for (i = 3; i < nrules; ++i) { rlhs[i] = plhs[i]->index; /* read_grammar 把所有规则的左边都放在plhs中 */ rrhs[i] = j; /* j对应于read_grammar依次读到的右边的索引 */ assoc = TOKEN; prec2 = 0; while (pitem[j]) /* 该规则的所有项目*/ { /* 一个规则对应哪个项目由ritem的索引j决定 * 它是哪个符号由rimte[j]决定 */ ritem[j] = pitem[j]->index; if (pitem[j]->class == TERM) { /* 规则的结合性和优先级等于最后一个终结符项目相应的值 * 如果存在 */ prec2 = pitem[j]->prec; assoc = pitem[j]->assoc; } ++j; } ritem[j] = (Value_t) - i; ++j; /* 下一个规则的起始项目 */ if (rprec[i] == UNDEFINED) { /* 没有使用 %prec 显示指定规则的优先级和结合性 */ rprec[i] = prec2; rassoc[i] = assoc; } } rrhs[i] = j;
FREE(plhs); FREE(pitem); }
|
这个函数对读入的数据做一些处理,为接下来reader之后的自动机生成做准备
在read_grammar函数中提到的四个数组为pitem, plhs, rprec, rassoc
其中rprec和rassoc除了显示%prec指定的之外,将被赋值为规则对应的最后一个终结符的值
另外pitem和plhs需要被转化为ritem和rlhs, 因为最后需要的是方便生成自动机的整数值
四个symbol_XXX数组的索引就可代表符号,ritem 存的正是这些索引
rlhs很简单的赋值就可以
rlhs[i] = plhs[i]->index; /* read_grammar 把所有规则的左边都放在plhs中 */
|
ritem在calc.y对应的值为:
这里很容易看出来pitem为什么保留4个位置。
ritem以-rule_number是为以后方便。
另外rrhs存有规则的第一个文法符号。
print_grammar
该函数把规则打印到y.output中(-v),对于calc.y,其输出为
0 $accept : list $end
1 list : 2 | list stat '\n' 3 | list error '\n'
4 stat : expr 5 | LETTER '=' expr
6 expr : '(' expr ')' 7 | expr '+' expr 8 | expr '-' expr 9 | expr '*' expr 10 | expr '/' expr 11 | '-' expr 12 | LETTER 13 | number
14 number : DIGIT 15 | number DIGIT
|
阅读(1800) | 评论(0) | 转发(0) |