리눅스 바이슨이 뭐야?

Linux에서 bison은 문법 분석기 프로그램을 생성하는 데 사용되는 도구입니다. 사용자가 제공한 문법 규칙을 문법 분석기로 변환할 수 있습니다. bison은 복잡한 파일 구문 분석을 처리하기 위해 flex(어휘 분석기)와 함께 사용해야 합니다. 일하다. 바이슨은 주어진 문법의 생성부터 시작하여 알고리즘을 거쳐 최종적으로 액션 테이블을 구성한 후 이 액션 테이블을 사용하여 문장을 구문 분석합니다.

이 튜토리얼의 운영 환경: linux7.3 시스템, Dell G3 컴퓨터.

Unix Lex/YACC는 Linux FLex/Bison으로 발전했습니다

Lex는 당시 AT&T에서 인턴이었던 Mike Lesk와 Eric Schmidt에 의해 1975년에 완성되었습니다(Schmidt가 더 많은 작업을 수행했습니다). 단독으로 사용하거나 Johnson's yacc와 함께 사용할 수 있는 분석기 프로그램입니다. Lex는 매우 유명하지만 효율성이 너무 낮고 버그가 있습니다. 1987년경 Lawrence Berkeley Laboratory의 Vern Paxson은 Lex를 C로 다시 작성하고 Berkeley 라이센스에 따라 FLex(Fast Lexical Analysis Generator)라는 이름을 붙였습니다. Flex는 이제 여전히 Berkeley 라이선스를 기반으로 하는 SourceForge의 프로젝트입니다.
[Flex](https://github.com/westes/flex "Flex")는 원래 Unix 버전의 무료(GNU가 아닌) 구현입니다. c/C++용 어휘 스캔 생성기에 사용되는 lex.

(참고: Schmidt는 Google의 CEO였습니다.)

bison의 전신은 yacc입니다. Yacc는 Knuth의 LR 구문 분석 이론을 기반으로 1975년부터 1978년까지 Bell Labs의 S.C. Johnson에 의해 작성되었습니다. 1985년경 UC Berkeley 대학원생 Bob Corbett는 향상된 내부 알고리즘을 사용하여 Berkeley yacc를 구현했습니다. FSF의 Richard Stallman은 Berkeley yacc를 다시 작성하여 GNU 프로젝트에 사용하여 오늘날의 GNU Bison을 형성하는 데 많은 기능을 추가했습니다. Bison은 현재 FSF 프로젝트로 유지 관리되며 GNU Public License에 따라 출시됩니다. [Bison](http://www.gnu.org/software/bison/manual/)은 yacc와 호환되는 자유 문법 생성기입니다.

FLex/Bison으로 개발된 초기 Unix Lex/YACC는 상위 버전과 호환됩니다(즉, 이전 버전과 호환됨).

Flex/bison 작동 방식

사용 측면에서 보면 Flex와 Bison은 Linux에서 어휘 분석기와 구문 분석기라는 두 가지 프로그램을 생성하는 데 사용되는 도구입니다. 이들은 구조화된 입력을 처리할 수 있으며 일반적으로 복잡한 처리를 위해 조합하여 사용됩니다. 파일 파싱 작업.

bison은 사용자가 제공한 문법 규칙을 문법 분석기로 변환할 수 있습니다. 간단히 말하면, 바이슨은 주어진 문법의 생성부터 시작하여 알고리즘을 거쳐 최종적으로 액션 테이블을 구성한 후 이 액션 테이블을 사용하여 문장을 구문 분석합니다. 구체적으로, bison은 사용자가 제공한 문법의 생성을 읽고 C 언어 형식으로 LALR(1) 작업 테이블을 생성하고 이를 yyparse라는 C 함수에 포함시킵니다. 이 함수의 기능은 이 작업 테이블을 사용하여 구문 분석하는 것입니다. 토큰 스트림, 이 토큰 스트림은 flex에 의해 생성된 어휘 분석기로 소스 프로그램을 스캔하여 얻습니다.

플렉스 파일은 패턴(콩, 녹두...)을 정의하고 플렉스 처리(어휘 분석)를 통해 출력을 토큰 세그먼트로 분할합니다(입력 콩을 하나씩 선택). 이를 통해 다양한 액션(콩을 갈아 두유로 만들기(액션), 녹두로 녹두 케이크 만들기(액션))...
flex에 의해 생성된 토큰을 Bison에 공급하여 처리할 수 있습니다(더 쉽고 디버그하기 쉬움). 물론, 들소에게 먹이를 주지 않고 직접 처리할 수도 있습니다(다음 예처럼). 그러나 Bison을 사용하면 복잡한 로직을 보다 편리하게 처리할 수 있어 작성이 간단하고 디버그가 쉬워집니다.

인코딩 연습: 문자 카운터

//本例中仅仅使用flex以及少量手写代码（main中），来完成字符串统计功能。
Yolandas-MacBook-Pro:flex-bison liuyuanyuan$ cat fb1-1.l
/* 统计输入字符串*/
%{
  int chars = 0;
  int words = 0;
  int lines =0;

%}

%%
[a-zA-Z]+ {
		words++;
		chars += strlen(yytext);
          }

\n        {     chars++; lines++;}

.         {     chars++;     }

%%


int main(int args, char **argv)
{
	yylex();
	printf("lines=%6d words=%6d chars=%6d\n", lines, words, chars);
	return 0;
}

//Linux 系统上用 -lfl 选项编译, Mac 的编译选项是 -ll
Yolandas-MacBook-Pro:flex-bison liuyuanyuan$ gcc -ll lex.yy.c  -o fb1-1
Yolandas-MacBook-Pro:flex-bison liuyuanyuan$ ./fb1-1
hello 
this is yolanda
bye.
lines=     3 words=     5 chars=    28

1 flex(fast lex, scanner) 파일 콘텐츠 구조(*.l, 3개 부분으로 나누어짐)

/* P1: declarations(定义段) */
%{
  
%}

%%
  /* P2: translation rules(规则段) */
%%

/* P3: auxiliary functions(用户辅助程序段，c函数)*/

정의 섹션에는 텍스트 블록, 정의 및 내부가 포함됩니다. 선언이 기다려집니다.
C 언어 헤더 파일, 함수 및 변수 선언은 일반적으로 %{...%} 사이에 배치되며 이 부분의 내용은 생성된 .c 파일의 시작 부분에 직접 복사됩니다.

%옵션 옵션을 포함합니다

%option noyywrap /* 定义段中包含了option选项*/

%{
#include "cal.tab.h"
extern int yylval;
%}

규칙 세그먼트 일련의 일치 패턴(정규 표현식)과 작업(C 코드)인 %%...%% 사이의 부분입니다.

Flex 스캐너가 실행되면 입력을 규칙 세그먼트의 패턴과 일치시키고 일치 항목을 찾을 때마다(일치하는 입력을 토큰이라고 함) 해당 패턴과 연관된 C 코드를 실행합니다.

pattern（正则表达式） { action(c代码) }

example:
[0-9]+ {yylval = atoi(yytest); return NUMBER;}

사용자 보조 프로그램 세그먼트는 C 코드이므로 그대로 c 파일에 복사됩니다. 일반적으로 여기에 몇 가지 보조 기능이 정의되어 있습니다.

int terror(chr *s)
{
    printf("%s\n", s);
    return 0;
}

2 bison(yacc, 파서) 파일 콘텐츠 구조(*.y, 3개 부분으로 구분, %%로 구분)

/*P1: declarations 定义段*/
%{

%}
 
%%
/*P2: grammar rules 规则段(rule-action)*/
    
     A: a1  {  语义动作1 }
	  | a2  {  语义动作2 }
	  | …
	  | an  {  语义动作n }
	  | b  //没有{…},则使用缺省的语义动作       
	; //产生式结束标记
    //语义动作一般是在产生式右部分析完，归约动作进行前执行。
    A→ a1 | a2 |  … | an | b 
%%

/* P3: supporting C routines 用户辅助程序段(C函数) */

정의 섹션은 두 부분으로 나눌 수 있습니다:

1. 및 %} 헤더 파일 포함, 매크로 정의, 전역 변수 정의, 함수 선언 등을 포함하여 그 사이의 부분은 C 언어로 작성됩니다.

2. 문법.

일반적으로 사용되는 Bison 태그 선언에는 %token %union %start %type %left %right %nonassoc 등이 포함됩니다.

%token 定义文法中使用了哪些终结符。定义形式： %token TOKEN1 TOKEN2  
终结符一般全大写；（如 TOKEN1 TOKEN2）  
一行可定义多个终结符，空格分隔；  

%left、%right、%nonassoc 也是定义文法中使用了哪些终结符。定义形式与%token类似。  
先定义的优先级低，最后定义的优先级最高，同时定义的优先级想通过。  
%left表示左结合，%right表示右结合；  
%nonassoc 表示不可结合（即它定义的终结符不能连续出现。例如
%left AA BB  
%nonassoc CC  
%right DD  
表示优先级关系为：AA=BB 注意：也可以于%prec来结合使用来改变token的优先级和结合性 例如： :'-' expr %prec NEG { $$ = -$2; };  

%union 声明语法符号的语义值类型的集合，  
bison中每个符号包括记号和非终结符都有一个不同数据类型的语义值，并使用yylval变量在移进和归约中传递这些值，YYSTYPE（宏定义）为yylval的类型，默认为int；  
我们使用%union来重新定义符号的类型  
%union  
{  
int iValue; /* integer value */  
char sIndex; /* symbol table index */  
nodeType *nPtr; /* node pointer */  
};  

%type 定义非终结符其属性值的类型。  
%type sym1 sym2  
%type sym3  

%start 指定文法的开始的文法符号（非终结符），是最终需要规约而成的符号。  
定义形式为：%start startsym ， 其中startsym为文法的开始符号。  
如果不使用%start定义文法开始符号，则默认在第二部分规则段中定义的第一条生产式规则的左部非终结符为开始符号。

规则段 由rule(语法规则)和action(包括C代码)组成。

bison规则基本是BNF，做了一点简化以易于输入。

规则中目标或非终端符放在左边，后跟一个冒号：然后是产生式的右边，之后是对应的动作（用{}包含）。

%%
  program: program expr '\n' { printf("%d\n", $2); }
  ;

  expr: INTEGER {$$ = $1; }
           | expr '+' expr { $$ = $1 + $3; }
           | expr '-' expr { $$ = $1 - $3}
  ;
%%

注意：$1表示右边的第一个标记的值，$2表示右边的第二个标记的值，依次类推。$$表示归约后的值。

用户辅助程序段 为C代码，会被原样复制到c文件中，这里一般自定义一些函数。

3 flex-bison 代码协作方式

flex/bison编码实践：编写简单计算器

1 macOS下flex/bison安装

brew install flex
brew install bison
# macos下flex/bison安装简单方便，另需安装gcc用于编译c语言程序。
brew install gcc

2 flex词法文件：calc.l

%option noyywrap

%{
    /*
     *  一个简单计算器的Lex词法文件
     */
	void yyerror(char*);
	#include "calc.tab.h"
%}

%%

     /* a-z为变量 */   
[a-z]	{
            yylval = *yytext - 'a';
            return VARIABLE;
    	}

    /* 整数 */
[0-9]+	{
            yylval = atoi(yytext);
            return INTEGER;
    	}

    /* 运算符 */
[-+()=/*\n]	{return *yytext;}

    /* 空白被忽略 */
[ \t]    ;

    /* 其他字符都是非法的 */
.    yyerror("invalid input");

%%

3 bison语法文件：calc.y

%token    INTEGER VARIABLE
%left    '+' '-'
%left    '*' '/'

%{
	#include <stdio.h>   
    void yyerror(char*);
    int yylex(void);
	
    int sym[26];
%}

%%
program:
    program statement '\n'
    |
    ;
statement:
     expr    {printf("%d\n", $1);}
     |VARIABLE '=' expr    {sym[$1] = $3;}
     ;
expr:
    INTEGER
    |VARIABLE{$$ = sym[$1];}
    |expr '+' expr    {$$ = $1 + $3;}
    |expr '-' expr    {$$ = $1 - $3;}
    |expr '*' expr    {$$ = $1 * $3;}
    |expr '/' expr    {$$ = $1 / $3;}
    |'('expr')'    {$$ = $2;}
    ;
%%

void yyerror(char* s)
{
    fprintf(stderr, "%s\n", s);
}

int main(void)
{
    printf("A simple calculator.\n");
    yyparse();
    return 0;
}</stdio.h>

4 Makefile 文件：

all: clean calc


calc: calc.l calc.y
	bison -d calc.y
	flex calc.l
	cc -o $@ calc.tab.c lex.yy.c -lm

clean:
	rm -f calc \
	lex.yy.c calc.tab.c calc.tab.h

5 执行

(可以直接执行make也就是执行Makefile中定义的内容，也可以单步执行)

Yolandas-MBP:calcSimple liuyuanyuan$ ls -l
total 32
-rw-r--r--@ 1 liuyuanyuan  staff  157  8 13 09:53 Makefile
-rw-r--r--@ 1 liuyuanyuan  staff  507  8 13 10:01 calc.l
-rw-r--r--@ 1 liuyuanyuan  staff  731  8 13 23:04 calc.y

Yolandas-MBP:calcSimple liuyuanyuan$ make
rm -f calc \
	lex.yy.c calc.tab.c calc.tab.h
bison -d calc.y
flex calc.l
cc -o calc calc.tab.c lex.yy.c -lm

Yolandas-MBP:calcSimple liuyuanyuan$ ls -l
total 272
-rw-r--r--@ 1 liuyuanyuan  staff    157  8 13 09:53 Makefile
-rwxr-xr-x  1 liuyuanyuan  staff  24600  8 14 12:00 calc
-rw-r--r--@ 1 liuyuanyuan  staff    507  8 13 10:01 calc.l
-rw-r--r--  1 liuyuanyuan  staff  42011  8 14 12:00 calc.tab.c
-rw-r--r--  1 liuyuanyuan  staff   2143  8 14 12:00 calc.tab.h
-rw-r--r--@ 1 liuyuanyuan  staff    731  8 13 23:04 calc.y
-rw-r--r--  1 liuyuanyuan  staff  44590  8 14 12:00 lex.yy.c

Yolandas-MBP:calcSimple liuyuanyuan$ ./calc
A simple calculator.
1+2
3

위 내용은 리눅스 바이슨이 뭐야?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!