问题标签 [language-theory]

我创建了一种特殊用途的“编程语言”，故意（通过设计）不能两次评估同一段代码（即它不能循环）。它本质上是用来描述一个类似流程图的过程，其中流程图中的每个元素都是一个条件，它对同一组数据执行不同的测试（不能修改它）。分支可以拆分和合并，但不能以循环方式，即。流程图不能循环回到自身。当到达分支结束时，返回当前状态并退出程序。

写下来时，典型的程序在表面上类似于纯函数式语言的程序，除了不允许任何形式的递归并且函数永远不能返回任何内容。退出函数的唯一方法是调用另一个函数，或者调用返回当前状态的通用退出语句。通过采用结构化编程语言并删除所有循环语句，或者通过采用“非结构化”编程语言并禁止在代码中倒退的任何 goto 或 jmp 语句，也可以实现类似的效果。

现在我的问题是：有没有一种简洁准确的方式来描述这种语言？我没有任何正式的CS背景，对于自动机理论和形式语言理论的文章我很难看懂，所以我有点不知所措。我知道我的语言不是图灵完备的，经过巨大的痛苦，我设法向自己保证，我的语言可能可以归类为“常规语言”（即可以由只读图灵机评估的语言），但有更具体的术语吗？

如果该术语对于精通一般编程概念但没有正式 CS 背景的观众可以直观地理解，则可以加分。如果有一种特定类型的机器或自动机可以评估这种语言，也可以加分。哦，是的，请记住，我们不是在评估数据流 - 每个元素都可以（只读）访问完整的输入数据集。:)

在超前的关系中有一种美。考虑以下示例：

1. 原子由亚原子粒子组成，分子由原子组成，细胞由分子组成，器官由细胞组成，人由器官组成，社会由人组成。
2. 围棋游戏的复杂策略是建立在需要构建具有“两只眼睛”的结构以便它们能够生存的基础上的——然而，“两只眼睛”的东西从来没有在规则中说明，但它本身就是围棋的一种新兴属性。非常简单的围棋规则。
3. Conway's_Game_of_Life的图灵完备性可以用滑翔机、枪支和宇宙飞船来证明，它们又基于开和关的概念以及非常简单的规则集。

在所有情况下，最小的对象集和最小的规则集最终会导致非常复杂的结构。

我的第一个问题：是否可以概述一组可用于构建 OOP 语言的小而简约的编程“对象”和“规则”？

现在，聪明的计算机科学家可能会指出规则 110的图灵完备性并说这就是你所需要的！但这并不是我想要的。相反，冒着提出定义不明确的问题的风险，可以构建到面向对象编程语言中的最简单、人类可理解的概念是什么？

对于暗示我想要什么的糟糕且不完整的示例，请定义三个概念对象：引用、函数和信息持有者。然后（第 2 级？）定义一个结构作为信息持有者，通过对其他信息文件夹的引用来保存其他信息。一个基本的类（第 3 级？）将通过对函数的引用来扩充结构，但必须构建额外的结构来处理私有函数与公共函数的概念。最终，我们应该得到一种功能齐全的 OOP 语言，它完全建立在基本概念之上，而且我们在任何地方都没有作弊通过使用机器代码硬编码优化或语法盐。理想情况下，最终结果仍然是有吸引力且可读的代码。

我的第二个问题：是否有任何 OOP 语言已经接近这一点？

阅读一些 相关 问题让我想到了 HTML 的理论性质。

我在这里不是在谈论类似 XHTML 的代码。我说的是这种疯狂的标记之类的东西，它是完全有效的 HTML（！）

那么考虑到 SGML 在这里注入的巨大复杂性，HTML 是一种上下文无关的语言吗？无论如何，它是一种正式的语言吗？有语法吗？

HTML5 怎么样？

_{我是正式语言概念的新手，所以请多多包涵。是的，我已经阅读了维基百科的文章；）}

我知道语句后需要分号（我说的是 Java、C++ 和类似语言），但在花括号后不需要分号。为什么这样？

是什么原因？我的意思是，这背后的理论是什么？

主要的 Javascript 解释器是否有任何内置优化？我正在考虑非常简单的案例，例如

我有一个数字列表，我想找到至少 3 个...这里是一个例子

我在 sql 数据库中有大量数字，格式为（例如）

等等等等基本上是0到99之间的6个随机数。

现在我想找到一组给定数字中至少出现 3 个的字符串。例如：

给定：01-02-03-10-11-12 返回其中至少包含 3 个数字的字符串。例如

我在想可能有一些算法甚至正则表达式可以匹配这个......但我认为我缺乏计算机科学教科书的经验让我绊倒了。

不——这不是作业问题！这是为了实际应用！

我正在用 ruby​​ 开发，但任何语言的答案都将不胜感激

假设我有以下语法：

如果不ϵ涉及该语法，我将构建第一个状态，例如：

但是ϵ符号呢？我应该包括：

也？

如果是这样...在创建下一个州时...我应该做GOTO(Io,ϵ)，成为第一个州吗？

我正在尝试创建一个后缀到中缀转换器，但我无法为后缀公式创建语法。我也找了一段时间没有成功。。

我可以使用什么语法来识别有效的后缀表达式？

我需要的标记是：、number和+( *pow )。^

我欣赏 Python 的一件事是它区分了可变类型和不可变类型。在开始使用 Python 之前在 c 中进行了一段时间的编程后，我惊讶于 Python 如此轻松地消除了指针取消引用的所有复杂性，这些复杂性让我在 c 中发疯。在 Python 中，一切都按我预期的方式工作，我很快意识到可变/不可变的区别在其中起着重要作用。

当然，仍然存在一些问题（可变函数参数默认值是一个值得注意的例子），但总的来说，我觉得可变/不可变的区别极大地阐明了变量及其值是什么以及它们应该如何表现的问题。

但它来自哪里？我不得不假设 GvR 不是第一个想到这种区别的人，Python 也不是第一个使用它的语言。我有兴趣了解使用此概念的早期语言，以及有关它的任何早期理论讨论。

字母表“a，b，c”中所有字符串的语言是否具有相同数量的子字符串“ab”和“ba”？

我相信答案是否定的，但很难对其进行正式的演示，即使是非正式的演示。

关于如何解决这个问题的任何想法？