要介绍上下文无关语言我们先来了解一下定义上下文无关文法的工具——产生式的写法。我们还是使用编程语言的表达式作为例子但这次我们假设表达式只有三种——单个表示变量名标识符、括号括起来的表达式和两个表达式相加。比如a是一个变量表达式ab是两个变量表达式相加的表达式(ab)是一个括号表达式。我们用符号E来表示一个表达式那么这三种表达式分别可以定义为E →idE → EEE →(E)这种形式的定义就叫做产生式。出现在→左侧符号E称作非终结符nonterminal symbol代表可以继续产生新符号的“文法变量”。 符号→表示非终结符可以“产生”的东西。而上述产生式中的蓝色id、、等符号是具有固定意义的单词它们不再会产生新的东西称作终结符terminal symbol。注意非终结符可以出现在产生式的右侧这就是具有递归性质文法的来源。产生式经过一系列的推导就能够生成各种完全由终结符组成的句子。比如我们演示一下表达式(a b) c的推导过程E E E (E) E (E E) E (a E) E (a b) E (a b) c推导过程中的代表将当前句型中的一个非终结符替换成产生式右侧的内容。以上推导过程中我们每次都将句型中最左边一个非终结符展开所以这种推导称为最左推导。当然也有最右推导不同之处就算是每次将句型中最右边的非终结符展开E E E E c (E) c (E E) c (E b) c (a b) c可见同一个结果可以具有多种不同的推导过程。使用最左推导时句型的左侧逐渐变得只有终结符而最右推导正好相反推导过程中句型的右侧逐渐变得只有终结符最终结果都是整个句子变为终结符。所有符合文法定义的句子都可以用文法的产生式推导出来。我们语法分析的目的是解析输入的单词流(a b) c得到它的语法分析树。先来看看语法分析树是什么样的。还是以(a b) c为例语法分析树是这样的语法分析树的每一个节点都是一个非终结符或者终结符其中终结符都是树的叶子结点没有子节点而非终结符都是有子节点的。一旦我们得到了语法分析树就可以很容易地进行后续的语义分析比如这个表达式的语义是“先将a和b代表的变量相加再把所得的结果与c代表的变量相加”。那么语法分析树是怎么得到的呢其实刚才的产生式推导过程就可以顺便建立语法分析树只要在展开非终结符的同时在语法分析树中相应的节点下加入非终结展开的结果即可生成。下面我们用动画演示上述产生式通过最左推导和最右推导产生(a b) c语法分析树的过程最左推导最右推导我们可以看到最左推导和最右推导的语法分析树是一样的这证明用相同的文法解析同样的输入也至少存在两种不同的分析方法。后续篇章介绍的递归下降法就是一种最左推导的分析方法而另一类非常流行的LR分析器则是基于最右推导的分析方法。目前流行的编译器开发方式是在语法分析阶段构造一棵真正的语法分析树然后再通过遍历语法树的方法进行后续的分析所以最左推导和最右推导的过程对我们来讲区别不大。我们刚才举的例子中表达式(a b) c只能有一种语法分析树。但另外一些语法分析的输入可能存在多种语法分析树 这称为歧义。刚才的文法其实就是有歧义的在哪里请大家思考一下但为了更清楚地表达歧义的危害我们再举一个新的例子它在前面例子中增加了乘法E →idE → EEE → E*EE →(E)如果用上述产生式推导出表达式a * b c就有两种可能的最左推导最左推导1E E E E * E E a * E E a * b E a * b c最左推导2E E * E a * E a * E E a * b E a * b c这两种推导的语法树是不一样的推导1推导2我们刚才讨论了语法分析树将用于下一步的语义分析。而在语义分析中上述两个语法树的不同主要体现在运算符的优先级上。如果按照推导1的语法树应该先将a和b相乘再加上c而如果按照推导2的语法树则应该先把b和c相加再和a相乘。很明显这两种语义的计算结果是可以不一样的。我们不想编程语言中的同一种表达式有两种语义所以有歧义的文法是不适合用在语法分析的。实践中应该使用没有歧义的文法来确保同一段程序仅存在唯一一种语法分析树。比如我们可以修改一下上述文法的产生式让运算符具有左结合的特性并让乘法一开始就有高于加法的优先级F →idF →(E)T → T*FT → FE → ETE → T修改文法之后*号的两侧不允许直接出现带号的表达式而只能出现带括号的表达式和变量名同时连续的加法或乘法必须从左侧开始运算。这就限制了推导可能进行的方式。在新文法下表达式a * b c就只存在一种语法分析树了我们最后用在miniSharp的文法就和这一个非常类似。在实践当中我们通常需要仔细观察和思考所用的文法是否具有歧义。如果有一些文法拿不定主意我建议大家去参考C# spec里面对C#的文法进行极其详细的定义我相信大家看过Spec之后会更加了解一门现代的编程语言的文法。我也将在后续篇章中介绍一些常见语法结构的设计方法。在本篇的最后我想再多介绍一点点上下文无关语言。有些同学可能从刚才开始就想问为何这种语言和文法叫做“上下文无关”呢其实这里的“上下文无关”是指文法中的产生式都可以无条件展开为箭头右侧的内容。另外存在一种上下文相关文法它的产生式都需要在一定条件下才能展开。上下文相关语言要比上下文无关文法复杂得多而其没有一种通用的方法可以有效地解析上下文相关语言因此它也不会用在编程语言的设计当中。同学们也许已经意识到即使是上下文无关文法和语言也要比正则表达式和正则语言复杂得多。在此我没有办法详细地描述上下文无关语言的性质但是我可以给感兴趣的同学稍微科普一下。就像正则表达式存在一种等价的计算模型——有穷自动机——可以用来解析正则语言一样上下文无关文法也存在一种等价的计算模型——下推自动机Put-Down Automation,PDA。下推自动机除了一组有限的状态和状态转换以外还带有一个无限容量的栈。和有穷自动机不同下推自动机的状态并不仅根据输入字符和当前状态来进行转移还要根据栈顶的字符而且下推自动机还必须决定何时向栈中压入或弹出字符。和有穷自动机类似下推自动机也存在非确定性下推自动机NPDA和确定性下推自动机DPDA两种。这两种下推自动机是不等价的。其中非确定性下推自动机对应于整个上下文无关语言而确定性下推自动机则对应于上下文无关语言的一个真子集。NPDA所具有的“猜测”能力要比NFA强大得多以至于我们无法很容易地用计算机来模拟。我们只能够模拟DPDA来进行解析。所幸的是几乎所有编程语言的文法都是能用一个DPDA所接受的。我们在接下来的篇章中引入的语法分析机制有些甚至还达不到DPDA的能力也就是说我们只能处理上下文无关文法中的一小部分。但即使是这一小部分也足够将C#这样的语法描述出来了。
要介绍上下文无关语言我们先来了解一下定义上下文无关文法的工具——产生式的写法。我们还是使用编程语言的表达式作为例子但这次我们假设表达式只有三种——单个表示变量名标识符、括号括起来的表达式和两个表达式相加。比如a是一个变量表达式ab是两个变量表达式相加的表达式(ab)是一个括号表达式。我们用符号E来表示一个表达式那么这三种表达式分别可以定义为E →idE → EEE →(E)这种形式的定义就叫做产生式。出现在→左侧符号E称作非终结符nonterminal symbol代表可以继续产生新符号的“文法变量”。 符号→表示非终结符可以“产生”的东西。而上述产生式中的蓝色id、、等符号是具有固定意义的单词它们不再会产生新的东西称作终结符terminal symbol。注意非终结符可以出现在产生式的右侧这就是具有递归性质文法的来源。产生式经过一系列的推导就能够生成各种完全由终结符组成的句子。比如我们演示一下表达式(a b) c的推导过程E E E (E) E (E E) E (a E) E (a b) E (a b) c推导过程中的代表将当前句型中的一个非终结符替换成产生式右侧的内容。以上推导过程中我们每次都将句型中最左边一个非终结符展开所以这种推导称为最左推导。当然也有最右推导不同之处就算是每次将句型中最右边的非终结符展开E E E E c (E) c (E E) c (E b) c (a b) c可见同一个结果可以具有多种不同的推导过程。使用最左推导时句型的左侧逐渐变得只有终结符而最右推导正好相反推导过程中句型的右侧逐渐变得只有终结符最终结果都是整个句子变为终结符。所有符合文法定义的句子都可以用文法的产生式推导出来。我们语法分析的目的是解析输入的单词流(a b) c得到它的语法分析树。先来看看语法分析树是什么样的。还是以(a b) c为例语法分析树是这样的语法分析树的每一个节点都是一个非终结符或者终结符其中终结符都是树的叶子结点没有子节点而非终结符都是有子节点的。一旦我们得到了语法分析树就可以很容易地进行后续的语义分析比如这个表达式的语义是“先将a和b代表的变量相加再把所得的结果与c代表的变量相加”。那么语法分析树是怎么得到的呢其实刚才的产生式推导过程就可以顺便建立语法分析树只要在展开非终结符的同时在语法分析树中相应的节点下加入非终结展开的结果即可生成。下面我们用动画演示上述产生式通过最左推导和最右推导产生(a b) c语法分析树的过程最左推导最右推导我们可以看到最左推导和最右推导的语法分析树是一样的这证明用相同的文法解析同样的输入也至少存在两种不同的分析方法。后续篇章介绍的递归下降法就是一种最左推导的分析方法而另一类非常流行的LR分析器则是基于最右推导的分析方法。目前流行的编译器开发方式是在语法分析阶段构造一棵真正的语法分析树然后再通过遍历语法树的方法进行后续的分析所以最左推导和最右推导的过程对我们来讲区别不大。我们刚才举的例子中表达式(a b) c只能有一种语法分析树。但另外一些语法分析的输入可能存在多种语法分析树 这称为歧义。刚才的文法其实就是有歧义的在哪里请大家思考一下但为了更清楚地表达歧义的危害我们再举一个新的例子它在前面例子中增加了乘法E →idE → EEE → E*EE →(E)如果用上述产生式推导出表达式a * b c就有两种可能的最左推导最左推导1E E E E * E E a * E E a * b E a * b c最左推导2E E * E a * E a * E E a * b E a * b c这两种推导的语法树是不一样的推导1推导2我们刚才讨论了语法分析树将用于下一步的语义分析。而在语义分析中上述两个语法树的不同主要体现在运算符的优先级上。如果按照推导1的语法树应该先将a和b相乘再加上c而如果按照推导2的语法树则应该先把b和c相加再和a相乘。很明显这两种语义的计算结果是可以不一样的。我们不想编程语言中的同一种表达式有两种语义所以有歧义的文法是不适合用在语法分析的。实践中应该使用没有歧义的文法来确保同一段程序仅存在唯一一种语法分析树。比如我们可以修改一下上述文法的产生式让运算符具有左结合的特性并让乘法一开始就有高于加法的优先级F →idF →(E)T → T*FT → FE → ETE → T修改文法之后*号的两侧不允许直接出现带号的表达式而只能出现带括号的表达式和变量名同时连续的加法或乘法必须从左侧开始运算。这就限制了推导可能进行的方式。在新文法下表达式a * b c就只存在一种语法分析树了我们最后用在miniSharp的文法就和这一个非常类似。在实践当中我们通常需要仔细观察和思考所用的文法是否具有歧义。如果有一些文法拿不定主意我建议大家去参考C# spec里面对C#的文法进行极其详细的定义我相信大家看过Spec之后会更加了解一门现代的编程语言的文法。我也将在后续篇章中介绍一些常见语法结构的设计方法。在本篇的最后我想再多介绍一点点上下文无关语言。有些同学可能从刚才开始就想问为何这种语言和文法叫做“上下文无关”呢其实这里的“上下文无关”是指文法中的产生式都可以无条件展开为箭头右侧的内容。另外存在一种上下文相关文法它的产生式都需要在一定条件下才能展开。上下文相关语言要比上下文无关文法复杂得多而其没有一种通用的方法可以有效地解析上下文相关语言因此它也不会用在编程语言的设计当中。同学们也许已经意识到即使是上下文无关文法和语言也要比正则表达式和正则语言复杂得多。在此我没有办法详细地描述上下文无关语言的性质但是我可以给感兴趣的同学稍微科普一下。就像正则表达式存在一种等价的计算模型——有穷自动机——可以用来解析正则语言一样上下文无关文法也存在一种等价的计算模型——下推自动机Put-Down Automation,PDA。下推自动机除了一组有限的状态和状态转换以外还带有一个无限容量的栈。和有穷自动机不同下推自动机的状态并不仅根据输入字符和当前状态来进行转移还要根据栈顶的字符而且下推自动机还必须决定何时向栈中压入或弹出字符。和有穷自动机类似下推自动机也存在非确定性下推自动机NPDA和确定性下推自动机DPDA两种。这两种下推自动机是不等价的。其中非确定性下推自动机对应于整个上下文无关语言而确定性下推自动机则对应于上下文无关语言的一个真子集。NPDA所具有的“猜测”能力要比NFA强大得多以至于我们无法很容易地用计算机来模拟。我们只能够模拟DPDA来进行解析。所幸的是几乎所有编程语言的文法都是能用一个DPDA所接受的。我们在接下来的篇章中引入的语法分析机制有些甚至还达不到DPDA的能力也就是说我们只能处理上下文无关文法中的一小部分。但即使是这一小部分也足够将C#这样的语法描述出来了。
双梁正问题 【 torch 实战】（Python代码实现）)
