上下文无关文法

从第十二章开始是这本书第二部分,下推自动机理论,之前的第一部分是有限自动机理论,而这本书一共有三个部分,第三部分是图灵理论

使用语法来定义语言

  考虑一个算术表达式

((1/2)+9)/(4+(8/21)+(5/(3+(1/2))))

对于人类来说,可以不费多大力气就得出这个算式的结果,但是对于计算机来说,该如何让它去理解这样一个字符串?并且转换成CPU能够看懂的语言呢?为了解释这些字符,我们同样需要一种机器,它能够接受一个正确的算术表达式,拒绝那些语法不规范或者无意义的字符串,比如((9)+,这个字符串就不应当在该机器上停机,虽然这看上去很理想,但是实际上的问题在于,在真正的读取到最后一个字符之前,我们不可能知道这是一个非法的表达式,如果把+换成),那么这就是一个合法的算术表达式,没有任何问题,如果试图仰仗类似Mealy机的有限自动机去一边读取一遍翻译成机器语言并输出,那么机器就会在意识到表达式是非法的之前输出对应的代码。
  回顾一下算术表达式的递归定义,它包含两条规则:

  1. 任何数字都是合法的算术表达式
  2. 如果xy都是算术表达式,那么(x)-(x)(x+y)(x-y)(x*y)(x/y)(x\verb!^!y)也都是算术表达式

对于诸如((3+4)*(6+7))这种表达式,可以很轻易的自底向上找出对应的产生规则

  • 3是算术表达式
  • 4是算术表达式
  • (3+4)是算术表达式
  • 6是算术表达式
  • 7是算术表达式
  • (6+7)是算术表达式
  • ((3+4)*(6+7))是算数表达式

在得到产生规则之后,就可以很轻易的逐条逐条的把他们转换为机器语言

  • LOAD 3到寄存器1
  • LOAD 4到寄存器2
  • ADD 寄存器1 寄存器2 到寄存器5
  • LOAD 6到寄存器3
  • LOAD 7到寄存器4
  • ADD 寄存器3 寄存器4 到寄存器6
  • MULTIPLY 寄存器5 寄存器6

注:这些并非标准的汇编语言,只是方便理解的伪代码

而对于机器来说,最难的部分就是如何从那个字符串中推导出这些规则,历史上某个人(谁知道呢)发现这个问题和人类学习各种自然语言的过程是相近的,机器识别计算机语言的过程,就类似人类识别自然语言的过程,而人类识别自然语言靠的是文法(Grammar),文法在语言中起到了构建一个合法的语句的作用,它包含一套规则,而这套规则就是一种递归定义,人类通过分析句子由文法构成的不同成分来理解这个句子,而这个过程叫做解析(parsing)
  与自然语言不同的是,计算机的解析过程非常严格,人类也许能够轻易理解大部分不遵循语法规则但是能够表达其意思的句子,计算机不可以,计算机的解析过程将会严格的按照指定的文法规范进行,任何不符合文法的字符串都会被拒绝,在计算机科学领域,我们把类似"语法/文法"这种表达了一系列构成语句的规则的集合叫做生成文法(generative grammar)1生成二字强调了这些规则提供了从个体(单词或者字母表中的字母)来构造一个句子的能力
  在第一章中提到过,在这个理论中,语言的意思是不被重视的,只要遵循语法,他们就是一个合法的句子,我们把有关句子的意思的规则叫做语义(semantic),而不涉及意思的规则叫做语法(syntax),计算机语言解析涉及的所有类似的内容不包含语义相关,只包含语法相关(在编译器设计中,语义分析是之后的事情)
  让我们来看一个自然语言中由语法规则构成句子的示例,对于英语来说,可以列出一些如下的语法规则:

  1. 一个句子(sentence)可以由主语(subject)跟一个谓语(predicate)构成
  2. 一个主语(subject)可以由名词短语(noun-phrase)构成
  3. 一个名词短语(noun-phrase)可以由一个形容词(adjective)跟一个名词短语(noun-phrase)构成
  4. 一个名词短语(noun-phrase)可以由一个冠词(article)跟一个名词短语(noun-phrase)构成
  5. 一个名词短语(noun-phrase)可以是一个名词(noun)
  6. 一个谓语(predicate)可以由一个动词(verb)跟一个名词短语(noun-phrase)构成
  7. 名词可以是:apple,bear,cat,dog
  8. 动词可以是:eats,follows,gets,hugs
  9. 形容词可以是:itchy,jumpy
  10. 冠词可以是:a,an,the

