没有合适的资源?快使用搜索试试~ 我知道了~
首页RULER-FRONT: 统合访问者与属性文法的高效树遍历
RULER-FRONT是一种创新的编程范式,它结合了访问者设计模式和属性文法在树遍历算法中的优势,旨在解决传统遍历方法在并行计算和结果交换方面的挑战。访问者设计模式允许程序员灵活控制遍历顺序,这对于处理复杂的并发任务非常重要,但它在结果共享方面存在潜在错误。相比之下,属性文法(AG)通过属性求值器在多个遍历过程中装饰抽象语法树(AST),提供了一种方便的结果交换机制,但通常不鼓励副作用的使用。 RULER-FRONT的主要贡献在于提出了一种将标尺前文法(一种能够被翻译成不同语言的树结构表示形式)与访问者和属性文法结合起来的方法。具体来说,它将标尺前文法转化为命令式、动态类型的编程语言,如Java脚本,以便在实际应用中更加易用。这种转换使得AG的高效性和灵活性能够在更广泛的领域,包括Web应用程序处理文档对象模型(DOM)树的属性计算,得以体现。 尽管AG的简洁性和强大性使其在编译器开发中表现出色,但在扩展到非专业领域的应用程序时,需要克服学习成本高和语言限制等问题。RULER-FRONT的设计目标就是解决这些问题,通过提供一个更直观、更易于实现的编程接口,使得AG的优点能在更多应用场景中得到利用。 总结来说,RULER-FRONT是一种创新的解决方案,它通过整合访问者设计模式和属性文法的特性,创建了一种高效且易于使用的树遍历方法,适用于各种规模的项目,特别是那些需要处理并行计算和结果交换的场景。它的出现有望推动这些高级抽象技术在非专业编程领域的广泛应用。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/88626598/bg5.jpg)
A. Middelkoop
等人理论计算机科学电子笔记
264
(
5
)(
2011
)
47
51
最后,我们需要明确地使用
accept
来
写对孩子的访问。一些工具会产生
深度优先的访问者,这就证明了这样做的必要性,但这些都有限制。例如,
所有语句必须在调用子级之前编写。在图
1
中,我们重置了
它。深入
探访孩
子。要使用深度优先的访问者,我们必须移动这个语句(这可能不容易)。
此外,在我们展示的简单示例中,这两个访问在根节点上被依次调用。在实
践中,例如在具有主体类型的类型检查语言中,我们实际上在移动到下一个
子树之前调用子树上的多次访问这排除了深度优先访问者,并且手动编写也
容易出错。
图
1
中的示例可以很容易地变得更复杂,例如通过具有共享子菜单的菜单,
并形成非循环图而不是树。 随着每一个这样的并发症,上述问题变得更糟。作
为旁注,在本文中,我们将
AST
视为固定的数据结构。 例如,我们不考虑在桌
面上添加菜单项。我们提出的思想可以处理证明树的动态构造
[14]
,我们认为这
对于处理
AST
的动态变化也是足够的,但将这个主题留给未来的工作。
下面,我们寻找一种方法来生成类似于上面代码的代码,但是从描述中没
有上述问题。
2.2
属性文法
属性语法处理了上面提到的与访问者相关的问题,但不够灵活,无法考虑边
效应。我们简要地考虑为什么属性文法出现了一个有前途的解决方案,为什
么旁效应是一个问题。在我们展示这个例子之前,我们首先给出一些关于属
性语法的背景信息,以及它们在Java脚本中的编码。作为语法,我们采用
UUAG
的语法
[ 20 ]
和
ruler - front
(它们密切相关)的混合
属性文法是上下文无关文法的扩展,其中非终结符用属性注释,并且产生式
指定属性之间的等式。 上下文无关语法指定了
AST
的结构:
AST
的每个节点都
与一个产生式相关联。一个节点也与产生式左边的非终结符相关联,而一个节
点的每个子节点与产生式右边的相应非终结符相关联
例如,我们可以使用数据类型定义(下面解释)来表示
AST
中的生产以及
节点的结构。
数据
菜单
--非终结符
菜单
conCons hd:Menu tl:Menus -- productionCons,with two nonts
con
Nil
--
生产
Nil
,空
这个数据类型声明引入了一个非终结符Menus,它有两个结果,表示一个
cons-
list
。 第一个产品名为
Cons
,在
BNF
中对应于
Menus
→
Menu Menus
。右侧
(
RHS
)的两个非终结符Menu和Menus已明确指定为各自的名称hd和tl。
![](https://csdnimg.cn/release/download_crawler_static/88626598/bg6.jpg)
52
A. Middelkoop
等人理论计算机科学电子笔记
264
(
5
)(
2011
)
47
{
∗
{
−
∗
数据
根
孔
鲁特
root
:
Menu
--子节 点 名为
root
的节点
dataMenuconMenu
名称
cs
:
Menus
--具有属性
名
和子
cs
的节点
typeMenus:[Menu]--概念上是cons-list,物理上是数组
varroot
=
new Root
根(--
菜单
以物理方式表示
new Menu Menu
(
“
a
”
,
[--作为数组。 然而,从概念上讲,
new Menu Menu
(“b”
,
[--我们使用
new Menu Menu
(
“
c
”
,
[])--在cons-list表示之上。
,
new Menu Menu
(
“
d
”
,
[])]));
attrMenu Menusinhdepth finnMax
count --
gathMax
:宽度
syn
gathMax count
--
两个名为count
函数align
(
root
,
anchor
)--使用嵌入的属性语法
根
子句
根
--生产
方程
根
非根
:
深度
= 0--初始
深度
root
:
count
= 0--初始
计数
root
:
finnMax
=
root
:
gathMax
--选择聚集的最大值作为全局最大值
Crimeem
Menu
子句
Menu
--production
非项菜单
菜单
cs:depth
= 1 +
lhs:depth
--
增加子菜单的
深度
cs:count
= 1 +
lhs:count
--
增加
计数
lhs
:
count
=
cs
:
count
--将更新后的计数提供给父代
loc
:
elem
=
文档。
getElementById
(
loc
:
name
)
loc
:
o
设置
=
lhs
:
深度
20 -- indentation
loc
:
width
=
loc
:
o
缩进设置
+
loc
:
elem
。
clientWidth
lhs:gathMax
数学。
max
(
cs
:
gathMax
,
loc
:
width
)
cs
:
finnMax
=
lhs
:
finnMax
--向下传递最终最大值
loc
:
dummy
=(
function
()-- side-e不正确的语句
位置
:elem
。样式的
left
=(
anchor
.
o setLeft
+
loc
:
o setLeft
)+“px”;
位置
:elem
。样式的
top
=
(anchor
.
o setTop
+
lhs:count
30
)
+
“px”
;
位置
:elem
。样式的
width
=
(lhs:finMax loc:o xset)
+
“px”
;
位置
:
elem
。样式的
return“px”;
}
)()
--
直接调用匿名函数
生成式
Cons
和
Nil
的等式
条款
缺点
hd
:
深度
=
lhs
:
depth
--通过菜单向下传递
深度
tl
:
深度
=
lhs
:
深度
hd
:
计数
=
lhs
:
count
--以
tl
:
count
=
hd
:
count
--按顺 序
的方式,在菜单中遍历
计数
先是头部,然后是
lhs
:
计数
=
tl
:
count
--尾部 ,
然后返回到父级。
lhs
:
gathMax
=
数学。
max
(
hd
:
gathMax
,
tl
:
gathMax
)
hd
:
finMax
=
lhs
:
finMax
--向下
tl:finnMax
=
lhs:finnMax
无
条款
lhs
:
计数
=
lhs
:
count
--不改变线程计数
lhs
:
gathMax
= 0--初始最大值
varinhs
=
new Inh Root
();--包含根的inh属性
eval Root(sem Root
,
root
,
inhs)
;--
运行属性计算器
}
图
2
:基于属性语法的菜单对齐近似解决方案。
终端只有一个名称(如图
2
所示)。
此外,此数据类型声明引入了Java脚本构造函数来构造
AST
。每个产品被
映射到一个构造函数,该函数获取与产品的
RHS
中的符号对应的对象作为参
数。每个非终结符都映射到一个构造函数,该函数创建一个基对象,对应于
剩余25页未读,继续阅读
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 贵州煤矿矿井水分类与处理策略:悬浮物、酸性与非酸性
- 醛固酮增多症肾上腺静脉采样对比:ACTH后LR-CAV的最优评估
- 开源云连接传感器监控平台:农业土壤湿度远程监测
- 母婴用品企业年度生产计划线性规划优化模型:实证与应用
- 井下智能变电站:Rogowski线圈电流检测系统的研发与性能验证
- 霍州矿区煤巷稳定性分析及支护策略
- ARM嵌入式系统远程软件更新方案:基于TFTP协议
- 煤炭选煤中汞分布规律与洗选脱汞效果
- 提升码垛机器人性能:拉格朗日动力学模型与滑模模糊控制的应用
- 增强现实技术提升学前手写教学:设计与开发案例
- 不规则工作面沉陷三角剖分算法提升与应用
- 卡尔曼滤波在瞬变电磁干扰压制中的应用研究
- 煤矿安全能力研究:理论与系统构建
- LonWorks总线技术在斜巷运输车辆定位与跑车防护中的应用
- 神东煤炭集团高效煤粉锅炉系统:节能环保新实践
- Ti/SnO2+Sb2Ox/PbO2电极分形维数与电催化性能研究
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)