2007年12月20日星期四

lex/yacc系列:lex中的起始状态

词法分析程序中的起始状态(start state),是一种捕获对上下文敏感信息的方法。用起始状态标记规则,是通知词法分析程序只有在起始状态有效的情况下才识别该规则。

下面的示例统计C源文件中不同类型的行的数目,这些行有些包含代码,有些只包含注释或者空白。

%{
int nCommentLine, nCodeLine, nWhiteLine;
%}

%x COMMENT

%%
^[ \t]*"/*" { BEGIN COMMENT; }
^[ \t]*"/*".*"*/"[ \t]*\n { ++nCommentLine; }

<COMMENT>"*/"[ \t]*\n { BEGIN 0; ++nCommentLine; }
<COMMENT>"*/"         { BEGIN 0; }
<COMMENT>\n           { ++nCommentLine; }
<COMMENT>.\n          { ++nCommentLine; }

^[ \t]*\n { ++nWhiteLine; }

.+"/*".*"*/".*\n { ++nCodeLine; }
.*"/*".*"*/".+\n { ++nCodeLine; }
.+"/*".*\n       { ++nCodeLine; BEGIN COMMENT; }
.\n              { ++nCodeLine; }

. ;

%%
main()
{
 yylex();

 printf("code line: %d, comment line: %d, whitespace %d\n",
    nCodeLine, nCommentLine, nWhiteLine);
}

空白行的正则表达式描述:

^[ \t]*\n

“^”表示这种模式必须起始于行首。允许空格和制表符,但没有其他东西。以换行符“\n”结尾。

代码行或注释行被描述为任何不完全是空白的行。

^[ \t]*\n
\n   /* 空白行被前一条规则匹配 */
.    /* 其他东西 */

使用新的规则“\n”来统计不全是空白的行的数目,“.”用来丢弃无关字符。

下面的规则描述了处于一行的单个、自包含的注释,注释文本位于“/*”和“*/”之间:

^[ \t]*"/*".*"*/"[ \t]*\n

由于注释可以跨越多行,在定义部分,添加

%x COMMENT

它在词法分析程序中创建新的起始状态。在规则部分,添加以“<COMMENT>”开始的规则。这些规则只有在词法分析程序处于COMMENT状态时被识别。当看到注释的开头时,进入起始状态:

^[ \t]*"/*" { BEGIN COMMENT; }

动作中的BEGIN语句切换到COMMENT状态。这条规则要求注释始于行首,可以避免遇到下述情况时的计数错误:

int counter; /* this is
    a strange comment */

第一行并不是单独的一行。我们需要将第一行计为代码行,第二行作为注释行计算。下面是实现规则:

.+"/*".*"*/".*\n
.*"/*".*"*/".+\n

上述两个表达式描述的字符串集合有重叠,但并不完全相同。下面的表达式匹配第一条规则,但不符合第二个:

int counter; /* comment */

因为第二条规则要求注释后面有文字。同样,下面的表达式符合第二个规则,但不匹配第一条:

/* comment */ int counter;

它们都匹配下面的表达式:

/* comment #1 */ int counter; /* comment #2 */

下面来完成检测注释的正则表达式。我们采用起始状态,当处于COMMENT状态时,仅需要寻找换行符:

<COMMENT>\n
<COMMENT>.\n

并进行计数。第一条规则处理注释中的空行,第二条则处理注释中有文本的行。当检测到注释结尾时,如果后面没有其他东西,就把它作为注释行计数,否则就继续处理:

<COMMENT>"*/"[ \t]*\n { BEGIN 0; ++nCommentLine; }
<COMMENT>"*/"         { BEGIN 0; }

第一条规则计为注释行,第二条继续处理。动作中的“BEGIN 0”回到默认状态,退出COMMENT状态。

2007年12月7日星期五

lex/yacc系列:yacc进阶(四)