接下来来看看\text{The itchy bear hugs the jumpy dog}该如何被上面列出的10条规则所构成:

\begin{aligned}
\text{句子}&\implies\text{主语 谓语}& Rule.1 \\
&\implies\text{名词短语 谓语}& Rule.2 \\
&\implies\text{名词短语 动词 名词短语}& Rule.6 \\
&\implies\text{冠词 名词短语 动词 名词短语}& Rule.4 \\
&\implies\text{冠词 形容词 名词短语 动词 名词短语}& Rule.3\\
&\implies\text{冠词 形容词 名词 动词 名词短语}& Rule.5 \\
&\implies\text{冠词 形容词 名词 动词 冠词 名词短语}& Rule.4 \\
&\implies\text{冠词 形容词 名词 动词 冠词 形容词 名词短语}& Rule.3 \\
&\implies\text{冠词 形容词 名词 动词 冠词 形容词 名词}& Rule.5 \\
&\implies\text{the 形容词 名词 动词 冠词 形容词 名词}& Rule.10 \\
&\implies\text{the itchy 名词 动词 冠词 形容词 名词}& Rule.9 \\
&\implies\text{the itchy bear 动词 冠词 形容词 名词}& Rule.7 \\
&\implies\text{the itchy bear hugs 冠词 形容词 名词}& Rule.8 \\
&\implies\text{the itchy bear hugs the 形容词 名词}& Rule.10 \\
&\implies\text{the itchy bear hugs the jumpy 名词}& Rule.9 \\
&\implies\text{the itchy bear hugs the jumpy dog}& Rule.7 \\
\end{aligned}

这段例子中可以看到,文法用于在特定位置被单词替换,,箭头\implies代表了本次替换是依据上面的文法进行的,从句子作为初始符号,挨个应用上述的生成文法,并且一个一个的用更加“细致”的规则替换,比如“谓语”可以被替换为“动词+名词短语”,而“名词短语”又可以被替换为“名词”,然而到了“名词”这一步就卡住了,根据上述的10条规则,找不出任何可以替换“名词”的东西,我们把这种不能够再被进一步细化替换的单词(用单词说可能不太准确?)叫做终结符(terminal),而可以被进一步替换的叫做非终结符(nonterminal),在上述的例子中,只有所有的非终结符都被替换为终结符后,推导才算完成,而替换非终结符的过程叫做文法分析

在上面的例子中,可以注意到一种情况,那就是关于名词短语的分析,名词短语有三个不同的规则,其中有两个被应用以后还会出现一个新的名词短语,位于应用规则之后的最右端,这种应用规则之后新规则的最右侧符号是本身的情况本身被称为右递归,相对的,如果出现在最左侧就是左递归

根据上面的例子,也可以列出算术表达式的规则,用AE代表算术表达式的集合

\begin{aligned}
\text{Start}&\rightarrow(AE) \\
AE&\rightarrow(AE+AE) \\
AE&\rightarrow(AE-AE) \\
AE&\rightarrow(AE*AE) \\
AE&\rightarrow(AE/AE) \\
AE&\rightarrow(AE\verb!^!AE) \\
AE&\rightarrow(AE) \\
AE&\rightarrow-(AE) \\
AE&\rightarrow \text{ANY-NUMBER} \\
\end{aligned}

其中唯一的非终结符是AE,终结符是\text{ANY-NUMBER}和诸如+,-,*,/之类的符号,对于\text{ANY-NUMBER},虽然它的意思简直是不言而喻,但是很明显计算机是无法理解的,因此,也可以给出对应\text{ANY-NUMBER}的规则

