删帖吧

xyfree

滚

cjaizss

类似这样的想法，最多只可能更快的找出某些语言的错误所在，并且这是基于人的习惯错误统计的基础之上。
计算机并非人，人的思维模式至今还仍无法用数学来解释。
通过这样的手段去“提高”编译速度，八成是马大哈扫描式了，一些错误就被忽略掉了，这样的编译器我是不敢用的。

xyfree

回复 2# cjaizss

非也。
扫描并非影响文法识别的最大因素。
所以，我想说的其实并不是只扫描两端，而是根据两端来进行识别。

如果是以LL的那种递归下降，回溯才是最大的时间耗费。
若有某种办法，双端识别，应该就可以减少尝试的路径的量吧？

当然这种办法的前提是有效地把输入串切割成小段。
这可能要对文法设计有一定的要求

如果除去for语句，C/C++是符合这种要求的：

必然可以以 分号 ';' 或者 花括号 '{' '}' 来切割输入串，便于识别。

prolj

作为一个中国人，我告诉你，编译来不得半点儿错误。

prolj

自然语言理解 跟 编译 压根就没什么关系。人类的容错性比计算机好多了。

xyfree

回复 5# prolj

我晕， 一开始一句“作为一个中国人，……”我还以为你打算说什么东西呢~

我也很负责任地告诉你，我是希望改进自己的编译器，研究算法。
不跟你瞎扯淡。

自然语言理解跟编程语言编译没关系？谁告诉你的？
只是计算上是否可行的问题而已了。

再况且，我根本就没打算让编译器像人一样“理解”编程语言。
我只是提出一个设想，是不是可能有LR和LL之外的识别方法而已。

我换成另外一个说法，实际上就是常见的算法问题：
怎样从两个出发点选择路径，到达图之中的某一个点。

这样你明白我在说什么了吧？

Solidus

回复  cjaizss

非也。
扫描并非影响文法识别的最大因素。
所以，我想说的其实并不是只扫描两端，而是 ...
xyfree 发表于 2010-03-10 16:18

    我不太理解你这种方法如何能分别应用在提取词素和语法单元上，

如果以词法分析为例，“两端”这个说法本身就有问题，一个最简单的例子，我需要过滤掉空行，那么空行的意思是[ \t]*(\r)*\n,而非空行就是[ \t]*.+(\r)*\n,这里面可能还牵扯到非空行以xx开头的注释，也许要过滤掉。

如果以语法分析为例，“两端”更难判定，以C语言这种上下文相关语言为例，至少同一个范围有三个独立的符号表协作，你没办法在某个点上独立的判断出来符号X在当前scope下的词法值是什么，如果必须不依赖符号表建立完整的语法树，只能设定ID这一个词法值，那么就得靠回朔，比如

typedef int x_t;

void test()
{
       x_t = 3;
}

不依赖上文typedef,在这个block里的x_t毫无意义，如果词法分析模块不查表，你在x_t = 3这里根本就看不到错误，如果还需要得到正确的语法树，那么文法就必须把DECL写成DECL ： ID ID....; 这类文法在分析C语言中就已经得靠回朔了(例如LL(K>1)， LR(K>1), GLR, Backtracking-LR等等），否则就是冲突，现在无回朔的例如YACC（LALR(1))什么的东西都是靠一个近似的BNF然后自己手工分析去，例如对一个符号至少有俩可能的词法值，TYPE_ID和ID，之后依赖符号表确定到底是什么。

第一个例子说明，对于一个状态机，必须从起始状态经过中间状态才能知道哪里是结尾，而语法这个例子的意思是即使不带任何语义分析的，只提取语法结构的parser来说，也是一个协作系统，即使走过中间状态都不足以分析清楚什么是什么，都得借助额外的数据库辅助，所以独立的提取单元可能是个非常麻烦的事情，即使可以也需要比这种按部就班的预测分析慢得多得多。

最后就是，从我个人经验上看，分析部分所占用的时间比重不是很大，更多的是语义处理，查表，优化等等乱七八糟的事情。虽然理论上分析很重要，但是在工程中不论是代码量还是占用的CPU时间都很小。

PS：我不认为人类识别单词是靠两端，而是人类大脑中有个启发式的经年累月积累下的符号表，匹配算法现在也无从知晓，输入即可以是一个词也可以是一个短语和一个句子，然后自己脑补，精分~~，当然，人类这种脑补行为本身就是个错误率极高的事情，换句话说，之所以有计算机这类东西一大部分原因就是希望借助计算机无差错的重复去做有点傻的事情，而不是让一帮聪明的人高效的去做可能做错的事情，至少计算机的输入输出是可以证明的。

prolj

扯淡？
while 和 whlie 两个都能做关键字？
图？你打算用多大的图？怎么个搜索法？

xyfree

回复 7# Solidus

非常高兴看到一个有深度的留言。

