使用教程

1. 在 tscc 项目目录执行"npm i"安装 typescript
2. 在 tscc 项目目录执行"npm run pack"打包
3. 在你的项目目录执行"npm install path/to/tscc-xxx.tgz"安装

一个 LR(1)分析器，把 BNF 变成可用的编译器代码,example 中有用 TSCC 实现的正则引擎，一个 toy-language(这个项目已经放到 ty 里面了，不再是一个简单的 example)

产生式优先级和结合性:

默认由该产生式的最右侧终结符决定,如果定义了 priority,则使用 priority 对应符号所对应的优先级和结合性
需要注意的是:如果一个产生式最右终结符没有定义优先级和结合性,则产生式的优先级和结合性也为未定义,即使该产生式非最右终结符定义了优先级和结合性
如:
设有一产生式:A->B + C * D,其中终结符+定义了优先级和结合性,但是终结符*没有定义,则产生式的优先级和结合性也为未定义

规约-规约冲突:

选择优先级高的产生式进行规约,如果优先级一致则选择序号小的产生式,并提示规约-规约冲突(因为规约-规约冲突比较难发现，所以所有的规约-规约冲突都会提示)
这里和 yacc 不一致,yacc 只选择序号小的产生式,(这里是我观察的结果,对 Yacc 行为的描述不一定完全正确,因为我没有看 Yacc 的源码,只是通过编写一些特定的产生式,观察 Yacc 的输出,但是对于我自己编写的 tscc,他的行为是和我描述完全一致的)yacc 使用%prec 强制指定产生式优先级时不是无条件的把产生设置成和%prec 的符号一致,所以如果遇到一个状态又有移入-规约冲突,又有规约-规约冲突时,tscc 会和 yacc 不一致,假设有如下文法:

S:A
S:B y
S:C y
A:x y
B:x
C:x

则会存在包含如下三个项的一个状态:

1. A:x .y,$
2. B:x .,y
3. C:x .,y

对于输入 y,项 1 分别和项 2、项 3 产生移入-规约冲突。项 2 和项 3 产生了规约-规约冲突 如果我们用 priority 指定符号和产生式优先级(括号中)如下

符号y(2)
1. A:x .y,$
2. B:x .,y (1)
3. C:x .,y (3)

如果按照 yacc 的规约-规约冲突选择产生式序号小的项规约,则

1. 符号 y 和项 2 的移入-规约冲突中,我们应该选择移入,此时移入操作的优先级为 2
2. 符号 y 项 1 和项 3 的冲突选择项 3 进行规约(产生式优先级大于符号优先级)

如果我们换个对比序

1. 符号 y 和项 3 的移入-规约冲突中,我们应该选择规约,此时规约操作的优先级为 3
2. 项 3 和项 2 的冲突选择项 2 进行规约(选择序号小的产生式)

可见如果只选择产生式序号小的项进行规约,不同的对比顺序在 tscc 中会产生不一样的结果,所以我们选择优先级作为判断条件,只有优先级相等时才对比产生式序号

移入-规约冲突:

本条说明中用"产生式"代指冲突中需要规约而成的产生式,用符号表示向前看符号(即将移入的符号),如果出现移入-规约冲突,使用下面的规则进行处理:
优先级的定义请参见:grammar.association一节

1. 产生式优先级大于符号,选择规约操作;
2. 产生式优先级等于符号:

   1. 产生式结合性为左结合,选择规约操作;
   2. 产生式结合性为右结合,选择移入操作;
   3. 产生式结合性为不结合,提示移入-规约冲突,并将冲突的符号设置为 err(技术细节请看下面说明)

3. 产生式优先级小于符号优先级,选择移入操作;
4. 如果产生式和符号有一个定义了优先级,另一个没有定义(undefine),则认为 undefine 优先级小于任何已定义的优先级,根据规则 1、3 进行操作,并提示移入-规约冲突;
5. 如果符号和产生式都没有定义优先级,提示移入-规约冲突,并停止后续分析

对 nonassoc 的处理和 left 类似,当一个状态中出现移入-规约冲突时(文法出现二义性),规约而成的产生式优先级和移入符号优先级一致,且产生式的结合性为 nonassoc,tscc 内部会将这个冲突的解决方法设置为规约进行后续处理,在最终输出跳转表的时候将这个动作设置为 err

优先级和结合性是用于解决文法二义性的,如果文法本身没有出现二义性,则符号和产生式的优先级和结合性将会毫无意义,假设有如下文法:

association:[
    {'nonassoc':['a','s']}
]
S:A s
A:a

或者

association:[
    {'nonassoc':['a','s']}
]
S:A
S:B
A:a
B:b a s

