删帖吧

Solidus

回复  Solidus

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

你说得很对，在词法分析上面，即使是我自己说的什么 ...
xyfree 发表于 2010-03-12 16:53

   
关于词法分析这块咱们俩的视角可能不太一样，我写过类似lex和yacc这类东西

(Arsenal，纯娱乐性质，一直处在修修改改当中), 所以可能更关注通用性和可配置的

自动生成方面。所以我不太明白你说的关于分割子串这个概念，如果我没理解错的话

你的意思是先根据特定语言词素的特点进行预处理，之后再细分，比如C完全可以先靠

空格[ \r\n\t]一类的进行预处理提取出一堆子串，之后可以交给什么东西细分，比如

分割出一堆没有词法值的串：typedef int x_t void ....之后把这些没有词法值的串

交给后台N个线程同时检测词法值。老实说我不太赞同这种做法，但是如果你给定语言

足够适合的话应该也可行。



关于语法分析部分，我不清楚你对LR到底了解多少，如果我没理解错的话，你的方法

跟LR非常相似，我分两个角度说，一种在无冲突的LR（1）PDA上，一种在有冲突的的

LR(1)PDA上。

第一：在一个是在无冲突的LR(1)文法生成的PDA上，你的方法只比LR(1)慢，因为：
“
根据词法符号串的输入，在见到'{'的时候就可以进行分析了
前面的 void test()是声明了一个函数，
因为有 '{'和'}'的存在，可以知道紧接着就是它的定义。
”

你的意思是提前知道void test() + lookahead('{' ...‘}')是一个函数定义？问题

是你在这个state上知道了有什么用呢？例如这个文法：

function_definition : declaration_specifiers declarator compound_statement
输入是 void test(){ ...},
假设已经shift了"void" "test" "(" ")"，此时，parser stack为：

