Kostenlose Lernempfehlung: Javascript-Lern-Tutorial Atische Analyse
Vollständiger Code
Zunächst ist klar, dass dieser Code auf der LL-Syntaxanalyse basiert. Er implementiert die Funktion von vier gemischten arithmetischen Operationen:
TokenNumber: · code> <code>1
2
3
4
5
6
7
8
9
0
Kombination Operator:
+
- *
Einer von /
<sp></sp>
<lf code> <code><cr></cr>
Wir implementieren zunächst das Matching-Prinzip von regulären Ausdrücken:<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>
Das ist erwähnenswert Hier wird die Methode exec verwendet, die Methode exec() wird verwendet, um Übereinstimmungen eines regulären Ausdrucks in einer Zeichenfolge abzurufen.
Werfen wir einen Blick auf die Syntax: RegExpObject.exec(string)
·
1
2
3
4
5
6
7
8
9
0
的组合
Operator:+
-
*
/
之一
WhiteSpace:<sp></sp>
LineTerminator:<lf></lf>
<cr></cr>
看下产生式:
正则表达式
我们首先实现正则表达式的匹配原则:
<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>
此时我们看一下页面的运行打印结果:
值得一提的是这里用到了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' } } 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>
如上,我们对regexp.lastIndex - lastIndex
和 result[0]
的长度进行比较,判断是否有字符串没有匹配上。
将整个函数改成generator函数的形式,我们看下运行的结果:
语法分析
首先编写分块的产生式,我们看一下总的代码结构:
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); }
我们先从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(MultiplicativeExpresson(source))
最后运行的结果:
接下来看AdditiveExpression
本质上和MultiplicativeExpresson
Wenn RegExpObject ein globaler regulärer Ausdruck ist, ist das Verhalten von exec() etwas komplizierter. Es beginnt mit dem Abrufen der Zeichenfolge string bei dem Zeichen, das durch die lastIndex-Eigenschaft des RegExpObject angegeben wird. Wenn exec() Text findet, der mit einem Ausdruck übereinstimmt, setzt es die lastIndex-Eigenschaft des RegExpObject auf die Position neben dem letzten Zeichen des übereinstimmenden Texts nach der Übereinstimmung.
🎜 Dann müssen wir die Situation betrachten, in der es kein passendes Zeichen gibt, und ein Urteil fällen: 🎜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); }
regexp.lastIndex - lastIndex
und result[0 ]
wird verglichen, um festzustellen, ob eine Zeichenfolge nicht übereinstimmt. 🎜 Ändern Sie die gesamte Funktion in die Form einer Generatorfunktion und schauen wir uns die Ergebnisse an: 🎜🎜🎜🎜Syntaxanalyse🎜🎜🎜Schreiben Sie zunächst die Blockproduktionen, werfen wir einen Blick auf die gesamte Codestruktur:🎜<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>
MultiplicativeExpresson
Führen Sie eine Recherche durch, die in vier Situationen unterteilt ist: 🎜rrreee🎜 Werfen wir einen Blick auf den Aufruf von console.log(MultiplicativeExpresson(source))
, wenn die Quelle "10 * 25 / 2" >Das Ergebnis des letzten Laufs: 🎜🎜 Schauen Sie sich als nächstes AdditiveExpression
an. Es ist im Wesentlichen dasselbe wie MultiplicativeExpresson
. Die Unterschiede wurden im Code markiert: 🎜 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);
}
Nach dem Login kopierenNach dem Login kopieren
我们看一下当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);
}
Nach dem Login kopierenNach dem Login kopieren
看下运行后的结果:
以上就是所有的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>
Nach dem Login kopierenNach dem Login kopieren
相关免费学习推荐:javascript(视频)
Das obige ist der detaillierte Inhalt vonSprechen Sie über das Problem der Implementierung des abstrakten AST-Syntaxbaums in JS. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!