Kostenlose Lernempfehlung: Javascript-Lern-Tutorial Atische Analyse
Vollständiger Code
Vier arithmetische Operationen
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
/ WhiteSpace:<sp></sp><lf code> <code><cr></cr>- Sehen Sie sich die Produktion an:
-
- Reguläre Ausdrücke
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>Nach dem Login kopieren
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>Nach dem Login kopieren
此时我们看一下页面的运行打印结果：
值得一提的是这里用到了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>Nach dem Login kopieren
如上，我们对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);
}Nach dem Login kopieren
我们先从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);
}Nach dem Login kopieren
Nach dem Login kopieren
我们看一下当source为"10 * 25 / 2"时调用console.log(MultiplicativeExpresson(source))最后运行的结果：
接下来看AdditiveExpression 本质上和MultiplicativeExpresson
Wenn exec() passenden Text findet, gibt es ein Array von Ergebnissen zurück. Andernfalls wird null zurückgegeben. Das 0. Element dieses Arrays ist der Text, der mit dem regulären Ausdruck übereinstimmt, das 1. Element ist der Text, der mit dem 1. Unterausdruck von RegExpObject (falls vorhanden) übereinstimmt, und das 2. Element ist der Text, der mit dem 1. Unterausdruck von RegExpObject übereinstimmt. Der Text stimmte überein durch 2 Unterausdrücke (falls vorhanden) und so weiter. Zusätzlich zu den Array-Elementen und Längeneigenschaften gibt die Methode exec() zwei Eigenschaften zurück. Das Indexattribut deklariert die Position des ersten Zeichens des übereinstimmenden Textes. Das Eingabeattribut speichert die abgerufene Zeichenfolge string. Wir können sehen, dass beim Aufruf der exec()-Methode des nicht-globalen RegExp-Objekts das zurückgegebene Array dasselbe ist wie das Array, das durch den Aufruf der String.match()-Methode zurückgegeben wird. 🎜🎜Wenn RegExpObject jedoch 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. Dies bedeutet, dass Sie den gesamten übereinstimmenden Text in einer Zeichenfolge durchlaufen können, indem Sie die Methode exec() wiederholt aufrufen. Wenn exec() keinen passenden Text mehr findet, gibt es null zurück und setzt die lastIndex-Eigenschaft auf 0 zurück. 🎜🎜🎜Lexikalische Analyse🎜🎜🎜Wir optimieren den obigen Code in diesem Teil. 🎜 Zunächst einmal das, was ich gerade erwähnt habe: 🎜
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);
}Nach dem Login kopieren
Nach dem Login kopieren
🎜Wie oben vergleichen wir
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>Nach dem Login kopieren
Nach dem Login kopieren
🎜Beginnen wir mit
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 kopieren
Nach 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 kopieren
Nach 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 kopieren
Nach 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!
