本文主要是介绍《Lex 和 Yacc 》阅读笔记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
第一章：Lex 和 Yacc
最简单的Lex程序
%%
. | \n ECHO;
%%作用类似于不带参数运行的UNIX cat命令
用Lex识别单词
- 先列出要识别的一组动词：
is am are werewas be being beendo does did willwould should can couldhas have had go - 单词识别程序
%{
/** 这部分将拷贝到最终程序的原始C代码，需要包含后面文件中需要包含的头文件，由于是直接拷贝，在这里* 可以编写任何有效的C代码。* /%}%%
/*规则由两部分组成：模式+动作，模式是UNIX样式的正则表达式（由工具grep，sed和ed使用的相同表达式的扩展版本）。*/[\t ]+ /* ignore white space */ ; /* 在%{ %}外部，lex的注释必须用空白缩进 *//* "[]"表示括号中的任何一个字符都与模式匹配，"+"表示模式匹配加号前面的一个或多个连续的子模式的拷贝 */
is | /* lex模式只匹配输入字符或字符串一次。lex执行当前输入的最长可能匹配的动作。因为 "island" 是比 "is" 长的匹配，所以Lex把 "island" 看做匹配上面那条 "包括一切" 的规则。*/
am |
are |
were |
was |
be |
being |
been |
do |
does |
did |
will |
would |
should |
can |
could |
has |
have |
had |
go { printf("%s: is a verb\n", yytext); } /* yytext 数组包含匹配模式的文本 */very |
simply |
gently |
quietly |
calmly |
angrily { printf("%s: is an adverb\n", yytext); }to |
from |
behind |
above |
below |
between |
below { printf("%s: is a preposition\n", yytext); }if |
then |
and |
but |
or { printf("%s: is a conjunction\n", yytext); }their |
my |
your |
his |
her |
its { printf("%s: is an adjective\n", yytext); }I |
you |
he |
she |
we |
they { printf("%s: in a pronoun\n", yytext); }[a-zA-Z]+ { printf("%s: don't recognize, might be a noun\n", yytext); }\&.|\n { ECHO; /* normal default anyway */ }%%main()
{yylex();
}
- 运行：
% lex ch1-02.l
% cc lex.yy.c -o first -ll- 符号表：在添加新单词时不用修改和重新编译lex程序。如：
/* ch1-05.y*/# define NOUN 257# define PRONOUN 258# define VERB 259# define ADVERB 260# define ADJECTIVE 261# define PREPOSITION 262# define CONJUNCTION 263%{
/* ch1-05.l* We now build a lexical analyzer to be used by a higher-level parser.*/#include "ch1-05y.h" /* token codes from the parser */#define LOOKUP 0 /* default - not a defined word type. */int state; %}%%\n { state = LOOKUP; }\.\n { state = LOOKUP;return 0; /* end of sentence */}^verb { state = VERB; }
^adj { state = ADJECTIVE; }
^adv { state = ADVERB; }
^noun { state = NOUN; }
^prep { state = PREPOSITION; }
^pron { state = PRONOUN; }
^conj { state = CONJUNCTION; }[a-zA-Z]+ { if(state != LOOKUP) {add_word(state, yytext);} else {switch(lookup_word(yytext)) {case VERB:return(VERB);case ADJECTIVE:return(ADJECTIVE);case ADVERB:return(ADVERB);case NOUN:return(NOUN);case PREPOSITION:return(PREPOSITION);case PRONOUN:return(PRONOUN);case CONJUNCTION:return(CONJUNCTION);default:printf("%s: don't recognize\n", yytext);/* don't return, just ignore it */}}}. ; %%
/* define a linked list of words and types */
struct word {char *word_name;int word_type;struct word *next;
};struct word *word_list; /* first element in word list */extern void *malloc();int add_word(int type, char *word)
{struct word *wp; if(lookup_word(word) != LOOKUP) {printf("!!! warning: word %s already defined \n", word);return 0;}/* word not there, allocate a new entry and link it on the list */wp = (struct word *) malloc(sizeof(struct word));wp->next = word_list;/* have to copy the word itself as well */wp->word_name = (char *) malloc(strlen(word)+1);strcpy(wp->word_name, word);wp->word_type = type;word_list = wp;return 1; /* it worked */
}int lookup_word(char *word)
{struct word *wp = word_list;/* search down the list looking for the word */for(; wp; wp = wp->next) {if(strcmp(wp->word_name, word) == 0)return wp->word_type;}return LOOKUP; /* not found */
}%%/* 定义一个连接的单词和类型列表。在产品环境中，会使用散列表去存储。*/
struct word {char *word_name;int word_type;struct word *next;
};struct word *word_list; /* first element in word list */extern void *malloc();int add_word(int type, char *word)
{struct word *wp; if(lookup_word(word) != LOOKUP) {printf("!!! warning: word %s already defined \n", word);return 0;}/* 单词不在那里，分配一个新的条目并将它连接到列表上 */wp = (struct word *) malloc(sizeof(struct word));wp->next = word_list;/* 必须复制单词本身 */wp->word_name = (char *) malloc(strlen(word)+1);strcpy(wp->word_name, word);wp->word_type = type;word_list = wp;return 1; /* 它被处理过 */
}int lookup_word(char *word)
{struct word *wp = word_list;/* 向下搜索列表以寻找单词 */for(; wp; wp = wp->next) {if(strcmp(wp->word_name, word) == 0){return wp->word_type;}}return LOOKUP; /* 没有找到 */
}
- 词法分析程序和语法分析程序的通信：语法分析程序（parser）是较高级别的例程，当它需要来自输入的标记时，就调用词法分析程序。词法分析程序找到对语法分析程序有意义的标记就返回到语法分析程序，将返回标记的代码作为yylex()的值。词法分析程序和语法分析程序必须对标记代码的内容达成一致。通过让yacc定义标记代码来解决这个问题。Yacc可以生产包含所有标记定义的C头文件（y.tab.h包含在词法分析程序中，并且在词法分析程序动作代码中采用这些预处理程序符号，即替代之前的ch1-05.y）。
%{
#include <stdio.h>
/* chi-06.y* we found the following required for some yacc implementations. */
/* #define YYSTYPE int */
%}%token NOUN PRONOUN VERB ADVERB ADJECTIVE PREPOSITION CONJUNCTION%%sentence: simple_sentence { printf("Parsed a simple sentence.\n"); }| compound_sentence { printf("Parsed a compound sentence.\n"); }; simple_sentence: subject verb object| subject verb object prep_phrase;compound_sentence: simple_sentence CONJUNCTION simple_sentence| compound_sentence CONJUNCTION simple_sentence;subject: NOUN| PRONOUN| ADJECTIVE subject;verb: VERB| ADVERB VERB| verb VERB;object: NOUN| ADJECTIVE object;prep_phrase: PREPOSITION NOUN;%%extern FILE *yyin;main()
{while(!feof(yyin)) {yyparse();}
}yyerror(s)
char *s;
{fprintf(stderr, "%s\n", s);
}
- 运行Lex 和 Yacc：创建一个新的工程，写好l和y文件，把lex和yacc配置文件拷贝到目录中，设置工程属性（预编译：
@set BISON_SIMPLE=bison.simple，Debugging里Command arguments选择
@set BISON_HAIRY=bison.hairy
$(ProjectDir)bison -d ch1-06.y
$(ProjectDir)flex ch1-06.l<input.txt，把input.txt放入与源代码共同的文件夹下）
第二章：使用Lex
正则表达式
. 匹配除换行符以外的任何单个字符
* 匹配前面表达式的菱格或多个拷贝
[] 匹配括号中的任意的字符类。如果第一个字符时"^"，它的含义改变为匹配除括号中的字符以外的任意字符。"-"或"|"作为"["后的第一个字符时照字面意义解释。除了识别仪"\"开始的C转义序列以外，其他元字符在方括号中没有特殊含义。
^ 作为正则表达式的第一个字符匹配行的开头
$ 作为正则表达式的最后一个字符匹配行的结尾
{} 当括号中包含一个或2个数字时，指示前面的模式被允许匹配多少次。如A{1,3}表示匹配字符A一次到三次如果包含名称，认为是以该名称替换。
\ 用于转移元字符
+ 匹配前面的正则表达式的一次货多次出现
? 匹配前面的正则表达式的零次或一次出现。如-?[0-9]+匹配包括一个可选的前导减号的有符号的数字。
| 匹配前面的正则表达式或随后的正则表达式
"..." 引号中的每个字符解释为字面意义，除C转义序列外元字符会失去他们的特殊含义
/ 只有在后面跟有指定的正则表达式时才匹配前面的正则表达式。如0/1匹配字符串"01"中的"0"，但不匹配字符串"0"或"02"中的任何字符。由跟在斜线后的模式所匹配的内容不被"使用"，并且会被转变成随后的标记。每个模式只允许一个斜线。
() 将一系列正则表达式组成一个新的正则表达式.下面举一些例子：
[0-9]+ 整数
[0-9]*\.[0-9]+ 小数
-?(([0-9]+)|([0-9]*\.[0-9]+)([eE][-+]?[0-9]+)?)数字lex在匹配时有一个内部输入缓冲区，如果输入文本错误可能导致缓冲区溢出，可以考虑使用yymore。
- 统计单词数目
%{
unsigned charCount = 0, wordCount = 0, lineCount = 0;
%}word [^ \t\n]+ /*Lex替换机制*/
eol \n
%%
{word} { wordCount++; charCount += yyleng; }/*当存在两个同样长度的字符串时，词法分析程序使用lex的早起规则。因此"I"由{word}规则匹配，而不是由"."规则匹配。*/
{eol} { charCount++; lineCount++; }
. charCount++;
%%
/*当yylex()到达输入文件的尾端时，会调用yywrap()，该函数返回数值0或1。如果值为1，则程序完成且没有输入；如果值为0，则词法分析程序假设yywrap（）已经打开了它要读取的另一个文件，并继续读取yyin。*/
int yywrap()
{return 1;
}
int main()
{yylex();printf("%d %d %d\n",charCount, wordCount, lineCount);return 0;
}
当要求多个输入文件时：
%{
/** ch2-03.l** The word counter example for multiple files**/unsigned long charCount = 0, wordCount = 0, lineCount = 0;#undef yywrap /* sometimes a macro by default */%}word [^ \t\n]+
eol \n
%%
{word} { wordCount++; charCount += yyleng; }
{eol} { charCount++; lineCount++; }
. charCount++;
%%char **fileList;
unsigned currentFile = 0;
unsigned nFiles;
unsigned long totalCC = 0;
unsigned long totalWC = 0;
unsigned long totalLC = 0;main(argc,argv)
int argc;
char **argv;
{FILE *file;fileList = argv+1;nFiles = argc-1;if (argc == 2) {/** we handle the single file case differently from* the multiple file case since we don't need to* print a summary line*/currentFile = 1;file = fopen(argv[1], "r");if (!file) {fprintf(stderr,"could not open %s\n",argv[1]);exit(1);}yyin = file;}if (argc > 2)yywrap(); /* open first file */yylex();/** once again, we handle zero or one file* differently from multiple files.*/if (argc > 2) {printf("%8lu %8lu %8lu %s\n", lineCount, wordCount,charCount, fileList[currentFile-1]);totalCC += charCount;totalWC += wordCount;totalLC += lineCount;printf("%8lu %8lu %8lu total\n",totalLC, totalWC, totalCC);} elseprintf("%8lu %8lu %8lu\n",lineCount, wordCount, charCount);
return 0;
}/** the lexer calls yywrap to handle EOF conditions (e.g., to* connect to a new file, as we do in this case.)*/yywrap()
{FILE *file;if ((currentFile != 0) && (nFiles > 1) && (currentFile < nFiles)) {/** we print out the statistics for the previous file.*/printf("%8lu %8lu %8lu %s\n", lineCount, wordCount,charCount, fileList[currentFile-1]);totalCC += charCount;totalWC += wordCount;totalLC += lineCount;charCount = wordCount = lineCount = 0;fclose(yyin); /* done with that file */}while (fileList[currentFile] != (char *)0) {file = fopen(fileList[currentFile++], "r");if (file != NULL) {yyin = file;break;}fprintf(stderr,"could not open %s\n",fileList[currentFile-1]);}
return (file ? 0 : 1); /* 0 means there's more input */
}
- 分析命令行
%{#undef input /* AT&T中lex默认将input和unput定义为宏，所以将它们接触定义(#undef)，然后重新定义为C函数 */#undef unputint input(void);void unput(int ch);unsigned verbose;unsigned fname;char *progName;
%}%s FNAME /* 在词法分析程序中创建新的起始状态 */%%h |
"-?" |
-help { printf("usage is : %s [-help | -h | ? ][verbose | -v\] [(-file)filename]n", progName); }
-v ?
-verbose { printf("verbose mode is on\n"); verbose = 1; }
-f |
-file { BEGIN FNAME; fname = 1; /* -file参数企鹅胡安娜为FNAME状态，激活匹配文件名的模式。一旦它匹配了文件名，就切换回正则状态。*/}<FNAME>[^ ]+ { printf("use file %s\n", yytext); BEGIN 0; fname = 2; }[^ ]+ ECHO;
%%char **targv; /* 记录参数 */
char **argLim; /* 参数结束 */main(int argc, char **argv)
{progName = *argv;argv = argv + 1;arglim = argv - argc;yylex();if (fname < 2){printf("No filename given\n");}
}static unsigned offset = 0; /* 跟踪当前参数中的位置 *//* input()程序处理来自词法分析程序的获取字符的调用。当前的参数用尽时，它就移到下一个参数（如果有一个的话）并继续扫描。如果没有参数，就把它作为词法分析程序的文件尾条件并返回一个零字节。*/int input(void){char c;if (targv >= arglim){return (0); /* EOF */}/* 参数结束，移到下一个 */if ((c = targv[0][offset +=1 ]) != '\0')){return (c);}targv++;offset = 0;return (' ');
}/* 只简单推回原来的备份，不允许送回不同的文本。unput()程序处理来自词法分析程序的将字符“推回”输入流的调用。通过颠覆指针的方向来完成这项工作，在字符串中反向移动。在这种情况下，首先假设推回的字符与位于那儿的字符相同，除非动作代码明确地推回其他的东西，否则这种情况总是真的。一般情况下，动作程序可以推回它想推回的任何东西，而且unput（）的专用版本必须能处理这种情况。 */
void unput(int ch){/* Lex sometimes puts back the EOF */if (ch == 0){return ; /* 忽略，不能送回EOF */}if (offset){ /* 备份当前参数 */offset--;return;}targv--; /* 返回到前一个参数 */offset = strlen(*targv);
} - 关于起始状态
%s MAGIC%%
<MAGIC>.+ { BEGIN 0; printf("Magic: "); ECHO; }
magic { BEGIN MAGIC; }
%%main(){yylex();
} 当看到关键字“magic”时切换到MAGIC状态；否则，只回送输入。如果处于MAGIC状态，就在下一个被回送的标记前插入字符串“Magic：”。创建一个具有三个单词的输入文件：magic、two和three，并在整个词法分析程序中运行它。
%ch2-07 < magic.inputMagic:two
three如果改动一下示例，使具有起始状态的规则跟在一个没有起始状态的规则之后：
%{/* 这个示例故意不工作！*/
%}%s MAGIC%%
magic { BEGIN MAGIC; }
.+ { ECHO; }
<MAGIC>.+ { BEGIN 0; printf("Magic: "); ECHO; }
%%main(){yylex();
}得到了不同的结果：
%ch2-08 < magic.inputtwo
three可以将没有起始状态的规则隐式地认为具有一个”通配符“起始状态，它们匹配所有的其实状态，这常常是错误的根源。
- C源代码分析程序：检查C源文件并计算所看到的不同类型的行的数目，这些行有些包含代码，有些只包含注释或者空白。
%{int comments, code, whiteSpace;
%}%x COMMENT%%
^[.\t]*"/*" { BEGIN COMMENT; /* 进入注释处理状态 */}
^[ \t]*"/*".*"*/"[ \t]*\n { comments++; /* 自包含注释 */}
<COMENT>"*/"[ \t]*\n {BEGIN 0; comments++; }
<COMMENT>"*/" { BEGIN 0; }
<COMMENT>\n { comments++; }
<COMMENT>.\n { comments++; /* 强制匹配行结束，则当代码和注释在一行时认为一行注释和一行代码。*/}^[ \t]*\n { whiteSpace++; /* 空白行 */}.+"/*".*"*/".*\n { code++; }
.*"/*".*"*/".*\n { code++; }
.+"/*".*\n { code++; BEGIN COMMENT; }
.\n { code++; }. ; /* 忽略其他东西 */
%%main()
{yylex();printf("code: %d, comments %d, whitespace %d\n", code, comments, whiteSpace);
}第二章：使用yacc
Yacc不能处理需要向前看多于一个的标记才能确定它是否已经匹配一条规则的语法。例如：
phrase-->cart_animal AND CART| word_animal AND PLOW
cart_animal-->HORSE | GOAT
word_animal-->HORSE | OX需要修改为：
phrase-->cart_animal CART| word_animal PLOW分为定义段，规则段，符号值和动作：
%token NAME NUMBER
%%
statement: NAME '=' expression /* 单个被引起来的字符可以作为标记而不用声明它们*/| expression { printf(" = %d\n", $1); };expression: expression '+' NUMBER { $$ = $1 + $3; /* 默认情况下，yacc使所有值类型为int */}| expression '-' NUMBER { $$ = $1 - $3; }| NUMBER { $$ = $1; };其对应的lex文件为：
%{
#include "ch3-01.tab.h"
extern int yylval;
%}%%
[0-9]+ { yylval = atoi(yytext); return NUMBER; }
[ \t] ; /* ignore white space */
\n return 0; /* logical EOF */
. return yytext[0];
%%
void yyerror(char *s)
{fprintf(stderr,"%s\n",s);
}
int yywrap()
{return 1;
}
int main()
{yyparse();return 0;
}使用隐式表示优先级方法：
expression: expression '+' mulexp| expression '-' mulexp| mulexp;
mulexp: mulexp '*' primary| mulexp '/' primary| primary;
primary: '(' expression ')'| '-' primary| NUMBER;显式指定优先级：
%left '+' '-' /* 左结合且处于最低的优先级 */
%left '*' '/' /* 右结合且处于较高优先级 */
%nonassoc UMINUS /* UMINUS是一元减号的伪标记，没有结合规则且处于最高的优先级*/则使用了优先级后的yacc：
%token NAME NUMBER
%left '-' '+'
%left '*' '/'
%nonassoc UMINUS%%statement: NAME '=' expression| expression { printf("= %d\n", $1); };expression: expression '+' expression { $$ = $1 + $3; }| expression '-' expression { $$ = $1 - $3; }| expression '*' expression { $$ = $1 * $3; }| expression '/' expression{ if($3 == 0)yyerror("divide by zero");else$$ = $1 / $3;}| '-' expression %prec UMINUS { $$ = -$2; }| '(' expression ')' { $$ = $2; }| NUMBER { $$ = $1; };
%%
当加入有类型的标记时：
%{
double vbltable[26];
%}%union {double dval;int vblno;
}%token <vblno> NAME
%token <dval> NUMBER
%left '-' '+'
%left '*' '/'
%nonassoc UMINUS%type <dval> expression
%%
statement_list: statement '\n'| statement_list statement '\n';statement: NAME '=' expression { vbltable[$1] = $3; }| expression { printf("= %g\n", $1); };expression: expression '+' expression { $$ = $1 + $3; }| expression '-' expression { $$ = $1 - $3; }| expression '*' expression { $$ = $1 * $3; }| expression '/' expression{ if($3 == 0.0)yyerror("divide by zero");else$$ = $1 / $3;}| '-' expression %prec UMINUS { $$ = -$2; }| '(' expression ')' { $$ = $2; }| NUMBER| NAME { $$ = vbltable[$1]; };
%%
其相应的lex要改为：
%{
#include "yacc.tab.h"
#include <math.h>
//extern double vbltable[26];
%}%%
([0-9]+|([0-9]*\.[0-9]+)([eE][-+]?[0-9]+)?) {
yylval.dval = atof(yytext); return NUMBER;
}[ \t] ; /* ignore white space */[a-z] { yylval.vblno = yytext[0] - 'a'; return NAME; }"$" { return 0; /* end of input */ }\n |
. return yytext[0];
%%
void yyerror(char *s)
{
fprintf(stderr,"%s\n",s);
}
int yywrap()
{
return 1;
}
int main()
{
yyparse();
while (1);
return 0;
}符号表
#define NSYMS 20 /* maximum number of symbols */struct symtab {char *name;double value;
} symtab[NSYMS];struct symtab *symlook();/* 以文本字符串形式的名字为参数，并返回适当的符号表条目的指针，如果不存在，就添加它*/则具有符号表的yacc：
%{
#include "ch3hdr.h"
#include <string.h>
%}%union {double dval;struct symtab *symp;
}
%token <symp> NAME
%token <dval> NUMBER
%left '-' '+'
%left '*' '/'
%nonassoc UMINUS%type <dval> expression
%%
statement_list: statement '\n'| statement_list statement '\n';statement: NAME '=' expression { $1->value = $3; }| expression { printf("= %g\n", $1); };expression: expression '+' expression { $$ = $1 + $3; }| expression '-' expression { $$ = $1 - $3; }| expression '*' expression { $$ = $1 * $3; }| expression '/' expression{ if($3 == 0.0)yyerror("divide by zero");else$$ = $1 / $3;}| '-' expression %prec UMINUS { $$ = -$2; }| '(' expression ')' { $$ = $2; }| NUMBER| NAME { $$ = $1->value; };
%%
/* look up a symbol table entry, add if not present 用散列表效率更高些*/
struct symtab *
symlook(s)
char *s;
{char *p;struct symtab *sp;for(sp = symtab; sp < &symtab[NSYMS]; sp++) {/* is it already here? */if(sp->name && !strcmp(sp->name, s))return sp;/* is it free */if(!sp->name) {sp->name = strdup(s);/* 容易出错，因为后来的标记会重写yytext*/return sp;}/* otherwise continue to next */}yyerror("Too many symbols");exit(1); /* cannot continue */
} /* symlook */
其相应lex改为：
%{
#include "ch3-04.tab.h"
#include "ch3hdr.h"
#include <math.h>
%}%%
([0-9]+|([0-9]*\.[0-9]+)([eE][-+]?[0-9]+)?) {
yylval.dval = atof(yytext);
return NUMBER;
}[ \t] ; /* ignore white space */[A-Za-z][A-Za-z0-9]* { /* return symbol pointer */
yylval.symp = symlook(yytext);
return NAME;
}"$" { return 0; }\n |
. return yytext[0];
%%
void yyerror(char *s)
{
fprintf(stderr,"%s\n",s);
}
int yywrap()
{
return 1;
}
int main()
{
yyparse();
return 0;
}下面在符号表中添加保留字（？没看懂）
struct symtab {char *name;double (*funcptr)();double value;
}symtab[NSYMS];这篇关于《Lex 和 Yacc 》阅读笔记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
