分类目录归档:Others

YACC 基本用法

YACC 文件格式

yacc 文件分为三部分:
… definitions …(%{}%)
%%
… rules …
%%
… subroutines …

定义部分

第一部分包括标志(token)定义和 C 代码(用“%{”和“%}”括起来)。
如在定义部分定义标志:
%token INTEGER
当运行 yacc 后,会产生头文件,里面包含该标志的预定义,如:
#ifndef YYSTYPE 
#define YYSTYPE int 
#endif 
#define INTEGER 258 
extern YYSTYPE yylval;
lex 使用该头文件中的标志定义。Yacc 调用 lex 的 yylex() 来获得标志(token),与标志对应的值由lex 放在变量 yylval 中。yylval 的类型由 YYSTYPE 决定,YYSTYPE缺省类型是int。如:
[0-9]+ { 
yylval = atoi(yytext); 
return INTEGER; 
}
标志0-255被保留作为字符值,一般产生的token标志从258开始。如:
[-+] return *yytext; /* return operator */
返回加号或减号。注意要把减号放在前面,避免被认作是范围符号。
对于操作符,可以定义 %left 和 %right:%left表示左相关(left-associative),%right 表示右相关(right-associative)。可以定义多组 %lef t或 %right,在后面定义的组有更高的优先级。如:
%left ‘+’ ‘-‘
%left ‘*’ ‘/’
上面定义的乘法和除法比加法和减法有更高的优先级。
改变 YYSTYPE 的类型。如这样定义 TTSTYPE:
%union
{ 
     int iValue; /* integer value */ 
     char sIndex; /* symbol table index */ 
     nodeType *nPtr; /* node pointer */ 
};

则生成的头文件中的内容是:

typedef union
{ 
     int iValue;      /* integer value */ 
     char sIndex;    /* symbol table index */ 
     nodeType *nPtr; /* node pointer */ 
} YYSTYPE; 
extern YYSTYPE yylval;

可以把标志(token)绑定到 YYSTYPE 的某个域。如:

%token <iValue> INTEGER
%type <nPtr> expr
把 expr 绑定到 nPtr,把INTEGER绑定到 iValue。yacc 处理时会做转换。如:
expr: INTEGER { $$ = con($1); }
转换结果为:
yylval.nPtr = con(yyvsp[0].iValue);
其中 yyvsp[0] 是值栈(value stack)当前的头部。
定义一元减号符有更高的优先级的方法:
%left GE LE EQ NE ‘>’ ‘<‘
%left ‘+’ ‘-‘
%left ‘*’
%nonassoc UMINUS
%nonassoc 的含义是没有结合性。它一般与 %prec 结合使用表示该操作有同样的优先级。如:
expr: ‘-‘ expr %prec UMINUS { $$ = node(UMINUS, 1, $2); }
表示该操作的优先级与 UMINUS 相同,在上面的定义中,UMINUS 的优先级高于其他操作符,所以该操作的优先级也高于其他操作符计算。

规则部分

规则部分很象 BNF 语法。
规则中目标或非终端符放在左边,后跟一个冒号(:),然后是产生式的右边,之后是对应的动作(用{}包含)。如:
%token INTEGER
%%
program: program expr '\n' { printf("%d\n", $2); } 

;
expr: INTEGER { $$ = $1; }  
     | expr '+' expr { $$ = $1 + $3; } 
     | expr '-' expr { $$ = $1 - $3; } 
;
%%
int yyerror(char *s) 
{ 
     fprintf(stderr, "%s\n", s); 
     return 0; 
}

其中,$1 表示右边的第一个标记的值,$2 表示右边的第二个标记的值,依次类推。$$ 表示规约后的值。

第三部分

该部分是函数部分。当 yacc 解析出错时,会调用函数 yyerror(),用户可自定义函数的实现。

main 函数是调用 yacc 解析入口函数 yyparse()。如:

int main(void) 
{ 
     yyparse(); 
     return 0; 
}

递归的处理

