计算所有可能的长度为 N 的计算机程序

Question

我会使用 Javascript 作为语言使它易于理解

使用 ascii 作为字母表，并给出所有可能的 "statements" 长度 N 使用 ascii 形成，有多少将是一个有效的 JS 程序。长度 8

的示例

var i=0; //Is a string 8 characters long, and valid JS
jar i=0; //Is a string 8 characters long, but invalid JS
gfjsjhh3 //Is a string 8 characters long, but invalid JS
now imagine we have all possible strings 8 characters long. 
How many will be valid JS?

更多规则：

1) 变量尽可能短

2) 除非必要，否则无空格

更正式的问题定义：

如果给定字母 K 的文法 G，以及长度为 N 的所有可能组合（语句）的集合，这些组合（语句）可以用 K（或 K* 直到长度 N）形成，那么其中有多少个语句将满足语法 G.

我知道你认为这是一些学术性的、脱离现实的东西。但是，如果是程序的语句数量远少于组合总数，则可以使用small "numbers"来指代这些稀疏程序在组合海中出现的位置，并能够发送这个"address"而不是整个程序，大大减少了payload

Answer 1

语法通常只是有效性检查的一方面，查看 ES6 §5.3。而且语法很差，无法满足您“尽可能短”的要求。但是语法是推理事物的好工具，所以让我们专注于此。它仍然允许无效程序和具有长变量名的程序，但作为概念验证的起点（无论您的概念是什么）它应该足够了。

您可能会首先考虑 JS 的 derivation trees based on some BNF 语法。类似于 ES6 标准的第 11 至 15 节，但请确保您使用的语法深入到字符级别，而不是将整个标识符视为单个终端。对于您假设的压缩方案，如果您对树的每个节点的选择进行编码，您就会得到类似于您描述的压缩效果。

为了计算给定长度的程序的数量，您可以对 BNF 规则执行 dynamic programming。所以如果你有一条规则说

IndexedMemberExpression ::= MemberExpression '[' Expression ']'

（在 ES6 §12.3 之后松散建模）那么你知道长度为 n 的 IndexedMemberExpression 由 MemberExpression 组成长度 i 和长度 n − i − 2 的 Expression，对于某些 0 ≤ i ≤ n − 2，所以如果你知道这些有多少种方式，你就知道整个表达式。为每个 BNF 非终结符准备一个长度为 1000 的数组，按长度递增的顺序填充它们，就可以得到根规则的推导树（即语法正确的程序）的数量。

实际上，IndexedMemberExpression 只是一种 MemberExpression，您需要将所有这些加起来。所以更像是这样：

allocate an arry of size 1000 for each non-terminal,
  and initialize all the elements to zero

for n from 0 to 1000:

  …

  # compute PrimaryExpression[n] first

  # rule MemberExpression ::= PrimaryExpression
  MemberExpression[n] = PrimaryExpression[n]

  # rule MemberExpression ::= MemberExpression '[' Expression ']'
  if n >= 2:
    for i from 0 to n - 2:
      MemberExpression[n] += MemberExpression[i] * Expression[n-i-2]

  # rule MemberExpression ::= MemberExpression '.' IdentifierName
  if n >= 1:
    for i from 0 to n - 1:
      MemberExpression[n] += MemberExpression[i] * IdentifierName[n-i-1]

  …

对所有规则执行此操作，顺序确保在首次使用增量左侧的每个非终结符之前在右侧完全更新它。

请注意，对于几乎任何长度为 n 的字符序列，对应的字符串文字将是长度为 n + 的有效 JS 表达式2. 所以不要指望有效程序的数量与任意字符序列的数量相比具有完全不同的渐近行为。

计算所有可能的长度为 N 的计算机程序

Count all possible computer programs of length N

math

programming-languages

combinatorics