调用Bison和Flex例子

古城微笑少年丶 2021-12-24 02:55 341阅读 0赞

[https://pandolia.net/tinyc/ch13\_bison.html][https_pandolia.net_tinyc_ch13_bison.html]

## Flex(Lexical Analyzar) ##

*  Lex是一个产生词法分析器的工具(最早是Eric Emerson Schmidt和Mike Lesk制作）是许多UNIX系统的标准词法分析器（lexical analyzer）产生程序，而且这个工具所作的行为被详列为POSIX标准的一部分。而Flex就是由Vern Paxon实现的Lex
 *  FLex读进一个代表词法分析器规则的输入字符串流，然后输出C/C++语言的词法分析器源代码。
 *  wiki：[https://en.wikipedia.org/wiki/Flex\_%28lexical\_analyser\_generator%29][https_en.wikipedia.org_wiki_Flex_28lexical_analyser_generator_29]

### Flex的文件结构 ###

*  文件分成三个区块，均以一个只有两个百分比符号（%%）的单行来分隔，如下：  
    > 定义区域  
    %%  
    规则区域  
    %%  
    C/C++代码区
 *  定义区块是用来定义宏以及导入C写成的头文件所在区块。在这里面也可以写一些C代码，这一些代码会被复制到产生出来的C源代码的开头部分。
 *  规则区块是最重要的区块；这里将样式与C的陈述（statement）串连在一起。这一些样式都是正则表达式。当lexer看到输入里面有合乎给定的样式时，则会操作相对应的C代码。这就是flex运作的基础。
 *  C代码区块的内容会原封不动的照搬到产生出来的C源代码里面。

### 小例子 ###

%{
     #include 
    %}
    number [0-9]+
    %option noyywrap
    %% // 第一部分结束
    {number} {
        printf("number: %s\n", yytext);
    }
    %% // 第二部分结束
    int main()
    {
        yylex();
        return 0;
    }

*  %option noyywrap用于指明未定义yywrap函数，此函数用于在文件（或输入）的末尾调用。如果函数的返回值是1，就停止解析。否则等待输入后继续解析

注：正则表达式是使用单个字符串来描述、匹配一系列字符串的规则  
wiki：[https://zh.wikipedia.org/wiki/%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F][https_zh.wikipedia.org_wiki_E6_AD_A3_E5_88_99_E8_A1_A8_E8_BE_BE_E5_BC_8F]

## Bison ##

*  Bison是GNU版本的Yacc（Lexical Analyzar），用于做语法分析，它与Yacc兼容
 *  参考手册：http://www.gnu.org/software/bison/manual/bison.html  
    中译版：http://blog.csdn.net/sirouni2003/article/details/400672
 *  wiki：https://en.wikipedia.org/wiki/GNU\_bison

Bison的文件结构

*  和Flex一样，也分为三个部分
 *  分别是声明、语法规则和代码段，使用%%分开  
    > 定义区域  
    %%  
    规则区域  
    %%  
    C/C++代码区
    
     
 *  第一部分和Flex一样，用于存放终结符的声明、符号优先级和符号类型等定义
 *  第二部分用来定义文法规则
 *  第三部分也是用来存放C/C++代码

来个小例子

%{
    #include 
    #define YYSTYPE int
    
    void yyerror(char const *);
    int yylex(void);
    %}
    
    %token NUMBER
    
    %debug
    
    %%
    
    start:  { printf("yylval = %d\n", yylval);}
        | NUMBER {
            printf("NUMBER %d\n", yylval);
        }
        start NUMBER {
            printf("start NUMBER %d\n", yylval);
        }
        ;
    
    %%
    
    void yyerror(char const *msg)
    {
        printf("error: %s\n", msg);
    }
    
    int yylex()
    {
        printf(">>>");
    
        char str[10] = {};
    
    if(scanf("%s\n", str) == EOF)
        return 0;
    
    int number = atoi(str);
    
    printf("%d\n", number);
    
    yylval = number;
    
    return NUMBER;
    }
    
    int main()
    {
    return yyparse();
    }

*  %token用于定义一个终结符
 *  %debug指定bison在生成的代码中加入debug输出（和bison的-t参数一样）
 *  yyerror在分析过程中有语法错误时被调用
 *  yylex用于给分析器返回token（在生成的代码中自动被调用）

注：终结符是指文法规则中不能再被分解的最小单位，非终结符则是相反的概念。  
例如上面的文法规则中“start”就是非终结符，NUMBER就是一个终结符。

# 例子1 #

Flex程序：

[root@lex total]# cat lexer.l
 %{
 
 #include "y.tab.h"
 #include <stdio.h> 
 
 #undef YY_INPUT
 #define YY_INPUT(b,r,s) readInputForLexer(b,&r,s)
 
 %}
 
 DIGIT [0-9]
 %%
 
 \+ { printf("got plus\n"); return FUNCTION_PLUS; }
 \- { printf("got minus\n"); return FUNCTION_MINUS; }
 {DIGIT}* { printf("got number\n"); return NUMBER; }
 %%
 
 void yyerror(char* s) {
 printf("error %s \n",s);
 }
 
 int yywrap() {
 return -1;
 }

这个程序说明了数字、加号、减号的识别规则

同时，为了让yylex()可以读入字符串而不是读入文件，覆盖了 YY\_INPUT。

Bison（Yacc）程序：

[root@lex total]# cat parser.y
 %{
 #include <stdio.h>
 extern void yyerror(char* s);
 extern int yylex();
 extern int readInputForLexer(char* buffer,int *numBytesRead,int maxBytesToRead);
 %}
 
 %token FUNCTION_PLUS FUNCTION_MINUS NUMBER
 
 %%
 
 expression:
 NUMBER FUNCTION_PLUS NUMBER { printf("got plus expression! Yay!\n"); }
 |
 NUMBER FUNCTION_MINUS NUMBER { printf("got minus expression! Yay!\n");}
 ;
 %%

这个程序说明了两个表达式： 加法(NUMBER FUNCTION\_PLUS NUMBER) 和 减法(NUMBER FUNCTION\_MINUS NUMBER)。

主程序：myparser.c

#include <stdio.h>
 #include <string.h>
 
 int yyparse();
 int readInputForLexer( char *buffer, int *numBytesRead, int maxBytesToRead );
 
 static int globalReadOffset;
 // Text to read:
 static const char *globalInputText = "23 - 5";
 
 int main() {
 globalReadOffset = 0;
 yyparse();
 return 0;
 }
 
 int readInputForLexer( char *buffer, int *numBytesRead, int maxBytesToRead ) {
 int numBytesToRead = maxBytesToRead;
 int bytesRemaining = strlen(globalInputText)-globalReadOffset;
 int i;
 if ( numBytesToRead > bytesRemaining ) { numBytesToRead = bytesRemaining; }
 for ( i = 0; i < numBytesToRead; i++ ) {
 buffer[i] = globalInputText[globalReadOffset+i];
 }
 *numBytesRead = numBytesToRead;
 globalReadOffset += numBytesToRead;
 return 0;
 }

在主程序中，为了能够让 yylex读取字符串，声明了 readInputForlexer函数。

根据YACC的约定，yyparse()会去调用 yylex()。而yylex()调用 readInputForLexer，一次一次地返回给yyparse。

编译和执行：

yacc -d parser.y
    lex lexer.l
    gcc -o myparser *.c
    ./myparser

执行结果：

[root@lex total]# ./myparser
    got number
     got minus
     got number
    got minus expression! Yay!
    [root@lex total]#

# 例子2 #

Hello.l

%{
   #include <stdlib.h>
   #include "y.tab.h"
 %}
  
 %%
   ("hi"|"oi")"\n"       { return HI;  }
   ("tchau"|"bye")"\n"   { return BYE; }
   .                     { yyerror();  }
 %%
  
   int main(void)
   {
      yyparse();
      return 0;
   }
  
   int yywrap(void)
   {
      return 0;
   }
  
   int yyerror(void)
   {
       printf("Error\n");
       exit(1);
   }

Hello.y

编译和执行：

%token HI BYE
    
    %%
    program: 
             hi bye
            ;
    hi:     
            HI     { printf("Hello World\n");   }
            ;
    bye:    
            BYE    { printf("Bye World\n"); exit(0); }
             ;

编译连接

1.  `flex hello.l`
2.  `bison -dy hello.y`
3.  `gcc lex.yy.c y.tab.c -o hello`

>./hello  
hi  
Hello World  
bye  
Bye World

# 例子3 #

[最简单的flex & bison例子][flex _ bison]

y.tab.h

<table> 
 <tbody> 
 <tr> 
 <td> <code>/* Tokens.&nbsp; */</code> <code>#ifndef YYTOKENTYPE</code> <code># define YYTOKENTYPE</code> <code>&nbsp;&nbsp;&nbsp;</code><code>/* Put the tokens into the symbol table, so that GDB and other debuggers</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>know about them.&nbsp; */</code> <code>&nbsp;&nbsp;&nbsp;</code><code>enum</code>&nbsp;<code>yytokentype { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>DIGIT = 258,</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>LOWERCASELETTER = 259,</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>UPPERCASELETTER = 260,</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>OTHER = 261,</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>STOP = 262</code> <code>&nbsp;&nbsp;&nbsp;</code><code>};</code> <code>#endif</code> <code>/* Tokens.&nbsp; */</code> <code>#define DIGIT 258</code> <code>#define LOWERCASELETTER 259</code> <code>#define UPPERCASELETTER 260</code> <code>#define OTHER 261</code> <code>#define STOP 262</code> &nbsp; <code>#if ! defined YYSTYPE &amp;&amp; ! defined YYSTYPE_IS_DECLARED</code> <code>typedef</code>&nbsp;<code>int</code>&nbsp;<code>YYSTYPE;</code> <code># define yystype YYSTYPE /* obsolescent; will be withdrawn */</code> <code># define YYSTYPE_IS_DECLARED 1</code> <code># define YYSTYPE_IS_TRIVIAL 1</code> <code>#endif</code> &nbsp; <code>extern</code>&nbsp;<code>YYSTYPE yylval;</code> </td> 
 </tr> 
 </tbody> 
</table>

token.l

<table> 
 <tbody> 
 <tr> 
 <td> <code>%{ </code> <code>#include "y.tab.h"</code> <code>%}</code> <code>%%</code> <code>"q"</code>&nbsp;&nbsp;&nbsp;<code>return</code>&nbsp;<code>STOP;</code> <code>"Q"</code>&nbsp;&nbsp;&nbsp;<code>return</code>&nbsp;<code>STOP;</code> <code>[0-9] </code><code>return</code>&nbsp;<code>DIGIT;</code> <code>[a-z] </code><code>return</code>&nbsp;<code>LOWERCASELETTER;</code> <code>[A-Z] </code><code>return</code>&nbsp;<code>UPPERCASELETTER;</code> <code>.&nbsp;&nbsp;&nbsp;&nbsp; </code><code>return</code>&nbsp;<code>OTHER;</code> <code>%%</code> </td> 
 </tr> 
 </tbody> 
</table>

token.y

<table> 
 <tbody> 
 <tr> 
 <td> <code>%{ </code> <code>#include &lt;stdio.h&gt;</code> <code>%}</code> &nbsp; <code>%token DIGIT LOWERCASELETTER UPPERCASELETTER OTHER STOP</code> &nbsp; <code>%%</code> <code>start :</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>| start something</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>;</code> &nbsp; <code>something : DIGIT { </code><code>printf</code><code>(</code><code>"DIGIT\n"</code><code>);}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>| LOWERCASELETTER { </code><code>printf</code><code>(</code><code>"LOWERCASELETTER\n"</code><code>);}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>| UPPERCASELETTER { </code><code>printf</code><code>(</code><code>"UPPERCASELETTER\n"</code><code>);}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>| OTHER { </code><code>printf</code><code>(</code><code>"OTHER\n"</code><code>);}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>| STOP { </code><code>exit</code><code>(0);}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>;</code> <code>%%</code> &nbsp; <code>main()</code> <code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Intro</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>printf</code><code>(</code><code>"Type something followed by Return. Type 'q' or 'Q' to end.\n"</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>printf</code><code>(</code><code>"\n"</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Start the parser</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code><code>(yyparse());</code> <code>}</code> &nbsp; <code>yyerror(s)</code> <code>char</code>&nbsp;<code>*s;</code> <code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>printf</code><code>(</code><code>"yacc error: %s\n"</code><code>, s);</code> <code>}</code> &nbsp; <code>yywrap()</code> <code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code><code>(0);</code> <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

运行命令：flex token.l

会得到文件：lex.yy.c

运行命令：bison token.y

会得到文件： token.tab.c

运行命令：gcc \*

会得到文件 a.out

完成

[https_pandolia.net_tinyc_ch13_bison.html]: https://pandolia.net/tinyc/ch13_bison.html
[https_en.wikipedia.org_wiki_Flex_28lexical_analyser_generator_29]: https://en.wikipedia.org/wiki/Flex_%28lexical_analyser_generator%29
[https_zh.wikipedia.org_wiki_E6_AD_A3_E5_88_99_E8_A1_A8_E8_BE_BE_E5_BC_8F]: https://zh.wikipedia.org/wiki/%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F
[flex _ bison]: https://www.cnblogs.com/afxcn/archive/2013/05/17/3084166.html