问题标签 [context-free-grammar]

如何创建一个上下文无关的语法，它主要分析文字文本（空格、字符、符号等），同时寻找 ${...} 或 $someCommand{...} 形式的表达式？请注意，如果它找到“我今天得到了 10 美元”，它不应该对它做任何特别的事情。

可能吗？

我正在尝试做一个练习，将语法翻译成乔姆斯基范式。我知道在正常情况下如何做到这一点，但这次我使用的语法是正确的递归。（从技术上讲，语法是前一个问题的答案，所以我可能只是有错误的伽玛。）

我想我可以通过使用固定的规则序列代替 ε 规则来做到这一点，但我想确保我没有走错方向。用一个例子更容易解释：

对于产生 n 'a 的语法，其中 n 大于 0 和三的倍数：（别担心，这与我实际练习的语法完全不同）

正确的翻译是：

对于初学者来说，这是一个家庭作业问题。我有一个想法，但我仍然无法得到正确的答案。我不是在寻求答案，我只是在寻求帮助来回答问题。

我目前正在尝试为该语言编写上下文无关语法

因此，基本上 a 的数量是 b 的两倍，而两者之间的 ad。例如：

这是关于我所拥有的，我没有太多......我理解这些CFG的概念我只是不确定这个问题的逻辑。我不确定我是否朝着正确的方向前进......

谢谢。

我需要证明 A 不是上下文无关的。我猜我必须为此使用 Pumping Lemma，但是如何？

这听起来可能很奇怪，但它是在解析器中使用的，我希望能够解析某种形式的东西

富[酒吧]

因此，这将在列表中表示为：

[foo, [, bar, [] 也许这样的词在 DCG 中会写成：

问题是方括号是保留字符，那么我该如何在prolog中表示呢？

我正在上有限自动机的课程。我正在准备期中考试，但在为特定语言创建语法时遇到了麻烦。虽然我发现简单的非常直观，但当它们变得更复杂时，我似乎不知道从哪里开始。例如：

L = { w E { a,b,c}* : nb(w) != na(w) + nc(w) }

答案是：

S→S1 | S2
S1→bS3 | S3b | S3bS3
S3→S0 | S1
S2→XS4 | S4X | S4XS4
S4→S | S2
S0→bS0XS0 | XS0bS0 | e
X→a | C

如果有人可以就所涉及的思维过程给我一些指导，将不胜感激。

我有{a^i b^j c^k | i,j,k>=0 & i>j & j>k} 我开始假设m为我挑选一些的语言，例如一个字符串

然后将字符串拆分为不为空的字符串，(z =) uvwxy然后 当我选择一个“ ”时，我感到困惑。假设我选择然后我有： 而且我不完全确定从哪里开始，因为对我来说，看起来我可以选择该语言中的 vwx。vx#(vwx)<=mii=1uv^1wx^1y

有什么建议么？

字母：a、b、c 我正在尝试定义一个接受

我认为可以接受的一些字符串是：#abc#; #aabbcc#; #aaabbbccc#; #abbccc#; #aaabbc# 等 a、b 和 c 的数量不一定相等。

在最右边的黑色空间上启动下推自动机的头部。

通常我把我的 PDA 写成列：

等等...

字母表：0、1

考虑一个翻转，翻转每个字符：0 -> 1；1 -> 0 所以如果 w = 0011 那么 w-flip = 1100

考虑反向是颠倒顺序的字符所以如果 w = 01101 那么 w-reverse = 10110

现在我正在尝试制作一个 PDA，它采用字符串 w，然后打印 w，打印（w-flip-reversed）

所以这将打印：“011001”

考虑 # 是一个空白字符。所以一个字符串会开始 #011#

转换表如下所示：

等等

有任何想法吗？

我正在将上下文无关语法转换为格雷巴赫范式 (GNF)。主要的转换（来自 Hopcroft & Ullman）是对语法的索引变量的一系列迭代。它本质上是“无状态的”。我已经将它实现为适当索引上的一系列折叠（实现相当简单）：

maxIndex rl返回一组规则中的最大变量索引；subst rl kj用右手边以j索引变量开始的规则对k索引规则执行替换。执行完 gnf后，我需要以相反的顺序对语法进行最后一次传递。

问题是noLR，它用左递归k索引规则转换语法。这是一个“有状态”函数，因为必须为每个应用 noLR 的规则（或 k 索引规则）生成一个唯一变量。所以我写了一个有状态的函数

我可以对noLR进行排序，以更新noLR作为参数的n 。不过，我不确定如何在上述函数的step2中执行noLR 。我似乎无法在模式中使用 let ...，因为有状态计算嵌入在几个递归函数中。

我想要做的是让n成为某种类型的全局变量，类似于n的显式线程，我可以在step2中调用和更新它，这就是为什么我最初将函数编写为带有eta -expansion 的折叠（对于n）。有谁知道我如何在 state monad 中构造gnf来实现这种效果？除了折叠中的最后一次计算，没有其他东西是“有状态的”，我只喜欢使用带有“琐碎”示例的状态单子。我比较迷茫。