lang

https://github.com/xiazemin/graphviz https://www.jianshu.com/p/e44885a777f0

https://www.jianshu.com/p/37573261d3cf https://blog.csdn.net/marlonyao/article/details/83816299

hive是使用antlr来解析的

https://www.cntofu.com/book/115/line-between-lexer-and-parser.md https://blog.csdn.net/qq_36616602/article/details/85858133 1.安装IDEA. 2.在File-Settings-Plugins中安装ANTLR v4 grammar plugin插件. 3.新建一个Maven项目，在pom.xml文件中添加ANTLR4插件和运行库的依赖，注意一定要用最新版的。

项目流程 新建一个g4文件，在里面写入要识别语言的词法规则和语法规则      .

https://github.com/antlr/antlr4 https://www.cntofu.com/book/115/index.html

Graphviz （Graph Visualization Software的缩写）是一个由AT&T实验室启动的开源工具包，用于绘制DOT语言脚本描述的图形。它也提供了供其它软件使用的库。Graphviz是一个自由软件，其授权为Common Public License。其Mac版本曾经获得2004年的苹果设计奖。Graphviz包括很多命令行工具，dot命令是一个用来将生成的图形转换成多种输出格式的命令行工具，其输出格式包括PostScript，PDF，SVG，PNG，含注解的文本等等。neato命令用于spring model的生成（在Mac OS版本中称为energy minimized）。twopi命令用于放射状图形的生成。circo命令用于圆形图形的生成。fdp命令另一个用于生成无向图的工具。dotty命令一个用于可视化与修改图形的图形用户界面程序。lefty命令是一个可编程的(使用一种被EZ影响的语言[4])控件，它可以显示DOT图形，并允许用户用鼠标在图上执行操作。Lefty可以作为MVC模型的使用图形的GUI程序中的视图部分。 DOT语言是一种文本图形描述语言。它提供了一种简单的描述图形的方法，并且可以为人类和计算机程序所理解。DOT语言文件通常是具有.gv或是.dot的文件扩展名。本文将主要介绍从源代码安装Graphviz工具以及dot命令的使用方式 Graphviz （Graph Visualization Software的缩写）是一个由AT&T实验室启动的开源工具包，用于绘制DOT语言脚本描述的图形。它也提供了供其它软件使用的库。Graphviz是一个自由软件，其授权为Common Public License。其Mac版本曾经获得2004年的苹果设计奖。Graphviz包括很多命令行工具，dot命令是一个用来将生成的图形转换成多种输出格式的命令行工具，其输出格式包括PostScript，PDF，SVG，PNG，含注解的文本等等。neato命令用于spring model的生成（在Mac OS版本中称为energy minimized）。twopi命令用于放射状图形的生成。circo命令用于圆形图形的生成。fdp命令另一个用于生成无向图的工具。dotty命令一个用于可视化与修改图形的图形用户界面程序。lefty命令是一个可编程的(使用一种被EZ影响的语言[4])控件，它可以显示DOT图形，并允许用户用鼠标在图上执行操作。Lefty可以作为MVC模型的使用图形的GUI程序中的视图部分。 DOT语言是一种文本图形描述语言。它提供了一种简单的描述图形的方法，并且可以为人类和计算机程序所理解。DOT语言文件通常是具有.gv或是.dot的文件扩展名。本文将主要介绍从源代码安装Graphviz工具以及dot命令的使用方式。

https://github.com/Tencent/rapidjson http://miloyip.github.io/rapidjson/md_doc_internals.html#IterativeParser https://github.com/miloyip/nativejson-benchmark

https://github.com/xiazemin/json-parser

https://zhuanlan.zhihu.com/p/22457315 https://github.com/miloyip/json-tutorial 从零开始写一个 JSON 库，其特性如下：

RTTI（Run-Time Type Identification)，通过运行时类型信息程序能够使用基类的指针或引用来检查这些指针或引用所指的对象的实际派生类型。 RTTI 翻译过来是运行时类型信息。一个引用不仅可以指向和自己类型一致的对象，还可以指向自己子类的对象。那么JVM在执行代码时是如何判定引用指向的对象是否合法？这时就需要用到RTTI。 如何查看RTTI 查看一个引用的RTTI和class对象密不可分，这个对象是一个特殊对象，和类同生共死。class对象中包含了类的所有信息，比如类名。当我们编译一个类后，编译器会生成相应的class对象，并将该类和class对象一同写到了.class文件中。当类加载器加载类时会连同class对象一同加载到内存。而当我们创建对象时，JVM虚拟机是根据class对象创建出普通对象。因此，普通对象中将会持有class对象的引用。现在事情就很简单了，JVM通过引用找到普通对象，通过普通对象中的引用找到class对象，通过class对象查到了类信息，这时一个引用的RTTI就被获得了。

对于Mixin(混合)、Trait（特性）这两个面向对象特性，总是让人觉得说不清道不明的感觉，其实众多设计语言里，这里面的一些概念也是相互参杂的，并不是又那么一个严格的定义或界限说哪种一定是Mixin，或者哪种一定是Trait。这两种语言设施的提出，它的本质实际上都是解决代码复用的问题。

On pp 590-593 of Programming in Scala this is discussed in more detail: basically the react method never returns normally (it terminates with an exception) and therefore its call stack does not need to be preserved. You can think of it as looping forever.

Mixin 就是 混入的意思，主要是为了解决多重继承 带来复杂继承链的问题，或者说是多重继承实现的一种技巧 https://www.liaoxuefeng.com/wiki/897692888725344/923030524000032 https://www.zhihu.com/question/20778853 Mixin 在设计类的继承关系时，通常，主线都是单一继承下来的，例如，Ostrich继承自Bird。但是，如果需要“混入”额外的功能，通过多重继承就可以实现，比如，让Ostrich除了继承自Bird外，再同时继承Runnable。这种设计通常称之为Mixin。

https://github.com/ngs-doo/dsl-json https://github.com/emilsjolander/goson dsl库 具有高级编译时间数据绑定支持的最快 JVM (Java/Android/Scala/Kotlin) 库。 DSL平台兼容。

基本参数 最简单的获取函数调用者传递过来的参数便是使用 zend_parse_parameters() 函数。 zend_parse_parameters() 函数的前几个参数我们直接用内核里的宏来生成便可以了，形式为：ZEND_NUM_ARGS() TSRMLS_CC，注意两者之间有个空格，但是没有逗号。从名字可以看出，ZEND_NUM_ARGS() 代表着参数的个数。紧接着需要传递给 zend_parse_parameters() 函数的参数是一个用于格式化的字符串，就像 printf 的第一个参数一样。下面列出了最常用的几个符号：

在PHP开发中使用扩展会大大提高编码和运行效率，但在使用过程中（尤其是一些开源扩展）难免遇到各种各样的问题，其中一个就是模块间冲突或依赖

1.从物理机说起 虚拟机也是计算机，设计思想和物理机有很多相似之处；

全部视频：https://segmentfault.com/a/11…

https://www.cnblogs.com/driftcloudy/p/3296525.html https://www.cnblogs.com/driftcloudy/p/5400994.html

phpize的作用可以这样理解：侦测环境(phpize工具是在php安装目录下,基于这点phpize对应了当时的php环境，所以是要根据该php的配置情况生成对应的configure文件)，建立一个configure文件。必须在一个目录下去运行phpize。那么phpize就知道你的的环境是哪个目录，并且configure文件建立在该目录下。

合并数组 array_merge和+对数组操作的区别 1.在数组的键值为数字形式时： array_merge不会对数据产生覆盖，重新进行索引； ‘+’在后面的数组中与前面数组的键相同时，舍弃后面的数组。 <?php $arrone = array(‘qwer’, ‘qaz’); $arrtwo = array(‘qwerqwer’, ‘qazqaz’); $arrtwo2 = array(‘qwerqwer’, 5=>’qazqaz’);

PHP数组底层数据结构

首先include和require都是引入指定的文件。_once表示只引入一次，即之前已经引入过的不再引入。 nclude与require的区别 1、加载失败的处理方式不同 include与require除了在处理引入文件的方式不同外，最大的区别就是： include在引入不存文件时产生一个警告且脚本还会继续执行， require则会导致一个致命性错误且脚本停止执行。

php扩展里 PHP_MINIT_FUNCTION， PHP_MSHUTDOWN_FUNCTION， PHP_RINIT_FUNCTION PHP_RSHUTDOWN_FUNCTION 这4个函数的。 发现在 php-fpm里执行的过程是这样的。

•gzencode 默认使用ZLIB_ENCODING_GZIP编码，使用gzip压缩格式，实际上是使用defalte 算法压缩数据，然后加上文件头和adler32校验 •gzdeflate 默认使用ZLIB_ENCODING_RAW编码方式，使用deflate数据压缩算法，实际上是先用 LZ77 压缩，然后用霍夫曼编码压缩 •gzcompress ；默认使用ZLIB_ENCODING_DEFLATE编码，使用zlib压缩格式，实际上是用 deflate 压缩数据，然后加上 zlib 头和 CRC 校验

类型系统被采用并被作为类型检查的一种手段，从二十世纪五十年代的FORTRAN语言编译器就已开始。采用类型论（type theory）观点的编程语言类型系统的研究，在软件工程、编程语言设计、高性能编译器和网络安全等方面都有重要应用. 2.类型系统（type system） 2.1定义

一、前言 每个编程语言都存在变量类型和类型之间的转换问题，一般很多书籍都提供了类型之间怎样进行转换的知识，但是很少介绍这些类型转换的背后原理。有人会问，我只要知道怎样进行转换这些类型就可以了，有必要了解这些知识么？我的觉得还是很有必要了解，只有了解了这些类型转换的原理，我们在编程时才能避免一些坑。例如：

php5 中使用双向链表实现插入数据的有序性 php7 使用映射表实现数据的有序性，hash key 得到桶的位置，桶中存储插入顺序，实际数据按照顺序存储 在 PHP7中，我们往数组中插入元素的顺序，就决定了我们数组遍历元素的顺序。可以说，PHP7中的数组是有序的。这个有序就是指元素插入数组时的顺序，与遍历时顺序的一致性。为了直观地让大家了解到PHP7数组的有序性，请看下面一段PHP代码：

JS 中的最大安全整数是多少？ JS 中所有的数字类型，实际存储都是通过 8 字节 double 浮点型 表示的。浮点数并不是能够精确表示范围内的所有数的， 虽然 double 浮点型的范围看上去很大: 2.23x10^(-308) ~ 1.79x10^308。 可以表示的最大整数可以很大，但能够精确表示，使用算数运算的并没有这么大。 它其实连这样的简单加法也会算错：

　C语言的结构（struct）：包含多个成员，可能有多种数据类型，并且需要分配几种类型占用空间之和的空间。

php-fpm.conf的配置文件中有一个参数request_slowlog_timeout是这样描述的

PHP函数rand和mt_rand 　　 mt_rand() 比rand() 快四倍 　　 　　很多老的 libc 的随机数发生器具有一些不确定和未知的特性而且很慢。PHP 的 rand() 函数默认使用 libc 随机数发生器。mt_rand() 函数是非正式用来替换它的。该函数用了 Mersenne Twister (马其塞旋转) 中已知的特性作为随机数发生器，mt_rand() 可以产生随机数值的平均速度比 libc 提供的 rand() 快四倍。 mt_rand()是更好地随机数生成器，因为它跟rand()相比播下了一个更好地随机数种子；而且性能上比rand()快4倍

https://www.freebuf.com/tag/dvwa DVWA（Damn Vulnerable Web Application）是一个用来进行安全脆弱性鉴定的PHP/MySQL Web应用，旨在为安全专业人员测试自己的专业技能和工具提供合法的环境，帮助web开发者更好的理解web应用安全防范的过程。

PHP5在使用一个类时，如果发现这个类没有加载，就会自动运行__autoload()函数，在这个函数中我们可以加载需要使用的类。在我们这个简单的例子中，我们直接将类名加上扩展名”.class.php”构成了类文件名，然后使用require_once将其加载。从这个例子中，我们可以看出autoload至少要做三件事情，第一件事是根据类名确定类文件名，第二件事是确定类文件所在的磁盘路径(在我们的例子是最简单的情况，类与调用它们的PHP程序文件在同一个文件夹下)，第三件事是将类从磁盘文件中加载到系统中。第三步最简单，只需要使用include/require即可。要实现第一步，第二步的功能，必须在开发时约定类名与磁盘文件的映射方法，只有这样我们才能根据类名找到它对应的磁盘文件。

