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
网友评论