或者,更准确一点:哪些编程语言是由无上下文语法定义的?
从我收集的内容来看,由于宏和模板之类的东西,C ++不是无上下文的。我的直觉告诉我,函数式语言可能没有上下文,但我没有任何硬数据来支持。
额外的代表简洁的例子:-)
语法正确的程序集对于几乎所有语言都是无上下文的。
对于几乎所有语言,编译的程序集不是无上下文的。例如,如果所有编译C程序的集合都是无上下文的,那么通过与常规语言(也称为正则表达式)交叉,匹配所有编译C程序的集合
^int main\(void\) { int a+; a+ = a+; return 0; }$
将是无上下文的,但这显然与语言a + kba ^ kba ^ k同构,众所周知这不是无上下文的。
哪些编程语言没有上下文? [...]
我的直觉告诉我,功能语言可能没有上下文[...]
简短版本:几乎没有任何真实世界的编程语言在任何意义上都没有上下文。语言是否无上下文与其功能无关。这仅仅是语言规则和功能要解析的复杂程度。
这是命令式语言Brainfuck的CFG:
Program → Instr Program | ε
Instr → '+' | '-' | '>' | '<' | ',' | '.' | '[' Program ']'
这是功能性SKI combinator calculus的CFG:
Program → E
E → 'S' E E E
E → 'K' E E
E → 'I'
E → '(' E ')'
这些CFG识别这两种语言的所有有效程序,因为它们非常简单。
较长的版本:通常,无上下文语法(CFG)仅用于粗略指定语言的语法。必须区分语法正确的程序和编译的程序。最常见的是,编译器将语言分析分为语法分析,构建和验证一段代码的一般结构,以及验证程序含义的语义分析。
如果用“无语境语言”表示“......所有程序都编译”,那么答案就是:几乎没有。符合该法案的语言几乎没有任何规则或复杂的特征,如变量的存在,空格敏感性,类型系统或任何其他上下文:在一个地方定义并在另一个地方依赖的信息。
另一方面,如果“无上下文语言”仅表示“......所有程序都通过语法分析”,答案就是语法本身有多复杂。有许多语法特征很难或不可能仅用CFG来描述。通过向解析器添加其他状态来跟踪计数器,查找表等,可以克服其中一些问题。
使用CFG无法表达的语法功能示例:
typedef int my_int;
my_int x;
在分号处,需要使用my_int的条目更新类型环境。但是如果词法分析器已经向前看my_int,那么它将把它作为标识符而不是类型名称。E → E ^ E
E → E × E
E → E + E
E → (E)
E → num
然而,这个CFG是ambiguous,并且通常伴随着precedence / associativity table说,例如^绑定最紧密,×绑定比+更紧密,^是右关联,而×和+是左关联的。
优先级和关联性可以以机械方式编码到CFG中,使得它是明确的并且仅产生操作符正确行为的语法树。以上语法的一个例子:
E₀ → EA E₁
EA → E₁ + EA
EA → ε
E₁ → EM E₂
EM → E₂ × EM
EM → ε
E₂ → E₃ EP
EP → ^ E₃ EP
E₃ → num
E₃ → (E₀)
但模糊的CFG +优先/关联表是常见的,因为它们更具可读性,因为各种类型的LR parser生成器库可以通过eliminating shift/reduce conflicts生成更有效的解析器,而不是处理更大尺寸的明确的转换语法。理论上,所有有限的字符串集都是常规语言,因此所有有限大小的合法程序都是常规的。由于常规语言是无上下文语言的子集,因此所有有限大小的程序都是无上下文的。争论仍在继续,
虽然可以说一种语言只允许少于一百万行的程序是可接受的限制,但将编程语言描述为常规语言是不切实际的:描述太大了。 - Torben Morgensen的Basics of Compiler Design, ch. 2.10.2
CFG也是如此。为了解决您的子问题,有点不同,
哪种编程语言是由无上下文语法定义的?
大多数真实世界的编程语言都是由它们的实现定义的,并且大多数用于真实编程语言的解析器要么是手写的,要么是使用扩展无上下文解析的解析器生成器。遗憾的是,找到您喜欢的语言的确切CFG并不常见。当你这样做时,它通常是在Backus-Naur form(BNF),或者解析器规范,很可能不是纯粹的上下文。
来自野外的语法规范示例:
根据您对问题的理解,答案会发生变化。但IMNSHO,正确的答案是所有现代编程语言实际上都是上下文敏感的。例如,没有上下文无关语法只接受语法正确的C程序。那些指向C语言的yacc / bison上下文免费语法的人都忽略了这一点。
为了获得非上下文无关语法的最具戏剧性的例子,Perl的语法就像我理解的那样,是turing-complete。
如果我理解你的问题,你正在寻找可以通过上下文无关语法(cfg)描述的编程语言,以便cfg生成所有有效的程序并且只生成有效的程序。
我相信大多数(如果不是全部)现代编程语言因此不是上下文。例如,一旦您拥有用户定义的类型(在现代语言中非常常见),您就会自动对上下文敏感。
验证语法和验证程序的语义正确性之间存在差异。检查语法是无上下文的,而检查语义正确性则不是(同样,在大多数语言中)。
然而,这并不意味着这种语言不可能存在。例如,无类型的lambda calculus可以使用无上下文语法来描述,当然,图灵完整。
大多数现代编程语言都不是无上下文的语言。作为证明,如果我深入研究CFL的根,它的相应机器PDA不能像{ww | w is a string}
那样处理字符串匹配。所以大多数编程语言都需要这样
例:
int fa; // w
fa=1; // ww as parser treat it like this
VHDL有点上下文敏感:
VHDL以同样的方式对上下文敏感。在一个过程中考虑这个陈述:
jinx := foo(1);
那么,根据进程范围(及其封闭范围)中定义的对象,这可以是:
- 一个函数调用
- 索引数组
- 索引由无参数函数调用返回的数组
要正确解析这个问题,解析器必须携带一个分层符号表(带有封闭的范围),并且当前文件甚至不够。
foo
可以是包中定义的函数。因此,解析器应首先分析由其解析的文件导入的包,并找出其中定义的符号。这只是一个例子。 VHDL类型/子类型系统是一个类似的上下文敏感的混乱,很难解析。
(Eli Bendersky,“Parsing VHDL is [very] hard”,2009)