yet another compiler compiler（yacc）

yet another compiler compiler（yacc）简介：使用说明：yacc语法结构：BNF文法介绍：什么是文法介绍？为什么要学习BNF文法介绍？文法介绍例子：句型和句子：两种主要的分析方法。语法树相关知识点简介：什么是语法树？语法树例子①：yacc Demo实例：定义段：规则段：用户子程序段

简介：

在之前介绍过Lex，他检测代码的规范语法，将我们输入的字符串解析成对应的token

解析完毕以后就该yacc上场了，Lex主要是词法分析，yacc是语法分析

yacc可将语法规则文件转换成C源码文件，编译此源文件可得到一个用于语法分析的程序。

由于语法分析要使用词法分析的结果，所以yacc经常会搭配lex一起工作。

如果说词法分析的作用是从连续的字符中识别出标识符、关键字、数字、运算符并存储为符号（token）流，语法分析的作用就是从词法分析识别出的符号流中识别出符合 C 语言语法的语句。因为计算机无法像人那样同时看多个标识符、关键字、数字、运算符，无法像人那样一眼看出这是一个函数声明，那是一个 if 语句，只能非常笨拙地一个符号一个符号去识别。与词法分析器有些类似，语法分析器也是依据用计算机表示的语法，一个符号一个符号地识别出符合 C 语言语法的语句。语法的计算机表示就是产生式。在语法分析器中把通过产生式产生的 C语言语法映射成一套模板，并把这套模板融汇在语法分析器的程序中。语法分析器的作用就是将词法分析器别出的符号（token）一个一个地与这套模板进行匹配，匹配上这套模板中的某个语法，就可以识别出一句完整的语句，并确定这条语句的语法。 转载自《编译系统透视：图解编译原理》

使用说明：

语法文件详细的规则可以参考我之前的帖子

https://www.jianshu.com/p/7a9476c65672

yacc也需要对应的规则文件配合yacc，可以生产y.tab.c和y.tab.h

（ 语法分析就要从这个符号串中识别出符合 C 语言语法的语句。识别的方法是：以 C 语言语法

为模板，将符号串按序逐个匹配，如果能匹配成功，就可以确定匹配成功的符号串是一条符合 C 语言语法的句

子，同时也就确定了这条语句的语法属性（如函数声明语句）及句子的各个语法成分（如返回值类型、函数名、

参数列表）。如果与所有语法类型的模板都无法匹配，说明这个符号串有语法错误。）

流程如下图：

image.png

yacc语法结构：

yacc语法包括三部分：定义段、规则段和用户子例程段

...定义段...

%%

...规则段...

%%

...用户子例程段...

各部分由以两个百分号开头的行分开，尽管某一个部分可以为空，但是前两部分是必须的，第三部分和前面的百分号可以省略。

BNF文法介绍：

语法分析的目的是判断语句是否符合语言所规定的语法要求。所以，语法分析的首要任务是制订相应的语法规则。

语法规则是通过文法来描述的。

什么是文法介绍？

文法有很多描述方法，最常用的一种方法是BNF范式（Backus-Naur Form）。

下面是一个基于中文语法、利用BNF范式来描述的文法示例。

image.png

为什么要学习BNF文法介绍？

当yacc拿到 各种token（具体参考上一章）的时候

需要将token拼成句子，比如 int a = b

很简单的语法，如果直接解析成 = b，这种就是错误的语法，所以在yacc里面也需要通过 “主谓宾” 的方式去

拼够，因为yacc的功能是将token拼成一句代码的 “过程”

yacc可以将各种token进行区分，分成对应的 “主谓宾”。

比如他遇到了 你 我 他 他就会认为这个是主语。

文法介绍例子：

我们还是以邓老师的例子

比如 一句话很简单的 他吃饭

1，先去寻找主语，发现 他 满足，程序就会变成 主语，吃饭

2，当读取 吃或者喝的时候 认为是谓语，变成 “主语，谓语，饭”

3，当读取到饭的时候，变成 “主语，谓语，宾语”

4，宾语可能是很多种情况，我们成为 子句子 ， 子句子 比如不一定吃的是饭 ，可以吃的是菜，我们认为他是自句子，在程序中 ，

比如 int a 我们也可以变成int b。b变量 就可以算成子句子，所以饭属于子句子宾语。

“他吃饭”按照文法规则进行多次迭代，替换非终结符，最终得到句子，所以它符合示例的语法规范，所以认定其语法是正确的。

yacc其实也是如上类似逻辑。

比如 一句 “你水” 没有谓语这种就认为是错误的。

句型和句子：

语法分析的过程中会产生一些包含非终结符的字符串，比如 “主语吃饭” “子句子饭”等。

这些包含非终结符的字符串叫句型（sentential form）

而不包含非终结符的字符串叫句子（sentence）

任何句型都可以由文法开始符经过零次或多次推导得到。而从任何句型出发，经过不断推导，都可以得到一个有效的句子。由上述示例可知，语法分析的大体过程就是不断对输入语句按照文法进行分析，替换其中的非终结符，直到处理完毕。

