在所有计算机上运行的所有软件都是用某种程序设计语言编写的，但是在一个程序可以运行之前，它首先需要被翻译成一种能够被计算机执行的形式，完成这项翻译工作的软件系统称为编译器(compiler)
0x1:语言处理器
1.编译器简单地说，一个编译器就是一个程序，它可以阅读以某一种语言(源语言)编写的程序，并把该程序翻译成一个等价、用另一种语言(目标语言)编写的程序，编译器的重要任务之一是报告它在翻译过程中发现的原程序中的错误2.解释器解释器(interpreter)是另一种常见的语言处理器，它并不通过翻译的方式生成目标程序，解释器直接利用用户提供的输入执行源程序中指定的操作//在把用于输入映射成为输出的过程中，由一个编译器产生的机器语言目标程序通常比一个解释器要快很多，然而，解释器的错误诊断效果通常比编译器更好，因为它逐个语句地执行源程序java语言处理器结合了编译和解释过程，一个java源程序首先被编译成一个称为字节码(bytecode)的中间表示形式，然后由一个虚拟机对得到的字节码加以解释执行，这样设计的好处之一是在一台机器上编译得到的字节码可以在另一台机器上解释执行，通过网络就可以完成机器之间的迁移为了更快地完成输入到输出的处理，有些被称为即时(justintime)编译器的java编译器在运行中间程序处理输入的前一刻先把字节码翻译成为机器语言，然后再执行程序
0x2:一个编译器的结构
编译器能够把源程序映射为在语义上等价的目标程序，这个映射过程由两个部分组成:分析部分、综合部分
如果我们更加详细地研究编译过程，会发现它顺序执行了一组步骤(phase)，每个步骤把源程序的一种表现形式转换为另一种表现形式，在实践中，多个步骤可能被组合在一起，而这些组合在一起的步骤之间的中间表示不需要被明确地构造出来，存放整个源程序的信息的符号表可由编译器的各个步骤使用有些编译器在前端和后端之间有一个与机器无关的优化步骤，这个优化步骤的目的是在中间表示之上进行转换，以便后端程序能够生成更好的目标程序
1.词法分析
编译器的第一个步骤称为词法分析(lexicalanalysis)或扫描(scanning)，词法分析器读入组成源程序的字符流，并且将它们组织成为有意义的词素(lexeme)的序列，对于每个词素，词法分析器产生如下形式的词法单元(token)作为输出
可以看到，在静态分析、编译原理应用领域，代码优化器这一步可以推广到WEBSHELL恶意代码检测技术上，利用这一步得到的"归一化"代码，可以进行纯词法层面的"恶意特征字符串模式匹配"
2.语法分析
编译器的第2个步骤称为语法分析(syntaxanalysis)或解析(parsing)。语法分析器使用由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示，该中间表示给出了词法分析产生的词法单元流的语法结构，一个常用的表示方法是语法树(syntaxtree)，树中的每个内部结点表示一个运算，而该结点的子节点表示该预算的分量(左右参数)编译器的后续步骤使用这个语法结构来帮助分析源程序，并生成目标程序
3.语义分析
语义分析器(semanticanalyzer)使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致，它同时也收集类型信息，并把这些信息存放在语法树或符号表中，以便在随后的中间代码生成过程中使用语义分析的一个重要部分是类型检查(typechecking)，编译器检查每个运算符是否具有匹配的运算分量程序设计语言可能允许某些类型转换，即自动类型转换(coercion)
4.中间代码生成
在把一个源程序翻译成目标代码的过程中，一个编译器可能构造出一个或多个中间表示，这些中间表示可以有多种形式(语法树就是一种中间表示，它们通常在语法分析和语义分析中使用)在源程序的语法分析和语义分析完成之后，编译器会生成一个明确的低级或类机器语言的中间表示，我们可以把这个表示看作是某种抽象机器的程序，该中间表示应该具有两个重要的性质
1.易于生成2.能够轻松地翻译为目标机器上的语言5.代码优化
6.代码生成
代码生成器以源程序的中间表示形式作为输入，并把它映射到目标语言，如果目标语言是机器代码，那么就必须为程序使用的每个变量选择寄存器或内存地址，然后中间指令被翻译成能够完成相同任务的机器指令序列。代码生成的一个至关重要的方面是合理分配寄存器以存放变量的值需要明白的是，运行时刻的存储组织方式依赖于被编译的语言，编译器在中间代码生成或代码生成阶段做出有关存储的分配的决定
7.符号表管理
编译器的重要功能之一是记录源程序中使用的变量的名字，并收集和每个名字的各种属性有关的信息，这些属性可以提供一个名字的存储分配、类型、作用域等信息，对于过程，这些信息还包括
1.名字的存储分配2.类型3.作用域(在程序的哪些地方可以使用这个名字的值)4.参数数量5.参数类型6.每个参数的传递方式(值传递或引用传递)7.返回类型符号表数据结构为每个变量名创建了一个记录条目，记录的各个字段就是名字的各个属性，这个数据结构允许编译器迅速查找到每个名字的记录，并向记录中快速存放和获取记录中的数据
8.编译器构造工具
一个常用的编译器构造工具包括
1.扫描器的生成器:可以根据一个语言的语法单元的正则表达式描述生成词法分析器2.语法分析器的生成器:可以根据一个程序设计语言的语法描述自动生成语法分析器3.语法制导的翻译引擎:可以生成一组用于遍历分析树并生成中间代码的例程4.代码生成器的生成器:依据一组关于如何把中间语言的每个运算翻译成目标机器上的机器语言的规则，生成一个代码生成器5.数据流分析引擎:可以帮助收集数据流信息，即程序中的值如何从程序的一个部分传递到另一部分，数据流分析是代码优化的一个重要部分6.编译器构造工具集:提供了可用于构造编译器的不同阶段的例程的完整集合
编译器的设计中有很多通过数学方法抽象出问题本质从而解决现实世界复杂问题的例子，这些例子可以被用来说明如何使用抽象方法来解决问题:接受一个问题，写出抓住了问题的关键特性的数学抽象表示，并用数学技术来解决它，问题的表达必须根植于对计算机程序特性的深入理解，而解决方法必须使用经验来验证和精化
0x1:编译器设计和实现中的建模
对编译器的研究主要是有关如何设计正确的数学模型和选择正确算法的研究，设计和选择时，还需要考虑到对通用性及功能的要求与简单性及有效性之间的平衡
1.最基本的数学模型是有穷状态自动机和正则表达式，这些模型可以用于描述程序的词法单位(关键字、标识符等)以及描述被编译器用来识别这些单位的算法2.上下文无关文法，它用于描述程序设计语言的语法结构，例如嵌套的括号和控制结构3.树形结构是表示程序结构以及程序到目标代码的翻译方法的重要模型0x2:代码优化的科学
现在，编译器所作的代码优化变得更加重要，而且更加复杂，因为处理器体系结构变得更加复杂，也有了更多改进代码执行方式的机会，之所以变得更加重要，是因为巨型并发计算机要求实质性的优化，否则它们的性能将会呈数量级下降，随着多核计算机的发展，所有的编译器将面临充分利用多核计算机的优势的问题即使有可能通过随意的方法来建造一个健壮的编译器，实现起来也是非常困难，因为，研究人员已经围绕代码优化建立了一套广泛且有用的理论，应用严格的数学基础，使得我们可以证明一个优化是正确的，并且它对所有可能的输入都产生预期的效果需要明白的是，如果想使得编译器产生经过良好优化的代码，图、矩阵、线性规划之类的模型是必不可少的，编译器优化必须满足下面的设计目标
计算机体系结构的快速发展也对新编译技术提出了越来越多的需求，几乎所有的高性能系统都利用了两种技术:并行(parallelism)、内存层次结构(memoryhierarchy)
1.二进制翻译
编译器技术可以用于把一个机器的二进制代码翻译成另一个机器的二进制代码，使得可以在一个机器上运行原本为另一个指令集编译的程序
2.硬件合成
不仅仅大部分软件是用高级语言描述的，连大部分硬件设计也是使用高级硬件描述语言描述的，例如Verilog、VHDL(VeryHigh-SpeedIntefratedCircuitHardwareDescriptionLanguage超高速集成电路硬件描述语言)硬件设计通常是在寄存器传输层(RegisterTransferLevelRTL)上描述的，在这个层面中，变脸代表寄存器，而表达式代表组合逻辑，硬件合成工具把RTL描述自动翻译为门电路，而门电路再被翻译成为晶体管，最后生成一个物理布局
3.数据查询解释器
除了描述软件和硬件，语言在很多应用中都是有用的，比例，查询语言(例如SQL语言StructuredQueryLanguage结构化查询语言)被用来搜索数据库，数据库查询由包含了关系和布尔运算符的断言组成，它们可以被解释，也可以编译为代码，以便在一个数据库中搜索满足这个断言的记录
3.程序设计语言基础
0x1:静态和动态的区别
在为一个语言设计一个编译器时，我们所面对的最重要的问题之一是编译器能够对一个程序做出哪些判定
1.如果一个语言使用的策略支持编译器静态决定某个问题，那么我们说这个语言使用了一个静态(static)策略，或者说这个问题可以在编译时刻(compiletime)决定2.另一方面，一个只允许在运行程序的时候做出决定的策略被称为动态策略(dynamicpolicy)，或者被认为需要在运行时刻(runtime)做出决定0x2:环境与状态
我们在讨论程序设计语言时必须了解的另一个重要区别是在程序运行时发生的改变是否会影响数据元素的值，还是仅仅影响了对那个数据的名字的解释名字和内存(存储)位置的关联，及之后和值的关联可以用两个映射来描述，这两个映射随着程序的运行而改变
1.环境(environment)是一个从名字到存储位置的映射，因为变量就是指内存位置(即C语言中的术语"左值")，我们还可以换一种方法，把环境定义为从名字到变量的映射//环境的改变需要遵守语言的作用域规则2.状态(state)是一个从内存位置到它们的值的映射，以C语言的术语来说，即状态把左值映射为它们的相应的右值0x3:静态作用域和块结构
0x5:动态作用域
从技术上讲，如果一个作用域策略依赖于一个或多个只有在程序执行时刻才能知道的因素，它就是动态的，然而，术语动态作用域通常指的是下面的策略
0x6:参数传递机制
所有的程序设计语言都有关于过程的概念，但是在这些过程如何获取它们的参数方面，不同的语言之间有所不同
1.值调用
在值调用(call-by-value)中，会对实参求值(如果它是表达式)或拷贝(如果它是变量)，这些值被放在属于被调用过程的相应形式参数的内存位置上(即入栈)，值调用的效果是，被调用过程所做的所有有关形式参数的计算都局限于这个过程，对应的实参本身不会被改变需要注意的是，我们同样可以传递变量的指针，这样对于过程来说虽然依然是值传递，但是从效果上等同于传递了对应参数的引用
2.引用调用
在引用调用(call-by-reference)中，实参的地址作为相应的形式参数的值被传递给被调用者，在被调用者的代码中使用该形参时，实现方法是沿着这个指针找到调用者指明的内存位置，因此，改变形式参数看起来就像是改变饿了实参一样
3.名调用
0x7:别名
引用调用或者其他类似的方法，比如像Java中那样把对象的引用当值传递，会引起一个有趣的结果，即两个形参指向同一个位置，这样的变量称为另一个变量的别名(alias)，结果是，任意两个看起来从两个不同的形参中获得值的变量也可能变成对方的别名，这个现象在PHP中也同样存在事实上，如果编译器要优化一个程序，就要理解别名现象以及产生这一现象的机制，必须在确认某些变量相互之间不是别名之后才可以优化程序
4.一个简单的语法制导翻译器
0x1:引言
编译器在分析(scanning)阶段把一个源程序划分成各个组成部分，并生成源程序的内部表示形式，这种内部表示称为中间代码，然后，编译器在合成阶段将这个中间代码翻译成目标程序分析阶段的工作是围绕着待编译语言的的"语法"展开的，一个程序设计语言的语法(syntax)描述了该语言的程序的正确形式，而该语言的语义(semantics)则定义了程序的含义，即每个程序在运行时做什么事情我们将在接下来讨论一个广泛使用的表示方法来描述语法，即上下文无关文法或BNF(Backus-Naur范式)，描述语义的难度远远大于描述语言语法的难度，因此，我们将结合非形式化描述和启发式描述的来描述语言的语义
图中显示了两种中间代码形式
1.左:抽象语法树(abstractsyntaxtree):表示了源程序的层次化语法结构2.右:"三地址"指令序列:三地址指令最多只执行一个运算，通常是计算、比较、分支跳转0x2:语法定义
在本节中，我们将讨论一种用于描述程序设计语言语法的表示方法"上下文无关文法"，或简称"文法"，文法将被用于组织编译器前端文法自然地描述了大多数程序设计语言构造的层次化语法结构，例如，Java中的if-else语句通常具有如下形式
if(expression)statementelsestatement//即一个if-else语句由关键字if、左括号、表达式、右括号、语句块、关键字else、语句块组成，这个构造规则可以表示为stmt->if(expr)stmtelsestmt//其中箭头(->)表示"可以具有如下形式"这样的规则称为产生式(production)，在一个产生式中，像关键字if和括号这样的词法元素称为终结符号(terminal)，像expr和stmt这样的变量表示终结符号的序列，它们称为非终结符号(nonterminal)
1.文法定义
一个上下文无关文法(context-freegrammar)由四个元素组成
1.终结符号集合，也称为"词法单元"，终结符号是该文法所定义的语言的基本符号的集合2.非终结符号集合，也称为"语法变量"，每个非终结符号表示一个终结符号串的集合3.产生式集合，其中每个产生式包括1)一个称为产生式头或左部的非终结符号2)一个箭头3)一个称为产生式体或右部的由终结符号及非终结符号组成的序列，产生式主要用来表示某个构造的某种书写形式，如果产生式头非终结符号代表一个构造，那么该产生式体就代表了该构造的一种书写方式4)指定一个非终结符号为开始符号在编译器中，词法分析器读入源程序中的字符序列，将它们组织为具有词法含义的词素，生成并输出代表这些词素的词法单元序列，词法单元由两个部分组成:名字和属性值
1.词法单元的名字是词法分析器进行语法分析时使用的抽象符号，我们通常把这些词法单元名字称为终结符号，因为它们在描述程序设计语言的文法中是以终结符号的形式出现的2.如果词法单元具有属性值，那么这个值就是一个指向符号表的指针，符号表中包含了该词法单元的附加信息，这些附加信息不是文法的组成部分，因此我们在讨论语法分析时，通产将词法单元和终结符号当作同义词如果某个非终结符号是某个产生式的头部，我们就说该产生式是该非终结符号的产生式，一个终结符号串是由零个或多个终结符号组成的序列，零个终结符号组成的串称为空串(emptystring)
2.推导
根据文法推导符号串时，我们首先从开始符号出发，不断将某个非终结符号替换为该非终结符号的某个产生式的体，可以从开始符号推导得到的所有终结符号串的集合称为该文法定义的语言(language)语法分析(parsing)的任务是:接受一个终结符号串作为输入，找出从文法的开始符号推导出这个串的方法，如果不能从文法的开始符号推导得到该终结符号，则报告该终结符号串中包含的语法错误一般情况下，一个源程序中会包含由多个字符组成的词素，这些词素由词法分析器组成词法单元，而词法单元的第一个分量就是被语法分析器处理的终结符号
3.语法分析树
语法分析树用图形方式展现了从文法的开始符号推导出相应语言中的符号串的过程，如果非终结符号A有一个产生式A->XYZ，那么在语法分析树中就有可能有一个标号为A的内部结点，该结点有三个子节点，从左向右的标号分别为X、Y、Z
从本质上说，给定一个上下文无关文法，该文法的一棵语法分析树(parsetree)是具有以下性质的树
1.根结点的标号为文法的开始符号2.每个叶子结点的标号为一个终结符号或空串3.每个内部结点的标号为一个非终结符号4.如果非终结符号A是某个内部结点的标号，并且它的子结点的标号从左至右分别为X1、X2、...、Xn，那么必然存在产生式A->X1X2..Xn，其中X1X2..Xn既可以是终结符号，也可以是非终结符号，作为一个特殊情况，如果A->空串是一个产生式，那么一个标号为A的结点可以只有标号为空串的子结点一棵语法分析树的叶子结点从左向右构成了树的结果(yield)，也就是从这课语法分析树的根节点上的非终结符号推导得到(生成)的符号串一个文法的语言的另一个定义是指任何能够由某课语法分析树生成的符号串的集合，为一个给定的终结符号串构建一棵语法分析树的过程称为对该符号串进行语法分析
4.二义性
在根据一个文法讨论某个符号串的结构时，我们必须非常小心，一个文法可能有多课语法分析树能够生成同一个给定的终结符号串，这样的文法称为具有二义性(ambiguous)，要证明一个文法具有二义性，我们只需要找到一个终结符号串，说明它是两棵以上语法分析树的结果因为具有两棵以上语法分析树的符号串通常具有多个含义，所以我们需要为编译应用设计出没有二义性的文法，或者在使用二义性文法时使用附加规则来消除二义性
5.运算符的结合性
在大多数程序设计语言中，加减乘除4种算术运算符都是左结合的，某些常用运算符是右结合的，例如赋值运算符，对于左结合的文法来说，语法树向左下端延伸，而右结合的文法语法树向有下端延伸
6.运算符的优先级
算术表达式的文法可以根据表示运算符结合性和优先级的表格来建立
expr->expr+term|expr-term|termterm->term*factor|term/factor|factorfactor->digit|(expr)0x3:语法制导翻译
语法制导翻译是通过向一个文法的产生式附加一些规则或程序片段而得到的
一个表达式E的后缀表示(postfixnotation)可以按照下面的方式进行归纳定义
1.如果E是一个变量或者常量，则E的后缀表示是E本身2.如果E是一个形如"E1opE2"的表达式，其中op是一个二目运算符，那么E的后缀表示是E1E2op3.如果E是一个形如(E1)的被括号括起来的表达式，则E的后缀表示就是E1的后缀表示例如，9-(5+2)的后缀表达式是952+-，即5+2首先被翻译成52+，然后这个表达式又成为减号的第二个运算分量运算符的位置和它的运算分量个数(anty)使得后缀表达式只有一种解码方式，所以在后缀表示中不需要括号，处理后缀表达式的技巧就是
1.从左边开始不断扫描后缀串，直到发现一个运算符为止2.然后向左找出适当数目的运算分量，并将这个运算符和它的运算分量组合在一起3.计算出这个运算符作用于这些运算分量上后得到的结果4.并用这个结果替换原来的运算分量和运算符，然后继续这个过程，向右搜寻另一个运算符3.综合属性
1.假设语法分析树的一个结点N的标号为文法符号X，我们用X.a表示该结点上X的属性a的值2.如果一棵语法分析树的各个结点上标记了相应的属性值，那么这课语法分析树就称为注释(annotated)语法分析树(注释分析树)
如果某个属性在语法分析树结点N上的值是由N的子结点以及N本身的属性值确定的，那么这个属性就称为综合属性(synthesizedattribute)，综合属性有一个很好的性质:只需要对语法分析树进行一次自底向上的遍历，就可以计算出属性的值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.预测分析法
3.设计一个预测分析器
对于文法的任何非终结符号，它的各个产生式体的FIRST集合互不相交，如果我们有一个翻译方案，即一个增加了语义动作的文法，那么我们可以将这些语义动作当作此语法分析器的过程的一部分执行一个预测分析器(predictiveparser)程序由各个非终结符对应的过程组成，对应于非终结符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:抽象语法和具体语法
设计一个翻译器时，名为抽象语法树(abstractsyntaxtree)的数据结构是一个很好的起点，在一个表达式的抽象语法树中，每个内部结点代表一个运算符，该结点的子结点代表这个运算符的运算分量。对于一个更加一般化的情况，当我们处理任意的程序设计语言构造时，我们可以创建一个针对这个构造的运算符，并把这个构造的具有语义信息的组成部分作为这个运算符的运算分量抽象语法树也简称语法树(syntaxtree)，在某种程序上和语法分析树相似
1.在抽象语法树中，内部结点代表的是程序构造:2.在语法分析树中，内部结点代表的是非终结符号:具体语法树(concretesyntaxtree)，相应的文法称为该语言的具体语法(concretesyntax)文法中的很多非终结符号都是代表程序的构造，但也有一部分是各种各样的辅助符号，比如代表项、因子或其他表达式变体的非终结符号，在抽象语法树中，通常不需要这些辅助符号，因此会将这些符号省略掉，为了强调他们的区别，我们有时把语法分析树称为具体语法树(concretesyntextree)，而相应的文法称为该语言的具体语法(concretesyntax)
0x2:调整翻译方案
0x3:非终结符号的过程
0x4:翻译器的简化
0x5:完整的程序
/***Createdbyzhenghan.zhon2016/1/18.*/importjava.io.*;classParser{staticintlookahead;publicParser()throwsIOException{lookahead=System.in.read();}voidexpr()throwsIOException{term();while(true){if(lookahead=='+'){match('+');term();System.out.write('+');}elseif(lookahead=='-'){match('-');term();System.out.write('-');}elsereturn;}}voidterm()throwsIOException{if(Character.isDigit((char)lookahead)){System.out.write((char)lookahead);match(lookahead);}else{thrownewError("syntaxerror");}}voidmatch(intt)throwsIOException{if(lookahead==t){lookahead=System.in.read();}else{thrownewError("syntaxerror");}}}publicclassPostfix{publicstaticvoidmain(String[]args)throwsIOException{System.out.println("hello");Parserparse=newParser();parse.expr();System.out.write('\n');}}
对整个编译过程有了一个整体的认识之后，下面我们从词法分析开始逐步深入学习编译原理
6.词法分析
一个词法分析器从输入中读取字符，并将它们组成"词法单元对象"。除了用于语法分析的终结符号之外，一个词法单元对象还包含一些附加信息，这些信息以属性值的形式出现构成一个词法单元的输入字符称为词素(lexern)，因此，"词法分析器"使得"语法分析器"不需要考虑词法单元的词素表示方法
0x1:删除空白和注释
大部分语言语序词法单元之间出现任意数量的空白，在语法分析过程中同样会忽略源程序中的注释，所以这些注释也可以当作空白处理
for(;;peek=nextinputcharacter){if(peekisablankoratab)donothing;elseif(peekisanewline)line=line+1;elsebreak;}0x2:预读
在决定向语法分析器返回哪个词法单元之前，词法分析器可能需要预先读入一些字符，例如C或Java的词法分析器在遇到字符">"之后必须预先读入一个字符
1.如果下一个字符是"="，那么">"就是字符序列">="的一部分。这个序列是代表"大于等于"运算符的词法单元的词素2.否则，">"本身形成了一个"大于"运算符，词法分析器就多读了一个字符一个通用的预先读取输入的方法是使用输入缓冲区，词法分析器可以从缓冲区中读取一个字符，也可以把字符放回缓冲区，我们可以用一个指针来跟踪已被分析的输入部分，向缓冲区放回一个字符可以通过回移指针来实现因为通常只需要预读一个字符，所以一种简单的解决方法是使用一个变量，比如peek，来保存下一个输入字符，在读入一个数字的数位或一个标识符的字符时，词法分析器会预读一个字符，例如在1后面预读一个字符来区别1、10，在t后预读一个字符来区分t和true词法分析器只有在必要的时候才进行预读，像"*"这样的运算符不需要预读就能够识别，在这种情况下，peek的值被设置为空白符，词法分析器在寻找下一个词法单元时会跳过这个空白符
//词法分析起的不变式断言当词法分析器返回一个词法单元时，变量peek要么保存了当前词法单元的词素后的那个字符，要么保存空白符0x3:常量
在一个表达式的文法中，任何允许出现数位的地方都应该允许出现任意的整型常量，要使得表达式中可以出现整数常量，我们可以创建一个代表整型常量的终结符号，例如num，也可以将整数常量的语法加入到文法中将字符组成整数并计算它的数值的工作通常是由词法分析器完成的，因此在语法分析和翻译过程中可以将数字当作一个单元进行处理
当在输入流中出现一个数位序列时，词法分析器将向语法分析器传送一个词法单元，该词法单元包含终结符号num、及根据这些数位计算得到的整型属性值，如果我们把词法单元写成用<>括起来的元祖，那么输入31+28+59就被转换成序列
大多数程序设计语言使用for、do、if这样的固定字符串作为标点符号，或者用于标识某种构造，这些字符串称为关键字(keyword)字符串还可以作为标识符，来为变量、数组、函数等命名，为了简化语法分析器，语言的文法通常把标识符当作终结符号进行处理，当某个标识符出现在输入中时，语法分析器都会得到相同的终结符号，如id，例如在处理如下输入时
count=count+increment//语法分析器处理的是终结符号序列id=id+id词法单元id有一个属性保存它的词素，将词法单元写作元祖形式，输入流的元祖序列是
1.如果关键字作为保留字:只有当一个字符串不是关键字时它才能组成一个标识符2.关键字作为标识符本章中的词法分析器使用一个表来保存字符串，解决了如下问题
1.单一表示:一个字符串可以将编译器的其余部分和表中字符串的具体表示隔离开，因为编译器后续的步骤可以只使用指向表中字符串的指针或引用，操作引用要比操作字符串本身更加高效2.保留字:要实现保留字，可以在初始化时在字符串表中加入保留的字符串以及它们对应的词法单元。当词法分析器读到一个可以组成标识符的字符串或词素时，它首先检查这个字符串表中是否有这些词素，如是，它就返回表中的词法单元，否则返回带有终结符号id的词法单元伪代码如下
Hashtablewords=newHashtable();if(peek存放了一个字母){将字母或数位读入一个缓冲区b;s=b中的字符形成的字符串;w=words.get(s)返回的词法单元;if(w不是null)returnw;else{将键-值对(s,
将上文给出的伪代码片段组合起来，可以得到一个返回词法单元对象的函数scan
Tokenscan(){跳过空白符;处理数字;处理保留字和标识符;//如果程序运行到这里，就将预读字符peek作为一个词法单元Tokent=newToekn(peek);peek=空白符;returnt;}0x6:符号表
符号表(symboltable)是一种供编译器用于保存有关源程序构造的各种信息的数据结构
2.符号表的使用
7.生成中间代码
编译器的前端构造出源程序的中间表示，而后根据这个中间表示生成目标程序
0x1:两种中间表示形式
0x2:语法树的构造
0x3:静态检查
静态检查是指在编译过程中完成的各种一致性检查，这些检查不仅可以确保一个程序被顺利地编译，而且还能在程序运行之前发现编程错误，静态检查包括
静态检查要确保一个赋值表达式的左部表示的是一个左值，一个像i这样的标识符是一个左值，像a[2]这样的数组访问也是左值，但2这样的常量不可以出现在一个赋值表达式的左部
2.类型检查
类型检查确保一个构造的类型符合其上下文对它的期望，例如在if语句中
if(expr)stmt//期望表达式expr是boolean型的0x4:三地址码
一旦抽象语法树构造完成，我们就可以计算树中各结点的属性值并执行各结点中的代码片段，进行进一步的分析和综合
1.三地址指令
三地址代码是由如下形式的指令组成的序列
x=yopz//x、y、z可以是名字、常量或由编译器生成的临时量；而op表示一个运算符三地址指令将被顺序执行，当时当遇到一个条件或无条件跳转指令时，执行过程就会跳转
2.语句的翻译
通过利用跳转指令实现语句内部的控制流，我们可以将语句转换成三地址代码
3.表达式的翻译
我们将考虑包含二目运算符op、数组访问和赋值运算，并包含常量及标识符的表达式，以此来说明对表达式的翻译
0x5:小结
8.词法分析器的实现
如果要手动地实现词法分析器，需要首先建立起每个词法单元的词法结构图或其他描述，然后我们可以编写代码来识别输入中出现的每个词素，并返回识别到的词法单元的有关信息我们也可以通过如下方式自动生成一个词法分析器
1.向一个词法分析器生成工具(lexical-analyzergenerator)描述出词素的模式2.然后将这些模式编译为具有词法分析器功能的代码在学习词法分析器生成工具之前，我们先学习正则表达式，正则表达式是一种可以很方便地描述词素模式的方法
1.正则表达式首先转换为不确定有穷自动机2.然后再转换为确定有穷自动机3.得到的结果作为"驱动程序"的输入，这个驱动程序就是一段模拟这些自动机的代码，它使用这些自动机来确定下一个词法单元4.这个驱动程序以及对自动机的规约形成了词法分析器的核心部分0x1:词法分析器的作用
词法分析器在编译器中负责读取源程序，因此它还会完成一些识别词素之外的其他任务
1.任务之一是过滤掉源程序中的注释和空白(空格、换行符、制表符以及在输入中用于分割词法单元的其他字符)2.另一个任务是将编译器生成的错误消息与源程序的位置关联起来有时，词法分析器可以分成两个级联的处理阶段
1.扫描阶段主要负责完成一些不需要生成词法单元的简单处理，比如删除注释和将多个连续的空白字符压缩成一个字符2.词法分析阶段是较为复杂的部分，它处理扫描阶段的输出并生成词法单元1.词法分析及解析
把编译过程的分析部分划分为词法分析和语法分析阶段有如下几个原因
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.串和语言
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.可以用一个正则表达式定义的语言叫做正则集合(regularset)2.如果两个正则表达式r、s表示同样的语言，则称r、s等价(equivalent)，记作r=s3.正则表达式遵守一些代数定律，每个定律都断言两个具有不同形式的表达式等价4.正则定义
5.正则表达式的扩展
0x4:词法单元的识别
我们已经讨论了如何使用正则表达式来表示一个模式，接下来，我们继续讨论如何根据各个需要识别的词法单元的模式来构造出一段代码
1.状态转换图
作为构造词法分析器的一个中间步骤，我们首先将模式转换成具有特定风格的流图，称为"状态转换图"状态转换图(transitiondiagram)有一组被称为"状态(state)"的结点或圆圈，词法分析器在扫描输入串的过程中寻找和某个模式匹配的词素，而转换图中的每个状态代表一个可能在这个过程中出现的情况，我们可以将一个状态看作是对我们已经看到的位于lexemeBegin指针和forward指针之间的字符的总结，它包含了我们在进行词法分析时需要的全部信息一些关于状态转换图的重要约定如下
我们可以使用两种方法来处理那些看起来很像标识符的保留字
1.初始化时就将各个保留字填入符号表，符号表条目的某个字段会指明这些串不是普通的标识符，并指出它们所代表的词法单元2.为每个关键字建立单独的状态转换图，要注意的是，这样的状态转换图包含的状态表示看到该关键字的各个后续字母后的情况3.连续性例子4.基于状态转换图的词法分析器的体系结构
有几种方法可以根据一组状态转换图构造出一个词法分析器，不管整体的策略是什么，每个状态总是对应于一段代码，我们可以想象有一个变量state保存了一个状态转换图的当前状态的编号，有一个switch语句根据state的值将我们转到对应于各个可能状态的相应的代码段，我们可以在那里找到该状态需要执行的动作，一个状态的代码本身常常也是一条switch语句或多路分支语句，这个语句读入并检查下一个输入字符，由此确定下一个状态
1.我们可以让词法分析器顺序地尝试各个词法单元的状态转换图2.我们可以"并行地"运行各个状态转换图3.我们可以将所有的状态转换图合并为一个图，我们允许合并后的状态转换图尽量多的读取输入，直到不存在下一个状态位置，然后去最长的和某个模式匹配的最长词素0x5:CodeExample
RelevantLink:
9.词法分析器生成工具Lex
Lex(在最新的实现中也称为Flex)，它支持使用正则表达式来描述各个词法单元的模式，由此给出一个词法分析器的规约，Lex工具的输入表示方法称为Lex语言(LexLanguage)，而工具本身则称为Lex编译器(LexCompiler)，在它的核心部分，Lex编译器将输入的模式转换成一个状态转换图，并生成相应的实现代码，存放到文件lex.yy.c中，这些代码模拟了状态转换图
0x2:Lex程序的结构
一个Lex程序具有如下形式
2.转换规则
Lex程序的每个转换规则具有如下形式
包含了各个动作需要使用的所有辅助函数
0x3:Lex中的冲突解决
Lex解决冲突的两个规则，当输入的多个前缀与一个或多个模式匹配时，Lex用如下规则选择正确的词素
1.总是选择最长的前缀2.如果最长的可能前缀与多个模式匹配，总是选择在Lex程序中先被列出的模式0x4:向前看运算符
0x5:有穷自动机
我们接下来学习Lex是如何将它的输入程序变成一个词法分析器的，转换的核心是被称为有穷自动机(finiteautomate)的表示方法，这些自动机在本质上是与状态转换图类似的图，但有如下几点不同
1.有穷自动机是识别器(recognizer)，它们只能对每个可能的输入串返回"是"、或"否"两种结果2.有穷自动机分为两类1)不确定的有穷自动机(nondeterministicfiniteautomateNFA)对其边上的标号没有任何限制，一个符号标记离开同一状态的多条边，并且空串也可以作为标号2)对于每个状态及自动机输入字母表中的每个符号，确定的有穷自动机(deterministicfiniteautomateDFA)有且只有一条离开该状态、以该符号为标号的边确定的和不确定的有穷自动机能识别的语言的集合是相同的，事实上，这些语言的集合正好是能够用正则表达式描述的语言的集合，这个集合中的语言称为正则语言(regularlanguage)
1.不确定的有穷自动机
0x6:从正则表达式到自动机
0x7:词法分析器生成工具的设计
0x8:Lex使用学习
1.Helloworld
example1.lt
%{#include
可以看到，示例程序会自动读取输入，并根据正则词法规则进行词法解析，并生成对应的Token制导结果
2.正则匹配
接下来在Lex中引用正则，本质上这也是词法分析状态机的基础
%{#include
待解析文件
logging{categorylameservers{null;};categorycname{null;};};zone"."{typehint;file"/etc/bind/db.root";};example1.lt
%{#include
YACC没有输入流的概念，它仅接受预处理过的符号集，Yacc被用作编译器的解析文析的工具。计算机语言不允许有二义性。因此，YACC在遇到有歧义时会抱怨移进/归约或者归约/归约冲突
1.入门例程
待编译文件
heatonHeateron!heatoffHeateroff!targettemperature22Newtemperatureset!example1.lt
%{#include
1.引入了头文件y.tab.h2.不再使用print函数，而是直接返回符号的名字。这样做的目的是为了接下来将它嵌入到YACC中，而后者对打印到屏幕的内容根本不关心。Y.tab.h定义了这些符号example1.y
%{#include
yacc-dexample1.y//如果调用YACC时启用了-d选项，会将这些符号会输出到y.tab.h文件lexexample1.ltgcclex.yy.cy.tab.c-oexample12.拓展温度调节器使其可处理参数
上面的示例可以正确的解析温度调节器的命令，但是它并不知道应该做什么，它并不能取到你输入的温度值接下来工作就是向其中加一点功能使之可以读取出具体的温度值。为此我们需要学习如何将Lex中的数字(NUMBER)匹配转化成一个整数，使其可以在YACC中被读取当Lex匹配到一个目标时，它就会将匹配到的文字放到yytext中。YACC从变量yylval中取值
%{#include
%{#include
1.在YACC文件中，main函数调用了yyparse()，此函数由YACC自动生成，在y.tab.c文件中2.函数yyparse从yylex中读取符号/值组成的流。你可以自己编码实现这点，或者让Lex帮你完成。在我们的示例中，我们选择将此任务交给Lex3.Lex中的yylex函数从一个称作yyin的文件指针所指的文件中读取字符。如果你没有设置yyin，默认是标准输入(stdin)。输出为yyout，默认为标准输出(stdout)4.可以在yywrap函数中修改yyin，此函数在每一个输入文件被解析完毕时被调用，它允许你打开其它的文件继续解析，如果是这样，yywarp的返回值为0。如果想结束解析文件，返回15.每次调用yylex函数用一个整数作为返回值，表示一种符号类型，告诉YACC当前读取到的符号类型，此符号是否有值是可选的，yylval即存放了其值6.默认yylval的类型是整型(int)，但是可以通过重定义YYSTYPE以对其进行重写。分词器需要取得yylval,为此必须将其定义为一个外部变量。原始YACC不会帮你做这些，因此你得将下面的内容添加到你的分词器中，就在#include
10.PHPLex(LexicalAnalyzer)
词法分析阶段就是从输入流里边一个字符一个字符的扫描，识别出对应的词素，最后把源文件转换成为一个TOKEN序列，然后丢给语法分析器PHP在最开始的词法解析器是使用的是flex，后来PHP的改为使用re2c我们通过一个简单的例子来看下re2c。如下是一个简单的扫描器，它的作用是判断所给的字符串是数字/小写字母/大小字母
#include
1.YYCTYPE:用于保存输入符号的类型，通常为char型和unsignedchar型2.YYCURSOR:指向当前输入标记，当开始时，它指向当前标记的第一个字符，当结束时，它指向下一个标记的第一个字符3.YYFILL(n):当生成的代码需要重新加载缓存的标记时，则会调用YYFILL(n)4.YYLIMIT:缓存的最后一个字符，生成的代码会反复比较YYCURSOR和YYLIMIT，以确定是否需要重新填充缓冲区0x1:RE2Cre2c-convertregularexpressionstoC/C++re2cisalexergeneratorforC/C++.ItfindsregularexpressionspecificationsinsideofC/C++commentsandreplacesthemwithahard-codedDFA.TheusermustsupplysomeinterfacecodeinordertocontrolandcustomizethegeneratedDFA.re2c本质上是一个生成词法生成器的生成器
1.Giventhefollowingcode
unsignedintstou(constchar*s){#defineYYCTYPEcharconstYYCTYPE*YYCURSOR=s;unsignedintresult=0;for(;;){/*!re2cre2c:yyfill:enable=0;"\x00"{returnresult;}[0-9]{result=result*10+c;continue;}*/}}2.re2c-iswillgenerate
unsignedintstou(constchar*s){#defineYYCTYPEcharconstYYCTYPE*YYCURSOR=s;unsignedintresult=0;for(;;){{YYCTYPEyych;yych=*YYCURSOR;if(yych<=0x00)gotoyy3;if(yych<='/')gotoyy2;if(yych<='9')gotoyy5;yy2:yy3:++YYCURSOR;{returnresult;}yy5:++YYCURSOR;{result=result*10+c;continue;}}}}SYNTAXCodeforre2cconsistsofasetofrules,nameddefinitionsandinplaceconfigurations.
0x2:PHPLexer代码分析
\php-src-master\Zend\zend_language_scanner.lzend_language_scanner.l文件是re2c的规则文件，如果安装了re2c，可以通过以下命令来生成c文件
re2c-F-c-ozend_language_scanner.czend_language_scanner.l在re2c生成的词法解析器中，有两个维度的状态机
其表达的意思就是：当我们词法解析器处于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的宏调用，例如
staticvoidyy_scan_buffer(char*str,unsignedintlen){YYCURSOR=(YYCTYPE*)str;YYLIMIT=YYCURSOR+len;if(!SCNG(yy_start)){SCNG(yy_start)=YYCURSOR;}}定位一下#defineSCNG
/*GlobalsMacros*/#defineSCNGLANG_SCNG$PHPSRC/Zend/zend_globals_macros.h
#else#defineLANG_SCNG(v)(language_scanner_globals.v)externZEND_APIzend_php_scanner_globalslanguage_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;unsignedintyy_leng;unsignedchar*yy_start;unsignedchar*yy_text;unsignedchar*yy_cursor;unsignedchar*yy_marker;unsignedchar*yy_limit;intyy_state;zend_stackstate_stack;zend_ptr_stackheredoc_label_stack;/*original(unfiltered)script*/unsignedchar*script_org;size_tscript_org_size;/*filteredscript*/unsignedchar*script_filtered;size_tscript_filtered_size;/*input/outputfilters*/zend_encoding_filterinput_filter;zend_encoding_filteroutput_filter;constzend_encoding*script_encoding;/*initialstringlengthafterscanningtofirstvariable*/intscanned_string_len;};0x4:扫描过程
词法扫描的入口在zend_language_scanner.l的intlex_scan(zval*zendlval)中
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规则处理 PHP的字符串类型在词法分析阶段应该是最复杂的，PHP里边的字符串可以由"单引号"或"双引号"来围住，单引号的字符串比双引号的字符串效率会更高 11.语法分析 在设计语言时，每种程序设计语言都有一组精确的规则来描述良构(well-formed)程序的语法结构。程序设计语言构造的语法可以使用"上下文无关文法"、或者"BNF范式"表示法来描述。文法为语言设计者和编译器编写者都提供了很大的便利 1.文法给出了一个程序设计语言的精确易懂的语法规约2.对于某些类型的文法，我们可以自动地构造出高效的语法分析器，它能够确定一个源程序的语法结构。同时，语法分析器的构造过程可以揭示出语法的二义性，同时很可能发现一些容易在语言的初始设计阶段被忽略的问题3.一个正确设计的文法给出了一个语言的结构，该结构有助于把源程序翻译为正确的目标代码，也有助于检测错误4.一个文法支持逐步加入可以完成新任务的新语言构造从而迭代地演化和开发语言0x1:引论 1.语法分析器的作用 在我们的编译器模型中，语法分析器从词法分析器获得一个由词法单元组成的串，并验证这个串可以由源语言的文法生成，对于良构的程序，语法分析器构造出一棵语法分析树，并把它传递给编译器的其他部分进一步处理，实际上，并不需要显示地构造出这课语法分析树，这仅仅是在内存中的一个数据结构处理文法的语法分析器大体上可以分为几种类型 2.代表性的文法 下面的文法指明了运算符的结合性和优先级 E->E+T|T//E表示一组以+号分隔的项所组成的表达式T->T*F|F//T表示由一组以*分隔的因子所组成的项F->(E)|id//F表示因子，它可能是括号括起来的表达式，也可能是标识符3.语法错误的处理 程序可能有不同层次的错误 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，那么这个文法就是左递归的(leftrescursive)，自顶向下语法分析方法不能处理左递归的文法，因此需要一个转换方法来消除左递归，同时，这样的替换不能改变可从A推导得到的串的集合 4.提取左公因子 提取左公因子是一种文法转换方法，它可以产生适用于预测分析技术或自顶向下分析技术的文法。当不清楚应该在两个A产生式中如何选择时，我们可以通过改写产生式来推后这个决定，等我们读入了足够多的输入，获得足够信息后再做出正确选择 5.非上下文无关语言的构造 0x4:自顶向下的语法分析 自顶向下语法分析可以被看作是为输入串构造语法分析树的问题，它从语法分析树的根节点开始，按照先根次序(深度优先)创建这课语法分析树的各个结点，自顶向下语法分析也可以被看作寻找输入串的最左推导的过程在一个自顶向下语法分析的每一步中，关键问题是确定对一个非终结符号(例如A)应用哪个产生式，一旦选择了某个A产生式，语法分析过程的其余部分负责将相应产生式体中的终结符号和输入相匹配 1.递归下降的语法分析 一个递归下降语法分析程序由一组过程组成，每个非终结符号有一个对应的过程(产生式翻译过程)，程序的执行从开始符号对应的过程开始，如果这个过程的过程体扫描了整个输入串，它就停止执行并宣布语法分析成功完成 voidA(){选择一个A产生式,A->X1X2..Xk;for(i=1tok){if(Xi是一个非终结符号)调用过程Xi();elseif(Xi等于当前的输入符号a)读入下一个输入符号;else/*发生了一个错误*/}}通用的递归下降分析技术可能需要回溯，也就是说，它可能需要重复扫描输入，然而，在对程序设计语言的构造进行语法分析时很少需要回溯，因此需要回溯的语法分析器并不常见，即使在自然语言语法分析这样的场合，回溯也不是很高效，因此我们更倾向于基于表格的方法，例如动态程序规划算法或者Earley方法 2.FIRST和FOLLOW 1.如果X是一个终结符号，那么FIRST(X)=X2.如果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会使用下面的两个规则来解决所有的语法分析动作冲突 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的错误恢复使用了错误产生式的形式 12.构造可配置词法语法分析器生成器 13.基于PHPLexer重写一份轻量级词法分析器 我们以PHP命令行模式为切入点，理解PHP从接收输入到词法分析的全过程 D:\wamp\bin\php\php5.5.12\php.exe-ftest.php//执行文件 $PHPSRC/sapi/cli/php_cli.c ..case'f':/*parsefile*/if(behavior==PHP_MODE_CLI_DIRECT||behavior==PHP_MODE_PROCESS_STDIN){param_error=param_mode_conflict;break;}elseif(script_file){param_error="Youcanuse-fonlyonce.\n";break;}script_file=php_optarg;break;..casePHP_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 PHPAPIintphp_execute_script(zend_file_handle*primary_file){zend_file_handle*prepend_file_p,*append_file_p;zend_file_handleprepend_file={{0},NULL,NULL,0,0},append_file={{0},NULL,NULL,0,0};..if(CG(start_lineno)&&prepend_file_p){intorig_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_APIintzend_execute_scripts(inttype,zval*retval,intfile_count,...)/*{{{*/{va_listfiles;inti;zend_file_handle*file_handle;zend_op_array*op_array;va_start(files,file_count);for(i=0;i D:\wamp\bin\php\php5.5.12\php.exe-stest.php//PHP的词法解析过程通过文件操作完成，通过指针移动，逐个从文件中抽取出一个"状态机匹配命中Token"，然后输出给语法分析器，在语法高亮逻辑这里，语法分析器就是一个HTML高亮显示器，并没有做多余的语法分析$PHPSRC/sapi/cli/php_cli.c ..case's':/*generatehighlightedHTMLfromsource*/if(behavior==PHP_MODE_CLI_DIRECT||behavior==PHP_MODE_PROCESS_STDIN){param_error="Sourcehighlightingonlyworksforfiles.\n";break;}behavior=PHP_MODE_HIGHLIGHT;break;..casePHP_MODE_HIGHLIGHT:{zend_syntax_highlighter_inisyntax_highlighter_ini;if(open_file_for_scanning(&file_handle)==SUCCESS){php_get_highlight_struct(&syntax_highlighter_ini);zend_highlight(&syntax_highlighter_ini);}gotoout;}break;..我们接下里从PHP打开待执行文件、词法解析、返回Token词素几个部分逐步理解PHP的词法分析过程 0x1:PHP打开待执行文件 ..zend_file_handlefile_handle;..open_file_for_scanning(&file_handle)..1.Zend引擎的全局宏定义 2.全局宏定义对应的数据结构 1.PHP是一门动态的弱类型语言2.PHP的写机制里会使用内存处理的引用计数的复本3.PHP变量，通常来说，由两部分组成：标签(例如，可能是符号表中的一个条目)和实际变量容器4.变量容器，在代码中称为zval，掌握了所需处理变量的所有数据。包括1)实际值2)当前类型3)统计指向此容器的标签的数量4)指示这些标签是引用还是副本的标志注意到zval_struct->zend_valuevalue成员，它是一个联合体 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_funcsiterator_funcs;我们在创建类的时候，可以重载这些函数 4.PHP的变量传递 我们知道，PHP的变量传递是引用传递的，通过ZVAL机制，PHP内核在处理变量传递赋值的时候只是将新变量同样指向被赋值的引用，同时将被赋值的引用计数加1，这在copy_string的实现机制中可以看出来 staticzend_always_inlinezend_string*zend_string_copy(zend_string*s){if(!IS_INTERNED(s)){GC_REFCOUNT(s)++;}returns;}5.PHP的哈希表实现PHP内核中的哈希表是十分重要的数据结构，PHP的大部分的语言特性都是基于哈希表实现的，例如 1.变量的作用域2.函数表3.类的属性、方法等4.Zend引擎内部的很多数据都是保存在哈希表中的数据结构及说明 PHP中的哈希表是使用拉链法来解决冲突的，具体点讲就是使用链表来存储哈希到同一个槽位的数据，Zend为了保存数据之间的关系使用了双向列表来链接元素PHP中的哈希表实现在Zend/zend_hash.c中，PHP使用如下两个数据结构来实现哈希表，HashTable结构体用于保存整个哈希表需要的基本信息，而Bucket结构体用于保存具体的数据内容 typedefstruct_hashtable{uintnTableSize;//hashBucket的大小，最小为8，以2x增长。uintnTableMask;//nTableSize-1，索引取值的优化uintnNumOfElements;//hashBucket中当前存在的元素个数，count()函数会直接返回此值ulongnNextFreeElement;//下一个数字索引的位置Bucket*pInternalPointer;//当前遍历的指针（foreach比for快的原因之一）Bucket*pListHead;//存储数组头元素指针Bucket*pListTail;//存储数组尾元素指针Bucket**arBuckets;//存储hash数组dtor_func_tpDestructor;//在删除元素时执行的回调函数，用于资源的释放zend_boolpersistent;//指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。unsignedcharnApplyCount;//标记当前hashBucket被递归访问的次数（防止多次递归）zend_boolbApplyProtection;//标记当前hash桶允许不允许多次访问，不允许时，最多只能递归3次#ifZEND_DEBUGintinconsistent;#endif}HashTable;哈希表初始化 数据容器:槽位 typedefstructbucket{ulongh;//对char*key进行hash后的值，或者是用户指定的数字索引值uintnKeyLength;//hash关键字的长度，如果数组索引为数字，此值为0void*pData;//指向value，一般是用户数据的副本，如果是指针数据，则指向pDataPtrvoid*pDataPtr;//如果是指针数据，此值会指向真正的value，同时上面pData会指向此值structbucket*pListNext;//整个hash表的下一元素structbucket*pListLast;//整个哈希表该元素的上一个元素structbucket*pNext;//存放在同一个hashBucket内的下一个元素structbucket*pLast;//同一个哈希bucket的上一个元素//保存当前值所对于的key字符串，这个字段只能定义在最后，实现变长结构体chararKey[1];}Bucket;如上面各字段的注释。h字段保存哈希表key哈希后的值。这里保存的哈希值而不是在哈希表中的索引值，这是因为如下原因 1.索引值和哈希表的容量有直接关系，如果哈希表扩容了，那么这些索引还得重新进行哈希在进行索引映射，这也是一种优化手段2.在PHP中可以使用字符串或者数字作为数组的索引。数字索引直接就可以作为哈希表的索引，数字也无需进行哈希处理。h字段后面的nKeyLength字段是作为key长度的标示，索引是数字的话，则nKeyLength为03.在PHP数组中如果索引字符串可以被转换成数字也会被转换成数字索引。所以在PHP中例如'10'，'11'这类的字符索引和数字索引10，11没有区别(但是这里涉及到一个转换约定)结构体的最后一个字段用来保存key的字符串，而这个字段却申明为只有一个字符的数组，其实这里是一种长见的变长结构体，主要的目的是增加灵活性。以下为哈希表插入新元素时申请空间的代码 p=(Bucket*)pemalloc(sizeof(Bucket)-1+nKeyLength,ht->persistent);if(!p){returnFAILURE;}memcpy(p->arKey,arKey,nKeyLength);如代码，申请的空间大小加上了字符串key的长度，然后把key拷贝到新申请的空间里。在后面比如需要进行hash查找的时候就需要对比key这样就可以通过对比p->arKey和查找的key是否一样来进行数据的查找。申请空间的大小-1是因为结构体内本身的那个字节还是可以使用的在PHP5.4中将这个字段定义成constchar*arKey类型了 PHP的内存管理器是分层(hierarchical)的，这个管理器共有三层 1.存储层(storage)2.堆(heap)层3.emalloc/efree层存储层(storage) 存储层通过malloc()、mmap()等函数向系统真正的申请内存，并通过free()函数释放所申请的内存。存储层通常申请的内存块都比较大，这里申请的内存大并不是指storage层结构所需要的内存大，只是堆层通过调用存储层的分配方法时，其以段的格式申请的内存比较大，存储层的作用是将内存分配的方式对堆层透明化 4种内存方案 PHP在存储层共有4种内存分配方案 14.在Opcode层面进行语法还原WEBSHELL检测 1.filename:zend_op_array->filename2.opcode名称:opcodes[op.opcode].name3.表达式计算结果:opcodes[op.opcode].result4.参数1:opcodes[op.opcode].op1_type,opcodes[op.opcode].op15.参数2:opcodes[op.opcode].op2_type,opcodes[op.opcode].op2但是这种方案也存在一个问题，Zend把PHP用户态源代码翻译为Opcode汇编源代码之后，用户态语法层面的特征已经被极大地弱化了，例如if、foreach这类语法会翻译为了if/goto这种形态的汇编模式随之而来的，如果要在Opcode汇编层面进行代码优化、还原、甚至是Opcode反转用户态代码，都是十分困难的