Compiler Theory(编译原理)、词法/语法/AST/中间代码优化在Webshell检测上的应用

catalog

0. 引论
1. 构建一个编译器的相关科学
3. 程序设计语言基础
4. 一个简单的语法制导翻译器
5. 简单表达式的翻译器(源代码示例)
6. 词法分析
7. 生成中间代码
8. 词法分析器的实现
9. 词法分析器生成工具Lex
10. PHP Lex(Lexical Analyzer)
11. 语法分析
12. 构造可配置词法语法分析器生成器
13. 基于PHP Lexer重写一份轻量级词法分析器
14. 在Opcode层面进行语法还原WEBSHELL检测 

 

0. 引论

在所有计算机上运行的所有软件都是用某种程序设计语言编写的，但是在一个程序可以运行之前，它首先需要被翻译成一种能够被计算机执行的形式，完成这项翻译工作的软件系统称为编译器(compiler)

0x1: 语言处理器

1. 编译器
简单地说，一个编译器就是一个程序，它可以阅读以某一种语言(源语言)编写的程序，并把该程序翻译成一个等价、用另一种语言(目标语言)编写的程序，编译器的重要任务之一是报告它在翻译过程中发现的原程序中的错误
2. 解释器
解释器(interpreter)是另一种常见的语言处理器，它并不通过翻译的方式生成目标程序，解释器直接利用用户提供的输入执行源程序中指定的操作
//在把用于输入映射成为输出的过程中，由一个编译器产生的机器语言目标程序通常比一个解释器要快很多，然而，解释器的错误诊断效果通常比编译器更好，因为它逐个语句地执行源程序

java语言处理器结合了编译和解释过程，一个java源程序首先被编译成一个称为字节码(bytecode)的中间表示形式，然后由一个虚拟机对得到的字节码加以解释执行，这样设计的好处之一是在一台机器上编译得到的字节码可以在另一台机器上解释执行，通过网络就可以完成机器之间的迁移
为了更快地完成输入到输出的处理，有些被称为即时(just in time)编译器的java编译器在运行中间程序处理输入的前一刻先把字节码翻译成为机器语言，然后再执行程序

0x2: 一个编译器的结构

编译器能够把源程序映射为在语义上等价的目标程序，这个映射过程由两个部分组成: 分析部分、综合部分

1. 分析部分(编译器的前端 front end)
    1) 分析(analysis)部分把源程序分解成多个组成要素，并在这些要素之上加上语法结构
    2) 然后，它使用这个结构来创建该源程序的一个中间表示，如果分析部分检查出源程序没有按照正确的语法构成，或者语义上不一致，它就必须提供有用的信息，使得用户可以按此建议进行改正
    3) 分析部分还会收集有关源程序的信息，并把信息存放在一个称为符号表(symbol table)的数据结构中(调用其他obj中的函数就需要用到符号表)，符号表和中间表示形式一起传送给综合部分

2. 综合部分(编译器的后端 back end)
    1) 综合(synthesis)部分根据中间表示和符号表中的信息来构造用户期待的目标程序

如果我们更加详细地研究编译过程，会发现它顺序执行了一组步骤(phase)，每个步骤把源程序的一种表现形式转换为另一种表现形式，在实践中，多个步骤可能被组合在一起，而这些组合在一起的步骤之间的中间表示不需要被明确地构造出来，存放整个源程序的信息的符号表可由编译器的各个步骤使用
有些编译器在前端和后端之间有一个与机器无关的优化步骤，这个优化步骤的目的是在中间表示之上进行转换，以便后端程序能够生成更好的目标程序

1. 词法分析

编译器的第一个步骤称为词法分析(lexical analysis)或扫描(scanning)，词法分析器读入组成源程序的字符流，并且将它们组织成为有意义的词素(lexeme)的序列，对于每个词素，词法分析器产生如下形式的词法单元(token)作为输出

<token-name、attribute-value>
1. token-name: 由语法分析步骤使用的抽象符号
2. attribute-value: 指向符号表中关于这个词法单元的条目
//符号表条目的信息会被语义分析和代码生成步骤使用

这个词法单元被传送给下一个步骤，即语法分析，分割词素的空格会被词法分析器忽略掉

可以看到，在静态分析、编译原理应用领域，代码优化器这一步可以推广到WEBSHELL恶意代码检测技术上，利用这一步得到的"归一化"代码，可以进行纯词法层面的"恶意特征字符串模式匹配"

2. 语法分析

编译器的第2个步骤称为语法分析(syntax analysis)或解析(parsing)。语法分析器使用由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示，该中间表示给出了词法分析产生的词法单元流的语法结构，一个常用的表示方法是语法树(syntax tree)，树中的每个内部结点表示一个运算，而该结点的子节点表示该预算的分量(左右参数)
编译器的后续步骤使用这个语法结构来帮助分析源程序，并生成目标程序

3. 语义分析

语义分析器(semantic analyzer)使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致，它同时也收集类型信息，并把这些信息存放在语法树或符号表中，以便在随后的中间代码生成过程中使用
语义分析的一个重要部分是类型检查(type checking)，编译器检查每个运算符是否具有匹配的运算分量
程序设计语言可能允许某些类型转换，即自动类型转换(coercion)

4. 中间代码生成

在把一个源程序翻译成目标代码的过程中，一个编译器可能构造出一个或多个中间表示，这些中间表示可以有多种形式(语法树就是一种中间表示，它们通常在语法分析和语义分析中使用)
在源程序的语法分析和语义分析完成之后，编译器会生成一个明确的低级或类机器语言的中间表示，我们可以把这个表示看作是某种抽象机器的程序，该中间表示应该具有两个重要的性质

1. 易于生成
2. 能够轻松地翻译为目标机器上的语言

5. 代码优化

机器无关的代码优化步骤试图改进中间代码，以便生成更好的目标代码，不同的编译器所做的代码优化工作量相差很大，那些优化工作做得最多的编译器，即所谓的"优化编译器"，会在优化阶段花相当多的时间

6. 代码生成

代码生成器以源程序的中间表示形式作为输入，并把它映射到目标语言，如果目标语言是机器代码，那么就必须为程序使用的每个变量选择寄存器或内存地址，然后中间指令被翻译成能够完成相同任务的机器指令序列。代码生成的一个至关重要的方面是合理分配寄存器以存放变量的值
需要明白的是，运行时刻的存储组织方式依赖于被编译的语言，编译器在中间代码生成或代码生成阶段做出有关存储的分配的决定

7. 符号表管理

编译器的重要功能之一是记录源程序中使用的变量的名字，并收集和每个名字的各种属性有关的信息，这些属性可以提供一个名字的存储分配、类型、作用域等信息，对于过程，这些信息还包括

1. 名字的存储分配
2. 类型
3. 作用域(在程序的哪些地方可以使用这个名字的值)
4. 参数数量
5. 参数类型
6. 每个参数的传递方式(值传递或引用传递)
7. 返回类型

符号表数据结构为每个变量名创建了一个记录条目，记录的各个字段就是名字的各个属性，这个数据结构允许编译器迅速查找到每个名字的记录，并向记录中快速存放和获取记录中的数据

8. 编译器构造工具

一个常用的编译器构造工具包括

1. 扫描器的生成器: 可以根据一个语言的语法单元的正则表达式描述生成词法分析器
2. 语法分析器的生成器: 可以根据一个程序设计语言的语法描述自动生成语法分析器
3. 语法制导的翻译引擎: 可以生成一组用于遍历分析树并生成中间代码的例程
4. 代码生成器的生成器: 依据一组关于如何把中间语言的每个运算翻译成目标机器上的机器语言的规则，生成一个代码生成器
5. 数据流分析引擎: 可以帮助收集数据流信息，即程序中的值如何从程序的一个部分传递到另一部分，数据流分析是代码优化的一个重要部分
6. 编译器构造工具集: 提供了可用于构造编译器的不同阶段的例程的完整集合

 

1. 构建一个编译器的相关科学

编译器的设计中有很多通过数学方法抽象出问题本质从而解决现实世界复杂问题的例子，这些例子可以被用来说明如何使用抽象方法来解决问题: 接受一个问题，写出抓住了问题的关键特性的数学抽象表示，并用数学技术来解决它，问题的表达必须根植于对计算机程序特性的深入理解，而解决方法必须使用经验来验证和精化

0x1: 编译器设计和实现中的建模

对编译器的研究主要是有关如何设计正确的数学模型和选择正确算法的研究，设计和选择时，还需要考虑到对通用性及功能的要求与简单性及有效性之间的平衡

1. 最基本的数学模型是有穷状态自动机和正则表达式，这些模型可以用于描述程序的词法单位(关键字、标识符等)以及描述被编译器用来识别这些单位的算法
2. 上下文无关文法，它用于描述程序设计语言的语法结构，例如嵌套的括号和控制结构
3. 树形结构是表示程序结构以及程序到目标代码的翻译方法的重要模型

0x2: 代码优化的科学

现在，编译器所作的代码优化变得更加重要，而且更加复杂，因为处理器体系结构变得更加复杂，也有了更多改进代码执行方式的机会，之所以变得更加重要，是因为巨型并发计算机要求实质性的优化，否则它们的性能将会呈数量级下降，随着多核计算机的发展，所有的编译器将面临充分利用多核计算机的优势的问题
即使有可能通过随意的方法来建造一个健壮的编译器，实现起来也是非常困难，因为，研究人员已经围绕代码优化建立了一套广泛且有用的理论，应用严格的数学基础，使得我们可以证明一个优化是正确的，并且它对所有可能的输入都产生预期的效果
需要明白的是，如果想使得编译器产生经过良好优化的代码，图、矩阵、线性规划之类的模型是必不可少的，编译器优化必须满足下面的设计目标

1. 优化必须是正确的，也就是说，不能改变被编译程序的原始含义
2. 优化必须能够改善很多程序的性能
3. 优化所需的时间必须保持在合理的范围内
4. 所需要的工程方面的工作必须是可管理的

0x3: 针对计算机体系结构的优化

计算机体系结构的快速发展也对新编译技术提出了越来越多的需求，几乎所有的高性能系统都利用了两种技术: 并行(parallelism)、内存层次结构(memory hierarchy)

1. 并行性
并行可以出现在多个层次上
    1) 指令层次上: 多个运算可以被同时执行，所有的现代微处理器都采用了指令集的并行性，但这种并行性可以对程序员隐藏起来，硬件动态地检测指令流之间的依赖关系，并且在可能的时候并行地发出指令，不管硬件是否对指令进行重新排序，编译器都可以重新安排指令，以使得指令级并行更加有效
    指令级的并行也显示地出现在指令集汇总，VLIW(Very Long Instruction Word 非常长指令字)机器拥有可并行执行多个运算的指令，Intel IA64是这种体系结构的一个有名的例子
    所有的高性能通用微处理器还包含了可以同时对一个向量中的所有数据进行运算的指令，人们已经开发出相应的编译器技术，从顺序程序除法为这样的机器自动生成代码

    2) 处理器层次上: 同一个应用的多个不同线程在不同的处理器上运行
    程序员可以为多处理器编写多线程的代码，也可以通过编译器从传统的顺序程序自动生成并行代码，编译器对程序员隐藏了一些细节

2. 内存层次结构
一个内存层次结构由几层具有不同速度和大小的存储器组成，离处理器距离越近，速度越快，但存储空间越小，高效使用寄存器可能是优化一个程序时要处理的最重要的问题，同时高速缓存和物理内存是对指令集集合隐藏的，并由硬件管理

0x4: 程序翻译

1. 二进制翻译

编译器技术可以用于把一个机器的二进制代码翻译成另一个机器的二进制代码，使得可以在一个机器上运行原本为另一个指令集编译的程序

2. 硬件合成

不仅仅大部分软件是用高级语言描述的，连大部分硬件设计也是使用高级硬件描述语言描述的，例如Verilog、VHDL(Very High-Speed Intefrated Circuit Hardware Description Language 超高速集成电路硬件描述语言)
硬件设计通常是在寄存器传输层(Register Transfer Level RTL)上描述的，在这个层面中，变脸代表寄存器，而表达式代表组合逻辑，硬件合成工具把RTL描述自动翻译为门电路，而门电路再被翻译成为晶体管，最后生成一个物理布局

3. 数据查询解释器

除了描述软件和硬件，语言在很多应用中都是有用的，比例，查询语言(例如SQL语言 Structured Query Language 结构化查询语言)被用来搜索数据库，数据库查询由包含了关系和布尔运算符的断言组成，它们可以被解释，也可以编译为代码，以便在一个数据库中搜索满足这个断言的记录

 

3. 程序设计语言基础

0x1: 静态和动态的区别

在为一个语言设计一个编译器时，我们所面对的最重要的问题之一是编译器能够对一个程序做出哪些判定

1. 如果一个语言使用的策略支持编译器静态决定某个问题，那么我们说这个语言使用了一个静态(static)策略，或者说这个问题可以在编译时刻(compile time)决定
2. 另一方面，一个只允许在运行程序的时候做出决定的策略被称为动态策略(dynamic policy)，或者被认为需要在运行时刻(run time)做出决定

0x2: 环境与状态

我们在讨论程序设计语言时必须了解的另一个重要区别是在程序运行时发生的改变是否会影响数据元素的值，还是仅仅影响了对那个数据的名字的解释
名字和内存(存储)位置的关联，及之后和值的关联可以用两个映射来描述，这两个映射随着程序的运行而改变

1. 环境(environment)是一个从名字到存储位置的映射，因为变量就是指内存位置(即C语言中的术语"左值")，我们还可以换一种方法，把环境定义为从名字到变量的映射
//环境的改变需要遵守语言的作用域规则
2. 状态(state)是一个从内存位置到它们的值的映射，以C语言的术语来说，即状态把左值映射为它们的相应的右值

0x3: 静态作用域和块结构

包括C语言和它的同类语言在内的大多数语言使用静态作用域，C语言的作用域规则是基于程序结构的，一个声明的作用域由该声明在程序中出现的位置隐含地决定
0x4: 显式访问控制

类和结构为它们的成员引入了新的作用域，通过public、private、protected这样的关键字的使用，像C++和Java这样的面向对象语言提供了对超类中的成员名字的显式访问控制，这些关键字通过限制访问来支持封装(encapsulation)，因此，私有(private)名字被有意地限定了作用域，这个作用域仅仅包含了该类和"友类"(C++的术语)相关的方法声明和定义，被保护的(protected)名字可以由子类访问，而公共的(public)名字可以从类外访问
在C++中，一个类的定义可能和它的部分或全部方法的定义分离，因此对于一个和类C相关联的名字，可能存在一个在它作用域之外的代码区域，然后又跟着一个在它作用域内的代码区域(一个方法定义)，实际上，在这个作用域之内和之外的代码区域可能相互交替，直到所有的方法都被定义完毕

0x5: 动态作用域

从技术上讲，如果一个作用域策略依赖于一个或多个只有在程序执行时刻才能知道的因素，它就是动态的，然而，术语动态作用域通常指的是下面的策略

对一个名字x的使用指向的是最近被调用但还没有终止且声明了x的过程中的这个声明，这种类型的动态作用域仅仅在一些特殊情况下才会出现，例如
1. C预处理起中的宏扩展
2. 面向对象编程中的方法解析

动态作用域解析对多态过程是必不可少的，所谓多态过程是指对于同一个名字根据参数类型具有两个或多个定义的过程，在这种情况下，编译器可以把每个过程调用替换为相应的过程代码的引用

0x6: 参数传递机制

所有的程序设计语言都有关于过程的概念，但是在这些过程如何获取它们的参数方面，不同的语言之间有所不同

1. 值调用

在值调用(call-by-value)中，会对实参求值(如果它是表达式)或拷贝(如果它是变量)，这些值被放在属于被调用过程的相应形式参数的内存位置上(即入栈)，值调用的效果是，被调用过程所做的所有有关形式参数的计算都局限于这个过程，对应的实参本身不会被改变
需要注意的是，我们同样可以传递变量的指针，这样对于过程来说虽然依然是值传递，但是从效果上等同于传递了对应参数的引用

2. 引用调用

在引用调用(call-by-reference)中，实参的地址作为相应的形式参数的值被传递给被调用者，在被调用者的代码中使用该形参时，实现方法是沿着这个指针找到调用者指明的内存位置，因此，改变形式参数看起来就像是改变饿了实参一样

3. 名调用

0x7: 别名

引用调用或者其他类似的方法，比如像Java中那样把对象的引用当值传递，会引起一个有趣的结果，即两个形参指向同一个位置，这样的变量称为另一个变量的别名(alias)，结果是，任意两个看起来从两个不同的形参中获得值的变量也可能变成对方的别名，这个现象在PHP中也同样存在
事实上，如果编译器要优化一个程序，就要理解别名现象以及产生这一现象的机制，必须在确认某些变量相互之间不是别名之后才可以优化程序

 

4. 一个简单的语法制导翻译器

0x1: 引言

编译器在分析(scanning)阶段把一个源程序划分成各个组成部分，并生成源程序的内部表示形式，这种内部表示称为中间代码，然后，编译器在合成阶段将这个中间代码翻译成目标程序
分析阶段的工作是围绕着待编译语言的的"语法"展开的，一个程序设计语言的语法(syntax)描述了该语言的程序的正确形式，而该语言的语义(semantics)则定义了程序的含义，即每个程序在运行时做什么事情
我们将在接下来讨论一个广泛使用的表示方法来描述语法，即上下文无关文法或BNF(Backus-Naur范式)，描述语义的难度远远大于描述语言语法的难度，因此，我们将结合非形式化描述和启发式描述的来描述语言的语义

词法分析器使得翻译器可以处理由多个字符组成的构造，比例标识符。标识符由多个字符组成，但是在语法分析阶段被当作一个单元进行处理，这样的单元称作词法单元(token)
接下来考虑中间代码的生成

图中显示了两种中间代码形式

1. 左: 抽象语法树(abstract syntax tree): 表示了源程序的层次化语法结构
2. 右: "三地址"指令序列: 三地址指令最多只执行一个运算，通常是计算、比较、分支跳转

0x2: 语法定义

在本节中，我们将讨论一种用于描述程序设计语言语法的表示方法"上下文无关文法"，或简称"文法"，文法将被用于组织编译器前端
文法自然地描述了大多数程序设计语言构造的层次化语法结构，例如，Java中的if-else语句通常具有如下形式

if (expression) statement else statement
//即一个if-else语句由关键字if、左括号、表达式、右括号、语句块、关键字else、语句块组成，这个构造规则可以表示为
stmt -> if (expr) stmt else stmt
//其中箭头(->)表示"可以具有如下形式"

这样的规则称为产生式(production)，在一个产生式中，像关键字if和括号这样的词法元素称为终结符号(terminal)，像expr和stmt这样的变量表示终结符号的序列，它们称为非终结符号(nonterminal)

1. 文法定义

一个上下文无关文法(context-free grammar)由四个元素组成

