Lex+Yacc使用方法(本文档是后面实验内容用到).doc

Lex(Lexical Analyzar 词法分析生成器)，Yacc(Yet Another Compiler Compiler编译器代码生成器)是 Unix 下十分重要的词法分析，语法分析的工具经常用于语言分析，公式编译等广泛领域遗憾的是网上中文资料介绍不是过于简单，就是跳跃太大，入门参考意义并不大本文通过循序渐进的例子，从 0 开始了解掌握 Lex 和Yacc 的用法一.Lex(Lexical Analyzar) 初步示例先看简单的例子(注：本文所有实例皆在 RetHat Linux 下完成):一个简单的 Lex 文件 exfirst.l 内容：%{#include "stdio.h"%}%%[/n] ;[0-9]+ printf("Int : %s/n",yytext);[0-9]*/.[0-9]+ printf("Float : %s/n",yytext);[a-zA-Z][a-zA-Z0-9]* printf("Var : %s/n",yytext);[/+/-/*///%] printf("Op : %s/n",yytext);. printf("Unknown : %c/n",yytext[0]);%%在命令行下执行命令 flex 解析，会自动生成 lex.yy.c 文件：[root@localhost liweitest]flex exfirst.l进行编译生成 parser 可执行程序：[root@localhost liweitest]cc -o parser lex.yy.c -ll[注意：如果不加-ll 链结选项，cc 编译时会出现以下错误，后面会进一步说明。

]/usr/lib/gcc-lib/i386-redhat-linux/3.2.2/../../../crt1.o(.text+0x18): In function `_start':../sysdeps/i386/elf/start.S:77: undefined reference to `main'/tmp/cciACkbX.o(.text+0x37b): In function `yylex':: undefined reference to `yywrap'/tmp/cciACkbX.o(.text+0xabd): In function `input':: undefined reference to `yywrap'collect2: ld returned 1 exit status创建待解析的文件 file.txt：titlei=1+3.9;a3=909/6bcd=4%9-333通过已生成的可执行程序，进行文件解析[root@localhost liweitest]# ./parser 其中规则部分是必须的，定义和用户子程序部分是任选的 (1)定义部分定义部分起始于 %{ 符号，终止于 %} 符号，其间可以是包括 include 语句、声明语句在内的 C 语句。

