用于创建“上下文自由语法”的提示；

本文介绍了用于创建“上下文自由语法”的提示；的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我是CFG的新手，

有人可以给我提示如何创建可生成某种语言的CFG

I am new to CFG's,
Can someone give me tips in creating CFG that generates some language

例如

我得到的是：

但是我认为这是错误的，因为 b 可以大于 a 。

but I think this area is wrong, because there is a chance that the number of b's can be greater than a's.

如何使用示例a b 编写CFG h2>

How to write CFG with example ab

语言描述： a b b consist of a followed by b where number of a are equal or more then number of b.

一些示例字符串： {^，a，aa，aab，aabb，aaaab，ab ......}

所以对于一个 a code> b ，但可以添加额外的 a 。感染字符串只能由 a 组成。另请注意， ^ 是null的语言成员，因为在 ^ NumberOf（a）= NumberOf（b）= 0

So there is always one a for one b but extra a are possible. infect string can be consist of a only. Also notice ^ null is a member of language because in ^ NumberOf(a) = NumberOf(b) = 0

在语法中，应该有一些规则，例如，如果添加 b 符号，您还添加了 a 符号。

In the grammar, there should be rules such that if you add a b symbol you also add a a symbol.

，这可以通过以下方式完成：

and this can be done with something like:

   S --> aSb

但这并不完整，因为我们需要一条规则来生成额外的 a s：

But this is incomplete because we need a rule to generate extra as:

   A --> aA | a

将两个生产规则合并为一个语法 CFG。

Combine two production rules into a single grammar CFG.

   S --> aSb | A
   A --> aA  | a

因此，您可以生成由 a 也是 a 和 b （（a b ）模式。

So you can generate any string that consist of a also a and b in (a b) pattern.

但是在上面的语法中，没有方法生成 ^ 字符串。

But in above grammar there is no way to generate ^ string.

因此，请更改此语法，如下所示：

So, change this grammar like this:

   S --> B   | ^
   B --> aBb | A
   A --> aA  | a

此语法可以生成{a b | m> = n}语言。

this grammar can generate {a b | m >= n} language.

注意：要生成 ^ 空字符串，我在语法通过添加 S-> B | ^ ，因此您可以添加 ^ 或符号 a 的字符串和 b 。（现在 B 扮演先前语法中的 S 的角色，以生成相等数量的 a 和 b ）

Note: to generate ^ null string, I added an extra first step in grammar by adding S--> B | ^, So you can either add ^ or your string of symbol a and b. (now B plays role of S from previous grammar to generate equal numbers of a and b)

编辑：感谢@Andy Hayden

您还可以为相同的语言{a b | m> = n}：

Thanks to @Andy Hayden
You can also write equivalent grammar for same language {a b | m >= n}:

   S --> aSb | A
   A --> aA | ^

注意：此处 A-> aA | ^ 可以生成零个或任意数量的 a 。
（由于有效的解析，高度较小的最好）

notice: here A --> aA | ^ can generate zero or any number of a. And that should be preferable to my grammar because it generates a smaller parse tree for the same string.
(smaller in height preferable because of efficient parsing)

以下提示可能有助于为正式语言编写语法：

The following tips may be helpful to write Grammar for a formal language:

这篇关于用于创建“上下文自由语法”的提示；的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

的提示