JS如何实现AST抽象语法树
小编给大家分享一下JS如何实现AST抽象语法树，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！
前端中的AST抽象语法树问题
四则运算
正则表达式
词法分析
语法分析
完整代码
四则运算
首先明确，此次的代码都是基于LL的语法分析来实现的，实现的是四则混合运算的功能，先看下定义： TokenNumber：· 1 2 3 4 5 6 7 8 9 0 的组合 Operator:+ - * / 之一 WhiteSpace:<SP> LineTerminator:<LF> <CR>
看下产生式：
正则表达式
我们首先实现正则表达式的匹配原则：
<script>
varregexp=/([0-9\.]+)|([\t]+)|([\r\n]+)|(\*)|(\/)|(\+)|(\-)/g
vardictionary=["Number","Whitespace","LineTerminator","*","/","+","-"];
functiontokenize(source){
varresult=null;
while(true){
result=regexp.exec(source);
if(!result)break;
for(vari=1;i<=dictionary.length;i++){
if(result[i])
console.log(dictionary[i-1]);
}
console.log(result);
}
}
tokenize("1024+10*25");</script>此时我们看一下页面的运行打印结果：
值得一提的是这里用到了exec方法，exec() 方法用于检索字符串中的正则表达式的匹配。 我们看一下它的语法：RegExpObject.exec(string)
如果 exec() 找到了匹配的文本，则返回一个结果数组。否则，返回 null。此数组的第 0 个元素是与正则表达式相匹配的文本，第 1 个元素是与 RegExpObject 的第 1 个子表达式相匹配的文本（如果有的话），第 2 个元素是与 RegExpObject 的第 2 个子表达式相匹配的文本（如果有的话），以此类推。除了数组元素和 length 属性之外，exec() 方法还返回两个属性。index 属性声明的是匹配文本的第一个字符的位置。input 属性则存放的是被检索的字符串 string。我们可以看得出，在调用非全局的 RegExp 对象的 exec() 方法时，返回的数组与调用方法 String.match() 返回的数组是相同的。
但是，当 RegExpObject 是一个全局正则表达式时，exec() 的行为就稍微复杂一些。它会在 RegExpObject 的 lastIndex 属性指定的字符处开始检索字符串 string。当 exec() 找到了与表达式相匹配的文本时，在匹配后，它将把 RegExpObject 的 lastIndex 属性设置为匹配文本的最后一个字符的下一个位置。这就是说，您可以通过反复调用 exec() 方法来遍历字符串中的所有匹配文本。当 exec() 再也找不到匹配的文本时，它将返回 null，并把 lastIndex 属性重置为 0。
词法分析
我们在这一部分对上面的代码做优化。 首先是刚才提到的:当 RegExpObject 是一个全局正则表达式时，exec() 的行为就稍微复杂一些。它会在 RegExpObject 的 lastIndex 属性指定的字符处开始检索字符串 string。当 exec() 找到了与表达式相匹配的文本时，在匹配后，它将把 RegExpObject 的 lastIndex 属性设置为匹配文本的最后一个字符的下一个位置。 那么我们就要考虑到没有匹配上字符的情况，做一个判断处理：
<script>
varregexp=/([0-9\.]+)|([\t]+)|([\r\n]+)|(\*)|(\/)|(\+)|(\-)/g
vardictionary=["Number","Whitespace","LineTerminator","*","/","+","-"];
function*tokenize(source){
varresult=null;
varlastIndex=0;
while(true){
lastIndex=regexp.lastIndex;
result=regexp.exec(source);
if(!result)break;
if(regexp.lastIndex-lastIndex>result[0].length)
break;
lettoken={
type:null,
value:null
}
for(vari=1;i<=dictionary.length;i++){
if(result[i])
token.type=dictionary[i-1];
}
token.value=result[0];
yieldtoken}
yield{
type:'EOF'
}
}
for(lettokenoftokenize("1024+10*25")){
console.log(token)
}</script>如上，我们对regexp.lastIndex - lastIndex 和 result[0] 的长度进行比较，判断是否有字符串没有匹配上。 将整个函数改成generator函数的形式，我们看下运行的结果：
语法分析
首先编写分块的产生式，我们看一下总的代码结构：
<script>
varregexp=/([0-9\.]+)|([\t]+)|([\r\n]+)|(\*)|(\/)|(\+)|(\-)/g
vardictionary=["Number","Whitespace","LineTerminator","*","/","+","-"];
function*tokenize(source){
varresult=null;
varlastIndex=0;
while(true){
lastIndex=regexp.lastIndex;
result=regexp.exec(source);
if(!result)break;
if(regexp.lastIndex-lastIndex>result[0].length)
break;
lettoken={
type:null,
value:null
}
for(vari=1;i<=dictionary.length;i++){
if(result[i])
token.type=dictionary[i-1];
}
token.value=result[0];
yieldtoken}
yield{
type:'EOF'
}
}
letsource=[];
for(lettokenoftokenize("10*25")){
if(token.type!=="Whitespace"&&token.type!=="LineTerminator")
source.push(token);
}
functionExpression(tokens){
}
functionAdditiveExpression(source){
}
functionMultiplicativeExpresson(source){
console.log(source);
}
MultiplicativeExpresson("10*25")</script>我们先从MultiplicativeExpresson来进行研究，它分为四种情况：
functionMultiplicativeExpresson(source){
//如果是数字则进行封装
if(source[0].type==="Number"){
letnode={
type:"MultiplicativeExpresson",
children:[source[0]]
}
source[0]=node;
returnMultiplicativeExpresson(source)
}
//如果是乘号或者除号，则将三项出栈，进行重组
if(source[0].type==="MultiplicativeExpresson"&&source[1]&&source[1].type==="*"){
letnode={
type:"MultiplicativeExpresson",
operator:"*",
children:[]
}
node.children.push(source.shift());
node.children.push(source.shift());
node.children.push(source.shift());
source.unshift(node);
returnMultiplicativeExpresson(source)
}
if(source[0].type==="MultiplicativeExpresson"&&source[1]&&source[1].type==="/"){
letnode={
type:"MultiplicativeExpresson",
operator:"*",
children:[]
}
node.children.push(source.shift());
node.children.push(source.shift());
node.children.push(source.shift());
source.unshift(node);
returnMultiplicativeExpresson(source)
}
//递归结束的条件
if(source[0].type==="MultiplicativeExpresson")
returnsource[0];
returnMultiplicativeExpresson(source);
}我们看一下当source为"10 * 25 / 2"时调用console.log(MultiplicativeExpresson(source))最后运行的结果：
接下来看AdditiveExpression 本质上和MultiplicativeExpresson没有什么不同，差异点已经标注在代码当中了：
functionAdditiveExpression(source){
if(source[0].type==="MultiplicativeExpresson"){
letnode={
type:"AdditiveExpression",
children:[source[0]]
}
source[0]=node;
returnAdditiveExpression(source)
}
//如果是乘号或者除号，则将三项出栈，进行重组
if(source[0].type==="AdditiveExpression"&&source[1]&&source[1].type==="+"){
letnode={
type:"AdditiveExpression",
operator:"+",
children:[]
}
node.children.push(source.shift());
node.children.push(source.shift());
//考虑到第三个数可能时Number需要在这里再次调用一下MultiplicativeExpresson做处理
MultiplicativeExpresson(source);
node.children.push(source.shift());
source.unshift(node);
returnAdditiveExpression(source)
}
if(source[0].type==="AdditiveExpression"&&source[1]&&source[1].type==="-"){
letnode={
type:"AdditiveExpression",
operator:"-",
children:[]
}
node.children.push(source.shift());
node.children.push(source.shift());
MultiplicativeExpresson(source);
node.children.push(source.shift());
source.unshift(node);
returnAdditiveExpression(source)
}
//递归结束的条件
if(source[0].type==="AdditiveExpression")
returnsource[0];
//第一次进循环调用
MultiplicativeExpresson(source);
returnAdditiveExpression(source);
}我们看一下当source为"10 * 25 / 2"时调用console.log(AdditiveExpression(source))最后运行的结果：
那么Expression的代码逻辑就很好表达了：
functionExpression(tokens){
if(source[0].type==="AdditiveExpression"&&source[1]&&source[1].type==="EOF"){
letnode={
type:"Expression",
children:[source.shift(),source.shift()]
}
source.unshift(node);
returnnode;
}
AdditiveExpression(source);
returnExpression(source);
}看下运行后的结果：
以上就是所有的js解析抽象语法树的代码。
完整代码
<script>
varregexp=/([0-9\.]+)|([\t]+)|([\r\n]+)|(\*)|(\/)|(\+)|(\-)/g
vardictionary=["Number","Whitespace","LineTerminator","*","/","+","-"];
function*tokenize(source){
varresult=null;
varlastIndex=0;
while(true){
lastIndex=regexp.lastIndex;
result=regexp.exec(source);
if(!result)break;
if(regexp.lastIndex-lastIndex>result[0].length)
break;
lettoken={
type:null,
value:null
}
for(vari=1;i<=dictionary.length;i++){
if(result[i])
token.type=dictionary[i-1];
}
token.value=result[0];
yieldtoken}
yield{
type:'EOF'
}
}
letsource=[];
for(lettokenoftokenize("10*25/2")){
if(token.type!=="Whitespace"&&token.type!=="LineTerminator")
source.push(token);
}
functionExpression(tokens){
if(source[0].type==="AdditiveExpression"&&source[1]&&source[1].type==="EOF"){
letnode={
type:"Expression",
children:[source.shift(),source.shift()]
}
source.unshift(node);
returnnode;
}
AdditiveExpression(source);
returnExpression(source);
}
functionAdditiveExpression(source){
if(source[0].type==="MultiplicativeExpresson"){
letnode={
type:"AdditiveExpression",
children:[source[0]]
}
source[0]=node;
returnAdditiveExpression(source)
}
//如果是乘号或者除号，则将三项出栈，进行重组
if(source[0].type==="AdditiveExpression"&&source[1]&&source[1].type==="+"){
letnode={
type:"AdditiveExpression",
operator:"+",
children:[]
}
node.children.push(source.shift());
node.children.push(source.shift());
//考虑到第三个数可能时Number需要在这里再次调用一下MultiplicativeExpresson做处理
MultiplicativeExpresson(source);
node.children.push(source.shift());
source.unshift(node);
returnAdditiveExpression(source)
}
if(source[0].type==="AdditiveExpression"&&source[1]&&source[1].type==="-"){
letnode={
type:"AdditiveExpression",
operator:"-",
children:[]
}
node.children.push(source.shift());
node.children.push(source.shift());
MultiplicativeExpresson(source);
node.children.push(source.shift());
source.unshift(node);
returnAdditiveExpression(source)
}
//递归结束的条件
if(source[0].type==="AdditiveExpression")
returnsource[0];
//第一次进循环调用
MultiplicativeExpresson(source);
returnAdditiveExpression(source);
}
functionMultiplicativeExpresson(source){
if(source[0].type==="Number"){
letnode={
type:"MultiplicativeExpresson",
children:[source[0]]
}
source[0]=node;
returnMultiplicativeExpresson(source)
}
//如果是乘号或者除号，则将三项出栈，进行重组
if(source[0].type==="MultiplicativeExpresson"&&source[1]&&source[1].type==="*"){
letnode={
type:"MultiplicativeExpresson",
operator:"*",
children:[]
}
node.children.push(source.shift());
node.children.push(source.shift());
node.children.push(source.shift());
source.unshift(node);
returnMultiplicativeExpresson(source)
}
if(source[0].type==="MultiplicativeExpresson"&&source[1]&&source[1].type==="/"){
letnode={
type:"MultiplicativeExpresson",
operator:"*",
children:[]
}
node.children.push(source.shift());
node.children.push(source.shift());
node.children.push(source.shift());
source.unshift(node);
returnMultiplicativeExpresson(source)
}
//递归结束的条件
if(source[0].type==="MultiplicativeExpresson")
returnsource[0];
returnMultiplicativeExpresson(source);
}
console.log(Expression(source))</script>以上是“JS如何实现AST抽象语法树”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注恰卡编程网行业资讯频道！
相关文章
本站已关闭游客评论，请登录或者注册后再评论吧~
热门文章
保利为什么叫央企之王(保利是国企还是央企)
2022-07-06
恢复外国人入境时间表(中国取消14天隔离政策了吗)
2021-06-19
香港哪些明星是反港分子(已背叛祖国的明星名单)被国家拉入黑名单明星
2021-04-20
身份造假与销售话术(记者卧底世纪佳缘 揭秘“红娘”)
2021-12-08
PyCharm怎么连接配置mysql数据库?
2021-06-29
如何将cda格式文件转换为mp3格式(cda格式怎么转换成mp3)
2021-12-11