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

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

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

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

1> Simon Shine..：

---

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

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

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

这是针对命令式语言Brainfuck的CFG :

Program ? Instr Program | ?
Instr ? '+' | '-' | '>' | '<' | ',' | '.' | '[' Program ']'

这是功能性 SKI组合子演算的CFG :

Program ? E
E ? 'S' E E E
E ? 'K' E E
E ? 'I'
E ? '(' E ')'

这些CFG识别这两种语言的所有有效程序,因为它们非常简单.

---

较长的版本:通常,无上下文语法(CFG)仅用于粗略指定语言的语法.必须区分语法正确的程序和编译的程序.最常见的是,编译器将语言分析分为语法分析,构建和验证一段代码的一般结构,以及验证程序含义的语义分析.

如果用"无语境语言"表示" ......所有程序都编译 ",那么答案就是:几乎没有.符合该法案的语言几乎没有任何规则或复杂的特征,如变量的存在,空格敏感性,类型系统或任何其他上下文:在一个地方定义并在另一个地方依赖的信息.

另一方面,如果"无上下文语言"仅表示" ......所有程序都通过语法分析 ",答案就是语法本身有多复杂.有许多语法特征很难或不可能仅用CFG来描述.通过向解析器添加其他状态来跟踪计数器,查找表等,可以克服其中一些问题.

使用CFG无法表达的语法功能示例:

缩进和空格敏感的语言,如Python和Haskell.跟踪任意嵌套的缩进级别本质上是上下文敏感的,并且需要用于缩进级别的单独计数器; 每个级别使用多少空格以及有多少级别.

仅使用固定数量的空格允许固定级别的缩进将通过复制每个缩进级别的语法来起作用,但实际上这是不方便的.

该Ç解析的typedef问题说,C程序词法分析过程中不明确的,因为它不能单从语法知道,如果事情是常规标识符或现有类型的类型定义别名.

例子是:

  typedef int my_int;
  my_int x;

在分号处,需要使用my_int的条目更新类型环境.但是如果词法分析器已经向前看my_int,那么它将把它作为标识符而不是类型名称.

基于宏和模板的语言,如Lisp,C++,Template Haskell,Nim等.由于语法在解析时会发生变化,因此一种解决方案是将解析器变为自修改程序.另请参阅" C++是无上下文还是上下文相关？ "

通常,运算符优先级和关联性不直接在CFG中表示,即使它是可能的.例如,一个小表达式语法的CFG,其中^绑定比×紧,×绑定比+更紧,可能如下所示:

E ? E ^ E
E ? E × E
E ? E + E
E ? (E)
E ? num

然而,这个CFG是模糊的,并且通常伴随着优先级/关联表,例如^绑定最紧密,×绑定比+更紧密,^是右关联的,并且×和+是左关联的.

优先级和关联性可以以机械方式编码到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解析器生成器库可以通过消除移位/减少冲突而不是处理更大尺寸的明确的转换语法来产生更有效的解析器.

理论上,所有有限的字符串集都是常规语言,因此所有有限大小的合法程序都是常规的.由于常规语言是无上下文语言的子集,因此所有有限大小的程序都是无上下文的.争论仍在继续,

虽然可以说一种语言只允许少于一百万行的程序是可接受的限制,但将编程语言描述为常规语言是不切实际的:描述太大了.
     - Torben Morgensen的编译器设计基础知识,ch.2.10.2

CFG也是如此.为了解决您的子问题,有点不同,

哪种编程语言是由无上下文语法定义的？

大多数真实世界的编程语言都是由它们的实现定义的,并且大多数用于真实编程语言的解析器要么是手写的,要么是使用扩展无上下文解析的解析器生成器.遗憾的是,找到您喜欢的语言的确切CFG并不常见.当你这样做时,它通常是Backus-Naur形式(BNF),或者解析器规范,很可能不是纯粹的上下文.

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

标准ML的BNF

像Haskell一样的BNF

BNF for SQL

PHP的Yacc语法

2> Dave..：

---

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

对于几乎所有语言,编译的程序集不是无上下文的.例如,如果该组的所有编译C程序是免费的上下文中,然后通过用常规的语言(也称为正则表达式),该组相匹配的所有编译的C程序的相交

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

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

---

语法有效程序和语义有效程序之间的区别是误导性的,因为后者在语境敏感语法中表达语法(对于编程语言感兴趣的案例).说程序在语法上是有效的,因为CFG可以接受它,这是错误的,因为有效程序的语言需要限制仅由CFG接受的字符串的条件,这意味着它们不能由CFG描述.无论如何+1

---

+1的答案是真的.接受的答案是误导性的.

---

如果有人希望看到证明该语言{a ^ kba ^ kba ^ kb | k> = 0}是非常规的，请参见Torben Mogensen的《编译器设计基础》第2.10.2章：http://www.diku.dk/~torbenm/Basics

3> starflyer..：

---

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