时间戳

首页 > 解决方案 > 语言的上下文无关语法 {a^ib^jc^i}

compiler-construction - 语言的上下文无关语法 {a^ib^jc^i}

问题描述

在练习期间，我应该为以下语言编写上下文无关语法：

在此处输入图像描述

我不确定我是否完全理解这种方法，但这就是我得到的。

由于我们需要至少 1 c被任何相等数量的a和b包围（可能为零），我想出了以下 CFG：

T --> aCb | aTb | C
C --> cS | cC
S --> empty

例如，从上面看，我永远不能创建一个字符串，其中没有至少 1 个c。但是我可以创建一个只有一个c而没有a或b的字符串。类似地，我可以创建带有aa ... c ... bb的字符串（任意数量的a和b之间只有 1 个c）以及任何与前一个类似但带有任意数量c的字符串s 也是。

但是，我觉得这个 CTF 比需要的要复杂一些。任何人都可以告诉我如何改进，或者如果它是错误的 - 我错过了什么？

编辑：经过rici的一些好的输入，我现在得到的是：

T --> aTb | cC
C --> cC | empty

通过删除任何冗余（例如aCb可以通过aTband实现C）以及非终端S.

标签： compiler-constructioncontext-free-grammarcontext-free-language

解决方案

  1. 消除S。除了收取薪水之外，它没有做任何事情。

  2. T → a C b是多余的，因为您已经拥有T → a T band T → C，这显然可以做同样的事情（通过按顺序应用它们）。

推荐阅读