CFG识别的单词是什么 S -> 1 | 0

Question

我正在处理这个练习：

的单词是什么

S - > 1 | S 0

我觉得这个问题特别具有挑战性，因为有太多的组合，我不知道如何详尽地列举所有的可能性。首先，单词 1、10、100、10100、100100 是一些已识别的单词。

Answer 1

I find the problem particularly challenging because there are so many combinations and I have no clue these how to exhaustively enumerate all possibilities.

与大多数语法一样，可以生成无限多的句子。但是任何给定大小的组合确实不是很多，因为：

语法是线性（没有产生式有超过一个non-terminal）
只有两部作品。

枚举所有可能的句子的简单方法是 breadth-first 搜索可能的最左边的推导，从仅包含起始符号的句子形式开始。（您可以使用最右推导，但最左推导似乎更自然。）

这是一个非常简单的操作，特别是对于计算机来说，虽然语法这么简单，但手工操作起来很容易：

  0   S            start symbol
  1   1            in (0) replace S->1
  2   S 0          in (0) replace S->S 0
  3   1 0          in (2) replace S->1
  4   S 0 0        in (2) replace S->S 0
  ...

这里有一些 Javascript 可以为任意 context-free 语法生成句子（如果 all 参数为 true，则为句子形式）。（语法解析器是原始的，仍然缺少错误消息。但它适用于正确输入的语法。明天我可能会再研究一下。）

function Grammar(s) {
  let tokens = /(\w+|"[^"]+"|'[^']*')|(:)|([|;])|(\S)/g
  let which = m => m.findIndex((v, i)=>v&&i)
  let grammar = new Map()
  grammar.start = undefined
  let put = (lhs, rhs) => {
    if (grammar.has(lhs)) grammar.get(lhs).push(rhs)
    else grammar.set(lhs, [rhs])
  }
  
  let lhs = undefined
  let rhs = []
  
  for (let m of s.matchAll(tokens)) {
    switch (which(m)) {
      case 1: rhs.push(m[1]); break; /* Symbol */
      case 2: if (lhs && rhs.length)
                put(lhs, rhs)
              else if (!lhs && rhs.length == 1) {
                if (!grammar.start)
                  grammar.start = rhs[0]
              }
              else break;
              lhs = rhs.pop()
              rhs = []
              break;
      case 3: if (lhs) {
                put(lhs, rhs)
                rhs = []
                if (m[3] == ';') lhs = undefined
              }
              break
      case 4: break
    }
  }
  if (lhs) put(lhs, rhs);
  return grammar
}

let grammar = Grammar(`
expr: atom
    | expr '+' expr
    | expr '*' expr
    | '-' expr
atom: NUM
    | '(' expr ')'
`)

function* derivationGenerator(grammar, all) {
  level = [ [grammar.start] ]
  while (level.length) {
    nextLevel = []
    for (const form of level) {
      let idx = form.findIndex(sym => grammar.has(sym))
      if (idx < 0 || all) yield form
      if (idx >= 0) {
        let before = form.slice(0, idx)
        let after = form.slice(idx+1)
        grammar.get(form[idx]).forEach(
          rhs => nextLevel.push(before.concat(rhs, after)))
      }
    }
    level = nextLevel
  }
}

function take(gen, n, handle) {
  for (let v of gen) {
    handle(v)
    if (--n <= 0) return gen
  }
}

take(derivationGenerator(grammar), 10, form => console.log(...form))

CFG识别的单词是什么 S -> 1 | 0

What are the words recognized by the CFG S - > 1 | S 0

context-free-grammar