\begin{aligned}
\text{ANY-NUMBER}&\rightarrow\text{FIRST-PART} \\
\text{FIRST-PART}&\rightarrow\text{FIRST-PART OTHER-PART} \\
\text{FIRST-PART}&\rightarrow\text{1,2,3,4,5,6,7,8,9} \\
\text{OTHER-PART}&\rightarrow\text{1,2,3,4,5,6,7,8,9,0}
\end{aligned}

注意\text{FIRST-PART}的第一条规则就是左递归的

上述例子里,从\text{FIRST-PART}可以派生出无限多个\text{OTHER-PART},就像

\begin{aligned}
\text{ANY-NUMBER}&\rightarrow\text{FIRST-PART} \\
\text{FIRST-PART}&\rightarrow\text{FIRST-PART OTHER-PART} \\
\text{FIRST-PART}&\rightarrow\text{FIRST-PART OTHER-PART OTHER-PART} \\
\text{FIRST-PART}&\rightarrow\text{FIRST-PART OTHER-PART OTHER-PART OTHER-PART} \\
&......
\end{aligned}

通过应用不同的规则来从初始符号生成由终结符构成的字符串的过程叫做推导(derivation)或者产生(generation),而这些语法规则一般被称为产生式规则(production rules),这些规则包含了所有可能的替换,推导过程不一定是唯一的,也就是对初始符号应用两种不同的产生规则可能会得到相同的结果。

生成文法的符号

  在上一节中,我们给出了几种不同的例子,这些例子中所涉及的结构和概念可以被统称为上下文无关文法(Context-Free Grammar),简称CFG,这种文法在1956年被诺姆·乔姆斯基所发明

定义
一个上下文无关文法(Context-Free Grammar),简称CFG,是一个四元组(\Sigma,V,R,S),其中

  1. 字母表\Sigma,其中的字符被称为终结符(terminals)
  2. 非终结符集合V,其中所有的元素都被称为非终结符(nonterminals)
  3. 初始符号S\in V,代表了推导过程的开始
  4. 产生式规则R,是一个V(V\cup\Sigma)^\ast的关系,一般拥有如下的形式
非终结符\rightarrow由有限多个终结符/非终结符构成的字符串

其中至少有一条规则要求S位于左侧,而规则右侧所谓“有限多个终结符/非终结符”意味可以仅由终结符组成,也可以仅由非终结符组成,也可以混合起来,甚至可以是空字符串

为了防止弄混终结符和非终结符,我们规定终结符一律用小写字母,而非终结符一律用大写字母

定义
由一个CFG生成的语言L(G)是所有能够从S出发经由产生式规则R推导出的由终结符构成的字符串的集合,被称为上下文无关语言(Context-Free Language),简称CFL,可以说G生成/推导/定义了语言L,记作L(G)

有一点需要注意的是\Lambda,如果\Lambda出现在产生式规则中,则它既不是非终结符,也不是终结符,比如对于规则

\begin{aligned}
S&\rightarrow SS \\
S&\rightarrow aS \\
S&\rightarrow\Lambda
\end{aligned}

可以有如下的推导过程

\begin{aligned}
S&\implies SS\\
&\implies SSS\\
&\implies SaS\\
&\implies \Lambda aS\\
&\implies \Lambda a\Lambda\\
&\implies a
\end{aligned}

虽然\Lambda本身不可以被任何非终结符或者终结符替换,但是他本身也并不是终结符,因为他可以从\Lambda a\Lambda中被消去,\Lambda在这里依然是一个特殊的存在,诸如如下的产生式

Nonterminals\rightarrow\Lambda

相当于直接删除掉这个非终结符

注意,\rightarrow代表产生式中的产生规则,而\implies代表一个根据产生式进行替换的过程

因此,诸如

\begin{aligned}
X&\rightarrow aX\\
X&\rightarrow bX\\
X&\rightarrow \Lambda
\end{aligned}

