-
Notifications
You must be signed in to change notification settings - Fork 1
lilijreey/flex
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
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 0
No packages published