问题标签 [ambiguous-grammar]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
1 回答
572 浏览

parsing - 可以转化为 LR 解析表的上下文无关文法是否明确?

我知道,一般来说,上下文无关语法是否明确是不确定的。然而,这并不意味着这不能为上下文无关文法的子集决定。


语法用于将输入文本转换为解析树。如果一个文法可以为给定的输入生成不止一个解析树,那么它就是模棱两可的。

LR 解析器算法首先将文法转换为 LR 解析器表。之后,它使用 LR 解析器自动机将给定的输入流处理成使用 LR 解析器表的解析树。第一步通常由解析器生成器完成,而第二步是针对每个解析操作执行的。

考虑 LR 解析器表构造算法construct(G) = T | error。该算法接收上下文无关文法G。如果表构造成功,T则返回无冲突的 LR 解析器表。如果建表失败,则返回错误。这种算法的示例是 SLR、LALR 和 CLR。算法失败的典型例子是 shift-reduce 和 reduce-reduce 冲突。

对于有限的输入流和无冲突的 LR 解析器表,LR 解析器自动机可以确定性地从给定的输入流中导出一棵解析树,或者如果输入流与语法不匹配则返回错误。解析步骤可以形式化为parse(T, I) = O | error,其中T是无冲突的 LR 解析表,I是令牌的输入流,O是单个解析树。如果输入流与语法不匹配,则返回错误。

问题

总结以上我的理解的陈述是,任何可以以某种方式转换为无冲突 LR 解析器表的语法都是明确的。但是,如果算法返回错误,这并不意味着任何关于语法是否有歧义的陈述。因此,LR 表构造算法半决定上下文无关文法的子集是否明确。它是否正确?

以下是我的结论可能会落空的一些步骤:

  • LR 表构造算法可能不会终止
  • LR 解析器自动机可能不会终止
  • LR 表构造算法不正确,因此 LR 解析器自动机将接受与构造它的语法不完全相同的输入流集,或者它派生出不同于语法的另一个解析树。

据我所知,对于常见的 LR 表构造算法,以上都不是真的。

我无法找到关于此的明确声明,因此我将非常感谢您提供解释以及讨论并明确回答该问题的参考。

我认为这个问题在设计编程语言时非常重要,因为如果我的结论是正确的,LR 解析器会确保每个用该语言编写的程序都可以被正确解析。还有其他方法可以确保语法明确吗?

0 投票
1 回答
186 浏览

swift - Swift 如何消除表达式上下文中的类型参数的歧义?

看下面两个表达式:

在不知道什么、bazFooBarbaz可以是类型或方法,FooBar可以是类型或变量)的情况下,无法区分 是<表示类型参数列表还是小于运算符。

任何理智的编程语言在解析这样的表达式时都不应该依赖 what baz, Fooand are 。Bar然而,无论我在哪里放置空格,Swift 都设法消除了以下表达式的歧义:

编译器如何管理这个?而且,更重要的是,在 Swift 语言规范中是否有任何位置。描述此规则的地方。翻阅Language ReferenceSwift 书的部分,我只找到了这一部分:

在某些构造中,带有前导<或的运算符>可能被拆分为两个或多个标记。其余部分以相同方式处理,可以再次拆分。因此,无需使用空格来消除>诸如Dictionary<String, Array<Int>>. 在此示例中,结束>字符不被视为单个标记,然后可能会被误解为位移>>运算符。

certain constructs在这种情况下指的是什么?实际的语法只包含一个提及类型参数的产生式规则:

显式成员表达式 → 后缀表达式.标识符generic-argument-clause opt

任何解释或资源将不胜感激。

0 投票
1 回答
84 浏览

context-free-grammar - 这个语法有歧义吗

我想将此语法转换为明确的语法:

我找到了一个比我的解决方案更复杂的解决方案,但我不确定我的解决方案是否正确:

那么我的解决方案正确吗?

0 投票
1 回答
84 浏览

bison - 解决 C 初始化列表的语法歧义

我似乎无法解决以下规则中包含的歧义:

InitializerList_a →,[Initializer][InitializerList_a]