为计算器添加的另一个功能是数学函数,例如平方根、指数和对数。

蛮干的方法是把每个函数名作为单独的标记,然后为每个函数添加单独的规则:

%token SQRT LOG EXP
...
%%
expression: ...
 ¦ SQRT '(' expression ')' { $$ = sqrt($3); }
 ¦ LOG '(' expression ')'  { $$ = log($3); }
 ¦ EXP '(' expression ')'  { $$ = exp($3); }

在扫描程序中,则需要为输入“sqrt”返回标记SQRT,等等:

sqrt return SQRT;
log return LOG;
exp return EXP;

[A-Za-z][A-Za-z0-9]* { ...

特殊模式应放在一般模式的前面,以确保正确的匹配。

这种方式可以工作,但是存在问题。一个问题是必须在语法分析程序和词法分析程序中为每个函数硬性编码,这样的工作单调乏味,很难添加很多的函数。另一个问题是函数名应该是保留字,也就是说,sqrt不能作为变量名使用。后者是否成为问题取决于你的意图。

我们将函数名放置在符号表中,而不是作为特殊模式放入词法分析程序中。为符号表条目增加一个新的字段funcptr,如果该条目是一个函数名,它的值就是指向C函数的指针。

struct symtab {
 char *name;
 double (*funcptr)();
 double value;
} symtab[NSYMS];

必须在分析程序开始之前将函数名放入符号表,因此需要编写自己的main()函数,它调用新例程addfunc(),将每个函数名添加到符号表,然后调用yyparse()addfunc()的代码实现是,得到对应于名字的符号表条目并设置funcptr字段。

main()
{
 addfunc("sqrt", sqrt);
 addfunc("exp", exp);
 addfunc("log", log);

 yyparse();
}

void
addfunc(char *name, double (*func)())
{
 struct symtab *sp = symlook(name);
 sp->funcptr = func;
}

定义代表函数名的标记FUNC,词法分析程序看到函数名时返回FUNC,看到变量名时则返回NAME,两者的值都是符号表指针。

在语法分析程序中,用一个通用的函数规则替代每个函数的单独的规则:

%token <symp> NAME FUNC
%%
expression: ...
 ¦ FUNC '(' expression ')' { $$ = ($1->funcptr)($3); }

当语法分析程序看到函数引用时,它可以通过该函数在符号表中的条目找到真正的内部函数引用。

在词法分析程序中,不使用显式匹配函数名的模式,而是修改名字的动作代码,如果符号表条目表明是一个函数名就返回FUNC

[A-Za-z][A-Za-z0-9]* {
  struct *symtab *sp = symlook(yytext);

  yylval.symp = sp;
  if (sp->funcptr)
   return FUNC;
  else
   return NAME;
 }

上面的实现可以达到目的,但我们将再次进行修改。这最后的修改从技术角度而言很小,但从编程语言的层次而言是个很大的改变。将函数名和变量名区分开毫无理由:语法分析程序可以通过语法辨别函数和变量!

因此恢复词法分析程序,对于任何名字总是返回NAME。然后修改语法分析程序,在处理函数时仍使用NAME

%token NAME
%%
expression: ...
 ¦ NAME '(' expression ')' { ... }

下面是完整的源代码。头文件:

#define NSYMS 20

struct symtab {
 char *name;
 double (*funcptr)();
 double value;
} symtab[NSYMS];

struct symtab *symlook();

语法分析程序:

%{
#include "calc5.h"
#include <string.h>
#include <math.h>

int nsym = 0;
%}

%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; }
 ¦ NAME '(' expression ')'
    { if ($1->funcptr)
       $$ = ($1->funcptr)($3);
      else {
       printf("%s not a function\n", $1->name);
       $$ = 0.0;
      }
    }
 ;

