flex_bison读书笔记

0x00: 起因

工作上的一些原因需要学习一下。做个记录督促自己读书学习，好好学习。

0x01: 一些概念

语句和表达式

• 表达式（Expression）有值，而语句（Statement）不总有。

  表达式是可以被求值的代码，而语句是一段可执行代码。
  因为表达式可被求值，所以它可写在赋值语句等号的右侧。
  而语句不一定有值，所以像import、for和break等语句就不能被用于赋值。
  Python的语句分为两大类：简单和复合语句。
  简单语句是指一逻辑行的代码。例如表达式语句、赋值语句和return语句等。
  复合语句是指包含、影响或控制一组语句的代码。例如if、try和class语句等。
  表达式本身可以作为表达式语句，也能作为赋值语句的右值或if语句的条件等，所以表达式可以作为语句的组成部分，但不是必须成分（例如continue语句）。

左递归

一个文法是左递归的，若我们可以找出其中存在某非终端符号A，最终会推导出来的句型(sentential form)里面包含以自己为最左符号(left-symbol)的句型

1. 直接左递归

Expr ----> Expr + Term

举个例子：

A ---> Aa|C

2. 间接左递归

A ---> Ba|C
B ---> Ab|D

这种会产生：

A ---> Ba ---> Aba ---> ...

0x02: 高级计算器的实现

先看语法分析的部分：

$ cat fb3-2.y
/* Companion source code for "flex & bison", published by O'Reilly
 * Media, ISBN 978-0-596-15597-1
 * Copyright (c) 2009, Taughannock Networks. All rights reserved.
 * See the README file for license conditions and contact info.
 * $Header: /home/johnl/flnb/code/RCS/fb3-2.y,v 2.1 2009/11/08 02:53:18 johnl Exp $
 */
/* calculator with AST */

%{
#  include <stdio.h>
#  include <stdlib.h>
#  include "fb3-2.h"
%}

%union {
  struct ast *a;
  double d;
  struct symbol *s;        /* which symbol */
  struct symlist *sl;
  int fn;            /* which function */
}

/* declare tokens */ 表明类型
%token <d> NUMBER
%token <s> NAME
%token <fn> FUNC
%token EOL

%token IF THEN ELSE WHILE DO LET


//right、left表明了结合顺序，即优先级
%nonassoc <fn> CMP
%right '='
%left '+' '-'
%left '*' '/'
%nonassoc '|' UMINUS


//把值<a>赋值给了 stmt list explist 三者
%type <a> exp stmt list explist
//同理
%type <sl> symlist

%start calclist

%%

//语句，调用相对应的方法，生成AST
stmt: IF exp THEN list           { $$ = newflow('I', $2, $4, NULL); }
   | IF exp THEN list ELSE list  { $$ = newflow('I', $2, $4, $6); }
   | WHILE exp DO list           { $$ = newflow('W', $2, $4, NULL); }
   | exp
;

//右递归

list: /* nothing */ { $$ = NULL; }
   | stmt ';' list { if ($3 == NULL)
                    $$ = $1;
                      else
            $$ = newast('L', $1, $3);
                    }
   ;

//表达式的ast构建
exp: exp CMP exp          { $$ = newcmp($2, $1, $3); }
   | exp '+' exp          { $$ = newast('+', $1,$3); }
   | exp '-' exp          { $$ = newast('-', $1,$3);}
   | exp '*' exp          { $$ = newast('*', $1,$3); }
   | exp '/' exp          { $$ = newast('/', $1,$3); }
   | '|' exp              { $$ = newast('|', $2, NULL); }
   | '(' exp ')'          { $$ = $2; }
   | '-' exp %prec UMINUS { $$ = newast('M', $2, NULL); }
   | NUMBER               { $$ = newnum($1); }
   | FUNC '(' explist ')' { $$ = newfunc($1, $3); }
   | NAME                 { $$ = newref($1); }
   | NAME '=' exp         { $$ = newasgn($1, $3); }
   | NAME '(' explist ')' { $$ = newcall($1, $3); }
;

//表达式列表
explist: exp
 | exp ',' explist  { $$ = newast('L', $1, $3); }
;

//符号列表，用于函数调用，右递归的
symlist: NAME       { $$ = newsymlist($1, NULL); }
 | NAME ',' symlist { $$ = newsymlist($1, $3); }
;


//计算器的顶层规则

