其实这就是一个并行parse的问题,从传统的文法解析和自动机角度来说,这个过程的并行化程度有限,顶多取代部分回溯操作。但是如果我们抛弃常规思维的话,会发现还是有很多地方可以改为并行化的。典型的来说,每个源代码文件就可以作为独立的单元并行解析。当然,我认为目前的分析简单的分为词法分析和语法分析还是很糙的。要最大可能扩大并行度,我们要分层解析,原理是每一层负责将要解析的文本拆分成多个独立的解析单元以扩大并行度。解析单元如json的{},HTML的标签,CSV的行。
当然,很显然不是所有的语言解析都可以面向并行优化,但是在多核多线程的今天,如何提高编译并行度以充分利用硬件性能是很重要的。
以C#语言为例,我所构思的分层解析可以这样:
第一层:字符串和注释以及条件编译符号解析,语句块和语句解析。
经过第一层解析之后的结果是语句树,每一个叶节点是一条语句,每一个非叶节点是一个语句块,语句中可能包含字符串。
第二层A:语句和表达式解析,将每一条语句解析为初步AST,此时符号尚未绑定。因为这一层面向语句,并行度极高。
第二层B:语句块解析,语句块符号表绑定。
第二层A和第二层B操作可以同时进行。
第三层:根据第二层处理的语句块符号表,将AST中的符号与具体的元素(类型、方法、字段、变量、运算符等)进行绑定。
第四层:语法检查,对AST进行语法检查,提取语法错误,并将AST进一步修缮为最终表达式树。
举例说明:
using System; namespace MyTest { public class Test { private String str = "123"; //get a string; public string GetString() { return str; } } }
第一层解析后的结果为:
S:using System; B:namespace MyTest { B:public class Test { S:private String str = T:"123"; B:public string GetString() { S:return str; } } }
第二层A,提取所有语句解析为初步AST:
S:using System; => using ( System ) S:private String str = T:"123"; => modifier:private, type:String, name:str, value:T"123" S:return str => return, value:str
第二层B:
B:namespace MyTest { imported: namespace System namespace: MyTest } B:public class Test { impoerted: namespace System namespace: MyTest class: Test } B:public string GetString() { impoerted: namespace System namespace: MyTest class: Test }
第三层:
S:using System; => using ( namespace:System ) S:private String str = T:"123"; => modifier:private, type:System.String, name:str, value:C:"123":string S:return str => return, value:field:str