递归处理有左递归和右递归。
左递归形式:
list: item
| list ‘,’ item;
右递归形式:
list: item
| item ‘,’ list
使用右递归时,所有的项都压入堆栈里,才开始规约;而使用左递归的话,同一时刻不会有超过三个项在堆栈里。
If-Else的冲突
当有两个 IF 一个 ELSE 时,该 ELSE 和哪个 IF 匹配是一个问题。有两种匹配方法:与第一个匹配和与第二匹配。现代程序语言都让 ELSE 与最近的 IF 匹配,这也是 yacc 的缺省行为。
虽然 yacc 行为正确,但为避免警告,可以给 IF-ELSE 语句比 IF 语句更高的优先级:
%nonassoc IFX
%nonassoc ELSE
stmt: IF expr stmt %prec IFX
| IF expr stmt ELSE stmt
出错处理
当 yacc 解析出错时,缺省的行为是调用函数 yyerror(),然后从 yylex 返回一个值。一个更友好的方法是忽略一段错误输入流,继续开始扫描。这里要涉及到 YACC 中错误保留字 error 的应用。
Yacc源程序的风格
建议按照如下风格来写:
(1)终端符名全部用大写字母,非终端符全部用小写字母;
(2)把语法规则和语义动作放在不同的行;
(3)把左部相同的规则写在一起,左部只写一次,而后面所有规则都写在竖线“|”之后;
(4)把分号“;”放在规则最后,独占一行;
(5)用制表符来对齐规则和动作。
语法分析中的错误处理
当进行语法分析时发现输入串有语法错误,最好能在报告出错信息以后继续进行语法分析,以便发现更多的错误。
Yacc 处理错误的方法是:当发现语法错误时,yacc 丢掉那些导致错误的符号适当调整状态栈。然后从出错处的后一个符号处或跳过若干符号直到遇到用户指定的某个符号时开始继续分析。Yacc 内部有一个保留的终结符 error,把它写在某个产生式的右部,则Yacc就认为这个地方可能发生错误,当语法分析的确在这里发生错误时,Yacc 就用上面介绍的方法处理,如果没有用到 error的产生式,则 Yacc打印出 “Syntax error”,就终止语法分析。
下面看两个使用 error 的简单例子:
1.下面的产生式
stat: error
;
使 yacc 在分析 stat 推导出的句型时,遇到语法错误时跳过出错的部分,继续分析(也会打印语法错误信息)
2.下面的产生式
stat: error ‘;’
;
使 yacc 碰到语法错时,跳过输入串直到碰到下一个分号才继续开始语法分析。
嵌入式动作
对于语法分析程序中的每一个语法规则,都有相应的 C/C++ 语句来做一些额外的处理,这个额外的处理就是语法动作。不过语法动作和词法动作的不同之处在于,语法动作允许嵌入式的语法动作,而词法动作不行。
尽管 yacc 的语法分析技术只允许动作在规则的末端,但 yacc 可以自动模拟嵌入在规则内部的动作。如果在规则内部写入一个动作,yacc 就会创造一个右侧为空并且左边是自动生成的名字规则,使得嵌入的动作进高规则的动作里去,用自动成成的名字代替最初的规则内的动作。
例如: 下面的句子是等价的
thing : A {printf(“I am A”) ;} B
thing : A fakename B;
fakename : {printf(“I am A”);}
这种方式将A值作为 $1,  规则末端的动作可将嵌入式动作的值作为 $2 ,B 的值为 $3.
Example:
//L文件:
%{
#include "FIRST_TA.H"
#include <stdio.h>
#include <stdlib.h>
%}
%%
a    {return A_STATE;}
b    {return B_STATE;}
c     {return C_STATE;}
not   {return NOT;}
%%

//Y文件:
%{
#include <stdio.h>
#include <stdlib.h>
%}
%token    A_STATE B_STATE C_STATE NOT
%%

program :    
    A_STATE B_STATE {
        int c, d;
        c = 20;
        d = 25;
    }
      c_state_not  {
            int e,f;
            e = 30;
            f = 35;
        }
    |
    A_STATE B_STATE  {
            int a, b;
            a = 10;
            b = 15;
    }
    c_state_not : C_STATE NOT{}
%%

输入文件的字符:a, b, c, f, c, not

NumPy 部分操作的理解

  • 矩阵操作中 axis = -1,相当与对矩阵最后一维进行操作
  • NumPy 的 ndarray 进行算术运算符操作是 element-wise 的,即是逐元素进行操作
  • np.mean 等操作中的 keepdim 选项,将平均掉的那一维保留,但是长度只为 1

Reference:

  • http://www.scipy-lectures.org/intro/numpy/operations.html