Skip to main content

lex和yacc

· 5 min read

词法分析​

lex主要是用来做词法分析用的,简单来说就是分词.
每次调用yylex都会返回一个词,lucence的标准分词器也是用lex一类的包分好词的.
Lucene的分词分好之后会构造倒排索引.

lex例子​


%{
%}
%%

end  { ECHO ;return 2 ;}

aaa {ECHO ;}

.|\N {}

%%
int main(){
    yylex();
}
int yywrap(){
 return 1;
}

然后执行

lex test.lex

语法分析​

语法分析是什么?

语法分析是一个特别的规则系统,或者说.语法分析是一个图灵机,可以表达正则表达式无法表达的内容

语法分析如何选择? 语法分析的一个关键问题是如何在多个产生式中选择一个产生式,有且仅有一个产生式.

bison是yacc的gun版本
和flex一样,bison也是分成3个部分,使用%%分割 Linux下面开源的yacc版本为bison

...定义段...

%%

...规则段...

%%

...用户子例程段...

第一个部分主要是c的相关声明和token声明,非终结符的声明等
第二部分主要是产生式和语义动作
第三部分则是执行的相关c函数

/* Infix notation calculator--calc */
  
%{
#define YYSTYPE double
#include <math.h>
#include <stdio.h>
%}

/* BISON Declarations */
%token NUM
%left '-' '+'
%left '*' '/'
%left NEG     /* negation--unary minus */
%right '^'    /* exponentiation        */

/* Grammar follows */
%%
input:    /* empty string */
             | input line
;

line:     '\n'
            | exp '\n'  { printf ("\t%.10g\n", $1); }
;

exp:      NUM                { $$ = $1;         }
           | exp '+' exp        { $$ = $1 + $3;    }
        | exp '-' exp        { $$ = $1 - $3;    }
        | exp '*' exp        { $$ = $1 * $3;    }
        | exp '/' exp        { $$ = $1 / $3;    }
        | '-' exp  %prec NEG { $$ = -$2;        }
        | exp '^' exp        { $$ = pow ($1, $3); }
        | '(' exp ')'        { $$ = $2;         }
;
%%
#include <ctype.h>
main ()
{
  yyparse ();
}
yyerror (s)  /* Called by yyparse on error */
     char *s;
{
  printf ("%s\n", s);
}

yylex ()
{
  int c;

  /* skip white space  */
  while ((c = getchar ()) == ' ' || c == '\t')
    ;
  /* process numbers   */
  if (c == '.' || isdigit (c))
    {
      ungetc (c, stdin);
      scanf ("%lf", &yylval);
      return NUM;
    }
  /* return end-of-file  */
  if (c == EOF)
    return 0;
  /* return single chars */
  return c;
}

生成并编译

bison bison parse.y
gcc parse.tab.c -lm
# ./a.out 
3+2
5

下面描述常用的变量的使用​

%token​

%token 放在定义段

%token NUMBER

会在生成c文件的时候变成

#define NUMBER 258

所以可以理解%token是一种简写,可以减少#define的使用

YYSTYPE​

In real parsers, the values of different symbols use different data types, e.g., int and double for numeric symbols, char * for strings, and pointers to structures for higher level symbols. If you have multiple value types, you have to list all the value types used in a parser so that yacc can create a C union typedef called YYSTYPE to contain them. (Fortunately, yacc gives you a lot of help ensuring that you use the right value type for each symbol .)

引用自lex & yacc

YYSTYPE 是一个类型的宏定义,目的是给终结符合非终结符确定类型的集合

%union 是YYSTYPE定义的简写

%token 是定义词素枚举值的简写

%type 是非终结符的类型定义的简写

%union {
  double dval;
  int vblno;
}

%token NUMBER

使用--defines参数生成头文件

# bison --defines test.y

最后会生成如下的文件

enum yytokentype{
    NUMBER = 258
};

union YYSTYPE{
  double dval;
  int vblno;
};

如果给token 添加类型的话

%token <vblno> NAME
%token <dval> NUMBER
%type <dval> expression

In action code, yacc automatically qualifies symbol value references with the appropriate field'name, e.g., if the third symbol is a NUMBER, a reference to $3 acts like $3,dval.

引用自lex & yacc

在语义动作的代码里面,如果第三个元素是NUMBER 的话, $3等价于$3.dval

相关阅读