1. 终结符号集合，也称为"词法单元"，终结符号是该文法所定义的语言的基本符号的集合
2. 非终结符号集合，也称为"语法变量"，每个非终结符号表示一个终结符号串的集合
3. 产生式集合，其中每个产生式包括
    1) 一个称为产生式头或左部的非终结符号
    2) 一个箭头
    3) 一个称为产生式体或右部的由终结符号及非终结符号组成的序列，产生式主要用来表示某个构造的某种书写形式，如果产生式头非终结符号代表一个构造，那么该产生式体就代表了该构造的一种书写方式
    4) 指定一个非终结符号为开始符号

在编译器中，词法分析器读入源程序中的字符序列，将它们组织为具有词法含义的词素，生成并输出代表这些词素的词法单元序列，词法单元由两个部分组成: 名字和属性值

1. 词法单元的名字是词法分析器进行语法分析时使用的抽象符号，我们通常把这些词法单元名字称为终结符号，因为它们在描述程序设计语言的文法中是以终结符号的形式出现的
2. 如果词法单元具有属性值，那么这个值就是一个指向符号表的指针，符号表中包含了该词法单元的附加信息，这些附加信息不是文法的组成部分，因此我们在讨论语法分析时，通产将词法单元和终结符号当作同义词

如果某个非终结符号是某个产生式的头部，我们就说该产生式是该非终结符号的产生式，一个终结符号串是由零个或多个终结符号组成的序列，零个终结符号组成的串称为空串(empty string)

2. 推导

根据文法推导符号串时，我们首先从开始符号出发，不断将某个非终结符号替换为该非终结符号的某个产生式的体，可以从开始符号推导得到的所有终结符号串的集合称为该文法定义的语言(language)
语法分析(parsing)的任务是: 接受一个终结符号串作为输入，找出从文法的开始符号推导出这个串的方法，如果不能从文法的开始符号推导得到该终结符号，则报告该终结符号串中包含的语法错误
一般情况下，一个源程序中会包含由多个字符组成的词素，这些词素由词法分析器组成词法单元，而词法单元的第一个分量就是被语法分析器处理的终结符号

3. 语法分析树

语法分析树用图形方式展现了从文法的开始符号推导出相应语言中的符号串的过程，如果非终结符号A有一个产生式A -> XYZ，那么在语法分析树中就有可能有一个标号为A的内部结点，该结点有三个子节点，从左向右的标号分别为X、Y、Z

从本质上说，给定一个上下文无关文法，该文法的一棵语法分析树(parse tree)是具有以下性质的树

1. 根结点的标号为文法的开始符号
2. 每个叶子结点的标号为一个终结符号或空串
3. 每个内部结点的标号为一个非终结符号
4. 如果非终结符号A是某个内部结点的标号，并且它的子结点的标号从左至右分别为X1、X2、...、Xn，那么必然存在产生式A -> X1 X2 .. Xn，其中X1 X2 .. Xn既可以是终结符号，也可以是非终结符号，作为一个特殊情况，如果A -> 空串是一个产生式，那么一个标号为A的结点可以只有标号为空串的子结点

一棵语法分析树的叶子结点从左向右构成了树的结果(yield)，也就是从这课语法分析树的根节点上的非终结符号推导得到(生成)的符号串
一个文法的语言的另一个定义是指任何能够由某课语法分析树生成的符号串的集合，为一个给定的终结符号串构建一棵语法分析树的过程称为对该符号串进行语法分析

4. 二义性

在根据一个文法讨论某个符号串的结构时，我们必须非常小心，一个文法可能有多课语法分析树能够生成同一个给定的终结符号串，这样的文法称为具有二义性(ambiguous)，要证明一个文法具有二义性，我们只需要找到一个终结符号串，说明它是两棵以上语法分析树的结果
因为具有两棵以上语法分析树的符号串通常具有多个含义，所以我们需要为编译应用设计出没有二义性的文法，或者在使用二义性文法时使用附加规则来消除二义性

5. 运算符的结合性

在大多数程序设计语言中，加减乘除4种算术运算符都是左结合的，某些常用运算符是右结合的，例如赋值运算符，对于左结合的文法来说，语法树向左下端延伸，而右结合的文法语法树向有下端延伸

6. 运算符的优先级

算术表达式的文法可以根据表示运算符结合性和优先级的表格来建立

expr -> expr + term | expr - term | term
term -> term * factor | term / factor | factor
factor -> digit | (expr)

0x3: 语法制导翻译

语法制导翻译是通过向一个文法的产生式附加一些规则或程序片段而得到的

1. 语法制导翻译相关的概念

1. 属性(attribute): 属性表示与某个程序构造相关的任意的量，属性可以是多种多样的，比如
    1) 表达式的数据类型
    2) 生成的代码中的指令数目
    3) 为某个构造生成的代码中第一条指令的位置
因为我们用文法符号(终结符号、或非终结符号)来表示程序构造，所以我们将属性的概念从程序构造扩展到表示这些构造的文法符号上

2. (语法制导的)翻译方案(translation scheme): 翻译方案是一种将程序片段附加到一个文法的各个产生式上的表示法，当在语法分析过程中使用一个产生式时，相应的程序片段就会执行，这些程序片段的执行效果按照语法分析过程的顺序组合起来，得到的结果就是这次分析/综合过程处理源程序得到的翻译结果

2. 后缀表示

一个表达式E的后缀表示(postfix notation)可以按照下面的方式进行归纳定义

1. 如果E是一个变量或者常量，则E的后缀表示是E本身
2. 如果E是一个形如"E1 op E2"的表达式，其中op是一个二目运算符，那么E的后缀表示是E1E2op
3. 如果E是一个形如(E1)的被括号括起来的表达式，则E的后缀表示就是E1的后缀表示

例如，9-(5+2)的后缀表达式是952+-，即5+2首先被翻译成52+，然后这个表达式又成为减号的第二个运算分量
运算符的位置和它的运算分量个数(anty)使得后缀表达式只有一种解码方式，所以在后缀表示中不需要括号，处理后缀表达式的技巧就是

1. 从左边开始不断扫描后缀串，直到发现一个运算符为止
2. 然后向左找出适当数目的运算分量，并将这个运算符和它的运算分量组合在一起
3. 计算出这个运算符作用于这些运算分量上后得到的结果
4. 并用这个结果替换原来的运算分量和运算符，然后继续这个过程，向右搜寻另一个运算符

3. 综合属性

将量和程序构造关联起来(比如把数值及类型和表达式相关联)的想法可以基于文法来表示，我们将属性和文法的非终结符号及终结符号相关联，然后，我们给文法的各个产生式附加上语义规则。对于语法分析树中的一个结点，如果它和它的子结点之间的关系符合某个产生式，那么该产生式对应的规则就描述了如何计算这个结点上的属性

语法制导定义(syntax-direted definition)把每个文法符号和一个属性集合相关联，并且把每个产生式和一组语义规则(semantic rule)相关联，这些规则用于计算与该产生式中符号相关联的属性值

属性可以按照如下方式求值，对于一个给定的输入串x，构造x的一个语法分析树，然后按照下面的方法应用语义规则来计算语法分析树中各个结点的属性

1. 假设语法分析树的一个结点N的标号为文法符号X，我们用X.a表示该结点上X的属性a的值
2. 如果一棵语法分析树的各个结点上标记了相应的属性值，那么这课语法分析树就称为注释(annotated)语法分析树(注释分析树)

如果某个属性在语法分析树结点N上的值是由N的子结点以及N本身的属性值确定的，那么这个属性就称为综合属性(synthesized attribute)，综合属性有一个很好的性质: 只需要对语法分析树进行一次自底向上的遍历，就可以计算出属性的值
4. 简单语法制导定义

语法制导定义具有下面的重要性质

要得到代表产生式头部的非终结符号的翻译结果的字符串，只需要将产生式体中各非终结符号的翻译结果按照它们在非终结符号中的出现顺序连接起来，并在其中穿插一些附加的串即可，具有这个性质的语法制导定义称为简单(simple)语法制导定义

5. 树的遍历

树的遍历将用于描述属性的求值过程，以及描述一个翻译方案中的各个代码片段的执行过程。一个树的遍历(traversal)从根节点开始，并按照某个顺序访问树的各个结点
一次深度优先(depth-first)遍历从根节点开始，递归地按照任意顺序访问各个结点的子结点，并不一定要按照从左向右的顺序遍历，之所以称之为深度优先，是因为这种遍历总是尽可能地访问一个结点的尚未被访问的子节点(尽量一次就从一个结点追溯它的叶子)，因为它总是尽可能快地访问离根节点最远的结点(即最深的结点) 

1. 语法制导定义没有规定一棵语法分析树中各个属性值的求值顺序，只要一个顺序能够保证计算属性a的值时，a所依赖的其他属性都已经计算完毕，这个顺序就是可以接受的
2. 综合属性可以在自底向上遍历的时候计算
3. 自顶向下遍历指在计算完成某个结点的所有子结点的属性值之后才开始计算该结点的属性值的过程
4. 一般来说，当既有综合属性又有继承属性时，关于求值顺序的问题就变得相当复杂

0x4: 语法分析

语法分析是决定如何使用一个文法生成一个终结符号串的过程，我们接下来将讨论一种称为"递归下降"的语法分析方法，该方法可以用于语法分析和实现语法制导翻译器
程序设计语言的语法分析器几乎总是一次性地从左到右扫描输入，每次向前看一个终结符号，并在扫描时构造出分析树的各个部分
大多数语法分析方法都可以归纳为以下两类

1. 自顶向下(top-down)方法
自顶向下(top-down)构造过程从叶子结点开始，逐步构造出根结点，这种方法很容易地手工构造出高效的语法分析器

2. 自底向上(bottorn-up)方法
自底向上(bottorn-up)分析方法可以处理更多种文法和翻译方案，所以直接从文法生成语法分析器的软件工具常常使用自底向上的方法

1. 自顶向下分析方法

2. 预测分析法

递归下降分析方法(recursive-descent parsing)是一种自顶向下的语法分析方法，它使用一组递归过程来处理输入，文法的每个非终结符都有一个相关联的过程，这里我们考虑递归下降分析法的一种简单形式，称为预测分析法(predictive parsing)，在预测分析法中，各个非终结符对应的过程中的控制流可以由"向前看符号"无二义地确定，在分析输入串时出现的过程调用序列隐式地定义了该输入串的一棵语法分析树，如果需要，还可以通过这些过程调用来构建一个显式的语法分析树

3. 设计一个预测分析器

对于文法的任何非终结符号，它的各个产生式体的FIRST集合互不相交，如果我们有一个翻译方案，即一个增加了语义动作的文法，那么我们可以将这些语义动作当作此语法分析器的过程的一部分执行
一个预测分析器(predictive parser)程序由各个非终结符对应的过程组成，对应于非终结符A的过程完成以下两项任务

1. 检查"向前看符号"，决定使用A的哪个产生式，如果一个产生式的体为a(a为非空串)且向前看符号在FIRST(a)中，那么就选择这个产生式
    1) 对于任何向前看符号，如果两个非空的产生式体之间存在冲突，我们就不能对这种文法使用预测语法分析
    2) 如果A有空串产生式，那么只有当向前看符号不在A的其他产生式体的FIRST集合中时，才会使用A的空串产生式
2. 然后，这个过程模拟被选中产生式的体，也就是说，从左边开始逐个"执行"此产生式体中的符号，"执行"一个非终结符号的方法是调用该非终结符号对应的过程，一个与向前看符号匹配的的终结符号的"执行"方法则是读入下一个输入符号，如果在某个点上，产生式体中的终结符号和向前看符号不匹配，那么语法分析器就会报告一个语法错误

4. 左递归

通过下降语法分析器有可能进入无限循环，当出现如下所示的"左递归"产生式时，分析器就会出现无限循环

expr -> expr + term

在这里，产生式的最左边的符号和产生式头部的非终结符号相同，假设expr对应的过程决定使用这个产生式，因为产生式体的开头是expr，所以expr对应的过程将被递归调用，由于只有当产生式体中的一个终结符号被成功匹配时，向前看符号才会发生改变，因此在对expr的两次调用之间输入符号没有发生改变，结果，第二次expr调用所做的事情与第一次调用所做的事情完全相同，这意味着会对expr进行第三次调用，并不断重复，进入无限循环

 

5. 简单表达式的翻译器(源代码示例)

语法制导翻译方案常常作为翻译器的规约

0x1: 抽象语法和具体语法

设计一个翻译器时，名为抽象语法树(abstract syntax tree)的数据结构是一个很好的起点，在一个表达式的抽象语法树中，每个内部结点代表一个运算符，该结点的子结点代表这个运算符的运算分量。对于一个更加一般化的情况，当我们处理任意的程序设计语言构造时，我们可以创建一个针对这个构造的运算符，并把这个构造的具有语义信息的组成部分作为这个运算符的运算分量
抽象语法树也简称语法树(syntax tree)，在某种程序上和语法分析树相似

1. 在抽象语法树中，内部结点代表的是程序构造: 
2. 在语法分析树中，内部结点代表的是非终结符号: 具体语法树(concrete syntax tree)，相应的文法称为该语言的具体语法(concrete syntax)

文法中的很多非终结符号都是代表程序的构造，但也有一部分是各种各样的辅助符号，比如代表项、因子或其他表达式变体的非终结符号，在抽象语法树中，通常不需要这些辅助符号，因此会将这些符号省略掉，为了强调他们的区别，我们有时把语法分析树称为具体语法树(concrete syntex tree)，而相应的文法称为该语言的具体语法(concrete syntax)

0x2: 调整翻译方案

0x3: 非终结符号的过程

0x4: 翻译器的简化

0x5: 完整的程序

/**
 * Created by zhenghan.zh on 2016/1/18.
 */

import java.io.*;

class Parser
{
    static int lookahead;

    public Parser() throws IOException
    {
        lookahead = System.in.read();
    }

    void expr() throws IOException
    {
        term();
        while(true)
        {
            if (lookahead == '+')
            {
                match('+');
                term();
                System.out.write('+');
            }
            else if (lookahead == '-')
            {
                match('-');
                term();
                System.out.write('-');
            }
            else
                return;
        }
    }

    void term() throws IOException
    {
        if (Character.isDigit((char)lookahead))
        {
            System.out.write((char)lookahead);
            match(lookahead);
        }
        else
        {
            throw new Error("syntax error");
        }
    }

    void match(int t) throws IOException
    {
        if (lookahead == t)
        {
            lookahead = System.in.read();
        }
        else
        {
            throw new Error("syntax error");
        }
    }
}

public class Postfix
{
    public static void main(String[] args) throws IOException
    {
        System.out.println("hello");
        Parser parse = new Parser();
        parse.expr();
        System.out.write('\n');
    }
}

对整个编译过程有了一个整体的认识之后，下面我们从词法分析开始逐步深入学习编译原理

 

6. 词法分析

一个词法分析器从输入中读取字符，并将它们组成"词法单元对象"。除了用于语法分析的终结符号之外，一个词法单元对象还包含一些附加信息，这些信息以属性值的形式出现
构成一个词法单元的输入字符称为词素(lexern)，因此，"词法分析器"使得"语法分析器"不需要考虑词法单元的词素表示方法

0x1: 删除空白和注释

大部分语言语序词法单元之间出现任意数量的空白，在语法分析过程中同样会忽略源程序中的注释，所以这些注释也可以当作空白处理

for (;; peek = next input character)
{
    if( peek is a blank or a tab ) do nothing;
    else if( peek is a newline ) line = line + 1;
    else break;
}

0x2: 预读

在决定向语法分析器返回哪个词法单元之前，词法分析器可能需要预先读入一些字符，例如C或Java的词法分析器在遇到字符">"之后必须预先读入一个字符

1. 如果下一个字符是"="，那么">"就是字符序列">="的一部分。这个序列是代表"大于等于"运算符的词法单元的词素
2. 否则，">"本身形成了一个"大于"运算符，词法分析器就多读了一个字符

一个通用的预先读取输入的方法是使用输入缓冲区，词法分析器可以从缓冲区中读取一个字符，也可以把字符放回缓冲区，我们可以用一个指针来跟踪已被分析的输入部分，向缓冲区放回一个字符可以通过回移指针来实现
因为通常只需要预读一个字符，所以一种简单的解决方法是使用一个变量，比如peek，来保存下一个输入字符，在读入一个数字的数位或一个标识符的字符时，词法分析器会预读一个字符，例如在1后面预读一个字符来区别1、10，在t后预读一个字符来区分t和true
词法分析器只有在必要的时候才进行预读，像"*"这样的运算符不需要预读就能够识别，在这种情况下，peek的值被设置为空白符，词法分析器在寻找下一个词法单元时会跳过这个空白符

//词法分析起的不变式断言
当词法分析器返回一个词法单元时，变量peek要么保存了当前词法单元的词素后的那个字符，要么保存空白符

0x3: 常量

在一个表达式的文法中，任何允许出现数位的地方都应该允许出现任意的整型常量，要使得表达式中可以出现整数常量，我们可以创建一个代表整型常量的终结符号，例如num，也可以将整数常量的语法加入到文法中
将字符组成整数并计算它的数值的工作通常是由词法分析器完成的，因此在语法分析和翻译过程中可以将数字当作一个单元进行处理

当在输入流中出现一个数位序列时，词法分析器将向语法分析器传送一个词法单元，该词法单元包含终结符号num、及根据这些数位计算得到的整型属性值，如果我们把词法单元写成用<>括起来的元祖，那么输入31+28+59就被转换成序列

<num, 31> <+> <num, 28> <+> <num, 59>

0x4: 识别关键字和标识符

大多数程序设计语言使用for、do、if这样的固定字符串作为标点符号，或者用于标识某种构造，这些字符串称为关键字(keyword)
字符串还可以作为标识符，来为变量、数组、函数等命名，为了简化语法分析器，语言的文法通常把标识符当作终结符号进行处理，当某个标识符出现在输入中时，语法分析器都会得到相同的终结符号，如id，例如在处理如下输入时

count = count + increment
//语法分析器处理的是终结符号序列id = id + id

词法单元id有一个属性保存它的词素，将词法单元写作元祖形式，输入流的元祖序列是

<id, "count"> <=> <id, "count"> <+> <id, "increment"> <;>

关键字通常也满足标识符的组成规则，因此我们需要某种机制来确定一个词素什么时候组成一个关键字，什么时候组成一个标识符

1. 如果关键字作为保留字: 只有当一个字符串不是关键字时它才能组成一个标识符
2. 关键字作为标识符 

本章中的词法分析器使用一个表来保存字符串，解决了如下问题

1. 单一表示: 一个字符串可以将编译器的其余部分和表中字符串的具体表示隔离开，因为编译器后续的步骤可以只使用指向表中字符串的指针或引用，操作引用要比操作字符串本身更加高效
2. 保留字: 要实现保留字，可以在初始化时在字符串表中加入保留的字符串以及它们对应的词法单元。当词法分析器读到一个可以组成标识符的字符串或词素时，它首先检查这个字符串表中是否有这些词素，如是，它就返回表中的词法单元，否则返回带有终结符号id的词法单元

伪代码如下

