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

也许我不是来自这个星球,但在我看来,以下应该是语法错误:

int a[] = {1,2,}; //extra comma in the end

但事实并非如此.我很惊讶,当编译这段代码在Visual Studio中,但我已经学会了不至于C++规则而言信任MSVC的编译器,所以我检查的标准,它是标准允许为好.如果你不相信我,你可以看到8.5.1的语法规则.

为什么允许这样做？这可能是一个愚蠢无用的问题,但我希望你理解我为什么这么问.如果它是一般语法规则的子案例,我会理解 - 他们决定不再使一般语法更难以在初始化列表的末尾禁止冗余逗号.但不,明确允许附加逗号.例如,在函数调用参数列表的末尾(当函数采用时...)不允许使用冗余逗号,这是正常的.

那么,是否有任何特殊原因明确允许这个冗余逗号？

我正在阅读解析器和解析器生成器,并在维基百科的LR解析页面中找到了这个语句:

可以使用LR解析器的一些变体来解析许多编程语言.一个值得注意的例外是C++.

为什么会这样？C++的哪个特定属性导致无法使用LR解析器进行解析？

使用谷歌,我只发现C可以用LR(1)完美解析,但C++需要LR(∞).

LR,SLR和LALR解析器之间的实际区别是什么？我知道SLR和LALR是LR解析器的类型,但就解析表而言,它们的实际区别是什么？

以及如何显示语法是LR,SLR还是LALR？对于LL语法,我们只需要显示解析表的任何单元格都不应包含多个生产规则.LALR,SLR和LR的任何类似规则？

例如,我们如何才能显示语法

S --> Aa | bAc | dc | bda
A --> d

是LALR(1)但不是SLR(1)？

编辑(ybungalobill):我没有得到一个满意的答案,LALR和LR之间有什么区别.因此LALR的表格较小,但它只能识别LR语法的一个子集.有人可以详细说明LALR和LR之间的区别吗？LALR(1)和LR(1)足以应答.它们都使用1个令牌前瞻,两个都是表驱动的!它们有何不同？

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

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

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

我熟悉C和C++的语法是上下文相关的事实,特别是你需要在C中使用"lexer hack".另一方面,我的印象是你只能解析Java尽管两种语言之间存在相当大的相似性,但仍有2个前瞻性令牌.

你需要改变什么才能使它更易于解析？

我问,因为我所见过的关于C的上下文敏感性的所有例子在技术上都是允许的,但非常奇怪.例如,

foo (a);

可以foo用参数调用void函数a.或者,它可以声明a是一个类型的对象foo,但你可以很容易地摆脱parantheses.在某种程度上,这种奇怪之处的发生是因为C语法的"直接声明者"生成规则实现了声明函数和变量的双重目的.

另一方面,Java语法具有用于变量声明和函数声明的单独生成规则.如果你写

foo a;

然后你知道它是一个变量声明,foo可以毫不含糊地解析为一个类型名.如果foo尚未在当前作用域中的某处定义类,则这可能不是有效代码,但这是可以在稍后的编译器传递中执行的语义分析的工作.

我已经看到它说由于typedef很难解析C,但你也可以在Java中声明自己的类型.此外direct_declarator,哪种C语法规则有错？

如果我输入019 > 020JavaScript控制台(在Chrome和Firefox中测试),我会得到答案true.

这是因为020被解释为OctalIntegerLiteral(等于16),而019显然被解释为DecimalLiteral(和等于19).由于19是大于16,019 > 020是true.

令我困惑的是为什么019被解释为DecimalLiteral第一名.它是哪种产品？DecimalIntegerLiteral不允许019:

DecimalIntegerLiteral ::
    0
    NonZeroDigit DecimalDigits_opt

OctalIntegerLiteral也不允许019(因为9不是八进制数字):

OctalIntegerLiteral ::
    0 OctalDigit
    OctalIntegerLiteral OctalDigit

OctalDigit :: one of
    0 1 2 3 4 5 6 7

因此,从我在规范中看到的,019实际应该被拒绝,我不明白为什么它被解释为十进制整数.

我想这里有一些兼容性规则,但我找不到正式的定义.可以请任何人帮我这个吗？

(为什么我需要这个:我正在使用JavaCC为Java开发一个JavaScript/ECMAScript解析器,并且必须特别注意规范 - 以及它的偏差.)

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

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

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

是否有现成的英语语法,我可以加载它并在NLTK中使用？我搜索了使用NLTK解析的示例,但似乎我必须在解析句子之前手动指定语法.

非常感谢!

在离开这个话题 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 形式（ …