学习上下无关文法

OK, 现在来讲一讲最近学的一些东西，首先就是一个叫 context-free grammars, cfg, 上下无关文法。然后为什么要学习这个呢？因为大多数的编程语言都是语法和句语句构成是上下无关的语言，然后还有合法的那种布尔查选语言表达式也是上下无关语言。英语的句式在一定程度上也可以有上下无关的文法表达。

然后我们也知道有正则表达式，正则表达式它无法表示比如括号之类的匹配。然后所以我们首先用一种 grammar，也就是文法来描述上下无关语言，然后定义一种 PDA，也就是 push down autonomous 的机器来识别这种语言。上下文 cfg 的定义由次元组组成，次元组是什么呢？就是一个括号里面有四个参数，首先就是 variable 变量集合，就是比如大写字母 S, A, B 的，然后再就是一个 terminal，terminal 是什么？中截幅集合，就是里面比如 0, 1, A, B 或者 example，然后再就是 star variable，就是开始变量用 S 表示，然后再就是 P，P 是什么呢？P 就是 production，也就是实现这个的东西的一种规则。

比如我们有一个形如 0 的 n 次方 1 的 n 次方的这个语言，我们就可以写成 S → 0S1，然后一个竖线 example。这个竖线表示的是什么呢？竖线表示的是或，也就是说如果我要推导这个东西的话，就是变成 S 可以推导成 0S1 或者说是空集。然后这个 0S1 呢又可以推导成 00S11，然后如果 S 是空集的话，它就可以推导出 0011，也就是说接受了这个 0011。

然后对于回文来说，它需要的是左边和右边，就是最左边和最右边的相等，然后里面一个和最右边的左边一个相等，所以它可以表示为什么呢？P，然后 S → aPa，一个竖线 bPb，一个竖线 example。然后这个也可以进行推导，虽然这个可以表示回文数，但是它只能有偶数位，它不能表示奇数位的问题。

然后再就是考虑到一个新知识，就是推导和推导数。推导是什么呢？就是根据你的那个规则来进行填写，然后左推导就是每一步替换最左边的变量，右推导就是每一步替换最右边的变量。比如这个例子 S → 0S1 | 1S0 | example，然后它的 011100 的推导过程可以写成 S → 0S1 → 01S → 011S0S，最后再经过几步可以变成 01100。

然后推导数是什么呢？推导数有四个东西，一个是 root，root 就是根节点，也就是起始变量，类似节点是变量，然后竖的叶子是终结符，子节点是从左到右产生右侧的内容。然后 ambiguous grammar，奇异就是说你一个东西，一个 string 或者是一个字符串，可以由一个数有多种方法产生，则它就会产生一种奇异。如果它只能这个数，只有一种方法可以产生这个 string，那么它就是 unambiguous。然后大概就是讲这么多。