问题标签 [context-free-language]

我正在学习编译器，我对如何创建一种语言的上下文无关语法感到困扰。有没有一种方法可以为大多数语言创建上下文无关语法？我是这个领域的新手，所以这个问题很基础，希望你能帮助我。

给定三个符号：“（”“）”和“;”

如何为满足以下条件的 S 表达式创建上下文无关语法的产生规则：

• 整个表达式嵌套在括号中，这意味着它以“（”开头并以“）”结尾。

如果从左到右读取表达式，则表达式任何位置（最后一个除外）上的开括号的数量都大于闭括号的数量。在表达式的末尾，开括号的数量应该等于闭括号。

• 括号可以以任何方式嵌套。
• 右括号必须用“;”与左括号分开。
• 最里面的括号可以包含一个“;” 或保持为空。
• “;” 不得连续发生。

任何引入的非终结符也需要使用大写字母。

语法中包含的字符串：

不包含在语法中的字符串。

我曾尝试使用以下语法，但我从中得到了一些错误的值，感谢任何输入/更正。

鉴于 L1 是确定性上下文无关语言，而 L2 是常规语言。L1 U L2 结果 DCFL 还是正则？

请举例说明上下文

非正则语言的补语总是递归语言吗？

我了解 1.context-free 语言不会在补语下关闭。2.递归可枚举语言在补码下不封闭。3.递归语言确实在补码下封闭。

但是我怎样才能使用这些事实来回答最初的问题呢？如何判断非正则语言是否递归？

假设您有一种语言 L，并且您想确定它是否是上下文无关的。与常规语言相交的上下文无关语言是上下文无关的。这足以证明 L 是上下文无关的吗？

意义，

L intersect P = T 其中 P 是常规语言，T 是上下文无关的。这是否意味着 L 是上下文无关的？

我必须决定几种语言是否是常规的、上下文无关的、det。无上下文或 type-0。我了解如何显示一种不规则的语言（使用抽水引理），但是如何非常快速地为其他语言类型决定它？第一语言是

{a,b,c}* \ {a^n b^n c^n | n is element of natural numbers}

首先，我不学习计算机科学，我只是对这个学科感兴趣。

解析器基本上做到了这一点：

1. 读取输入
2. 创建令牌
3. 实际解析令牌并创建一个 AST

所以我认为为了确定一个单词是否是常规语言，你使用 FSM，而对于 CF 语言，你需要一个解析器，因为可能存在递归结构。因此，存在用于常规语言的扫描器生成器和用于 CF 语言的解析器生成器。

但是现在我读到你可以为正则表达式构建一个递归的体面解析器：

http://matt.might.net/articles/parsing-regex-with-recursive-descent/

那么这一切是如何结合在一起的呢？

为什么我需要解析常规语言？我认为有限状态机就足够了？

例如，如果我想识别 java 程序中的块注释（即/* .. */），我只需要编写一个 FSM，所以基本上是一个 switch-case-statement。我不需要解析器...

感谢您的帮助和澄清！

问题是提供上下文无关的语法，其中 L={w∈{a,b}∗∣w 中 a 的数量比 b 的数量大一}。我的解决方案是

谁能告诉我为什么我的解决方案不适用于这种语言？

语言是 {w|w has an odd length}，字母表是 {0,1}。

我想出了一个解决方案

这本书有

这些是等价的吗？

我刚参加了期中考试，但无法回答这个问题。

我们如何才能表明下面的语言是模棱两可的？

L={a ⁿ b ^m c ^p : n≠m} U {a ⁿ b ^m c ^p : m≠p}

我认为这很难，谁能帮助我使用自动化工具或......我们如何证明它？