首页 文章

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

提问于
浏览 次
53

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

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

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

compiler-theory context-free-grammar

8 回答

  • 1

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

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

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

    将是无上下文的，但这显然与语言同构，而众所周知，语言不是无上下文的 .

    回复于
  • 2

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

    回复于
  • 36

    VHDL有点上下文敏感 .

    （谷歌：解析-vhdl-非常难）

    回复于
  • 28

    哪些编程语言不受上下文限制？ [...]我的直觉告诉我，函数式语言可能没有上下文[...]

    The short version: 几乎没有任何真正的编程语言在任何意义上都没有上下文 . 语言是否无上下文与其功能无关 . 这仅仅是语言规则和功能要解析的复杂程度 .

    这是命令式语言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识别这两种语言的所有有效程序，因为它们非常简单 .

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

    如果"context-free language"你的意思是“ ... for which all programs compile ”，那么答案就是：几乎没有 . 符合该法案的语言几乎没有任何规则或复杂的特征，如变量的存在，空格敏感性，类型系统或任何其他上下文：在一个地方定义并在另一个地方依赖的信息 .

    另一方面，如果"context-free language"仅表示“ ... for which all programs pass syntax analysis ”，答案就是语法本身有多复杂 . 有很多语法特征很难或不可能单独用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，其中^绑定比x更紧，×绑定比它更紧密，可能如下所示：

    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的编译器设计基础知识，ch . 2.10.2

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

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

    大多数真实编程语言都是由它们的实现定义的，并且大多数用于真实编程语言的解析器要么是手写的，要么是使用扩展无上下文解析的解析器生成器 . 遗憾的是，为您喜欢的语言找到一个精确的CFG并不常见 . 当你这样做时，它通常在Backus-Naur form（BNF）中，或者解析器规范很可能不是纯粹的上下文 .

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

    回复于
  • 7

    我认为Haskell和ML支持上下文免费 . 对于Haskell，请参阅link .

    回复于
  • 1

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

    例：

    int fa; // w
fa=1; // ww as parser treat it like this
    回复于
  • 2

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

    回复于
  • 1

    如果我理解你的问题，你正在寻找可以通过上下文无关语法（cfg）描述的编程语言，以便cfg生成所有有效的程序和只有有效的程序 .

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

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

    然而，这并不意味着这种语言不可能存在 . 例如，Untyped lambda calculus可以使用无上下文语法来描述，当然，图灵完成 .

    回复于

相关问题