calclist: /* nothing */
  | calclist stmt EOL {
    if(debug) dumpast($2, 0);
     printf("= %4.4g\n> ", eval($2));
     treefree($2);
    }
    //识别一个函数声明 let xxx() = xxx 这样的
  | calclist LET NAME '(' symlist ')' '=' list EOL {
                       dodef($3, $5, $8);
                       printf("Defined %s\n> ", $3->name); }

  | calclist error EOL { yyerrok; printf("> "); }
 ;
%%

词法分析部分：

$ cat fb3-2.l
/* Companion source code for "flex & bison", published by O'Reilly
 * Media, ISBN 978-0-596-15597-1
 * Copyright (c) 2009, Taughannock Networks. All rights reserved.
 * See the README file for license conditions and contact info.
 * $Header: /home/johnl/flnb/code/RCS/fb3-2.l,v 2.1 2009/11/08 02:53:18 johnl Exp $
 */
/* recognize tokens for the calculator */

%option noyywrap nodefault yylineno
%{
# include "fb3-2.h"
# include "fb3-2.tab.h"
%}

/* float exponent */ 浮点数，e开头，正负，这是指数部分
EXP    ([Ee][-+]?[0-9]+)


//操作符单操作数
%%
 /* single character ops */
"+" |
"-" |
"*" |
"/" |
"=" |
"|" |
"," |
";" |
"(" |
")"     { return yytext[0]; }

//双操作数操作符
 /* comparison ops */
">"     { yylval.fn = 1; return CMP; }
"<"     { yylval.fn = 2; return CMP; }
"<>"    { yylval.fn = 3; return CMP; }
"=="    { yylval.fn = 4; return CMP; }
">="    { yylval.fn = 5; return CMP; }
"<="    { yylval.fn = 6; return CMP; }


//关键字
 /* keywords */

"if"    { return IF; }
"then"  { return THEN; }
"else"  { return ELSE; }
"while" { return WHILE; }
"do"    { return DO; }
"let"   { return LET;}

//内建的一些函数
 /* built in functions */
"sqrt"  { yylval.fn = B_sqrt; return FUNC; }
"exp"   { yylval.fn = B_exp; return FUNC; }
"log"   { yylval.fn = B_log; return FUNC; }
"print" { yylval.fn = B_print; return FUNC; }

 /* debug hack */
"debug"[0-9]+ { debug = atoi(&yytext[5]); printf("debug set to %d\n", debug); }

//声明的函数的函数名，字母开头
 /* names */
[a-zA-Z][a-zA-Z0-9]*  { yylval.s = lookup(yytext); return NAME; }

//浮点数
[0-9]+"."[0-9]*{EXP}? |
"."?[0-9]+{EXP}? { yylval.d = atof(yytext); return NUMBER; }

//其他的符号
"//".*
[ \t]   /* ignore white space */
\\\n    printf("c> "); /* ignore line continuation */
"\n"    { return EOL; }

.    { yyerror("Mystery character %c\n", *yytext); }
%%

函数实现，构造ast什么的：

$ cat fb3-2funcs.c
/* Companion source code for "flex & bison", published by O'Reilly
 * Media, ISBN 978-0-596-15597-1
 * Copyright (c) 2009, Taughannock Networks. All rights reserved.
 * See the README file for license conditions and contact info.
 * $Header: /home/johnl/flnb/code/RCS/fb3-2funcs.c,v 2.1 2009/11/08 02:53:18 johnl Exp $
 */
/*
 * helper functions for fb3-2
 */
#  include <stdio.h>
#  include <stdlib.h>
#  include <stdarg.h>
#  include <string.h>
#  include <math.h>
#  include "fb3-2.h"


//这些是辅助函数：构造符号表、hash算法、查找

/* symbol table */
/* hash a symbol */
static unsigned
symhash(char *sym)
{
  unsigned int hash = 0;
  unsigned c;

  while(c = *sym++) hash = hash*9 ^ c;

  return hash;
}

struct symbol *
lookup(char* sym)
{
  struct symbol *sp = &symtab[symhash(sym)%NHASH];
  int scount = NHASH;        /* how many have we looked at */

  while(--scount >= 0) {
    if(sp->name && !strcmp(sp->name, sym)) { return sp; }

    if(!sp->name) {        /* new entry */
      sp->name = strdup(sym);
      sp->value = 0;
      sp->func = NULL;
      sp->syms = NULL;
      return sp;
    }

    if(++sp >= symtab+NHASH) sp = symtab; /* try the next entry */
  }
  yyerror("symbol table overflow\n");
  abort(); /* tried them all, table is full */

}


//这是构造ast的函数，根据参数，填充ast的结构。
//填充 type，节点什么的

