构建上下文无关语法

2024-01-23

如何为以下语言构建上下文无关语法:

L = {a^l b^m c^n d^p   | l+n==m+p; l,m,n,p >=1}

我首先尝试:

S -> abcd | aAbBcd | abcCdD | aAbcdD | AabBcCd

进而A=其他东西...但我无法让它工作。

.

我想知道我们如何记住应该为 no 增加多少个 c。 b 的增加?
例如:

string : abbccd

语法是:

  1. S1-> 一个S1 d | S2

  2. S2 -> S3 S4

  3. S3-> 一个S3乙|厄普西隆

  4. S4 -> S5 S6

  5. S5-> bS5c |厄普西隆

  6. S6-> cS6d |厄普西隆

规则 1 添加相同数量的 a 和 d。

规则 3 添加相同数量的 a 和 b。

规则 5 添加了相同数量的 b 和 c。

规则 6 添加相同数量的 c 和 d

这些规则还确保根据给定的语言维持字母顺序。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

构建上下文无关语法 的相关文章

  • 上下文无关语言问题(泵引理)

    我知道这与编程没有直接关系 但我想知道是否有人知道如何将泵引理应用于以下证明 显示L a n b n c m n m 不是上下文无关的语言 我对应用泵送引理非常有信心 但这一点真的让我很恼火 你怎么认为 编辑 我完全把你引入了错误的轨道 当
  • 0,1 上的双字补码的上下文无关语法是什么? [关闭]

    Closed 这个问题不符合堆栈溢出指南 目前不接受答案 L ww w 属于 0 1 的补集的 CFG 是多少 首先 请注意以下事实 任何奇怪的单词都是语言的一部分 让我们定义以下语言 L1 w1w w 0 1 L0 w0w w 0 1 这
  • OpenGL是一个“状态机”吗?

    OpenGL 通常被描述为 状态机 因为据我所知 它由可以通过其 API 设置的全局变量组成 并且它们更改 定义其行为 例如 可以设置当前颜色或变换矩阵 许多状态变量具有连续的值范围 然而 据我了解 计算机科学中的 状态机 或 有限状态机
  • 如何修改解析语法以允许赋值和非赋值语句?

    所以问题是关于下面的语法 我正在研究一种小型解释语言 我们在课堂上学习了一些编译器设计 所以我想将其提升到一个新的水平并自己尝试一些东西 我被困在试图制作非终结符号Expr Statement Expr SC Expr I need hel
  • 将上下文无关语法转换为正则表达式

    我目前正在查看 CFG 并看到答案 但我不确定他们是如何得到它的 他们是如何将其从 CFG 转换为正则表达式的 S gt aS bX a X gt aX bY a Y gt aY a answer R E gt a a ba a ba ba
  • 使用 C++11 正则表达式捕获上下文无关语法文件的内容

    Preface 我正在尝试编写自己的上下文无关语法规范 以与我的词法分析器 解析器的规则相关联 它的意思是类似于ANTLR 其中大写标识符分类为词法分析器规则 小写标识符分类为解析器规则 它旨在接受词法分析器规则的字符串文字和 或正则表达式
  • 如何确定上下文无关语法是否描述了常规语言?

    给定任意上下文无关语法 我如何检查它是否描述了常规语言 我不是在寻找考试 技巧 我正在寻找一种可以编写代码的万无一失的机械测试 如果有帮助 这里是我可能会收到的 CFG 作为输入的示例 具体来说 请注意 答案一定比仅仅寻找左递归或右递归复杂
  • 用堆栈实现的 LL(1) 解析器:如何构建 AST?

    我目前正在手工构建一个解析器 它是一个 LL 1 解析器 目前 它是一个很棒的识别器 它的函数 parse List tokens 决定标记是否是该语言的成员 现在 我想为该输入构建相应的 AST 但是 我知道如何以递归下降的方式实现它 已
  • PEG 和 CFG 有什么区别?

    由此维基百科 http en wikipedia org wiki Parsing expression grammar Semantics page 之间的根本区别 上下文无关语法和解析 表达式语法是 PEG 的 选择运算符是有序的 如果
  • JavaScript 是上下文无关语言吗?

    这篇文章关于浏览器如何工作 http taligarsiel com Projects howbrowserswork1 htm解释了 CSS 如何是上下文无关的 而 HTML 是not 但是 JavaScript 呢 JavaScript
  • 这种语言有下推自动机(PDA)吗?

    the language is An B 2n Cn where n gt 0 我认为是有的 因为你可以这样处理 推入A 推入B 每个C从堆栈中弹出3次 如果没有C并且堆栈为空 则返回true 否则返回false 使用泵引理来证明这不是上下
  • NLTK 上下文无关语法生成器

    我正在开发一个带有 Unicode 字符的非英语解析器 为此 我决定使用 NLTK 但它需要预定义的上下文无关语法 如下所示 S gt NP VP VP gt V NP V NP PP PP gt P NP V gt saw ate wal
  • 简单英语中的乔姆斯基层次结构

    我试图找到乔姆斯基提出的 4 个级别的正式语法 无限制 上下文相关 上下文无关 常规 的简单 即非形式 解释 我已经很久没有学习正式语法了 各种定义现在让我难以想象 明确地说 我是not寻找随处可见的正式定义 例如here http en
  • 对于给定的有限代表字符串列表,正则表达式的语法推理?

    我正在分析一个大型公共数据集 其中包含许多详细的人类可读字符串 这些字符串显然是由某些常规 在形式语言理论意义上 语法生成的 逐一查看这些字符串组以了解其中的模式并不太难 不幸的是 大约有 24 000 个独特的字符串被分为 33 个类别和
  • “现代”正则表达式的识别能力

    真正的现代正则表达式实际上可以识别哪一类语言 每当存在带有反向引用的无限长度捕获组时 例如 1 正则表达式现在匹配非常规语言 但这本身并不足以匹配类似的东西S S 匹配括号对的上下文无关语言 递归正则表达式 这对我来说是新的 但我确信 Pe
  • 转换为乔姆斯基范式

    我确实需要你的帮助 我有这些作品 1 A gt aAb 2 A gt bAa 3 A gt 我应该应用乔姆斯基范式 CNF 为了应用上述规则 我应该 消除 产生式 消除单一生产 删除无用的符号 我立即陷入困境 原因是 A 是一个可为空的符号
  • D的语法真的是上下文无关的吗?

    几个月前我在 D 新闻组上发布了这个问题 但由于某种原因 答案从未真正说服我 所以我想我应该在这里问 D 的语法显然是上下文无关的 http www digitalmars com d 2 0 template comparison htm
  • 在打字稿 AST 中获取变量声明类型的正确方法?

    看了一眼declarationEmitter对于变量声明 它具有以下功能 emitVariableDeclaration最终调用 writeTypeOfDeclaration 这段代码的作用就是它所说的 它需要一个变量声明并打印变量及其类型
  • 正则表达式中的顺序不重要吗?

    我正在查看此 stackoverflow 链接中提出的问题 奇数个 a 的正则表达式 https stackoverflow com questions 28902496 regular expression for odd number
  • BNF 可以处理远期消费吗?

    最近我发现了 python 模块pyparsing 一个通过编写来解析数据的绝佳工具grammar 而不是解析器 我对上下文无关语法的概念很陌生 所以请纠正这个问题中的任何错误假设 Pyparsing 可以实现 BNF 巴科斯 诺尔范式 h

随机推荐