问题标签 [context-sensitive-grammar]

C 语言中的非上下文无关语言的例子有哪些？C语言中如何存在以下非CFL？

a) L1 = {wcw|w 是 {a,b}*}

b) L2 = {a^nb^mc^nd^m| n,m >=1}

我正在学习“编译器理论”，它说大多数语言都使用“确定性上下文无关语法”。我想知道是否有任何语言使用“上下文相关语法”？

更新：

我问了一个人，他说c++和ruby有一些上下文相关的语法。

例如，在 c++ 中，此代码：

如果有一个名为 的方法abc，则abc()表示“调用此方法”。如果有 class class abc{ }，则表示“创建 abc 类的实例”。

而在 ruby​​ 中，由于它具有元编程，因此它具有更多上下文敏感的语法。

他是对的吗？

我正在尝试理解上下文相关的语法，并且我理解为什么语言喜欢

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

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

我经常听到有人声称 C++ 是一种上下文相关的语言。举个例子：

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

如果您查看上下文无关语言的定义，它基本上会告诉您所有语法规则都必须具有仅由一个非终结符组成的左侧。另一方面，上下文相关文法允许在左侧出现任意的终结符和非终结符字符串。

浏览“C++ 编程语言”的附录 A，我找不到一个语法规则，它的左侧除了一个非终结符之外还有其他任何东西。这意味着 C++ 是上下文无关的。（当然，从上下文无关语言形成上下文相关语言的子集的意义上说，每种上下文无关语言也是上下文相关的，但这不是重点。）

那么，C++ 是上下文无关的还是上下文敏感的？

是否可以在情感分析中使用上下文相关的语法？如果是，那么如何？基本上，我想做一些短语级别的分析。

我刚参加了期中考试，但无法回答这个问题。

有人可以举几个该语言的例子并为该语言构建一个语法，或者 至少告诉我我将如何去做？

还有如何写语法L：

L = {a ⁿ b ^m | n,m = 0,1,2,..., n <= 2m } ?

提前致谢。

我正在学习形式语言和自动机理论，我有一个关于书中没有回答的问题的问题。问题是：

这种语言是上下文无关的、常规的还是上下文相关的？

L= {a ⁿ w w ^R b ⁿ | w 是 ( a+b )*, w ^R是 w 的倒数并且 n>=0 }

我认为这种语言是上下文相关的，因为它至少需要两个堆栈才能接受。

有人可以对此发表评论吗？

谢谢。

我在 comp.theory 列表中读到了这篇精彩的文章：

http://coding.derkeiler.com/Archive/General/comp.theory/2004-03/0189.html

海报指出，大多数编程语言都定义了一个上下文无关的核心，然后在解析树上运行额外的算法来过滤掉语言中非法的结构：

这将语言的上下文无关部分与上下文相关部分分开——这通常被认为是良好的实践（一种用于语言设计的模块化“编程”学科）。

您能否提供一个“Hello World”示例来说明这种技术？也就是说，提供一种简单的上下文敏感语言，识别上下文无关核心，然后勾勒出如何使用上下文无关核心解析输入，然后过滤掉解析树中的非法结构。

你能给我推荐任何讨论这种技术的文章或书籍吗？

我正在尝试使用 bison 和 flex 为自定义的类似 pascal 的语言制作编译器，但我最终得到了根据我的自定义语法应该正确的程序的语法错误。

我的自定义语法：

我在野牛上的语法实现：

我的 flex 实现非常简单，我只为所需的每个符号或标识符返回标记。

在以下简单程序上使用我的实现：

我最终得到一个语法错误。:=根据我使用的调试打印，特别是当解析到达点后：

这是我第一次使用 flex 和 bison，所以我猜我对 bison 的原始语法执行错误，因为在./bison.exe -dy comp.y我得到命令之后：

野牛冲突 64 移位/减少

任何想法都会有所帮助。谢谢！

我最近一直在为基于 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 名称和变量/函数名称等。要启用与之前声明的类型同名的声明变量（来自第一个链接的示例）：

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

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

declspecs_ts表示声明说明符，其中“是否已看到类型说明符；在类型说明符之后，typedef 名称是要重新声明的标识符（_ts 或 _nots）。”

从 declspecs_ts 我们可以到达

乍一看，我不敢相信 shift/reduce 冲突没有出现！ setspecs是空的，所以我们declspecs_ts后面跟着declarator，所以我们可以预期解析器应该混淆TYPENAME是 fromdeclspecs_ts还是 from declarator。

任何人都可以简要（甚至准确地）解释这一点。提前致谢！

编辑：有用的链接：http ://www.gnu.org/software/bison/manual/bison.html#Semantic-Tokens