溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下JS如何實現AST抽象語法樹，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！
前端中的AST抽象語法樹問題
四則運算
正則表達式
詞法分析
語法分析
完整代碼
四則運算
首先明確，此次的代碼都是基于LL的語法分析來實現的，實現的是四則混合運算的功能，先看下定義：
TokenNumber：· 1 2 3 4 5 6 7 8 9 0 的組合
Operator:+ - * / 之一
WhiteSpace:<SP>
LineTerminator:<LF> <CR>
看下產生式：
正則表達式
我們首先實現正則表達式的匹配原則：
<script>
var regexp = /([0-9\.]+)|([ \t]+)|([\r\n]+)|(\*)|(\/)|(\+)|(\-)/g
var dictionary = ["Number", "Whitespace", "LineTerminator", "*", "/", "+", "-"];
function tokenize(source) {
var result = null;
while(true) {
result = regexp.exec(source);
if(!result) break;
for(var i = 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>
var regexp = /([0-9\.]+)|([ \t]+)|([\r\n]+)|(\*)|(\/)|(\+)|(\-)/g
var dictionary = ["Number", "Whitespace", "LineTerminator", "*", "/", "+", "-"];
function* tokenize(source) {
var result = null;
var lastIndex = 0;
while(true) {
lastIndex = regexp.lastIndex;
result = regexp.exec(source);
if(!result) break;
if(regexp.lastIndex - lastIndex > result[0].length)
break;
let token = {
type: null,
value: null
}
for(var i = 1; i <= dictionary.length; i ++) {
if(result[i])
token.type = dictionary[i - 1];
}
token.value = result[0];
yield token }
yield {
type: 'EOF'
}
}
for (let token of tokenize("1024 + 10 * 25")) {
console.log(token)
}</script>如上，我們對regexp.lastIndex - lastIndex 和 result[0] 的長度進行比較，判斷是否有字符串沒有匹配上。
將整個函數改成generator函數的形式，我們看下運行的結果：
語法分析
首先編寫分塊的產生式，我們看一下總的代碼結構：
<script>
var regexp = /([0-9\.]+)|([ \t]+)|([\r\n]+)|(\*)|(\/)|(\+)|(\-)/g
var dictionary = ["Number", "Whitespace", "LineTerminator", "*", "/", "+", "-"];
function* tokenize(source) {
var result = null;
var lastIndex = 0;
while(true) {
lastIndex = regexp.lastIndex;
result = regexp.exec(source);
if(!result) break;
if(regexp.lastIndex - lastIndex > result[0].length)
break;
let token = {
type: null,
value: null
}
for(var i = 1; i <= dictionary.length; i ++) {
if(result[i])
token.type = dictionary[i - 1];
}
token.value = result[0];
yield token }
yield {
type: 'EOF'
}
}
let source = [];
for(let token of tokenize("10 * 25")) {
if (token.type !== "Whitespace" && token.type !== "LineTerminator")
source.push(token);
}
function Expression(tokens) {
}
function AdditiveExpression(source){
}
function MultiplicativeExpresson(source) {
console.log(source);
}
MultiplicativeExpresson("10 * 25")</script>我們先從MultiplicativeExpresson來進行研究，它分為四種情況：
function MultiplicativeExpresson(source) {
//如果是數字則進行封裝
if(source[0].type === "Number") {
let node = {
type: "MultiplicativeExpresson",
children:[source[0]]
}
source[0] = node;
return MultiplicativeExpresson(source)
}
//如果是乘號或者除號，則將三項出棧，進行重組
if(source[0].type === "MultiplicativeExpresson" && source[1] && source[1].type === "*") {
let node = {
type: "MultiplicativeExpresson",
operator: "*",
children: []
}
node.children.push(source.shift());
node.children.push(source.shift());
node.children.push(source.shift());
source.unshift(node);
return MultiplicativeExpresson(source)
}
if(source[0].type === "MultiplicativeExpresson" && source[1] && source[1].type === "/") {
let node = {
type: "MultiplicativeExpresson",
operator: "*",
children: []
}
node.children.push(source.shift());
node.children.push(source.shift());
node.children.push(source.shift());
source.unshift(node);
return MultiplicativeExpresson(source)
}
//遞歸結束的條件
if(source[0].type === "MultiplicativeExpresson")
return source[0];
return MultiplicativeExpresson(source);
}我們看一下當source為"10 * 25 / 2"時調用console.log(MultiplicativeExpresson(source))最后運行的結果：
接下來看AdditiveExpression 本質上和MultiplicativeExpresson沒有什么不同，差異點已經標注在代碼當中了：
function AdditiveExpression(source){
if(source[0].type === "MultiplicativeExpresson") {
let node = {
type: "AdditiveExpression",
children:[source[0]]
}
source[0] = node;
return AdditiveExpression(source)
}
//如果是乘號或者除號，則將三項出棧，進行重組
if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "+") {
let node = {
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);
return AdditiveExpression(source)
}
if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "-") {
let node = {
type: "AdditiveExpression",
operator: "-",
children: []
}
node.children.push(source.shift());
node.children.push(source.shift());
MultiplicativeExpresson(source);
node.children.push(source.shift());
source.unshift(node);
return AdditiveExpression(source)
}
//遞歸結束的條件
if(source[0].type === "AdditiveExpression")
return source[0];
//第一次進循環 調用
MultiplicativeExpresson(source);
return AdditiveExpression(source);
}我們看一下當source為"10 * 25 / 2"時調用console.log(AdditiveExpression(source))最后運行的結果：
那么Expression的代碼邏輯就很好表達了：
function Expression(tokens) {
if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "EOF") {
let node = {
type: "Expression",
children: [source.shift(), source.shift()]
}
source.unshift(node);
return node;
}
AdditiveExpression(source);
return Expression(source);
}看下運行后的結果：
以上就是所有的js解析抽象語法樹的代碼。
完整代碼
<script>
var regexp = /([0-9\.]+)|([ \t]+)|([\r\n]+)|(\*)|(\/)|(\+)|(\-)/g
var dictionary = ["Number", "Whitespace", "LineTerminator", "*", "/", "+", "-"];
function* tokenize(source) {
var result = null;
var lastIndex = 0;
while(true) {
lastIndex = regexp.lastIndex;
result = regexp.exec(source);
if(!result) break;
if(regexp.lastIndex - lastIndex > result[0].length)
break;
let token = {
type: null,
value: null
}
for(var i = 1; i <= dictionary.length; i ++) {
if(result[i])
token.type = dictionary[i - 1];
}
token.value = result[0];
yield token }
yield {
type: 'EOF'
}
}
let source = [];
for(let token of tokenize("10 * 25 / 2")) {
if (token.type !== "Whitespace" && token.type !== "LineTerminator")
source.push(token);
}
function Expression(tokens) {
if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "EOF") {
let node = {
type: "Expression",
children: [source.shift(), source.shift()]
}
source.unshift(node);
return node;
}
AdditiveExpression(source);
return Expression(source);
}
function AdditiveExpression(source){
if(source[0].type === "MultiplicativeExpresson") {
let node = {
type: "AdditiveExpression",
children:[source[0]]
}
source[0] = node;
return AdditiveExpression(source)
}
//如果是乘號或者除號，則將三項出棧，進行重組
if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "+") {
let node = {
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);
return AdditiveExpression(source)
}
if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "-") {
let node = {
type: "AdditiveExpression",
operator: "-",
children: []
}
node.children.push(source.shift());
node.children.push(source.shift());
MultiplicativeExpresson(source);
node.children.push(source.shift());
source.unshift(node);
return AdditiveExpression(source)
}
//遞歸結束的條件
if(source[0].type === "AdditiveExpression")
return source[0];
//第一次進循環 調用
MultiplicativeExpresson(source);
return AdditiveExpression(source);
}
function MultiplicativeExpresson(source) {
if(source[0].type === "Number") {
let node = {
type: "MultiplicativeExpresson",
children:[source[0]]
}
source[0] = node;
return MultiplicativeExpresson(source)
}
//如果是乘號或者除號，則將三項出棧，進行重組
if(source[0].type === "MultiplicativeExpresson" && source[1] && source[1].type === "*") {
let node = {
type: "MultiplicativeExpresson",
operator: "*",
children: []
}
node.children.push(source.shift());
node.children.push(source.shift());
node.children.push(source.shift());
source.unshift(node);
return MultiplicativeExpresson(source)
}
if(source[0].type === "MultiplicativeExpresson" && source[1] && source[1].type === "/") {
let node = {
type: "MultiplicativeExpresson",
operator: "*",
children: []
}
node.children.push(source.shift());
node.children.push(source.shift());
node.children.push(source.shift());
source.unshift(node);
return MultiplicativeExpresson(source)
}
//遞歸結束的條件
if(source[0].type === "MultiplicativeExpresson")
return source[0];
return MultiplicativeExpresson(source);
}
console.log(Expression(source))</script>以上是“JS如何實現AST抽象語法樹”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
