byacc 笔记一 reader

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