Hashtable words = new Hashtable();

if(peek 存放了一个字母)
{
    将字母或数位读入一个缓冲区b;
    s = b中的字符形成的字符串;
    w = words.get(s)返回的词法单元;
    if(w 不是 null) return w;
    else
    {
        将键-值对(s, <id, s>)加入到words;
        return 词法单元<id, s>
    }
}

0x5: 词法分析器

将上文给出的伪代码片段组合起来，可以得到一个返回词法单元对象的函数scan

Token scan()
{
    跳过空白符;
    处理数字;
    处理保留字和标识符;
    //如果程序运行到这里，就将预读字符peek作为一个词法单元
    Token t = new Toekn(peek);
    peek = 空白符;
    return t;
}

0x6: 符号表

符号表(symbol table)是一种供编译器用于保存有关源程序构造的各种信息的数据结构

1. 这些信息在编译器的分析阶段被逐步收集并放入符号表
2. 它们在综合(scan)阶段用于生成目标代码
2. 符号表的每个条目中包含与一个标识符相关的信息，例如
    1) 字符串(词素)
    2) 类型
    3) 存储位置
    4) 其他相关信息
3. 符号表通常需要支持同一个标识符在一个程序中的多重声明

我们知道，一个声明的作用域是指该声明起作用的那一部分程序，我们将为每个作用域建立一个单独的符号表来实现作用域，每个带有声明的程序块都会有自己的符号表，这个块中的每个声明都在此符号表中有一个对应的条目，这种方法对其他能够设立作用域的程序设计语言构造同样有效，例如每个类也可以拥有自己的符号表，它的每个域和方法都在此表中有一个对应的条目

1. 符号表条目是在分析阶段由词法分析器、语法分析器和语义分析器创建并使用的，相对于词法分析器而言，语法分析器通常更适合创建条目，它可以更好地区分一个标识符的不同声明
2. 在有些情况下，词法分析器可以在它碰到组成一个词素的字符串时立刻建立一个符号表条目，但是在更多的情况下，词法分析器只能向语法分析器返回一个词法单元以及指向这个词素的指针，只有语法分析器才能决定是使用之前已经创建的符号表条目，还是为这个标识符创建一个新条目

1. 为每个作用域设置一个符号表

术语"标识符x的作用域"实际上指的是x的某个声明的作用域，术语作用域(scope)本身是指一个或多个声明起作用的程序部分
作用域是非常重要的，因为在程序的不同部分，可能会出于不同的目的而多次声明相同的标识符，再例如，子类可能重新声明一个方法名字以覆盖父类中的相应方法
如果程序块可以嵌套，那么同一个标识符的多次声明就可能出现在同一个块中

1. 块的符号表的实现可以利用作用域的最近嵌套原则，嵌套的结构确保可应用的符号表形成一个栈
2. 在栈的顶部是当前块的符号表，栈中这个表的下方是包含这个块的各个块的符号表，即语句块的最近嵌套(most-closely)规则
3. 符号表可以按照类似于栈的方式来分配和释放

有些编译器维护了一个散列表来存放可访问的符号表条目，这样的散列表实际上支持常量时间的查询，但是在进入和离开块时需要插入和删除相应的条目，并且在从一个块B离开时，编译器必须撤销所有因为B中的声明而对此散列表作出的修改，为此可以在处理B的时候维护一个辅助的栈来跟踪对这个散列表所做的修改，实现语句块的最近嵌套原则时，我们可以将符号表链接起来，也就是使得内嵌语句块的符号表指向外围语句块的符号表

2. 符号表的使用

从效果上看，一个符号表的作用是将信息从声明的地方传递到实际使用的地方

1. 当分析标识符x的声明时，一个语义动作将有关x的信息"放入"符号表中
2. 然后，一个像factor -> id这样的产生式的相关语义动作从符号表中"取出"这个标识符的信息，因为对一个表达式E1 or E2的翻译只依赖于对E1、E2的翻译，不直接依赖于符号表，所以我们可以加入任意数量的运算符，而不会影响从声明通过符号表到达使用地点的基本信息流

 

7. 生成中间代码

编译器的前端构造出源程序的中间表示，而后根据这个中间表示生成目标程序

0x1: 两种中间表示形式

1. 树型结构
    1) 语法分析树: 在语法分析过程中，将创建抽象语法树的结点来表示有意义的程序构造，随着分析的进行，信息以与结点相关的属性的形式被添加到这些结点上，选择哪些属性要依据待完成的翻译来决定
    2) 抽象语法树
2. 线性表示形式
    1) 三地址代码: 三地址代码是一个由基本程序步骤(例如两个值相加)组成的序列，和树形结构不一样，它没有层次化的结构，如果我们想对代码做出显著的优化，就需要这种表示形式，在那种情况下，我们可以把组成程序的很长的三地址语句序列分解为"基本块"，所谓基本块就是一个总是顺序执行的语句序列，执行时不会出现分支跳转

除了创建一个中间表示之外，编译器前端还会检查源程序是否遵循源语言的语法和语义规则，这种检查称为静态检查(static check)

0x2: 语法树的构造

0x3: 静态检查

静态检查是指在编译过程中完成的各种一致性检查，这些检查不仅可以确保一个程序被顺利地编译，而且还能在程序运行之前发现编程错误，静态检查包括 

1. 语法检查: 语法检查要求比文法中的要求更多，例如
    1) 任何作用域内同一个标识符最多只能声明一次
    2) 一个break语句必须处于一个循环或switch语句之内
//这些约束都是语法要求，但是它们并没有包括在用于语法分析的文法中
2. 类型检查: 一种语言的类型规则确保一个运算符或函数被应用到类型和数量都正确的运算分量上，如果必须要进行类型转换，比如将一个浮点数与一个整数相加，类型检查器就会在语法树中插入一个运算符来表示这个转换

1. 左值和右值

静态检查要确保一个赋值表达式的左部表示的是一个左值，一个像i这样的标识符是一个左值，像a[2]这样的数组访问也是左值，但2这样的常量不可以出现在一个赋值表达式的左部

2.  类型检查

类型检查确保一个构造的类型符合其上下文对它的期望，例如在if语句中

if(expr) stmt
//期望表达式expr是boolean型的

0x4: 三地址码

一旦抽象语法树构造完成，我们就可以计算树中各结点的属性值并执行各结点中的代码片段，进行进一步的分析和综合

1. 三地址指令

三地址代码是由如下形式的指令组成的序列

x = y op z
//x、y、z可以是名字、常量或由编译器生成的临时量；而op表示一个运算符

三地址指令将被顺序执行，当时当遇到一个条件或无条件跳转指令时，执行过程就会跳转

2. 语句的翻译

通过利用跳转指令实现语句内部的控制流，我们可以将语句转换成三地址代码

3. 表达式的翻译

我们将考虑包含二目运算符op、数组访问和赋值运算，并包含常量及标识符的表达式，以此来说明对表达式的翻译

0x5: 小结

1. 构造一个语法制导翻译器要从源语言的文法开始，一个文法描述了程序的层次结构。文法的定义使用了称为"终结符号"的基本符号和称为"非终结符号"的变量符号，这些符号代表了语言的构造。一个文法的规则，即产生式，由一个作为"产生式头"或"产生式左部"的非终结符，以及称为"产生式体"或"产生式右部"的终结符号/非终结符号序列组成。文法中有一个非终结符被指派为开始符号
2. 在描述一个翻译器时，在程序构造中附加属性是非常有用的，属性是指与一个程序构造关联的任何量值，因为程序构造是使用文法符号来表示的，因此属性的概念也被扩展到文法符号上。属性的例子包括与一个表示数字的终结符号num相关的整数值，或与一个表示标识符的终结符号id相关联的字符串
3. 词法分析器从输入中逐个读取字符，并输出一个词法单元的流，其中词法单元由一个终结符号以及以属性值形式出现的附加信息组成
4. 语法分析要解决的问题是指如何从一个文法的开始符号推导出一个给定的终结符号串。推导的方法是反复将某个非终结符号替换为它的某个产生式的体。从概念上讲，语法分析器会创建一棵语法分析树
5. 语法制导翻译通过在文法中添加规则或程序片段来完成
6. 语法分析的结果是源代码的一种中间表示形式，称为中间代码(AST或三地址码)

 

8. 词法分析器的实现

如果要手动地实现词法分析器，需要首先建立起每个词法单元的词法结构图或其他描述，然后我们可以编写代码来识别输入中出现的每个词素，并返回识别到的词法单元的有关信息
我们也可以通过如下方式自动生成一个词法分析器

1. 向一个词法分析器生成工具(lexical-analyzer generator)描述出词素的模式
2. 然后将这些模式编译为具有词法分析器功能的代码

在学习词法分析器生成工具之前，我们先学习正则表达式，正则表达式是一种可以很方便地描述词素模式的方法 

1. 正则表达式首先转换为不确定有穷自动机
2. 然后再转换为确定有穷自动机
3. 得到的结果作为"驱动程序"的输入，这个驱动程序就是一段模拟这些自动机的代码，它使用这些自动机来确定下一个词法单元
4. 这个驱动程序以及对自动机的规约形成了词法分析器的核心部分

0x1: 词法分析器的作用

词法分析是编译的第一个阶段，词法分析器的主要任务是读入源程序将、它们组成词素、生成并输出一个词法单元序列，每个词法单元对应于一个词素，这个词法单元序列被输出到语法分析器进行语法分析，词法分析器通常还要和符号表进行交互，当词法分析器发现了一个标识符的词素时，它要将这个词素添加到符号表中，在某些情况下，词法分析器会从符号表中读取有关标识符种类的信息，以确定向语法分析器传送哪个词法单元

词法分析器在编译器中负责读取源程序，因此它还会完成一些识别词素之外的其他任务

1. 任务之一是过滤掉源程序中的注释和空白(空格、换行符、制表符以及在输入中用于分割词法单元的其他字符)
2. 另一个任务是将编译器生成的错误消息与源程序的位置关联起来

有时，词法分析器可以分成两个级联的处理阶段

1. 扫描阶段主要负责完成一些不需要生成词法单元的简单处理，比如删除注释和将多个连续的空白字符压缩成一个字符
2. 词法分析阶段是较为复杂的部分，它处理扫描阶段的输出并生成词法单元

1. 词法分析及解析

把编译过程的分析部分划分为词法分析和语法分析阶段有如下几个原因

1. 最重要的考虑是简化编译器的设计，将词法分析和语法分析分离通常使我们至少可以简化其中的一项任务，例如如果一个语法分析器必须把空白符和注释当作语法进行处理，那么它就会比那些假设空白和注释已经被词法分析器过滤掉的处理器复杂得多，如果我们正在设计一个新的语言，将词法和语法分开考虑有助于我们得到一个更加清晰的语言设计方案
2. 提高编译器效率，把词法分析器独立出来使我们能够使用专用语词法分析任务、不进行语法分析的技术，此外，我们可以使用专门的用于读取输入字符的缓冲技术来显著提高编译器的速度
3. 增强编译器的可移植性，输入设备相关的特殊性可以被限制在词法分析器中

2. 词法单元、模式、词素

在讨论词法分析时，我们使用三个相关但有区别的术语

1. 词法单元由一个词法单元名和一个可选的属性值组成，词法单元名是一个表示某种词法单位的抽象符号，比如一个特定的关键字，或者代表一个标识符的输入字符序列。词法单元名字是由语法分析器处理的输入符号
2. 模式描述了一个词法单元的词素可能具有的形式，当词法单元是一个关键字时，它的模式就是组成这个关键字的字符序列。对于标识符和其他词法单元，模式是一个更加复杂的结构，它可以和很多符号串匹配
3. 词素是源程序中的字符序列，它和某个词法单元的模式匹配，并被词法分析器识别为该词法单元的一个实例

在很多程序设计语言中，下面的类别覆盖了大部分或所有的词法单元

1. 每个关键字有一个词法单元，一个关键字的模式就是该关键字本身
2. 表示运算符的词法单元，它可以表示单个运算符，也可以表示一类运算符
3. 一个表示所有标识符的词法单元
4. 一个或多个表示常量的词法单元，例如数字和字面值字符串
5. 每一个标点符号有一个词法单元，例如左右括号、逗号、分号

3. 词法单元的属性

如果有多个词素可以和一个模式匹配，那么词法分析器必须向编译器的后续阶段提供有关被匹配词素的附加信息，例如0、1都能和词法单元number的模式匹 配，但是对于代码生成器而言，至关重要的是知道在源程序中找到了哪个词素，很多时候，词法分析器不仅向语法分析器返回一个词法单元名字，还会返回一个描述 该词法单元的词素的属性值
词法单元的名字将影响语法分析过程中的决定，而属性值会影响语法分析之后对这个词法单元的翻译
通常，一个标识符的属性值是一个指向符号表中该标识符对应条目的指针

4. 词法错误

如果没有其他组件的帮助，词法分析器很难发现源代码中的错误，然而，假设出现所有词法单元的模式都无法和剩余输入的某个前缀相匹配的情况，此时词法分析器就不能继续处理输入，当出现这种情况时，最简单的错误恢复策略是"恐慌模式"恢复，我们从剩余的输入中不断删除字符，直到词法分析器能够在剩余输入的开头发现一个正确的词法单元为止
可能采取的其他错误恢复动作包括

1. 从剩余的输入中删除一个字符
2. 从剩余的输入中插入一个遗漏的字符
3. 用一个字符来替换另一个字符
4. 交换两个相邻的字符

这些变换可以在试图修复错误输入时进行，最简单的策略是检查是否可以通过一次变换将剩余输入的某个前缀变成一个合法的词素，这种策略的合理性在于，在实践中，大多数词法错误只涉及一个字符

0x2: 输入缓冲

在讨论如何识别输入流中的词素之前，我们首先讨论几种可以加快源程序读入速度的方法。源程序读入虽然简单却很重要，由于我们常常需要查看一下词素之后的若干字符才能确定是否找到了正确的词素，因此这个任务变得有些困难

1. 缓冲区对

由于在编译一个大型源程序时需要处理大量的字符，处理这些字符需要很多的时间
因此开发了一些特殊的缓冲区技术来减少用于处理单个输入字符的时间开销，一种重要的机制就是利用两个交替读入的缓冲区

每个缓冲区的容量都是N个字符，通常N是一个磁盘块的大小，如4096字节，这使得我们可以使用系统读取指令一次将N个字符读入到缓冲区中，而不是每读入一个字符调用一次系统读取命令。如果输入文件中的剩余字符不足N个，那么就会有一个特殊字符(EOF)来标记源文件的结束，这个特殊字符不同于任何可能出现在源程序中的字符
程序为输入维护了两个指针

1. lexemeBegin指针: 该指针指向当前词素的开始处，当前我们正试图确定这个词素的结尾
2. forward指针: 它一直向前扫描，直到发现某个模式匹配位置

一旦确定了下一个词素，forward指针将指向该词素结尾的字符，词法分析器将这个词素作为某个返回给语法分析器的词法单元的属性值记录下来，然后使lexemeBegin指针指向刚刚找到的词素之后的第一个字符
将forward指针前移(即归零)要求我们首先检查是否已经到达某个缓冲区的末尾，如果是，我们必须将N个新字符读到另一个缓冲区中，且将forward指针指向这个新载入字符的缓冲区的头部
只要我们从不需要越过实际的词素向前看很远，以至于这个词素的长度加上我们向前看的距离大于N，我们就决不会在识别这个词素之前覆盖叼这个尚在缓冲区中的待别试词素

2. 哨兵标记

如果我们扩展每个缓冲区，使它们在末尾包含一个"哨兵(sentinel)"字符，我们就可以把对缓冲区末端的检测和对当亲字符的测试合二为一，这个哨兵字符必须是一个不会在源程序中出现的特殊字符，一个自然的选择就是字符EOF

0x3: 词法单元的规约

正则表达式是一种用来描述词素模式的重要表示方法，虽然正则表达式不能表达出所有可能的模式，但是它们可以高效地描述在处理词法单元时要用到的模式类型

1. 串和语言

字母表(alphabet)是一个有限的符号集合，符号的典型例子包括字母、数位、标点符号
某个字母表上的一个串(string)是该字母表中符号的一个有穷序列，在语言理论中，术语"句子"、"字"常常被当作"串"的同义词，而语言(language)是某个给定字母表上一个任意的可数的串集合，这个定义非常宽泛
下面是关于串相关的常用术语

1. 串s的前缀(prefix)是从s的尾部删除0个或多个符号后得到的串
2. 串s的后缀(suffix)是从s的开始处删除0个或多个符号后得到的串
3. 串s的子串(substring)是删除s的某个前缀和某个后缀之后得到的串
4. 串s的真(true)前缀、真后缀、真子串分别是s的既不等于空串、也不等于s本身的前缀、后缀的子串
5. 串s的子序列(subsequence)是从s中删除0个或多个符号后得到的串，这些被删除的符号可能不相邻

2. 语言上的运算

在词法分析中，最重要的语言上的运算是并、连接、闭包运算

3. 正则表达式

人们常常使用一种称为正则表达式的表示方法来描述语言，正则表达式
可以描述所有通过对某个字母表上的符号应用这些运算符而得到的语言
正则表达式可以由较小的正则表达式按照如下规则递归地构建，每个正则表达式r表示一个语言L(r)，这个语言也是根据r的子表达式所表示的语言递归地定义的

1. 可以用一个正则表达式定义的语言叫做正则集合(regular set)
2. 如果两个正则表达式r、s表示同样的语言，则称r、s等价(equivalent)，记作r = s
3. 正则表达式遵守一些代数定律，每个定律都断言两个具有不同形式的表达式等价

4. 正则定义

5. 正则表达式的扩展

0x4: 词法单元的识别

我们已经讨论了如何使用正则表达式来表示一个模式，接下来，我们继续讨论如何根据各个需要识别的词法单元的模式来构造出一段代码

1. 状态转换图

作为构造词法分析器的一个中间步骤，我们首先将模式转换成具有特定风格的流图，称为"状态转换图"
状态转换图(transition diagram)有一组被称为"状态(state)"的结点或圆圈，词法分析器在扫描输入串的过程中寻找和某个模式匹配的词素，而转换图中的每个状态代表一个可能在这个过程中出现的情况，我们可以将一个状态看作是对我们已经看到的位于lexemeBegin指针和forward指针之间的字符的总结，它包含了我们在进行词法分析时需要的全部信息
一些关于状态转换图的重要约定如下

1. 某些状态称为接受状态或最终状态，这些状态表明已经找到了一个词素，虽然实际的词素可能并不包括lexemeBegin指针和forward指针之间的所有字符，我们用双层的圈来表示一个接受状态，并且如果该状态要执行一个动作的话，通常是向语法分析器返回一个词法单元和相关属性值，我们把这个动作附加到该接收状态上
2. 另外，如果需要将forward回退到一个位置，那么我们将在该接受状态的附近加上一个*
3. 有一个状态被指定为开始状态，也称为初始状态，该状态由一条没有出发结点的、标号为"start"的边指明，在读入任何输入符号之前，状态转换图总是处于它的开始状态

