版权声明：您好，转载请留下本人博客的地址，谢谢 https://blog.csdn.net/hongbochen1223/article/details/50523336
（一）：写在前面
在上面的学习当中，我们通过简单的lex例子，进一步扩展lex例子，通过和yacc的融合来进行简单英语语法分析。通过这几个例子，使我们深深的感受到lex和yacc的方便和强大功能。我们最终的目标是通过学习使用lex和yacc来实现一个简单的shell解释器，估计借用lex和yacc力量，我们的shell命令解释器实现起来就非常简单了。
（二）：英语简单语法分析扩展
在这里我们通过对上一小节中的英语句型分析程序的扩展，实现简单复合语句的分析。
我们来看一下我们的程序源码：
文件名：ch05.lex
%{
/*
* 现在我们构建一个有高级语法分析程序使用的词法分析程序
*/
#include "y.tab.h"
#define LOOKUP 0 /* 默认情况 - 不是一个定义的单词类型 */
int state;
%}
%%
\n { state = LOOKUP; }
\.\n { state = LOOKUP;
return 0; /* 句子结尾 */
}
^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);
/* 不反悔，忽略 */
}
}
}
. ;
%%
/* 定义一个单词和类型的链表 */
struct word
{
char *word_name;
int word_type;
struct word *next;
};
struct word *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;
}
int yywrap()
{
return 1;
}
在这个程序当中，和上一个小节中的内容是差不多的，主要是将相应词性的词语放到一个链表当中，便于查找。
下面我们来看一下yacc文件中的定义。
文件名：ch05.y
%{
#include <stdio.h>
/* 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 pre_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
;
pre_phrase: PREPOSITION NOUN
;
%%
extern FILE *yyin;
int main()
{
yyparse();
while(!feof(yyin)){
yyparse();
}
return 0;
}
yyerror(s)
char *s;
{
fprintf(stderr,"%s\n",s);
}
在这里，我们添加了一些符合语句的分析语法。
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 pre_phrase
;
compound_sentence: simple_sentence CONJUNCTION simple_sentence
| compound_sentence CONJUNCTION simple_sentence
;
我们来看一下这几行代码：
在上一节中，我们了解到，yacc中，越靠上的规则，其优先级越高。所以，上面的sentence规则定义了是一个简单的语句，而该简单的语句simple_sentence又在下面定义了规则subject verb object，通过这两个规则，我们定义了简单语句。
然后通过简单语句的组合又定义了复合语句，这个可以通过我们的第三条规则来看出来。
下面我们来定义一下用于编译的Makefile文件：
Makefile
all:
lex ch05.lex
yacc -d ch05.y
gcc -c lex.yy.c y.tab.c
gcc -o hello lex.yy.o y.tab.o -ll
clean:
rm lex.yy.o y.tab.o lex.yy.c y.tab.c y.tab.h hello
接着使用命令make来编译该程序，编译完成之后，我们来看一下当前目录:
.
├── ch05.lex
├── ch05.y
├── hello
├── lex.yy.c
├── lex.yy.o
├── Makefile
├── y.tab.c
├── y.tab.h
└── y.tab.o
0 directories, 9 files
现在我们来运行一下刚刚我们编译的程序，使用下面的命令来运行该程序：
./hello（三）：lex和手写的词法分析程序
下面我们通过使用lex编写一个词法分析程序和使用C语言编写词法分析程序的比较，来提高我们对lex和yacc的方便性，全面性，整体性的认识。
首先，我们先看一下使用C语言编写的简单词法分析程序，该程序用来处理命令，数字，字符串和换行，忽略注释和空白的。我们来看一下：
#include <stdio.h>
#include <ctype.h>
#define NUMBER 400
#define COMMENT 401
#define TEXT 402
#define COMMAND 403
int main(int argc,char **argv)
{
int val;
while(val = lexer())
printf("value is %d.\n",val);
return 0;
}
int lexer()
{
int c;
while((c = getchar()) == ' ' || c == '\t');
if(c == EOF)
return 0;
if(c == '.' || isdigit(c)) /* 数字 */
{
while((c = getchar()) != EOF && isdigit(c));
ungetc(c,stdin);
return NUMBER;
}
if(c == '#') /* 注释 */
{
int index = 1;
while((c = getchar()) != EOF && c != '\n');
ungetc(c,stdin);
return COMMENT;
}
if(c == '"') /* 字符串 */
{
int index = 1;
while((c = getchar()) != EOF && c != '"' && c != '\n');
if(c == '\n')
ungetc(c,stdin);
return TEXT;
}
if(isalpha(c)) /* 命令 */
{
int index = 1;
while((c = getchar()) != EOF && isalnum(c));
ungetc(c,stdin);
return COMMAND;
}
return c;
}
这个大家可以编译一下，运行起来看看效果，这里我们就不编译运行了，因为我们主要是为了对比他们的区别。
下面我们来看一下lex编写的词法分析程序：
%{
#define NUMBER 400
#define COMMENT 401
#define TEXT 402
#define COMMAND 403
%}
%%
[ \t]+ ;
[0-9]+ |
[0-9]+\.[0-9]+ |
\.[0-9]+ { return NUMBER; }
#.* { return COMMENT; }
\"[^\"\n]\" { return TEXT; }
[a-zA-Z][a-zA-Z0-9]+ { return COMMAND; }
\n { return '\n'; }
%%
#include <stdio.h>
int main(int argc,char **argv)
{
int val;
while(val = yylex())
printf("value is %d\n",val);
return 0;
}
int yywrap()
{
return 1;
}
很明显，长度上lex版本是C词法分析程序的三分之一。我们的经验是程序中的错误数一般与他的长度成正比，我们估计词法分析程序的C版本要花三倍的时间来编写和排除错误。
同时，使用C编写的词法分析程序有一个明显的错误，就是注释有两颗星的时候，就意味着注释失败：
/** 注释 **/
所以说，使用C实现的词法分析程序可能会有一些想不到的错误。
（四）：写在后面
在下面的小节中，我们将更深入的研究lex，yacc的使用，以及lex和yacc混合使用方式，来实现更加复杂的词语法分析。