如果试图通过定义 a,s 为同一优先级的非结合终结符来避免 a 和 s 结合,会发现没有任何作用,因为文法不是一个二义性文法。
nonassoc 的真正作用是用于如下情况:

结合性:
+:left
>:nonassoc

文法:
exp:exp + exp
exp:exp > exp

则输入"a+b+c"会有如下二义性:可以解析为"(a+b)+c"或者"a+(b+c)"，这时候'+'的左结合就会让解析器选择前面的一个产生式。而"a>b>c"同样的可以解析为:"(a>b)>c"或者"a>(b>c)"，而因为'>'是nonassoc的，所以解析器直接报错。要想正确的实现nonassoc，还得通过语义分析,比如用户直接输入"(a>b)>c"，我们应该在语义检查阶段判断'>'的左右侧是否都是数字。 语义分析的事情就该放到语义分析阶段做

使用说明

使用 import tscc from "tscc.js"导入 tscc 模块,然后 new tscc(grammar,argument)即可,grammar 包含和文法的 BNF 和词法的正则规则。

grammar

grammar 原型如下:

interface Grammar {
    userCode?:string,
    association?: { [key: string]: string[] }[],
    symbols: {
        symbol: string;
        value?: (args: string) => any;
        reg: RegExp;
    }[];
    tokens?:string[];
    accept?: (args: any[]) => any;
    BNF: {
        [key: string]: {
            action?: ((args: any[]) => any);
            priority?: string;
        };
    }[];
}

userCode

可选

userCode?:string

用户的自定义代码，会被放在 parser 的最前面，可以用于自定义一些 class 或者 interface

association

可选

association?:[{
   key:[symbol]
}]

association 为一个数组,数组中每个元素为一个以'left'、'right'或者'nonassoc'为 key 的属性,表示符号的符号的结合性,属性值为一个 string 数组,表示当前 key 所描述的符号,以在 association 数组中所定义的下标作为终结符优先级,下标大的符号优先级高。如果一个符号在数组中的多个对象中被定义,后面的定义会覆盖前面的定义。
例：

association:[
    {'left':['+','-']},
    {'left':['*','/']},
    {'right': [`uminus`] }
]

定义了四个左结合的终结符"+"、"-"、"*"、"/",其中"*"、"/"的优先级大于"+"、"-"。 一个右结合的终结符 uminus,优先级最高(在数组中的序号最大)
需要注意的是:*与类似 yacc 或者 bison 中进行分析一样,在解决冲突时,符号的结合性是没用的,实际上符号只有优先级,产生式才有优先级和结合性,对符号定义结合性的原因是为了将这个结合性赋予对应的产生式*

tokens

可选
定义 BNF 中的终结符,一个字符串数组,每个元素为一个终结符,如果终结符在 association 中定义过,也可以不在 tokens 中再次定义
系统内置了两个终结符:"ε","$",分别表示空和结束(EOF)
例:

tokens:['+','-','*','/']

BNF

   BNF: {
       [key: string]: {
           action?: ((args: any[]) => any);
           priority?: string;
       };
   }[];

symbols 为一个数组,数组中每个元素为一个产生式,元素的 key 为产生式定义描述字符串,值为一个包含属性 action 和 priority 的对象,这两个属性都可以为 undefine。

key

产生式定义字符串编写规则如下:

A:B C D
A:

当产生式体为空时,自动为其补充产生式体 ε,所以上面第二个产生式

A:

等价于:

A:ε

BNF 编写中的一些需要注意的点

1. 如果同一个产生式出现多次,虽然在 debug 等途径中这些产生式看起来一样,但是在实际处理中他们会被当成不同的产生式,如:

   A:a
   A:a

   会被 tscc 理解成:

   S1=A:a
   S2=A:a

   通过 debug 等渠道打印状态表时,看到的还是 A:a 和 A:a,并且这种情况还会出现规约-规约冲突,相当于在这个状态中可以规约成产生式 S1 或者规约成产生式 S2，这和 bison 处理结果一致

2. 如果一个符号没有在 tokens 或者 association 中定义过,则这个符号会被当成非终结符处理
3. 产生式中的符号不能包含"$","@","#"这三个字符。
4. 如果文法中某个产生式重来没有被规约过,则提示：下面这些产生式没有被使用(规约)过或者 rules useless in grammar
5. 起始符号:用户定义的第一条产生式的头部为文法的起始符号
6. tscc 会自动在产生式数组最前面插入一个产生式构成增广文法,目的是告诉语法分析器什么时候停止解析并宣布成功解析输入的符号串

   假设编写了如下的产生式,第一条产生式为:S->A

   S->A
   A->a
   A->B
   B->b

   则 tscc 会自动生成一个产生式:S'->S,使得上面的产生式列表变成

   S'->S
   S->A
   A->a
   A->B
   B->b

   规则为:取用户输入的第一个产生式头的符号 A(起始符号),然后添加一个产生式 A'->A,在符号 A 的后面追加一个字符',使 A'->A 成为整个文法的第一条产生式,yacc 也用类似的方法增加一条产生式

   $accept-> A $end

