语法分析(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 | }

等一下，在真分支中，当D->S之后，要如何指定S后面要跟着一个D从而紧跟}E进入假分支？？

难道是新开一个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个状态，对长度超过N的{序列A，会和长度少于N的{序列B落在相同状态中

• 为B序列接上和B等长的}序列，容易知道该序列为合法序列

• 由假定可知，我们的DFA接受上述序列

• 然而，当A序列接上同等串后，由于左括号序列会落在和B序列相同的状态上，此事处理后续右括号序列将使得其行为和DFA处理上述扩展的B序列完全一致

• 由于A序列中左括号数量不等于接上的右括号数量

• 最终使得DFA接受该不合法串。QED！

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

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

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

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