有限自动机只记住有限个状态之一,足以判断奇偶等性质。但嵌套结构提出不同的问题:哪个右括号匹配哪个左括号?文法可以递归描述这种结构。要严谨地使用描述,必须同时证明每个生成的字符串都有效,以及每个有效字符串都能生成。
另一个区别也很重要:语言是字符串的集合,分析树则解释某个字符串的结构。两个文法可以生成完全相同的字符串,却赋予它们不同数量的分析树。平衡括号提供了一个小例子,让我们完整证明正确性、歧义、确定性语法分析和计数之间的关系。
文法每次改写一个非终结符
定义 8.1.1
(上下文无关文法、推导与分析树)
上下文无关文法是四元组 : 是有限非终结符集合; 是与 不相交的有限终结符字母表; 是开始符号; 是有限产生式集合,每式为 ,其中 、。
一步推导将某次出现的 换成产生式右侧,周围符号保持不变。语言 包含所有从 经过有限步可得到的纯终结符字符串。空串为 ,长度是零,并不是额外的终结符。
分析树是记录产生式的有序树。内部非终结符的孩子依次拼出所选右侧。从左到右读取终结符叶子,得到该树生成的字符串。空产生式贡献空串,画图时可以用 叶子表示。
产生式左侧只有一个非终结符,所以无论它出现在哪里,都能使用相同规则,这就是“上下文无关”的含义。推导记录改写的先后顺序,分析树则记录嵌套结构。
先独立定义什么是平衡
定义 8.1.2
(平衡值与平衡字符串)
字母表只含 ( 和 )。对于前缀 ,定义平衡值
即左括号数减右括号数。令 包含所有每个前缀平衡值都非负、且最终 的字符串 。空串属于 。
反例模式
总数相等,不保证嵌套结构正确
())( 有两个左括号和两个右括号,最终平衡值为零。但前缀 ()) 的平衡值是 ,已经有一个右括号找不到可用的左括号。因此它不属于 。
(()()) 各个非空前缀的平衡值为 ,所以是平衡字符串。前缀条件和最终相等,缺一不可。
一个看起来自然的文法是
三条规则分别表示连接两个平衡字符串、包围一个平衡字符串、或者使用空串。这些操作保持平衡,但仅凭这个观察,仍然只证明了语言相等的一个方向。
命题 8.1.3
(第一个文法的可靠性)
生成的每个字符串都平衡:。
证明
(对分析树作归纳)
对有限分析树进行归纳。空产生式生成 ,满足条件。如果根使用 ,而子树生成平衡的 ,那么 的平衡值从 1 开始,读取 期间至少为 1,最后的右括号使它回到零。
如果根使用 ,两棵子树生成平衡的 。位于 内的前缀非负;读完 时平衡值为零,继续进入 的前缀就具有 对应的平衡值,最后仍为零。因此所有产生式保持该性质,。
首次归零,决定唯一分解
命题 8.1.4
(首次归零分解)
每个非空的 都有唯一的分解 ,其中 。显示的右括号是 的前缀平衡值首次回到零的位置,并且 与 都比 短。
证明
(在首次归零处分割)
取非空的 。它必须以 ( 开始,否则第一个前缀已经为 。最终平衡值为零,所以存在第一个正位置,使平衡值回到零。这个位置为右括号,从而分解为
显示的外层括号在首次归零处结束。内部的 平衡:它的前缀平衡值为 对应平衡值减一;首次归零之前,这些值都非负,而且 最终为零。后缀 从一个零平衡前缀之后开始,继承其余前缀条件,所以也平衡。
都比 短。首次归零的位置也保证了这个分解唯一:对任何满足 的分解 , 的每个前缀的平衡值都至少为 ,所以显示的右括号就是首次归零处。
概念视角几何
把平衡字符串看作高度路径
把 ( 看作上升一步,) 看作下降一步。于是 就是路径在前缀 之后的高度,而字符串属于 ,恰好当路径从不低于高度零并在高度零结束。在这幅图像中,首次归零就是路径第一次回到横轴,所以 把路径切成一道拱(即 的路径上移一步)以及随后 的路径。对这类路径计数,就是下面的递推式所解决的计数问题。
考虑
命题 8.1.5
(生成平衡字符串的两个文法)
设 如上,则 。
证明
(对字符串长度作强归纳)
对字符串长度进行强归纳。空串使用 。非空平衡字符串 有首次归零分解 。根据归纳假设,较短的平衡字符串 都可以从 推导。先使用 ,再代入两个推导,就生成 。
与前面相同的可靠性论证也证明 只生成平衡字符串,所以 。此外, 能用 模拟 的每个非空产生式,因此也生成全部平衡字符串。结合可靠性,得到 。
例题 8.1.6
(首次归零将嵌套部分与后缀分开)
(())() 的前缀平衡值为 。首次归零在第四位,所以 、。外层括号只包围第一个 (),第二个 () 属于后缀。
在 中,一个完整的最左推导为
每步都改写最左边尚存的非终结符。空产生式不可省略:它们终止最内层字符串和最后的后缀。
改写顺序不同,不一定代表歧义
定义 8.1.7
(有歧义的文法)
如果某个生成字符串具有两棵不同的分析树,文法就有歧义。等价地,这个字符串有两个不同的最左推导。仅找到两个任意推导是不够的,因为同一棵树可以按不同顺序展开。
常见错误
(不同的改写顺序不等于不同的树)
例如,在 进行 后,可以先展开内部非终结符,也可以先展开后缀。中间字符串可能不同,但仍然可以描述同一棵树。
例题 8.1.8
(有歧义文法中 () 的两棵树)
对 () 确实存在歧义。一棵树在根使用 ,内部使用空产生式。另一棵在根使用 ,左子树生成 (),右子树生成 。根产生式不同,就是同一字符串的两棵不同树。再连接更多空串,可以产生更多树,却没有新增终结符字符串。
命题 8.1.9
(首次归零文法没有歧义)
每个平衡字符串在 中恰有一棵分析树。
证明
(对字符串长度归纳)
对长度进行归纳。只有空产生式能生成空串,因为另一条规则会加入可见的一对括号,所以空串只有一棵树。
非空串的根必须使用 。如果两棵子树生成 ,可靠性保证它们平衡。因此,根产生式的右括号必定为整个字符串首次归零的位置。字符串本身已经唯一决定这个位置,以及 。
两者都更短,归纳假设分别给出唯一子树,所以整棵树唯一。 没有歧义,即使 以有歧义的方式生成完全相同的语言。
证明透视
为何首次归零决定整棵树
归纳假设只用在两个子树上,它们严格更短。容易漏掉的一步是根产生式被迫选定: 不生成任何符号,所以非空串必须以 开始。不显然的一步是把关于树的命题转为关于字符串的命题:无论给出哪棵树,其根产生式的右括号都位于平衡值首次归零之处,而该位置只由字符串本身决定。因此同一字符串的两棵树不可能有不同的 与 。同一论证对 失效,因为 没有这样的锚点:连接的分割点可以是任何平衡值为零的位置,而空产生式可以插入任何地方。
常见错误
(文法有歧义不等于语言有歧义)
因此,歧义是特定文法的性质。证明一个文法有歧义,不等于证明它的语言没有任何无歧义文法;本例的两个文法已经清楚展示了这个区别。
用下方固定平衡词示例比较:两种改写顺序描述同一棵首次归零树;歧义文法内的两棵不同树则见证歧义。
同一个串、唯一分解与不同分析树
检查前缀平衡及首次归零,按最左或最右顺序展开同一棵固定树,再在歧义文法中构造两棵真正不同的树。仅改写顺序不同,不足以证明歧义。
所选产生式: G1: S→(S)S | ε.
各前缀的平衡
只有整数前缀长度代表串。每步遇 ( 加1,遇 ) 减1,实线连接这些离散值。横线是零平衡,实心圆是所选前缀。非空平衡串的正方形标示首次正长度归零。结尾数量相同不能修补先前负平衡。
所选前缀: ε; 平衡: 0. 整个串的平衡: 0.
| 前缀长度 | 前缀串 | 平衡 |
|---|---|---|
| 0 | ε | 0 |
| 1 | ( | 1 |
| 2 | (( | 2 |
| 3 | (() | 1 |
| 4 | (()) | 0 |
| 5 | (())( | 1 |
| 6 | (())() | 0 |
唯一首次归零分解: w=(u)v; 内部 u=(); 剩余后缀 v=().
G1:唯一有序分析树
S 节点使用所示产生式,括号是终结叶。虚线 ε 叶表示空产出,不贡献终结符。子节点从左至右读;下方文字版保留完整有序层次。
分析树生成的串: (())(). 此树的有序文字版.
此树的有序文字版: G1:唯一有序分析树
- S→(S)S
- ( 左括号
- S→(S)S
- ( 左括号
- S→ε
- ε · 空产出
- ) 右括号
- S→ε
- ε · 空产出
- ) 右括号
- S→(S)S
- ( 左括号
- S→ε
- ε · 空产出
- ) 右括号
- S→ε
- ε · 空产出
每行替换有下划线的 S,位置从改写前字符串的1开始计。切换最左/最右保持同一棵树,可能改变中间形式;G1 空树在两种顺序都只有一次改写。
| 步 | 改写前 | 展开 S 的位置 | 产生式 | 改写后 |
|---|---|---|---|---|
| 1 | S | 1 | S→(S)S | (S)S |
| 2 | (S)S | 2 | S→(S)S | ((S)S)S |
| 3 | ((S)S)S | 3 | S→ε | (()S)S |
| 4 | (()S)S | 4 | S→ε | (())S |
| 5 | (())S | 5 | S→(S)S | (())(S)S |
| 6 | (())(S)S | 6 | S→ε | (())()S |
| 7 | (())()S | 7 | S→ε | (())() |
此处最左与最右都展开同一棵固定 G1 树,中间形式不同并不生成第二棵树。
- 此串平衡
- 是
- 所选前缀
- ε
- 平衡
- 0
- 整个串的平衡
- 0
- 首次负平衡前缀长度
- 没有
- 首次归零位置
- 4
- 所选文法的有限分析树数目
- 1
- 分析树生成的串
- (())()
每个前缀都非负,结尾平衡为零;此串具有所示分析结构。 平衡: 0; 整个串的平衡: 0. 所选文法的有限分析树数目: 1. 此树使用的 S 产生式次数: 7.
分开证明语言与分析树的结论
平衡串要求每个前缀的左括号不少于右括号,且结尾总数相等。())( 最后总数相等,但长度3前缀平衡为 −1,因此无效。(() 从不负平衡,结尾却为1,也无效。空串同时满足两个条件。
非空平衡串首符号是 (,之后首次归零的位置固定与它匹配的右括号,得 w=(u)v。在该归零前,外层内部平衡减1后仍非负;后缀从零重新开始,因此 u、v 都平衡且严格更短。首次归零唯一决定两者。使用 S→(S)S 再递归 u、v 就构造 G1 树,空串用 S→ε。
归纳亦证明唯一性。只有空产生式可生成空串。非空串的 G1 根必用 S→(S)S,子产出平衡迫使根的右括号正是首次归零。串先决定两个子产出,归纳再决定各自树。对 (())(),首次归零在位置4,u=()、v=(),与正文推导一致。先展开内部或先展开后缀,仅是在安排同一棵树的不同展开顺序。
G0 生成同一平衡语言:包围平衡串与连接平衡串都保留前缀条件,而首次归零构造可用其包围及连接规则表达。但它有歧义:() 的一棵树根用 S→(S),内部为空;另一棵根用 S→SS,将前树放左,右边加空树。结构不同但终结产出相同。所示 G0 见证将此构造一般化;不同 S 产生式次数保证是不同有限树。
歧义属于特定文法,不自动属于其语言。G0 可任意增加空后缀包装,因此每个平衡串有无穷多棵有限树;G1 却恰有一棵,两者生成的终结串集合不变。同样,Catalan 递推数平衡串,不是在数 G0 歧义树。本图在同一文法内比较真正不同的树作为见证,没有将两种文法的树不同本身当作歧义证明。
即时检查:G1 的两种改写顺序能否证明 G1 有歧义?
不能。歧义要求同一终结串有两棵不同有序分析树,等价于两个不同最左推导。同树的两个展开顺序不够;空串时两个顺序甚至相同。G0 见证结构真正不同,才证明歧义。
七个单一括号类型的固定短串,G1 首次归零树及 G0 的构造见证族,显示一至三层空包装。无穷性由任意延长构造证明,不是声称有限列表已完整。不实现任意文法分析、LR 表、PDA 执行或 Catalan 串枚举。
有限状态为什么不能记住所有深度
定理 8.1.10
(平衡字符串语言不是正则语言)
语言 不是正则语言:没有确定型有限自动机能识别它。
证明
(相同状态、相同后缀、相同答案)
假设某个具有 个状态的 DFA 识别 。考虑由 个左括号构成的前缀,其中 。共有 个前缀,必有两个长度为 的前缀到达相同状态。
对两者都接上恰好 个右括号。第一个字符串左右括号各 个,而且先左后右,因此平衡。第二个有 个左括号但只有 个右括号,并不平衡。
从同一状态读取同一后缀,DFA 必须给出相同接受结果,造成矛盾。因此 不是正则语言。这个论证对每个固定有限状态数都成立。
证明透视
有限性在碰撞论证的何处用到
有限性只用到一次,就是鸽笼步骤: 个前缀不可能到达 个互不相同的状态。不显然的一步是选择的次序:先固定由左括号组成的前缀,在知道碰撞的一对之后才选后缀,因此后缀依赖于 。论证之所以封闭,是因为 DFA 的未来行为只取决于当前状态,相同的状态无法区分 与 。去掉有限性,论证立即失效:计数器有无界多个取值,可以区分所有前缀 。
只有一类括号时,一个可以无界增长的非负计数器就能记录尚未匹配的左括号。下推自动机可以用栈高度表示同一个数量。这不违反 DFA 论证:计数器或栈可以随输入增长,DFA 的状态数却固定。如果有多类括号,仅记录高度还不足以核对类型。
判断成员资格,或者返回唯一结构
第一个函数检查独立的前缀定义。第二个实现 :None 表示空产生式,(inside, suffix) 表示 的两棵非终结符子树。因此返回 None 是空串的有效分析结果,而不是失败值。无效字符串会抛出 ValueError。
def is_balanced(text):
balance = 0
for symbol in text:
if symbol == "(":
balance += 1
elif symbol == ")":
balance -= 1
else:
return False
if balance < 0:
return False
return balance == 0
def parse_balanced(text):
position = 0
def parse_S():
nonlocal position
if position == len(text) or text[position] == ")":
return None
if text[position] != "(":
raise ValueError("expected opening parenthesis")
position += 1
inside = parse_S()
if position == len(text) or text[position] != ")":
raise ValueError("missing closing parenthesis")
position += 1
suffix = parse_S()
return (inside, suffix)
tree = parse_S()
if position != len(text):
raise ValueError("unmatched closing parenthesis")
return tree
每个终结符只被消耗一次;每个递归调用不是消耗一对括号,就是返回空子树。因此,分析时间相对于字符串长度为线性级,树和递归空间最坏也为线性级。这个教学实现在字符串很长时受 Python 递归深度限制。迭代的成员检查不需要递归,但计数器仍然需要足够多的位来表示当前深度,而不是固定的有限状态集合。
例题 8.1.11
(在两个无效字符串上运行解析器)
取 ())。位置 的 parse_S() 消耗 (;内层调用在位置 返回 None,因为 text[1] 是 );接着消耗右括号,位置 的后缀调用同样返回 None,因为 text[2] 是 )。此时已建出树 (None, None),但 position 是 而 len(text) 是 ,所以最后的检查会因右括号没有配对而抛出 ValueError。
取 (()。外层调用消耗第一个 (;内层调用消耗第二个 (,遇到 ),并建出 (None, None)。回到外层调用时,position 等于 len(text),所以检查右括号失败,ValueError 报告缺少右括号。相对地,parse_balanced("") 返回 None:这是空串的有效分析,不是错误。
用唯一分解计算字符串数量
命题 8.1.12
(平衡字符串的递推式)
令 为含 对括号的平衡字符串数。则 ,而当 时, 等于 时 之和。
证明
(以唯一的首次归零分解计数)
令 为含 对括号的平衡字符串数。空串只有一个,所以 。非空串 中,如果 含 对, 就含 对。分解唯一,因此不会遗漏或重复计数:
得到 、、、,即 Catalan 数的开头。
常见错误
(计算字符串不等于计算分析树)
这个公式计算不同字符串,而不是 的任意推导树;对有歧义的树计数会回答另一个问题。
有:这些数目就是 Catalan 数,而且每个数约为前一个的四倍。
自然的下一个问题
这些数目有公式吗?
有:这些数目就是 Catalan 数,而且每个数约为前一个的四倍。
这个递推式有封闭公式 ,可用其他方法证明。例如 、,与上面的数值相符。比值 趋近于 ,所以平衡字符串的数目大约按 增长,只差一个多项式因子。
练习与详解
快速检查
(同时检查两个平衡条件)
、(()())、())(、(() 中哪些平衡?对每个被拒绝的字符串,指出负平衡前缀或者非零的最终平衡值。
解答 · 答案
空串和 (()()) 平衡。())( 的前缀 ()) 平衡值为 ,即使整个字符串最终为零也无效。(() 没有负前缀,但最终为 1,仍有一个左括号未匹配。
快速检查
(找到唯一分解与分析树)
求 (())() 的首次归零分解。用 None 表示空子树、(inside, suffix) 表示非空子树,写出分析器返回的树。
解答 · 答案
首次归零在第四位,内部和后缀都为 (),分别有树 (None, None)。完整树为 ((None, None), (None, None)),根描述第一对外层括号以及剩余后缀。
快速检查
(区分歧义与改写顺序)
在 使用 后,两个推导以相反顺序展开两个非终结符,最后得到相同字符串和相同树。这是否证明歧义?什么样的一对例子才足够?
解答 · 答案
不够:它们只是按照不同顺序展开同一棵树。必须给出同一字符串的两棵不同分析树,或者两个不同的最左推导。首次归零的唯一性证明排除了 出现这样的例子。
快速检查
(展示真正歧义,而不改变语言)
对于 ,描述两种不同根产生式如何生成 ()。这是否证明平衡括号语言没有无歧义文法?
解答 · 答案
一棵树的根使用包围规则,内部为空。另一棵根使用连接,左侧生成 ()、右侧为空。根规则不同,证明两棵树不同。但 是同一语言的无歧义文法,所以不能从 有歧义推断语言没有无歧义描述。
快速检查
(从相同 DFA 状态推出矛盾)
如果两个和五个左括号的前缀到达同一 DFA 状态,接上哪个共同的右括号后缀,可以使一个属于平衡语言而另一个不属于?为什么 DFA 仍然必须给出相同答案?
解答 · 答案
接上两个右括号。第一个字符串平衡,第二个仍有三个未匹配的左括号。DFA 的后续行为只依赖当前状态,所以相同状态再读取相同后缀,接受结果必须相同,不能同时识别正确。
快速检查
(计算字符串,而不是有歧义的树)
从 用递推式求 ,并列出 的五个字符串。为什么这不是 的分析树数量?
解答 · 答案
。五个三对字符串为 ((()))、(()())、(())()、()(())、()()()。它们是不同的终结符字符串; 对同一字符串可以有多棵树,包括额外连接空串的树,因此树数不等于这个字符串数。