%%
struct symtab *
symlook(char *s)
{
 int i;

 for (i = 0; i < nsym; ++i) {
  if (!strcmp(symtab[i].name, s))
   return &symtab[i];
 }

 if (nsym < NSYMS) {
  symtab[nsym].name = strdup(s);
  ++nsym;
  return &symtab[nsym-1];
 }

 yyerror("Too many symbols");
 exit(1);
}

void
addfunc(char *name, double (*func)())
{
 struct symtab *sp = symlook(name);
 sp->funcptr = func;
}

main()
{
 addfunc("sqrt", sqrt);
 addfunc("exp", exp);
 addfunc("log", log);

 yyparse();
}

在语法分析程序中,添加了错误检测,以确保用户调用的函数是一个真正的函数。

词法分析程序:

%{
#include "y.tab.h"
#include "calc5.h"
#include <math.h>
%}

%%
([0-9]+|([0-9]*\.[0-9]+)([eE][-+]?[0-9]+)?) {
  yylval.dval = atof(yytext);
  return NUMBER;
 }

[ \t] ;

[A-Za-z][A-Za-z0-9]* {
  yylval.symp = symlook(yytext);
  return NAME;
 }

"$"   { return 0; }

\n    ¦
.     { return yytext[0]; }

%%

除了函数名和变量名可以重合外,计算器如所期望的进行操作。

% calc5
sqrt(3)
= 1.73205
foo(3)
foo not a function
= 0
sqrt = 5
sqrt(sqrt)
= 2.23607

至于是否允许用户在同一程序中对函数和变量使用同样的名字,现在还有争论。如果允许,可能会造成程序难以理解;如果不允许,又可能迫使用户发明新的名字,以避免与保留字冲突。两者都可能走向极端。COBOL语言有300个保留字,没有人能够完全记住它们,因此程序员采用了一些奇怪的约定,例如每个变量名以数字开头,以确保不会与保留字冲突。另一方面,PL/I语言则根本没有保留字,因此如下的令人糊涂的代码是允许的:

IF IF = THEN THEN ELSE = THEN; ELSE ELSE = IF;

最后是编译该程序的Makefile:

LEX = lex
YACC = yacc

CC = cc -DYYDEBUG=1

calc5: y.tab.o lex.yy.o
  $(CC) -o calc5 y.tab.o lex.yy.o -ly -ll -lm

lex.yy.o: lex.yy.c "y.tab.h

lex.yy.o y.tab.o: calc5.h

y.tab.c "y.tab.h: calc5.y
  $(YACC) -d calc5.y

lex.yy.c: calc5.l
  $(LEX) calc5.l

有关make的更多信息,请参考其他资料。

2007年12月5日星期三

lex/yacc系列:yacc进阶(三)

下面我们使用符号表——一种用来跟踪使用中的名字的结构,来增加使用长变量名的能力。每次语法分析程序读取输入中的名字,它都在符号表中查找这个名字,并且得到一个对应于符号表条目的指针。因为符号表要求词法分析程序和语法分析程序之间共享数据结构,所以我们创建一个头文件calc4.h:

#define NSYMS 20 /* 允许的符号个数 */

struct symtab {
  char *name;
  double value;
} symtab[NSYMS];

struct symtab *symlook();

在这个实现中,符号表是一个结构数组(也可以使用其他类型的数据结构,例如链表),每个结构包含变量的名字和它的值。还声明了一个函数symlook(),它以文本字符串形式的名字为参数,返回对应的符号表条目的指针,如果不存在,就添加。

语法分析程序只需要少许修改,以使用符号表:

%{
#include "calc4.h"
#include

int nsym = 0;
%}

%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; }
 ;

%%
struct symtab *
symlook(char *s)
{
 int i;

 for (i = 0; i < nsym; ++i) {
  if (!strcmp(symtab[i].name, s))
   return &symtab[i];
 }

 if (nsym < NSYMS) {
  symtab[nsym].name = strdup(s);
  ++nsym;
  return &symtab[nsym-1];
 }

 yyerror("Too many symbols");
 exit(1);
}