2. 保留字和标识符的识别

我们可以使用两种方法来处理那些看起来很像标识符的保留字

1. 初始化时就将各个保留字填入符号表，符号表条目的某个字段会指明这些串不是普通的标识符，并指出它们所代表的词法单元
2. 为每个关键字建立单独的状态转换图，要注意的是，这样的状态转换图包含的状态表示看到该关键字的各个后续字母后的情况

3. 连续性例子
4. 基于状态转换图的词法分析器的体系结构

有几种方法可以根据一组状态转换图构造出一个词法分析器，不管整体的策略是什么，每个状态总是对应于一段代码，我们可以想象有一个变量state保存了一个状态转换图的当前状态的编号，有一个switch语句根据state的值将我们转到对应于各个可能状态的相应的代码段，我们可以在那里找到该状态需要执行的动作，一个状态的代码本身常常也是一条switch语句或多路分支语句，这个语句读入并检查下一个输入字符，由此确定下一个状态

1. 我们可以让词法分析器顺序地尝试各个词法单元的状态转换图
2. 我们可以"并行地"运行各个状态转换图
3. 我们可以将所有的状态转换图合并为一个图，我们允许合并后的状态转换图尽量多的读取输入，直到不存在下一个状态位置，然后去最长的和某个模式匹配的最长词素

0x5: Code Example

// getTokenExample.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h" 
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <stdlib.h>

using namespace std;

char ch;
char stra[256];
struct keyword
{
    int number;
    char attribute[20];
}keywords[17]=
{
    {1,"break"},
    {2,"char"},
    {3,"continue"},
    {4,"do"},
    {5,"double"},
    {6,"else"},
    {7,"extern"},
    {8,"float"},
    {9,"for"},
    {10,"int"},
    {11,"if"},
    {12,"long"},
    {13,"short"},
    {14,"static"},
    {15,"switch"},
    {16,"void"},
    {17,"while"}
};
 
int IsLetter(char ch);
int IsDigit(char ch);
int checkReserve(char str[]);
char Concat(char str[],char a);
void lexer();
void GetBC();
void resetScanBuffer(char str[]);
void inPut();
void GetChar();

void lexer()
{
    char strToken[50] = "";
    if(IsLetter(ch))
    {
        //get a token
        while(IsLetter(ch) || IsDigit(ch))
        {
            Concat(strToken, ch);
            GetChar();
        }
        //check if keyword
        checkReserve(strToken);
        if(checkReserve(strToken))
        {
            cout << '<' << checkReserve(strToken) << ',' << strToken << '>' << endl;
            //clear scan buffer
            resetScanBuffer(strToken);
        }
        else 
        {
            cout << '<' << "70," << strToken << '>' << endl; 
            resetScanBuffer(strToken);
        }
    }
    else if(IsDigit(ch))
    {
        while(IsDigit(ch))
        {
            Concat(strToken,ch);
            GetChar();
        }
        cout << '<' << "80," << strToken << '>' << endl;
    }
    else 
    {
        //check calculate symbol
        switch(ch)
        {
            case '<' : 
                GetChar();
                if(ch == '=') 
                    cout << '<' << "31," << "<=" << '>' << endl;
                else if(ch == '>') 
                    cout << '<' << "32," << "<>" << '>' << endl;
                else 
                    cout << '<' << "30," << '<' << '>' << endl;
                break;
            case '>' : 
                GetChar();
                if(ch == '=') 
                {
                    cout << '<' << "34," << ">=" << '>' << endl;
                    break;
                }
                else 
                {
                    cout << '<' << "33," << '>' << '>' << endl;
                    break;
                }
            case '=' :
                cout << '<' << "35," << '=' << '>' << endl;
                break;
            case '(' :
                cout << '<' << "36," << '(' << '>' << endl;
                break;
            case ')' :
                cout << '<' << "37," << ')' << '>' << endl;
                break;
            case '*' :
                GetChar();
                if(ch == '*') 
                {
                    cout << '<' << "38," << "**" << '>' << endl;
                    break;
                }
                else 
                {
                    cout << '<' << "39," << '*' << '>' << endl;
                    break;
                }
            case ':' : 
                GetChar();
                if(ch == '=') 
                {
                    cout << '<' << "40," << ":=" << '>' << endl;
                    break;
                }
                else 
                    break;
            case '+' : 
                cout << '<' << "41," << '+' << '>' << endl;
                break;
            case '-' : 
                cout << '<' << "42," << '-' << '>' << endl;
                break;
            case '?' : 
                cout << '<' << "43," << '?' << '>' << endl;
                break;
            case ',' : 
                cout << '<' << "44," << ',' << '>' << endl;
                break;
            case ';' : 
                cout << '<' << "45," << ';' << '>' << endl;
                break;
            case '\n' : 
                break;
            default : 
                cout << '<' << "0," << ch << '>' << endl;
                break;
        }
    }
}

    
void GetBC()
{
    while(ch == ' ' || ch == '\n' || ch == '\t')
        GetChar();
}
int IsLetter(char ch)
{
    if((ch <= 90) && (ch >= 65) || (ch <= 122) && (ch >= 97))
        return 1;
    else 
        return 0;
}

int IsDigit(char ch)
{
        if((ch <= 57) && (ch >= 48))
            return 1;
        else 
            return 0;
}

int checkReserve(char str[])
{
    int i;
    for(i = 0; i < 17; i++)
    {
          if(strcmp(str, keywords[i].attribute) == 0)
            return keywords[i].number;
    }
    return 0;
}

char Concat(char str[],char a)
{
    int i = 0;
    i = strlen(str);
    str[i] = a;
    str[i+1] = '\0';
    return *str;
}

void resetScanBuffer(char str[])
{
    int i,j;
    i = strlen(str);
    for(j = 0; j < i; j++)
        str[i] = '\0';
}

void inPut()
{
    int i;
    for(i=0;ch!='$';i++)
    {stra[i]=ch;
    ch=getchar();}
}

void GetChar()
{
    int i=1;
    ch = stra[i];
    i++;
}
    


int _tmain(int argc, _TCHAR* argv[])
{
    GetChar();
    GetBC();
    while(ch != ' ' && ch != '\n' && ch != '\t')
    {
        lexer();
        ch = getchar();
        GetBC();
    } 
    return 0;
}

Relevant Link:

《编译原理 中文第二版》 89页
http://www.ymsky.net/views/64074.shtml
http://rosettacode.org/wiki/Tokenize_a_string#C.2B.2B
http://www.hackingwithphp.com/21/5/6/how-to-parse-text-into-tokens
http://www.cnblogs.com/yanlingyin/archive/2012/04/17/2451717.html

 

9. 词法分析器生成工具Lex

Lex(在最新的实现中也称为Flex)，它支持使用正则表达式来描述各个词法单元的模式，由此给出一个词法分析器的规约，Lex工具的输入表示方法称为Lex语言(Lex Language)，而工具本身则称为Lex编译器(Lex Compiler)，在它的核心部分，Lex编译器将输入的模式转换成一个状态转换图，并生成相应的实现代码，存放到文件lex.yy.c中，这些代码模拟了状态转换图

0x2: Lex程序的结构

一个Lex程序具有如下形式

声明部分
%%
转换规则
%%
辅助函数

1. 声明部分

声明部分包括变量和明示常量(manifest constant，被声明的表示一个常数的标识符，如一个词法单元的名字)的声明

2. 转换规则

Lex程序的每个转换规则具有如下形式

模式 { 动作 }
1. 模式: 是一个正则表达式，它可以使用声明部分中给出的正则定义
2. 动作: 动作部分是代码片段

3. 辅助函数

包含了各个动作需要使用的所有辅助函数

0x3: Lex中的冲突解决

Lex解决冲突的两个规则，当输入的多个前缀与一个或多个模式匹配时，Lex用如下规则选择正确的词素

1. 总是选择最长的前缀
2. 如果最长的可能前缀与多个模式匹配，总是选择在Lex程序中先被列出的模式

0x4: 向前看运算符

0x5: 有穷自动机

我们接下来学习Lex是如何将它的输入程序变成一个词法分析器的，转换的核心是被称为有穷自动机(finite automate)的表示方法，这些自动机在本质上是与状态转换图类似的图，但有如下几点不同

1. 有穷自动机是识别器(recognizer)，它们只能对每个可能的输入串返回"是"、或"否"两种结果
2. 有穷自动机分为两类
    1) 不确定的有穷自动机(nondeterministic finite automate NFA)对其边上的标号没有任何限制，一个符号标记离开同一状态的多条边，并且空串也可以作为标号
    2) 对于每个状态及自动机输入字母表中的每个符号，确定的有穷自动机(deterministic finite automate DFA)有且只有一条离开该状态、以该符号为标号的边

确定的和不确定的有穷自动机能识别的语言的集合是相同的，事实上，这些语言的集合正好是能够用正则表达式描述的语言的集合，这个集合中的语言称为正则语言(regular language)

1. 不确定的有穷自动机

0x6: 从正则表达式到自动机

0x7: 词法分析器生成工具的设计

0x8: Lex使用学习

1. Hello world

example1.lt

%{
#include <stdio.h>
%}
%%
stop    printf("Stop command received\n");
start   printf("Start command received\n");
%%

编译

lex example1.lt
gcc lex.yy.c -o example -ll
./example

可以看到，示例程序会自动读取输入，并根据正则词法规则进行词法解析，并生成对应的Token制导结果

2. 正则匹配

接下来在Lex中引用正则，本质上这也是词法分析状态机的基础

%{
#include <stdio.h>
%}
%%
[0123456789]+           printf("NUMBER\n");
[a−zA−Z][a−zA−Z0−9]*    printf("WORD\n");
%%

3. 一个更复杂的类C语法示例

待解析文件

logging {
    category lame−servers { null; };
    category cname { null; };
};

zone "." {
    type hint;
    file "/etc/bind/db.root";
};

example1.lt

%{
#include <stdio.h>
%}
%%
[a−zA−Z][a−zA−Z0−9]*    printf("WORD ");
[a−zA−Z0−9\/.−]+        printf("FILENAME ");
\"                      printf("QUOTE ");
\{                      printf("OBRACE ");
\}                      printf("EBRACE ");
;                       printf("SEMICOLON ");
\n                      printf("\n");
[ \t]+                  /* ignore whitespace */;
%%

0x9: Yacc学习

YACC没有输入流的概念，它仅接受预处理过的符号集，Yacc被用作编译器的解析文析的工具。计算机语言不允许有二义性。因此，YACC在遇到有歧义时会抱怨移进/归约或者归约/归约冲突

1. 入门例程

待编译文件

heat on
    Heater on!
heat off
    Heater off!
target temperature 22
    New temperature set!

example1.lt

%{
#include <stdio.h>
#include "y.tab.h"
%}
%%
[0-9]+                  return NUMBER;
heat                    return TOKHEAT;
on|off                  return STATE;
target                  return TOKTARGET;
temperature             return TOKTEMPERATURE;
\n                      /* ignore end of line */;
[ \t]+                  /* ignore whitespace */;
%%

注意两个重要的变化

1. 引入了头文件y.tab.h
2. 不再使用print函数，而是直接返回符号的名字。这样做的目的是为了接下来将它嵌入到YACC中，而后者对打印到屏幕的内容根本不关心。Y.tab.h定义了这些符号

example1.y

%{
#include <stdio.h>
#include <string.h>

void yyerror(const char *str)
{
    fprintf(stderr,"error: %s\n",str);
}

int yywrap()
{
    return 1;
}

main()
{
    yyparse();
}

%}

%token NUMBER TOKHEAT STATE TOKTARGET TOKTEMPERATURE

%%

commands: /* empty */
    | commands command
    ;


command:
    heat_switch
    |
    target_set
    ;

heat_switch:
    TOKHEAT STATE 
    {
        printf("\tHeat turned on or off\n");
    }
    ;

target_set:
    TOKTARGET TOKTEMPERATURE NUMBER
    {
        printf("\tTemperature set\n");
    }
    ;

编译

yacc -d example1.y
//如果调用YACC时启用了-d选项，会将这些符号会输出到y.tab.h文件
lex example1.lt
gcc lex.yy.c y.tab.c -o example1

2. 拓展温度调节器使其可处理参数

上面的示例可以正确的解析温度调节器的命令，但是它并不知道应该做什么，它并不能取到你输入的温度值
接下来工作就是向其中加一点功能使之可以读取出具体的温度值。为此我们需要学习如何将Lex中的数字(NUMBER)匹配转化成一个整数，使其可以在YACC中被读取
当Lex匹配到一个目标时，它就会将匹配到的文字放到yytext中。YACC从变量yylval中取值

%{
#include <stdio.h>
#include "y.tab.h"
%}
%%
[0-9]+                  yylval=atoi(yytext); return NUMBER;
heat                    return TOKHEAT;
on|off                  yylval=!strcmp(yytext,"on"); return STATE;
target                  return TOKTARGET;
temperature             return TOKTEMPERATURE;
\n                      /* ignore end of line */;
[ \t]+                  /* ignore whitespace */;
%%

example1.y

%{
#include <stdio.h>
#include <string.h>

void yyerror(const char *str)
{
    fprintf(stderr,"error: %s\n",str);
}

int yywrap()
{
    return 1;
}

main()
{
    yyparse();
}

%}

%token NUMBER TOKHEAT STATE TOKTARGET TOKTEMPERATURE

%%

commands:
    | commands command
    ;


command:
    heat_switch
    |
    target_set
    ;

heat_switch:
    TOKHEAT STATE 
    {
        if($2)
            printf("\tHeat turned on\n");
        else
            printf("\tHeat turned off\n");
    }
    ;

target_set:
    TOKTARGET TOKTEMPERATURE NUMBER
    {
        printf("\tTemperature set to %d\n",$3);
    }
    ;

0x10: Lex和YACC内部工作原理

1. 在YACC文件中，main函数调用了yyparse()，此函数由YACC自动生成，在y.tab.c文件中
2. 函数yyparse从yylex中读取符号/值组成的流。你可以自己编码实现这点，或者让Lex帮你完成。在我们的示例中，我们选择将此任务交给Lex 
3. Lex中的yylex函数从一个称作yyin的文件指针所指的文件中读取字符。如果你没有设置yyin，默认是标准输入(stdin)。输出为yyout，默认为标准输出(stdout)
4. 可以在yywrap函数中修改yyin，此函数在每一个输入文件被解析完毕时被调用，它允许你打开其它的文件继续解析，如果是这样，yywarp的返回值为0。如果想结束解析文件，返回1
5. 每次调用yylex函数用一个整数作为返回值，表示一种符号类型，告诉YACC当前读取到的符号类型，此符号是否有值是可选的，yylval即存放了其值
6. 默认yylval的类型是整型(int)，但是可以通过重定义YYSTYPE以对其进行重写。分词器需要取得yylval,为此必须将其定义为一个外部变量。原始YACC不会帮你做这些，因此你得将下面的内容添加到你的分词器中，就在#include<y.tab.h>下即可:
extern YYSTYPE yylval;
Bison会自动完成剩下的事情

Relevant Link:

http://ds9a.nl/lex-yacc/
http://segmentfault.com/a/1190000000396608#articleHeader18

 

10. PHP Lex(Lexical Analyzer)

词法分析阶段就是从输入流里边一个字符一个字符的扫描，识别出对应的词素，最后把源文件转换成为一个TOKEN序列，然后丢给语法分析器
PHP在最开始的词法解析器是使用的是flex，后来PHP的改为使用re2c
我们通过一个简单的例子来看下re2c。如下是一个简单的扫描器，它的作用是判断所给的字符串是数字/小写字母/大小字母

#include <stdio.h>

char *scan(char *p)
{
    #define YYCTYPE char
    #define YYCURSOR p
    #define YYLIMIT p
    #define YYMARKER q
    #define YYFILL(n)
        /*!re2c
          [0-9]+ {return "number";}
          [a-z]+ {return "lower";}
          [A-Z]+ {return "upper";}
          [^] {return "unkown";}
         */
}

int main(int argc, char* argv[])
{
    printf("%s\n", scan(argv[1])); 
    return 0;
}
/*
re2c -o a.c a.l
gcc a.c -o a
chmod +x a
./a 1000

output: number
*/

代码中用到的几个re2c约定的宏定义如下

1. YYCTYPE: 用于保存输入符号的类型，通常为char型和unsigned char型
2. YYCURSOR: 指向当前输入标记，当开始时，它指向当前标记的第一个字符，当结束时，它指向下一个标记的第一个字符
3. YYFILL(n): 当生成的代码需要重新加载缓存的标记时，则会调用YYFILL(n)
4. YYLIMIT: 缓存的最后一个字符，生成的代码会反复比较YYCURSOR和YYLIMIT，以确定是否需要重新填充缓冲区 

0x1: RE2C
re2c - convert regular expressions to C/C++
re2c is a lexer generator for C/C++. It finds regular expression specifications inside of C/C++ comments and replaces them with a hard-coded DFA. The user must supply some interface code in order to control and customize the generated DFA.
re2c本质上是一个生成词法生成器的生成器

1. Given the following code

unsigned int stou (const char * s)
{
#   define YYCTYPE char
    const YYCTYPE * YYCURSOR = s;
    unsigned int result = 0;

    for (;;)
    {
        /*!re2c
            re2c:yyfill:enable = 0;

            "\x00" { return result; }
            [0-9]  { result = result * 10 + c; continue; }
        */
    }
}

2. re2c -is will generate

unsigned int stou (const char * s)
{
#   define YYCTYPE char
    const YYCTYPE * YYCURSOR = s;
    unsigned int result = 0;

    for (;;)
    { 
    {
        YYCTYPE yych;

        yych = *YYCURSOR;
        if (yych <= 0x00) goto yy3;
        if (yych <= '/') goto yy2;
        if (yych <= '9') goto yy5;
    yy2:
    yy3:
        ++YYCURSOR;
        { return result; }
    yy5:
        ++YYCURSOR;
        { result = result * 10 + c; continue; }
    }

    }
}

SYNTAX
Code for re2c consists of a set of rules, named definitions and inplace configurations.

0x2: PHP Lexer代码分析

\php-src-master\Zend\zend_language_scanner.l
zend_language_scanner.l 文件是re2c的规则文件，如果安装了re2c，可以通过以下命令来生成c文件

re2c -F -c -o zend_language_scanner.c zend_language_scanner.l

在re2c生成的词法解析器中，有两个维度的状态机

1. 第一个维度是从"字符串"的维度来维护的状态
2. 第二个是从"字符"的维度来维护状态

例如在Zend引擎中，当扫描到"<?php"时，Zend会将当前第一维度的状态设置为ST_IN_SCRIPTING，表示现在我们已经进入了PHP脚本解析的状态了。这个维度的状态可以很方便的在lex文件中作为各种前置条件，例如在lex文件中有很多这样的声明

其表达的意思就是：当我们词法解析器处于ST_IN_SCRIPTING这个状态时，遇到"exit"这个字符串就返回一个T_EXIT的Token标志(在Zend引擎中Token的宏都是以T_开头，其实际对应是一个数字)

