Shulou(Shulou.com)06/02 Report--

This article focuses on "how to use FLex and Bison to achieve calculators", interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Now let the editor take you to learn "how to use FLex and Bison to implement calculators"!

Reference:

Flex common specifications

Bison common specifications

Flex+bison Development Calculator

1 Unix Lex/YACC develops into Linux FLex/Bison

Lex, which was done in 1975 by Mike Lesk and Eric Schmidt, who was still an internship in AT&T (Schmidt did more), is a lexical analyzer generator that can be used alone or work with Johnson's yacc. Lex is very famous, but it is too inefficient and has bug. Around 1987, Vern Paxson of Lawrence Berkeley Labs rewrote Lex in C and named it FLex (the Fast Lexical Analyzer Generator), based on the Berkeley license. Flex is now a project of SourceForge, still based on the Berkeley license

[Flex] (https://github.com/westes/flex "Flex") is the free (but non-GNU) implementation of the original unix version of lex, which is used as a lexical scan generator for cUnip c + +.

(note: Schmidt used to be the CEO of google)

The predecessor of bison is yacc. Yacc was written by S.C.Johnson of Bell Labs from 1975 to 1978 based on Knuth's LR parsing theory. Around 1985, Bob Corbett, a graduate student of UC Berkeley, implemented Berkeley yacc using improved internal algorithms. Richard Stallman from FSF rewrote Berkeley yacc and used it in the GNU project, adding many features to form today's GNU Bison. Bison is now maintained as a FSF project, released under the GNU Public license, [Bison] (http://www.gnu.org/software/bison/manual/) is a syntax generator for yacc-compliant free.

The early Lex/YACC of Unix developed into FLex/Bison, and the new version of the program is up-compatible (that is, compatible with the old version), and now chang uses Flex and Bison.

2 working principle of flex-bison

From the point of view of use, Flex and Bison are tools used to generate lexical analyzer and parser under Linux, which can deal with structured input and are generally used together to deal with complex file parsing work.

The flex file defines pattern (which is soybeans and which is mung beans). Through flex processing (lexical analysis), the output is divided into segments of token (picking out the input beans one by one), thus performing different action (soybeans grind soybean milk (action), mung beans go to make mung bean cakes (action).

The tokens generated by flex can be fed to Bison (easier to debug), or you can handle it yourself without feeding bison (such as the following example). But the use of bison can be more convenient to deal with complex logic, simple to write, easy to debug.

/ / in this example, only flex and a small amount of handwritten code (in main) are used to complete string statistics. Yolandas-MacBook-Pro:flex-bison liuyuanyuan$ cat fb1-1.1 Yolandas-MacBook-Pro:flex-bison liuyuanyuan$ cat fb1 * Statistical input string * /% {int chars = 0; int words = 0; int lines = 0 X%}% [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 } / / compile with the-lfl option on the Linux system. The compilation option for Mac is-llYolandas-MacBook-Pro:flex-bison liuyuanyuan$ gcc-ll lex.yy.c-o fb1-1Yolandas-MacBook-Pro:flex-bison liuyuanyuan$. / fb1-1hello this is yolandabye.lines= 3 words= 5 chars= 283 flex (fast lex, scanner) file content structure (* .l) Divided into 3 parts) / * P1: declarations (definition segment) * /% {%}% / * P2: translation rules (rule segment) * /%% / * P3: auxiliary functions (user assistant program segment) C function) * /

Definition segments include text blocks, definitions, internal declarations, and so on.

The header files, functions and variable declarations of the C language are generally placed in% {. %}, the contents of this section are copied directly to the beginning of the generated .c file.

Include% option option

% option noyywrap / * definition section contains option option * /% {# include "cal.tab.h" extern int yylval;%}

Rule segment%%. The part between% is a series of matching patterns (regular expressions) and actions (C code).

When the flex scanner runs, it matches the input to the pattern of the rule segment, and executes the C code associated with that pattern every time it finds a match (the matched input is called a token).

Pattern (regular expression) {action (c code)} example: [0-9] + {yylval = atoi (yytest); return NUMBER;}

The user auxiliary program segment is C code, which will be copied to the c file as is. Generally, some auxiliary functions are defined here.

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

4 bison (yacc, parser) file content structure (* .y, divided into 3 parts,% separated) / * P1: declarations definition segment * /% {}% / * P2: grammar rules rule segment (rule-action) * / A: A1 {semantic action 1} | a2 {semantic action 2} |... | | an {semantic Action n} | b / / No {… | }, the default semantic action is used; / / the production closing tag / / semantic action is generally performed after the production right part is analyzed and the reduction action is carried out. A → A1 | a2 |... | | an | b% / * P3: supporting C routines user assistant program segment (C function) * / |

The definition segment can be divided into two parts:

1. The part between% {and%}, written in C language, including header file include, macro definition, global variable definition, function declaration, etc.

two。 Make some declarations about grammatical terminators and non-terminators.

Common Bison tag declarations are:% token% union% start% type% left% right% nonassoc, etc.

% token defines which Terminators are used in the grammar. Definition form:% token TOKEN1 TOKEN2 Terminator is generally all uppercase; (for example, TOKEN1 TOKEN2) one line can define multiple Terminators separated by spaces;% left,% right,% nonassoc also define which Terminators are used in the grammar. The definition form is similar to% token. The priority defined first is low, the last defined priority is the highest, and the defined priority wants to pass. % left indicates left association,% right indicates right association, and% nonassoc indicates unassociative (that is, the Terminator it defines cannot occur consecutively). For example

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.