NAME标记的值是指向符号表的指针,%unionNAME%token声明适当地有所改变,而且给变量赋值和读取变量的动作现在将标记值作为指针来使用,读写符号表条目的value字段。函数symlook()被定义在用户子例程部分,它顺序地搜索符号表来寻找与作为参数传入的名字对应的条目,并返回其指针;如果没有找到,就把它保存在符号表中。顺序搜索对于这个简单示例是合适的,但对于大尺寸的符号表来说太慢了,需要使用散列表或者其他的快速搜索方法。

词法分析程序也需要稍加修改以适应符号表。识别变量名的规则匹配“[A-Za-z][A-Za-z0-9]*”,任何以字母开头的包含
字母和数字的字符串被认为是变量名。它的动作调用symlook()得到指向符号表条目的指针,并将它存储在标记的值yylval.symp中。

%{
#include "y.tab.h"
#include "calc4.h"
#include
%}

%%
([0-9]+|([0-9]*\.[0-9]+)([eE][-+]?[0-9]+)?) {
  yylval.dval = atof(yytext);
  return NUMBER;
 }

[ \t] ;

[A-Za-z][A-Za-z0-9]* {
  yylval.symp = symlook(yytext);
  return NAME;
 }

"$"   { return 0; }

\n    ¦
.     { return yytext[0]; }

%%

因为字符串动态分配,所以对于变量名的长度没有限制。下面是运行实例:

% calc4
foo = 12
foo /5
= 2.4
thisisanextremelylongvariablenamewhichnobodywouldwanttotype = 42
3 * thisisanextremelylongvariablenamewhichnobodywouldwanttotype
= 126
thisisanextremelylongvariablenamewhichnobodywouldwanttotype / foo
= 3.5
$

2007年12月4日星期二

lex/yacc系列:yacc进阶(二)

下面再扩展计算器的功能,使它能够处理名字为单个字母的变量。先只考虑26个小写字母为变量名,我们将这26个变量储存在数组vbltable中。为了使计算器更有用,我们还进一步扩展,使它能处理多条表达式,每行一条,并且使用浮点数作为数值。

拥有变量和实数数值的计算器语法分析程序calc3.y:

%{
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]; }
 ;

拥有变量和实数数值的计算器词法分析程序calc3.l:

%{
#include "y.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] ;

[a-z] { yylval.vblno = yytext[0] - 'a'; return NAME; }

"$"   { return 0; }

\n    ¦
.     { return yytext[0]; }

%%

在这个程序中,符号值有多种数据类型:表达式的值是double,变量引用和符号NAME的值是对应于vbltable的从0到25之间的整数。为了定义可能的符号类型,在定义部分加入了%union声明:

%union {
  double dval;
  int vblno;
}

声明中的内容将被逐字拷贝到输出文件y.tab.h中,作为C类型定义YYSTYPE的联合声明的内容:

#define NAME 257
#define NUMBER 258
#define UMINUS 259
typedef union {
  double dval;
  int vblno;
} YYSTYPE;
extern YYSTYPE yylval;

生成的头文件中还声明了变量yylval,并且定义了语法中使用的的符号标记的标记号。

在语法分析程序中的定义部分的符号定义行,由尖括号扩住的联合声明中的字段名指定了符号值的类型。

%token <vblno> NAME
%token <dval> NUMBER

%type <dval> expression

非终结符不需要声明,除非需要通过声明%type指定其类型。也可以在%left%right%nonassoc通过尖括号指定类型。在动作代码中,yacc对于符号值引用将自动添加合适的字段名,例如,如果第三个字符是NUMBER,对$3的引用就等于$3.dval。

在这个扩展的语法分析程序中还加入了一个新的起始符号statement_list,因此它能处理一系列而不仅仅是一条语句,每条语句以换行结尾。还为设置变量的规则增加了一个动作,并在最后添加了一条将NAME转换成expression的新规则,它获取变量的值。

词法分析程序也必须进行一些修改。yylval已经在y.tab.h中声明,所以不需要再次声明。词法分析程序并不能自动识别符号的类型,所以设置yylval时必须显式地添加字段引用。动作代码调用atof()读入数字,然后将值赋给yylval.dval。对于变量,在yylval.vblno中返回变量表中变量的下标。最后,使“\n”成为了一个普通标记,并使用“$”标志输入的结束。

下面是运行实例:

% calc3
2/3
= 0.666667
a = 2/7
a
= 0.285714
z = a+1
z
= 1.28571
a/z
= 0.222222
$

2007年12月3日星期一

HTML常用特殊字符

-ID代码描述
 160nbspnon-break space
&38ampampersand
¦166brvbarbroken bar
>62gtgreater-than sign
<60ltless-than sign
¢162centcent sign
£163poundpound sign
©169copycopyright sign
®174regregistered sign
8482tradetrade mark sign
°176degdegree sign
±177plusmnplus-minus sign
×215timesmultiplication sign
÷247dividedivision sign
¹185sup1superscript one
²178sup2superscript two
³179sup3superscript three
½189frac12valgar fraction one half
¼188frac14valgar fraction one quarter
¾190frac34valgar fraction three quarters
µ181micromicro sign
8593uarrupwards arrow
8592larrleftards arrow
8595darrdownwards arrow
8594
rarrrightwards arrow
8596
harrleft right arrow
8629
crarrdownwards arrow with corner leftwards
8657uArrupwards double arrow
8656lArrleftwards double arrow
8659dArrdownwards double arrow
8658rArrrightwards double arrow
8660
hArrleft right double arrow

lex/yacc系列:yacc进阶(一)

下面尝试将简单的计算器扩展,处理带乘法、除法、负号和括号的表达式:

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 { $$ = -$2; }
 ¦ '(' expression ')' { $$ = $2; }
 ¦ NUMBER { $$ = $1; }
 ;

除法动作检查被零除的情况,调用yyerror()(标准的yacc错误处理例程)报告错误。

上面的语法存在问题:它有歧义。例如,输入2+3*4,可以意味着(2+3)*4,也可以是2+(3*4),对于输入3-4-5-6,可以是3-(4-(5-6))),也可以是(3-4)-(5-6),或者其他很多种可能性。

如果你编译上面那样的语法,yacc将告知存在多个移进/归约冲突,表明它无法决定到底是先将标记压入堆栈,还是先归约规则。

例如,当分析“2+3*4”时,语法分析程序要经过这些步骤(这里将expression简写为E):

2     移进 NUMBER
E     归约 E → NUMBER
E+    移进 +
E+3   移进 NUMBER
E+E   归约 E → NUMBER

这时,语法分析程序查看“*”,它可以或者利用规则:

expression : expression '+' expression

将“2+3”归约为expression,或者移进“*”,期望稍后能归约:

expression : expression '*' expression

问题是我们没能告诉yacc操作符的优先级和组合规则。优先级控制表达式中哪个操作符要先执行。数学和编程惯例规定乘法和除法优先于加法和减法,所以a+b*c的意思是a+(b*c),d/e-f的意思是(d/e)-f。在所有的表达式语法中,操作符都被归组到由低到高不同的优先级中。级别的数目取决于语言。C语言因为有太多的优先级而出名,一共有15个级别。

组合规则(associativity)控制同一优先级上的操作符组合顺序。操作符可以从左至右组合,例如在C语言中,a-b-c意味着(a-b)-c;或者从右至左,例如a=b=c的意思是a=(b=c)。在某些情况下,操作符根本不能组合,例如在Fortran语言中,A.LE.B.LE.C是无效的。