在词法解析器扫描字符的过程中，需要记录扫描过程的各个参数以及当前状态，这些变量都是以yy开头命名。常用到的就是：yy_state, yy_text, yyleng, yy_cursor, yy_limit
各个变量的状态扫描前后的变化示意图。
扫描echo前

扫描echo后：

通过一个字符一个字符的扫描最终会得到一个Token序列，然后交由语法分析器去解析

0x3: Zend词法解析状态

Zend引擎在做词法解析时会自己维护扫描过程的状态，其实就是将yy_text等变量自己封装一个结构体，我们可以在lex文件中看到很多SCNG的宏调用，例如

static void yy_scan_buffer(char *str, unsigned int len)
{
    YYCURSOR       = (YYCTYPE*)str;
    YYLIMIT        = YYCURSOR + len;
    if (!SCNG(yy_start)) {
        SCNG(yy_start) = YYCURSOR;
    }
}

定位一下#define SCNG

/* Globals Macros */
#define SCNG    LANG_SCNG

$PHPSRC/Zend/zend_globals_macros.h

#else
# define LANG_SCNG(v) (language_scanner_globals.v)
extern ZEND_API zend_php_scanner_globals language_scanner_globals;
#endif 

可以看到Zend引擎维护了一个zend_php_scanner_globals的结构体
$PHPSRC/Zend/zend_globals.h

struct _zend_php_scanner_globals 
{
    zend_file_handle *yy_in;
    zend_file_handle *yy_out;

    unsigned int yy_leng;
    unsigned char *yy_start;
    unsigned char *yy_text;
    unsigned char *yy_cursor;
    unsigned char *yy_marker;
    unsigned char *yy_limit;
    int yy_state;
    zend_stack state_stack;
    zend_ptr_stack heredoc_label_stack;

    /* original (unfiltered) script */
    unsigned char *script_org;
    size_t script_org_size;

    /* filtered script */
    unsigned char *script_filtered;
    size_t script_filtered_size;

    /* input/output filters */
    zend_encoding_filter input_filter;
    zend_encoding_filter output_filter;
    const zend_encoding *script_encoding;

    /* initial string length after scanning to first variable */
    int scanned_string_len;
};

0x4: 扫描过程

词法扫描的入口在zend_language_scanner.l的int lex_scan(zval *zendlval)中

int lex_scan(zval *zendlval)
{
restart:
    ////设置当前token的首位置为当前位置
    SCNG(yy_text) = YYCURSOR;

//这段注释定义了各个类型的正则表达式匹配，在词法解析程序(如bison、re2c等)程序将本文件转化为c代码时会用到
/*!re2c
re2c:yyfill:check = 0;
LNUM    [0-9]+
DNUM    ([0-9]*"."[0-9]+)|([0-9]+"."[0-9]*)
EXPONENT_DNUM    (({LNUM}|{DNUM})[eE][+-]?{LNUM})
HNUM    "0x"[0-9a-fA-F]+
BNUM    "0b"[01]+
LABEL    [a-zA-Z_\x7f-\xff][a-zA-Z0-9_\x7f-\xff]*
WHITESPACE [ \n\r\t]+
TABS_AND_SPACES [ \t]*
TOKENS [;:,.\[\]()|^&+-/*=%!~$<>?@]
ANY_CHAR [^]
NEWLINE ("\r"|"\n"|"\r\n")

/* compute yyleng before each rule */
<!*> := yyleng = YYCURSOR - SCNG(yy_text);

//对于一些无需复杂处理的关键字，我们扫描到对应的关键字，直接生成对应的Token标志即可
<ST_IN_SCRIPTING>"exit" {
    return T_EXIT;
}

/*
<ST_IN_SCRIPTING>是指扫描到这个关键字的前置条件是词法解析器要处于ST_IN_SCRIPTING这个状态
在lex文件里边有以下几种方式可以设置当前的词法解析器状态
1. #define YYGETCONDITION()  SCNG(yy_state)
2. #define YYSETCONDITION(s) SCNG(yy_state) = s
3. #define BEGIN(state) YYSETCONDITION(STATE(state))
4. static void _yy_push_state(int new_state TSRMLS_DC)
{
    //将当前状态压栈，然后重设当前状态为新状态
    zend_stack_push(&SCNG(state_stack), (void *) &YYGETCONDITION(), sizeof(int));
    YYSETCONDITION(new_state);
}
*/
<ST_IN_SCRIPTING>"die" {
    return T_EXIT;
}

<ST_IN_SCRIPTING>"function" {
    return T_FUNCTION;
}

<ST_IN_SCRIPTING>"const" {
    return T_CONST;
} 
...

<INITIAL>"<?=" {
    BEGIN(ST_IN_SCRIPTING);
    return T_OPEN_TAG_WITH_ECHO;
}


<INITIAL>"<?php"([ \t]|{NEWLINE}) {
    HANDLE_NEWLINE(yytext[yyleng-1]);
    BEGIN(ST_IN_SCRIPTING);
    return T_OPEN_TAG;
}


<INITIAL>"<?" {
    if (CG(short_tags)) {
        BEGIN(ST_IN_SCRIPTING);
        return T_OPEN_TAG;
    } else {
        goto inline_char_handler;
    }
}
//进入PHP解析状态
inline_char_handler:
//我们知道PHP是嵌入式的，只有包含在<?php ?>或者<? ?>标签中的字符才会被执行解析
while (1) 
{
    YYCTYPE *ptr = memchr(YYCURSOR, '<', YYLIMIT - YYCURSOR); 
    YYCURSOR = ptr ? ptr + 1 : YYLIMIT;

    if (YYCURSOR >= YYLIMIT) 
    {
        break;
    }

    if (*YYCURSOR == '?') 
    {
        if (CG(short_tags) || !strncasecmp((char*)YYCURSOR + 1, "php", 3) || (*(YYCURSOR + 1) == '=')) { /* Assume [ \t\n\r] follows "php" */

            YYCURSOR--;
            break;
        }
    }
}

从这里也可以看出php的open tag的多种写法，接着我们看一下PHP里边注释是怎么扫描的，接着我们看一下PHP里边注释是怎么扫描的

<ST_IN_SCRIPTING>"#"|"//" 
{
    while (YYCURSOR < YYLIMIT) 
    {
        switch (*YYCURSOR++) 
        {
            case '\r':
                if (*YYCURSOR == '\n') 
                {
                    YYCURSOR++;
                }
                /* fall through */
            case '\n':
                CG(zend_lineno)++;
                break;
            case '?':
                if (*YYCURSOR == '>') 
                {
                    YYCURSOR--;
                    break;
                }
                /* fall through */
            default:
                continue;
        }

        break;
    }

    yyleng = YYCURSOR - SCNG(yy_text);

    return T_COMMENT;
}

可以看出，PHP是支持#以及//两种方式的单行注释。处于ST_IN_SCRIPTING状态下，遇到"#"|"//"，变触发了单行注释的扫描，从当前字符开始一直扫描到流缓冲区的末尾(也即是while(YYCURSOR < YYLIMIT))
遇到\r\n以及\n时，递增记录当前解析的行(zend_lineno++)，为了更好容错性，PHP还兼容了//?>这样的语法，也即是说当行注释是不会注释到?>的，可以从case '?'这个分支看出Zend的处理，先让当前指针YYCURSOR--，回到?>前一个字符，然后跳出循环，这样才不会吃掉"?>"导致后边认不到PHP的关闭标签
多行注释的扫描逻辑如下

<ST_IN_SCRIPTING>"/*"|"/**"{WHITESPACE} 
{
    int doc_com;

    if (yyleng > 2) 
    {
        doc_com = 1;
        RESET_DOC_COMMENT();
    } 
    else 
    {
        doc_com = 0;
    }

    while (YYCURSOR < YYLIMIT) 
    {
        if (*YYCURSOR++ == '*' && *YYCURSOR == '/') 
        {
            break;
        }
    }

    if (YYCURSOR < YYLIMIT) 
    {
        YYCURSOR++;
    } 
    else 
    {
        zend_error(E_COMPILE_WARNING, "Unterminated comment starting line %d", CG(zend_lineno));
    }

    yyleng = YYCURSOR - SCNG(yy_text);
    HANDLE_NEWLINES(yytext, yyleng);

    if (doc_com) 
    {
        CG(doc_comment) = zend_string_init(yytext, yyleng, 0);
        return T_DOC_COMMENT;
    }

    return T_COMMENT;
}

如果一直到文件结尾都没扫到*/，那就zend_error一个Waring错误，但是不会影响接下去的解析

数字类型的解析，从一开始的正则规则里边可以知道PHP支持5中类型的数字常量声明

LNUM    [0-9]+
DNUM    ([0-9]*"."[0-9]+)|([0-9]+"."[0-9]*)
EXPONENT_DNUM    (({LNUM}|{DNUM})[eE][+-]?{LNUM})
HNUM    "0x"[0-9a-fA-F]+
BNUM    "0b"[01]+

其实对于代码来说，数字其实也是字符，词法分析器扫描到这5个规则的时候，需要把当前的zendlval对应的解析成数字存起来，同时返回一个数字类型的Token标志，我们跟进最简单的LNUM规则处理

<ST_IN_SCRIPTING>{LNUM} 
{
    char *end;
    //首先检查一下当前的字符串是否超出C语言的long类型长度，如果不超过，直接接调用strtol把字符串转换成long int类型
    if (yyleng < MAX_LENGTH_OF_LONG - 1) 
    { 
        /* Won't overflow */
        errno = 0;
        ZVAL_LONG(zendlval, ZEND_STRTOL(yytext, &end, 0));
        /* This isn't an assert, we need to ensure 019 isn't valid octal
         * Because the lexing itself doesn't do that for us
         */
        if (end != yytext + yyleng) 
        {
            zend_error_noreturn(E_COMPILE_ERROR, "Invalid numeric literal");
        }
        ZEND_ASSERT(!errno);
    } 
    else 
    {
        errno = 0;
        ZVAL_LONG(zendlval, ZEND_STRTOL(yytext, &end, 0));
        //如果超出了long的范围，Zend还是尝试看看能不能转，如果发生溢出（error == ERANGE）那就把当前数字转成double类型
        if (errno == ERANGE) 
        { 
            /* Overflow */
            errno = 0;
            if (yytext[0] == '0')
            { 
                /* octal overflow */
                errno = 0;
                ZVAL_DOUBLE(zendlval, zend_oct_strtod(yytext, (const char **)&end));
            } 
            else 
            {
                ZVAL_DOUBLE(zendlval, zend_strtod(yytext, (const char **)&end));
            }
            /* Also not an assert for the same reason */
            if (end != yytext + yyleng) 
            {
                zend_error_noreturn(E_COMPILE_ERROR, "Invalid numeric literal");
            }
            ZEND_ASSERT(!errno);
            return T_DNUMBER;
        }
        /* Also not an assert for the same reason */
        if (end != yytext + yyleng) 
        {
            zend_error_noreturn(E_COMPILE_ERROR, "Invalid numeric literal");
        }
        ZEND_ASSERT(!errno);
    }
    return T_LNUMBER;
}

PHP变量类型，PHP的变量是以美元符$开头，从词法规则里边可以看到

//$var->prop
<ST_DOUBLE_QUOTES,ST_HEREDOC,ST_BACKQUOTE>"$"{LABEL}"->"[a-zA-Z_\x7f-\xff] {
    yyless(yyleng - 3);
    yy_push_state(ST_LOOKING_FOR_PROPERTY);
    zend_copy_value(zendlval, (yytext+1), (yyleng-1));
    return T_VARIABLE;
}

/* A [ always designates a variable offset, regardless of what follows
 */
//$var["key"]
<ST_DOUBLE_QUOTES,ST_HEREDOC,ST_BACKQUOTE>"$"{LABEL}"[" {
    yyless(yyleng - 1);
    yy_push_state(ST_VAR_OFFSET);
    zend_copy_value(zendlval, (yytext+1), (yyleng-1));
    return T_VARIABLE;
}
//$var
<ST_IN_SCRIPTING,ST_DOUBLE_QUOTES,ST_HEREDOC,ST_BACKQUOTE,ST_VAR_OFFSET>"$"{LABEL} {
    zend_copy_value(zendlval, (yytext+1), (yyleng-1));
    return T_VARIABLE;
}

有三种变量的声明调用方式，$var, $var->prop, $var["key"]，接着，通过zend_copy_value拷贝变量名到zendlval里边记录起来供之后语法解析阶段插入到符号表里边去

PHP的字符串类型在词法分析阶段应该是最复杂的，PHP里边的字符串可以由"单引号"或"双引号"来围住，单引号的字符串比双引号的字符串效率会更高

<ST_IN_SCRIPTING>b?['] 
{
    register char *s, *t;
    char *end;
    int bprefix = (yytext[0] != '\'') ? 1 : 0;

    while (1) 
    {
        if (YYCURSOR < YYLIMIT) 
        {
            if (*YYCURSOR == '\'') 
            {
                YYCURSOR++;
                yyleng = YYCURSOR - SCNG(yy_text);

                break;
            } 
            else if (*YYCURSOR++ == '\\' && YYCURSOR < YYLIMIT) 
            {
                //YYCURSOR++的目的就是为了跳过下一个字符，例如：'\''，如果不跳过第二个单引号的话，我们扫描到第二个引号就会认为字符串结束了
                YYCURSOR++;
            }
        } 
        else 
        {
            yyleng = YYLIMIT - SCNG(yy_text);

            /* Unclosed single quotes; treat similar to double quotes, but without a separate token
             * for ' (unrecognized by parser), instead of old flex fallback to "Unexpected character..."
             * rule, which continued in ST_IN_SCRIPTING state after the quote */
            ZVAL_NULL(zendlval);
            //从输入流中取出字符串的内容，返回一个T_CONSTANT_ENCAPSED_STRING的Token标志
            return T_ENCAPSED_AND_WHITESPACE;
        }
    }

    ZVAL_STRINGL(zendlval, yytext+bprefix+1, yyleng-bprefix-2);

    /* convert escape sequences */
    s = t = Z_STRVAL_P(zendlval);
    end = s+Z_STRLEN_P(zendlval);
    while (s<end) {
        if (*s=='\\') {
            s++;

            switch(*s) {
                case '\\':
                case '\'':
                    *t++ = *s;
                    Z_STRLEN_P(zendlval)--;
                    break;
                default:
                    *t++ = '\\';
                    *t++ = *s;
                    break;
            }
        } else {
            *t++ = *s;
        }

        if (*s == '\n' || (*s == '\r' && (*(s+1) != '\n'))) {
            CG(zend_lineno)++;
        }
        s++;
    }
    *t = 0;

    if (SCNG(output_filter)) {
        size_t sz = 0;
        char *str = NULL;
        s = Z_STRVAL_P(zendlval);
        // TODO: avoid reallocation ???
        SCNG(output_filter)((unsigned char **)&str, &sz, (unsigned char *)s, (size_t)Z_STRLEN_P(zendlval));
        ZVAL_STRINGL(zendlval, str, sz);
    }
    return T_CONSTANT_ENCAPSED_STRING;
}

双引号的字符串处理就复杂一点

<ST_IN_SCRIPTING>b?["] 
{
    int bprefix = (yytext[0] != '"') ? 1 : 0;

    while (YYCURSOR < YYLIMIT) 
    {
        switch (*YYCURSOR++) 
        {
            //如果双引号字符串里边没有变量，直接就返回一个字符串了，从这里看出，其实双引号字符串在没有包含$的情况下的效率跟单引号字符串是差不多的
            case '"':
                yyleng = YYCURSOR - SCNG(yy_text);
                zend_scan_escape_string(zendlval, yytext+bprefix+1, yyleng-bprefix-2, '"');
                return T_CONSTANT_ENCAPSED_STRING;
            //双引号里边是支持变量的！$hello = "Hello"; $str = "${hello} World";
            case '$':
                if (IS_LABEL_START(*YYCURSOR) || *YYCURSOR == '{') {
                    break;
                }
                continue;
            case '{':
                if (*YYCURSOR == '$') {
                    break;
                }
                continue;
            case '\\':
                if (YYCURSOR < YYLIMIT) {
                    YYCURSOR++;
                }
                /* fall through */
            default:
                continue;
        }

        YYCURSOR--;
        break;
    }

    /* Remember how much was scanned to save rescanning */
    //如果遇到了变量！这个时候就要切换到ST_DOUBLE_QUOTES状态了
    SET_DOUBLE_QUOTES_SCANNED_LENGTH(YYCURSOR - SCNG(yy_text) - yyleng);

    YYCURSOR = SCNG(yy_text) + yyleng;

    BEGIN(ST_DOUBLE_QUOTES);
    return '"';
}

PHP魔术变量分为"编译时替换"以及"运行时替换"

<ST_IN_SCRIPTING>"__CLASS__" {
    return T_CLASS_C;
}

<ST_IN_SCRIPTING>"__TRAIT__" {
    return T_TRAIT_C;
}

<ST_IN_SCRIPTING>"__FUNCTION__" {
    return T_FUNC_C;
}

<ST_IN_SCRIPTING>"__METHOD__" {
    return T_METHOD_C;
}

<ST_IN_SCRIPTING>"__LINE__" {
    return T_LINE;
}

<ST_IN_SCRIPTING>"__FILE__" {
    return T_FILE;
}

<ST_IN_SCRIPTING>"__DIR__" {
    return T_DIR;
}

<ST_IN_SCRIPTING>"__NAMESPACE__" {
    return T_NS_C;
}

PHP的容错机制

<ST_LOOKING_FOR_VARNAME>{ANY_CHAR} 
{
    yyless(0);
    yy_pop_state();
    yy_push_state(ST_IN_SCRIPTING);
    goto restart;
}

<ST_IN_SCRIPTING,ST_VAR_OFFSET>{ANY_CHAR} 
{
    if (YYCURSOR > YYLIMIT) {
        return 0;
    }

    zend_error(E_COMPILE_WARNING,"Unexpected character in input:  '%c' (ASCII=%d) state=%d", yytext[0], yytext[0], YYSTATE);
    goto restart;
}

Relevant Link: 

http://blog.csdn.net/hguisu/article/details/7490027
http://sourceforge.net/projects/re2c/
http://sourceforge.net/projects/re2c/files/re2c/
http://re2c.org/
http://www.phppan.com/2011/09/php-lexical-re2c/#comment-4699 
http://re2c.org/manual.html
http://www.secoff.net/archives/331.html
http://blog.csdn.net/raphealguo/article/details/16941531

 

11. 语法分析

在设计语言时，每种程序设计语言都有一组精确的规则来描述良构(well-formed)程序的语法结构。程序设计语言构造的语法可以使用"上下文无关文法"、或者"BNF范式"表示法来描述。文法为语言设计者和编译器编写者都提供了很大的便利

1. 文法给出了一个程序设计语言的精确易懂的语法规约
2. 对于某些类型的文法，我们可以自动地构造出高效的语法分析器，它能够确定一个源程序的语法结构。同时，语法分析器的构造过程可以揭示出语法的二义性，同时很可能发现一些容易在语言的初始设计阶段被忽略的问题
3. 一个正确设计的文法给出了一个语言的结构，该结构有助于把源程序翻译为正确的目标代码，也有助于检测错误
4. 一个文法支持逐步加入可以完成新任务的新语言构造从而迭代地演化和开发语言

0x1: 引论

1. 语法分析器的作用

在我们的编译器模型中，语法分析器从词法分析器获得一个由词法单元组成的串，并验证这个串可以由源语言的文法生成，对于良构的程序，语法分析器构造出一棵语法分析树，并把它传递给编译器的其他部分进一步处理，实际上，并不需要显示地构造出这课语法分析树，这仅仅是在内存中的一个数据结构
处理文法的语法分析器大体上可以分为几种类型

1. 通用型
2. 自顶向下: 从语法分析树的顶部(根节点)开始向底部(叶子结点)构造语法分析树
3. 自底向上: 从叶子结点开始，逐渐向根节点方向构造
//这两种分析方法中，语法分析器的输入总是按照从左到右的方式被扫描，每次扫描一个符号

2. 代表性的文法

下面的文法指明了运算符的结合性和优先级

E -> E + T | T
//E表示一组以+号分隔的项所组成的表达式

T -> T * F | F
//T表示由一组以*分隔的因子所组成的项

F -> (E) | id
//F表示因子，它可能是括号括起来的表达式，也可能是标识符

3. 语法错误的处理

程序可能有不同层次的错误

1. 词法错误
    1) 标识符、关键字、运算符拼写错误
    2) 没有在字符串文本上正确地加上引号
2. 语法错误
    1) 分号放错地方
    2) 花括号多余或缺失
