吾生也有涯，而知也无涯，能学一点算一点…
如果手动安装的话，那还比较简单，基本上点点就可以了。但是如果使用Terraform自动化安装AlmaLinux，则比想象的要复杂。这个复杂度对于所以云市场（MarketPlace）的资源都有类似的问题：需要先在Terraform脚本中同意相关协议才能够安装，这是复杂度的主要原因。
这里给出示例，供参考。
Name和OCIDOCID是Oracle Cloud上所有云资源的唯一标识符。每一个OS镜像也都有一个OCID。在官网页面上，也只是列出小部分Oracle镜像，以及对应的OCID：参考All Image Families。但是，对于大量来自其云市场（MarketPlace）的镜像，这里是查不到的，即便在云市场能够查到，也并没有给出OCID。
在使用梯度下降法进行回归时，需要频繁的进行偏导数的计算。在很多的相关介绍中会展示使用计算图进行偏导数的计算。这里简述对该方法的一些理解。
这里对求导的链式法则的典型形式做一个简单的回顾。
在对复杂的表达式求导/微分时，有时候看起来会很复杂。如果能够灵活的使用链式法则可以巧妙将复杂函数的求导转换为简单函数的求导。
$$
f(x) = g(h(x))
\\
f'(x) = \frac{\partial f}{\partial x} = \frac{\partial g}{\partial h} \frac{\partial h}{\partial x}
$$
例如，使用该法则可以很简单对如下函数求导：
$$
f(x) = e^{(x^2)}
\\
g(h) = e^h \, h(x) = x^2
\\
f'(x) = \frac{\partial g}{\partial h} \frac{\partial h}{\partial x} = e^h * 2 * x = 2x*e^h = 2xe^{x^2}
$$
如果使用计算图的方式表达如上的求导，如下：
$$
f(x) = f(g(x))
\\
\frac{\partial f}{\partial x} = \frac{\partial f}{\partial g}\frac{\partial g}{\partial h}
$$
所以：在计算图中，在一个单向路径上的算子，求导时，将各个导数相乘即可。
(more…)这是一个系列文章，旨在了解如何使用Flex/Lex和Yacc/Bison进行词法和语法解析。在前面，已经完成了使用Lex/flex做基础的词法解析、实现一个简单的计算器、flex/bison系列3：更复杂的一个编译程序实现（上）。在上篇中，已经完成语法规则、主要的数据结构设计。这里就继续完成程序，最后编译测试。
目录
这个系列我们需要通过flex/bison实现一个编译程序，能够实现一种简单的程序语言，这个程序语言包含了：基础运算、变量与赋值、表达式计算、if语句、while语句、print语句等。例如，使用该程序语言，我们可以实现如下程序：
i = 1;
a = 0;
while ( a < 100 ) {
i = i + 1;
a = a + i;
}
print i;该程序解决的问题是：在自然数序列（1、2、4…）中，前面多少个自然数的和首次大于100。你可以使用上面定义的语言，编写自己的程序。
好了，接着前面三篇的内容，我们继续完成该语言的编译程序。
t_node* build_node(enum NODETYPE nt,t_node* left,t_node* right, int i){
debug_print(__FILE__,__LINE__,__func__,"");
t_node *t_n;
t_n = NULL;
t_n = (t_node *)malloc(sizeof(t_node));
if (t_n == NULL){
printf("Out of Memory\n");
exit(1);
}
t_n->nt = nt;
t_n->left = left;
t_n->right = right;
t_n->i = i;
return t_n;
}int exec_node(t_node *n){
if( n == NULL ) return 0;
debug_print(__FILE__,__LINE__,__func__,"enter exec_node");
switch(n->nt){
case NT_INTEGER:
debug_print(__FILE__,__LINE__,__func__,"NT_INTEGER node");
break;
case NT_VAR_NAME:
debug_print(__FILE__,__LINE__,__func__,"NT_VAR_NAME node");
break;
case NT_O_ADD:
exec_node(n->left);
exec_node(n->right);
n->i = get_node_ret(n->left) + get_node_ret(n->right);
debug_print(__FILE__,__LINE__,__func__,"NT_O_ADD node");
break;
case NT_O_MINUS:
exec_node(n->left);
exec_node(n->right);
n->i = get_node_ret(n->left) - get_node_ret(n->right);
debug_print(__FILE__,__LINE__,__func__,"NT_O_MINUS node");
break;
case NT_O_MULTIPLY:
debug_print(__FILE__,__LINE__,__func__,"NT_O_MULTIPLY node");
exec_node(n->left);
exec_node(n->right);
n->i = get_node_ret(n->left) * get_node_ret(n->right);
break;
case NT_BOOL_EXPR_GT:
debug_print(__FILE__,__LINE__,__func__,"NT_BOOL_EXPR_GT node");
n->i = 0;
exec_node(n->left);
exec_node(n->right);
if (get_node_ret(n->left) > get_node_ret(n->right) )
{ n->i = 1 ; }
break;
case NT_BOOL_EXPR_LT:
debug_print(__FILE__,__LINE__,__func__,"NT_BOOL_EXPR_LT node");
n->i = 0;
exec_node(n->left);
exec_node(n->right);
if (get_node_ret(n->left) < get_node_ret(n->right) )
{ n->i = 1 ; }
break;
case NT_IF:
debug_print(__FILE__,__LINE__,__func__,"NT_IF node");
exec_node(n->left);
if (get_node_ret(n->left)){
exec_node(n->right);
}
break;
case NT_WHILE:
debug_print(__FILE__,__LINE__,__func__,"NT_WHILE node");
exec_node(n->left);
while( get_node_ret(n->left) ){
exec_node(n->right);
exec_node(n->left);
}
break;
case NT_PRINT:
debug_print(__FILE__,__LINE__,__func__,"NT_PRINT node");
exec_node(n->left);
printf("print '%d'",get_node_ret(n->left));
break;
case NT_ASSIGNMENT:
debug_print(__FILE__,__LINE__,__func__,"NT_ASSIGNMENT node");
exec_node(n->left);
exec_node(n->right);
var[n->left->i - 'a'] = get_node_ret(n->right);
break;
case NT_STATEMENT_BLOCK:
debug_print(__FILE__,__LINE__,__func__,"NT_STATEMENT_BLOCK node");
exec_node(n->left);
exec_node(n->right);
break;
case NT_PROGRAM:
debug_print(__FILE__,__LINE__,__func__,"NT_PROGRAM node");
break;
}
return 0;
}int free_node(t_node *n){
if( n != NULL ) {
free_node(n->left);
free_node(n->right);
}
free(n);
return 0;
}void debug_print(const char *fname, int lineno, const char *fxname, const char *debug_info){
#ifdef cal_DEBUG
printf("\n debug: enter at line %d in %s,function: %s info: %s\n",
lineno,
fname,
fxname,
debug_info
);
#endif
}%%
program: statement_block
{
exec_node($1);
free_node($1);
printf("\n job done! \n");
}
;
statement_block: %empty
{
$$ = build_node(
NT_STATEMENT_BLOCK,
NULL,
NULL,
NULL,
0
);
debug_print(__FILE__,__LINE__,__func__,"");
}
| statement_block statement
{ $$ = build_node(
NT_STATEMENT_BLOCK,
$1,
$2,
NULL,
0
);
debug_print(__FILE__,__LINE__,__func__,"");
}
;
statement: assignment { $$ = $1; }
| print_func { $$ = $1; }
| if_block { $$ = $1; }
| while_block { $$ = $1; }
;
if_block: IF '(' bool_expr ')' '{' statement_block '}'
{
$$ = build_node(
NT_IF,
$3,
$6,
NULL,
0
);
}
while_block: WHILE '(' bool_expr ')' '{' statement_block '}'
{
$$ = build_node(
NT_WHILE,
$3,
$6,
NULL,
0
);
}
assignment: VAR_NAME '=' expression ';' { $$ = build_node(
NT_ASSIGNMENT,
build_node(NT_VAR_NAME,NULL,NULL,NULL,(int)$1),
$3,
NULL,
0);
}
print_func : PRINT expression ';' { $$ = build_node(NT_PRINT,$2,NULL,NULL,0); }
bool_expr: expression GT expression { $$ = build_node(NT_BOOL_EXPR_GT,$1,$3,NULL,0);}
| expression LT expression { $$ = build_node(NT_BOOL_EXPR_LT,$1,$3,NULL,0);}
expression: INTEGER { $$ = build_node(NT_INTEGER,NULL,NULL,NULL,$1); }
| VAR_NAME { $$ = build_node(NT_VAR_NAME,NULL,NULL,NULL,(int)$1); }
| expression O_ADD expression { $$ = build_node(NT_O_ADD,$1,$3,NULL,0);}
| expression O_MINUS expression { $$ = build_node(NT_O_MINUS,$1,$3,NULL,0);}
| expression O_MULTIPLY expression { $$ = build_node(NT_O_MULTIPLY,$1,$3,NULL,0);}
%%enum NODETYPE{
NT_STATEMENT,
NT_IF,
NT_WHILE,
NT_PROGRAM,
NT_STATEMENT_BLOCK,
NT_O_ADD,
NT_O_MINUS,
NT_O_MULTIPLY,
NT_INTEGER,
NT_VAR_NAME,
NT_BOOL_EXPR_GT,
NT_BOOL_EXPR_LT,
NT_PRINT,
NT_ASSIGNMENT
};
typedef struct t_node{
enum NODETYPE nt;
struct t_node* left;
struct t_node* right;
struct t_node* rrnode;
int i; // for NT_INTEGER NT_VAR_NAME node
}t_node;有了这些信息，就可以使用NODETYPE来构建，解析树了。在每次解析到对应节点或进行Reduction时，我们在语法文件的Action部分就可以调用一个build_node函数来构建对应的节点。我们可以看看如下的程序的解析树结构：
i = 1 ;
a = 0 ;
while ( a < 100 ) {
a = a + i;
i = i + 1;
}
print i ;这个程序，可以找到，在自然数级数中，到第几项的时候，其和就超过了100。
最后是程序实现的部分，包括
cat cal.l
%{
#include "cal.tab.h"
%}
%option noyywrap
%%
[[:digit:]]+ {
yylval.a = atoi(yytext);
return INTEGER;
}
[a-z] {
yylval.c = yytext[0];
return VAR_NAME;
}
"+" { return O_ADD;};
"-" { return O_MINUS;};
"*" { return O_MULTIPLY;};
"while" {return WHILE;}
"if" {return IF;}
"print" {return PRINT;}
">" {return GT;}
"<" {return LT;}
[();={}] {return yylval.c = *yytext;}
%%cat cal.header.h
enum NODETYPE{
NT_STATEMENT,
NT_IF,
NT_WHILE,
NT_PROGRAM,
NT_STATEMENT_BLOCK,
NT_O_ADD,
NT_O_MINUS,
NT_O_MULTIPLY,
NT_INTEGER,
NT_VAR_NAME,
NT_BOOL_EXPR_GT,
NT_BOOL_EXPR_LT,
NT_PRINT,
NT_ASSIGNMENT
};
typedef struct t_node{
enum NODETYPE nt;
struct t_node* left;
struct t_node* right;
struct t_node* rrnode;
int i; // for NT_INTEGER NT_VAR_NAME node
}t_node;cat cal.y
%{
#include <stdio.h>
#include <stdlib.h>
#include "cal.tab.h"
#include "cal.header.h"
// #define cal_DEBUG 1
void debug_print(const char *fname, int lineno, const char *fxname, const char *debug_info){
#ifdef cal_DEBUG
printf("\n debug: enter at line %d in %s,function: %s info: %s\n",
lineno,
fname,
fxname,
debug_info
);
#endif
}
t_node* build_node(enum NODETYPE nt,t_node* left,t_node* right, t_node* r_right , int i){
debug_print(__FILE__,__LINE__,__func__,"");
t_node *t_n;
t_n = NULL;
t_n = (t_node *)malloc(sizeof(t_node));
if (t_n == NULL){
printf("Out of Memory\n");
exit(1);
}
t_n->nt = nt;
t_n->left = left;
t_n->right = right;
t_n->rrnode = r_right;
t_n->i = i;
return t_n;
}
int var[26];
int main (){
int yydebug=1;
yyparse();
return 0;
}
void
yyerror (char const *s)
{
fprintf (stderr, "something error: %s\n over", s);
}
int exec_node(t_node *n){
if( n == NULL ) return 0;
debug_print(__FILE__,__LINE__,__func__,"enter exec_node");
switch(n->nt){
case NT_INTEGER:
debug_print(__FILE__,__LINE__,__func__,"NT_INTEGER node");
break;
case NT_VAR_NAME:
debug_print(__FILE__,__LINE__,__func__,"NT_VAR_NAME node");
break;
case NT_O_ADD:
exec_node(n->left);
exec_node(n->right);
n->i = get_node_ret(n->left) + get_node_ret(n->right);
debug_print(__FILE__,__LINE__,__func__,"NT_O_ADD node");
break;
case NT_O_MINUS:
exec_node(n->left);
exec_node(n->right);
n->i = get_node_ret(n->left) - get_node_ret(n->right);
debug_print(__FILE__,__LINE__,__func__,"NT_O_MINUS node");
break;
case NT_O_MULTIPLY:
debug_print(__FILE__,__LINE__,__func__,"NT_O_MULTIPLY node");
exec_node(n->left);
exec_node(n->right);
n->i = get_node_ret(n->left) * get_node_ret(n->right);
break;
case NT_BOOL_EXPR_GT:
debug_print(__FILE__,__LINE__,__func__,"NT_BOOL_EXPR_GT node");
n->i = 0;
exec_node(n->left);
exec_node(n->right);
if (get_node_ret(n->left) > get_node_ret(n->right) )
{ n->i = 1 ; }
break;
case NT_BOOL_EXPR_LT:
debug_print(__FILE__,__LINE__,__func__,"NT_BOOL_EXPR_LT node");
n->i = 0;
exec_node(n->left);
exec_node(n->right);
if (get_node_ret(n->left) < get_node_ret(n->right) )
{ n->i = 1 ; }
break;
case NT_IF:
debug_print(__FILE__,__LINE__,__func__,"NT_IF node");
exec_node(n->left);
if (get_node_ret(n->left)){
exec_node(n->right);
}
break;
case NT_WHILE:
debug_print(__FILE__,__LINE__,__func__,"NT_WHILE node");
exec_node(n->left);
while( get_node_ret(n->left) ){
exec_node(n->right);
exec_node(n->left);
}
break;
case NT_PRINT:
debug_print(__FILE__,__LINE__,__func__,"NT_PRINT node");
exec_node(n->left);
printf("print '%d'",get_node_ret(n->left));
break;
case NT_ASSIGNMENT:
debug_print(__FILE__,__LINE__,__func__,"NT_ASSIGNMENT node");
exec_node(n->left);
exec_node(n->right);
var[n->left->i - 'a'] = get_node_ret(n->right);
break;
case NT_STATEMENT_BLOCK:
debug_print(__FILE__,__LINE__,__func__,"NT_STATEMENT_BLOCK node");
exec_node(n->left);
exec_node(n->right);
break;
case NT_PROGRAM:
debug_print(__FILE__,__LINE__,__func__,"NT_PROGRAM node");
break;
}
return 0;
}
int get_node_ret(t_node *n){
int r = n->i;
switch(n->nt){
case NT_VAR_NAME:
r = var[n->i - 'a'];
break;
}
return r;
}
int free_node(t_node *n){
if(n != NULL){
// printf("\n try to free memory of node %d \n",n->nt);
}
return 0;
}
%}
%union {
int a; // for integer
char c; // for var_name
int int_bool; // for bool_expr
struct t_node* t_n;
}
%type <t_n> expression bool_expr print_func assignment
%type <t_n> while_block statement statement_block if_block
%token <c> VAR_NAME
%token <a> INTEGER
%token O_ADD O_MINUS O_MULTIPLY
%token GT LT
%token WHILE IF
%token PRINT
%left O_ADD O_MINUS
%left O_MULTIPLY
%%
program: statement_block
{
exec_node($1);
free_node($1);
printf("\n job done! \n");
}
;
statement_block: %empty
{
$$ = build_node(
NT_STATEMENT_BLOCK,
NULL,
NULL,
NULL,
0
);
debug_print(__FILE__,__LINE__,__func__,"");
}
| statement_block statement
{ $$ = build_node(
NT_STATEMENT_BLOCK,
$1,
$2,
NULL,
0
);
debug_print(__FILE__,__LINE__,__func__,"");
}
;
statement: assignment { $$ = $1; }
| print_func { $$ = $1; }
| if_block { $$ = $1; }
| while_block { $$ = $1; }
;
if_block: IF '(' bool_expr ')' '{' statement_block '}'
{
$$ = build_node(
NT_IF,
$3,
$6,
NULL,
0
);
}
while_block: WHILE '(' bool_expr ')' '{' statement_block '}'
{
$$ = build_node(
NT_WHILE,
$3,
$6,
NULL,
0
);
}
assignment: VAR_NAME '=' expression ';' { $$ = build_node(
NT_ASSIGNMENT,
build_node(NT_VAR_NAME,NULL,NULL,NULL,(int)$1),
$3,
NULL,
0);
}
print_func : PRINT expression ';' { $$ = build_node(NT_PRINT,$2,NULL,NULL,0); }
bool_expr: expression GT expression { $$ = build_node(NT_BOOL_EXPR_GT,$1,$3,NULL,0);}
| expression LT expression { $$ = build_node(NT_BOOL_EXPR_LT,$1,$3,NULL,0);}
expression: INTEGER { $$ = build_node(NT_INTEGER,NULL,NULL,NULL,$1); }
| VAR_NAME { $$ = build_node(NT_VAR_NAME,NULL,NULL,NULL,(int)$1); }
| expression O_ADD expression { $$ = build_node(NT_O_ADD,$1,$3,NULL,0);}
| expression O_MINUS expression { $$ = build_node(NT_O_MINUS,$1,$3,NULL,0);}
| expression O_MULTIPLY expression { $$ = build_node(NT_O_MULTIPLY,$1,$3,NULL,0);}
%%lex cal.l && \
bison -d cal.y && \
gcc cal.tab.c lex.yy.c -o a.out && \
./a.out < p.f.txt最后，需要注意，该程序更注重的是测试与实现，所以在“内存释放”可能会存在一些泄露的问题。
这是一个系列文章，旨在了解如何使用Flex/Lex和Yacc/Bison进行词法和语法解析。在前面，已经完成了使用Lex/flex做基础的词法解析、实现一个简单的计算器。开始这个系列的第三部分，使用flex和bison完成一个更加复杂的的编译程序。整体上有一定的复杂度，所以分上下篇分别介绍。上篇介绍：实现概要、语法、，下篇介绍数据结构与实现（包括解析树实现、执行）。
在前面的案例中，我们实现了一个简单的加减乘运算的计算器程序。这里我们尝试实现一个更复杂一些的编译程序，语法能够支持如下内容：
我们用这几个能力，可以编写如下的程序：
i = 1;
a = 0;
while ( a < 100 ) {
i = i + 1;
a = a + i;
}
print i;这个程序实现了一个简单的功能，解决的问题是：在自然数序列（1、2、4…）中，前面多少个自然数的和首次大于100。你可以使用上面的命令编写其他的任意程序。
如果只是使用前面的指令，似乎难以实现对if/while语句的支持。这里，就需要使用典型的编译与执行思路了，先使用语法解析构建一个“语法树”（也叫“解析树”），然后再执行该解析树。具体的，一些设计如下：
int * var[26]）存储变量，因为在前面限制了变量名只能是[a-z]typedef struct t_node{
enum NODETYPE nt;
struct t_node* left;
struct t_node* right;
int i; // for NT_INTEGER NT_VAR_NAME node
}t_node;这里为了简化：
在开始实现与执行解析树之前，我们先定义语法规则，以支持赋值、if、while、print等语法。语法规则定义时，需要注意尽量避免出现shift/reduce冲突，并且这里的语法规则不包含Action部分：
//start symbol
program:
| program statement_block { printf("\n job done! \n"); }
;
statement_block:
| statement_block statement
;
statement: assignment
| print_func
| if_block
| while_block
;
while_block: WHILE '(' bool_expr ')' '{' statement_block '}'
if_block: IF '(' bool_expr ')' '{' statement_block '}'
assignment: VAR_NAME '=' expression ';'
print_func : PRINT expression ';'
| PRINT VAR_NAME ';'
bool_expr: expression GT expression
| expression LT expression
expression: INTEGER
| VAR_NAME
| expression O_ADD expression
| expression O_MINUS expression
| expression O_MULTIPLY expressiont_node.a 存储的是具体的整数t_node.aexpression对应的语法规则如下
expression: INTEGER
| VAR_NAME
| expression O_ADD expression
| expression O_MINUS expression
| expression O_MULTIPLY expression那么，再看看O_ADD O_MINUS O_MULTIPLY这类节点：
t_node.a中bool_expr: expression GT expression
| expression LT expression NT_BOOL_EXPR 这个节点实现一个打印整数值的功能，参数可以是一个变量，也可以是一个表达式：
print_func : PRINT expression ';'
| PRINT VAR_NAME ';' NODETYPE为 NT_PRINT_FUNC expression的结果值assignment: VAR_NAME '=' expression ';'赋值语句左边是变量名，这里定义是[a-z]，右边是一个表达式，语句以分号结束。
VAR_NAME ，右子节点为 expression while_block: WHILE '(' bool_expr ')' '{' statement_block '}'bool_expr 右子节点为 : statement_blockbool_expr的真假，再决定是否执行右子节点。这里需要注意，每次获取bool_expr的时候，都需要先执行一次该节点。if_block: IF '(' bool_expr ')' '{' statement_block '}'statement: assignment
| print_func
| if_block
| while_block可以看到，statement由assignment、print_func、if_block、while_block是这些中的任何一个。所以，在实际构建中，并不会有该节点。与expression类似。
statement_block:
| statement_block statement
;program:
| program statement_block { printf("\n job done! \n"); }
;build_node：构建当前语法规则的节点，该函数返回当前构建出来节点的指针，通常也是各个语法规则Action部分的返回值。t_node* build_node(
enum NODETYPE nt,
t_node* left,
t_node* right,
int i)exec_node：执行某个节点，并执行其左/右子节点（如果存在的话）。不同的节点的执行操作会有一些不同，例如：
if节点需要做一些判断，再决定是否执行；while节点则需要循环bool_expr以决定是否执行某段代码。各类节点的exec操作可以参考上一节的详细描述。该函数定义如下
int exec_node(t_node *n)typedef struct t_node{
enum NODETYPE nt;
struct t_node* left;
struct t_node* right;
struct t_node* rrnode;
int i; // for NT_INTEGER NT_VAR_NAME node
}t_node;enum NODETYPE{
NT_STATEMENT,
NT_IF,
NT_WHILE,
NT_PROGRAM,
NT_STATEMENT_BLOCK,
NT_O_ADD,
NT_O_MINUS,
NT_O_MULTIPLY,
NT_INTEGER,
NT_VAR_NAME,
NT_BOOL_EXPR_GT,
NT_BOOL_EXPR_LT,
NT_PRINT,
NT_ASSIGNMENT
};下一篇，我们将基于此完成完整的代码。
补充完整的语法文件cal.y
包括：
%{
// 入口函数
#include <stdio.h>
int main (){
yyparse();
return 0;
}
enum NODETYPE{
NT_PROGRAM,
NT_STATEMENT_BLOCK,
NT_STATEMENT,
NT_IF,
NT_WHILE,
NT_O_ADD,
NT_O_MINUS,
NT_O_MULTIPLY,
NT_INTEGER,
NT_VAR_NAME
};
typedef struct t_node{
enum NODETYPEP nt;
t_node * left;
t_node * right;
t_node * rrnode;
YYSTYPE yval;
}t_node;
//递归执行整个parser tree
int exec_node(t_node *n){
return 0;
}
int var[26];
%}
// 定义YYSTYPE
%union {
int a; // for integer
char c; // for var_name
bool b; // for bool_expr
}
// 定义Token
%token <c> VAR_NAME
%token <a> INTEGER
%token O_ADD O_MINUS O_MULTIPLY
%token GT LT
%token WHILE IF
%token PRINT
// 定义运算符
%left O_ADD O_MINUS
%left O_MULTIPLY
%{
#include "cal.tab.h"
%}
%option noyywrap
%%
[[:digit:]]+ {
yylval.a = atoi(yytext);
return INTEGER;
}
[a-z] {
yylval.c = yytext[0];
return VAR_NAME;
}
"+" { return O_ADD;};
"-" { return O_MINUS;};
"*" { return O_MULTIPLY;};
"while" {return WHILE;}
"if" {return IF;}
"print" {return PRINT;}
">" {return GT;}
"<" {return LT;}
[();={}] {return yylval.c = *yytext;}
%%lex cal.l
bison -d cal.y
gcc cal.tab.c lex.yy.c -o a.out
bison -W -d cal.y
cal.y:62.8: warning: empty rule without %empty [-Wempty-rule]
program:
^
cal.y:66.16: warning: empty rule without %empty [-Wempty-rule]
statement_block:
^
cal.y: warning: 6 shift/reduce conflicts [-Wconflicts-sr]错误1：这里的 PRINT expression ‘;’ PRINT VAR_NAME ‘;’ 是有包含关系，重复的。因为VAR_NAME本身也是一个expression。故修改如下：
print_func : PRINT expression ';'
| PRINT VAR_NAME ';'
expression: INTEGER
| VAR_NAME
| expression O_ADD expression
| expression O_MINUS expression
| expression O_MULTIPLY expression疑问与思考：左边/右边的表达有什么不同。（注意，左边的表达会报shift/reduce conflict）
program:
| program statement_block
;
statement_block:
| statement_block statement
;
statement: assignment
| print_func
| if_block
| while_block
;program: statement_block
;
statement_block:
| statement_block statement
;
statement: assignment
| print_func
| if_block
| while_block
;%%
program: statement_block { printf("\n job done! \n");}
;
statement_block:
| statement_block statement
;
statement: assignment
| print_func
| if_block
| while_block
;
if_block: IF '(' bool_expr ')' '{' statement_block '}'
while_block: WHILE '(' bool_expr ')' '{' statement_block '}'
assignment: VAR_NAME '=' expression ';'
print_func : PRINT expression ';'
bool_expr: expression GT expression
| expression LT expression
expression: INTEGER
| VAR_NAME
| expression O_ADD expression
| expression O_MINUS expression
| expression O_MULTIPLY expression
这是一个系列文章，旨在了解如何使用Flex/Lex和Yacc/Bison进行词法和语法解析。在前面，已经完成了使用Lex/flex做基础的词法解析。接着，开始这个系列的第二部分，使用flex和bison完成一个简单的计算器。
为了简化实现，将注意力放在简单flex和bison使用上，这里对计算器做了几个简化：
也就是该程序可以计算加法、减法、乘法，以及他们的任意组合，如： 3+4、 3+4*2、 3+4*2-3、 3+4*2-3*2
后续，还将考虑增加更急复杂的计算器，包括：
这里先从简单的开始。
这是在vim中写出的第一遍代码，包含了词法文件cal.l和语法文件cal.y，详细如下。这其中当然是有很多错误的，之所以，依旧写出来，是为了和正确代码对比，以此看看对哪些概念理解有偏差。如果你是找一个正确例子的话，可以跳过这一段。
%{
#inlcude <stdlib.h>
%}
/* 十进制整数 */
%token INTEGER
%union {
int a;
}
/* 操作符 + - * / */
%token OPERATOR
%%
program:
program expression \n { printf("%d",$2); } // 这里就是以回车结尾，也可以考虑使用 = 结尾
|
expression:
INTEGER
| expression '+' expression {$$ = $1 + $2}
| expression '-' expression {$$ = $1 - $2}
| expression '*' expression {$$ = $1 * $2}
dec_integer:
INTEGER
{
$$ = $1.a;
}这里也有几个已知的问题，例如：运算符的优先级没有定义，也就说4+3*2可能会算成14。没错，如果眼尖的话，还发现有一些拼写错误。
接着是cal.l文件：
#inlcude <stdlib.h>
#include "y.tab.h"
%}
[:digit:]+ {
yylval.a = atoi(yytext)
RETURN INTEGER;
}当然，这里面有很多的错误。一会儿来看后面正确的内容。
t.col < 2 or t.col < 11 and t.col > 4 是什么意思：-- 猜测一下，如下的 SELECT 查询是否能够返回记录：
CREATE TABLE t(col INT);
INSERT INTO t values (1);
WHERE t.col < 2 or t.col < 11 and t.col > 4扯远了，再回到cal.y文件，优先级和结合律需要进行如下修改，以定义”*”优先级高于”+”、”-“：
%left '+' '-'
%left '*'这里的代码先后，就定义了优先级；优先级越高，定义在越在后面；left表示，左结合。
'\n' 。%token <a> INTEGER
%type <a> expression完成这样的定义后，在lex的文件cal.l中，就可以对yylval进行赋值，如：yylval.a = atoi(yytext); 这时，对于yacc文件中cal.y，如果引用这个TOKEN，就可以使用$1（或者是$2、$3）来引用lex解析后的返回值，如：expression: INTEGER { $$ = $1;}。
cat cal.y
...
%token O_ADD O_MINUS O_MULTIPLY O_EQ
%left O_ADD O_MINUS
%left O_MULTIPLY
%token <a> INTEGER
%type <a> expression
...
cat cal.l
...
"=" { return O_EQ;};
"+" { return O_ADD;};
"-" { return O_MINUS;};
"*" { return O_MULTIPLY;};
...cal.tab.c:(.text+0x53b): undefined reference to `yyerror'按照文档，可以定义一个最简单的yerror函数（参考：The Error Reporting Function yyerror），如下：
void
yyerror (char const *s)
{
fprintf (stderr, "something error: %s\n over", s);
}补充一个main入口函数，修改cal.l、cal.y即可。
修正后的cal.l
%{
#include "cal.tab.h"
#include <stdio.h>
%}
%option noyywrap
%%
[0-9]+ {
yylval.a = atoi(yytext);
return INTEGER;
}
"=" { return O_EQ;};
"+" { return O_ADD;};
"-" { return O_MINUS;};
"*" { return O_MULTIPLY;};
%%修正后的cal.y
%{
#include <stdlib.h>
#include <stdio.h>
int main(){
yyparse();
}
void
yyerror (char const *s)
{
fprintf (stderr, "something error: %s\n over", s);
}
%}
%union {
int a;
}
%token O_ADD O_MINUS O_MULTIPLY O_EQ
%token <a> INTEGER
%left O_ADD O_MINUS
%left O_MULTIPLY
%type <a> expression
%%
program:
|
program expression O_EQ { printf("result is : %d",$2); }
;
expression:
INTEGER { $$ = $1;}
| expression O_ADD expression {$$ = $1 + $3; }
| expression O_MINUS expression {$$ = $1 - $3; }
| expression O_MULTIPLY expression {$$ = $1 * $3;}
;然后，就可以生成c文件并编译可执行文件了：
lex cal.l
bison -d cal.y
gcc cal.tab.c lex.yy.c -o a.out
./a.out
4+3*2=
也可以像这样：
lex cal.l && bison -d cal.y && gcc cal.tab.c lex.yy.c -o a.out && ./a.out%{ // %{ ... %} 包含了完整的C语言代码
#include <stdlib.h> // 这里包含需要的头文件、入口函数main
#include <stdio.h> // 以及一个简答的yyerror函数
int main(){
yyparse();
}
void
yyerror (char const *s)
{
fprintf (stderr, "something error: %s\n over", s);
}
%}
%union { // 这是一个非常重要的联合体，用于定义
int a; // 各种不同类型的Token所返回的数据
} // 广泛的被yylex使用，并用于与.yy文件共享数据
// 也就是 YYSTYPE
%token O_ADD O_MINUS O_MULTIPLY O_EQ
%token <a> INTEGER // 这里表示INTEGER(这是一个被lex识别的token）
// INTEGER（被lex识别的token返回值为YYSTYPE.a
%left O_ADD O_MINUS // 这里定义 + -为左结合律
%left O_MULTIPLY // 这里定义 * 为左结合律，并且优先级高于 + -
%type <a> expression // 这里定义语法规则(grammer rule)expression
// 的返回值为 YYSTYPE.a
%%
program: // 这是start symbol，所有的program都需要符合该定义
|
program expression O_EQ { printf("result is : %d",$2); }
;
expression:
INTEGER { $$ = $1;}
| expression O_ADD expression {$$ = $1 + $3; }
| expression O_MINUS expression {$$ = $1 - $3; }
| expression O_MULTIPLY expression {$$ = $1 * $3;}
;这是一个系列文章，旨在了解如何使用Flex/Lex和Yacc/Bison进行词法和语法解析。这个系列，分成了几个部分，包括
了解这个系列需要一定的编译原理知识作为背景知识，了解程序如何从字符串先解析成Token，而后使用语法解析器生成解析树，最后执行该解析树。
lex/flex可以按照“词法文件”的定义，将文本解析成单个的Token，然后通过执行“词法文件”中定义的Action来完成一些操作，一般，flex的输出会通过函数/变量将结果传递给yacc/bison进行进一步的语法解析。为了简化，本文将仅通过独立的“词法文件”完成一些操作，以了解flex的基础使用。
这里完成的程序是一个简单的“count”程序，输入是一个文件，程序输出文件中包含的字符数、词语数、以及行数。
1. 安装lex： yum/apt-get install flex
2. 编写如下词法文档：
%{ //
int characters = 0; // %{ ... }% 之间的部分是"Declarations"
int words = 0; // Declarations 部分声明的变量，是可以在全局使用的
int lines = 0; // 例如，在该示例的main程序中，就通过extern声明的方式
%} // 使用了这些变量
%% //
\n { // 从这里开始是Translations阶段
++lines; // 这里定了Token，以及遇到了Token之后
++characters; // 应该采取/执行什么，例如这里遇到了\n字符
} // 则，将lines/characters变量都加1
[ \t]+ characters += yyleng; //
[^ \t\n]+ { // 注释部分的文本需要删除，程序才能正常编译
++words; // 删除注释的vim命令：1,$s/\/\/.*$//g
characters += yyleng; //
} //
//
%%直接使用如上代码的话，后面就会在gcc编译的时候遇到如下错误：
$ lex zzx.l
$ gcc lex.yy.c wc.c -o wc.out
/tmp/cc1SPYm2.o：In function yylex':
lex.yy.c:(.text+0x42f)：undefined reference toyywrap'
/tmp/cc1SPYm2.o：In function input':
lex.yy.c:(.text+0xf73)：undefined reference toyywrap'
collect2: ld returned 1 exit status
如果你也遇到了这个错误，不用担心，你并不孤单，在Stackoverflow上看到解决该失败的的答案一共有150点赞（up），就知道大家都一样了（参考@Stackoverflow）。因为默认的，lex生成的词法解析程序中，在最后是需要调用的yywrap函数的（关于yywrap），如果不打算提供该函数，则可以使用lex选项 %option noyywrap 禁用该调用。那么上面的代码就需要修改为：
$ cat zzx.l
%{
int characters = 0;
int words = 0;
int lines = 0;
%}
%option noyywrap
%%
\n {
++lines;
++characters;
}
[ \t]+ characters += yyleng;
[^ \t\n]+ {
++words;
characters += yyleng;
}
%%词法文件需要使用工具flex将其编译生成一个c语言文件，然后再使用gcc将其编译成一个可执行文件。编译前，我们需要先编写一个简单的main函数. 再编写一个程序的入口函数（main），并调用yylex()就可以了。具体如下：
$ cat wc.c
#include <stdio.h>
int yylex(void);
int main(void)
{
extern int characters, words, lines;
yylex();
printf("%d characters, ", characters);
printf("%d words, ", words);
printf("%d lines\n", lines);
return 0;
}这里需要注意：在程序中，我们通过调用yylex()完成了实际的词法解析过程，并获得执行结果。这是一个非常简单的示例，实际过程比这要更加复杂，在词法文件中，每一次rule解析完成后，再起action部分，通常都会有return语句结束本次yylex调用，所以会是一个反复调用yylex的过程。
$ lex zzx.l
$ gcc lex.yy.c wc.c -o wc.out
$ chmod +x wc.out
$ cat s.txt
this is a input file.
this is a input file.
$ ./wc.out < zzx.l
404 characters, 36 words, 18 lines
$ ./wc.out < s.txt
44 characters, 10 words, 2 lines好了，至此，我们就完成一个词法解析的任务，因为这个任务不涉及任何语法（yyac）解析，所以比较适合初学者学习词法解析工具lex。
为了再略微增强该示例的，这里对上面的示例又做了一个小调整，新增一行“Definitions”，有时候为了增强可读性，会对一些expression定义一个名称，如下，将\n定义为NL：
%{ //
int characters = 0; // %{ ... }% 之间的部分是"Declarations"
int words = 0; // Declarations 部分声明的变量，是可以在全局使用的
int lines = 0; // 例如，在该示例的main程序中，就通过extern声明的方式
%} // 使用了这些变量
//
NL \n // 这里新增了一行，这是一行 Definitions
// 将\n用字母NL定义，所以下面的\n也就可以使用NL
// 试想，如果表达式很复杂用这种方式，可读性会增强很多
%% //
NL { // 从这里开始是Translations阶段
++lines; // 这里定了Token，以及遇到了Token之后
++characters; // 应该采取/执行什么，例如这里遇到了\n字符
} // 则，将lines/characters变量都加1
[ \t]+ characters += yyleng; //
[^ \t\n]+ { // 注释部分的文本需要删除，程序才能正常编译
++words; // 删除注释的vim命令：1,$s/\/\/.*$//g
characters += yyleng; //
} //
//
%% 自此，我们就了解一个词法解析文件的几个主要部分：Definitions、Declarations、rule（以及rule对应的Action）。
参考资料：
yylex()函数，该函数每次基于某个规则（rule）解析到一个新的Token的时候，则会执行对应的“Action”（也就是每个Token后面的代码）部分的代码。例如，上面的程序中会执行++lines或++words代码。yyleng、yytext、yyin等，完整的列表可以参考：Values Available To the User。另外，这些“变量”并不是真的变量，大部分都是一些“宏”，例如，yytext的真实定义可能是这样的：#define yytext (((struct yyguts_t*)yyscanner)->yytext_r)。了解这一点，有利于理解这些”变量”并不能在外部直接引用。
return,例如如果遇到一个整数，可能会看到类似这样的代码：return INTEGER; 这时候，yylex()遇到一个对应的字符就会返回INTEGER。INTEGER,语法为 %token INTEGERINTEGER的预定义：#define INTEGER 257INTEGER了cat cal.y
...
%token INTEGER
...cat cal.tab.h //这是bison生成的文件
...
#define INTEGER 257
...cat cal.l
...
[[:digit:]]+ { return INTEGER; }
...return语句给yyparse()中调用yylex时，返回当前Token的类型。如果一个Token是一个[:digit:]+的时候，我们除了需要知道这个Token是一个整数之外，至少yyparse()还需要知道这个是一个什么整数，具体数值是多少，当然并不是所有的token都需要，一般identifier都是需要的。而，前面的yytext都是yylex本地的“变量”。这时候，通常会使用yylval。yylval是一个由yacc/bison定义的变量（默认是int类型），用于存储词法解析需要传递给yyparse的数据，在yacc/bison的语句处理的Action阶段，可以使用变量，以获得词法解析阶段的一些值。例如，一个Token是一个整数、字符串（并非keyword）的时候，我们会将对应的值存储在yylval中。所以，yylval通常会被定义为一个联合体（union类型），用于存储不同类型的值。关于这几个概念的更详细细致的解释可以参考最前面提到的“IBM的z/OS系统的文档中关于lex和yacc的介绍”（参考：Tutorial on using lex and yacc）。