两种主要的分析方法。

·一种是自顶向下的推导（英文为derivation）法。

以“他吃饭”为例，推导法首先从文法开始符句子的产生式开始：句子被替换成子句子和宾语，子句子被替换成主语和谓语。接着，主语被替换成“他”，谓语被替换成“吃”，宾语被替换成“饭”。最终得到的结果和输入的语句一样，所以输入语句的语法正确。推导法适合手工编码实现。

另一种是自底向上的归约（英文为derivation）法。就比如之前介绍的文法介绍例子。

yacc就是利用向上的归约方式进行生成语法分析器。

语法树相关知识点简介：

什么是语法树？

在语法分析过程中，人们发现使用树形结构来描述整个推导过程会比较直观和方便，该树也被称为语法树（syntax tree，或语法分析树parse tree）。

语法树是句子结构的图形表示，它代表了句子的推导结果，有利于理解句子语法结构的层次。简单说，语法树就是按照某一规则进行推导时所形成的树。

yacc生成的结果便是通过语法树抽象出来的结果。

语法树例子①：

如果我们需要让计算机帮忙算一下 「1加2再乘以3」 的结果，该怎么表达呢？ 现在我们大多数的现代编程语言，都是使用「中缀表达式」的方式来编写运算，比如JavaScript：

(1 + 2) * 3

而FORTH语言则使用「后缀表达式」，这基本上与日语中的语序是一致的：

1 2 + 3 *

LISP语言使用的「前缀表达式」：

( * (+ 1 2) 3)

我们再看一下这三种表达式的语法树：

image.png

可以看出，对于这三种简单的语言，它们只是在这个语法树上按不同的规则遍历而已。三者的代码看起来差别很大，但实际上所用的树结构是相同的。

yacc Demo实例：

转自（http://www.quut.com/c/ANSI-C-grammar-y-1998.html）

参考自《深入理解Android:Java虚拟机Art》

一个demo主要分为

定义段，规则段，用户子程序段

定义段：

//先定义好需要处理的token信息
%token IDENTIFIER CONSTANT STRING_LITERAL SIZEOF
%token PTR_OP INC_OP DEC_OP LEFT_OP RIGHT_OP LE_OP GE_OP EQ_OP NE_OP
%token AND_OP OR_OP MUL_ASSIGN DIV_ASSIGN MOD_ASSIGN ADD_ASSIGN
%token SUB_ASSIGN LEFT_ASSIGN RIGHT_ASSIGN AND_ASSIGN
%token XOR_ASSIGN OR_ASSIGN TYPE_NAME

%token TYPEDEF EXTERN STATIC AUTO REGISTER INLINE RESTRICT
%token CHAR SHORT INT LONG SIGNED UNSIGNED FLOAT DOUBLE CONST VOLATILE VOID
%token BOOL COMPLEX IMAGINARY
%token STRUCT UNION ENUM ELLIPSIS

%token CASE DEFAULT IF ELSE SWITCH WHILE DO FOR GOTO CONTINUE BREAK RETURN



//文件开始符,每个语法规则文件一定需要有一个文件开始符
%start translation_unit
%%
//和 Lex规则文件一样也需要有一个 yyerror函数,当解析出错的时候调用
void yyerror(char const *s)
{
 fflush(stdout);
 printf("\n%*s\n%*s\n", column, "^", column, s);
}

规则段：

yacc规则段其实就是文法，文法中产生式常见的书写格式为

A:BC|D

规则中目标或非终端符放在左边，后跟一个冒号（：），然后是产生式的右边，之后是对应的动作（用{}包含）

拿个很简单的 printf 举例子如下

 { printf("%d\n", $2); }  ;
expr: INTEGER { $ = $1; }  
 | expr '+' expr { $ = $1 + $3; } 
 | expr '-' expr { $ = $1 - $3; } 
;

1表示右边第一个标记的数值，2表示右边的第二个标记的值，依次类推。$$表示归约后的值。

用户子程序段

yacc 将用户子例程段的内容完全拷贝到C文件中，通常这部分包括从动作调用的例程。 该部分是函数部分。当yacc解析出错时，会调用函数yyerror()，用户可自定义函数的实现。 main函数是调用yacc解析入口函数yyparse()。如：

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

参考：

《深入理解Android:Java虚拟机Art》

《编译系统透视：图解编译原理》

https://www.jianshu.com/p/1fe5a61fd9dc

https://www.cnblogs.com/zhuchengyang/p/7692626.html

安卓逆向百级教程+全网最新js逆向视频+永久小蜜圈+永久售后群=1299

视频下载网盘
�http://nas.alienhe.cn:5008/home.html�
下载视频账号密码：
账号guest 密码world

Js试看:
http://oss.alienhe.cn/JS%E9%80%86%E5%90%91%E5%85%A5%E9%97%A8-%E5%B8%A6%E6%B0%B4%E5%8D%B0.mp4