declarator                <-  R(test()）
declaration_specifiers <-  R(void）
假设我们的文法在这个状态上，合法的选择有两个，一个是继续提取词素，当看到';'

时，变换parser_stack为：
init_declarator_list   <-  R(declarator）
declaration_specifiers <-  R(void）

之后移入';'最后规约为
declaration <- R(declaration_specifiers,init_declarator_list ";")
这样，或者输入'{'，根据文法function_definition生成的PDA，将把我们带入另一个

状态，开始分析compound_statement,最终规约成function_definition,换句话说，你

的方法和LR（1）的没有本质区别，

你的还多加了一步预搜索，LR（1）看到'{'确定走向状态S了，你的方法必须预搜索到

'}'之后再把所有得到的词素回退到lexer中，之后才走向状态S，这里的问题是，你最

终的结果都是function_definition,你的方法和LR(1)的方法都是在state S'+

lookahead'{'非常确定的走向function_definition，那么预搜索'}'在一个无冲突的

PDA上你的方法无意义。


第二：在一个有冲突的LR(1)PDA上，lookahead会导向N种状态，这时候常见的解决办法是要么改文法，要么增加LR(K)的K值，这回导致巨大的分析表。要么给这个PDA加功能，例如backtracking-LR就是深搜，先尝试第一个状态，在尝试第二个，那个走通了就是那个，但是这会导致很麻烦的数据簿记和恢复问题。另一种是GLR，我对GLR了解不是很多，粗略的说就是在冲突点上分裂分析栈，同时存储N个子树，每个冲突点都分裂，最终完成后修剪子树，这个比backtracking-LR还麻烦，这两种方法都需要回朔，但是你的方法如果在深入研究也许可以在冲突点上手动向后预搜索，并确定是哪个选择哪个状态，这种方法不会通用，但是在某种给定语言上也许会有效，我觉得值得研究下~~



PS：最后想说一下我上次发言描述不清楚的一个事情：就是理论上词法分析确实不一

定需要符号表，换句话说，理论上先生成抽象语法树，之后在其上执行语义动作和错

误报告是完全没有问题的。我那个例子还是从通用性的这种预测分析法出发的，例如

对于C语言+LR分析法就有问题，在某几个状态在lookahead上存在冲突，例如一个常见

的文法

例如

state[139] : )        Reduce: [ <primary_expression> -> IDENTIFIER .  ]       
                Reduce: [ <type_specifier> -> IDENTIFIER .  ]       

（PS:我自己的文法，名字可能不太标准，就那个意思，凑合看）

说不定应用你的方法在冲突点上向后预查可以解决点什么，哈哈哈

prolj

clang lcc gcc的词法是这么做的，一次读入很大的一个buff，然后指针一个字符一个字符的走着判断。
至于两头开始，首先要断词，有断词搜索的代价，tok早就分析出来了。
词法跟LL LR还没什么关系吧？

prolj

呵呵，做工程，不是好玩儿的理论，要考虑实现代价和性能的，断词也要一个字符一个字符的判断是不是空格，有这个判断，为什么不直接识别出来tok，非常再做一个两头判断呢？

flw2

夸张的说，在编译器中，识别token需要时间吗?还分割什么，分割都是一个一个字符走的。
whiel， 看了w和l 就知道单词是否正确？那是因为大脑数据很多

一个PC机，一秒钟可以识别100MB-300MB的文本。

一个原文件100K算很大的吧，

xyfree

楼上两位， prolj 和 flw2 同志，以及将要跟帖的请注意，先搞清楚在讨论什么。

连我自己都说了，我那个想法，应用在词法分析上根本就是不值得。
而且，我一开始就说了，看1楼：根据那个“原理”，用于“语法识别”，会不会比较好。
看懂了吗，我一开始就没在说词法分析。

再说了，我现在就是探讨可能性。
您俩老要用高性能可用的实际产品，先等等好吧？
理论都还没出来呢！

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

回复 11# Solidus

发现 Solidus 同志对 LR 的理解比我多得多，
推荐点资料给我研究研究？

Solidus

楼上两位， prolj 和 flw2 同志，以及将要跟帖的请注意，先搞清楚在讨论什么。

连我自己都说了，我那个想 ...
xyfree 发表于 2010-03-12 22:36

      我不是专门研究这个的，所以最好去新闻组问问，我个人比较喜欢这类东西，所以就说点我知道的吧。

    这类东西其实理论上的东西不是很多，基本上照着龙书就能写出个架子来了，教科书方面我见过的相对完整的论述LR的有本<Crafting a compiler with C>,不过这两本书都有问题，龙书里面生成LALR(1)和LR(1)分析表的算法比较古老，足够简单，但是慢的离谱，弄个C++的文法上去估计得算一阵子（我第一个版本就是完全照搬龙书的，90个Term,300条产生式,生成个LALR(1)分析表得10秒钟,后来换了个算法之后只需要20ms)。后一本对LR(0)->LALR(1)的传播链算法有所提及，但是语焉不详，所以这类算法你得搜索文献了，我现在能回忆起来的有个：<Efficient Computation of LALR(1) Look-Ahead Sets>，具体资料你可以去新闻组搜搜，我大部分资料都从那里来的。 其实最好找个现成的实现看，这类东西代码量都不大，然后再读文献比较好，因为此类东西主要是探讨一些数据结构的簿记方式。


另一些比较有意思的和LR有关的东西大概有我提过的：例如Backtracking-LR,介绍这个的有<  Parsing Non-LR(k) Grammars with Yacc>，<A Backtracking LR Algorithm for Parsing Ambiguous Context-Dependent Languages>,GLR的我没读过相关文献，不太清楚有什么著名的东西。这两样东西都不算是理论论述，也属于如何组织数据结构。

还有一个我个人认为最酷玩意儿：从EBNF->LALR，新闻组上这问题问的也比较多，相关文献也多，例如<Yet another generation of LALR parsers for regular right part grammars>, 我都没看过也记不住名字了，但是有时间搞明白了加到自己的语法分析库里真的很酷~~

PS：其实我并不看好LR这种技术，我认为现在是ANTLR这类随意指定K的LL生成器的天下（虽然我从没用过它 ）(非常类似的现象还有现代regex引擎的变迁，性能不再是第一要素，功能才是！)，真正做个C++这种怪物级别的编译器最好的办法通常是手写递归下降，<  Parsing Non-LR(k) Grammars with Yacc>里有所提及，我写这类LL或LR引擎主要是好奇，外加给自己做一些小工具而已~~

cjaizss

回复  cjaizss

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

那么请问你怎么找到两端的?

prolj

OK，语法，语法是怎么回事儿？语法也要尊重原始语义吧？
a+++1，应该是a++ +1，两头分析，怎么分析？a+ + +1？
无论是LL还是LR，都是顺序读入tok，进行shift和reduce。
在你语法分析的时候，读入了所有的tok，再从两端进行shift和reduce？既然已经都读入了，为什么不随时进行shift和reduce呢？
我想我说的比较明了了吧？具体给你个例子吧，lcc，这个比较简单，lcc是以函数为单位进行编译的，顺序读入tok，build dag，独到一个函数的结束的时候，遍历dag reduce来CG。
lz的思路没转过来，计算机不是人，没那么智能，你老师给讲课的时候，说“向前看”一个tok，对于计算机来讲是“读入，并判断”，是计算出来的。

xyfree

回复 17# cjaizss

    请看3楼，就是你回复的那一段并且引用没有全引出来的那一段
   

回复  cjaizss

若有某种办法，双端识别，应该就可以减少尝试的路径的量吧？

当然这种办法的前提是有效地把输入串切割成小段。
这可能要对文法设计有一定的要求
xyfree 发表于 2010-03-10 16:18

    以及7楼

回复  Solidus

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

xyfree 发表于 2010-03-12 16:53

prolj

还记得你老师讲的各种文法么？什么算符优先文法，反正我是忘了。
就说LL个LR吧，为什么采用LL(1)的多？因为LL(0)太弱，分析不出来很多东西。为什么不用LR？应该问为什么现实中没有LR的实现？因为LR(n)，那得需要多大的一张表啊？分析一个语法4G内存够么？不光LR(n)，就连LR(1)的实现都没有，太大了，根本超出了计算可承受的范围。最多只有到LALR(1)和SLR(1)的实现，为什么？这是工程。
我最喜欢的一本书《编译器工程》，不断强调，编译器是一个工程，一个来自实践回到实践的工程。
要玩儿理论，计算理论非常好玩儿，最近几年的Arch方面的paper都是在灌水，一套纯理论上去，工业界压根没人关心，为啥？实现成本非常高，效果？。。。
我也希望能进研究院，整天玩儿理想化的计算模型，提出大胆的假设。反正现阶段不现实。