有两种方式可以指定语法中的优先级和组合规则:隐式地和显示地。所谓隐式地指定,是指使用单独的非终结符号为每个优先级重新编写语法。假设使用常用的优先级和从左至右的组合规则,重新编写的表达式规则如下:

expression : expression '+' mulexp
 ¦ expression '-' mulexp
 ¦ mulexp
 ;

mulexp : mulexp '*' primary
 ¦ mulexp '/' primary
 ¦ primay
 ;

primary : '(' expression ')'
 ¦ '-' primary
 ¦ NUMBER
 ;

yacc还允许显式地指定优先级。可以在定义部分添加:

%left '+' '-'
%left '*' '/'
%nonassoc UMINUS

每一行定义了一个优先级:“+”和“-”从左至右组合,处于最低的优先级;“*”和“/”从左至右组合,处于较高的优先级;UMINUS是一个代表一元负号的伪标记,没有组合规则,处于最高的优先级。(从右至左组合规则使用%right定义。)

yacc指定规则右侧最右边标记的优先级作为该规则的优先级。当yacc遇到歧义语法引起的移进/归约冲突时,它就参考优先级表,并且如果冲突所涉及的所有规则都包含一个出现在优先级声明中的标记时,它使用优先级来解决冲突。

在前面的语法中,所有的冲突都发生在形如expression OPERATOR expression的规则中,所以为四个操作符设置优先级将解决所有的冲突。在这个语法分析程序中,使用优先级与利用额外规则的隐式方式相比,需要归约的规则比较少,所以程序略小而且速度稍快。

下面是完整的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; }
 ;

负号规则包括“%prec UMINUS”,这条规则包括的唯一操作符是“-”,这个操作符具有很低的优先级,但是我们希望一元负号具有比乘法更高的优先级,%prec告知yacc这条规则使用UMINUS的优先级。

lex/yacc系列:yacc简介

yacc(Yet Another Compiler Compiler),用类似BNF的格式从规则列表中生成语法分析程序的程序。

对于某些应用,我们完成简单的词法分析就足够了;而另一些应用需要识别特殊的标记序列并执行适当的动作。传统上,对这样的一套动作描述称为语法。lex将输入流分解成块(标记),然后yacc取得这些块并将它们按照一定的逻辑组合在一起。

语法

yacc的输入语法是BNF(Backus-Naur Form,巴克斯-诺尔范式)的简化版本。BNF是表示语法的一种方法,常用于指定程序设计语言的正式语法。下面是用于构建示例计算器的语法形式:

statement → NAME = expression
expression → NUMBER + NUMBER
 ¦  NUMBER - NUMBER

竖线“¦”表示或者,意味着多种可能性,例如,表达式可以是加法或者减法。箭头左侧的符号,即规则的左边,通常缩写为LHS(lef-hand side),右侧的符号是规则的右边,通常缩写为RHS(right-hand side)。出现在输入流中、被词法分析程序返回的符号是终结符或标记;而规则左侧出现的是非终结符。终结符与非终结符必须是不同的,标记出现在规则左侧是错误的。

通常用树状结构来表示所分析的句子。每个语法都包括起始符号,这些起始符号必须位于语法分析树的根部。在这个语法中,statement是起始符号。

递归规则

规则可以直接或间接地引用本身,这一特性使分析任意长的输入序列成为可能。扩展上面的语法来处理更长的算术表达式:

expression → NUMBER
 ¦  expression + NUMBER
 ¦  expression - NUMBER

yacc对分析递归规则非常有效,几乎可以在使用的每个语法中都看到递归规则。

移进/归约分析

