Flex & bison start

Flex And Bison It is a tool specially designed for programmers of compilers and interpreters ：

• Flex For lexical analysis （lexical analysis, Or called scanning）, Break the input into meaningful chunks , It's called a mark （token）.
• Bison For parsing （syntax analysis, Or called parsing）, Determine how these tokens relate to each other .

for example , The following code snippet ：

alpha = beta + gamma;

Lexical analysis breaks this code down into such tokens ：alpha, =, beta, +, gamma, ;. Then the grammar analysis determined beta + gamma It's an expression , And this expression is assigned to alpha.

But then they proved very effective in other applications . Any application , Especially text processing , Just look for a specific pattern in its input , Or it uses command language as input , They are all suitable for Flex And Bison.

for example ,SQL analysis ：

• MySQL: C++ Lexical analysis , Bison Syntax analysis

  • sql/sql_yacc.yy^[1]
• PostgreSQL: Flex Lexical analysis , Bison Syntax analysis

  • parser/scan.l^[2]
  • parser/gram.y^[3]

In compiler structure , Lexical analyzer 、 The parser is the main component of the compiler front end . Most compilers are organized into three main phases ： front end 、 Optimizer and back end . The front end focuses on understanding source language programs , Convert it to some intermediate representation （IR）. and Flex And Bison It is a tool designed for the front end of the compiler .

origin

bison originate yacc, One by Stephen C. Johnson On 1975 Year to 1978 Parser generation program completed in Bell Laboratories during . It's just like its name （yacc yes yet another compiler compiler Abbreviation ） As implied , At that time, many people were writing parser generators .Johnson Our tools are based on D. E. Knuth The grammatical analysis theory studied （ therefore yacc Very reliable ） And convenient input syntax . This makes yacc stay Unix It's very popular among users , Even though at that time Unix The restricted copyright that it follows allows it to be used only in academia and bell systems . Around the 1985 year ,Bob Corbett, A graduate student at the University of California, Berkeley , The improved internal algorithm is used to realize yacc And became Berkeley yacc. Because this version is better than Bell Labs yacc Faster and uses flexible Berkeley licenses , It soon became the most popular yacc. From the free software foundation （Free Software Foundation） Of Richard Stallman Rewrite the Corbett And use it for GNU In the project , There? , It has been added a lot of new features and evolved into the current bison.bison Now as FSF Is maintained for a project , And it's based on GNU Public License for issuance .

stay 1975 year ,Mike Lesk And summer interns Eric Schmidt Write the lex, A lexical analyzer generator , Most of the programming work is done by Schmidt complete . They found that lex It can be used as an independent tool , It can also be used as Johnson Of yacc The collaborative program of .lex So it became very popular , Although it runs a little slow and has a lot of errors .（ however Schmidt Later, I had a very successful career in the computer industry , He is now ,2009 year , yes Google Of CEO.2010 year CEO Handed over , Continue to be Google Chairman of the board of directors .）

In about 1987 year ,Lawrence Berkeley Laboratory, Vern Paxson Use one kind of ratfor（ It was an extended Fortran Language ） written lex The version is rewritten as C Linguistic , go by the name of flex, intend “ Fast lexical analyzer generator ”（Fast Lexical Analyzer Generator）. Because it is more than AT&T Of lex Faster and more reliable , And like Berkeley's yacc That's based on the Berkeley license , It has finally surpassed the original lex.flex Now it is SourceForge A project for , Still based on the Berkeley license .

install

majority Linux and BSD System comes with flex and bison As a basic part of the system . If your system does not contain them , They are also easy to install .

For example, in Ubuntu/Debian System , Can directly apt install ：

# Ubuntu 20
$ sudo apt install flex bison -y

$ flex -V
flex 2.6.4
$ bison -V
bison (GNU Bison) 3.5.1

Example

For an example, see https://github.com/ikuokuo/start-ai-compiler/tree/main/books/flex_bison , From the conclusion Flex & Bison A Book .

Examples show how to use Flex & Bison Develop a calculator , And can support variables 、 The process 、 Loop and conditional expressions , With built-in functions , It also supports user-defined functions .

Compile all the examples as follows ：

cd books/flex_bison/

#  compile  release
make
#  compile  debug
make debug

#  clear 
make clean

The sample program will output into _build Catalog , Do as follows ：

$ ./_build/linux-x86_64/release/1-5_calc/bin/1-5_calc
> (1+2)*3 + 4/2
= 11

$ ./_build/linux-x86_64/release/3-5_calc/bin/3-5_calc
> let sq(n)=e=1; while |((t=n/e)-e)>.001 do e=avg(e,t);;
Defined sq
> let avg(a,b)=(a+b)/2;
Defined avg
> sq(10)
= 3.162
> sqrt(10)
= 3.162
> sq(10)-sqrt(10)
= 0.000178

If only one instance is compiled ：

cd ch01/1-1_wc/

#  compile  release
make -j8
#  compile  debug
make -j8 args="debug"

#  clear 
make clean

Program

Flex And Bison The program consists of three parts ： Definition section 、 Rule sections and user subroutines .

... definition section ...
%%
... rules section ...
%%
... user subroutines section ...

Flex The rule part is based on regular expressions ,Bison Based on BNF (Backus-Naur Form) Grammar . Detailed usage , Please follow the conclusion Flex & Bison A Book , And examples .

I won't elaborate too much here , This article aims to let you know that there are Flex And Bison This tool , And what they can help us accomplish .

Conclusion

Flex And Bison It's a lexical analyzer （Scanner） And parser （Parser） Automatic generation tool , Applying the results of formal language theory . These tools can also be used for text search 、 Website filtering 、 Word processing and command line language interpreters .

This article mainly comes from the following books ：

• 2011-03 / flex And bison（ Chinese version ）^[4] / read ^[5]
• 2009 / flex & bison - Text Processing Tools^[6] / read ^[7]

GoCoding Personal experience sharing , We can pay attention to the official account ！

Reference material

[1]

sql/sql_yacc.yy: https://github.com/mysql/mysql-server/blob/8.0/sql/sql_yacc.yy

[2]

parser/scan.l: https://github.com/postgres/postgres/blob/master/src/backend/parser/scan.l

[3]

parser/gram.y: https://github.com/postgres/postgres/blob/master/src/backend/parser/gram.y

[4]

2011-03 / flex And bison（ Chinese version ）: https://book.douban.com/subject/6109479/

[5]

read : http://home.ustc.edu.cn/~guoxing/ebooks/flex%E4%B8%8Ebison%E4%B8%AD%E6%96%87%E7%89%88.pdf

[6]

2009 / flex & bison - Text Processing Tools: https://book.douban.com/subject/3568327/

[7]

read : https://web.iitd.ac.in/~sumeet/flex__bison.pdf