Free learning recommendation: javascript learning tutorial
AST abstract syntax tree problem in the front end
- Four arithmetic operations
- Regular expression
- Lexical analysis
- Syntax analysis
- Complete code
Four Arithmetic Operations
First of all, it is clear that the code this time is based on LL syntax analysis. It implements the function of the four arithmetic mixed operations. Let’s look at the definition first:
TokenNumber: · 1 2 3 4 5 6 7 8 9 0 combination
Operator: - * / One of
WhiteSpace:<sp></sp>
LineTerminator:
<lf></lf> <cr></cr>
Look at the production: 
##Regular Expression
We first implement the matching principle of regular expressions:<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>At this time we take a look at the running print results of the page: 
It is worth mentioning that The exec method is used here. The exec() method is used to retrieve regular expression matches in a string.
Let's take a look at its syntax:
RegExpObject.exec(string)
Lexical analysis
We optimize the above code in this part. First of all, what was just mentioned:
When RegExpObject is a global regular expression, the behavior of exec() is slightly more complicated. It starts retrieving the string string at the character specified by the RegExpObject's lastIndex property. When exec() finds text that matches an expression, it sets the RegExpObject's lastIndex property to the position next to the last character of the matching text after the match. Then we have to consider the situation where there is no matching character and make a judgment:
<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> As above, we have regexp.lastIndex - lastIndex and The length of result[0] is compared to determine whether any string does not match. Change the entire function into the form of a generator function. Let’s look at the results of the operation: 
Syntax analysis
First write the chunks Production, let's take a look at the overall code structure:<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> Let's study it first from MultiplicativeExpresson, which is divided into four situations:
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);
} Let's take a look When the source is "10 * 25 / 2", call console.log(MultiplicativeExpresson(source))The final running result: 
Let’s see next
AdditiveExpression is essentially the same as MultiplicativeExpresson. The differences have been marked in the code:
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>
相关免费学习推荐：javascript（视频）
The above is the detailed content of Talk about the problem of implementing AST abstract syntax tree in JS. For more information, please follow other related articles on the PHP Chinese website!
es6数组怎么去掉重复并且重新排序May 05, 2022 pm 07:08 PM去掉重复并排序的方法：1、使用“Array.from(new Set(arr))”或者“[…new Set(arr)]”语句，去掉数组中的重复元素，返回去重后的新数组；2、利用sort()对去重数组进行排序，语法“去重数组.sort()”。
JavaScript的Symbol类型、隐藏属性及全局注册表详解Jun 02, 2022 am 11:50 AM本篇文章给大家带来了关于JavaScript的相关知识，其中主要介绍了关于Symbol类型、隐藏属性及全局注册表的相关问题，包括了Symbol类型的描述、Symbol不会隐式转字符串等问题，下面一起来看一下，希望对大家有帮助。
原来利用纯CSS也能实现文字轮播与图片轮播！Jun 10, 2022 pm 01:00 PM怎么制作文字轮播与图片轮播？大家第一想到的是不是利用js，其实利用纯CSS也能实现文字轮播与图片轮播，下面来看看实现方法，希望对大家有所帮助！
JavaScript对象的构造函数和new操作符（实例详解）May 10, 2022 pm 06:16 PM本篇文章给大家带来了关于JavaScript的相关知识，其中主要介绍了关于对象的构造函数和new操作符，构造函数是所有对象的成员方法中，最早被调用的那个，下面一起来看一下吧，希望对大家有帮助。
JavaScript面向对象详细解析之属性描述符May 27, 2022 pm 05:29 PM本篇文章给大家带来了关于JavaScript的相关知识，其中主要介绍了关于面向对象的相关问题，包括了属性描述符、数据描述符、存取描述符等等内容，下面一起来看一下，希望对大家有帮助。
javascript怎么移除元素点击事件Apr 11, 2022 pm 04:51 PM方法：1、利用“点击元素对象.unbind("click");”方法，该方法可以移除被选元素的事件处理程序；2、利用“点击元素对象.off("click");”方法，该方法可以移除通过on()方法添加的事件处理程序。
整理总结JavaScript常见的BOM操作Jun 01, 2022 am 11:43 AM本篇文章给大家带来了关于JavaScript的相关知识，其中主要介绍了关于BOM操作的相关问题，包括了window对象的常见事件、JavaScript执行机制等等相关内容，下面一起来看一下，希望对大家有帮助。
20+道必知必会的Vue面试题（附答案解析）Apr 06, 2021 am 09:41 AM本篇文章整理了20+Vue面试题分享给大家，同时附上答案解析。有一定的参考价值，有需要的朋友可以参考一下，希望对大家有所帮助。
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
AI Hentai Generator
Generate AI Hentai for free.
Hot Article
Hot Tools
SublimeText3 Linux new version
SublimeText3 Linux latest version
SublimeText3 Chinese version
Chinese version, very easy to use
EditPlus Chinese cracked version
Small size, syntax highlighting, does not support code prompt function
WebStorm Mac version
Useful JavaScript development tools
Notepad++7.3.1
Easy-to-use and free code editor
