标签: context-free-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++是无上下文还是上下文敏感？

有人可以向我解释一下上下文无关语法是什么吗？在查看维基百科条目,然后查看关于正式语法的维基百科条目后,我完全被遗忘了.有人会这么好解释这些东西是什么吗？

我想知道这一点,因为我希望调查解析,以及一方面,正则表达式引擎的限制.

我不确定这些术语是否与编程直接相关,或者它们是否与语言学有关.如果是这样的话,我道歉,如果是这样的话可能会被移动？

我正在攻读我的计算语言测试,并且有一个想法我遇到了问题.

我知道常规语法更简单,不能包含歧义,但不能完成编程语言所需的大量任务.我也理解无上下文语法允许模糊,但允许编程语言(如回文)所需的一些东西.

我遇到的问题是通过了解常规语法非终结符可以映射到终端或非终结符后跟终端,或者无上下文非终结符映射到终端和非终结符的任意组合,从而理解我如何得到以上所有内容.

有人可以帮我把所有这些放在一起吗？

真正的现代正则表达式真正识别哪种语言？

每当存在具有反向引用的无限长度捕获组(例如(.*)_\1)时,正则表达式现在匹配非常规语言.但是,就其本身而言,这还不足以匹配诸如S ::= '(' S ')' | ?匹配对的parens的无上下文语言.

递归正则表达式(对我来说是新的,但我确信存在于Perl和PCRE中)似乎至少能识别出大多数CFL.

有没有人在这方面做过或读过任何研究？这些"现代"正则表达的限制是什么？对于LL或LR语法,他们是否严格认可或严格低于CFG？或者是否存在可以被正则表达式识别而不是CFG 而且相反的语言？

非常感谢与相关论文的链接.

我最近正在努力教自己解析器(语言/无上下文语法)是如何工作的,除了一件事以外,大部分解析器似乎都有意义.我特别关注LL(k)语法,其中两个主要算法似乎是LL解析器(使用堆栈/解析表)和递归下降解析器(简单地使用递归).

据我所知,递归下降算法适用于所有LL(k)语法,可能更多,而LL解析器适用于所有LL(k)语法.然而,递归下降解析器显然要比LL解析器简单得多(正如LL一个比LR一个简单).

所以我的问题是,使用任何一种算法时可能遇到的优点/问题是什么？为什么有人会选择LL而不是递归下降,因为它适用于同一组语法并且实现起来比较棘手？

在离开这个话题 20 多年（自从我获得 CS 本科学位以来）之后，我又回到了语言设计/规范（通过 BNF/EBNF 语法）。

我只是模糊地记得这个领域的各种相关术语，比如 LR(1)、LALR 等。我一直在尝试通过一些谷歌搜索和阅读来刷新，但它来得很慢（可能是因为我没有完全理解这些东西回到学校）。所以我可能做事相当粗略。

我决定用语法来描述一种玩具语言，然后尝试分析并可能优化它，作为我重新学习的一部分。

注意：下面的所有片段也可以在此处的要点中找到。

我从 EBNF 表示开始（由该工具处理/验证）：

Program                 := WhSp* (StmtSemi WhSp*)* StmtSemiOpt? WhSp*;
Stmt                    := AStmt | BStmt | CStmt | DStmt;
StmtSemi                := Stmt? (WhSp* ";")+;
StmtSemiOpt             := Stmt? (WhSp* ";")*;
WhSp                    := "_";
AStmt                   := "a";
BStmt                   := "b";
CStmt                   := "c";
DStmt                   := "d";

以下是该语言的一些有效匹配（每行一个匹配）：

_____
;;;;;
_;_;_
a
__a__
a;
a;b;
a;_b;
_a;_b;_
_a_;_b_;_
__a__;;
_;_a;_b;c;;;__;;__d;___a___

这里有一些该语言中没有的值（同样，每行一个）：

ab
a_b
a;_b_c

然后我将其手动转换为以下 BNF 形式（ …

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

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

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

我几个月前在D新闻组上发布了这个,但由于某种原因,答案从未真正说服过我,所以我想我会在这里问.

D的语法显然没有上下文.

但是,C++的语法不是(即使没有宏).(请仔细阅读!)

现在被授予,我对编译器,词法分析器和解析器一无所知(正式).我所知道的只是我在网上学到的东西.
以下是(我相信)我对上下文的理解,在非技术术语中:

语言的语法是无上下文的,当且仅当你能够总是理解给定代码片段的含义(尽管不一定是确切的行为)而不需要在任何其他地方"看".

或者,更严格:

如果我需要,语法不能无上下文我只是通过查看它就无法告诉表达式的类型.

因此,例如,C++失败上下文测试,因为意义的confusing<sizeof(x)>::q < 3 > (2) 依赖于值的q.

到现在为止还挺好.

现在我的问题是:可以对D说同样的话吗？

例如,在D中,可以通过Value[Key]声明创建哈希表

int[string] peoplesAges;   // Maps names to ages

静态数组可以用类似的语法定义:

int[3] ages;   // Array of 3 elements

模板可以用来使它们混淆:

template Test1(T...)
{
    alias int[T[0]] Test;
}

template Test2(U...)
{
    alias int[U] Test2;  // LGTM
}

Test1!(5) foo;
Test1!(int) bar;
Test2!(int) baz;  // Guess what? It's …

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

我所知道的是

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

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

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

我理解LR和LALR都是自下而上的解析算法,但两者之间有什么区别？

LR(0),LALR(1)和LR(1)解析之间有什么区别？如何判断语法是LR(0),LALR(1)还是LR(1)？