摘要:
MySQL使用了flex/yacc做词法解析和语法解析, 本文以简短的例子说明其语法。
yacc说明:
YACC介绍（译文）_KobeFadeaway的博客
Yacc(Yet Another Compiler Compiler)， 是 Unix/Linux 上一个用来生成编译器的编译器（编译器代码生成器）。Yacc 生成的编译器主要是用 C 语言写成的语法解析器（Parser），需要与词法解析器 Lex 一起使用，再把两部份产生出来的 C 程序一并编译。Yacc 本来只在 Unix 系统上才有，但现时已普遍移植往 Windows 及其他平台。
分析程序生成器 (parser generator) 是一个指定某个格式中的一种语言的语法作为它的输入，并为该种语言产生分析过程以作为它的输出的程序。在历史上，分析程序生成器被称作编译 - 编译程序 (compiler- compiler)，这是由于按照规律可将所有的编译步骤作为包含在分析程序中的动作来执行。现在的观点是将分析程序仅考虑为编译处理的一个部分，所以这个术语也就有些过时了。
合并 LALR (1) 分析算法是一种常用的分析生成器，它被称作 Yacc ( yet another compiler- compiler )。给出 Yacc 的概貌来，将使用 Yacc 为 TINY 语言开发一个分析程序。
Yacc 提供了一种用于描述计算机程序输入的通用工具。Yacc 用户指定其输入的结构，以及在识别每个此类结构时要调用的代码。Yacc 将这样的规范转换为处理输入过程的子例程。通常，由该子例程处理用户应用程序中的大多数控制流是方便且适当的
以计算器说明yacc使用:
文件打包:
yacc-dev.7z-C++文档类资源
lexya_c.l
%{
#include <stdlib.h>
#include "userdef.h"
#include "lexya_c.tab.h"
void yyerror(char *);
void add_buff(char *);
void add_var(char *);
extern char sBuff[10][20];
extern int iBuffX;
extern int iBuffY;
extern varIndex strMem[256];
extern int iMaxIndex;
extern int iCurIndex;
%}
%%
[a-zA-Z][a-zA-Z0-9]* {
add_var(yytext);
yylval = iCurIndex;
add_buff(yytext);
return VAR;
}
[0-9]+ {
yylval = atoi(yytext);
add_buff(yytext);
return INT;
}
[-+()=*/] {
yylval = *yytext;
add_buff(yytext);
return *yytext;
}
[\n] {
yylval = *yytext;
iBuffY=0;iBuffX++;
return *yytext;
}
[\t] ;
. yyerror("unknow char");
%%
void add_buff(char * buff) {
strcat(sBuff[iBuffX],buff);
iBuffY+=strlen(buff);
}
void add_var(char *mark) {
if (iMaxIndex==0){
strcpy(strMem[0].sMark,mark);
iMaxIndex++;
iCurIndex=0;
return;
}
int i;
for(i=0;i<=iMaxIndex-1;i++) {
if(strcmp(strMem[i].sMark,mark)==0) {
iCurIndex=i;
return;
}
}
strcpy(strMem[iMaxIndex].sMark,mark);
iCurIndex=iMaxIndex;
iMaxIndex++;
}
int yywrap(void) {
return 1;
}
lexya_c.y
%{
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "userdef.h"
int yylex(void);
void yyerror(char *);
void debug_info(char *, int *, char *);
void stm_info();
extern varIndex strMem[256];
int iMaxIndex=0;
int iCurIndex=0;
char sBuff[10][20]={0};
int iBuffX=0;
int iBuffY=0;
%}
%token INT VAR
%left '+' '-'
%left '*' '/'
%%
program:
program statement
|
;
statement:
expr { printf("%d\n",$1); }
| VAR '=' expr {
debug_info("=",yyvsp,"210");
strMem[$1].iValue=$3;
}
| statement '\n' {
printf("--------------------------------\n\n");
}
;
expr:
INT {
debug_info("INT",yyvsp,"0");
$$ = $1;
}
| VAR {
debug_info("VAR",yyvsp,"2");
$$ = strMem[$1].iValue;
}
| expr '*' expr {
debug_info("*",yyvsp,"010");
$$ = $1 * $3;
}
| expr '/' expr {
debug_info("/",yyvsp,"010");
$$ = $1 / $3;
}
| expr '+' expr {
debug_info("+",yyvsp,"010");
$$ = $1 + $3;
}
| expr '-' expr {
debug_info("-",yyvsp,"010");
$$ = $1 - $3;
}
| '(' expr ')' {
debug_info("()",yyvsp,"101");
$$ = $2;
}
;
%%
void debug_info(char * info,int * vsp, char * mark) {
printf("--RULE: %s \n", info);
int i=0;
int ilen=strlen(mark);
for(i=0;i>=1-ilen;i--) {
switch(mark[ilen+i-1]){
case '1':
printf("$%d %d %c \n", i+ilen, vsp[i], vsp[i]);
break;
case '0':
printf("$%d %d \n", i+ilen, vsp[i]);
break;
case '2':
printf("$%d %s %d\n", i+ilen, strMem[vsp[i]].sMark, strMem[vsp[i]].iValue);
break;
}
}
stm_info();
}
void stm_info() {
int i=0;
printf("--STATEMENT: \n");
if(iBuffY==0)
printf("%s \n",sBuff[iBuffX-1]);
else
printf("%s \n",sBuff[iBuffX]);
printf("\n");
}
void yyerror(char *s) {
printf("%s\n", s);
}
int main(void) {
yyparse();
return 0;
}
userdef.h
#ifndef __USERDEF__H__
#define __USERDEF__H__
typedef struct {
int iValue; //存数值
char sMark[10];//存代表的字符，如aa ,bb
} varIndex;
varIndex strMem[256];//字符数组
#endif //!__USERDEF__H__
input
aa=4+2*(3-2-1)+6
bb=1-10/(6+4)+8
cd=aa-bb
aa
bb
cd
makefile
build:
bison -d lexya_c.y
lex lexya_c.l
gcc -g -o parser lex.yy.c lexya_c.tab.c
run:
./parser < input
clean:
rm -rf lex.yy.c lex.yy.h parser
运行测试:
编译:
[root@LAPTOP-R709FV7O lex]# make
bison -d lexya_c.y
lex lexya_c.l
gcc -g -o parser lex.yy.c lexya_c.tab.c
运行:
[root@LAPTOP-R709FV7O lex]# make
bison -d lexya_c.y
lex lexya_c.l
gcc -g -o parser lex.yy.c lexya_c.tab.c
[root@LAPTOP-R709FV7O lex]#
[root@LAPTOP-R709FV7O lex]# make run
./parser < input
--RULE: INT
$1 4
--STATEMENT:
aa=4
--RULE: INT
$1 2
--STATEMENT:
aa=4+2
--RULE: INT
$1 3
--STATEMENT:
aa=4+2*(3
--RULE: INT
$1 2
--STATEMENT:
aa=4+2*(3-2
--RULE: -
$3 2
$2 45 -
$1 3
--STATEMENT:
aa=4+2*(3-2-
--RULE: INT
$1 1
--STATEMENT:
aa=4+2*(3-2-1
--RULE: -
$3 1
$2 45 -
$1 1
--STATEMENT:
aa=4+2*(3-2-1)
--RULE: ()
$3 41 )
$2 0
$1 40 (
--STATEMENT:
aa=4+2*(3-2-1)
--RULE: *
$3 0
$2 42 *
$1 2
--STATEMENT:
aa=4+2*(3-2-1)
--RULE: +
$3 0
$2 43 +
$1 4
--STATEMENT:
aa=4+2*(3-2-1)+
--RULE: INT
$1 6
--STATEMENT:
aa=4+2*(3-2-1)+6
unknow char
--RULE: +
$3 6
$2 43 +
$1 4
--STATEMENT:
aa=4+2*(3-2-1)+6
--RULE: =
$3 10
$2 61 =
$1 aa 0
--STATEMENT:
aa=4+2*(3-2-1)+6
--------------------------------
--RULE: INT
$1 1
--STATEMENT:
bb=1
--RULE: INT
$1 10
--STATEMENT:
bb=1-10
--RULE: INT
$1 6
--STATEMENT:
bb=1-10/(6
--RULE: INT
$1 4
--STATEMENT:
bb=1-10/(6+4
--RULE: +
$3 4
$2 43 +
$1 6
--STATEMENT:
bb=1-10/(6+4)
--RULE: ()
$3 41 )
$2 10
$1 40 (
--STATEMENT:
bb=1-10/(6+4)
--RULE: /
$3 10
$2 47 /
$1 10
--STATEMENT:
bb=1-10/(6+4)
--RULE: -
$3 1
$2 45 -
$1 1
--STATEMENT:
bb=1-10/(6+4)+
--RULE: INT
$1 8
--STATEMENT:
bb=1-10/(6+4)+8
unknow char
--RULE: +
$3 8
$2 43 +
$1 0
--STATEMENT:
bb=1-10/(6+4)+8
--RULE: =
$3 8
$2 61 =
$1 bb 0
--STATEMENT:
bb=1-10/(6+4)+8
--------------------------------
--RULE: VAR
$1 aa 10
--STATEMENT:
cd=aa
--RULE: VAR
$1 bb 8
--STATEMENT:
cd=aa-bb
unknow char
--RULE: -
$3 8
$2 45 -
$1 10
--STATEMENT:
cd=aa-bb
--RULE: =
$3 2
$2 61 =
$1 cd 0
--STATEMENT:
cd=aa-bb
--------------------------------
unknow char
--RULE: VAR
$1 aa 10
--STATEMENT:
aa
10
--------------------------------
unknow char
--RULE: VAR
$1 bb 8
--STATEMENT:
bb
8
--------------------------------
--RULE: VAR
$1 cd 2
--STATEMENT:
cd
2