7. 如果文法的起始符号没有推导任何有效句子,即 first(start_symbol)为空(不是为 ε,ε 也是一个符号,而是在计算 first 集合的时候没有得到任何终结符),则抛出异常"起始符号 A 没有推导出任何句子"
8. 提示信息远远没有 yacc 丰富,很多提示规则也是我边想边添加的,以后遇到新问题继续添加提示

priority

参考产生式优先级和结合性一节

action

action 为一个函数,当输入的单词能够规约成这条产生式时,就会调用本函数,所以可以叫做规约动作。传入的参数为一个数组,数组的元素分别为产生式体中的符号,产生式头的值被设置为规约动作的返回值。
需要注意的是:ε 会被忽略,即对于产生式 A:ε B ε C 来说,规约动作的参数数组长度为 2,并且 args[0]对应符号 B 的值,args[1]对应符号 C 的值,产生式体中的 ε 被跳过

中间动作:

action 的第二个参数被设置为语法分析栈中的符号，这是因为 yacc 或者 bison 可以在一条产生式的中间插入产生式动作，而 tscc 可以做到一样的功能，但是写法有些区别
在 yacc 中,如果对一条产生式规则 E:E + E ,在产生式中间定义了一个动作,在末尾定义了一个规约动作,如下:

E:E '+' {printf("中间动作,第一个符号%d,第二个符号:%d",$1,$2);} E {$$=$1+$4;};

则本质上 yacc 是在产生式的中间插入了一个非终结符,然后将中间动作设置为这个非终结符的规约动作,可以看到产生的规约动作取第二个 E 的时候用$4,而不是$3,并且中间动作中的$$表示的也是插入产生头部的值,将从分析栈中提取栈顶的两个符号(不弹出,只取值)赋给动作的$1,$2 等变量,如下:

E:E '+' Tmp E;
Tmp: ε {printf("中间动作,第一个符号%d,第二个符号:%d",$1,$2);};//$1为前面一条产生式中的符号E,$2前面一条产生式的符号'+'

因为 yacc 在解析.y 文件的时候知道中间动作的位置,所以能自动从栈中取出确定数量的符号给中间动作使用,而 tscc 对动作没有任何解析,直接使用了 js 函数原型作为动作(因为编写 BNF 的解析也需要时间,像 bison 就用自己编写了自己的.y 文件解析器,而因为时间成本问题,tscc 暂时没这么做，因为 js 本身的灵活性,tscc 的 BNF 定义规则可读性也还不错),所以需要自己定义插入符号,然后自行从分析栈中取得符号

BNF:[
   {"E:E + tmp E":{action:(args)=>{return args[0]+args[3];}}},
   {"tmp:":{action:(args,stack)=>{
    let sym=stack.slice(-2);//取栈中最后两个符号,得到的就是E和+
    console.log(`${sym[0]}:${sym[1]}`);
   }}}
]

BNF 例子:

BNF:[{ "exp:exp + exp": { action: function (args) { return args[0] + args[2]; } } },//将产生式体第一个exp和第二个exp相加,结果赋予产生式头
{ "exp:number": { action: function (args) { return args[0]; } } },//将产生式体第一个符号的值赋予产生式头
{ "exp:- number": { action: function (args) { return -args[0]; }, priority: "uminus" } }]//定义产生式的优先级和结合性与符号uminus相同,将exp的值取反

accept

可选

accept?: (args: any[]) => any;

accept 为增广文法成功规约时的规约动作,设 BNF 中定义的第一个产生式为 A:B C,tscc 会自动添加一个产生式 A':A,并将规约动作设置为 accept,并且将 accept 的返回值作为 parse 方法的返回值。
例:

accept:function(args){console.log('编译完成');}

argument

agrument 定义如下:

{
   debug: boolean,
   language: "zh-cn" | "en-us"
}

debug:tscc 是否输出 LR(1)项集族和跳转表,方便用户调试 language:目前只能为"zh-cn"或者"en-us",控制 tscc 的调试语言和生成代码中提示的语言

错误恢复

