哪些编程语言没有上下文?

问题描述 投票:56回答:8

或者,更准确一点:哪些编程语言是由无上下文语法定义的?

从我收集的内容来看,由于宏和模板之类的东西,C ++不是无上下文的。我的直觉告诉我,函数式语言可能没有上下文,但我没有任何硬数据来支持。

额外的代表简洁的例子:-)

compiler-theory context-free-grammar
8个回答
34
投票

语法正确的程序集对于几乎所有语言都是无上下文的。

对于几乎所有语言,编译的程序集不是无上下文的。例如,如果所有编译C程序的集合都是无上下文的,那么通过与常规语言(也称为正则表达式)交叉,匹配所有编译C程序的集合

^int main\(void\) { int a+; a+ = a+; return 0; }$

将是无上下文的,但这显然与语言a + kba ^ kba ^ k同构,众所周知这不是无上下文的。


41
投票

哪些编程语言没有上下文? [...]

我的直觉告诉我,功能语言可能没有上下文[...]

简短版本:几乎没有任何真实世界的编程语言在任何意义上都没有上下文。语言是否无上下文与其功能无关。这仅仅是语言规则和功能要解析的复杂程度。

这是命令式语言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无法表达的语法功能示例:

  • 缩进和空格敏感的语言,如Python和Haskell。跟踪任意嵌套的缩进级别本质上是上下文敏感的,并且需要用于缩进级别的单独计数器;每个级别使用多少空格以及有多少级别。 仅使用固定数量的空格允许固定级别的缩进将通过复制每个缩进级别的语法来起作用,但实际上这是不方便的。
  • C Typedef Parsing Problem说C语言程序在词法分析中是模糊的,因为如果某些东西是现有类型的常规标识符或typedef别名,它就不能单独从语法中知道。 例子是: typedef int my_int; my_int x; 在分号处,需要使用my_int的条目更新类型环境。但是如果词法分析器已经向前看my_int,那么它将把它作为标识符而不是类型名称。
  • 基于宏和模板的语言,如Lisp,C ++,Template Haskell,Nim等。由于语法在解析时会发生变化,因此一种解决方案是将解析器变为自修改程序。另见“Is C++ context-free or context-sensitive?
  • 通常,即使可能,运算符优先级和关联性也不直接在CFG中表示。例如,一个小表达式语法的CFG,其中^绑定比×更紧,×绑定比+更紧,可能如下所示: 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),或者解析器规范,很可能不是纯粹的上下文。

来自野外的语法规范示例:


8
投票

根据您对问题的理解,答案会发生变化。但IMNSHO,正确的答案是所有现代编程语言实际上都是上下文敏感的。例如,没有上下文无关语法只接受语法正确的C程序。那些指向C语言的yacc / bison上下文免费语法的人都忽略了这一点。


3
投票

为了获得非上下文无关语法的最具戏剧性的例子,Perl的语法就像我理解的那样,是turing-complete


3
投票

如果我理解你的问题,你正在寻找可以通过上下文无关语法(cfg)描述的编程语言,以便cfg生成所有有效的程序并且只生成有效的程序。

我相信大多数(如果不是全部)现代编程语言因此不是上下文。例如,一旦您拥有用户定义的类型(在现代语言中非常常见),您就会自动对上下文敏感。

验证语法和验证程序的语义正确性之间存在差异。检查语法是无上下文的,而检查语义正确性则不是(同样,在大多数语言中)。

然而,这并不意味着这种语言不可能存在。例如,无类型的lambda calculus可以使用无上下文语法来描述,当然,图灵完整。


2
投票

大多数现代编程语言都不是无上下文的语言。作为证明,如果我深入研究CFL的根,它的相应机器PDA不能像{ww | w is a string}那样处理字符串匹配。所以大多数编程语言都需要这样

例:

int fa; // w
fa=1; // ww as parser treat it like this

2
投票

VHDL有点上下文敏感:

VHDL以同样的方式对上下文敏感。在一个过程中考虑这个陈述:

jinx := foo(1);

那么,根据进程范围(及其封闭范围)中定义的对象,这可以是:

  • 一个函数调用
  • 索引数组
  • 索引由无参数函数调用返回的数组

要正确解析这个问题,解析器必须携带一个分层符号表(带有封闭的范围),并且当前文件甚至不够。 foo可以是包中定义的函数。因此,解析器应首先分析由其解析的文件导入的包,并找出其中定义的符号。

这只是一个例子。 VHDL类型/子类型系统是一个类似的上下文敏感的混乱,很难解析。

(Eli Bendersky,“Parsing VHDL is [very] hard”,2009)


1
投票

我认为HaskellML支持上下文免费。请参阅此link for Haskell。

© www.soinside.com 2019 - 2024. All rights reserved.