Skip to content

lilijreey/flex

Repository files navigation

## 需要知道的几个概念
 * Parser
 * Syntax of a Language
 * Semantics of a Language
 * R.E
 * DFA
 * NFA
 * LL reduce
 * Tokens
     如何表示tokens ,使用正则表达式 R.E
 * Terminal Tokens
 * Nonterminal Tokens
 * Lexical Analysis
 * Context-free grammars
 * LR Parser
 * LALR parser
 

## 语法分析
有两种方法而且是等价的
* 推倒  
   是把开始符号推到为源代码
    (一般使用左边优先(这样是从源文件的开始推倒的))
    gcc ccl 使用的是推到

  + 推到算法
   推到要解决的问题是,何时替换非终结符,已经替换为哪种形式
   *递归下降分析, 使用递归算法,映射文法()
   * LL(1) 文法,是递归下降分析的一种改进, (1) 的意思是超前搜索1个符号
     所有文法都可以被改写为等价的可以被LL(1) 算法解析的形式
   
    构造自上而下的语法分析器主要包括
   1. 变换程序文法,满足LL(1) 的要求
   2. 构造文法的First, Follow 集合
   3. 编码


* 移进归约 
   是把源代码规约为开始符号
    (一般使用最左规约)
  推到和规约这两个过程互为逆运算

    Yacc 就是使用的规约
  

语法分析过程(文法)和状态机的天然相似性

=================================================
* 左递归文法
* 任何程序设计语言的文法必定存在递归。因为没有递归的文法
  只能描述有限的语言。然而,任何程序设计语言必定的无限的语言.
    因此不能消除左递归文法的递归形式,这能将左递归变成等价的右递归
   或其他形式

   P -> Pa|b  等价变换 P -> bR;
                        R -> aR | ε
     会有一个空串, 空字符的意义就是,可以把这个非终结符,消除

   First 集合 Follow 集合

  

## lex
#用来定义所有的模式匹配规则
#x.l x.lex, x.y x.yacc
# 注释为C注释
Lex 文件格式
%{
     第一部分 定义
%}

%s 声明状态
  e.g. %s CL VAR METHOD
    使用 BEGIN XXX 来进入一个状态
     使用 BEGIN INITAL 来进入初始的状态
   在Rule中可以使用 <state>R.E {action} 在指定
   注意<state>和R.E 中不能有间隔
   在某种状态中的action
   action 中return 返回的是Token,可以是Terminal or nonterminal
   Token 有 .y 文件声明并生成 token.tab.h
   没有<state> 的R.E 在任何状态中都工作

  * 如果有rule中没有匹配的,默认会输出
   如果要忽略 可以
    .	;
    . 不包括\n

  * 不要传递 yytext 到yacc 中,以为有可能在yacc使用之前
   yytext 的值已经被改变,因该copy一份在传递,
      即传值而不要传递引用;

还可以在这里定义 pattern
e.g.

digit [0-9]
letter [a-zA-Z]
 
   
%%
 第二部分 规则
 R.E {Action;}
 <State> R.E {Action;}
 如果要匹配的是R.E 的元字符可以使用'' 括起来
  e.g. "*" {return PTR;}


%%
E.R 字符	含义
A-Z, 0-9, a-z	构成了部分模式的字符和数字。
.	匹配任意字符,除了 \n。
-	用来指定范围。例如:A-Z 指从 A 到 Z 之间的所有字符。
[ ]	一个字符集合。匹配括号内的 任意 字符。如果第一个字符是 ^ 那么它表示否定模式。例如: [abC] 匹配 a, b, 和 C中的任何一个。
*	匹配 0个或者多个上述的模式。
+	匹配 1个或者多个上述模式。
?	匹配 0个或1个上述模式。
$	作为模式的最后一个字符匹配一行的结尾。
{ }	指出一个模式可能出现的次数。 例如: A{1,3} 表示 A 可能出现1次或3次。
\	用来转义元字符。同样用来覆盖字符在此表中定义的特殊意义,只取字符的本意。
^	否定。
|	表达式间的逻辑或。
"<一些符号>"	字符的字面含义。元字符具有。
/	向前匹配。如果在匹配的模版中的“/”后跟有后续表达式,只匹配模版中“/”前 面的部分。如:如果输入 A01,那么在模版 A0/1 中的 A0 是匹配的。
( )	

的三部分 子程序


定义部分:
 可以用来声明函数, 变量,定义代替
