标签: context-sensitive-grammar

我经常听到C++是一种上下文敏感语言的说法.请看以下示例:

a b(c);

这是变量定义还是函数声明？这取决于符号的含义c.如果c是变量,则a b(c);定义名为btype 的变量a.它是直接初始化的c.但是如果c是一个类型,则a b(c);声明一个名为a的函数b,c并返回一个a.

如果您查找无上下文语言的定义,它基本上会告诉您所有语法规则必须具有仅由一个非终端符号组成的左侧.另一方面,上下文敏感语法允许左侧的任意字符串的终端和非终端符号.

浏览"C++编程语言"的附录A,除了左侧的单个非终端符号之外,我找不到单个语法规则.这意味着C++是无上下文的.(当然,在无上下文语言形成上下文敏感语言的子集的意义上,每种无上下文语言也都是上下文敏感的,但这不是重点.)

那么,C++是无上下文还是上下文敏感？

有人可以向我解释为什么这种语法[无上下文语法和上下文敏感语法]接受一个字符串？

我所知道的是

无上下文语法是一种形式语法,其中每个生成(重写)规则是V→w的形式,其中V是单个非终结符号,w是一串终端和/或非终端.w可以是空的

上下文敏感语法是一种形式语法,其中任何生成(重写)规则的左侧和右侧可以被终端和非终结符号的上下文包围.

但是,我怎么能解释为什么这些语法接受一个字符串？

我试图找到一个简单的(即非正式的)解释,正如乔姆斯基所阐述的4级正式语法(无限制,上下文敏感,无上下文,常规).

自从我学习正式语法以来,这已经是一个时代了,各种各样的定义现在让我难以想象.要明确的是,我不是在寻找你​​到处都可以找到的正式定义(例如这里和这里 - 我可以谷歌以及其他任何人),或者甚至是任何形式的正式定义.相反,我希望找到的是干净简单的解释,为了完整性而不牺牲清晰度.

相关问题/材料:

• 我们如何匹配^ nb ^ n与Java正则表达式？

• 如何确定一个数字是否是正则表达式的素数？(它涉及一元素数匹配,而我正在寻找≥2的基数;不过是一个很好的伎俩,是什么让我思考这个)

• http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html

众所周知,由各种编程语言支持的"正则表达式"生成在形式意义上非常规的语言,并且如上述材料所示,能够识别至少一些上下文敏感语言.

语言L = {x | x是基数10中的素数.}是一种上下文敏感语言,因为素数可以通过线性有界自动机来测试(但它不是通过泵浦引理参数的无上下文语言).

那么,是否可以编写一个Perl或Java正则表达式,它恰好接受基数为10的所有素数？如果感觉更容易,可以随意替换≥2的任何其他基础或精确识别所有复合数字.

例如,使用转义来运行任意Perl代码被视为作弊.重复替换(很容易图灵完成)也超出了范围; 整个工作应该在正则表达式内完成.这个问题更多的是关于正则表达式实际有多强大的界限.

我正在读Terence Parr的最终ANTLR参考文献,他说:

语义谓词是一种通过允许运行时信息驱动识别来识别上下文敏感语言结构的强大方法

但书中的例子非常简单.我需要知道的是:ANTLR可以解析上下文相关的规则,例如:

xAy - > xBy

如果ANTLR无法解析这些规则,是否还有另一种工具可以处理上下文敏感的语法？

我正在尝试理解上下文敏感的语法,我理解为什么语言会像

1. {ww | w是一个字符串}
2. {a ⁿ b ⁿ c ⁿ | a,b,c是符号}

不是上下文,但我想知道一个类似于无类型lambda演算的语言是否与上下文相关.我想看一个简单但非玩具的例子(我考虑上面的玩具示例),一个上下文敏感语法的例子,对某些生产规则,例如,告诉一些符号串是否可以目前处于范围内(例如,在生成函数体时).上下文敏感语法是否足够强大,可以使未定义/未声明/未绑定的变量成为语法(而不是语义)错误？

根据此答案 => Scala中是具有两种不同的含义关键字:1来表示一个功能类型:Double => Double和2以创建lambda表达式:(x: Double): Double => 2*x.

这与正式语法有什么关系,即这会使Scala上下文敏感吗？

我知道大多数语言都没有上下文,但我不确定我所描述的情况是否与此有关.

编辑:

好像我不太了解上下文敏感的语法.我知道生产规则应该是什么样子,以及它们的含义("只有当A被这些符号包围时才适用这种生产"),但我不确定它们与实际(编程)语言的关系.

我认为我的困惑源于阅读"乔姆斯基引入这个术语,因为一个词的含义可能取决于它的语境",并且我=>在引用中与术语"单词"相关联,并且它的两个用法是两个独立的上下文.

如果一个答案可以解决我的困惑,那就太好了.

CSG类似于CFG,但减少符号是多个.

那么,我可以使用CFG解析器解析CSG,减少生产到多个终端或非终端吗？

喜欢

1. S ? a bc
2. S ? a S B c
3. c B ? W B
4. W B ? W X
5. W X ? B X
6. B X ? B c
7. b B ? b b

当我们见面时W X,我们可以减少W X到W B吗？

当我们见面时W B,我们可以减少W B到c B吗？

因此,如果CSG解析器基于CFG解析器,那么写起来并不难,是真的吗？

但是当我检查维基时,它说解析CSG,我们应该使用linear bounded automaton.

什么是linear bounded automaton？

在乔姆斯基的层次结构中，未定义递归语言集。我知道递归语言是递归可枚举语言的子集，并且所有递归语言都是可确定的。

我很好奇的是递归语言与上下文相关语言的比较。我是否可以假定上下文敏感的语言是递归语言的严格子集，因此所有上下文敏感的语言都是可决定的？

我最近一直在为基于 C 的语言编写解析器。我正在使用 CUP（Java 的 Yacc）。

我想实施“词法分析器黑客”（http://eli.thegreenplace.net/2011/05/02/the-context-sensitive-of-c%E2%80%99s-grammar-revisited/ 或 https:/ /en.wikipedia.org/wiki/The_lexer_hack），以区分 typedef 名称和变量/函数名称等。要启用与之前声明的类型相同名称的变量（来自第一个链接的示例）：

typedef int AA;

void foo() {
    AA aa;       /* OK - define variable aa of type AA */
    float AA;    /* OK - define variable AA of type float */
}

我们必须引入一些新的产生式，其中变量/函数名称可以是IDENTIFIER或TYPENAME。这就是困难发生的时刻——语法冲突。

我试图不将这种凌乱的 Yacc 语法用于 gcc 3.4 ( http://yaxx.googlecode.com/svn-history/r2/trunk/gcc-3.4.0/gcc/c-parse.y )，但这次我不知道如何自己解决冲突。我看了一下 Yacc 语法：

declarator:
    after_type_declarator
    | notype_declarator
    ;

after_type_declarator:
    ...
    | TYPENAME
    ;

notype_declarator:
    ...
    | IDENTIFIER
    ;

fndef:
    declspecs_ts setspecs declarator
    // …