struct ast *
newast(int nodetype, struct ast *l, struct ast *r)
{
  struct ast *a = malloc(sizeof(struct ast));

  if(!a) {
    yyerror("out of space");
    exit(0);
  }
  a->nodetype = nodetype;
  a->l = l;
  a->r = r;
  return a;
}

//number的ast
struct ast *
newnum(double d)
{
  struct numval *a = malloc(sizeof(struct numval));

  if(!a) {
    yyerror("out of space");
    exit(0);
  }
  a->nodetype = 'K';
  a->number = d;
  return (struct ast *)a;
}

//比较表达式的ast
struct ast *
newcmp(int cmptype, struct ast *l, struct ast *r)
{
  struct ast *a = malloc(sizeof(struct ast));

  if(!a) {
    yyerror("out of space");
    exit(0);
  }
  a->nodetype = '0' + cmptype;
  a->l = l;
  a->r = r;
  return a;
}

//函数的ast
struct ast *
newfunc(int functype, struct ast *l)
{
  struct fncall *a = malloc(sizeof(struct fncall));

  if(!a) {
    yyerror("out of space");
    exit(0);
  }
  a->nodetype = 'F';
  a->l = l;
  a->functype = functype;
  return (struct ast *)a;
}

//调用的ast
// call funcname();这种
struct ast *
newcall(struct symbol *s, struct ast *l)
{
  struct ufncall *a = malloc(sizeof(struct ufncall));

  if(!a) {
    yyerror("out of space");
    exit(0);
  }
  a->nodetype = 'C';
  a->l = l;
  a->s = s;
  return (struct ast *)a;
}

//引用的ast
struct ast *
newref(struct symbol *s)
{
  struct symref *a = malloc(sizeof(struct symref));

  if(!a) {
    yyerror("out of space");
    exit(0);
  }
  a->nodetype = 'N';
  a->s = s;
  return (struct ast *)a;
}

//赋值表达式 ast
struct ast *
newasgn(struct symbol *s, struct ast *v)
{
  struct symasgn *a = malloc(sizeof(struct symasgn));

  if(!a) {
    yyerror("out of space");
    exit(0);
  }
  a->nodetype = '=';
  a->s = s;
  a->v = v;
  return (struct ast *)a;
}

//条件表达式的ast
struct ast *
newflow(int nodetype, struct ast *cond, struct ast *tl, struct ast *el)
{
  struct flow *a = malloc(sizeof(struct flow));

  if(!a) {
    yyerror("out of space");
    exit(0);
  }
  a->nodetype = nodetype;
  a->cond = cond;
  a->tl = tl;
  a->el = el;
  return (struct ast *)a;
}


//符号list
struct symlist *
newsymlist(struct symbol *sym, struct symlist *next)
{
  struct symlist *sl = malloc(sizeof(struct symlist));

  if(!sl) {
    yyerror("out of space");
    exit(0);
  }
  sl->sym = sym;
  sl->next = next;
  return sl;
}

//释放符号list
void
symlistfree(struct symlist *sl)
{
  struct symlist *nsl;

  while(sl) {
    nsl = sl->next;
    free(sl);
    sl = nsl;
  }
}

//定义一个函数
//func(parma1,parma2…);
/* define a function */
void
dodef(struct symbol *name, struct symlist *syms, struct ast *func)
{
  if(name->syms) symlistfree(name->syms);
  if(name->func) treefree(name->func);
  name->syms = syms;
  name->func = func;
}

static double callbuiltin(struct fncall *);
static double calluser(struct ufncall *);