tscc 的错误恢复采用和 yacc 类似的策略,如果用户定义了一个形如 A: α error β 的错误处理产生式,则当语法分析器遇到一个错误时,会不断的从分析栈中弹出符号,直到栈中的一个状态包含形如 A-> α .error β 的项(简单来说就是直到遇到一个能移入 error 的状态),然后语法分析器就假装在输入中遇到了 error,执行移入操作,在移入之后从词法分析器中抛弃一系列符号,直到新的输入能正常进行语法分析为止。

注意:error 是一个内置终结符

tscc 的输出

tscc 会输出一个字符串,这个字符串是一段合法的 typescript 代码,里面包 Parser 这个类,用户可以在后面增加一行代码调用这个类:

new Parser().parse(new Lex());//Lex为词法分析器

parser 的使用

如上面所说,使用 tscc 生成 parser 之后,调用这个类的 parse 方法即可,该方法的返回值为 accept 定义的返回值,如果在分析过程中遇到错误，将会调用 yyerror 函数提示并抛出 ParseException 异常,其他自定义异常用户可自行处理

demo

参考四则运算 demo"/src/example/calculate/readme.md"

一些常见错误原因分析

1. 存在无法计算 first 集合的符号串

   串中的某个非终结符不能推导出 first 集合,如下面的文法

   S->S a

   其中 S 为非终结符,a 为终结符,first(S)无法计算

2. 存在无法推导的非终结符

   某个符号无法推导出任何符号,如下面的文法

   S->A

   其中 S 和 A 都为非终结符,很明显在 first(S)=first(A),然而非终结符 A 没有任何有效推导
   或者:

   S->S α

   这种悬空递归文法也是没有任何有效推到的

LR(K)文法局限性

存在很多 CFG(context free grammar,上下文无关文法)是 LR(1)分析办法解决不了的,如:

token: a b c d e

S:a A c d
S:a B c
A:B
B:b

可以看出上述文法并没有二义性,输入:a b c 的时候,因为如果后续是 d 则应该把 b 按照 A->B->b 的路径反向归约,如果后续输入是文件结束符,则应该按照 B->b 归约即可,然而 LR(1)分析器只向后读取一个符号,所以只能知道下一个符号是 c,所以理所当然的出现了二义性,如果使用 LR(2)解析器则可以解决上述冲突。
上面这个文法会出现规约-规约冲突，下面这个文法就会出现移入/规约冲突

S:a A b c
S:a B d
A:
B:b

究其原因,本质上就是对于 LR(k)分析器而言,如果任意两个产生式从推导路径分叉点开始有 k 个终结符序列一致,则这两个产生式就会出现冲突,如上述第二个例子,假设输入序列是"a b c",当分析器移入终结符 a 之后会进入一个如下的状态:

S->a .A b c ,$
S->a .B d ,$
A->ε .,b
B->.b ,d

此时就会出现移入/规约冲突,当然你也可以理解成另类的规约-规约冲突:

1. 把 b 规约成串"A b"(其中 A 为 ε)
2. 把 b 规约成串"B"

这是因为 LR(1)只会向前看一个符号,对于输入符号"b"而言,"A b"和"B"这两个路径都可以推导出串"b"
这也是前面所说,如果用 LR(k) k 大于 1 的文法分析器来分析这个文法,就不会出现冲突,但是如果我们可以很容易构造一个文法,在两个以上不同的路径中出现 k 个终结符序列一致的情况,则这个分析器同样会失效
当然 GLR 分析器理论上可以分析所有 CFG,因为 GLR 会把所有可能的路径都走一遍,相当于一个 LR(∞)解析器,当然相应的分析效率就会大幅度下降

我在设计文法的时候也遇到过类似情况
one_immediate_arr:[ number ]  //长度为1的立即数组 如 [10]
obj:( type ) obj //类型转换
对于输入:(int)[],
冲突如下:
1.把数组[]强制转型为int
2.声明一个int数组
实际上根据我的文法定义,是不允许定义空白数组的，所以上述输入应该按照情况2规约，但是提示的冲突点是符号'[',因为向前看一个符号的时候看到了'[',还得再看第二个符号是不是number才能做出决策

和 Yacc 的不同

1. 对于规约-规约冲突处理规则不同,具体请参阅规约-规约冲突一节
2. Yacc 是 LALR 分析器，相对于 LR(1)分析器有些不同,比如对于著名的 if-else 冲突,如果想要让 else 和最近的 if 结合,则 Yacc 和 tscc 都能够得到正确的分析程序,但是如果你想要搞点怪的,让 else 和最远的 if 结合,则 Yacc 就无法生成这种程序了,因为 LALR 相对于 LR(1)少了很多状态(内存空间),相应的语法分析能力要欠缺一点