yacc语法分析程序的工作原理是寻找可以匹配目前为止所看到的标记的规则。yacc处理语法分析程序时创建了一组状态,每个状态表示一个或多个被部分地分析的规则中的一个可能的位置。语法分析程序读取标记时,每次当它读到一个标记,而该标记不能完成任何规则,就把该标记压入内部堆栈,并且切换到对应于这个刚读入的标记的新的状态。这个动作称为移进(shift)。当它发现了组成某条规则右侧的全部符号时,它就把这些右侧符号弹出堆栈,而将相对应的左侧符号压入堆栈,并且切换到反映堆栈中新符号的新的状态。这个动作称为归约(reduction),因为它通常减少堆栈中项目的数量。(但也并不总是如此,因为可能有右侧为空的规则。)每当yacc归约一条规则,它就执行与之相关的用户代码。

下面的示例以上面介绍的分析过程分析输入“res = 8 + 12”。刚开始,将标记一次一个压入堆栈:

res
res =
res = 8
res = 8 +
res = 8 + 12

这里可以归约规则“expression → NUMBER + NUMBER”,所以8、+、12被弹出堆栈,代之以expression

res = expression

现在可以归约规则“NAME = expression”,所以res、=和expression被弹出,代之以statement。这时候,输入完成,堆栈也被归约到起始符号,按照语法,这个输入是有效的。

yacc不能分析什么

  • 歧义语法,同样的输入符合多个规则
  • 没有歧义,但需要向前看多于一个标记才能决定是否匹配一条规则的语法。例如:

    phrase → cart_animal AND CART
     ¦  work_animal AND PLOW
    cart_animal → HORSE GOAT
    work_animal → HORSE OX

    对于如“HORSE AND CART”的输入,yacc不能决定HORSE是cart_animal还是work_animal,直到它看到CART,但是yacc不能看那么远。如果把上面的第一条规则改为如下形式:

    phrase → cart_animal CART
     ¦  work_animal PLOW

    yacc就不会遇到麻烦,它会提前看下一个标记来决定,如果HORSE后跟PLOW,就是work_animal,如果后跟CART,则为cart_animal

yacc语法分析程序

yacc语法分析程序的结构与lex结构类似(lex结构模仿了yacc的结构)。第一部分(定义段)处理yacc生成的语法分析程序的控制信息,并且一般建立语法分析程序运行的执行环境。第二部分包含语法分析程序的规则。第三部分是被逐字拷贝到生成的C程序中的C代码。

下面以简单的计算器示例来了解语法分析程序的结构。

定义段

定义段包含语法中使用的标记的描述、分析程序的堆栈中使用的值的类型,以及其他的一些东西。它还可以包含由%(%)扩住的C代码,这些代码将被逐字拷贝到生成的C程序中。下面通过声明两个符号标记来开始示例语法分析程序。

%token NAME NUMBER

单个的引用字符可以不经声明直接作为标记使用,所以不需要声明“=”、“+”或“-”。

规则段

语法部分是由一列语法规则组成,其格式与前面使用的规则的格式大致相同。因为ASCII键盘没有“→”键,所以在规则的左侧和右侧使用冒号“:”,而且在每个规则的结尾有一个分号“;”:

%%
statement : NAME '=' expression
 ¦  expression
 ;

expression : NUMBER '+' NUMBER
 ¦  NUMBER '-' NUMBER
 ;

这里,分析程序增加了一条规则:statement可以是纯表达式,也可以是一个赋值。如果用户输入一个纯表达式,就打印它的结果。

第一条规则的左侧符号通常是起始符号,但可以在定义段使用%start声明覆盖它。

符号的值以及动作

yacc语法分析程序中的每个符号都有一个值,这个值给出了该符号的特定实例的额外信息:如果符号表示一个数字,它的值就是某个数字;如果符号表示一个引用字符串,它的值就可能是一个指向该字符串拷贝的指针;如果符号表示程序中的一个变量,它的值就是指向这个变量的符号表项的指针。有些标记没有有用的值,例如,表示闭括号的标记,因为所有的闭括号都是一样的。

在示例语法分析程序中,NUMBER的值是一个数值,expression的值是表达式的值,NAME的值是一个符号表指针。

