构建上下文无关语法

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(使用前将#替换为@)

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

  • 现实世界的 LR(k > 1) 语法?

    制作 k gt 1 的人工 LR k 语法很容易 Input A1 B x Input A2 B y introduce reduce reduce conflict for terminal a A1 a A2 a B b b b b t
  • 给定以下语言构造语法 {a^n b^m | n,m = 0,1,2,...,n <= 2m} [关闭]

    这个问题不太可能对任何未来的访客有帮助 它只与一个较小的地理区域 一个特定的时间点或一个非常狭窄的情况相关 通常不适用于全世界的互联网受众 为了帮助使这个问题更广泛地适用 访问帮助中心 我刚刚参加了期中考试 但无法回答这个问题 有人可以举几
  • 不允许使用外括号的表达式语法

    对于涉及二元运算符 gt 的表达式 我有以下语法 expression expression BITWISE OR xor expression xor expression xor expression xor expression BI
  • 用堆栈实现的 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
  • 上下文相关的标记化是否需要词汇语法中的多个目标符号?

    根据ECMAScript 规范 https tc39 es ecma262 sec ecmascript language lexical grammar 词法输入的识别有几种情况 元素对句法语法上下文敏感 即 消耗输入元素 这需要多个目标
  • 这种语言有下推自动机(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
  • 什么是终结符和非终结符?

    我正在读 雷布尔 维基百科页面 https en wikipedia org wiki Rebol 解析表达式是用 parse 方言编写的 与 do 方言一样 它是数据交换方言的面向表达式的子语言 与 do 方言不同 parse 方言使用表
  • 有没有一种正则语言来表示正则表达式?

    具体来说 我注意到正则表达式的语言本身并不是正则的 因此 我无法使用正则表达式来解析给定的正则表达式 我需要使用解析器 因为正则表达式本身的语言是上下文无关的 有没有什么方法可以用可以使用正则表达式解析结果字符串的方式来表示正则表达式 注意
  • 对于给定的有限代表字符串列表,正则表达式的语法推理?

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

    我需要一些帮助来解决泵引理问题 L a b c a L lt b L lt c L 这是我到目前为止得到的 y uvw is the string from the pumping lemma 我让 y abbc n n 是泵引理的长度 y
  • “现代”正则表达式的识别能力

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

    如何为以下语言构建上下文无关语法 L a l b m c n d p l n m p l m n p gt 1 我首先尝试 S gt abcd aAbBcd abcCdD aAbcdD AabBcCd 进而A 其他东西 但我无法让它工作 我
  • D的语法真的是上下文无关的吗?

    几个月前我在 D 新闻组上发布了这个问题 但由于某种原因 答案从未真正说服我 所以我想我应该在这里问 D 的语法显然是上下文无关的 http www digitalmars com d 2 0 template comparison htm
  • 正则表达式中的顺序不重要吗?

    我正在查看此 stackoverflow 链接中提出的问题 奇数个 a 的正则表达式 https stackoverflow com questions 28902496 regular expression for odd number
  • csv格式是常规语法还是上下文无关语法?

    我目前正在编写一个 csv 解析器 csv 格式的定义由下式给出RFC4180 https www rfc editor org rfc rfc4180这是由 ABNF 定义的 所以csv的定义绝对是上下文无关语法 不过我想知道csv是否是
  • LL(1) 解析器中 FIRST 和 FOLLOW 集的用途?

    谁能向我解释一下 LL 1 语法中如何使用 FIRST 和 FOLLOW 我知道它们用于语法表构建 但我不明白如何使用 在 LL 1 解析器中 解析器的工作方式是维护一个工作空间 该工作空间最初播种到开始符号 后跟字符串结束标记 通常表示为
  • PDA 接受包含 a 多于 b 的字符串语言

    制作一个 PDA 来识别以下语言 包含 a 多于 b 的字符串的语言 我已经在这个问题上挣扎了好几天了 我的心理似乎完全陷入了困境 任何人都可以为我如何解决这个问题提供一些指导或方向吗 你的 a多于b 的问题可以通过PDA解决 您所要做的就

随机推荐