digit [0-9]
letter [A-Za-z]

 在规则中可以直接使用 {digit} 来

正则元字符
" \ [] ^ - ? . * + | () $ / {} % <>


所有对元字符的引用都要使用转义字符
e.g. \* 匹配 * 本身

使用引号包含的字符串就代表他自己
\t tab
\b backspace
\n newline
\\ \

e.g. xyz"++"
   equal "xyz++"
   equal xyz/+/+

[] 中有3个元字符 \ - ^
如果要在[] 中包含字符 - 他必须是第一个字符或最后一个
 e.g. [-+0-9] matches all the gigits and the two signs

(ab|cd) 选择一个


Action
对于任何匹配的token 都会执行一个对于的action 就是执行代码,默认的是
把输入输出,一个空的action 是 ;

输出匹配到的token Lex 提供了一个yytext 的变量存放匹配到的token
[a-z]+ printf("%s", yytext);
也可使用 ECHO 来代替
[a-z]+ ECHO;

### Lex 变量
yyleng 来存放匹配token的长度
yylineno 提供当前行数
yytext 匹配的token
yyout
yyin
yylloc 代表当前词法单元所对应的位置信息

### Yacc 变量
yylval Lex 将解析的token保存在yylval中,为了保存不同类型的变量
        yylval 别定义为union
  %union {
    double dval
    struct xx* xx
  }

默认的yylval 的类型是int
可以自己定义 YYSTYPE 来指定yylval 的类型

YY_USER_ACTION 一个宏代表在执行每个语义动作之前需要被执行的一段代码,默认空
可以用来对位置信息进行维护
e.g.
%{
	int yycolumn = 1;
         #define YY_USER_ACTION yylloc.first_line = yylloc.last_line = yylineno; \
	    yylloc.first_column = yycolumn; yylloc.last_column = yycolumn + yyleng - 1; \
	    yycolumn += yyleng;
	%}

在定义 token 是就要使用
%token <dval> DOUBLE
%token <xx> XX
如果没有指定 <Member> && 就是指向yylval 本身
 来指定每个token 的类型这样Yacc 中的token $*
就会是对应的union 成员
  e.g. $1->xxx


%type <Type> nonterminal
对于在BNF中的notermial 由于要使用$$ 所以也需要告诉Yacc 他们的类型

如果可以进行规约则会执行对应的 action
规则的默认为 $$= $1 如何不要这样就要手动写一个空action (语义动作)
e.g.
members: NL {}
用 $i 来引用第i的右边符号
$$ 来引用左边的nonterminal

%union 声明了各种可能携带语义值的类型,每个Terminal Non-Termianl 都可以
使用 <varinat> (就是%union 中的变量名) 来指明自己使用的类型

Yacc
如果action 有多个句子要使用 {} 扩起来
如果不写默认为 {$$=$1;}

## Lex Yacc 如何交互
在Lex 中使用Yacc 的yylval(一个union) 变量
把token传递给Yacc
  lex Pattern {yylval.d = atof(yytext); return DOUBLE} // 把Lex解析的token 传递给了Yacc
  Yacc XX : DOUBLE EOF {$$= $1 +1;} //$1 本身已经是yylval.d 了
EOF
符号 <<EOF>> 用语匹配文件结束

             


##Lex 内置函数
yywrap 
  当lex 读完输入文件后就会调用 yywrap 
  如果返回1 表示输入已经结束
  int yywrap(void) {return 1;}

yyerror 
  错误处理函数, void yyerror(const char*)
  通常用来输出错误,或者纠错
  默认没有,要自己在bison 中定义

yyparse
  yacc 提供的函数,可以直接使用, yyparse 会自动
   调用 yylex 来取得陪个token yylex 是yylex 是Lex生成的
 
flex
 生产词法分析源码
 flex xx.lex 
 会生成一个 lex.yy.c 的文件

debug lex -d
bison -v
 会生成一个.output 的文件

## yacc bison
  bison -d xx.y 
  -d 会生成 xx.tab.h 文件
  bison 的输入文件后缀名必须是y
  会生成 xx.tab.c, xx.tab.h

bison 需要一个名为 yylex 的函数来返回Token. 这个yylex 既可以是自己手动编写的
      也可以是flex 生成的, 如果是使用flex 生成的需要在.y 文件中声明一下
	e.g.
	void yyerror(char *);
	int yylex(void);

Yacc 的文法使用BNF的变量描述