3. 语义错误
    1) 运算符和运算分量之间的类型不匹配，例如，返回类型为void的某个方法中出现了一个返回某个int值的return语句
4. 逻辑错误
    1) 可以是因程序员的错误推理而引起的任何错误，比如在一个C程序中应该使用比较运算符==的地方使用了赋值运算符=，这样的程序可能是良构的，但是却没有正确反映出程序员的意图

语法分析方法的精确性使得我们可以非常高效地检测出语法错误，有些语法分析方法，比如LL和LR方法，能够在第一时间发现错误。也就是说，当来自词法分析器的词法单元流不能根据该语言的文法进一步分析时就会发现错误，更精确地讲，它们具有"可行前缀特性(viable-prefix property)"，也就是说，一旦发现输入的某个前缀不能通过添加一些符号而形成这个语言的串，就可以立刻检测到语法错误

4. 错误恢复策略

1. 恐慌模式的恢复 
2. 短语层次的恢复
3. 错误产生式
4. 全局纠正

0x2: 上下文无关文法

1. 上下文无关文法的正式定义

一个上下文无关文法由以下元素组成

1. 终结符号: 组成串的基本符号，"词法单元名字"和"终结符号"是同义词，因为在大多数编程语言中，终结符号就是一个独立的词法单元
2. 非终结符号: 表示串的集合的语法变量，非终结符号表示的串集合用于定义由文法生成的语言。非终结符号给出了语言的层次结构，而这种层次结构是语法分析和翻译的关键
3. 在一个文法中，某个非终结符号被指定为开始符号，这个符号表示的串集合就是这个文法生成的语言
4. 一个文法的产生式描述了将终结符号和非终结符号组合成串的方法，每个产生式由下列元素组成
    1) 一个被称为产生式头或左部的非终结符号，这个产生式定义了这个头所代表的串集合的一部分
    2) 符号->，有时也使用::=来替代箭头
    3) 一个由零头或多个终结符号与非终结符号组合的产生式体或右部。产生式体中的成分描述了产生式头上的非终结符号所对应的串的某个构造方法

2. 符号表示的约定

3. 推导

将产生式看作重写规则，就可以从推导的角度精确地描述构造语法分析树的方法，从开始符号出发，每个重写步骤把一个非终结符号替换为它的某个产生式的体，这个推导思想对应于自顶向下构造语法分析树的过程，但是推导概念所给出的精确性在自底向上的语法分析过程中尤其有用 

4. 语法分析树和推导

语法分析树是推导的图形表示形式，它过滤掉了推导过程中对非终结符号应用产生式的顺序，语法分析树的每个内部结点表示一个产生式的应用，该内部结点的标号是此产生式头中的非终结符号A，这个结点的子节点的标号从左到右组成了在推导过程中替换这个A的产生式体
一棵语法分析树的叶子结点的标号既可以是非终结符号，也可以是终结符号，从左到右排列这些符号就可以得到一个句型，它称为这棵树的结果(yield)或边缘(frontier)

5. 二义性

如果一个文法可以为某个句子生成多课语法分析树，那么它就是二义性(ambiguous)，换句话说，二义性文法就是对同一个句子有多个最左推导或多个最右推导文法

6. 验证文法生成的语言

验证文法G生成语言L的过程可以分成两个部分

1. 证明G生成的每个串都在L中
2. 并且反向证明L中的每个串都确实能由G生成

7. 上下文无关文法和正则表达式

需要明白的是，文法是比正则表达式表达能力更强的表示方法，每个可能使用正则表达式描述的构造都可以使用文法来描述，但是反之不成立。换句话说，每个正则语言都是一个上下文无关语言，但是反之不成立

0x3: 设计文法

文法能够描述程序设计语言的大部分(但不是全部)语法，比如，在程序中标识符必须先声明后使用，但是这个要求不能通过一个上下文无关文法来描述。因此，一个词法分析器接受的词法单元序列构成了程序设计语言的超集。编译器的后续步骤必须对语法分析器的输出进行分析，以保证源程序遵守那些没有被语法分析器检查的规则

1. 词法分析和语法分析

我们知道，任何能够使用正则表达式描述的语言都可以使用文法描述，但是，为什么lex/flex/re2c这些词法解析器都使用正则表达式来定义一个语言的词法语法，理由有以下几个

1. 将一个语言的语法结构分为词法和非词法两部分可以很方便地将编译器前端模块化，将前端分解为两个大小适中的组件
2. 一个语言的词法规则通常很简单，我们不需要使用像文法这样的功能强大且复杂的表示方法来描述这些规则
3. 和文法相比，正则表达式通常提供了更加简洁且易于理解的表示词法单元的方法(易于编写)
4. 根据正则表达式自动构造得到的词法分析器的效率要高于根据任意文法自动构造得到的分析器

原则上，并不存在一个严格的制导方针来规定哪些东西应该放到词法规则中，正则表达式最适合描述诸如标识符、常量、关键字、空白这样的语言构造的结构，另一方面，文法最适合描述嵌套结构，比如对称的括号对，匹配的begin-end、相互对应的if-then-else等，这些嵌套结构不能使用正则表达式描述

2. 消除二义性

一个二义性文法可以被改写为无二义性的文法

3. 左递归的消除

如果一个文法中有一个非终结符号A使得对某个串a存在一个推导A => Aa，那么这个文法就是左递归的(left rescursive)，自顶向下语法分析方法不能处理左递归的文法，因此需要一个转换方法来消除左递归，同时，这样的替换不能改变可从A推导得到的串的集合

4. 提取左公因子

提取左公因子是一种文法转换方法，它可以产生适用于预测分析技术或自顶向下分析技术的文法。当不清楚应该在两个A产生式中如何选择时，我们可以通过改写产生式来推后这个决定，等我们读入了足够多的输入，获得足够信息后再做出正确选择

5. 非上下文无关语言的构造

0x4: 自顶向下的语法分析

自顶向下语法分析可以被看作是为输入串构造语法分析树的问题，它从语法分析树的根节点开始，按照先根次序(深度优先)创建这课语法分析树的各个结点，自顶向下语法分析也可以被看作寻找输入串的最左推导的过程
在一个自顶向下语法分析的每一步中，关键问题是确定对一个非终结符号(例如A)应用哪个产生式，一旦选择了某个A产生式，语法分析过程的其余部分负责将相应产生式体中的终结符号和输入相匹配

1. 递归下降的语法分析

一个递归下降语法分析程序由一组过程组成，每个非终结符号有一个对应的过程(产生式翻译过程)，程序的执行从开始符号对应的过程开始，如果这个过程的过程体扫描了整个输入串，它就停止执行并宣布语法分析成功完成

void A()
{
    选择一个A产生式, A -> X1X2..Xk;
    for(i = 1 to k)
    {
        if(Xi是一个非终结符号)
            调用过程Xi();
        else if(Xi等于当前的输入符号a)
            读入下一个输入符号;
        else /*发生了一个错误*/
    }
}

通用的递归下降分析技术可能需要回溯，也就是说，它可能需要重复扫描输入，然而，在对程序设计语言的构造进行语法分析时很少需要回溯，因此需要回溯的语法分析器并不常见，即使在自然语言语法分析这样的场合，回溯也不是很高效，因此我们更倾向于基于表格的方法，例如动态程序规划算法或者Earley方法

2. FIRST和FOLLOW

自顶向下和自底向上语法分析器的构造可以使用和文法G相关的两个函数FIRST和FOLLOW来实现。在自顶向下语法分析过程中，FIRST和FOLLOW使得我们可以根据下一个输入符号来选择应用哪个产生式。在恐慌模式的错误恢复中，由FOLLOW产生的词法单元集合可以作为同步词法单元
计算各个文法符号X的FIRST(X)时，不断应用下列规则，直到再没有新的终结符号或e可以被加入到任何FIRST集合中为止

1. 如果X是一个终结符号，那么FIRST(X) = X
2. 如果X是一个非终结符号，且X -> Y1Y2...Yk是一个产生式，其中k >= 1，那么如果对于某个i、a在FIRST(Yi)中且e在所有的FIRST(Y1)、FIRST(Y2)...FIRST(Yi-1)中，就把a加入到FIRST(X)中
3. 如果X -> e是一个产生式，那么将e加入到FIRST(X)中

3. LL(1)文法

对于称为LL(1)的文法，我们可以构造出预测分析器，即不需要回溯的递归下降语法分析器，LL(1)中的第一个"L"表示从左向右扫描输入，第二个"L"表示最左推导，而"1"则表示在每一步中只需要向前看一个输入符号来决定语法分析动作 

4. 非递归的预测分析

我们可以构造出一个非递归的预测分析器，它显式地维护一个栈结构，而不是通过递归调用的方式隐式地维护栈。这样的语法分析器可以模拟最左推导的过程

0x5: 自底向上的语法分析

一个自底向上的语法分析过程对应于为一个输入串构造语法分析树的过程，它从叶子结点(底部)开始逐渐向上到达根节点(顶部)

1. 规约

我们可以将自底向上语法分析过程看成一个串w"规约"为文法开始符号的过程，在每个规约(reduction)步骤中，一个与某产生式体相匹配的特定子串被替换为该产生式头部的非终结符号
在自底向上语法分析过程中，关键问题是何时进行规约以及应用哪个产生式进行规约

2. 句柄剪枝

3. 移入-规约语法分析技术

移入-规约语法分析是自底向上语法分析的一种形式，它使用一个栈来保存文法符号，并用一个输入缓冲区来存放将要进行语法分析的其余符号，句柄在被识别之前，总是出现在栈的顶部

0x6: LR语法分析技术

0x7: 更强大的LR语法分析器

0x8: 使用二义性文法

0x9: 语法分析器生成工具

我们接下来使用语法分析器生成工具来构造一个编译器的前端，它们使用LALR语法分析器生成工具Yacc

1. 语法分析器生成工具Yacc

一个Yacc源程序由三个部分组成

/*
一个Yacc程序的声明部分分为以下几个部分，它们都是可选
1. 通常的C声明
2. 翻译过程中使用的临时变量
3. 对词法单元的声明: 如果向Yacc语法分析器传送词法单元的词法分析器是使用Lex创建的，则Lex生成的词法分析器也可以使用这里声明的词法单元
*/
声明

%%
/*
每个规则由一个文法产生式和一个相关联的语义动作组成
产生式头: <产生式体>1 { <语义动作>1 }
| <产生式体>2 { <语义动作>2 }
..
| <产生式体>n { <语义动作>n }

1. 在一个Yacc产生式中，如果一个由字母和数字组成的字符串没有加引号且未被声明为词法单元，它就会被当作非终结符号处理。带引号的单个字符，比如'c'，会被当作终结符号c以及它所代表的词法单元所对应的整数编码(即Lex将把'c'的字符编码当作整数返回给词法分析器)
2. 不同的产生式体用竖线分开，每个产生式头以及它的可选产生式体及语义动作之后跟一个分号
3. 第一个产生式的头符号被看作开始符号
4. 一个Yacc语义动作是一个C语言的序列
*/
翻译规则
%%

/*
1. 这里必须提供一个名为yylex()的词法分析器(框架规约)，用Lex来生成yylex()是一个常用的选择
2. 词法分析器yylex()返回一个由词法单元名和相关属性值组成的词法单元。如果要返回一个词法单元名字，比如DIGIT，那么这个名字必须先在Yacc规约的第一部分进行声明
3. 一个词法单元的相关属性值通过一个Yacc定义的变量yylval传送给语法分析器
*/
辅助性C语言例程

2. 使用带有二义性文法的Yacc规约

除非另行指定，否则Yacc会使用下面的两个规则来解决所有的语法分析动作冲突

1. 解决一个归约/归约冲突时，选择在Yacc规约中列在前面的那个冲突产生式
2. 解决移入/规约冲突时总是选择移入，这个规则正确地解决了因为悬空else二义性而产生的移入/归约冲突
3. 词法单元的优先级是根据它们在声明部分的出现顺序而定的，优先级最低的词法单元最先出现。同一个声明中的词法单元具有相同的优先级

3. 用Lex创建Yacc的词法分析器

Lex的作用是生成可以和Yacc一起使用的词法分析器。Lex库ll将提供一个名为yylex()的驱动程序。Yacc要求它的词法分析器的名字为yylex()，如果用Lex来生成词法分析器，那么我们可以将Yacc规约的第三部分的例程yylex()替换为语句: #include "lex.yy.c"
并令每个Lex动作都返回Yacc已知的终结符号，通过使用语句#include "lex.yy.c"，程序yylex能够访问Yacc定义的词法单元名字，因为Lex的输出文件是作为Yacc的输出文件y.tab.c的一部分被编译的

4. Yacc中的错误恢复

Yacc的错误恢复使用了错误产生式的形式

Relevant Link:

https://github.com/luapower/lexer/tree/master/media/lexers 

 

12. 构造可配置词法语法分析器生成器

源程序在被编译为目标程序需要经过如下6个过程：词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成。词法分析和语法分析是编译过程的初始阶段，是编译器的重要组成部分，早期相关理论和工具缺乏的环境下，编写词法语法分析器是很繁琐的事情。上世纪70年代，贝尔实验室的M. E. Lesk，E. Schmidt和Stephen C. Johnson分别为Unix系统编写了词法分析器生成器Lex和语法分析器生成器Yacc，Lex接受由正则表达式定义的词法规则，Yacc接受由BNF范式描述的文法规则，它们能够自动生成分析对应词法和语法规则的C源程序，其强大的功能和灵活的特性很大程度上简化了词法分析和语法分析的构造难度。如今Lex和Yacc已经成为著名的Unix标准内置工具(Linux下对应的工具是Flex和Bison)，并被广泛用于编译器前端构造，它已经帮助人们实现了数百种语言的编译器前端，比较著名的应用如mysql的SQL解析器，PHP，Ruby，Python等脚本语言的解释引擎，浏览器内核Webkit，早期的GCC等。本文将介绍可配置词法分析器和语法分析器生成器的内部原理

Relevant Link:

http://blog.csdn.net/xinghongduo/article/details/39455543
http://blog.csdn.net/xinghongduo/article/details/39505193
http://blog.csdn.net/xinghongduo/article/details/39529165 

 

13. 基于PHP Lexer重写一份轻量级词法分析器

我们以PHP命令行模式为切入点，理解PHP从接收输入到词法分析的全过程

D:\wamp\bin\php\php5.5.12\php.exe -f test.php
//执行文件

$PHPSRC/sapi/cli/php_cli.c

..
case 'f': /* parse file */
if (behavior == PHP_MODE_CLI_DIRECT || behavior == PHP_MODE_PROCESS_STDIN) 
{
    param_error = param_mode_conflict;
    break;
} 
else if (script_file) 
{
    param_error = "You can use -f only once.\n";
    break;
}
script_file = php_optarg;
break;
..
case PHP_MODE_STANDARD:
if (strcmp(file_handle.filename, "-")) {
    cli_register_file_handles();
}

if (interactive && cli_shell_callbacks.cli_shell_run) {
    exit_status = cli_shell_callbacks.cli_shell_run();
} else {
    php_execute_script(&file_handle);
    exit_status = EG(exit_status);
}
break;
..

php_execute_script(&file_handle);    
$PHPSRC/main/main.c

PHPAPI int php_execute_script(zend_file_handle *primary_file)
{
    zend_file_handle *prepend_file_p, *append_file_p;
    zend_file_handle prepend_file = {{0}, NULL, NULL, 0, 0}, append_file = {{0}, NULL, NULL, 0, 0};
    ..
    if (CG(start_lineno) && prepend_file_p) {
            int orig_start_lineno = CG(start_lineno);

            CG(start_lineno) = 0;
            if (zend_execute_scripts(ZEND_REQUIRE, NULL, 1, prepend_file_p) == SUCCESS) {
                CG(start_lineno) = orig_start_lineno;
                retval = (zend_execute_scripts(ZEND_REQUIRE, NULL, 2, primary_file, append_file_p) == SUCCESS);
            }
        } else {
            retval = (zend_execute_scripts(ZEND_REQUIRE, NULL, 3, prepend_file_p, primary_file, append_file_p) == SUCCESS);
        }
        ..

zend_execute_scripts()
Zend/Zend.c

ZEND_API int zend_execute_scripts(int type, zval *retval, int file_count, ...) /* {{{ */
{
    va_list files;
    int i;
    zend_file_handle *file_handle;
    zend_op_array *op_array;

    va_start(files, file_count);
    for (i = 0; i < file_count; i++) {
        file_handle = va_arg(files, zend_file_handle *);
        if (!file_handle) {
            continue;
        }
        
        //通过zend_compile_file把文件解析成opcode中间代码(这一步会经过词法语法分析)
        op_array = zend_compile_file(file_handle, type);
        if (file_handle->opened_path) {
            zend_hash_add_empty_element(&EG(included_files), file_handle->opened_path);
        }
        zend_destroy_file_handle(file_handle);
        if (op_array) {
            //用zend_execute执行这个生成的中间代码
            zend_execute(op_array, retval);
            ..

接下来是opcode的生成和zend虚拟机对opcode的执行流程，我们留待之后深入研究，我们回到PHP的语法高亮过程，聚焦PHP的词法分析

D:\wamp\bin\php\php5.5.12\php.exe -s test.php
//PHP的词法解析过程通过文件操作完成，通过指针移动，逐个从文件中抽取出一个"状态机匹配命中Token"，然后输出给语法分析器，在语法高亮逻辑这里，语法分析器就是一个HTML高亮显示器，并没有做多余的语法分析

$PHPSRC/sapi/cli/php_cli.c

..
case 's': /* generate highlighted HTML from source */
if (behavior == PHP_MODE_CLI_DIRECT || behavior == PHP_MODE_PROCESS_STDIN) 
{
    param_error = "Source highlighting only works for files.\n";
    break;
}
behavior=PHP_MODE_HIGHLIGHT;
break;
..
case PHP_MODE_HIGHLIGHT:
{
    zend_syntax_highlighter_ini syntax_highlighter_ini;

    if (open_file_for_scanning(&file_handle)==SUCCESS) {
        php_get_highlight_struct(&syntax_highlighter_ini);
        zend_highlight(&syntax_highlighter_ini);
    }
    goto out;
}
break;
..

我们接下里从PHP打开待执行文件、词法解析、返回Token词素几个部分逐步理解PHP的词法分析过程

0x1: PHP打开待执行文件

..
zend_file_handle file_handle;
..
open_file_for_scanning(&file_handle)
..

1. Zend引擎的全局宏定义

1. CG宏
本宏关联的数据结构定义为_zend_compiler_globals. 宏中包含了以下主要数据，这些数据都是在Zend解释PHP代码过程中定义 
    1) function_table: 定义的函数的符号表
    2) class_table: 定义的类的符号表
    3) filenames_table: 文件名列表，是PHP Zend引擎打开的文件
    4) autoglobals: 自动全局变量符号表,这个表存放了超全局变量，比如$SESSION, $GLOBALS之类的