FPM源代码目录位于PHP源代码目录下的sapi/fpm

PHP5.5中加入了一个新特性—迭代生成器和协程。

所有的依赖都定义在composer.json中，手册中给出了一些基本用法和例子。你可能已经注意到，在指定版本号的时候，我们并不一定要指明一个精确的版本。那么就有可能发生这么一个情况，对于同一份composer.json，我们在不同时刻拉取到的依赖文件可能不同（因为composer会在满足条件的情况下去拉取最新的那份依赖），从而导致一些异常情况。composer update和composer install正是为了解决这个问题而出现的。 当你执行composer update的时候，composer会去读取composer.json中指定的依赖，去分析他们，并且去拉取符合条件最新版本的依赖。然后他会把所拉取到的依赖放入vendor目录下，并且把所有拉取的依赖的精确版本号写入composer.lock文件中。

__autoload的作用：当我们在一个页面使用其他文件的类方法时候，经常使用的是require ,require_once ,include,include_once,

https://github.com/composer/satis 安装satis包 cd /home/wwwroot/ composer create-project composer/satis –stability=dev –keep-vcs 添加配置文件 cd satic vim satis.json添加类似如下内容 { “name”: “My Repository”, “homepage”: “http://59.110.107.59”, “repositories”: [ {“type”: “vcs”, “url”: “https://github.com/bambooleaf/reps_demo.git”}, {“type”: “vcs”, “url”: “https://github.com/isunshines/hello-world.git”} ], “require”:{ “reps_demo/helloworld”:””, “isunshines/hellow-world”:”” }, “archive”:{ “directory”:”dist”, “format”:”tar”, “prefix-url”:”http://59.110.107.59/”, “skip-dev”:true } } 配置文件详解 name：仓库名字 homepage：主页地址 repositories：包所在地址 require：指定获取哪些包及对应的版本，获取所有包使用”require-all”: true，与包中composer.json中的名称相同，不同会出现问题 directory: 必需要的，表示生成的压缩包存放的目录，会在build时的目录中 format: 压缩包格式, zip（默认）和tar prefix-url: 下载链接的前缀的Url，默认会从homepage中取 skip-dev: 默认为假，是否跳过开发分支 absolute-directory: 绝对目录 whitelist: 白名单，只下载哪些 blacklist: 黑名单，不下载哪些 checksum: 可选，是否验证sha1 生成站点 bin/satis build satis.json ./public 服务配置 PHP服务器设置 php -S 127.0.0.1:8080 -t ./public Nginx服务配置类似如下内容

正则表达式（Regular Expression，缩写为regexp，regex或regxp)，又称正规表达式、正规表示式或常规表达式或正规化表示法或正规表示法，是指一个用来描述或者匹配一系列符合某个句法规则的字符串的单个字符串 。在很多文本编辑器或其他工具里，正则表达式通常被用来检索和/或替换那些符合某个模式的文本内容 。许多程序设计语言都支持利用正则表达式进行字符串操作。例如，在Perl中就内建了一个功能强大的在正则表达式引擎。正则表达式这个概念最初是由 Unix中的工具软件（例如sed和grep）普及开的。
PHP同时使用两套正则表达式规则，一套是由电气和电子工程师协会（IEEE）制定的POSIX Extended 1003.2兼容正则（事实上PHP对此标准的支持并不完善），另一套来自PCRE（Perl Compatible Regular Expression）库提供PERL兼容正则，这是个开放源代码的软件，作者为 Philip Hazel。

使用POSIX兼容规则的函数有：
ereg_replace()
ereg()
eregi()
eregi_replace()
split()
spliti()
sql_regcase()
mb_ereg_match()
mb_ereg_replace()
mb_ereg_search_getpos()
mb_ereg_search_getregs()
mb_ereg_search_init()
mb_ereg_search_pos()
mb_ereg_search_regs()
mb_ereg_search_setpos()
mb_ereg_search()
mb_ereg()
mb_eregi_replace()
mb_eregi()
mb_regex_encoding()
mb_regex_set_options()
mb_split()

使用PERL兼容规则的函数有：
preg_grep()
preg_replace_callback()
preg_match_all()
preg_match()
preg_quote()
preg_split()
preg_replace()

定界符：

POSIX兼容正则没有定界符，函数的相应参数会被认为是正则。

PERL兼容正则可以使用任何不是字母、数字或反斜线（\）的字符作为定界符，如果作为定界符的字符必须被用在表达式本身中，则需要用反斜线转义。也可以使用()，{}，[] 和 <> 作为定界符

修正符：

POSIX兼容正则没有修正符。

PERL兼容正则中可能使用的修正符（修正符中的空格和换行被忽略，其它字符会导致错误）：

i (PCRE_CASELESS)：
匹配时忽略大小写。

m（PCRE_MULTILINE）：
当设定了此修正符，行起始(^)和行结束($)除了匹配整个字符串开头和结束外，还分别匹配其中的换行符(\n)的之后和之前。

s（PCRE_DOTALL）：
如果设定了此修正符，模式中的圆点元字符（.）匹配所有的字符，包括换行符。没有此设定的话，则不包括换行符。

x（PCRE_EXTENDED）：
如果设定了此修正符，模式中的空白字符除了被转义的或在字符类中的以外完全被忽略。

e：
如果设定了此修正符，preg_replace() 在替换字符串中对逆向引用作正常的替换，将其作为 PHP 代码求值，并用其结果来替换所搜索的字符串。 只有 preg_replace() 使用此修正符，其它 PCRE 函数将忽略之。

A（PCRE_ANCHORED）：
如果设定了此修正符，模式被强制为“anchored”，即强制仅从目标字符串的开头开始匹配。

D（PCRE_DOLLAR_ENDONLY）：
如果设定了此修正符，模式中的行结束($)仅匹配目标字符串的结尾。没有此选项时，如果最后一个字符是换行符的话，也会被匹配在里面。如果设定了 m 修正符则忽略此选项。

S：
当一个模式将被使用若干次时，为加速匹配起见值得先对其进行分析。如果设定了此修正符则会进行额外的分析。目前，分析一个模式仅对没有单一固定起始字符的 non-anchored 模式有用。

U（PCRE_UNGREEDY）：
使“?”的默认匹配成为贪婪状态的。

X（PCRE_EXTRA）：
模式中的任何反斜线后面跟上一个没有特殊意义的字母导致一个错误，从而保留此组合以备将来扩充。默认情况下，一个反斜线后面跟一个没有特殊意义的字母被当成该字母本身。

u（PCRE_UTF8）：
模式字符串被当成UTF-8。

逻辑区隔：

POSIX兼容正则和PERL兼容正则的逻辑区隔符号作用和使用方法完全一致：
[]：包含任选一操作的相关信息。
{}：包含匹配次数的相关信息。
()：包含一个逻辑区间的相关信息，可被用来进行引用操作。
|：表示“或”，[ab]和a|b是等价的。

元字符与“[]”相关：

有两组不同的元字符：一种是模式中除了方括号内都能被识别的，还有一种是在方括号“[]”内被识别的。

POSIX兼容正则和PERL兼容正则“[]之外”“一致”的元字符：
\ 有数种用途的通用转义符
^ 匹配字符串的开头
$ 匹配字符串的结尾
? 匹配0或者1

• 匹配 0 个或多个前面指定类型的字符
• 匹配 1 个或多个前面指定类型的字符

POSIX兼容正则和PERL兼容正则“[]之外”“不一致”的元字符：
. PERL兼容正则匹配除了换行符外的任意一个字符
. POSIX兼容正则匹配任意一个字符

POSIX兼容正则和PERL兼容正则“[]之内”“一致”的元字符：
\ 有数种用途的通用转义符
^ 取反字符，但仅当其为第一个字符时有效

