jsbison
jsbison copied to clipboard
acodercc
使用javascript实现的类似yacc/bison的语法解析器的生成器
现在的lrparse函数是查s/r表的，但s/r表是最终的确定型的动作表。 如果想要使jsbison能够支持更丰富的自定义动作，比如caliburn所要求用到的自动分号补全等等功能，那么查s/r表决定动作，不够灵活。 所以取消s/r表的生成，新增加一个ilrparse函数，直接根据itemsets表，决定动作。 甚至再下一步，直接根据cfg/productions/firsts/follows表来决定自动机动作。 这时就可以在决定动作时，增加更多的自定义功能。
从项集族的构造，到基于ItemSets的s/r表的生成，是shift/reduce的核心，虽然最终是查询s/r表决定自动机的工作，但ItemSets表，是将CFG -> productions / firsts / follows -> ItemSets -> s/r表，整个流程中核心的步骤。 1. LR(1)自动机，每个状态是一个项集。项集中每个项，其输入点可能在最后，也可能不在最后。 2. 在项集X中，输入点不在末尾的项i，会基于输入点位置的符号a，使用goto(X, a)函数创建一个新的项集Y。而新项集Y，和原项集X之间的关系，就是goto(X, a) === Y。 3. 项集中的每个项，其输入点后的符号，如果是一个终结符a，则在parse时，遇到这个token-a，就将自动机进入下一个状态，就是这个项集的goto表上，通过移入a转换到的下一个状态(项集)。
现在看来，基于当前符号栈的符号流，计算当前符号流是哪些产生式的可行前缀，已是无可避免必须要做的了。 可行前缀计算使用场景： ### 对**OfftendingToken(冒犯TOKEN)**的判定上，要使用可行前缀的概念。 _定义：如果将下一个token压入符号栈，会导致符号栈中的符号流不是任何产生式的可行前缀，那么这个token就是OfftendingToken。 *使用：caliburn项目要解析javascript，需要自动补全分号，有一条规则，就是在遇到OfftendingToken时，前面有一个LineTerminator，将前面的LineTerminator换成semicolon，或者这个OfftendingToken是一个'}'时，要在前面补上一个semicolon。 *具体做法：因为移进归约表，标记了每个状态下面临下一个符号时，应该执行移进动作，还是执行归约动作，如果查表时没查到任何动作，说明此时符号栈出现了问题，面对下一个TOKEN不知该移进还是该归约，__所以，此时的符号栈一定不是可行前缀了！！_* ### 对**RestrictedToken(受限TOKEN)**的判定上，要使用可行前缀的概念。 _定义：在es grammar描述中，特殊的文法修饰符号[noLineTerminator here]所出现的位置后面的token，被定义为RestrictedToken。 *使用：也是caliburn项目要解析javascript时，万恶的w3c es grammar中规定，在RestrictedToken前面如果出现了LineTerminator，则在该位置插入一个LineTerminator。 *具体做法：当归约时，判断当前归约的产生式的rhs符号中，是否有受限token，如果有的话，检查该受限token和前面的一个token之间，是否出现过被忽略的LineTerminator，如果出现过，则不使用该产生式进行归约，而是给输入流倒带，回退LineTerminator后面的TOKEN，然后符号栈也弹出相应的几个token，接下来，__给输入流倒带，手动回退进去一个LineTerminator！！_*
因为jsbision要对jsparser caliburn进行支持，而jsparser的自动分号补全规则中有要求，所以不仅要增加对受限token的支持，还支持haveLineTerminator状态。 但是无论是受限token，还是haveLineTerminator状态，都非标准的LR(1)移进归约解析器所该拥有的功能，两者必须适度抽象为对标准LR(1)移进归约解析器的增强。 一个是_状态的增强_，以后可能不仅仅是haveLineTerminator状态，还需要解析器支持其他状态，这个并不能由jsbison本身使用硬编码进行支持，而是应该在bnf的语法动作中进行支持。 第二个是_受限TOKEN_的增强，这个受限TOKEN，功能非常类似于jcon项目中解析器的lookhead组合子，所以有必要对其进行抽象，对bnf语法进行增强，使token在production出现的时，可以定义条件约束，，而不是在定义token时增加约束。
为 https://github.com/takumi4ichi/caliburn 项目的分号补全，以及除法TOKEN和正则TOKEN的区分，以及lookheadno(FUNCTION, {)而增加该功能需求。 比如 ``` bnf program -> line; line -> NUMBER ';' | IDENT [noLineTerminator] '++'; ; ``` 可以看出，这个接受以下句子： ``` text 123; abc++; ``` abc是一个IDENT，但是和下一个token_++_之间，出现了[noLineTerminator]，所以执行一些特殊的语法动作，来对自动插入分号的需求进行支持。 该功能从 [@jsinjs](https://github.com/kissjs/JSinJS/blob/master/source/SyntacticalParser.js) 中学习。...
方式：使用本程序将输入文件(bnf, Lex)，产生JSON格式jsbison-cfg数据对象，也用jison的bnfparser产生jison格式的cfg，基于两种cfg格式建立等价函数进行比较。 问题：要有各种典型输入的测试用例集，典型输入和语法规则表进行关联。
目前jsbison的goalSymbol的rhs的最后一个symbol不能为nullable的，既不能推导出epsilon来。 如果可以推导出epsilon来，在匹配所有的输入后，会陷入死循环，不断的应用这个推导出epsilon的产生式进行归约。。 需要debug
我们讲内核项（kernel item)，是基于项集A，经过goto(A, a)计算的直接结果项集，所有项的dotPosition在symbol-a的后面，dotPosition后面的symbol我们称为dotSymbol，dotSymbol可能是非终结符，也可能是终结符。 而对项集进行闭包运算后，新增的那些对dotSymbol为非终结符时，基于dotSymbol的各个产生式创建的dotPosition为0的项，都是非内核项。。 而我们说的项的核心(core)，是指LR1项中，产生式和dotPosition。。不包括LR1-Item的lookaheads符号，就是项的核心。 项的核心(core)这个概念，一般只用在合并LR1项集族中拥有相同核心的项集，成为LALR项集族时。
项集族中，每个项集都是由项构成的。。 项是由产生式，输入点，触发归约的前瞻符号列表，三部分构成。 当输入点在项的最后，且下个输入符号在触发归约的前瞻符号列表中，就可以根据这个项的产生式进行归约。 否则就进行移进操作，移进，就是将输入点位置的符号为输入符号的项的输入点后移，产生一个新的项，并基于这个新项，创建项集族。 这也就是goto函数做的，计算当前项集中每个输入点不在最后的项，基于这些项和输入点的符号，创建新的项，并产生新的项集，然后把新项集的编号设置到gotos(State, symbol)上。
需要将javascript文件，parse为json格式的解析树（用于代码高亮，语义置换等），以及json格式的规则AST（用于解释执行等需要遍历的地方）。