/* 
#define CG(v) (compiler_globals.v) 
extern ZEND_API struct _zend_compiler_globals compiler_globals;
*/

2. EG宏
本宏关联的数据结构定义为_zend_executor_globals. 宏中包含了以下主要数据 
    1) included_files: 包含的文件列表
    2) function_table: 执行过程中定义的函数符号表
    3) class_table: 定义的类的符号表
    4) zend_constants: 定义的常量表
    5) ini_directives: ini文件定义信息
    6) modifiedinidirectives: 更新后的ini定义信息
    7) symbol_table: 变量符号表
/*
# define EG(v) (executor_globals.v) 
extern zend_executor_globals executor_globals; 
*/

3. LANG_SCNG宏
/*
# define LANG_SCNG(v) (language_scanner_globals.v) 
extern zend_php_scanner_globals language_scanner_globals; 
*/

4. INI_SCNG宏
/*
# define INI_SCNG(v) (ini_scanner_globals.v)  
extern zend_ini_scanner_globals ini_scanner_globals; 
*/

5. TSRMG宏

6. PG宏
main/php_globals.h:
# define PG(v) TSRMG(core_globals_id, php_core_globals *, v)

7. SG宏
main/SAPI.h:
# define SG(v) TSRMG(sapi_globals_id, sapi_globals_struct *, v)
//SG宏主要用于获取SAPI层范围内的全局变量 

PHP内核代码中大量使用了全局变量和extern修饰符，全局变量的赋值和使用贯穿了脚本编译、中间代码执行、运行时整个生命周期，同时值得注意的是，之所以在PHP代码中能够使用$GLOBAL、$SESSION这样的超全局变量，也得益于PHP内核中全局变量的使用

2. 全局宏定义对应的数据结构

struct _zend_compiler_globals 
{
    zend_stack loop_var_stack;

    zend_class_entry *active_class_entry;

    zend_string *compiled_filename;

    int zend_lineno;

    zend_op_array *active_op_array;

    HashTable *function_table;    /* function symbol table */
    HashTable *class_table;        /* class table */

    HashTable filenames_table;

    HashTable *auto_globals;

    zend_bool parse_error;
    zend_bool in_compilation;
    zend_bool short_tags;

    zend_declarables declarables;

    zend_bool unclean_shutdown;

    zend_bool ini_parser_unbuffered_errors;

    zend_llist open_files;

    struct _zend_ini_parser_param *ini_parser_param;

    uint32_t start_lineno;
    zend_bool increment_lineno;

    znode implementing_class;

    zend_string *doc_comment;

    uint32_t compiler_options; /* set of ZEND_COMPILE_* constants */

    zend_string *current_namespace;
    HashTable *current_import;
    HashTable *current_import_function;
    HashTable *current_import_const;
    zend_bool  in_namespace;
    zend_bool  has_bracketed_namespaces;

    HashTable const_filenames;

    zend_compiler_context context;
    zend_stack context_stack;

    zend_arena *arena;

    zend_string *empty_string;
    zend_string *one_char_string[256];

    HashTable interned_strings;

    const zend_encoding **script_encoding_list;
    size_t script_encoding_list_size;
    zend_bool multibyte;
    zend_bool detect_unicode;
    zend_bool encoding_declared;

    zend_ast *ast;
    zend_arena *ast_arena;

    zend_stack delayed_oplines_stack;
};


struct _zend_executor_globals 
{
    zval uninitialized_zval;
    zval error_zval;

    /* symbol table cache */
    zend_array *symtable_cache[SYMTABLE_CACHE_SIZE];
    zend_array **symtable_cache_limit;
    zend_array **symtable_cache_ptr;

    zend_array symbol_table;        /* main symbol table */

    HashTable included_files;    /* files already included */

    JMP_BUF *bailout;

    int error_reporting;
    int exit_status;

    HashTable *function_table;    /* function symbol table */
    HashTable *class_table;        /* class table */
    HashTable *zend_constants;    /* constants table */

    zval          *vm_stack_top;
    zval          *vm_stack_end;
    zend_vm_stack  vm_stack;

    struct _zend_execute_data *current_execute_data;
    zend_class_entry *scope;

    zend_long precision;

    int ticks_count;

    HashTable *in_autoload;
    zend_function *autoload_func;
    zend_bool full_tables_cleanup;

    /* for extended information support */
    zend_bool no_extensions;

#ifdef ZEND_WIN32
    zend_bool timed_out;
    OSVERSIONINFOEX windows_version_info;
#endif

    HashTable regular_list;
    HashTable persistent_list;

    int user_error_handler_error_reporting;
    zval user_error_handler;
    zval user_exception_handler;
    zend_stack user_error_handlers_error_reporting;
    zend_stack user_error_handlers;
    zend_stack user_exception_handlers;

    zend_error_handling_t  error_handling;
    zend_class_entry      *exception_class;

    /* timeout support */
    zend_long timeout_seconds;

    int lambda_count;

    HashTable *ini_directives;
    HashTable *modified_ini_directives;
    zend_ini_entry *error_reporting_ini_entry;

    //zend_objects_store objects_store;
    //zend_object *exception, *prev_exception;
    const zend_op *opline_before_exception;
    zend_op exception_op[3];

    struct _zend_module_entry *current_module;

    zend_bool active;
    zend_bool valid_symbol_table;

    zend_long assertions;

    uint32_t           ht_iterators_count;     /* number of allocatd slots */
    uint32_t           ht_iterators_used;      /* number of used slots */
    HashTableIterator *ht_iterators;
    HashTableIterator  ht_iterators_slots[16];

    void *saved_fpu_cw_ptr;
#if XPFPA_HAVE_CW
    XPFPA_CW_DATATYPE saved_fpu_cw;
#endif

    void *reserved[ZEND_MAX_RESERVED_RESOURCES];
};

struct _zend_ini_scanner_globals {
    zend_file_handle *yy_in;
    zend_file_handle *yy_out;

    unsigned int yy_leng;
    unsigned char *yy_start;
    unsigned char *yy_text;
    unsigned char *yy_cursor;
    unsigned char *yy_marker;
    unsigned char *yy_limit;
    int yy_state;
    zend_stack state_stack;

    char *filename;
    int lineno;

    /* Modes are: ZEND_INI_SCANNER_NORMAL, ZEND_INI_SCANNER_RAW, ZEND_INI_SCANNER_TYPED */
    int scanner_mode;
};

struct _zend_php_scanner_globals 
{
    zend_file_handle *yy_in;
    zend_file_handle *yy_out;

    unsigned int yy_leng;
    unsigned char *yy_start;
    unsigned char *yy_text;
    unsigned char *yy_cursor;
    unsigned char *yy_marker;
    unsigned char *yy_limit;
    int yy_state;
    zend_stack state_stack;
    zend_ptr_stack heredoc_label_stack;

    /* original (unfiltered) script */
    unsigned char *script_org;
    size_t script_org_size;

    /* filtered script */
    unsigned char *script_filtered;
    size_t script_filtered_size;

    /* input/output filters */
    zend_encoding_filter input_filter;
    zend_encoding_filter output_filter;
    const zend_encoding *script_encoding;

    /* initial string length after scanning to first variable */
    int scanned_string_len;
};

3. PHP ZVAL结构体

1. PHP是一门动态的弱类型语言
2. PHP的写机制里会使用内存处理的引用计数的复本 
3. PHP变量，通常来说，由两部分组成：标签(例如，可能是符号表中的一个条目)和实际变量容器 
4. 变量容器，在代码中称为zval，掌握了所需处理变量的所有数据。包括
    1) 实际值
    2) 当前类型
    3) 统计指向此容器的标签的数量
    4) 指示这些标签是引用还是副本的标志 

注意到zval_struct->zend_value value成员，它是一个联合体

typedef union _zend_value {
    zend_long         lval;                /* long value */
    double            dval;                /* double value */
    zend_refcounted  *counted;
    zend_string      *str;
    zend_array       *arr;
    zend_object      *obj;
    zend_resource    *res;
    zend_reference   *ref;
    zend_ast_ref     *ast;
    zval             *zv;
    void             *ptr;
    zend_class_entry *ce;
    zend_function    *func;
    struct {
        ZEND_ENDIAN_LOHI(
            uint32_t w1,
            uint32_t w2)
    } ww;
} zend_value;

PHP是一种若类型语言，通过ZVAL这种变量容器机制，PHP中的变量赋值变得异常灵活，可以将变量赋值为任何东西
注意到PHP对类Class的赋值和保存，我们知道PHP是一种面向对象的开发语言，从内核层面来看，这是因为PHP底层是基于C++/C开发的，PHP的对象最终是通过C++的对象/继承最终是通过C++实现的，所以PHP中声明的对象都从一个基类继承而来，每个类都默认包含了一些"默认函数"

union _zend_function *constructor;
union _zend_function *destructor;
union _zend_function *clone;
union _zend_function *__get;
union _zend_function *__set;
union _zend_function *__unset;
union _zend_function *__isset;
union _zend_function *__call;
union _zend_function *__callstatic;
union _zend_function *__tostring;
union _zend_function *__debugInfo;
union _zend_function *serialize_func;
union _zend_function *unserialize_func;

zend_class_iterator_funcs iterator_funcs;

我们在创建类的时候，可以重载这些函数

4. PHP的变量传递

我们知道，PHP的变量传递是引用传递的，通过ZVAL机制，PHP内核在处理变量传递赋值的时候只是将新变量同样指向被赋值的引用，同时将被赋值的引用计数加1，这在copy_string的实现机制中可以看出来

static zend_always_inline zend_string *zend_string_copy(zend_string *s)
{
    if (!IS_INTERNED(s)) {
        GC_REFCOUNT(s)++;
    }
    return s;
}

5. PHP的哈希表实现
PHP内核中的哈希表是十分重要的数据结构，PHP的大部分的语言特性都是基于哈希表实现的，例如

1. 变量的作用域
2. 函数表
3. 类的属性、方法等
4. Zend引擎内部的很多数据都是保存在哈希表中的 

数据结构及说明

PHP中的哈希表是使用拉链法来解决冲突的，具体点讲就是使用链表来存储哈希到同一个槽位的数据， Zend为了保存数据之间的关系使用了双向列表来链接元素
PHP中的哈希表实现在Zend/zend_hash.c中，PHP使用如下两个数据结构来实现哈希表，HashTable结构体用于保存整个哈希表需要的基本信息， 而Bucket结构体用于保存具体的数据内容

typedef struct _hashtable { 
    uint nTableSize;        // hash Bucket的大小，最小为8，以2x增长。
    uint nTableMask;        // nTableSize-1 ， 索引取值的优化
    uint nNumOfElements;    // hash Bucket中当前存在的元素个数，count()函数会直接返回此值 
    ulong nNextFreeElement; // 下一个数字索引的位置
    Bucket *pInternalPointer;   // 当前遍历的指针（foreach比for快的原因之一）
    Bucket *pListHead;          // 存储数组头元素指针
    Bucket *pListTail;          // 存储数组尾元素指针
    Bucket **arBuckets;         // 存储hash数组
    dtor_func_t pDestructor;    // 在删除元素时执行的回调函数，用于资源的释放
    zend_bool persistent;       //指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。
    unsigned char nApplyCount; // 标记当前hash Bucket被递归访问的次数（防止多次递归）
    zend_bool bApplyProtection;// 标记当前hash桶允许不允许多次访问，不允许时，最多只能递归3次
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

哈希表初始化

ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
{
    uint i = 3;
    //...
    if (nSize >= 0x80000000) {
        /* prevent overflow */
        ht->nTableSize = 0x80000000;
    } else {
        while ((1U << i) < nSize) {
            i++;
        }
        ht->nTableSize = 1 << i;
    }
    // ...
    ht->nTableMask = ht->nTableSize - 1;
 
    /* Uses ecalloc() so that Bucket* == NULL */
    if (persistent) {
        tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket *));
        if (!tmp) {
            return FAILURE;
        }
        ht->arBuckets = tmp;
    } else {
        tmp = (Bucket **) ecalloc_rel(ht->nTableSize, sizeof(Bucket *));
        if (tmp) {
            ht->arBuckets = tmp;
        }
    }
 
    return SUCCESS;
} 

如果设置初始大小为10，则上面的算法将会将大小调整为16。也就是始终将大小调整为接近初始大小的 2的整数次方
mask的作用就是将哈希值映射到槽位所能存储的索引范围内。 例如：某个key的索引值是21， 哈希表的大小为8，则mask为7，则求与时的二进制表示为： 10101 & 111 = 101 也就是十进制的5。 因为2的整数次方-1的二进制比较特殊：后面N位的值都是1，这样比较容易能将值进行映射， 如果是普通数字进行了二进制与之后会影响哈希值的结果。那么哈希函数计算的值的平均分布就可能出现影响
设置好哈希表大小之后就需要为哈希表申请存储数据的空间了，如上面初始化的代码， 根据是否需要持久保存而调用了不同的内存申请方法。如前面PHP生命周期里介绍的,是否需要持久保存体现在：持久内容能在多个请求之间访问，而非持久存储是会在请求结束时释放占用的空间。 具体内容将在内存管理章节中进行介绍HashTable中的nNumOfElements字段很好理解，每插入一个元素或者unset删掉元素时会更新这个字段。 这样在进行count()函数统计数组元素个数时就能快速的返回
nNextFreeElement字段非常有用。先看一段PHP代码

<?php
$a = array(10 => 'Hello');
$a[] = 'TIPI';
var_dump($a);
 
// ouput
array(2) {
  [10]=>
  string(5) "Hello"
  [11]=>
  string(5) "TIPI"
}

PHP中可以不指定索引值向数组中添加元素，这时将默认使用数字作为索引， 和C语言中的枚举类似， 而这个元素的索引到底是多少就由nNextFreeElement字段决定了。 如果数组中存在了数字key，则会默认使用最新使用的key + 1，例如上例中已经存在了10作为key的元素， 这样新插入的默认索引就为11了

数据容器: 槽位

typedef struct bucket {
    ulong h;            // 对char *key进行hash后的值，或者是用户指定的数字索引值
    uint nKeyLength;    // hash关键字的长度，如果数组索引为数字，此值为0
    void *pData;        // 指向value，一般是用户数据的副本，如果是指针数据，则指向pDataPtr
    void *pDataPtr;     //如果是指针数据，此值会指向真正的value，同时上面pData会指向此值
    struct bucket *pListNext;   // 整个hash表的下一元素
    struct bucket *pListLast;   // 整个哈希表该元素的上一个元素
    struct bucket *pNext;       // 存放在同一个hash Bucket内的下一个元素
    struct bucket *pLast;       // 同一个哈希bucket的上一个元素
    // 保存当前值所对于的key字符串，这个字段只能定义在最后，实现变长结构体
    char arKey[1];              
} Bucket;

如上面各字段的注释。h字段保存哈希表key哈希后的值。这里保存的哈希值而不是在哈希表中的索引值，这是因为如下原因

1. 索引值和哈希表的容量有直接关系，如果哈希表扩容了，那么这些索引还得重新进行哈希在进行索引映射，这也是一种优化手段
2. 在PHP中可以使用字符串或者数字作为数组的索引。数字索引直接就可以作为哈希表的索引，数字也无需进行哈希处理。h字段后面的nKeyLength字段是作为key长度的标示， 索引是数字的话，则nKeyLength为0
3. 在PHP数组中如果索引字符串可以被转换成数字也会被转换成数字索引。 所以在PHP中例如'10'，'11'这类的字符索引和数字索引10，11没有区别(但是这里涉及到一个转换约定)

结构体的最后一个字段用来保存key的字符串，而这个字段却申明为只有一个字符的数组， 其实这里是一种长见的变长结构体，主要的目的是增加灵活性。 以下为哈希表插入新元素时申请空间的代码

p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
if (!p) {
    return FAILURE;
}
memcpy(p->arKey, arKey, nKeyLength);

如代码，申请的空间大小加上了字符串key的长度，然后把key拷贝到新申请的空间里。 在后面比如需要进行hash查找的时候就需要对比key这样就可以通过对比p->arKey和查找的key是否一样来进行数据的 查找。申请空间的大小-1是因为结构体内本身的那个字节还是可以使用的
在PHP5.4中将这个字段定义成const char* arKey类型了

1. Bucket结构体维护了两个双向链表，pNext和pLast指针分别指向本槽位所在的链表的关系(HASH冲突拉链法)
2. pListNext和pListLast指针指向的则是整个哈希表所有的数据之间的链接关系。 ashTable结构体中的pListHead和pListTail则维护整个哈希表的头元素指针和最后一个元素的指针 

PHP中数组的操作函数非常多，例如：array_shift()和array_pop()函数，分别从数组的头部和尾部弹出元素。 哈希表中保存了头部和尾部指针，这样在执行这些操作时就能在常数时间内找到目标。 PHP中还有一些使用的相对不那么多的数组操作函数：next()，prev()等的循环中， 哈希表的另外一个指针就能发挥作用了：pInternalPointer，这个用于保存当前哈希表内部的指针。 这在循环时就非常有用

Relevant Link:

http://php.net/manual/zh/internals2.variables.intro.php
http://docstore.mik.ua/orelly/webprog/php/ch14_06.htm
http://php.net/manual/zh/language.oop5.overloading.php
http://www.php-internals.com/book/?p=chapt03/03-01-02-hashtable-in-php
http://segmentfault.com/a/1190000000718519

6. PHP内存池

PHP的内存管理器是分层(hierarchical)的，这个管理器共有三层