//ast求值
double
eval(struct ast *a)
{
  double v;

  if(!a) {
    yyerror("internal error, null eval");
    return 0.0;
  }

  switch(a->nodetype) {
    /* constant */
  case 'K': v = ((struct numval *)a)->number; break;

    /* name reference */
  case 'N': v = ((struct symref *)a)->s->value; break;

    /* assignment */
  case '=': v = ((struct symasgn *)a)->s->value =
      eval(((struct symasgn *)a)->v); break;

    /* expressions */
  case '+': v = eval(a->l) + eval(a->r); break;
  case '-': v = eval(a->l) - eval(a->r); break;
  case '*': v = eval(a->l) * eval(a->r); break;
  case '/': v = eval(a->l) / eval(a->r); break;
  case '|': v = fabs(eval(a->l)); break;
  case 'M': v = -eval(a->l); break;

    /* comparisons */
  case '1': v = (eval(a->l) > eval(a->r))? 1 : 0; break;
  case '2': v = (eval(a->l) < eval(a->r))? 1 : 0; break;
  case '3': v = (eval(a->l) != eval(a->r))? 1 : 0; break;
  case '4': v = (eval(a->l) == eval(a->r))? 1 : 0; break;
  case '5': v = (eval(a->l) >= eval(a->r))? 1 : 0; break;
  case '6': v = (eval(a->l) <= eval(a->r))? 1 : 0; break;

  //这部分是对条件表达式的ast的求值
  //比如if else 这些
  /* control flow */
  /* null if/else/do expressions allowed in the grammar, so check for them */
  case 'I’:
    //条件成立，走then或者do的分支
    if( eval( ((struct flow *)a)->cond) != 0) {
      if( ((struct flow *)a)->tl) {
    v = eval( ((struct flow *)a)->tl);
      } else
    v = 0.0;        /* a default value */
    //不成立，走else分支
    } else {
      if( ((struct flow *)a)->el) {
        v = eval(((struct flow *)a)->el);
      } else
    v = 0.0;        /* a default value */
    }
    break;

 // while语句
  case 'W':
    v = 0.0;        /* a default value */
    //条件成立，走do的逻辑
    if( ((struct flow *)a)->tl) {
      while( eval(((struct flow *)a)->cond) != 0)
    v = eval(((struct flow *)a)->tl);
    }
    //不成立，凉凉，啥都不做
    break;            /* last value is value */

  //语句列表
  //
  case 'L': eval(a->l); v = eval(a->r); break;
  //函数
  //func(param…);
  case 'F': v = callbuiltin((struct fncall *)a); break;
  //用户调用部分
  //比如 call xxx();
  case 'C': v = calluser((struct ufncall *)a); break;

  default: printf("internal error: bad node %c\n", a->nodetype);
  }
  return v;
}

//一些内建函数的实现，cc支持的
static double
callbuiltin(struct fncall *f)
{
  enum bifs functype = f->functype;
  double v = eval(f->l);

 switch(functype) {
 case B_sqrt:
   return sqrt(v);
 case B_exp:
   return exp(v);
 case B_log:
   return log(v);
 case B_print:
   printf("= %4.4g\n", v);
   return v;
 default:
   yyerror("Unknown built-in function %d", functype);
   return 0.0;
 }
}


//函数调用的实现，比较重要的部分。
static double
calluser(struct ufncall *f)
{
  //获取函数的信息，函数名，参数等
  struct symbol *fn = f->s;    /* function name */
  //形参
  struct symlist *sl;        /* dummy arguments */
  //实参
  struct ast *args = f->l;    /* actual arguments */
  //保存的参数
  double *oldval, *newval;    /* saved arg values */
  double v;
  int nargs;
  int i;

  if(!fn->func) {
    yyerror("call to undefined function", fn->name);
    return 0;
  }
  
  //获取参数数量，从形参列表遍历获得
  /* count the arguments */
  sl = fn->syms;
  for(nargs = 0; sl; sl = sl->next)
    nargs++;

  //为保存参数分配空间
  /* prepare to save them */
  oldval = (double *)malloc(nargs * sizeof(double));
  newval = (double *)malloc(nargs * sizeof(double));
  if(!oldval || !newval) {
    yyerror("Out of space in %s", fn->name); return 0.0;
  }
  
  //参数可能是表达式，所以需要对其求值。
  //比如 max(1+2,5) 就需要对第一个参数先求值，然后再进行计算。
  /* evaluate the arguments */
  for(i = 0; i < nargs; i++) {
    if(!args) {
      yyerror("too few args in call to %s", fn->name);
      free(oldval); free(newval);
      return 0;
    }

    if(args->nodetype == 'L') {    /* if this is a list node */
      newval[i] = eval(args->l);
      args = args->r;
    } else {            /* if it's the end of the list */
      newval[i] = eval(args);
      args = NULL;
    }
  }
  
  //保存形参的旧值，然后更新新值
  //比如 max(1+2,4-1) 更新成 max(3，3)
  /* save old values of dummies, assign new ones */
  sl = fn->syms;
  for(i = 0; i < nargs; i++) {
    struct symbol *s = sl->sym;

    oldval[i] = s->value;
    s->value = newval[i];
    sl = sl->next;
  }
  
  free(newval);

  /* evaluate the function */ //参数都更新完了之后，就可以直接去计算函数值了
  v = eval(fn->func);

  /* put the dummies back */  //因为之前更改了形参的list，现在要恢复
  sl = fn->syms;
  for(i = 0; i < nargs; i++) {
    struct symbol *s = sl->sym;

    s->value = oldval[i];
    sl = sl->next;
  }

  free(oldval);
  return v;
}