的产生式规则可以允许我们从非终结符X推导出任何字符串(\Sigma=\lbrace a,b\rbrace),也就是说,如果X出现在任何规则中,就可以应用这三条规则来将X转换成任意字符串
  虽然给出了数个CFG的例子,但是我们会发现在这些例子中,很多时候多个产生式的左侧都是同一个符号,而我们被迫去给每个规则都单独写一行,为了解决这个问题,可以引入符号|,一个竖线,我们使用S\rightarrow a|b来作为

\begin{aligned}
S&\rightarrow a\\
S&\rightarrow b
\end{aligned}

的缩写,这个竖线分隔开的部分是由左侧符号能推导出的所有字符串。除了这种形式以外,还有一些需要注意的部分,就是这种语法有多个变种,比如:

  1. ::=代表\rightarrow
  2. 把非终结符称作变元
  3. \epsilon\lambda来代替\Lambda
  4. 把非终结符用尖括号包裹起来,比如
    \begin{aligned}
    \langle S\rangle&\rightarrow\langle X \rangle | \langle Y\rangle\\
    \langle X\rangle&\rightarrow\Lambda \\
    \langle Y\rangle&\rightarrow a\langle Y\rangle|b\langle Y\rangle|a|b
    \end{aligned}

    这些变种都是通用的,我们把这种使用::=或者\rightarrow|以及“非终结符”和“终结符”表示CFG的范式叫做巴克斯-诺尔范式(Backus-Naur Form),简称BNF,这种范式被John W. Backus发明以描述语言ALGOL,事实上,绝大部分的编程语言,包括C/C#/Java/PASCAL/BASIC/FORTRAN,都可以被CFG定义,进而由BNF描述

  CFG能够定义正则语言和非正则语言,比如正则语言\text{EVEN-EVEN}(ab的出现次数都是偶数次的语言)就可以用如下方式定义

\begin{aligned}
S&\rightarrow SS|XS|SX|YSY|\Lambda\\
X&\rightarrow aa|bb\\
Y&\rightarrow ab|ba
\end{aligned}

而非正则语言\lbrace a^nb^n\rbrace则可以用如下CFG定义

\begin{aligned}
S&\rightarrow aSb|\Lambda
\end{aligned}

但是也有一些非正则语言是CFG无法定义的,比如{a^nbc^{n+1}},对于该语言,CFG无能为力

语法树

  我们可以用树形的图表来表示一个句子的结构,这样的树被称为语法树(Syntax Tree),每个CFG都可以用一个树形结构表示,其核心思想是从初始符号开始,每应用一个产生规则,都把其左侧的部分作为一个节点,右侧的每一个非终结符都作为一个子节点,按照从左到右的顺序递归向下的构建一颗树,直到所有非终结符都已经画上去为止,比如对于

\begin{aligned}
S&\rightarrow AA\\
AA&\rightarrow AAA|bA|Ab|a
\end{aligned}

如果依次应用S\implies AA\implies AAAbA\implies bAAbaba\implies babababa,就可以得到这样的一颗语法树

这张图其中的ab节点都不能再往下生成更多子节点了,因为他们都是终结符,这些节点被叫做叶子节点,所有的叶子节点都是终结符,所有的非叶子节点都是非终结符,把所有叶子节点代表的字符从左到右连接起来,就得到了由该CFG生成的一个字符串babababa。这种树的名字有许多种,包括语法树解析树生成树推导树等等,分别来自不同领域(语言学,编译器设计,数理逻辑)的术语

前缀标记法

  考虑一个算术表达式的CFG

S\rightarrow S+S|S*S|number

并且根据这个CFG生成一个字符串

3+4*5

现在,让我们来尝试理解一下,他到底代表7 * 5=35,还是3+20=23
尽管对于人类来说,理解这个表达式轻而易举,因为我们知道乘法运算的优先级高于加法,所以答案一定是后者,但是对于计算机来说,它并不知道这些,因此这个字符串对应的CFG就可能生成两种语法树,即如下两种之一