##BNF
  xx: /*空规则, 主要用于可以包含 ɛ 的空串*/
    | xx blblbl
    ;
又 Lex返回的标记只能是终结符 terminal
        
gcc xx.tab.c lex.yy.c
 生成的可执行文件 读取标准输出,然后输出的标准输出
  
自底向上 reduce 从一个表倒是简化为一个非终结符 noterminal
reduce confilict 当语法有有二意性时,及对一个表达是有多个匹配
  规则。  需要重写语法为二意性, 或者提供操作符优先级给yacc

%left 指定左结合
%right 指定右结合
%nonassoc 不可结合
最后列出的优先级高于先前列出的
当规则和单词的优先级相等时,%left 指明偏向与规约,%right 指明偏向与shitf

yacc 的格式和lex相同,第二部分为文法定义
yacc 维护两个堆栈,1个分析站,一个内容站
分析站中保存着中介符合和非中介符合
内容站保存这这些符合对应的值
$1 代表右是的地1个成员
$$ 代表缩小后的堆栈的顶部


Flex
flex的选项影响最终生成的词法分析器的属性和行为。
这些选项可以在运行flex命令时在终端输入,也可以在.l文件中使用%option指定。

Flex 读入多个文件
main() {
for (i=1; i < argc; i++)
{
 FIEL *f = fopen(argv[i], "r");
 yyrestart(f);
 yylex();
 fclose(f)

}
}


 %option noyywrap 来不生产yywarap
          yywrap 函数已经废弃了,Flex有新的方法提供多文件输入
     %option nounistd 强制flex生成的文件不包含 unistd.h 
     %option reentrant 强制生成可重入的代码
     %option yylineno 开启行号支持 
     %option nounput 指示不要使用 input 和 unput 函数
     %option bison-bridge 适配bison,生成的API能被bison 调用
     %option header-fil="xxx.h" 指定生成的头文件的名字
     %option outifle="lex.yy.c" 指定生成的文件的名字

放在 %{ %} 前面

提交提供一个 main函数,主动调用 yylex(), 和设置不使用 yywarp 可以
   使用 %option noyywrap

不用链接flex 的库

%option yylineno
 让flex 生成一个 yylineno 的变量,指定当前的行数
 当有多个文件时, 使用yyrestart/1 ,并不会重置yylineno
  要手动重置


%%

Bison 的每条产生式后面都可以紧跟一个%prec 标记,指明该产生式的优先级等同于一个终结符
用于指定优先级

%%

Qus.
 如何界定读完了一个文件,
 读完文件需要在BNF中表示吗

 Flex 是一个特殊的pattern <<EOF>>
 但是bison 呢, 应为使用yyparse();
  所以yyparse(); 函数调用完返回后就是分析完了所有的文件
  顶层的符合可以在最后把AST的root赋值给一个全局变量
   e.g. 
   %start program
   %%
   program : stmts { programBlock = $1; }
   ;

### Flex 缓冲区
  为了提高读取文件的效率
  所有的输入缓冲都有一个共同的类型 YY_BUFFER_STATE,
  可以使用a yy_create_buffer(), 为一个特定的输入文件创建缓冲
   e.g.
   YY_BUFFER_STATE bp;
    FILE* f;
    f=fopen(...),
    bp = yy_create_buffer(f, YY_BUF_SIZE);
    yy_switch_to_buffer(bp);
    yy_flush_buffer(bp);
    yy_delete_buffer(bp);


## Flex 的一些自带函数
* input() 读入一个char
* unput(char c) 将指定的字符放回缓存区
* yyless(int n) 函数将刚读取的n个字符放回输入里
* REJECT 用于匹配一些重叠的模式

lib
 -lfl -ly
 这两个包含一个就行,主要是用来添加main 函数的
 如果你不想写main, 并且只使用了flex 就写添加-lfl
 如果bison flex 都用就只能使用 -ly, -lfl 不会调用yyparse()


### 如何写出没有二义性的文法
* 所有的二义性文法都可以转发为一个没有二义性的文法
* 如何在文法中规定操作符的结合性
     T::= T op X   op 左结合
     T::= X op T   op 右结合
× 如何在文法中规定操作符的优先级
    T::= T op1 N
    N ::= N op2 M
 op2 比op1 的优先级高
  see dc/dc.y


###C++ CPP
flex bison

flexc++
bisonc++
一套用C++ 重写的flex 和bison

About

flex and bison and compiler knolage

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published