//释放节点，分情况，因为不同的操作符，子树数目不同，所以要分情况。
void
treefree(struct ast *a)
{
  switch(a->nodetype) {

    /* two subtrees */
  case '+':
  case '-':
  case '*':
  case '/':
  case '1':  case '2':  case '3':  case '4':  case '5':  case '6':
  case 'L':
    treefree(a->r);

    /* one subtree */
  case '|':
  case 'M': case 'C': case 'F':
    treefree(a->l);

    /* no subtree */
  case 'K': case 'N':
    break;

  case '=':
    free( ((struct symasgn *)a)->v);
    break;

  case 'I': case 'W':
    free( ((struct flow *)a)->cond);
    if( ((struct flow *)a)->tl) free( ((struct flow *)a)->tl);
    if( ((struct flow *)a)->el) free( ((struct flow *)a)->el);
    break;

  default: printf("internal error: free bad node %c\n", a->nodetype);
  }

  free(a); /* always free the node itself */

}

void
yyerror(char *s, ...)
{
  va_list ap;
  va_start(ap, s);

  fprintf(stderr, "%d: error: ", yylineno);
  vfprintf(stderr, s, ap);
  fprintf(stderr, "\n");
}

int
main()
{
  printf("> ");
  return yyparse();
}

//把ast dump出来做显示，方便调试
/* debugging: dump out an AST */
int debug = 0;
void
dumpast(struct ast *a, int level)
{

  printf("%*s", 2*level, "");    /* indent to this level */
  level++;

  if(!a) {
    printf("NULL\n");
    return;
  }

  switch(a->nodetype) {
    /* constant */
  case 'K': printf("number %4.4g\n", ((struct numval *)a)->number); break;

    /* name reference */
  case 'N': printf("ref %s\n", ((struct symref *)a)->s->name); break;

    /* assignment */
  case '=': printf("= %s\n", ((struct symref *)a)->s->name);
    dumpast( ((struct symasgn *)a)->v, level); return;

    /* expressions */
  case '+': case '-': case '*': case '/': case 'L':
  case '1': case '2': case '3':
  case '4': case '5': case '6':
    printf("binop %c\n", a->nodetype);
    dumpast(a->l, level);
    dumpast(a->r, level);
    return;

  case '|': case 'M':
    printf("unop %c\n", a->nodetype);
    dumpast(a->l, level);
    return;

  case 'I': case 'W':
    printf("flow %c\n", a->nodetype);
    dumpast( ((struct flow *)a)->cond, level);
    if( ((struct flow *)a)->tl)
      dumpast( ((struct flow *)a)->tl, level);
    if( ((struct flow *)a)->el)
      dumpast( ((struct flow *)a)->el, level);
    return;

  case 'F':
    printf("builtin %d\n", ((struct fncall *)a)->functype);
    dumpast(a->l, level);
    return;

  case 'C': printf("call %s\n", ((struct ufncall *)a)->s->name);
    dumpast(a->l, level);
    return;

  default: printf("bad %c\n", a->nodetype);
    return;
  }
}

0x03: 使用

测试环境 ubuntu 16.04 x64
这部分没啥意思，随便测试下就好了，主要还是看上面的代码。

# muhe @ ubuntu in ~/flexbison [20:49:52] 
$ ./fb3-2 
> 1+123
=  124
> 1
=    1
> 2
=    2
> 1.1+2
=  3.1
> 3.33333/1.2344
=  2.7
> let max(x,y) = if x >= y then x;else y;;
Defined max
> max(0.1,-0.2)
=  0.1
> max(99999999999999999999999999999999999999999,999999999999999999999999999999999999999999999999999999999999999999999999999)
= 1e+75
> 

设置了debug之后可以看到ast，方便调试：

> let max(x,y) = if x >= y then x;else y;;
Defined max
> max(1,2)
call max
  binop L
    number    1
    number    2
=    2
> 
> 

0x04: sql分析

书中第四章是一个sql的分析器，含词法分析、语法分析，代码量还好不算特别大。

目录结构:

$ tree .
.
├── Makefile
├── glrmysql.l  #mysql子集词法分析器
├── glrmysql.y  #mysql子集语法分析器
├── lpmysql.l
├── lpmysql.y
├── pmysql.l
└── pmysql.y

*.l是词法分析部分，*.y是语法分析部分。

这里有三份代码，glrxxxxx是第四章的代码，lpmxxxx是第八章的代码，pmysqlxx是第九章的代码，这里只看第四章的代码，这个例子比较简单，简化了很多东西。

0x05: 引用

在编程概念中，表达式和语句分别是什么概念？
左递归