• 指定字符ASCII范围，仔细研究ASCII码，你会发现[W-c]等价于[WXYZ\^_`abc]

POSIX兼容正则和PERL兼容正则“[]之内”“不一致”的元字符：

• POSIX兼容正则中[a-c-e]的指定会抛出错误。
• PERL兼容正则中[a-c-e]的指定等价于[a-e]。

匹配次数与“{}”相关：

POSIX兼容正则和PERL兼容正则在匹配次数方面完全一致：
{2}：表示匹配前面的字符2次
{2,}：表示匹配前面的字符2次或多次，默认都是贪婪（尽可能多）的匹配
{2,4}：表示匹配前面的字符2次或4次

逻辑区间与“()”相关：

使用()包含起来的区域是一个逻辑区间，逻辑区间的主要作用是体现出一些字符出现的逻辑次序，另一个用处就是可以用来引用（可以将此区间内的值引用给一个变量）。后一个作用比较奇特：
<?php
$str = “http://www.163.com/”;
// POSIX兼容正则：
echo ereg_replace(“(.+)”,”<a href = \1 >\1</a>”,$str);
// PERL兼容正则：
echo preg_replace(“/(.+)/”,”<a href = $1 >$1</a>”,$str);
// 显示两个链接
?>

在引用的时候，括号是可以嵌套的，逻辑次序是按照“(”出现的次序来标定的。

类型匹配：

POSIX兼容正则：
[:upper:]：匹配所有的大写字母
[:lower:]：匹配所有的小写字母
[:alpha:]：匹配所有的字母
[:alnum:]：匹配所有的字母和数字
[:digit:]：匹配所有的数字
[:xdigit:]：匹配所有的十六进制字符，等价于[0-9A-Fa-f]
[:punct:]：匹配所有的标点符号，等价于 [.,”’?!;:]
[:blank:]：匹配空格和TAB，等价于[ \t]
[:space:]：匹配所有的空白字符，等价于[ \t\n\r\f\v]
[:cntrl:]：匹配所有ASCII 0到31之间的控制符。
[:graph:]：匹配所有的可打印字符，等价于：[^ \t\n\r\f\v]
[:print:]：匹配所有的可打印字符和空格，等价于：[^\t\n\r\f\v]
[.c.]：功能不明
[=c=]：功能不明
[:<:]：匹配单词的开始
[:>:]：匹配单词的结尾

PERL兼容正则（这里可以看出PERL正则的强大）：
\a alarm，即 BEL 字符（’0）
\cx “control-x”，其中 x 是任意字符
\e escape（’0B）
\f 换页符 formfeed（’0C）
\n 换行符 newline（’0A）
\r 回车符 carriage return（’0D）
\t 制表符 tab（’0）
\xhh 十六进制代码为 hh 的字符
\ddd 八进制代码为 ddd 的字符，或 backreference
\d 任一十进制数字
\D 任一非十进制数的字符
\s 任一空白字符
\S 任一非空白字符
\w 任一“字”的字符
\W 任一“非字”的字符
\b 字分界线
\B 非字分界线
\A 目标的开头（独立于多行模式）
\Z 目标的结尾或位于结尾的换行符前（独立于多行模式）
\z 目标的结尾（独立于多行模式）
\G 目标中的第一个匹配位置

PHP 标准规范# PSR 是 PHP Standard Recommendations 的简写，由 PHP FIG 组织制定的 PHP 规范，是 PHP 开发的实践标准。

https://packagist.org/ 国内镜像： https://pkg.phpcomposer.com/ 国内仓库 http://packagist.p2hp.com/

IG 最初由几位知名 PHP 框架开发者发起，在吸纳了许多优秀的大脑和强健的体魄后，提出了 PSR-0 到 PSR-4 五套 PHP 非官方规范： PSR-0 (Autoloading Standard) 自动加载标准 PSR-1 (Basic Coding Standard) 基础编码标准 PSR-2 (Coding Style Guide) 编码风格向导 PSR-3 (Logger Interface) 日志接口 PSR-4 (Improved Autoloading) 自动加载优化标准

ArrayObject的使用是说明 ArrayObject是将数组转换为数组对象。 $array =array(‘1’=>’one’, ‘2’=>’two’, ‘3’=>’three’);

t_generator类和t_generator_registry类

这个两个类的主要功能就是为生成所有语言的代码提供基础信息和提供具体代码生成器对象，上面就是调用这个两个类的方法来生成具体语言的代码生成器对象和执行生成代码的功能函数。下面主要分析两个函数的功能，一个是t_generator_registry类的get_generator函数，这个是一个静态的函数可以直接通过类调用；另一个是t_generator类的generate_program函数。 (1）t_generator_registry类的get_generator函数

__construct()， __destruct()， __call()， __callStatic()， __get()， __set()， __isset()， __unset()， __sleep()， __wakeup()， __toString()， __invoke()， __set_state()， __clone() 和 __debugInfo() 等方法在 PHP 中被称为魔术方法（Magic methods）。在命名自己的类方法时不能使用这些方法名，除非是想使用其魔术功能。

于是当从db里select出来一堆东西之后，还要逐个循环封装成对象，每一个字段也要实现getField()和getField()方法，写起来还真有点麻烦，感觉就是在做重复性的工作。

PHP的反射机制提供了一套反射API，用来访问和使用类、方法、属性、参数和注释等，比如可以通过一个对象知道这个对象所属的类，这个类包含哪些方法，这些方法需要传入什么参数，每个参数是什么类型等等，不用创建类的实例也可以访问类的成员和方法，就算类成员定义为 private 也可以在外部访问。 官方文档提供了诸如 ReflectionClass、ReflectionMethod、ReflectionObject、ReflectionExtension 等反射类及相应的API

前向声明的定义：有些时候我们可以声明一些类但是并不去定义它，当然这个类的作用也很有限了。

尾调用的概念非常简单，一句话就能说清楚，就是指某个函数的最后一步是调用另一个函数。 function f(x){ return g(x); } 尾调用不一定出现在函数尾部，只要是最后一步操作即可。 function f(x) { if (x > 0) { return m(x) } return n(x); } 以下两种情况，都不属于尾调用。 // 情况一 function f(x){ let y = g(x); return y; }

函数式编程是一种编程模型，他将计算机运算看做是数学中函数的计算，并且避免了状态以及变量的概念。 闭包是由函数及其相关引用环境组合而成的实体(即：闭包=函数+引用环境)。 闭包只是在形式和表现上像函数，但实际上不是函数。函数是一些可执行的代码，这些代码在函数被定义后就确定了，不会在执行时发生变化，所以一个函数只有一个实例。闭包在运行时可以有多个实例，不同的引用环境和相同的函数组合可以产生不同的实例。所谓引用环境是指在程序执行中的某个点所有处于活跃状态的约束所组成的集合。其中的约束是指一个变量的名字和其所代表的对象之间的联系。那么为什么要把引用环境与函数组合起来呢？这主要是因为在支持嵌套作用域的语言中，有时不能简单直接地确定函数的引用环境。这样的语言一般具有这样的特性： 函数是一等公民（First-class value），即函数可以作为另一个函数的返回值或参数，还可以作为一个变量的值。 函数可以嵌套定义，即在一个函数内部可以定义另一个函数。 func adder() func(int) int { sum := 0 innerfunc := func(x int) int { sum += x return sum } return innerfunc }

func main() { pos, neg := adder(), adder() for i := 0; i < 10; i++ { fmt.Println(pos(i), neg(-2*i)) } 内嵌函数innerfunc中引用到外层函数中的局部变量sum，这段代码的运行结果： 0 0
1 -2
3 -6
6 -12
10 -20
15 -30
21 -42
28 -56
36 -72
45 -90 当用不同的参数调用adder函数得到（pos(i)，neg(i)）函数时，得到的结果是隔离的，也就是说每次调用adder返回的函数都将生成并保存一个新的局部变量sum。其实这里adder函数返回的就是闭包。 这个就是Go中的闭包，一个函数和与其相关的引用环境组合而成的实体。一句关于闭包的名言: 对象是附有行为的数据，而闭包是附有数据的行为。 函数式编程具有五个鲜明的特点。

LLVM是构架编译器(compiler)的框架系统，以C++编写而成，用于优化以任意程序语言编写的程序的编译时间(compile-time)、链接时间(link-time)、运行时间(run-time)以及空闲时间(idle-time)，对开发者保持开放，并兼容已有脚本。 LLVM计划启动于2000年，最初由美国UIUC大学的Chris Lattner博士主持开展。2006年Chris Lattner加盟Apple Inc.并致力于LLVM在Apple开发体系中的应用。Apple也是LLVM计划的主要资助者。 目前LLVM已经被苹果IOS开发工具、Xilinx Vivado、Facebook、Google等各大公司采用。 LLVM 命名最早源自于底层虚拟机（Low Level Virtual Machine）的缩写,由于命名带来的混乱，目前LLVM就是该项目的全称。LLVM 核心库提供了与编译器相关的支持，可以作为多种语言编译器的后台来使用。能够进行程序语言的编译期优化、链接优化、在线编译优化、代码生成。LLVM的项目是一个模块化和可重复使用的编译器和工具技术的集合。LLVM是伊利诺伊大学的一个研究项目，提供一个现代化的，基于SSA的编译策略能够同时支持静态和动态的任意编程语言的编译目标。自那时以来，已经成长为LLVM的主干项目，由不同的子项目组成，其中许多正在生产中使用的各种 商业和开源的项目，以及被广泛用于学术研究。 http://www.llvm.org/

术语 Terminology 堆栈指针（stack pointer） 指CPU中的一个寄存器，该寄存器始终指向栈的顶部，同时也指向当前函数活动记录的顶部。在X86架构下，该寄存器是esp，在MIPS架构下，该寄存器是sp，即MIPS的32个通用寄存器中的29号寄存器（从0开始编号）。

我们已经掌握了直觉逻辑（Intuitionistic Logic，IL），我们再回到lambda演算：我们已经得到了我们需要定义模型的逻辑工具。 当然，在没有更简单的事情了，对吧？

引进「全局」函数（即在我写的这些所有的关于lambda演算的介绍里都可以直接使用，而不用在每一个表达式中都声明一次这个函数的办法），我们将使用“let”表达式：

我们在lambda演算中引入了数字，只差两件事情就可以表达任意计算了：一个是如何表达选择（分支），另一个是如何表示重复。在这篇文章中，我将讨论布尔值和选择，下一篇将介绍重复和递归。

lambda演算使用递归实现循环（递归的解释可以看这里）。 但是，由于在lambda演算里函数没有名字，我们得采取一些非常手段。这就是所谓的Y组合子，又名lambda不动点运算符。

Peter Landin1965年在论文 A Correspondence between ALGOL 60 and Church’s Lambda-notation中指出的一样，面向过程的程序设计语言在λ演算模型的体系中是可以理解的，因为它提供了基本的过程抽象和程序应用机制。 匿名函数 以Lisp中的乘方函数为例,它可以使用lambda表达式表达为： (lambda (x) (* x x)) 以上是一个可以用作头等函数的例子。在这个表达式中，lambda创造了一个匿名函数并给予了它一个参数列表(x),虽然它只有一个参数，而(* x x)则是函数的主体。这个函数在Haskell中的实现是完全一样的。匿名函数有时候也被叫做lambda表达式。 再举个例子，Pascal和其它的命令式语言 长期以来都支持将通过函数指针的机制来将子程序 作为参数传递到其它子程序里面去。然而，函数指针并不是 函数成为头等函数类型的充分条件，因为一个头等数据类型必须要能够在运行时创建出一个它的实例。而支持运行时创建函数的语言有Smalltalk,Javascript,和最近的Scala,Eiffel,C#和C++11等。 归约策略 在编程语言的理论研究中，求值策略(Evaluation strategy)是一组用来确定程序设计语言中的表达式求值的规则。求值策略主要规定了在什么时候和用什么样的顺序给函数的实际参数求值，何时把参数代换入函数内，和用怎样的形式来进行代换。通常，人们使用λ演算模型中的归约策略来建模求值策略。 无论一个表达式是否为标准状态，将这个这个表达式化为标准型所需要的工作量很大程度上依赖于归约策略的使用。而归约策略的不同又和函数式编程中的及早求值还有惰性求值之间的不同有关。 1.完全β-归约 (Full β-reduction) 任何参数在任何时候都可以被归约，其实就是没有任何的归约策略，天知道会发生什么。 2.应用次序 (Applicative order) 最右边，最内部的表达式总是首先被归约，直观上可以知道，这意味着函数的参数总是在函数调用之前就被归约了。应用次序总是企图用标准形式去调用函数，即便在很多时候这是不可能的。 大多数的程序设计语言(包括Lisp,ML和命令式语言C和Java等)都被描述为严格类型语言，意思是使用了不正确形式参数的函数是形式不正确的。它们在实际上就是使用了应用次序和传值调用归约，但通常被成为及早求值策略。 3.正常次序 (Normal order) 最左边，最外部的表达式总是首先被归约，这也就意味着无论什么时候，参数都是再被归约之前就被替换进了抽象的函数体里面了。 4.传名调用 (Call by name) 和正常次序一样，但是不会在抽象的函数体中再进行归约，比如说，λx.(λx.x)x在这个策略中是正常形式, 虽然它包含了可归约的表达式(λx.x)x 5.传值调用 只有最外部的表达式被归约:一个表达式仅仅当它的右边已经被规约为一个值了才会被归约 6.传需求调用 “传需求调用”和传名调用类似，如果函数的实参被求值了，这个值就会被存储起来已备未来使用。它产生的结果和传名调用一样；但是如果函数的这个实参被调用了多次，那么传需求调用可以提高程序运行效率。它在现实语境中也被叫做惰性求值。 并行与并发 函数式编程在一开始就是面向并发处理的，这也得益于lambda的性质，lambda演算的Church-Rosser性质意味着归约(β归约)可以以任何顺序进行，甚至是并行来进行。这意味着各种不同的非确定性归约策略都是相近的。然而，lambda演算并不提供任何直接的并行结构。一个人可以添加像Futures结构体这样的并发结构体到lambda演算中去。相关的进程代数已经为了进程通信和并发而被研究了出来。 在λ-演算的基础上，发展起来的π-演算、χ-演算，成为近年来的并发程序的理论工具之一，许多经典的并发程序模型就是以π-演算为框架的。

计算机科学，尤其是编程语言，经常倾向于使用一种特定的演算：Lambda演算（Lambda Calculus）。这种演算也广泛地被逻辑学家用于学习计算和离散数学的结构的本质。Lambda演算伟大的的原因有很多，其中包括：

尾递归和一般的递归不同在对内存的占用，普通递归创建stack累积而后计算收缩，尾递归只会占用恒量的内存（和迭代一样）

抽象语法树的观点认为任何复杂的语句嵌套情况都可以借助于树的形式加以描述。确实，不得不承认应用抽象语法树可以使语句翻译变得相对容易，它很好地描述了语句、表达式之间的联系。不过，由于Neo Pascal并不会显式构造抽象语法树，所以不得不借助于其他数据结构实现。根据先前的经验，栈结构就是不二之选。 DAG（有向无环图） 后缀表达式：也称为逆波兰表达式，这种形式简单明晰，便于存储。在处理表达式翻译时，后缀表达式有着其他形式无法比拟的优势。不过，由于后缀表达式的应用领域比较单一，所以很少独立作为一个实际编译器的IR存在。

1. 后缀表达式 不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：(2 + 1) * 3 ， 即2 1 + 3 * 1.1. 前缀记法、中缀记法和后缀记法 它们都是对表达式的记法，因此也被称为前缀记法、中缀记法和后缀记法。它们之间的区别在于运算符相对与操作数的位置不同：前缀表达式的运算符位于与其相关的操作数之前；中缀和后缀同理。

堆栈机是一种计算机。在某些情况下，该术语是指模拟堆栈机器的软件方案。与其他计算机的主要区别在于它的大部分指令都是在一个数字下拉堆栈上运行，而不是寄存器中的数字。堆栈计算机使用反向波兰语表示法 指令集进行编程。大多数计算机系统以某种形式实现堆栈以传递参数并链接到子例程。这不会使这些计算机堆叠机器。

Pushdown Automation 下推自动机﹙PDA﹚是自动机理论中定义的一种抽象的计算模型。下推自动机比有限状态自动机复杂：除了有限状态组成部分外，还包括一个长度不受限制的栈；下推自动机的状态迁移不但要参考有限状态部分，也要参照栈当前的状态；状态迁移不但包括有限状态的变迁，还包括一个栈的出栈或入栈过程。 技术原理编辑 下推自动机可以形象的理解为，把有限状态自动机扩展使之可以存取一个栈。每一个下推自动机都接受一个形式语言。下推自动机存在确定与非确定两种形式，两者并不等价。﹙对有限状态自动机两者是等价的﹚被非确定下推自动机接受的语言是上下文无关语言。 基本特征编辑 如果把下推自动机扩展，允许一个有限状态自动机存取两个栈，我们得到一个能力更强的自动机，这个自动机与图灵机等价。 下推自动机 M 是如下的一个七元组 ( Q, Σ, Γ, δ, q0, Z0, F ) ，其中：

• Q 是一个有穷状态集合；
• Σ 是一个字母表，称为输入字母表。
• Γ 是一个字母表，称为栈字母表。
• q0 属于 Q ，是初始状态。
• Z0 属于 Γ ，是一个特殊的栈符号，称为栈起始符号。
• F 包含于 Q ，是终结状态集合。
• δ : Q×(Σ∪{ε})×Γ -> Q×Γ* 是 M 的动作函数。[1] 半环方法编辑 在给出下推自动机的定义之前先做如下的约定:Q, Γ同上面一致 , Q , Γ, Γ中的元素分别表示为 :q , Z ,π,其中 Γ的克林闭包 Γ =Γ0∪ Γ∪ Γ2∪ Γ3∪ … ,这里 Γ0 ={ε}, π同字符表中的字的概念类似叫作栈符号下推转换矩阵[ 2] :一个矩阵 M ∈(P(∑ ∪ ε)Q×Q)JΓ×Γ如果对所有的 π1 , π2 ∈ Γ,有 ,Mπ1=Zπ4,π2=π3π4 =MZ ,π3 　Z ∈ Γ, π4 ∈ Γ0则称该矩阵为下推转换矩阵.对任意 Z , 非零矩阵块 MZ ,π表示栈顶符号 Z 出栈, 栈符号表上的字 π入栈.(由于下推自动机也是无穷语言的一种有穷描述机制 ,故描述它动作的下推转换矩阵也必是有限个非零块矩阵组成 ,也就是说下推转换矩阵必是行列有限的 .)J 表示矩阵是行列有限矩阵 .由下推转换矩阵的定义可知下推转换矩阵是一个分块矩阵,它的每一个分块 Mπ1,π2, π1 , π2 ∈Γ是一个 P(∑ ∪ε)Q×Q矩阵 .进一步直观地来理解下推转换矩阵:假设下推栈包含 Zπ,三元组(q , a , Z)其中 a∈ ∑ ∪ ε, 它表示自动机在状态 q , 栈顶符号为 Z , 读入字符为 a ,与上面自动机的动作一样 :状态 q 变为 q1 ,栈顶符号 Z 弹出 ,并将 π1 中的符号从右到左依次压入栈 ,然后将读头向右移动一个字符而指向字符串的下一个字符,记为状态(q1 , π1).下推转换矩阵表示为 : a ∈ (MZπ′,π1π′)q, q1 () 特别地下推转换矩阵的定义要确保与 π′无关()这一条件的满足 .称((q , Zπ′),(q1 , π1 π′))是用 a 标记的边 .边的标记也就是字母表上的字母 .状态(q , π)到(q′, π′)的一条路是 c ,它是边的有序序列 :((q0 , π0),(q1 , π1))((q1 , π1),(q2 , π2)), …,((qk-1 , πk-1)(qk , πk)), k ≥0 且(q0 , π0)=(q, π), (qk , πk)=(q′, π′),记为 c ∶(q , π)※(q′, π′),并称 k 为路c 的长度, 记为 c .如果 at 是边((qt-1 , πt-1),(qt , πt))的标记,1 ≤t ≤k ,则称 a1a2 …ak 为路c 的标记 ,记为‖c‖ , 也就是 ‖c ‖ =a1 a2 …ak .路的标记也就是字母表中的字.对于每个状态(qt , πt),((qt , πt),(qt , πt))的路称作空路 ,记为 λt ,并有 λt =0 , ‖λt ‖ =ε若c ∶(q1 , π1)※(q2 ,π2), d ∶(q2 , π2)※(q3 , π3)是路 ,则它们的合成(也就是字母表的乘法)定义为 cd ∶(q1 , π1)※(q3 , π3), 且有cd = c + d , ‖cd ‖ =‖c ‖ ‖d ‖ .从而在上面的基础上给出下推自动机在半环中的定义 .下推自动机 :A=(Q , ∑ , Γ, M , q0 , Z0 ,F)其中, M 是下推转换矩阵, 其他符号同上面下推自动机的定义相同 .下推自动机 A=(Q, ∑ , Γ, M , q0 , Z0 ,F)的行为‖A‖ ∈ P(∑)定义为 :‖A‖ = ∪qf∈F ∑∞k=0 c∶(q ∑ i0,Z0)※(qf,ε),|c|=k‖c ‖ ,如果 w ∈ ‖A‖ ,则称 w 被‖A‖接收或者产生.下面将给出下推转移矩阵和下推自动机行为之间的关系:(M)kπ1,π2 q1, q2 是所有长度为 k 的路c ∶(q1 ,π1)※(q2 , π2)的标记 ,即 (M)kπ1,π2q1, q2 =c(q ∑ 1,π1)※(q2,π2),|c|=k‖c ‖ .对 k 实施数学归纳法证明 :这里要用到半环同构即任意的 M′∈ 〈P(∑)(Q×Γ)×(Q×Γ)J , +, · , 0 , E′〉, 必有 M′(q1, π1),(q2,π2) =(Mπ1, π2 )q1, q2, 其中M ∈〈P(∑)(Q×Γ)×(Q×Γ)J , +, · , 0 , E′〉.当 k =0 时 ,(M0π1, π2 )q1, q2 =M′0(q1,π1),(q2, π2) =E′(q1,π1),(q2, π2=δ(q1, π1),(q2π2)ε, 同时 c∶(π ∑ 1, q1)※(π2, q2),|c|=0‖c‖ =δ(q1, π1),(q2,π2)ε,所以 k =0 结论成立.假设对 k -1 ,k ≥1 结论成立, 则(M)kπ1,π2q1, q2 =M′k(q1,π1),(q2,π2)=(M′k-1 M′)(q1,π1),(q2,π2)=(q,π)∑∈Q×ΓM′k-1(q1,π1 ),(q,π)M′(q, π),(q2, π2) =(q,π)∑∈Q×Γ c ∑ 1∶(q1,π1)※(q,π),|c|=k-1‖c1 ‖c ∑ 2:(q,π)※(q2,π2),|c|=1‖c2 ‖ =(q,π)∑∈Q×Γ* c ∑ 1∶(q1,π1)※(π, q),|c|=k-1c ∑ 2∶(q, π)※(q2, π2),|c|=1‖c1c2 ‖ =c∶(q,π)※(∑q′,π′),|c|=k‖c ‖下推转换矩阵和移动函数的等价性 :任意 w ∈((M)kπ0,πk)q0, qk, 存在即时描述序列(q0 , a0 w0 , π0),(q1 , a2 ,w1 , π1), … ,(qk ,ε, πk),其中当 i ≤j 时, wj 是 w i 的后缀, 且 w =a0a1 …ak-1 .读完字 w 后, 自动机 A从状态(q0 , π0)转移到(qk , πk),即从 q0 转变为 qk ,同时下推栈的符号串由 π0 替换为 πk .这个序列用移动函数来描述为: δ(q0 , a0 , π0)※(q1 , π1), δ(q1 , a1 ,π1)※(q2 , π2), …, δ(qk-1 , ak-1 , πk-1)※(qk ,πk).[1] 查询研究编辑 基于下推自动机的 XML 数据流递归查询研究 可扩展标记语言(XML)由于其易用性和强大的复杂数据描述能力，已逐渐成为因特网上数据交换的标准。很多流行的数据库引擎已经开始通过增加对于这种新数据类型以及相关操作的支持来满足新的需求。XML数据流上的应用是XML研究的一个很重要的方面，在新的基于Web的应用场景下，有研究已经提出，有效地处理XML数据流[1-3]上的XPath、XQuery查询将会成为下一代信息系统的特点。可扩展标记语言(XML)由于其易用性和强大的复杂数据描述能力，已逐渐成为因特网上数据交换的标准。很多流行的数据库引擎已经开始通过增加对于这种新数据类型以及相关操作的支持来满足新的需求。XML数据流上的应用是XML研究的一个很重要的方面，在新的基于Web的应用场景下，有研究已经提出，有效地处理XML数据流[1-3]上的XPath、XQuery查询将会成为下一代信息系统的特点。出现了存在递归结构的 XML 数据流，如果当包含和谓词的XPath对它进行递归查询，将会发生多重匹配从而产生大量的匹配模式，需要花费大量的时间和空间管理这些匹配模式，这样会严重影响到查询处理的性能。面对这种情况，提出一种基于下推自动机技术的处理方法，能有效地实现XML数据流的递归查询。 1.1 XML 数据流递归查询 定义 1 XML 数据流对应的文档树结构中，从根到叶子的路径上，相同名字的元素结点重复出现，我们称作递归的XML 数据流[6]，在数据流中，所有从根到叶子的路径当中，相同名字的元素结点重复出现次数的数目称作元素结点的递归深度，符号为 R。 定义 2 在查询 XML 数据流时，相互嵌套的不同深度的XML 元素可能会匹配 XPath 查询表达式的同一个置步，这种现象称为多重匹配。 2 基于 PDA 的递归查询 N0N1 … Nn/O 作为查询表达式最通用的表示方式，Ni表示XPath 的置步，O 表示查询结果的输出形式。由于 XPath 由许多置步组成，查询目的是通过这些置步来定位 XML 文档片段。置步处理模块作为整个查询模型的基本组成部分，它是由 XPath 每个置步转化而来，该模块实质是一个状态集，这些状态包括主干路径匹配状态和谓词匹配状态，并且有模块运行的开始状态，状态之间用箭头连接在一起，箭头上标示了跳转条件，如果置步中存在谓词，主干路径匹配状态中有属性为TRUE 的状态，表明主干路径匹配和谓词检验成功；另外主干路径匹配状态中有属性为 FALSE 的状态，表明主干路径匹配成功和谓词检验不成功；如果置步中不存在谓词，则主干路径匹配状态中只有属性为 TRUE 的状态，表明主干路径匹配和谓词检验成功，这样与谓词存在的情况有良好的衔接。图 3是置步/person[name.text() = lee]转化成处理模块的一个实例，S0 是整个模块处理的开始状态，其中S0、S1 和S3 是主干路径匹配状态，其它状态是谓词匹配状态。标示的箭头，表示只有 Person 元素的开始事件才能通过箭头到达所指状态，</person>标示的箭头，表示只有 Person 元素的结束事件才能通过箭头到达所指状态，模块中其它标示的箭头尽管名称不同，但含义类似。查询过程中，当前活跃状态为 S2 时，将会出现 3 种情况：①Person 元素下无 Name 元素文本值，则状态直接从 S2 跳到 S1，状态 S1 属性为 False，谓词检验不成功；②Person 元素下有 Name 元素，但 Name 元素的文本值不符合要求，则状态从S2—>S4—>S1；主干路径匹配成功和谓词检验不成功；③Person 元素下有 Name 元素，并且 Name 元素的文本值符合要求，则状态从 S2—>S5—>S3，状态 S3 属性为 TRUE，主干路径匹配成功和谓词检验成功。 3 性能测试与分析 为了验证本文提出的算法性能和相对于以前工作的性能提升，本文用 Java 语言实现了基于 PDA 的递归查询算法，并进行了性能测试，并且和之前工作基于 LazyDFA 算法做了比较。实验平台为：操作系统为 Windows XP，CPU 为双核处理器，内存 1024M 实验数据，采用了 IBM 的 XML Generator[9]生成不同递归层次结构的 XML 数据集。XML 数据流处理对时间和内存的耗用量有严格的要求，对于XML数据流的递归查询，数据流的递归深度是影响这两个方面的主要因素，算法采用了整数移位运算的方式，它便于对匹配模式的保存和检验，同时谓词匹配位检验和缓存操作，有利于快速处理潜在的缓存结果。通过从运行时间和内存使用量上来对两个算法进行比较，从图 5、图 6 的实验结果显示，针对不同复杂程度的XML数据流，基于 PDA 算法的性能要优于 LazyDFA 算法

它对文法的限制最少，现今能用上下文无关文法描述的程序设计语言一般均可用LR方法进行有效的分析。 分析法介绍编辑 1965年，D.Knuth首先提出了LR(K)文法及LR(K)分析技术。所谓LR(K)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看K个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。 LR分析是当前最一般的分析方法。这是因为它对文法的限制最少，现今能用上下文无关文法描述的程序设计语言一般均可用LR方法进行有效的分析，而且在分析的效率上也不比诸如不带回溯的自顶向下分析、一般的“移进归约”以及算符优先等分析方法逊色。此外，LR分析器在工作过程中，还能准确及时地发现输入符号串的语法错误。凡此种种，就使LR分析方法在国际上受到了广泛的重视。 对于LR(K)文法的理论研究业已证明：① 每一LR(K)文法都是无二义性文法；② 一个由LR(K)文法所产生的语言也可由某一LR(1)文法产生。同时，由于通常的程序设计语言一般均能由LR(1)文法来产生。因此，对程序设计语言的编译来说，我们可仅考虑k≤1，即LR(0)和LR(1)的情况。 下面，我们首先介绍LR分析器的逻辑结构及工作原理，接着再依次介绍LR(0)，SLR(1)，LR(1)及LALR(1)等四种LR分析器的构造方法。其中，LR(0)分析器的分析能力最低，但它是构造其余三种LR分析器的基础。SLR是“简单LR”分析的缩写，它是为了解决构造LR(0)分析器所出现的问题而形成的一种方法，其分析能力自然要比LR(0)分析器稍强一些。 LR(1)分析器的分析能力是四种LR分析器中的最强者，但对规模较大的文法来说，在具体构造分析器时，由于所需的工作量及要求的存储空间都很庞大，将会遇到很大的困难。为此，采用所谓向前LR分析器即LALR(1)分析器将是一种恰当的选择。LALR(1)分析器的能力介于SLR(1)和LR(1)之间，但其分析表的规模比LR(1)分析表要小得多。至于工作量的问题，则可通过开发和使用LR分析器的自动生成工具来解决。目前十分流行的语法分析器自动生成工具YACC和OCCS正是为自动生成LALR(1)分析器而研制的。 结构及原理编辑 在逻辑上，一个LR分析器有一个输入符号串，一个下推分析栈，以及一个总控程序和分析表。LR分析器在总控程序的控制下自左至右扫视输入串的各个符号，并根据当前分析栈中所存放之文法符号的状况及正注视的输入符号，按分析表的指示完成相应的分析动作。在分析的每一时刻，分析栈中记录了迄今为止所移进或归约出的全部文法符号，即记录了从分析开始到目前为止的整个历程。 因此，为了方便，对于分析过程的每一步，我们可将分析栈中所存放的全部文法符号用一种“状态”来刻画，且将此状态名置于分析栈的栈顶所示。分析刚开始时，栈中仅有一个句子的左界符#，此时分析器处于初始状态S0，它不仅刻画了分析栈中当前仅有一个符号#这一事实，而且还预示着即将扫视的输入符号应当是可作为句子首符号的那些符号。类似地，状态S1刻画了分析栈中已有符号#X1的情况，…，栈顶状态Sm则刻画了分析栈中已存在符号串#X1X2…Xm的情况，等等。此外，根据分析栈的栈顶状态，还可对当前可能遇到的输入符号进行预测。例如，对于前面所述的文法G[E]，设分析栈中已移进和归约出的符号串为#E+T时的栈顶状态为Si，则Si不仅表征了迄今扫描过的输入串部分已被归约成#E+T，而且由Si还可以作这样的预测： 若输入符号串无语法错误，则当前可遇到的输入符号仅能是+,,)或#。 显然，在栈顶状态为上述Si的情况下，若当前所扫视到的符号为，则应将移进栈中；当所扫视到的符号为+,)或#时，则应将E+T归约为E；若所扫视到的符号不是上述四种符号之一，则应按语法错误处理。由此可见，知道了栈顶状态Sm和正扫视到的输入符号ai，就知道了当前所需的全部有用信息，从而也就可惟一地确定当前LR分析器所应采取的动作。所以，在具体实现时，并不需要将文法符号记入分析栈中。 LR分析器的核心是一张分析表，它由两个子表组成： 其一是分析动作表；另一个为状态转移表。其中： S1,S2,…,Sn为分析器的各个状态；a1,a2,…,al为文法的全部终结符号和句子界符；X1,X2,…,Xp为文法字汇表中的全部文法符号。分析动作表中的每一个元素ACTION[Sm,ai]指明，当栈顶状态为Sm且正扫视的输入符号为ai时要完成的分析动作。状态转移表中的元素GOTO[Sm,Xi]则指明，当向分析栈中移进一个输入符号或按某一产生式进行归约之后所要转移到的下一状态。 LR分析器的工作在总控程序的控制下进行，其过程如下 (为书写方便，我们将分析栈按顺时针旋转90度)： 1?分析开始时，首先将初始状态S0及句子左界符#推入分析栈。 2?设在分析的某一步，分析栈和余留输入符号串处于如下格局： S0S1S2…S↓m[]#X1X2…Xma↓iai+1…an# 则用当前栈顶的状态Sm及正扫视的输入符号ai组成符号对(Sm,ai)去查分析动作表，并根据分析表元素ACTION[Sm,ai]的指示采取相应的分析动作，每一分析表元素所指示的仅能是下列四种动作之一： (1) 若ACTION[Sm,ai]=“移进”，则表明句柄尚未在栈顶部形成，正期待继续移进输入符号以形成句柄，故将当前的输入符号ai推入栈中，即 S0 S1 S2 … S↓m[]# X1 X2 … Xm aia↓i+1ai+2…an# 然后，以符号对(Sm,ai)查状态转移表，设相应的表元素GOTO[Sm,ai]=Sm+1，再将此新的状态Sm+1 (即要转移到的下一状态)推入栈中，则有如下格局： S0 S1 S2 … Sm S↓m+1[]# X1 X2 … Xm aia↓i+1ai+2…an# (2) 若ACTION[Sm,ai]=rj，其中rj意指按文法的第j个产生式A→Xm-r+1Xm-r+2…Xm进行归约。这表明栈顶部的符号串Xm-r+1Xm-r+2…Xm已是当前句型 (对非终结符号A)的句柄。按第j个产生式进行归约，也就是将分析栈从顶向下的r个符号 (因为该产生式右部符号串的长度为r)退出，然后再将文法符号A推入栈中，此时分析栈的格局为 S0 S1 S2 … S↓m-r[]# X1 X2 … Xm-r Aa↓iai+1…an# 然后再以(Sm-r,A)查状态转移表，设GOTO[Sm-r,A]=SK，将此新状态推入栈中，则有如下的格局： S0S1S2…Sm-rS↓K[]#X1X2…Xm-rAa↓iai+1…an# 必须注意的是，当完成归约动作之后，输入串指示器不向前推进，它仍然指向动作前的位置。 (3) 若ACTION[Sm,ai]=“接受”则表明当前的输入串已被成功地分析完毕，应中止分析器的工作。 (4) 若ACTION[Sm,ai]=ERROR，则表明当前的输入串中有语法错误，此时应调用出错处理程序进行处理。 3?重复步骤2的工作，直到在分析的某一步，栈顶出现“接受状态”为止。此时，分析栈的最终格局应为 S0S↓z[]#Z#↓ 其中，Z为文法的开始符号，Sz则为使ACTION[Sz,#]=“接受”的惟一状态 (即接受状态)。 上述所列的三个步骤，实质上是对LR分析器总控程序的一个非形式化的描述，它对任何不同的LR分析表都是适用的。顺便提及，LR分析器的输出是在用某个产生式进行归约之后，通过执行相应的语义子程序来实现的，我们将在第5章再讨论这一问题。 分析表构造编辑 顾名思义，LR(0)分析就是LR(K)分析当K=0的情况，亦即在分析的每一步，只要根据当前的栈顶状态 (或者说根据当前分析栈中已移进或归约出的全部文法符号)就能确定应采取何种分析动作，而无须向前查看输入符号。 为了给出构造LR分析表的算法，我们首先需要引入一些非常重要的概念和术语。 活前缀 (viable prefix) 由例4?6对输入串“a,b,a”的分析过程容易看出，如果所分析的输入串没有语法错误，则在分析的每一步，若将分析栈中已移进和归约出的全部文法符号与余留的输入符号串拼接起来，就形成了所给文法的一个规范句型。换言之，也就是在分析的每一步，如输入串已被扫视的部分无语法错误，则当前分析栈中的全部文法符号应当是某一规范句型的前缀。而且还不难看出，此种规范句型的前缀决不会含有句柄右边的任何符号，这是因为一旦句型的句柄在栈的顶部形成，将会立即被归约之故。以后，我们将把规范句型具有上述性质 (即不含句柄之右的任何符号)的前缀称为它的活前缀。例如，对于文法G[L]的规范句型“E,b,a” (见表412分析过程第5步)，其句柄为“b”，栈中的符号串为“E，b”，此句型的活前缀为ε，“E”，“E，”，“E,b”等。 由此可见，一个LR分析器的工作过程，实质上也就是一个逐步产生 (或识别)所给文法的规范句型之活前缀的过程。同时，在分析的每一步，分析栈中的全部文法符号 (如果输入串无语法错误)应是当前规范句型的活前缀，并且与此时的栈顶状态相关联。因此，我们自然会想到，如果能构造一个识别所给文法的所有活前缀的有限自动机，那么就能很方便地构造出相应的LR分析表来。稍后我们将讨论这一问题。 LR项目 上面我们已经说过，在一个规范句型的活前缀中决不含有句柄右边的任何符号。因此，活前缀与句柄的关系不外下述三种情况： (1) 其中已含有句柄的全部符号 (句柄的最右符号即为活前缀的最右符号)； (2) 其中只含句柄的一部分符号 (句柄开头的若干符号与活前缀最右的若干个符号一致)； (3) 其中全然不含有句柄的任何符号。 第一种情况表明，此时某一产生式A→β的右部符号串β已出现在栈顶，因此相应的分析动作应是用此产生式进行归约。第二种情况意味着形如A→β1β2的产生式的右部子串β1已出现于栈顶，正期待着从余留输入串中看到能由β2推出的符号串。而第三种情况则意味着期望从余留输入串中能看到由某一产生式A→α的右部，即α所推出的符号串。为了刻画在分析过程中，文法的一个产生式右部符号串已有多大一部分被识别，我们可在该产生式的右部的某处加上一个圆点“·”来指示位置。例如，对于上述三种情况，标有圆点的产生式分别为A→β·，A→β1·β2以及A→·α。我们把右部某位置上标有圆点的产生式称为相应文法的一个LR(0)项目。特别，对形如A→ε的产生式，相应的LR(0)项目为A→·。显然，不同的LR(0)项目反映了分析过程中栈顶的不同情况。下面我们就会看到，文法的全部LR(0)项目，将是构造识别其全部活前缀的有限自动机的基础。 识别活前缀 DFA 在作出文法的全部LR(0)项目之后，现在用它们来构造识别全部活前缀的DFA。这种DFA的每一个状态由若干个LK(0)项目所组成的集合 (称为项目集)来表示。下面以例4?7所给出的文法为例来说明构造此种DFA的方法。 首先，我们用I0表示这个DFA的初态，它预示着分析过程的开始，并且期待着将给定的输入符号串逐步归约为文法的开始符号S′。或者反过来说，我们所期待的是，从使用产生式S′→S开始，能够逐步推导出所给的输入符号串。因此，我们应将项目S′→·S列入状态I0中。换言之，也就是我们期待着将要扫视的输入串正好就是能由S推出的任何终结符号串。然而，由于不能从输入串中直接读出非终结符号S，因此我们也应当把项目S→·A以及S→·B列入到I0中。由于A和B同样是非终结符号，所以又应当将A→·aAb，A→·c和B→·aBb，B→·d列入I0中。由于最后列入I0的项目中，圆点之后都是终结符号，故I0已经“封闭”，构造项目集I0宣告结束。这样，表示初态的项目集I0由如下的项目组成： I0: S′→·SS→·AA→·aAb S→·BB→·aBbB→·d A→·c 我们将项目S′→·S称为项目集I0的基本项目。上述从项目S′→·S出发构造项目集I0的过程，可用一个对其基本项目集{S′→·S}的闭包运算，即CLOSURE({S′→·S})来表示。一般地，设I为一项目集，则构造I的闭包CLOSURE(I)的算法如下： (1) I中每一项目都属于CLOSURE(I)； (2) 若形如A→α·Xβ的项目属于CLOSURE(I)，且X为非终结符号，则文法中任何X产生式的一切圆点在最左边的项目X→·γ也都属于CLOSURE(I)； (3) 重复上述过程，直至不再有新的项目加入CLOSURE(I)为止。 有了初态I0之后，我们来说明如何确定从I0可能转移到的下一个状态。设X为一个文法符号 (终结符号或非终结符号)，若I0中有圆点位于X左边的项目A→α·Xβ (其中α可以为ε)，则当分析器从输入串识别出 (即移进或归约出)文法符号X后，分析器将进入它的下一个状态。设此状态为Ii，显然Ii中必含有全部形如A→αX·β的项目，我们将这样的项目称为A→α·Xβ的后继项目。对于每一文法符号X，如果存在这样的后继项目，则可能不止一个，设其组成的集合为J,J中的每个项目也就是项目集Ii的基本项目。因此，按照与上面构造项目集I0相类似的讨论，我们就有 Ii=CLOSURE(J) 为了指明Ii是“I0关于文法符号X的后继状态”这一事实，我们可定义一个状态转移函数 GO(I,X)=CLOSURE(J) 其中，I为当前状态，X为文法符号，J为I中所有形如A→α·Xβ的项目的后继项目所组成的集合，而CLOSURE(J)就是项目集I (即状态I)关于X的后继项目集 (即后继状态)。例如，对于上例，我们有： I1=GO(I0,S)=CLOSURE({S′→S·})={S′→S·} I2=GO(I0,A)=CLOSURE({S→A·})={S→A·} I3=GO(I0,B)=CLOSURE({S→B·})={S→B·} I4=GO(I0,a)=CLOSURE({A→a·Ab,B→a·Bb})= {A→a·Ab, B→a·Bb, A→·aAb, B→·aBb, A→·c, B→·d} I5=GO(I0,c)=CLOSURE({A→c·})={A→c·} I6=GO(I0,d)=CLOSURE({B→d·})={B→d·} 请注意，由于I0中无圆点在b之前的项目，故GO(I0,b)无定义。这样，我们求出了I0的全部后继项目集I1,I2,I3,I4,I5,I6。容易看出，由于I1,I2,I3,I5,I6诸项目集中的项目均无后继项目，因此它们都没有后继状态。对于项目集I4，我们再仿此求出它的后继状态，这些后继状态是： I7=GO(I4,A)=CLOSURE({A→aA·b})={A→aA·b} I9=GO(I4,B)=CLOSURE({B→aB·b})={B→aB·b} 此外，由于 GO(I4,a)=I4GO(I4,c)=I5GO(I4,d)=I6 故它们均不产生新的项目集。最后，再求出I7,I9的后继项目集。它们分别是 I8=GO(I7,b)=CLOSURE({A→aAb·})={A→aAb·} I10=GO(I9,b)=CLOSURE({B→aBb·})={B→aBb·} 由于I8和I10已无后继项目集，所以至此我们已求出所给文法G[S]的全部项目集I0~I10，通常，我们将这些项目集的全体称为文法G[S]的LR(0)项目集规范族，并记为 C={I0,I1,I2,I3,…,I10} 于是，我们所要构造的识别文法G[S]全部活前缀的DFA为 M=(C,V,GO,I0,C) 其中： M的状态集也就是文法的LR(0)项目集规范族C={I0,I1,…,I10}； M的字母表也就是文法的字汇表V={S′，S，A，B，a,b,c,d}； M的映像也就是如上定义的状态转换函数GO； M的终态集也是C，这表明M的每一状态都是它的终态。 对于上述文法G[S]，如上构造的识别其全部活前缀的DFA的状态转换图如图416所示。 由于状态转换图416中的每一个状态都是终态，因此在上述DFA工作的过程中，从初态I0出发，沿着有向边所指示的方向前进，可以使DFA在所经历的任何状态上中止它的工作。当DFA到达某一状态时，我们把从初态I0出发，到达该状态所经过的全部有向边上的标记符号依次连接起来，就得到了DFA在到达该状态时，所识别出的某规范句型的一个活前缀。例如：当上述DFA处于初态I0时，它所识别的活前缀为ε；当M处于状态I3时，它所识别的活前缀为B；当M处于I4时，它所识别的活前缀为aa；而达到I9时，它所识别的活前缀为aaB等等。需要注意的是，对那些只含有归约项目的项目集，即M的I1,I2,I3,I5,I6,I8和I10，当M到达这些状态时，表明活前缀中已含有相应句柄的全部符号 (即句柄已在栈顶形成)，因此，我们将这些状态称为句柄识别状态。特别是当M处于状态I1时，M所识别的活前缀为S，这意味着已将所给的输入串归约为S，如果再按产生式S′→S归约一步，就得到了拓广文法G′的开始符号S′。因此，我们将状态I1称为“接受状态”，它预示着对输入串的分析已成功地完成。 对于一个给定文法G的拓广文法G′，当识别它的全部活前缀的DFA作出之后，我们就可据此构造相应的LR(0)分析表了。然而，应当首先注意的是，用前述方法所构造的每一个LR(0)项目集，实质上表征了在分析过程中可能出现的一种分析状态；再根据前面对LR(0)项目的分类，项目集中的每一个项目又与某一种分析动作相关联，因此，我们自然会提出这样的要求，即每一项目集中的诸项目应当是相容的。所谓相容，是指在一个项目集中，不出现这样的情况： (1) 移进项目和归约项目并存； (2) 多个归约项目并存。 如果一个文法G满足上述条件，也就是它的每个LR(0)项目集中都不含冲突项目，则称G为LR(0)文法。显然，只有当一个文法是LR(0)文法时，才能构造出不含冲突动作的LR(0)分析表来。 从前面的讨论和分析，我们将不难得出构造LR(0)分析表的算法。为方便起见，我们用整数0，1，2，…表示状态I0,I1,…，而且如表411那样，也将GOTO子表中有关终结符号的各列并入ACTION子表相应的各列中去，此外，算法中形如sj和rj等记号的含义同前，此算法如下： (1) 对于每个项目集Ii中形如A→α·Xβ的项目，若GO(Ii,X)=Ij，且X为一终结符号a时，置ACTION[i,a]=sj。但若X为非终结符号时，则仅置GOTO[i,X]=j。 (2) 若归约项目A→α·属于Ii，设A→α为文法的第j个产生式，则对文法的任何终结符号或句子的右界符# (将它们统一地记为a)，置ACTION[i,a]=rj。 (3) 若接受项目S′→S·属于Ii，则置ACTION[i,#]=acc。 (4) 在分析表中，凡不能按上述规则填入信息的元素，均置为“出错”。 SLR构造编辑 在前面讨论LR(0)分析表的构造算法时，我们曾经指出，仅当一个文法G是LR(0)文法时，才能对它构造出无冲突动作的LR(0)分析表。然而，对于通常的程序设计语言来说，它们一般都不能用LR(0)文法来描述。例如，考虑如下“简单分程序”的文法G[B′]： 0? B′→B3? D→d 1? B→bD;Se4? S→s;S 2? D→D;d5? S→s 相应识别其全部活前缀的DFA及LR(0)分析表如图417及表414所示。由于在项目集I8中，既含有移进项目[S→s·;S]，又含有归约项目[S→s·]，因而反映到分析表中就出现了具有多重定义的元素ACTION[8,′；′]={s10,r5}，前者指明当输入符号为“；”时应将它移进栈中，而后者则要求按第5个产生式S→s进行归约。于是就出现了有“移进归约”冲突的分析动作。又如，对于通常用来描述简单表达式的文法G[E]，当构造它的项目集规范族时，也会出现类似的情况。这就表明，这两个文法都不是LR(0)文法。然而，尽管如此，对大多数程序设计语言来说，这种具有冲突项目的项目集，在整个项目集规范族中所占的比例毕竟是很小的。因此，如果我们能设法解决出现在一个项目集中的“移进归约”或“归约归约”冲突，那么，只要对前述构造LR(0)分析表的算法稍加修改，它仍能适用于我们现在讨论的情况。 表414G[B′]的LR(0)分析表 b[]d[]；[]s[]e[]#[]B[]D[]S0[]s2[8]11[7]acc2[3]s4[9]33[4]s54[]r3[]r3[]r3[]r3[]r3[]r35[][]s7[][]s8[10]66[6]s97[]r2[]r2[]r2[]r2[]r2[]r28[]r5[]r5[]r5,s10[]r5[]r5[]r59[]r1[]r1[]r1[]r1[]r1[]r110[5]s8[10]1111[]r4[]r4[]r4[]r4[]r4[]r4 仔细分析上述构造LR(0)分析表的算法容易看出，使分析表中出现多重定义分析动作的原因在于其中的规则(2)，即对于每一项目集Ii中的归约项目A→α·，不管当前的输入符号是什么，都把ACTION子表相应于Ii那一行 (即第i行)的各个元素指定为rj，其中j是产生式A→α的编号。因此，如果该项目集Ii中同时还含有形如B→α·bβ或C→α·的项目，则在分析表的第i行中，必然会出现多重定义的元素。 由此可见，对于含有冲突的项目集 Ii={B→α·bβ，A→α·，C→α·} 在构造分析表时，如果能根据不同的向前符号a，将Ii中各项目所对应的分析动作加以区分，那么就有可能使冲突得到解决。为此，对于文法中的非终结符号U，我们定义集合 FOLLOW(U)={a|S′#?…Ua…, a∈VT∪{#}} 即FOLLOW(U)是由所有含U的句型中，直接跟在U后的终结符号或#组成的集合。现对上述项目集Ii，考察FOLLOW(A)，FOLLOW(C)及{b}，若它们两两不相交，则可采用下面的方法，对Ii中各个项目所对应的分析动作加以区分。 对任何输入符号a： (1) 当a=b时，置ACTION[i,b]=“移进”； (2) 当a∈FOLLOW(A)时，置ACTION[i,a]={按产生式A→α归约}； (3) 当a∈FOLLOW(C)时，置ACTION[i,a]={按产生式C→α归约}； (4) 当a不属于上述三种情况之一时，置ACTION[i,a]=“ERROR”。 一般地，若一个项目集I含有多个移进项目和归约项目，例如 I={A1→α·a1β1, A2→α·a2β2，…，Am→α·amβm, B1→α·, B2→α·, …, Bn→α·} 则当集合{a1,a2,…,am}，FOLLOW(B1),FOLLOW(B2)，…,FOLLOW(Bn)两两不相交时，可类似地根据不同的向前符号，对状态为i时的冲突动作进行区分。 上述用来解决分析动作冲突的方法称为SLR(1)规则。此规则是由F?DeRemer于1971年提出的。 有了SLR(1)规则之后，只须对前述构造LR(0)分析表的算法中的规则(2)作如下的修改：“(2)′若归约项目A→α·属于Ii，设A→α为文法的第j个产生式，则对于任何属于FOLLOW(A)的输入符号a，置ACTION[i,a]=rj”，且其余的规则仍保持不变，就得到了构造SLR(1)分析表的算法。 对于给定的文法G，若按上述算法构造的分析表不含多重定义的元素，则称文法G为SLR(1)文法。例如，对于上面的文法G[B′]，它的项目集 I8={S→s·; S,S→s·} 含有冲突的项目，但由于FOLLOW(S)={e}≠{;}，故冲突可用SLR(1)规则解决，与上述项目相应的分析动作分别是： ACTION[8,;]=s10ACTION[8,e]=r5 此外，再注意到FOLLOW(B′)=FOLLOW(B)={#}和FOLLOW(D)={;}，则按上述算法为G[B′]所构造的SLR(1)分析表b[]d[];[]s[]e[]#[]B[]D[]S0[]s2[8]11[7]acc2[3]s4[9]33[4]s54[4]r35[3]s7[][]s8[10]66[6]s97[4]r28[4]s10[][]r59[7]r110[5]s8[10]1111[6]r4 LR构造编辑 前面所介绍的SLR(1)分析法是一种较实用的方法。其优点是状态数目少，造表算法简单，大多数程序设计语言基本上都可用SLR(1)文法来描述。然而，也的确存在这样的文法，其项目集的“移进归约”冲突不可能通过SLR(1)规则得到解决。试看下面的例子。 例4?8考察文法G[S′]=({S′,S,A,B,C,D}, {a,b},,P,S′)其中，P由如下的产生式组成： 0? S′→S4?B→C 1?S→CbBA5?B→Db 2?A→Aab6?C→a 3?A→ab7?D→a 识别此文法的全部活前缀的DFA见图418。其中项目集I10={S→CbBA·,A→A·ab}存在“移进归约”冲突，但因FOLLOW(S)={#}，故上述冲突可通过SLR(1)规则得到解决。然而，在项目集I8={C→a·,D→a·}中，由于FOLLOW(C)={a,b}，FOLLOW(D)={b}，即FOLLOW(C)∩FOLLOW(D)≠?，故用SLR(1)规则解决上述“归约归约”冲突无效。而且还可验证，对于任何K>0，上述文法也是非SLR(k)的，故不能通过任何SLR(k)规则使项目集I8中的“归约归约”冲突得到解决 [2]。因此，我们需要更强的LR分析法，即LR(1)分析方法来解决这一问题。 对SLR(1)规则稍作分析即可发现，它对某些文法失效的原因，在于当所给的文法出现冲突的分析动作时，SLR(1)规则仅孤立地考察输入符号是否属于与归约项目A→α·相关联的集合FOLLOW(A)，以确定是否应按产生式A→α进行归约，而没有考察符号串α所在规范句型的“环境”，即没有考察α在规范句型中的“上下文”，这就具有一定的片面性。因为一旦α出现在分析栈的顶部 (设分析栈当前所存放的符号串为#δα)，且当前的输入符号a也属于FOLLOW(A)，就贸然将α归约为A，此时分析栈中的符号串将变成#δA，但若文法中并不存在以δAa为前缀的规范句型，那么，这种归约无效。例如，对于上述文法中的规范句型Cbabab，当分析达到格局 I0I2I4I8[]#Cbabab(4?50) 时，如果仅根据当前输入符号b∈FOLLOW(C)，就将栈顶符号a按产生式C→a归约为C，则有如下的格局： I0I2I4I6[]#CbCbab 但在该文法中，根本不存在以CbCb为前缀的规范句型，因此在执行下一动作将b移进之前，分析器将报告“出错”。由此可见，在分析过程中，当试图用某一产生式A→α归约栈顶符号串α时，不仅应查看栈中符号串δα，还应向前扫视一输入符号a (我们将a称为向前搜索符号)，只有当δAa的确构成文法某一规范句型的前缀时，才能用此产生式进行归约。为了指明上述事实，应当在原来的每一LR(0)项目[A→α·β]中放置一个向前搜索符号a，使之成为[A→α·β,a]的形式，我们将此种项目称为一个LR(1)项目。同时，为了使分析的每一步都能在栈中得到一个规范句型的活前缀，还应要求每一个LR(1)项目对相应的活前缀都是有效的 (其定义在下面给出)。此外，为了克服分析动作的冲突，在必要时，我们还可将某些项目集进行分解，以便使每一个状态都能确切地指明： 当α已出现在栈顶，且面临哪些输入符号时，才能按产生式A→α将α归约为A。 所谓一个LR(1)项目[A→α·β，a]对活前缀γ=δα有效，是指存在规范推导 S?δAy?δαβyy∈VT 且满足下列条件： (1) 当y≠ε时，a是y的首符号； (2) 当y=ε时，a=#。 例如，对于例4?8所给文法，因有 S?CbBA?CbBab?CbDbab 其中，δ=Cb,α=D,β=b,y=ab,A=B，故LR(1)项目[B→D·b,a]对活前缀γ=CbD有效。又因 S?CbDbab?Cbabab 其中，δ=Cb,A=D,α=a,β=ε,y=bab,故LR(1)项目[D→a·,b]对活前缀γ=Cba有效。由此也可看出，当分析器所处的格局为式(4?50)时，应当将栈顶符号a归为D，而不应将它归约为C。 与LR(0)文法的情况相类似，识别文法全部活前缀的DFA的每一个状态也是用一个LR(1)项目集来表示，而每一个项目集又是由若干个对相应活前缀有效的LR(1)项目组成。为了构造LR(1)项目集族，我们同样需要用到两个函数，即CLOSURE(I)及GO(I，X)。 对每一LR(1)项目集I，相应的CLOSURE(I)的定义如下： (1) I中的任何LR(1)项目都属于CLOSURE(I)。 (2) 设项目[A→α·Bβ，a]∈CLOSURE(I)，并假设它对活前缀γ=δα有效，则对文法中所有形如B→η的产生式和每一个b∈FIRST(βa)，形如[B→·η,b]的全部项目也都对γ有效，故若[B→·η,b]原不在CLOSURE(I)中，则应将其放入。事实上，因为[A→α·Bβ，a]对γ=δα有效，则由定义我们有： s?δAy?δαBβyy∈VT 且a∈FIRST(y)∪{#}，故可将上面的推导写成 S?δAy?δαBβaωω∈VT∪{#} 现设文法已经过化简，故不论β是否为ε，从βaω总能推出终结符号串，于是可假定 βaω?bω′ 又因a≠ε，有FIRST(βaω)=FIRST(βa)，从而就得到推导 S?δαBbω′ 由此可见，一切形如[B→·η,b]的项目也对活前缀γ=δα有效。 (3) 重复步骤(2)直到没有新的项目加入为止。 至于函数GO(I，X)，其中I为一LR(1)项目集，X为某一文法符号，与LR(0)文法类似，我们也将它定义为： GO(I,X)=CLOSURE(J) 其中J是由这样的一些LR(1)项目组成： 对I中所有圆点在X左边形如[A→α·Xβ,a]的项目，其后继项目[A→αX·β,a]∈J。注意，每一LR(1)项目与其后继项目有相同的向前搜索符号。 有了上述CLOSURE(I)和GO(I，X)的定义之后，采用与LR(0)类似的方法，可构造出所给文法G的LR(1)项目集族C及状态转换图。例如，对于上述文法，其LR(1)项目集及状态转换图如图419所示。 对于给定的文法G，当相应的LR(1)项目集族C及GO函数构造出来之后，便可按如下的算法构造它的LR(1)分析表： (1) 对于每个项目集Ii中形如[A→α·Xβ,b]的项目，若GO(Ii,X)=Ij，且当X为一终结符号a时，置ACTION[i,a]=sj。但若X为一非终结符号时，则置GOTO[i,X]=j。 (2) 若归约项目[A→α·,a]∈Ii，A→α为文法的第j个产生式，则置ACTION[i,a]=rj。 (3) 若项目[S′→S·,#]∈Ii，则置ACTION[i,#]=acc。 (4) 在分析表中，凡不能照上述规则填入信息的元素，均置为“出错”。 对于一个文法G来说，若按上述算法所构造的分析表不含有多重定义的元素，则称此分析表为G的LR(1)分析表。凡具有LR(1)分析表的文法称为LR(1)文法。例如，上述文法的LR(1)分析表见表416，所以它是一个LR(1)文法。 LALR构造编辑 上述每个LR(1)项目均由两部分组成： 第一部分是一个LR(0)项目，称为LR(1)项目的核；第二部分则是一个向前搜索符号集。对于移进项目而言，搜索符号对分析表的构造无影响；但对归约项目而言，则仅在当前输入符号属于该搜索符号集时，才能用相应的产生式进行归约。LR(1)分析表的这种机理，较圆满地解决了SLR(1)分析所难以解决的某些“移进归约”或“归约归约”冲突，从而使LR(1)的分析能力比SLR(1)分析有明显的提高。然而，LR(1)分析的主要缺点在于，对同一个文法而言，LR(1)分析表的规模将远远大于相应的SLR(1)或LR(0)分析表。例如，为一个C语言构造LR(0)分析表，一般大约设置300个状态即可，而构造LR(1)分析表则需上千个状态，即后者将导致时间和内存空间开销的急剧上升。因此，就有必要寻求一种其分析表的规模与SLR(1)相当，但其分析能力又不比LR(1)相差太大的LR分析方法，这就是下面我们要介绍的LALR(1)分析技术。 下面，我们首先对造成LR(1)项目集族规模大幅度上升的原因进行分析，然后再设法从中找出构造高效LR分析表 (即LALR(1)分析表)的方法。为此，试看下面的例子。 再考察文法G[E]： 0?S→E4?T→F 1?E→E+T5?F→(E) 2?E→T6?F→ID 3?T→TF 利用上面所给算法，为G[E]构造的LR(1)项目集族和识别活前缀的DFA如图420(a)，(b)所示 (请注意，由于图幅较大，这里将其划分为(a)，(b)两部分)。对比这两幅图我们立即就会发现，除其中的状态0和状态3之外，对于(a)中的每一状态 (LR(1)项目集)，在(b)中都有一个状态 (LR(1)项目集)与其相似。例如，比较状态7和16：在这两个项目集中，除搜索符号集不同外，各个LR(1)项目的核都彼此相同 (即产生式相同，且产生式中圆点的位置也相同)，我们把具有这种特点的两个LR(1)项目集称为同心集。所以，在图420(a)和(b)中，7/16，5/12，10/17，4/13，8/18，2/14，11/19，6/20，1/15和9/21都是同心集。显然，在LR(0)分析器中，每个“心”仅对应一个LR(0)项目集；但在LR(1)分析器中，由于向前搜索符号的不同，同一个“心”将会派生出多个同心集。这就是对同一文法而言，LR(1)项目集族远大于LR(0)项目集规范族的原因。 7E→E+·T[]#+T→·TF T→·F F→·(E) F→·ID〖〗#+ #+* #+* #+[][]16E→E+·T[]+)T→·TF T→·F F→·(E) F→·ID〖〗+)* +)* +)* +)* 为解决上述问题，F?DeRemer提出了LALR(1)分析法。这种方法的基本思想是将LR(1)项目集族中的同心项目集加以合并，以削减项目集的个数。所谓合并同心集，实际上也就是将其中的每个LR(1)项目的向前搜索符集对应地合并在一起。例如，对于文法G[E]的同心项目集4和13，设合并后的新项目集为4/13，则有 4E→T· T→T·F〖〗#+ #+[][]13E→T· T→T·F〖〗+) +)[][]4/13E→T· T→T·F〖〗#+) #+) 由于同心集的合并，对原来识别活前缀的DFA也须作相应的修改。 对于LALR(1)项目集族，我们须着重指出如下几点： (1) 合并同心集也就是将同心集中每个LR(1)项目的两个组成部分 (核及向前搜索符号集)分别、对应地合并在一起。设I1,I2,…,Im为同心项目集，J是合并之后的新的项目集，显然J与Ii同心；再设X∈V∪{#}，则GO(I1,X),GO(I2,X)，…，GO(Im,X)也必然同心，若把这m个同心项目集合并后的新项目集记为K，则有GOTO(J，X)=K。可见前面定义的GOTO函数在这里仍然适用。 (2) 尽管原来各LR(1)项目集均不存在冲突，但合并同心集后就有可能出现冲突。换言之，即LR(1)文法未必总是LALR(1)文法。不过，由此引入的冲突只能是“归约归约”冲突，而决不会是“移进归约”冲突。事实上，设原LR(1)项目集族中有如下两个项目集 Ik： [A→α·，W1] [B→β·aγ,b]Ij: [A→α·,W2] [B→β·aγ，c] 并设Ik与Ij均无冲突，故有 W1∩{a}=?W2∩{a}=? 从而 (W1∪W2)∩{a}=? 现将Ik与Ij合并，有 Ik/j: [A→α·,W1∪W2] [B→β·aγ，{b}∪{c}] 若此时Ik/j有“移进归约”冲突，则必有 (W1∪W2)∩{a}≠? 这就与Ik与Ij无冲突的假设相矛盾。因此，合并同心集不会引入新的“移进归约”冲突。 (3) 对同一个语法上正确的输入符号串而言，不论用LALR(1)分析表还是用LR(1)分析表进行分析，所经历的移进、归约序列总是相同的 (仅状态名可能不同)。然而，当输入符号串有错时，LALR分析器可能会比LR(1)分析器多进行几步归约才能报错，但决不会比LR分析器多移进输入符号。也就是说，LALR分析器虽然可能延迟了发现出错的时间，但对错误的准确定位不产生影响。 (4) LALR(1)项目集族总是与同一文法的SLR(1)项目集族有同样个数的项目集。但是构造LALR项目集族的开销比SLR大。实现LALR分析对文法的要求比LR(1)严、比SLR(1)宽，但开销远小于LR(1)。权衡利弊的结果，LALR堪称为当前实现自底向上语法分析，特别是构造分析器自动生成工具的最为适用的技术。 综上所述，可给出构造LALR(1)分析表的算法如下。 1? 对已给的拓广文法G′，构造相应的LR(1)项目集族C={I0,I1,…,In}。 2? 对于C，将各LR(1)项目集按同心关系进行分组，并将同组的同心集加以合并，设所得的新项目集族为C′={J0,J1,…,Jm}，其中含有项目[S′→·S,#]的项目集对应于初态。 3? 若C′中的项目集含有冲突项目，则G′不是LALR(1)文法。否则，可按如下法则构造LALR(1)分析表： (1) 用构造LR(1)分析表类似的方法构造ACTION表； (2) 对于某个X∈VN，若有GO(Jk,X)=Jt，则置GOTO(k,X)=t。 上述通过构造LR(1)项目集族和合并同心集来构造LALR分析表的方式仅有理论意义而无实用价值。因为构造完整的LR(1)项目集族的时间和空间开销都很大，故应首先设法予以解决。 迄今已有多种高效构造LALR分析表的算法，其共同的特点都是不从直接构造完整的LR(1)项目集入手，而是通过构造LR(0)项目集并添加相应的向前搜索符号来形成LALR(1)项目集 (请注意，对同一个文法而言，LALR(1)项目集与同心的LR(0)项目集一一对应)。例如，OCCS/YACC构造LALR(1)项目集所采用的策略是，每当创建一新的项目集时，就检查目前是否已存在与之同心的项目集，若有这样的项目集，则只需将向前搜索符号加入其中，而不再建立新的项目集。一种更为有效的方法甚至无需构造完整的LALR(1)项目集，而仅通过各个项目集中的“核心项目”便能构造相应的LALR(1)分析表。这里所说的核心项目是指形如[S′→·S，#]的项目 (其中，S′→S是拓广文法的第1个产生式)，或者是形如[A→α·Xβ,a]的项目 (其中，α≠ε，即圆点不出现在产生式右部的最左位置)，亦即那些用于构造本项目集闭包的“基本项目”。例如，对于文法G[E]，各项目集的核心项目如图422所示。 下面，我们对利用项目集的核心项目构造LALR分析表的原理进行说明。 ACTION 构造ACTION表的关键在于确定“归约”和“移进”两种动作。 (1) 归约动作的确定 由核心项目的定义可知，任何归约项目都必然会出现在某个项目集的核心项目之中，现设项目集I的核心为K，若[A→α·,a]∈K (其中α≠ε，搜索符号如何配置下面再介绍)，我们立即可以确定： 在当前状态下所面临的输入符号为a时，应按产生式A→α进行归约，即有 ACTION[I,a]=rj 若α=ε，则当且仅当 [B→γ·Cδ， b]∈KC?[]rAη 且a∈FIRST(ηδb)时，才能确定面临输入符号a时用产生式A→ε进行归约。由于对任何C∈VN，满足C?[]rAη的所有非终结符号A预先能完全确定，故项目集I所引发的归约动作，仅由其核心K即能完全确定。 (2) 移进动作的确定 若 [A→α·Xβ,b]∈KX?[]raη(a∈VT) 且上述推导的最后一步未使用ε产生式，则可确定： 状态I面临输入符号a时的动作为“移进”。其中，终结符号a可通过预先计算FIRST(X)加以确定。 GOTO 对于任何项目[B→γ·Xδ,b]∈K，相应的项目[B→γX·δ,b]显然必属于某个项目集J=GO(I，X)的核心L。另外，若 [B→γ·Cδ,b]∈KC?[]rAη 且A→Xβ是文法中的一个产生式，则对于任何 a∈FIRST(ηδb)[A→X·β,a]∈L 由于对每一对非终结符号(C，A)，是否存在关系C?[]rAη，可采用类似于计算FIRST集的方法预先求出，故仅从I的核心同样可构造出GOTO表。 配置 上面的讨论，是在假定每个核心项目都已配置了搜索符号的情况下进行的。现在，再回头讨论： 如何为每个LR(0)项目集的核心项目配置搜索符号，使之成为LALR项目集的核心项目。为此，我们首先考察搜索符号从项目集I传播到项目集GO(I，X)的规律。 再设项目集I的核心为K，若有 [B→γ·Cδ,b]∈KC?[]rAη 且A→Xβ是文法中的一个产生式，则根据上面的讨论有 [A→X·β,a]∈La∈FIRST(ηδb) 其中L是项目集J的核心，且J=GO(I,X)。现分如下两种情况讨论搜索符号a和b间的关系。 (1) 当ηδ?ε时，显然也有[A→X·β,b]∈L。此时，我们就说项目[A→X·β,b]中的搜索符号b是从项目[B→γ·Cδ,b]中传递过来的 (propagate)。 (2) 当ηδ不能推导出ε时，a仅取决于η或δ，而与b无关，此时我们就说搜索符号a是自生的 (spotaneous)。 无论a是传递的还是自生的，它总能根据项目[B→γ·Cδ,b]中的有关信息，通过上述计算获得，这便是搜索符号从项目集I传播到项目集J的规律。 其次，在同一项目集中，核心项目中的搜索符号向非核心项目传播的规律与上述规律极为相似。事实上，设[B→γ·Cδ,b]∈K，而C→α是文法中的一个产生式，则[C→·α，c]是I的一个非核心项目。其中，搜索符c∈FIRST(δb)，且按如下方法确定： 若δ不能推出ε，则c是自生的；否则，c=b，即c是从上面的项目传递下来的。 类似地，也可讨论搜索符号在非核心项目间的传播规律。例如，对于文法G[E]，从核心项目[S→·E，#]开始，向前搜索符号在I0中的传递和自生的情况如图423所示。 设K是LR(0)项目集I的核心，X是某个文法符号，则对GO(I，X)的核心中的每一项目A→αX·β，通过程序47描述的操作 (请注意，这里使用了一个虚拟搜索符号lookahead)，可由I中的项目确定其全部自生的搜索符号，并能确定K中的哪些项目将其搜索符号传递给GO(I，X)中的项目A→αX·β。 程序47确定自生搜索符号和传递搜索符号的项目 for (K中的每个项目B→γ·δ) { J′=CLOSURE ([B→γ·δ,lookahead]); /计算GO函数之值 */ for (J′中的每一项目[A→α·Xβ,a]) { if(a!=lookahead) 确定GO(I，X)核心项目[A→αX·β,a] 之搜索符号a是自生的 if(a==lookahead) 确定GO(I，X)核心项目[A→αX·β，a]之搜索符号a是从K中项目 B→γ·δ传递过来的； } } 最后，我们再考虑如何给每个LR(0)项目集的核心中的各个项目都配置一个搜索符号集，以获得各个LALR(1)项目集的核心。完成此项任务的大致过程如下。 (1) 为拓广文法G′构造全部LR(0)项目集的核心。 (2) 首先从初始项目集I0惟一的核心项目S′→·S (其搜索符号显然为#)开始，对每个LR(0)项目集的核心和每个文法符号X，利用上面的算法，确定GO(I，X)各核心项目的自生搜索符号集，并确定从I的哪些项目将搜索符号传递到GO(I，X)的核心项目。 (3) 按某种便于操作的结构，建立一张核心项目表，此项目表记录了每个项目集的各个核心项目及其相应的搜索符号集。开始时，这些搜索符号集仅是由第(2)步所确定的自生搜索符号集 (若该核心项目无自生向前搜索符号则为空)。 (4) 传递每个核心项目中的自生搜索符号，直到无法再进行传递为止。即反复扫视各项目集的每个核心项目，每当访问一个核心项目i时，便根据第(2)步所获的信息，将i当前要传递的搜索符号添加到承接它的那个核心项目之中，直至没有新的搜索符号要传递为止。 对一个给定的文法G而言，当它的各个LALR(1)项目集的核心构造出来之后，就能根据上面所描述的原理，为G构造相应的LALR(1)分析表。不过，尽管上述构造LALR分析表的方法效率较高，但对于常见的程序设计语言，企图用手工的方式来建立LALR分析表仍几乎是不可能的。所幸的是，目前已有一些自动生成LALR分析表的工具可资使用(如YACC)。 还应当指出，在构造LR语法分析器时，尚有若干技术问题需予以考虑，如二义性文法的处理，避免按单产生式的归约，等等。前者我们将在第5章介绍语法分析器自动生成工具时再进行讨论；至于后者，由于需涉及一些语义处理及其信息传递的细节，故就不再讨论了。 在结束本章时，我们还要给出如下的结论，这些结论的证明读者可参阅有关的文献(1，2，8，15)。 (1) 任何LR(K)，LL(K)及简单优先文法类都是无二义性的；对于算符优先文法，如果不考虑归约所得非终结符号的名字，也可认为是无二义性的。 (2) 任何二义性的文法都不可能是LR(1)(或LL(1))文法，但可借助于其它因素，如算符的优先级和结合规则以及某些语义解释等等，来构造无冲突的分析表。 (3) 每个SLR(K)文法都是LR( 各类文法之间的关系 各类文法之间的关系 K)文法，但却存在这样的LR(1)文法，它对任何K而言均不是SLR(K)文法。

说明：

rpc服框架，提供多语言的编译功能，并提供多种服务器工作模式；用户通过Thrift的IDL（接口定义语言）来描述接口函数及数据类型，然后通过Thrift的编译环境生成各种语言类型的接口文件，用户可以根据自己的需要采用不同的语言开发客户端代码和服务器端代码。

符号表在编译程序工作的过程中需要不断收集、记录和使用源程序中一些语法符号的类型和特征等相关信息。这些信息一般以表格形式存储于系统中。如常数表、变量名表、数组名表、过程名表、标号表等等，统称为符号表。对于符号表组织、构造和管理方法的好坏会直接影响编译系统的运行效率。

http://re2c.org/

http://docs.php.net/manual/zh/features.gc.collecting-cycles.php#features.gc.collecting-cycles 传统上，像以前的 php 用到的引用计数内存机制，无法处理循环的引用内存泄漏。然而 5.3.0 PHP 使用文章» 引用计数系统中的同步周期回收(Concurrent Cycle Collection in Reference Counted Systems)中的同步算法，来处理这个内存泄漏问题。

匿名函数与闭包的区别 匿名函数：没有函数名称的函数； 这就是匿名函数： function(argument1,argument2){

ex Lex 是一种生成扫描器的工具。扫描器是一种识别文本中的词汇模式的程序。 这些词汇模式（或者常规表达式）在一种特殊的句子结构中定义，这个我们一会儿就要讨论。