语法分析(1):编程语言不是正则的?

本文是本人撰写的编译原理讲义，适用于：被强迫学习编译原理前端，或者希望弄明白如何做科研的人

在一小时的会议中，已经实现妥当的词法分析器为甲方乙方带来了良好的讨论氛围。对于未知的语法分析，大家都很乐观，觉得他们也就具有细微的差别。只要照着词法分析器的经验，马上就可以成功。

“……那就先这么愉快地决定了，咱们先基于词法分析实现基本的条件语句，做个demo，让查总看看效果，回头再决定下一步开发计划。今天辛苦大家了，散会！”

开开心心回到工位，打开编辑器，开始了推理：

首先，条件语句就是if else。

既然之前词法可以通过A->abc| dA描述，那么条件语句的解析本身也是和状态相关的，尝试用正则文法进行描述：

假定if作为关键词被识别出来后，应进入到等待条件的状态，由此得到第一条式子

S->if A

然后，A可能是一个表达式。Emm，表达式很复杂，这里先用常数代替，应该差不多吧？那就有第二、三条式子：

A->(B B->d)C | dB

然后，C就要接着条件为真的一堆指令了，用花括号包裹，每条指令要用分号间隔，并且这些指令可能会嵌套回if本身，那么就有：

C->then{ D 
D->S | X | Y | }E //X和Y为简单读写指令 
X->read I  
Y->write I  
I -> [a-zA-Z_]I  
I->[a-zA-Z_0-9]I | [a-zA-Z_0-9];D 
E->else { F | ε //可能没有或分支 
F->S | X | Y | }

等一下，现在怎么指定S后面要跟着一个D？？新开一个S'，让这个序列的最后肯定会跟着D？

D->S' | X | Y | }E //修改D的产生式 
S'->if A' A'->(B' 
B'->d)C'|dB' 
C'->then{ D' 
D'->S' | X' | Y' | }E' 
X'->read I'   
Y'->write I'  
I' -> [a-zA-Z_]I'  
I'->[a-zA-Z_0-9]I' | [a-zA-Z_0-9];D'  
E'->else { F' | D 
F'->S' | X' | Y' | }D

有种屎山代码即将喷涌而出的不翔预感。。

等一下！！！！

F'->S'这里，S' 最多就只能确保后面紧接着一个D，但这里F'生成的应该是确保S'后面紧接着一个D'！这么说来，这条式子就要改成F'->S'' | X' | Y' | }D。然后S''又会生成新的S'''....子子孙孙无穷匮也！！！！！

一瞬间，王多鱼他二奶阴森着脸的场面在脑海中浮现，整个人如坠冰窟：

这么说来，if的嵌套，可能根本无法用正则文法表示？？

不会的吧？？我还想着明天交货呢。可能是哪里推错了，我再努努力。。。。

（一晚上过去）

失败了失败了失败了。待会儿怎么面对老板？

到底是我能力不行，还是说这个东西确实不能用正则文法描述？这能证明出来吗？？

那等一下，先把if else的嵌套化简成花括号的嵌套。

毕竟if else 嵌套的核心是一层套一层，如果正则连花括号的嵌套都搞不定，if else 更没戏。

那么，先假设识别花括号嵌套的正则文法存在，那么必然存在一个DFA可以识别if嵌套语句。

然后DFA的全称是确定性有限状态自动机，里面的状态有限。

由于符号只有左右花括号，那么每个状态最多只能指出去两个箭头。

如果只有一对花括号，那么自然是先从开始态到中间态A1再到接受态；

如果有两对花括号嵌套，那么自然应该是读了一个左花括号之后到了A1，之后再读一个到A2。回头读了一个右就回到A1，之后再到接受态。

那如果，嵌套的花括号数量未知。。。那状态的数量终究是有限的，因此处理不了嵌套层数未知的序列？？？

这不是证明，冷静。。我应该这么说：

• 假定嵌套括号序列是正则语言，

• 那么说明存在一台DFA，可以完美识别任意深度的花括号嵌套。

• DFA的定义是“有限状态自动机”，所以，它的状态数量必然是有限的，假设为 N 个。

• 当DFA读取前面的左括号 { 时，它每读一个，状态就会跳转一次；如果读入右括号 }  ，它就会回到上一个状态去。

• 现在，我构造一个有 N+1 层嵌套的输入串：{{{{...}}}} (总共 N+1 个 { 和 N+1 个 })。

• 当我们输入前N个花括号，状态会在原有的N个不同的状态中来回跳转。

• 另外已知“鸽巢原理”，也就是N+1只鸽子放到N个笼子中至少会有一个笼子会有2只或以上的鸽子。

• 在我们的场景中，输入的 { 就是“鸽子”。在输入前面N个左花括号的时候，为了可以在匹配到相应的右花括号后可以到达终态，这N个左花括号必然会导致状态机在N个不同的状态中跳转。

• 当输入第N+1个花括号的时候，相当于N+1只鸽子要放进 N 个“鸽巢”（DFA的状态）里，那么必然至少有两个不同的前缀，比如M个{ 和 N+1个{会进入到同一个状态S_k中！

• 那么对于这个状态，无论是我输入M个还是N+1个右花括号，都会导致DFA进入终态。

• 而前者，是不合法的序列，说明这个DFA不能只识别任意深度的花括号嵌套，存在矛盾！

• 所以，最开始的假设存在错误，嵌套括号序列不是正则语言。QED！

换句话来说，机器停在状态 S_k 时，它已经无法分清自己是处在“第M层嵌套”，还是“第N+1层嵌套”了。既然它已经忘了自己欠了几个左括号，当后面 } 开始出现时，它又怎么可能“准确对应”上正确的数量呢？！

由于任何的嵌套都可以简化成上面的花括号嵌套，所以，只要出现嵌套，那么这个语言就必然不是正则语言，也就不能用正则文法描述？？？？？！！！！！

旁白：主角好像证出了不得了的东西。欲知后事如何，且听下回分解。

PS：强行更新一章，免得自己都不敢跨过这条起跑线了。