Bison 文法文件的基本布局

%{
Prologue
%}

Bison declarations

%%
Grammar rules
%%
Epilogue

Scanner 0.1

%{
#define YYSTYPE char *
#include "y.tab.h"
int cur_line = 1;
void yyerror(const char *msg);
void unrecognized_char(char c);
#define _DUPTEXT {yylval = strdup(yytext);}
%}

/* note \042 is '"' */

OPERATOR        ([-/+*()=,;])
INTEGER         ([0-9]+)
STRING          (\042[^\042\n]*\042)
IDENTIFIER      ([_a-zA-Z][_a-zA-Z0-9]*)
WHITESPACE      ([ \t]*)

%%
{OPERATOR}      { return yytext[0]; }
"int"           { return T_Int; }
"print"         { return T_Print; }

{INTEGER}       { _DUPTEXT; return T_IntConstant; }
{STRING}        { _DUPTEXT; return T_StringConstant; }
{IDENTIFIER}    { _DUPTEXT; return T_Identifier; }

{WHITESPACE}    { /* ignore every whitespace */ }
\n              { cur_line++; }
.               { unrecognized_char(yytext[0]); }
%%

int yywrap(void) { 
    return 1;
}

void unrecognized_char(char c) {
    char buf[32] = "Unrecognized character: ?";
    buf[24] = c;
    yyerror(buf);
}

void yyerror(const char *msg) {
    printf("Error at line %d:\n\t%s\n", cur_line, msg);
    exit(-1);
}
  • yytext 是一个 read buffer。里面存放了目前读取到的字符串。

    • 由于它是一个 buffer,所以如果要保存,则必须复制一份(使用 strdup

      #include <string.h>
      char *strdup(const char *s);
      

      注意 strdup 申请了内存。用完应该 free

  • yylval 是一个外部变量。yylex 将 token 的语义值放到 yylval,以供 parser 使用。

Parser 0.1

%{
#include <stdio.h>
#include <stdlib.h>
void yyerror(const char*);
#define YYSTYPE char *
%}

%token T_StringConstant T_IntConstant T_Identifier T_Int T_Print

%left '+' '-'
%left '*' '/'
%right U_neg

%%

S:   
    Stmt                        { /* empty */ }
|   S Stmt                      { /* empty */ }
;

Stmt:
    VarDecl ';'                 { printf("\n\n"); }
|   Assign                      { /* empty */ }
|   Print                       { /* empty */ }
;

VarDecl:
    T_Int T_Identifier          { printf("var %s", $2); }
|   VarDecl ',' T_Identifier    { printf(", %s", $3); }
;

Assign:
    T_Identifier '=' E ';'      { printf("pop %s\n\n", $1); }
;

Print:
    T_Print '(' T_StringConstant Actuals ')' ';'
                                { printf("print %s\n\n", $3); }
;

Actuals:
    /* empty */                 { /* empty */ }
|   Actuals ',' E               { /* empty */ }
;

E:
    E '+' E                     { printf("add\n"); }
|   E '-' E                     { printf("sub\n"); }
|   E '*' E                     { printf("mul\n"); }
|   E '/' E                     { printf("div\n"); }
|   '-' E %prec U_neg           { printf("neg\n"); }
|   T_IntConstant               { printf("push %s\n", $1); }
|   T_Identifier                { printf("push %s\n", $1); }
|   '(' E ')'                   { /* empty */ }
;

%%

int main() {
    return yyparse();
}
  • #define YYSTYPE char * 用于规定语义值的数据类型。默认是 int ,这里改成了 char *

  • %token 用于声明 Token 列表。它们是 yylex 的返回值。

  • %left 用于规定运算符左结合。

对于 A op B op C,左结合相当于 (A op B) op C,右结合相当于 A op (B op C)

  • %prec 修饰符用于声明特定规则的优先级。基本也就只有负数修饰这一种用法,学着用就行了。

  • `

$$ `表示将要构造的语义值。`$1`,`$2` 表示分析栈中的语义值,数字越小约靠近栈顶。当然,用的时候其实很简单。你可以当成模板占位符。
exp = exp &#x27;+&#x27; exp   {
$$
</div>
 = $1 + $3; }
  // 
<div class="lb-math">
$$
$1  $2  $3
exp = &#x27;(&#x27; exp &#x27;)&#x27;   {
$$
</div>
 = $2; }
  // $$  $!  $2  $3

Lexer 和 Parser 间的调用惯例

yylex 的返回值代表 TOKEN 的编码。非正值表示输入结束。

参考

Bison 3.8.1 (gnu.org)

更新于 Jan 14, 2022 22:16 CST
如果有任何问题或者需要反馈文章的错误,欢迎您在此评论。