小编Ben*_*rel的帖子

每个本科生编程入门课程都会回顾常用的无上下文语法子集:LL(k),SLR(k),LALR(k),LR(k).我们还被教导,对于任何给定的k,这些语法中的每一个都是下一个语法的子集.

我从未见过的是解释什么样的编程语言语法特征可能需要转移到不同的语言类.GLR解析器有一个明显的实际动机,即在解析C++时避免解析器和符号表的不合理混合.但是,LL和LR这两个"标准"类之间的差异呢？

两个问题:

1. 什么(一般)句法结构可以用LR(k)而不是LL(k')来解析？
2. 在哪些方面,如果有的话,这些结构是否表现为理想的语言结构？

通过使k尽可能小来减少语言能力有一个似是而非的理由,因为需要许多许多前瞻标记的语言对于人类来说难以解析,以及机器要解析的"更难".问题(2)隐含地询问相同的推理是否最终在类之间以及在类中保持.

编辑:这是一个例子来说明我正在寻找的各种答案,但对于常规语言而不是无上下文:

当描述一个普通的语言,人们通常得到三大运营商:+,*和?.现在,你可以删除+而不降低语言的力量; 而不是写作x+,你写xx*,效果是一样的.但是,如果x是一些大而多毛的表达,那么x由于人类的遗忘,这两个人可能会随着时间的推移而发散,产生一个与原作者意图不符的语法正确的正则表达式.因此,即使添加+不严格增加功率,它确实使符号更不容易出错.

是否存在具有类似实际(人类？)效果的结构,从LR切换到LL时必须"删除"？

我一直在阅读Jones&Lins关于垃圾收集的书,该书于1996年出版.

显然,从那时起,计算世界发生了巨大的变化:具有大缓存的多核,无序芯片,以及桌面中更大的主存储器.对于大多数面向消费者的系统,全世界也或多或少地选择了x86和ARM微体系结构.

自这本开创性着作出版以来,最重要的进展是什么？

我特别关注论文,算法,学位论文等的指针,代表了垃圾收集理论和实践的进步.

在编译高阶函数调用时,是否有一种标准的方法来处理单独编译和不同类型的闭包转换之间的交互？

我知道在大多数编程语言中清晰编译的三个类似函数的结构:闭包,(顶级)函数和C++风格的函数对象.从语法上讲,它们的调用方式相同,但编译器可以最佳地生成形状清晰的调用站点:

Syntax:  | clo(args)                 |   func(args)     |   obj(args)
--------------------------------------------------------------------------------
Codegen: | clo.fnc(&clo.env, args)   |   func(args)     |   cls_call(&obj, args)
              ^      ^                      ^                   ^     ^
            fn ptr   |                      +--"top level" fn --+     |
                     +--- "extra" param, compared to source type -----+

(在C++中,cls_call将T::operator()用于obj类T.C++也允许虚拟仿函数,但这实际上是具有额外间接的闭包情形.)

此时,调用map (x => x > 3) lst并map (x => x > y) lst应调用不同的map函数,因为第一个是提升后的简单函数指针,第二个是闭包.

我可以想到处理这个问题的四种方法:

1. C++(98)方法,强制被调用者选择一个调用站点形状(通过形式参数类型:虚拟函子,函数指针或非虚函数)或使用模板删除单独的编译,有效地指定解决方案# 2下面.

2. 重载:编译器可以map使用适当的名称修改来执行多个实例化以及所有其他高阶函数.实际上,每个调用站点形状都有一个单独的内部函数类型,重载决策选择正确的.

3. 规定全球统一的呼叫站点形状.这意味着所有顶级函数都采用显式env参数,即使它们不需要它,并且必须引入"额外"闭包来包装非闭包参数.

4. 保留顶级函数的"自然"签名,但要求通过闭包完成所有高阶函数参数的处理.已关闭函数的"额外"闭包调用包装器trampoline函数来丢弃未使用的env参数.这似乎比选项3更优雅,但更难以有效实施.编译器生成大量的calling-convention-indepedent包装器,或者使用少量的call-convention-sensitive …