무료 학습 권장 사항: javascript 학습 튜토리얼
프런트 엔드의 AST 추상 구문 트리 문제
- 4개의 산술 연산
- 정규 표현식
- 어휘 분석
- 문법 분석
- 전체 코드
4가지 산술 연산
우선 이 코드는 LL 구문 분석을 기반으로 한다는 것이 분명합니다. 먼저 정의를 살펴보겠습니다.
TokenNumber:
· code> <code>1 2 3 4 5 6 7 8 9 0 조합 · 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;
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 연산자:
+ -
* /🎜 WhiteSpace:🎜
<sp></sp>🎜 LineTerminator:🎜
<cr></cr>🎜🎜프로덕션 살펴보기: 🎜
🎜🎜🎜정규식🎜🎜🎜먼저 정규식의 일치 원칙을 구현합니다.🎜 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);
}로그인 후 복사
로그인 후 복사
RegExpObject.exec(string)🎜🎜exec()가 일치하는 텍스트를 찾으면 결과 배열을 반환합니다. 그렇지 않으면 null을 반환합니다. 이 배열의 0번째 요소는 정규식과 일치하는 텍스트이고, 첫 번째 요소는 RegExpObject의 첫 번째 하위 표현식(있는 경우)과 일치하는 텍스트이며, 두 번째 요소는 RegExpObject의 첫 번째 하위 표현식과 일치하는 텍스트입니다. 2개의 하위 표현식(있는 경우) 등으로 계산됩니다. 배열 요소 및 길이 속성 외에도 exec() 메서드는 두 가지 속성을 반환합니다. index 속성은 일치하는 텍스트의 첫 번째 문자 위치를 선언합니다. 입력 속성은 검색된 문자열을 저장합니다. 비전역 RegExp 객체의 exec() 메서드를 호출할 때 반환된 배열이 String.match() 메서드를 호출하여 반환된 배열과 동일하다는 것을 알 수 있습니다. 🎜🎜그러나 RegExpObject가 전역 정규 표현식인 경우 exec()의 동작은 좀 더 복잡합니다. RegExpObject의 lastIndex 속성에 지정된 문자에서 문자열 검색을 시작합니다. exec()는 표현식과 일치하는 텍스트를 찾으면 RegExpObject의 lastIndex 속성을 일치 후 일치하는 텍스트의 마지막 문자 옆 위치로 설정합니다. 이는 exec() 메서드를 반복적으로 호출하여 문자열에서 일치하는 모든 텍스트를 반복할 수 있음을 의미합니다. exec()가 더 이상 일치하는 텍스트를 찾지 못하면 null을 반환하고 lastIndex 속성을 0으로 재설정합니다. 🎜🎜🎜어휘 분석🎜🎜🎜이 부분에서는 위 코드를 최적화합니다. 🎜 우선 방금 언급한 내용은 다음과 같습니다. 🎜RegExpObject가 전역 정규 표현식인 경우 exec()의 동작은 약간 더 복잡합니다. RegExpObject의 lastIndex 속성에 지정된 문자에서 문자열 검색을 시작합니다. exec()는 표현식과 일치하는 텍스트를 찾으면 RegExpObject의 lastIndex 속성을 일치 후 일치하는 텍스트의 마지막 문자 옆 위치로 설정합니다. 🎜 그런 다음 일치하는 문자가 없는 상황을 고려하여 판단해야 합니다. 🎜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와 result[0]를 비교합니다. ] 를 비교하여 일치하지 않는 문자열이 있는지 확인합니다. 🎜 전체 함수를 생성기 함수 형태로 변경하고 결과를 살펴보겠습니다. 🎜🎜🎜🎜구문 분석🎜🎜🎜먼저 블록 생성을 작성하고 전체 코드 구조를 살펴보겠습니다.🎜<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부터 시작해 보겠습니다. > 연구를 진행하면 4가지 상황으로 나누어집니다. 🎜rrreee🎜 소스가 "10 * 25 / 2"console.log(MultiplicativeExpresson(source))를 호출하는 것을 살펴보겠습니다. /code> >최종 실행 결과: 🎜🎜 다음으로 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>로그인 후 복사
로그인 후 복사
相关免费学习推荐：javascript（视频）
위 내용은 JS에서 AST 추상 구문 트리를 구현하는 문제에 대해 이야기해 보세요.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