对这两棵树分别自底向上求值,可以得到两个不同的结果,注意在这两颗树中,操作数都位于操作符的两侧,这时候可以对树进行简化,让操作符变成树的节点,而操作数变成叶子节点,就变成了下面这样

在这种情况下,这棵树所对应的CFG就不再是原先的CFG了,根据树的结构可以发现+*都变成了非终结符(因为他们可以派生出别的符号),而终结符只剩下了数字一种,这棵树对应的CFG是这样的(使用带下划线的\underline{n}标明这是终结符number,代表数字的集合,因为现在没有大写字母作为非终结符了)

\begin{aligned}
S&\rightarrow *|+|\underline{n}\\
+&\rightarrow ++|+*|+\underline{n}|*+|**|*\underline{n}|\underline{n}+|\underline{n}*|\underline{n}\underline{n}\\
*&\rightarrow++|+*|+\underline{n}|*+|**|*\underline{n}|\underline{n}+|\underline{n}*|\underline{n}\underline{n}
\end{aligned}

让我们把眼光放回上面的两棵树,如果我们尝试自顶向下,从左到右的遍历这两棵树,那么对于左侧和右侧的,就会分别得到

\text{+ 3 * 4 5}\\
\text{* + 3 4 5}

两个表达式,观察不难发现这两个表达式是如何运算的,每当发现一个运算符的时候,就去找到运算符后面的两个运算数,再把这两个运算数应用到运算符上,如果发现运算数中的一个包含新的运算符,那么就重复这个过程,对于第一个表达式,这个过程就是先求\text{* 4 5}=20,然后算\text{+ 3 20=23},这样就用一种非常巧妙的方法省略掉了括号,还能保证逻辑清晰,流程明确,类似这种把运算符放在两个运算数前面的标记法叫做前缀标记法(Prefix notation),或者波兰标记法2,它是由波兰逻辑学家Lan Lukasiewicz所发明。在设计解释器的时候,通常会把中缀表达式转换为前缀表达式,然后采用一个栈来对其进行求值

二义性

  考虑CFG

\begin{aligned}
S&\rightarrow AB\\
A&\rightarrow a\\
B&\rightarrow B
\end{aligned}

如果要生成ab,那么显而易见的有两种不同的生成策略,第一种是S\implies AB\implies aB\implies ab,第二种是S\implies AB\implies Ab\implies ab,虽然应用产生式的先后顺序不同,但是如果画出对应的语法树,会发现他们的语法树是相同的,因此,无论按照什么顺序推导,该文法都是没有歧义的

定义
一个上下文无关文法G被称为是二义性(ambiguous)的,如果存在一个w\in L(G),使得w的两种不同产生规则可以构成两种不同的语法树

考虑CFG

S\rightarrow aS|Sa|a

仅仅是对于a^3,就存在四种不同的语法树

\begin{aligned}
S&\implies aS\implies aaS\implies aaa \\
S&\implies aS\implies aSa\implies aaa \\
S&\implies Sa\implies aSa\implies aaa \\
S&\implies Sa\implies Saa\implies aaa
\end{aligned}

分别给这四个过程画语法树的话,会发现每个都是不一样的(注意,画出来的语法树可能可以通过把叶子节点从左侧挪到右侧变得相同,但是在语法树里,这样的旋转是不允许的,在产生规则中位于左侧的符号在语法树中也必须位于左侧),因此该文法是二义性的

Total Language Tree

定义
给定一个CFG,从初始符号S开始作为根节点,自顶向下的构造一颗树,其中对树的每个节点应用对应其符号的所有产生规则,每个结果都会生成一个新的子节点,最终得到的树是该文法的Total Language Tree3,这棵树的大小可能是无限的

所有产生规则包含递归的CFG的Total language Tree都将会是无限的


  1. 该理论源自乔姆斯基 ↩︎
  2. Lisp语言使用的就是波兰标记法 ↩︎
  3. 不知道咋翻译了 ↩︎

江头未是风波恶,别有人间行路难