你说得很对，在词法分析上面，即使是我自己说的什么“两端”开始分析，也暂时没想到怎么搞。
因为我说了，必须有一个依据来把输入切割成小段，在这样的基础上才有”两端“的概念存在。
在词法分析完成之前，几乎不存在这样的依据来进行切割。
   
其实也不是不可能，只不过算法可能非常复杂。
而且只有像是LEX、YACC这样的Compiler compiler的作者才需要考虑这个问题。

假如我先对词法规则进行计算，那么我就有可能得到一个词法分析上的可用于输入字符串分割的字符集合。
譬如，在常见的C语言代码里面（我没深入研究过，除去宏定义的话大致上还是差不多的），
各种运算符、分号、大中小括号括号、WS（即诸如空白、换行、tab之类的）都可以用来分割输入串。

按照这个想法看你给的代码（假设我已经计算好了C语言的“分割集”）
有这样的输入串
"typedef int x_t; void test() { x_t = 3; }"
那么就可以分割出：
typedef、int、x_t、void、test、x_t、3
分割出来之后再去识别这些子串到底是什么。
当然，就目前看来，在词法分析阶段进行这样的分割并没有提供什么方便。
我唯一能想到的好处就是有利于并行化识别，因为分析这些子串已经不再依赖全局的状态机了。

这些分割集理论上是存在的。
如果在词法分析的阶段使用了状态栈，那么出现分割集中的字符的时候，通常可以进行退栈。（这还是我没仔细分析过的结论）

另外，我不太觉得词法分析（lexical parsing）阶段要用到符号表。
符号表式在语法分析的过程中建立的。
当然，我没做过C语言的编译器，如果C语言确实要这样，那你是对的。

-----------------------

如果是用在语法分析阶段，这个方法显得比较有优势。
很显然，这里继续需要一个分割集，但通常不再是词法分析上的那个分割集。
譬如，在类似C语言风格的语言里面，这些语法上的分割集可以是
   分号（语句的末尾）
   左右花括号（通常是语句块）

看到这一句

1. 
   
2. typedef int x_t;
   

复制代码

经过词法分析之后应该会变成类似于这样的词法符号（也可以说是语言的元类型）

1. 
   
2. declarator[" typedef "]   primitive_type[" int "]    id[" x_t "]   divider[" ; "]
   

复制代码

之所以可以这样分析，是因为分割集的存在。
在词法符号串（也就是词法分析的结果）遇到分号的时候，语法分析器知道可以开始进行判断。

在遇到这个句型时，就可以根据文法定义来分析：什么语句可以是以 declarator 开头，以id 结尾的？
很多，C语言里面多数的声明语句都是这样。

接下来要处理的应该可以更加好的体现优势

1. void test()
   
2. {
   
3.         x_t = 3;
   
4. }

复制代码

根据词法符号串的输入，在见到'{'的时候就可以进行分析了
前面的 void test()是声明了一个函数，
因为有 '{'和'}'的存在，可以知道紧接着就是它的定义。

如果是LL，在遇到'{'的时候要做一个尝试，尝试匹配函数声明和定义。
如果按照LR，可能要到最后的'}'才能规约出这是一个函数声明并定义。（LR的方法太多，我这话可能不完全正确）

但是很明显，如果一个编程语言，例如C语言，能够产生分割集来写代码的话

void test() { ... } 已经足以确定是一个函数声明和定义。
如果中间出错了，那么按照代码提供的信息可以确定，出错的影响应该局限在大括号之间，而不是否定整块语句。

很多编译器之所以没有否定整个声明和定义的代码块，是因为会忽略出错，尝试继续析下去。
所以有时候，会牵扯到很多无关的代码。

思路就是这样，欢迎继续拍砖。

xyfree

扯淡？
while 和 whlie 两个都能做关键字？
图？你打算用多大的图？怎么个搜索法？
prolj 发表于 2010-03-12 11:41

while 的例子，你理解错我的意思了。看上一层的回复
还有再看这里

所以，我想说的其实并不是只扫描两端，而是根据两端来进行识别。
xyfree 发表于 2010-03-10 16:18

或者我说的有歧义，双语表达吧：
so, it's NOT what I mean that scanning only the two endians, but recognizing FROM the two endians.

像ANTLR，YACC 这样的工具，如果它愿意，可以在输入文法定义的时候，构造出一个多通路的图。
这个图必然可以变换成有唯一入口和唯一出口的。
这个图还有一些性质：可以有分支，可以有环，但每条分支路径和其他路径都没有交点。
图有多大，是由语法来决定的。
编译代码的时候，实际上是找到一条或多条从入口到出口的路径
我所说的分割集，就是这个图之中某些产生分支并形成回路的结点。

然后，LL和LR的思路，都是从图的唯一入口，走到图的唯一出口；或者退出（分析失败）
差别在于，LL分析的时候是深度优先，LR是广度优先。

我的设想是，从图的入口前进，也从图的出口回退。