这部分跟普通 C 程序开头没什么区别{#include "stdio.h"int linenum;%}(2) 规则部分规则部分起始于"%%"符号，终止于"%%"符号，其间则是词法规则词法规则由模式和动作两部分组成模式部分可以由任意的正则表达式组成，动作部分是由 C 语言语句组成，这些语句用来对所匹配的模式进行相应处理需要注意的是，lex 将识别出来的单词存放在 yytext[]字符数据中，因此该数组的内容就代表了所识别出来的单词的内容类似 yytext 这些预定义的变量函数会随着后面内容展开一一介绍动作部分如果有多行执行语句，也可以用{}括起来title showtitle();[/n] linenum++;[0-9]+ printf("Int : %s/n",yytext);[0-9]*/.[0-9]+ printf("Float : %s/n",yytext);[a-zA-Z][a-zA-Z0-9]* printf("Var : %s/n",yytext);[/+/-/*///%] printf("Op : %s/n",yytext);. printf("Unknown : %c/n",yytext[0]);%%A.规则部分的正则表达式规则部分是 Lex 描述文件中最为复杂的一部分，下面列出一些模式部分的正则表达式字符含义：A-Z, 0-9, a-z 构成模式部分的字符和数字。

指定范围例如：a-z 指从 a 到 z 之间的所有字符/ 转义元字符用来覆盖字符在此表达式中定义的特殊意义，只取字符的本身[] 表示一个字符集合匹配括号内的任意字符如果第一个字符是^那么它表示否定模式例如: [abC] 匹配 a, b, 和 C的任何一个^ 表示否定 匹配 0 个或者多个上述模式 匹配 1 个或者多个上述模式 匹配 0 个或 1 个上述模式 作为模式的最后一个字符时匹配一行的结尾{ } 表示一个模式可能出现的次数 例如: A{1,3} 表示A 可能出现 1 次或 3 次[a-z]{5} 表示长度为 5 的，由 a-z 组成的字符此外，还可以表示预定义的变量 匹配任意字符，除了 /n。

) 将一系列常规表达式分组如：{Letter}({Letter}|{Digit})*| 表达式间的逻辑或"一些符号" 字符的字面含义元字符具有如："*" 相当于 [/*]/ 向前匹配如果在匹配的模式中的"/"后跟有后续表达式，只匹配模版中"/"前面的部分如：模式为 ABC/D 输入 ABCD，时 ABC 会匹配 ABC/D，而 D 会匹配相应的模式输入 ABCE 的话，ABCE 就不会去匹配 ABC/DB.规则部分的优先级规则部分具有优先级的概念，先举个简单的例子：%{#include "stdio.h"%}%%[/n] ;A {printf("ONE/n");};AA {printf("TWO/n");};AAAA {printf("THREE/n");};%%此时，如果输入内容：[root@localhost liweitest]# cat file1.txtAAAAAAA[root@localhost liweitest]# ./parser 一、Lex 理论Lex 使用正则表达式从输入代码中扫描和匹配字符串。

每一个字符串会对应一个动作通常动作返回一个标记给后面的剖析器使用，代表被匹配的字符串每一个正则表达式代表一个有限状态自动机(FSA)我们可以用状态和状态间的转换来代表一个(FSA)其中包括一个开始状态以及一个或多个结束状态或接受状态我们以上文《Lex 和 Yacc 应用方法(一).初识 Lex》第一个例子详细说明：exfirst.l %{#include "stdio.h"%}%%[/n] ; A[0-9]+ printf("Int : %s/n",yytext); B[0-9]*/.[0-9]+ printf("Float : %s/n",yytext); C[a-zA-Z][a-zA-Z0-9]* printf("Var : %s/n",yytext); D[/+/-/*///%] printf("Op : %s/n",yytext); E. printf("Unknown : %c/n",yytext[0]); F%%这里使用一相对简单的输入文件 file.txti=1.344+39;bcd=4%9-333我们假定，Lex 系统创建一动态列表：内容+规则+状态Lex 状态：1 接受 2 结束接受表示该元素可以做为模式匹配结束表示该元素已完成模式匹配读入“i” [查找元素]查找相邻且状态为 1 的元素，无元素，[匹配规则]D，[新增列表并置数据](存在则覆盖)状态为 1，规则为 D，内容为"i"。

[操作顺序符] 1读入“=” [查找元素]查找相邻且状态为 1 的元素，“i=”寻找匹配规则，无规则[置上一元素]状态为 2[匹配规则]F，[新增列表并置数据](存在则覆盖)状态为 1，规则为 F，内容为"=" [操作顺序符] 2读入“1”，[查找元素]查找相邻且状态为 1 的元素，“=1”寻找匹配规则，无规则[置上一元素]状态为 2[匹配规则]B,[新增列表并置数据](存在则覆盖)状态为 1，规则为 B，内容为"1"[操作顺序符] 3读入“.” [查找元素]查找相邻且状态为 1 的元素，“1.”寻找匹配规则，无规则，但有潜在规则 C[匹配规则]F,[新增列表并置数据](存在则覆盖)状态为 1，规则为 F，内容为"."[置上一元素]状态为 1[操作顺序符] 4读入“3” [查找元素]查找相邻且状态为 1 的元素，“1.3”寻找匹配规则，有规则[置起始元素]状态为 1，规则为 C，内容为"1.3"[操作顺序符] 3 组合元素的起始操作符读入“4” [查找元素]查找相邻且状态为 1 的元素，“1.34”寻找匹配规则，有规则[置起始元素]状态为 1，规则为 C，内容为"1.34"[操作顺序符] 3 组合元素的起始操作符读入“4” [查找元素]查找相邻且状态为 1 的元素，“1.344”寻找匹配规则，有规则[置起始元素]状态为 1，规则为 C，内容为"1.344"[操作顺序符] 3 组合元素的起始操作符读入“+” [查找元素]查找相邻且状态为 1 的元素，“1.344+”寻找匹配规则，无规则[匹配规则]E,[新增列表并置数据](存在则覆盖)状态为 1，规则为 E，内容为"+"[置上一元素]状态为 2[操作顺序符] 4... 最后解析结果为内容 规则 状态i D 2= F 21.344 C 2+ E 2...上面列出的算法是仅属于个人的分析，是相对直观且便于理解的，也可以参照这个算法用 C 语言模拟出 lex 的效果。

不过真正的 Lex 算法肯定是更为复杂的理论体系，这个没有接触过，有兴趣可以参看相关资料二、yacc 的 BNF 文件个人认为 lex 理论比较容易理解的，yacc 要复杂一些我们先从 yacc 的文法说起yacc 文法采用 BNF。