在实际的语法分析程序中,不同符号的值可能使用不同的数据类型,例如,对于数字符号使用int和double,对于字符串使用char *,对于复杂符号使用结构指针。如果使用了多种数据类型,就必须在语法分析程序中列出所有的数据类型,yacc创建了一个包含所有数据类型的名为YYSTYPE的C联合(union)类型定义。

在示例程序中,唯一感兴趣的是输入的数字和表达式的数值。默认情况下,yacc将所有数值的类型定义为int,示例程序将使用这个默认定义。

每当语法分析程序归约一个规则时,它就执行与该规则相关的C代码,即规则的动作。规则动作被包含在大括号中,出现的位置在规则结尾之后,分号(;)或竖线(¦)之前。动作代码可以通过$1$2……引用规则右侧符号的值,也可以通过$$设置规则左侧的值。在示例程序中,符号expression的值是它所代表的表达式的值。下面添加一些代码来打印和计算表达式:

%%
statement : NAME '=' expression
 ¦  expression { printf("= %d\n", $1); }
 ;

expression : expression '+' NUMBER { $$ = $1 + $3; }
 ¦  expression '-' NUMBER { $$ = $1 - $3; }
 ¦  NUMBER { $$ = $1; }
 ;

构建表达式的规则计算相应的值,识别表达式的规则打印结果。在构建表达式的规则中,第一个和第二个数值分别对应于$1$3$2则是操作符的值,我们对它不感兴趣;该规则中的最后一个动作不是绝对必要的,因为当yacc每次归约后,在运行任何显式的动作代码之前,都会执行默认动作,将$1的值赋予$$

词法分析程序

为了测试示例的语法分析程序,我们还需要一个词法分析程序来提供标记。语法分析程序是较高级的例程,当它需要从输入流中获取一个标记,它就调用词法分析程序yylex()。词法分析程序一发现语法分析程序感兴趣的标记,它就返回语法分析程序,并将标记代码作为值返回。yacc将语法分析程序中的标记的名称定义在C预处理文件y.tab.h中,从而词法分析程序可以使用它们。

下面是为示例语法分析程序提供标记的简单词法分析程序:

%{
#include "y.tab.h"
extern int yylval;
%}

%%
[0-9]+ { yylval = atoi(yytext); return NUMBER; }
[ \t]  ; /* 忽略空白 */
\n     { return 0; }
.      { return yytext[0]; }
%%

上面的词法分析程序将数字串转换为数字,忽略空白,当遇到换行时返回输入结束标记(数字0),通知语法分析程序没有更多的东西需要读取。最后一条规则是非常常用的截流器(catch-all),即将所有其他未处理的字符作为单个字符返回给语法分析程序。字符标记通常是标点符号,如大括号、分号以及单字操作符。如果语法分析程序接收到不认识的标记,它就产生语法错误,因此这条规则可以让你很容易地处理所有的单字操作符,而让yacc的错误检查捕获和“抱怨”无效的输入。

当词法分析程序将一个标记返回给语法分析程序时,如果该标记有相关的值,词法分析程序在返回前必须将值储存在yylval中。在上面的示例中,yylval被显式声明。在更复杂的语法分析程序中,yacc在y.tab.h中将yylval声明为一个联合(union)。

编译运行示例语法分析程序

将上面的语法分析程序代码保存在文件calc1.y中,词法分析程序代码在calc1.l中。yyac将产生y.tab.h和C语言语法分析程序y.tab.c。lex创建lex.yy.c,C语言词法分析程序。你需要用lex和yacc库将它们编译在一起。这些库中包含所有支持例程的可用的默认版本,包括一个main(),它调用语法分析程序yyparse(),然后退出。

% yacc -d calc1.y
% lex calc1.l
% cc -o calc1 y.tab.c lex.yy.c -ly -ll
% calc1
99+12
= 111
% calc1
2 + 3-14+33
= 24
% calc1
100 + -50
syntax error