问题标签 [language-theory]

我最近开始学习正则表达式，并试图为上面的问题写一个。如果限制只放在一个字母上（例如，不超过 2 个“b”），这并不困难。

那么答案是：a* c*(b|ε)a* c*(b|ε)a* c*

但是对于 2 个“b”和 3 个“c”，“a”之间可能的排序总数为 24（5 选择 3），因此编写一个包含所有这些可能性的正则表达式将非常繁重（因为我们可以选择任意数量的 bs 和 cs，只要数量分别小于 2 和 3）（例如 bcbcc、cbbcc、bcbc、bcc、b、c、...）。

那么是否可以为问题编写一个简洁的正则表达式，或者至少可以通过简化来写出可能性？

当且仅当它是有限的 100 => n <= 0 时，语言 a^nb^2n 怎么可能是规则的？

我知道当 n=>0 时（ a^nb^n ）这种形式的语言是不规则的，因为我们需要一个临时内存来跟踪 a 和 b 的数量，而且我知道每一种有限语言都是常规的，但我不明白是什么使类似形式的有限语言成为常规的？我们如何证明呢？我需要一些线索，除了能够获得其等效的正则表达式之外，我还需要一些更详细的解释..

谢谢

假设我有一种类似 algol 的语言，具有静态类型和以下代码：

其中a是浮点数、b整数、c双精度和d长整数。然后，语言将转换d为 long 来操作c，并转换b为 double 来操作c*d结果。因此，在那之后， double 结果b+c*d将转换为 float 以将结果分配给a. 但是，当它发生时？我的意思是，所有转换都发生在运行时还是编译时？

如果我有：

上面的代码有条件。如果编译器在编译时转换它，某些部分可能永远不会运行。这个对吗？

我对 Coq 有点陌生，我正在尝试对 Coq 中的常规语法进行一些形式化。假设我有一个归纳类型如下：

代表(a* b*)语法的推导规则。假设我想提取它们以供以后使用。有什么办法可以做到这一点并将其存储在列表列表中？例如，我想要一个可以返回 me 的程序[[S [inr a; inl S];S [inr b;inl S];[]]。任何其他想法将不胜感激。

提前致谢。

我正在学习 Coq，我想用它来形式化正则语言理论，特别是有限自动机。假设我有一个自动机的结构如下：

其中 state 是归纳类型：

终端类型为

我正在尝试定义它，以便稍后我可以概括任何常规语言的定义。现在，我想构建一个识别语言 (a * b *) 的自动机，它是 {a,b} 字母表中的所有单词。有没有人知道如何构建某种定点函数来运行单词（我将其视为终端列表）并告诉我该自动机是否识别该单词？任何想法/帮助将不胜感激。

在此先感谢，埃里克。

在 Kernighan 和 Ritchie 撰写的“C 编程语言”（1988 年）中，第 10 页。234，关于C语言的语法，它读作

...这个语法对于 YACC 解析器生成器是可以接受的。它只有一个冲突，由 if-else 歧义产生。

他们指的是什么？什么是“if-else 歧义”，为什么它会为 YACC 产生冲突？

我有时会发现自己在扫描仪中备份。这是一个典型的例子：

在上面处理 JSON 数组的扫描器中，数组中的第一个元素可能会丢失，在这种情况下，扫描器会首先遇到一个逗号，否则它将遇到一个将开始一个值的字符。由于主循环总是以前进开始，如果遇到非逗号字符，则我备份，使其成为第一个字符。

是否有替代方案可以使扫描仪始终保持前进，或者在某些情况下不可避免地进行备份？

我正在用 C++ 实现一种编程语言，我正在进入 AST 生成阶段。

我想使用一个三步程序：

1. 识别语句的类型；
2. 将标记与左值右值和节点中的表达式分离为临时和本地 AST；
3. 设计并将其添加到全局 AST。

例如，这将为声明变量提供以下内容：

临时形式（右值/节点/左值）：

表示为经典的 AST：

然后，将临时树添加到全局树中，指定声明的类型：

这适用于除函数声明和函数调用之外的所有内容：

实际上，对于这种类型的表达式，没有节点可以区分左值和右值。我也不知道如何表示函数参数。我曾想过这样的事情：

同上通话：

但我觉得如果我这样做，就没有逻辑了。

所以，我想知道是否没有一种方法可以接近我的方法来改进它，或者我的方法是否必须完全修改。

PS：我在抽象语法分析和树领域还比较陌生，但是我已经阅读了很多关于这个主题的文档和教程。

问：证明 L={ww|w ∈ {0,1}*} 不是上下文无关的

我的解决方案：

假设 L 是上下文无关的

设其泵送长度为 P

因此，

字符串 = 0^P 1^P 0^P 1^P

设 P=2, S= 00 11 00 11

S 可以划分为 uv^ixy^iz

抽完之后，

0^3 1^2 0^3 1^2 因此它采用ww的形式 （满足第一个条件）

|vy|=4>0（满足第二个条件）

|vxy|= 7，大于泵送长度 2（不满足第 3 个条件）

因此，与 L 是上下文无关的假设相矛盾。

因此 L 不是上下文无关的

我的证明正确吗？

我从几个来源了解到 LL(1) 语法是：

1. 毫不含糊，
2. 不是左递归的，
3. 并且，确定性（左分解）。

我不能完全理解的是为什么以上对于任何 LL(1) 语法都是正确的。我知道 LL(1) 解析表将在某些单元格中有多个条目，但我真正想要得到的是以下命题的正式和一般（没有示例）证明：

左递归 (1)、非确定性 (2) 或歧义 (3) 文法不是 LL(1)。