实现上下文有关文法的三个方法

文法的三个方法"/>

实现上下文有关文法的三个方法

文法分为四型，它们是：正则文法、上下文无关文法、上下文有关文法、短语文法。
这四型文法的历史功绩在于，让人们认识到了语言的复杂性，并挑选最简单的两个实现了。这两个是正则文法和上下文无关文法，对应《编译原理》书中的词法分析和语法分析。
更复杂的上下文有关文法和短语文法，至今未能实现。本文进行探索，期望能有所贡献。

多脚本竞争执行

假设文法中每个符号都是有生命的个体，它们能自主地分析自己的上文是什么、下文是什么，进而作出决定，要把自己变成什么，或是采取怎样的行动。
每个文法符号都对应一个小脚本，这些脚本共同执行。这时会出现竞争，所以叫“多脚本竞争执行”。

有限状态机加树

• 正则文法→有限状态机
• 上下文无关文法→有限状态机+栈
• 上下文有关文法→有限状态机+树
• 短语文法→有限状态机+图

以上四行是个猜想。在上下文无关文法的分析过程中，遇到一个活前缀就替换成文法左侧的一个符号，这使得整个分析过程在栈里就能完成。对于上下文有关文法，文法左侧有多个符号，要把活前缀替换成多个符号，这就形成了树。
但是，文法是一种简单替换的策略，它能否胜任，尚不得而知。

公共命名空间

这个话题在之前的博客中讨论过许多次了，它的中心思想就是，把所有句子集中在一个大的表格中，并且能够通过查表完成翻译。
每一行是一个句子，每一列是一个方言。所有hello world程序都在同一行，用不同的列区分方言。例如，某一列是C语言，某一列是C++，或者是汉语、日语、英语。
因为记录了所有句子，所以，单独一个句子的复杂度就没那么高。