1. 存储层(storage)
2. 堆(heap)层
3. emalloc/efree层

存储层(storage)

存储层通过 malloc()、mmap() 等函数向系统真正的申请内存，并通过 free() 函数释放所申请的内存。存储层通常申请的内存块都比较大，这里申请的内存大并不是指storage层结构所需要的内存大，只是堆层通过调用存储层的分配方法时，其以段的格式申请的内存比较大，存储层的作用是将内存分配的方式对堆层透明化

4种内存方案

PHP在存储层共有4种内存分配方案

1. malloc: 默认使用malloc分配内存
2. win32: 如果设置了ZEND_WIN32宏，则为windows版本，调用HeapAlloc分配内存

//剩下两种内存方案为匿名内存映射，并且PHP的内存方案可以通过设置变量来修改
3. mmap_anon: Anonymous Memory Mapping
    1) 匿名内存映射 与 使用 /dev/zero 类型，都不需要真实的文件。要使用匿名映射之需要向 mmap 传入 MAP_ANON 标志，并且 fd 参数 置为 -1  
    2) 所谓匿名，指的是映射区并没有通过 fd 与 文件路径名相关联。匿名内存映射用在有血缘关系的进程间 

4. mmap_zero: /dev/zero Memory Mapping 
    1) 可以将伪设备 "/dev/zero" 作为参数传递给 mmap 而创建一个映射区。/dev/zero 的特殊在于，对于该设备文件所有的读操作都返回值为 0 的指定长度的字节流 ，任何写入的内容都被丢弃。我们的兴趣在于用它来创建映射区，用 /dev/zero 创建的映射区，其内容被初始为 0
    2) 使用 /dev/zero 的优点在于，mmap创建映射区时，不需要一个实际存在的文件，伪文件 /dev/zero 就足够了。缺点是只能用在相关进程间。相对于相关进程间的通信，使用线程间通信效率要更高一些。不管使用那种技术，对共享数据的访问都需要进行同步 

Relevant Link:

http://www.phppan.com/2010/11/php-source-code-30-memory-pool-storage/

0x2: PHP Lexer
$PHPSRC/Zend/zend_language_scanner.c

ZEND_API int open_file_for_scanning(zend_file_handle *file_handle)
{
    char *buf;
    size_t size, offset = 0;
    zend_string *compiled_filename;

    /* The shebang line was read, get the current position to obtain the buffer start */
    if (CG(start_lineno) == 2 && file_handle->type == ZEND_HANDLE_FP && file_handle->handle.fp) {
        if ((offset = ftell(file_handle->handle.fp)) == -1) {
            offset = 0;
        }
    }

    if (zend_stream_fixup(file_handle, &buf, &size) == FAILURE) {
        return FAILURE;
    }

    zend_llist_add_element(&CG(open_files), file_handle);
    if (file_handle->handle.stream.handle >= (void*)file_handle && file_handle->handle.stream.handle <= (void*)(file_handle+1)) 
    {
        zend_file_handle *fh = (zend_file_handle*)zend_llist_get_last(&CG(open_files));
        size_t diff = (char*)file_handle->handle.stream.handle - (char*)file_handle;
        fh->handle.stream.handle = (void*)(((char*)fh) + diff);
        file_handle->handle.stream.handle = fh->handle.stream.handle;
    }

    /* Reset the scanner for scanning the new file */
    SCNG(yy_in) = file_handle;
    SCNG(yy_start) = NULL;

    if (size != -1) {
        if (CG(multibyte)) {
            SCNG(script_org) = (unsigned char*)buf;
            SCNG(script_org_size) = size;
            SCNG(script_filtered) = NULL;

            zend_multibyte_set_filter(NULL);

            if (SCNG(input_filter)) {
                if ((size_t)-1 == SCNG(input_filter)(&SCNG(script_filtered), &SCNG(script_filtered_size), SCNG(script_org), SCNG(script_org_size))) {
                    zend_error_noreturn(E_COMPILE_ERROR, "Could not convert the script from the detected "
                            "encoding \"%s\" to a compatible encoding", zend_multibyte_get_encoding_name(LANG_SCNG(script_encoding)));
                }
                buf = (char*)SCNG(script_filtered);
                size = SCNG(script_filtered_size);
            }
        }
        SCNG(yy_start) = (unsigned char *)buf - offset;
        yy_scan_buffer(buf, (unsigned int)size);
    } else {
        zend_error_noreturn(E_COMPILE_ERROR, "zend_stream_mmap() failed");
    }

    BEGIN(INITIAL);

    if (file_handle->opened_path) {
        compiled_filename = zend_string_copy(file_handle->opened_path);
    } else {
        compiled_filename = zend_string_init(file_handle->filename, strlen(file_handle->filename), 0);
    }

    zend_set_compiled_filename(compiled_filename);
    zend_string_release(compiled_filename);

    if (CG(start_lineno)) {
        CG(zend_lineno) = CG(start_lineno);
        CG(start_lineno) = 0;
    } else {
        CG(zend_lineno) = 1;
    }

    RESET_DOC_COMMENT();
    CG(increment_lineno) = 0;
    return SUCCESS;
}
END_EXTERN_C()

0x3: 解析Token词素

int lex_scan(zval *zendlval)
{
restart:
    SCNG(yy_text) = YYCURSOR;


#line 1079 "Zend/zend_language_scanner.c"
{
    YYCTYPE yych;
    unsigned int yyaccept = 0;
    if (YYGETCONDITION() < 5) {
        if (YYGETCONDITION() < 2) {
            if (YYGETCONDITION() < 1) {
                goto yyc_ST_IN_SCRIPTING;
            } else {
                goto yyc_ST_LOOKING_FOR_PROPERTY;
            }
        } else {
            if (YYGETCONDITION() < 3) {
                goto yyc_ST_BACKQUOTE;
            } else {
                if (YYGETCONDITION() < 4) {
                    goto yyc_ST_DOUBLE_QUOTES;
                } else {
                    goto yyc_ST_HEREDOC;
                }
            }
        }
    } else {
        if (YYGETCONDITION() < 7) {
            if (YYGETCONDITION() < 6) {
                goto yyc_ST_LOOKING_FOR_VARNAME;
            } else {
                goto yyc_ST_VAR_OFFSET;
            }
        } else {
            if (YYGETCONDITION() < 8) {
                goto yyc_INITIAL;
            } else {
                if (YYGETCONDITION() < 9) {
                    goto yyc_ST_END_HEREDOC;
                } else {
                    goto yyc_ST_NOWDOC;
                }
            }
        }
    }
/* *********************************** */
yyc_INITIAL:

    YYDEBUG(0, *YYCURSOR);
    YYFILL(7);
    yych = *YYCURSOR;
    if (yych != '<') goto yy4;
    YYDEBUG(2, *YYCURSOR);
    ++YYCURSOR;
    if ((yych = *YYCURSOR) == '?') goto yy5;
yy3:
    YYDEBUG(3, *YYCURSOR);
    yyleng = YYCURSOR - SCNG(yy_text);
#line 1760 "Zend/zend_language_scanner.l"
    {
    if (YYCURSOR > YYLIMIT) {
        return 0;
    }

inline_char_handler:

    while (1) {
        YYCTYPE *ptr = memchr(YYCURSOR, '<', YYLIMIT - YYCURSOR);

        YYCURSOR = ptr ? ptr + 1 : YYLIMIT;

        if (YYCURSOR >= YYLIMIT) {
            break;
        }

        if (*YYCURSOR == '?') {
            if (CG(short_tags) || !strncasecmp((char*)YYCURSOR + 1, "php", 3) || (*(YYCURSOR + 1) == '=')) { /* Assume [ \t\n\r] follows "php" */

                YYCURSOR--;
                break;
            }
        }
    }

    yyleng = YYCURSOR - SCNG(yy_text);

    if (SCNG(output_filter)) {
        size_t readsize;
        char *s = NULL;
        size_t sz = 0;
        // TODO: avoid reallocation ???
        readsize = SCNG(output_filter)((unsigned char **)&s, &sz, (unsigned char *)yytext, (size_t)yyleng);
        ZVAL_STRINGL(zendlval, s, sz);
        efree(s);
        if (readsize < yyleng) {
            yyless(readsize);
        }
    } else {
      ZVAL_STRINGL(zendlval, yytext, yyleng);
    }
    HANDLE_NEWLINES(yytext, yyleng);
    return T_INLINE_HTML;
}
#line 1178 "Zend/zend_language_scanner.c"
yy4:
    YYDEBUG(4, *YYCURSOR);
    yych = *++YYCURSOR;
    goto yy3;
yy5:
    YYDEBUG(5, *YYCURSOR);
    yyaccept = 0;
    yych = *(YYMARKER = ++YYCURSOR);
    if (yych <= 'O') {
        if (yych == '=') goto yy7;
    } else {
        if (yych <= 'P') goto yy9;
        if (yych == 'p') goto yy9;
    }
yy6:
    YYDEBUG(6, *YYCURSOR);
    yyleng = YYCURSOR - SCNG(yy_text);
#line 1751 "Zend/zend_language_scanner.l"
    {
    if (CG(short_tags)) {
        BEGIN(ST_IN_SCRIPTING);
        return T_OPEN_TAG;
    } else {
        goto inline_char_handler;
    }
}
#line 1205 "Zend/zend_language_scanner.c"
yy7:
    YYDEBUG(7, *YYCURSOR);
    ++YYCURSOR;
    YYDEBUG(8, *YYCURSOR);
    yyleng = YYCURSOR - SCNG(yy_text);
#line 1738 "Zend/zend_language_scanner.l"
    {
    BEGIN(ST_IN_SCRIPTING);
    return T_OPEN_TAG_WITH_ECHO;
}
#line 1216 "Zend/zend_language_scanner.c"
yy9:
    YYDEBUG(9, *YYCURSOR);
    yych = *++YYCURSOR;
    if (yych == 'H') goto yy11;
    if (yych == 'h') goto yy11;
yy10:
    YYDEBUG(10, *YYCURSOR);
    YYCURSOR = YYMARKER;
    goto yy6;
yy11:
    YYDEBUG(11, *YYCURSOR);
    yych = *++YYCURSOR;
    if (yych == 'P') goto yy12;
    if (yych != 'p') goto yy10;
yy12:
    YYDEBUG(12, *YYCURSOR);
    yych = *++YYCURSOR;
    if (yych <= '\f') {
        if (yych <= 0x08) goto yy10;
        if (yych >= '\v') goto yy10;
    } else {
        if (yych <= '\r') goto yy15;
        if (yych != ' ') goto yy10;
    }
yy13:
    YYDEBUG(13, *YYCURSOR);
    ++YYCURSOR;
yy14:
    YYDEBUG(14, *YYCURSOR);
    yyleng = YYCURSOR - SCNG(yy_text);
#line 1744 "Zend/zend_language_scanner.l"
    {
    HANDLE_NEWLINE(yytext[yyleng-1]);
    BEGIN(ST_IN_SCRIPTING);
    return T_OPEN_TAG;
}
#line 1253 "Zend/zend_language_scanner.c"
yy15:
    YYDEBUG(15, *YYCURSOR);
    ++YYCURSOR;
    if ((yych = *YYCURSOR) == '\n') goto yy13;
    goto yy14;
/* *********************************** */
yyc_ST_BACKQUOTE:
    {
        static const unsigned char yybm[] = {
              0,   0,   0,   0,   0,   0,   0,   0, 
              0,   0,   0,   0,   0,   0,   0,   0, 
              0,   0,   0,   0,   0,   0,   0,   0, 
              0,   0,   0,   0,   0,   0,   0,   0, 
              0,   0,   0,   0,   0,   0,   0,   0, 
              0,   0,   0,   0,   0,   0,   0,   0, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128,   0,   0,   0,   0,   0,   0, 
              0, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128,   0,   0,   0,   0, 128, 
              0, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128,   0,   0,   0,   0, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
            128, 128, 128, 128, 128, 128, 128, 128, 
        };
        YYDEBUG(16, *YYCURSOR);
        YYFILL(2);
        yych = *YYCURSOR;
        if (yych <= '_') {
            if (yych != '$') goto yy23;
        } else {
            if (yych <= '`') goto yy21;
            if (yych == '{') goto yy20;
            goto yy23;
        }
        YYDEBUG(18, *YYCURSOR);
        ++YYCURSOR;
        if ((yych = *YYCURSOR) <= '_') {
            if (yych <= '@') goto yy19;
            if (yych <= 'Z') goto yy26;
            if (yych >= '_') goto yy26;
        } else {
            if (yych <= 'z') {
                if (yych >= 'a') goto yy26;
            } else {
                if (yych <= '{') goto yy29;
                if (yych >= 0x7F) goto yy26;
            }
        }
yy19:
        YYDEBUG(19, *YYCURSOR);
        yyleng = YYCURSOR - SCNG(yy_text);
#line 2170 "Zend/zend_language_scanner.l"
        {
    if (YYCURSOR > YYLIMIT) {
        return 0;
    }
    if (yytext[0] == '\\' && YYCURSOR < YYLIMIT) {
        YYCURSOR++;
    }

    while (YYCURSOR < YYLIMIT) {
        switch (*YYCURSOR++) {
            case '`':
                break;
            case '$':
                if (IS_LABEL_START(*YYCURSOR) || *YYCURSOR == '{') {
                    break;
                }
                continue;
            case '{':
                if (*YYCURSOR == '$') {
                    break;
                }
                continue;
            case '\\':
                if (YYCURSOR < YYLIMIT) {
                    YYCURSOR++;
                }
                /* fall through */
            default:
                continue;
        }

        YYCURSOR--;
        break;
    }

    yyleng = YYCURSOR - SCNG(yy_text);

    zend_scan_escape_string(zendlval, yytext, yyleng, '`');
    return T_ENCAPSED_AND_WHITESPACE;
}
#line 1364 "Zend/zend_language_scanner.c"
yy20:
        YYDEBUG(20, *YYCURSOR);
        yych = *++YYCURSOR;
        if (yych == '$') goto yy24;
        goto yy19;
yy21:
        YYDEBUG(21, *YYCURSOR);
        ++YYCURSOR;
        YYDEBUG(22, *YYCURSOR);
        yyleng = YYCURSOR - SCNG(yy_text);
#line 2114 "Zend/zend_language_scanner.l"
        {
    BEGIN(ST_IN_SCRIPTING);
    return '`';
}
#line 1380 "Zend/zend_language_scanner.c"
yy23:
        YYDEBUG(23, *YYCURSOR);
        yych = *++YYCURSOR;
        goto yy19;
yy24:
        YYDEBUG(24, *YYCURSOR);
        ++YYCURSOR;
        YYDEBUG(25, *YYCURSOR);
        yyleng = YYCURSOR - SCNG(yy_text);
#line 2101 "Zend/zend_language_scanner.l"
        {
    Z_LVAL_P(zendlval) = (zend_long) '{';
    yy_push_state(ST_IN_SCRIPTING);
    yyless(1);
    return T_CURLY_OPEN;
}
#line 1397 "Zend/zend_language_scanner.c"
yy26:
        YYDEBUG(26, *YYCURSOR);
        yyaccept = 0;
        YYMARKER = ++YYCURSOR;
        YYFILL(3);
        yych = *YYCURSOR;
        YYDEBUG(27, *YYCURSOR);
        if (yybm[0+yych] & 128) {
            goto yy26;
        }
        if (yych == '-') goto yy31;
        if (yych == '[') goto yy33;
yy28:
        YYDEBUG(28, *YYCURSOR);
        yyleng = YYCURSOR - SCNG(yy_text);
#line 1825 "Zend/zend_language_scanner.l"
        {
    zend_copy_value(zendlval, (yytext+1), (yyleng-1));
    return T_VARIABLE;
}
#line 1418 "Zend/zend_language_scanner.c"
yy29:
        YYDEBUG(29, *YYCURSOR);
        ++YYCURSOR;
        YYDEBUG(30, *YYCURSOR);
        yyleng = YYCURSOR - SCNG(yy_text);
#line 1549 "Zend/zend_language_scanner.l"
        {
    yy_push_state(ST_LOOKING_FOR_VARNAME);
    return T_DOLLAR_OPEN_CURLY_BRACES;
}
#line 1429 "Zend/zend_language_scanner.c"
yy31:
        YYDEBUG(31, *YYCURSOR);
        yych = *++YYCURSOR;
        if (yych == '>') goto yy35;
yy32:
        YYDEBUG(32, *YYCURSOR);
        YYCURSOR = YYMARKER;
        goto yy28;
yy33:
        YYDEBUG(33, *YYCURSOR);
        ++YYCURSOR;
        YYDEBUG(34, *YYCURSOR);
        yyleng = YYCURSOR - SCNG(yy_text);
#line 1818 "Zend/zend_language_scanner.l"
        {
    yyless(yyleng - 1);
    yy_push_state(ST_VAR_OFFSET);
    zend_copy_value(zendlval, (yytext+1), (yyleng-1));
    return T_VARIABLE;
}
#line 1450 "Zend/zend_language_scanner.c"
yy35:
        YYDEBUG(35, *YYCURSOR);
        yych = *++YYCURSOR;
        if (yych <= '_') {
            if (yych <= '@') goto yy32;
            if (yych <= 'Z') goto yy36;
            if (yych <= '^') goto yy32;
        } else {
            if (yych <= '`') goto yy32;
            if (yych <= 'z') goto yy36;
            if (yych <= '~') goto yy32;
        }
yy36:
        YYDEBUG(36, *YYCURSOR);
        ++YYCURSOR;
        YYDEBUG(37, *YYCURSOR);
        yyleng = YYCURSOR - SCNG(yy_text);
#line 1809 "Zend/zend_language_scanner.l"
        {
    yyless(yyleng - 3);
    yy_push_state(ST_LOOKING_FOR_PROPERTY);
    zend_copy_value(zendlval, (yytext+1), (yyleng-1));
    return T_VARIABLE;
}

Relevant Link:

http://bbs.chinaunix.net/thread-727747-1-1.html

 

14. 在Opcode层面进行语法还原WEBSHELL检测

1. 词法Token树解析(opcodes)
2. 词法规范化还原
    1) 赋值传递
    2) API函数执行
3. opcodes -> sourcecode
4. 正则规则检查

需要的相关信息

1. filename: zend_op_array->filename
2. opcode名称: opcodes[op.opcode].name
3. 表达式计算结果: opcodes[op.opcode].result
4. 参数1: opcodes[op.opcode].op1_type, opcodes[op.opcode].op1
5. 参数2: opcodes[op.opcode].op2_type, opcodes[op.opcode].op2

但是这种方案也存在一个问题，Zend把PHP用户态源代码翻译为Opcode汇编源代码之后，用户态语法层面的特征已经被极大地弱化了，例如if、foreach这类语法会翻译为了if/goto这种形态的汇编模式
随之而来的，如果要在Opcode汇编层面进行代码优化、还原、甚至是Opcode反转用户态代码，都是十分困难的

 

Copyright (c) 2015 LittleHann All rights reserved