它在我的解析器中引起了移位/减少冲突(我正在使用 Bison)。以下是它的关闭:

任何帮助,将不胜感激。如果需要,我可以发布野牛输出文件。

这是以更易读的方式编写的相同语法:

0 投票
1 回答
420 浏览

compiler-construction - 消除语法中的歧义

模棱两可的语法:

E -> 紫外线 | EBE | 五 | [E]

V -> 一个 | b

U -> < | >

乙->?| !| @

一些信息:

优先顺序: ?< ! <@,一元运算符(<,>)是最高的

二元运算符 ?, !, @ 是右结合的。

我的尝试:

E -> 紫外线 | EBT | 五 | [E]

T -> E

V -> 一个 | b

U -> < | >

乙->?| B1

B1 -> !| B2

B2->@

我不确定在转换过程中是否遗漏了一些极端情况。感谢你们能指出一些错误并提供一些提示。

0 投票
1 回答
78 浏览

nlp - 让menhir找到所有替代品?

我想以以下方式更改 menhir 输出的行为:我希望它查找所有语法替代项(如果找到),并将它们放在一个列表中,然后让我恢复这种模棱两可的解释。它不会减少冲突,只是存储它们。

在 menhir 的源代码中,在我看来,我必须查看“Engine.ml”。作为语法自动机的检查点的状态,产生的语法确定的标记出现在变体类型项目“Accepted v”中。该内容由之前的“accept env prod”函数找到,该函数是递归函数包的一部分,用于更改状态。

您有什么建议吗,我如何更改这些函数以将所有可能的结果放在此处的列表中并像什么都没发生一样继续进行?还是您认为,这无论如何都行不通?

谢谢。

0 投票
1 回答
70 浏览

whitespace - 为什么围绕作品的可选部分的布局会导致歧义?

在 Rascal 中,为什么当在产品的可选部分的位置存在布局时,会导致歧义?Eg"{ }"是模棱两可的Start1,虽然它Start2从以下语法中解析得很好,我本来希望它是完全相同的。

另外,我想知道是否有另一种表示Start2不重复的方式,而不是Start1不会导致同样的歧义。

显然,这段代码没有大量的重复,在这里Start2是一个不错的选择,但这只是一个例子。我正在使用包含三个或四个可选部分的许多产生式的语法,在最后一种情况下,显示的符号Start2已经需要将产生式的非可选部分复制 2^4=16 次,这在我看来确实很麻烦.

0 投票
1 回答
453 浏览

syntax - Verilog `PATHPULSE$` 语法

在阅读 Verilog 规范时,我注意到一个涉及指定路径脉冲的特殊句法结构。具体来说,表格中的陈述

根据规范,in_port并且out_port可以是标识符(包括\- 转义标识符)或带有 - 括号[]范围的标识符。

忽略PATHPULSE用括号对构造进行标记的问题,似乎仍然存在潜在的歧义问题,因为$它可以是正常标识符的一部分。例如,如果一个模块声明如下:

然后给出一个路径脉冲语句:

无法确定$将输入端口和输出端口分开的方式。

我的问题是:有没有更好的方法来标记PATHPULSE结构以避免这种歧义?或者这是 Verilog 的不足?

0 投票
1 回答
185 浏览

parsing - 命题逻辑语法的正确性

我正在尝试为命题逻辑编写语法,以创建 LL 解析器(词法分析)。

我尝试了以下语法:

但我发现它是模棱两可的。我尝试了以下方法来消除歧义:

这个语法正确吗?我成功地消除了歧义吗?

0 投票
1 回答
46 浏览

context-free-grammar - 编译器:改变模棱两可的语法

我对这个练习有一点小问题。

鉴于此语法:

a) 表明它与字符串不明确

b)说出什么语言捕捉了语法

c) 更改语法并构建后代解析器

我的解决方案:

a)我用字符串' ab '显示模棱两可:

b) 语法捕捉这种语言:

c)我的问题是更改语法以构建解析器。我尝试了不同的语法,但它们也模棱两可。例如这个:

你能帮我找到练习的正确语法或给我一个输入吗?