- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
重点:
关键点:
上一篇「词法分析器」将字符串拆分为了一个一个的 token。 本篇我们将 token 变成语法树.
还是这个例子 int age = 45 我们给出这个语法的规则:
intDeclaration : Int Identifier ('=' additiveExpression)?;
如果翻译为程序的话,伪代码如下 。
// 伪代码
MatchIntDeclare(){
MatchToken(Int); // 匹配 Int 关键字
MatchIdentifier(); // 匹配标识符
MatchToken(equal); // 匹配等号
MatchExpression(); // 匹配表达式
}
输出的 AST 类似于:
Programm Calculator
IntDeclaration age
AssignmentExp =
IntLiteral 45
上面的过程,称为「递归下降算法」。 从顶部开始不断向下生成节点,其中还会有递归调用的部分.
上面的例子比较简单,还可以用正则表达式文法来表示。 但如果是个算数表达式呢?正则文法就很难表示了.
这时我们可以用递归的规则来表示 。
additiveExpression
: multiplicativeExpression
| additiveExpression Plus multiplicativeExpression
;
multiplicativeExpression
: IntLiteral
| multiplicativeExpression Star IntLiteral
;
生成的 AST 为:
如果要计算表达式的值,只需要对根节点求值就可以了。 这个就叫做「上下文无关文法」.
但你把上述规则翻译为代码逻辑时,会发现一个问题,无限递归。 我们先用个最简单的示例:
additiveExpression
: IntLiteral
| additiveExpression Plus IntLiteral
;
比如输入 2+3:
IntLiteral
,发现不是additiveExpression Plus IntLiteral
,此时还没有消耗任何的 tokenadditiveExpression
,此时要处理的表达式还是 2+3
这里要注意的一个问题: 并不是觉得 2+3 符合 additiveExpression Plus IntLiteral 就能直接按照 + 拆分为两部分,然后两部分分别去匹配。 这里是顺序匹配的,直到匹配到该语法规则的结束符为止。 在 additiveExpression Plus IntLiteral 中 additiveExpression 的部分,也是在处理完整的 token 的(2+3).
如何处理这个左递归问题呢? 我们可以把表达式换个位置:
additiveExpression
: IntLiteral
| IntLiteral Plus additiveExpression
;
先匹配 IntLiteral 这样就能消耗掉一个 token,就不会无限循环了。 比如还是 2+3 。
2+3
不是 IntLiteral
,跳到下面2+3
的第一个字符是 2
被 IntLiteral
消耗掉,并结束 IntLiteral
匹配+
被 Plus
消耗掉3
进入 additiveExpression
,匹配为第一条规则 IntLiteral
这样就结束了,没有无限循环。 改写成算法是:
private SimpleASTNode additive(TokenReader tokens) throws Exception {
SimpleASTNode child1 = IntLiteral(); // 计算第一个子节点
SimpleASTNode node = child1; // 如果没有第二个子节点,就返回这个
Token token = tokens.peek();
if (child1 != null && token != null) {
if (token.getType() == TokenType.Plus) {
token = tokens.read();
SimpleASTNode child2 = additive(); // 递归地解析第二个节点
if (child2 != null) {
node = new SimpleASTNode(ASTNodeType.AdditiveExp, token.getText());
node.addChild(child1);
node.addChild(child2);
} else {
throw new Exception("invalid additive expression, expecting the right part.");
}
}
}
return node;
}
但也有问题: 比如 2+3+4,你会发现它的计算顺序变为了 2+(3+4) 后面 3+4 作为一个 additiveExpression 先被计算,然后才会和前面的 2 相加。改变了计算顺序.
上面右递归解决了无限递归的问题,但是又有了结合优先级的问题。 那么我们再改写一下左递归:
additiveExpression
: IntLiteral additiveExpression'
;
additiveExpression'
: '+' IntLiteral additiveExpression'
| ε
;
文法中,ε(读作 epsilon)是空集的意思。 语法树 AST 就变成了下图左边的样子,虽然没有无限递归,但是按照前面思路,使用递归下降算法,结合性还是不对。 我们期望的应该是右边的 AST 树样子。那么怎么才能变成右边的样子呢?
这里我们插入一个知识点: 前面语法规则的表示方式成为:「巴科斯范式」,简称 BNF 我们把下面用正则表达式简化表达的方式,称为「扩展巴科斯范式 (EBNF)」 add -> mul (+ mul)* 。
那么我们把上面的表达式改写成 EBNF 形式,变为:
additiveExpression -> IntLiteral ('+' IntLiteral)*
这里写法的变化,就能让我们的算法逻辑产生巨大的变化.
重点: 前面左递归也好、右递归也好,变来变去都是递归调用,导致无限循环、结合性的问题。如果我们干掉递归,用循环来代替,就能按照我们期待的方式来执行了。 这里的区别是:前面递归计算过程是后序,把最后访问到的节点先计算,然后再一步步的返回;而循环迭代是前序,先计算再往后访问.
我们再写出计算逻辑:
private SimpleASTNode additive(TokenReader tokens) throws Exception {
SimpleASTNode child1 = IntLiteral(tokens); // 应用 add 规则
SimpleASTNode node = child1;
if (child1 != null) {
while (true) { // 循环应用 add'
Token token = tokens.peek();
if (token != null && (token.getType() == TokenType.Plus)) {
token = tokens.read(); // 读出加号
SimpleASTNode child2 = IntLiteral(tokens); // 计算下级节点
node = new SimpleASTNode(ASTNodeType.Additive, token.getText());
node.addChild(child1); // 注意,新节点在顶层,保证正确的结合性
node.addChild(child2);
child1 = node;
} else {
break;
}
}
}
return node;
}
消除了递归,只有循环迭代。你可以和上面递归的代码对比下.
再提一个概念:「尾递归」 尾递归就是函数的最后一句是递归的调用自身,可以理解为先序。而这种尾递归通常都可以转化为一个循环语句.
前面我们已经把一个语句转换为了一个 AST 树,接下来我们遍历这个语法树,就能实现计算求值了。 以 2+3+4 为例,简化后的语法树长这样:
遍历的伪代码如下:
evaluate(node) {
if node.type == TYPE.ADD:
left_res = evaluate(node.getChild(0))
right_res = evaluate(node.getChild(1))
return left_res + right_res
else if node.type == TYPE.INT:
return node.val
}
✌️至此,我们实现了一个计算器.
后面你可以在此基础上进行扩展,增加更多的运算符。以及扩充为一个脚本语言解释器,添加变量赋值、计算等等操作咯.
最后此篇关于【编译原理】手工打造语法分析器的文章就讲到这里了,如果你想了解更多关于【编译原理】手工打造语法分析器的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
在此处回答的另一个问题中,我发现了以下 JavaScript代码: function _dom_trackActiveElement(evt) { if (evt && evt.target)
if (A == 0) OR (B == 0) 怎么说? 最佳答案 只是为了讽刺: if (A === 0 || B === 0) 关于语法,我们在Stack Overflow上找到一个类似的问题:
var ret = [] ,xresult = document.evaluate(exp, rootEl, null, X
我一直在寻找一些类似于下例的 JavaScript。有人可以解释一下吗,因为我以前从未见过这样编写的 JavaScript。 “SomethingHere”和冒号代表什么?我习惯于看到函数 myFun
这是我的程序: delimiter // drop procedure if exists migContactToActor; create procedure migContactToActor(
我遇到了一个问题。我一直在使用 gcc 编译/汇编我的 C 代码一段时间,并且习惯了阅读 Intel 汇编语法。我在生成程序集文件时使用了 -masm=intel 标志。 但是最近因为公司迁移,拿到了
自上而下和自下而上语法有什么区别?举个例子就太好了。 最佳答案 首先,语法本身不是自上而下或自下而上的,解析器是(尽管有些语法可以被其中一个解析,但不能被另一个解析)。 从实践的角度来看,主要区别在于
我知道这是草率的代码,但它是: display dialog ("Start Screensaver. Please type: matrix, coffee, waffles, star, wate
这个问题已经有答案了: Giving name to a loop (6 个回答) 已关闭 8 年前。 我见过这个字符在 C# 中使用,就像 Java 中的扩展一样,但最近我在代码中发现了这个 loo
我正在尝试编写一个函数来检查字符串是否为回文,但我认为在使用字符串指针时存在一些错误。这段代码有什么问题? #include #include #define MAX 1000 int IsPalin
所以在this question我询问了一些 Javascript 是如何被压缩的。问题已得到解答,但以下片段让我非常困惑,以至于我不得不问另一个问题。在这里: for (Y = 0; $ = 'zx
假设我有一个接受这些参数的函数。 int create(Ptr * p,void * (*insert)(void *, void *)) { //return something later } 结
这个问题已经有答案了: Bitwise '&' operator (6 个回答) 已关闭 5 年前。 我在代码中找到了这个,但我从未遇到过像 & 这样的事情,仅 && if ((code & 1) =
我在处理继承类及其中的构造函数和方法的语法时遇到了问题。 我想实现一个类日期和一个子类 date_ISO,它们将按特定顺序设置给定的日、月、年,并通过一种方法将其写入字符串。我觉得我的基类日期工作正常
我正在尝试通过存储过程填充表,如下所示: SET @resultsCount = (SELECT COUNT(*) FROM tableA); SET @i = 0; WHILE @i THEN
谁能解释一下下面代码中的“<<”? mysql test<
刚刚开始学习 MySQL,这是一个菜鸟问题,也是我在 StackOverflow 上的第一个问题。 假设我有 12 个订单状态,我想从其中的 5 个中选择总计。我会使用: SELECT SUM(tot
我的编程背景是在学校学过一点Java。由于某些原因,JavaScript 语法往往让我感到困惑。下面的 JavaScript 代码是一种我不知道如何构成的语法模式: foo.ready = funct
我正在阅读 javascript 源代码,并且我以前没有编写过 javascript。我对它的一些语法感到困惑。 $(function () { window.onload=function
我什至不知道如何命名我想要的东西。那么让我举个例子来解释一下。 虽然火狐使用textContent,但其他浏览器支持innerText属性。顺便说一句,如果我使用了错误的术语,请纠正我。无论如何,到目
我是一名优秀的程序员,十分优秀!