动机
上下文无关文法描述了字符串可以如何构造,但分析器必须在读入输入的同时决定使用哪条产生式。预测分析器只借助一个前瞻符号做出这一选择,既不先猜测、也不回退重来。核心困难来自空产生式:若某个非终结符可以消失,下一个输入符号就可能来自它后面的内容,而不是来自该非终结符本身。
FIRST 集与 FOLLOW 集把这两种前瞻来源区分开来。我们将构造 LL(1) 分析表,证明分析成功的确切含义,并说明为什么冲突只是针对某个具体文法的警告,而不是证明该语言不可能用其他方式分析。
定义
设 G = ( N , Σ , P , S ) G=(N,\Sigma,P,S) G = ( N , Σ , P , S ) 为有限上下文无关文法。假设 N N N 与 Σ \Sigma Σ 不相交,S ∈ N S\in N S ∈ N ,且 # \# # 是文法字母表之外的新结束标记。假设每个非终结符都从 S S S 可达,并且至少推导出一个终结符串;这一约化文法假设使下文的语义集合与标准的局部不动点规则一致。语言为空的文法不满足该假设,因为其开始符号不是可产生的(productive);本章不对这种情形断言不动点结论。当开始符号仍可产生时,通常的有用符号预处理可以删去不可产生和不可达的符号,但我们明确以所得的假设为前提。
文法符号串 α ∈ ( N ∪ Σ ) ∗ \alpha\in(N\cup\Sigma)^* α ∈ ( N ∪ Σ ) ∗ 称为可空的 (nullable),若 α ⇒ ∗ ε \alpha\Rightarrow^*\varepsilon α ⇒ ∗ ε 。定义 FIRST ( α ) \operatorname{FIRST}(\alpha) FIRST ( α ) 为:包含每个能作为 α \alpha α 所推导的终结符串之首的终结符,并且当 α \alpha α 可空时还包含 ε \varepsilon ε 。
对非终结符 A A A ,若对某些文法符号串 μ , ν \mu,\nu μ , ν 有 S ⇒ ∗ μ A a ν S\Rightarrow^*\mu A a\nu S ⇒ ∗ μ A a ν ,则终结符 a a a 属于 FOLLOW ( A ) \operatorname{FOLLOW}(A) FOLLOW ( A ) 。若 S ⇒ ∗ μ A ν S\Rightarrow^*\mu A\nu S ⇒ ∗ μ A ν 且 ν \nu ν 可空,则 # \# # 属于 FOLLOW ( A ) \operatorname{FOLLOW}(A) FOLLOW ( A ) 。等价地说,在某个句型中,若 A A A 的某次出现之后可以接以 a a a 开头的终结符延续,则该 a a a 在 FOLLOW 中;结束标记则记录了该次出现可能是输入的最后来源。
分析表的每个非终结符对应一行,每个终结符及 # \# # 各对应一列。对每条产生式 A → α A\to\alpha A → α ,对每个终结符 a ∈ FIRST ( α ) a\in\operatorname{FIRST}(\alpha) a ∈ FIRST ( α ) ,把该产生式放入 M [ A , a ] M[A,a] M [ A , a ] 。若 ε ∈ FIRST ( α ) \varepsilon\in\operatorname{FIRST}(\alpha) ε ∈ FIRST ( α ) ,还要对每个 b ∈ FOLLOW ( A ) b\in\operatorname{FOLLOW}(A) b ∈ FOLLOW ( A ) ,把它放入 M [ A , b ] M[A,b] M [ A , b ] 。单元格可以留空。冲突是指某个单元格含有两条不同的产生式;同一条产生式被放入两次不构成冲突。
概念视角 结构
无冲突即两项互斥检验 对化简后的文法,分析表无冲突,当且仅当对每个有产生式 A → α 1 ∣ ⋯ ∣ α m A\to\alpha_1\mid\cdots\mid\alpha_m A → α 1 ∣ ⋯ ∣ α m 的 A A A ,下列两个条件成立。第一,当 i ≠ j i\ne j i = j 时 FIRST ( α i ) ∩ FIRST ( α j ) = ∅ \operatorname{FIRST}(\alpha_i)\cap\operatorname{FIRST}(\alpha_j)=\varnothing FIRST ( α i ) ∩ FIRST ( α j ) = ∅ ,其中 ε \varepsilon ε 也算作成员。第二,若 α i \alpha_i α i 可空,则对每个 j ≠ i j\ne i j = i 都有 FIRST ( α j ) ∩ FOLLOW ( A ) = ∅ \operatorname{FIRST}(\alpha_j)\cap\operatorname{FOLLOW}(A)=\varnothing FIRST ( α j ) ∩ FOLLOW ( A ) = ∅ 。这分别是 FIRST/FIRST 与 FIRST/FOLLOW 检验,每次失败都指出相互碰撞的那一对产生式。
定理
对每条产生式 A → α B β A\to\alpha B\beta A → α B β ,FIRST ( β ) \operatorname{FIRST}(\beta) FIRST ( β ) 中的每个终结符都属于 FOLLOW ( B ) \operatorname{FOLLOW}(B) FOLLOW ( B ) 。若 β \beta β 可空,则 FOLLOW ( A ) \operatorname{FOLLOW}(A) FOLLOW ( A ) 的每个成员也属于 FOLLOW ( B ) \operatorname{FOLLOW}(B) FOLLOW ( B ) 。结束标记属于 FOLLOW ( S ) \operatorname{FOLLOW}(S) FOLLOW ( S ) 。
因为 A A A 可达,对某些符号串 μ , ν \mu,\nu μ , ν 有 S ⇒ ∗ μ A ν S\Rightarrow^*\mu A\nu S ⇒ ∗ μ A ν ,再用产生式 A → α B β A\to\alpha B\beta A → α B β 得到 S ⇒ ∗ μ α B β ν S\Rightarrow^*\mu\alpha B\beta\nu S ⇒ ∗ μα B β ν 。若终结符 a ∈ FIRST ( β ) a\in\operatorname{FIRST}(\beta) a ∈ FIRST ( β ) ,则对某个符号串 γ \gamma γ 有 β ⇒ ∗ a γ \beta\Rightarrow^*a\gamma β ⇒ ∗ aγ ,所以 S ⇒ ∗ μ α B a γ ν S\Rightarrow^*\mu\alpha B a\gamma\nu S ⇒ ∗ μα B aγ ν ,即 a ∈ FOLLOW ( B ) a\in\operatorname{FOLLOW}(B) a ∈ FOLLOW ( B ) 。
现设 β \beta β 可空。若 a ∈ FOLLOW ( A ) a\in\operatorname{FOLLOW}(A) a ∈ FOLLOW ( A ) ,例如 S ⇒ ∗ μ ′ A a ν ′ S\Rightarrow^*\mu' A a\nu' S ⇒ ∗ μ ′ A a ν ′ ,则 S ⇒ ∗ μ ′ α B β a ν ′ ⇒ ∗ μ ′ α B a ν ′ S\Rightarrow^*\mu'\alpha B\beta a\nu'\Rightarrow^*\mu'\alpha B a\nu' S ⇒ ∗ μ ′ α B β a ν ′ ⇒ ∗ μ ′ α B a ν ′ ,因为 β \beta β 消失;所以 a ∈ FOLLOW ( B ) a\in\operatorname{FOLLOW}(B) a ∈ FOLLOW ( B ) 。若 # ∈ FOLLOW ( A ) \#\in\operatorname{FOLLOW}(A) # ∈ FOLLOW ( A ) ,即 S ⇒ ∗ μ ′ A ν ′ S\Rightarrow^*\mu' A\nu' S ⇒ ∗ μ ′ A ν ′ 且 ν ′ \nu' ν ′ 可空,则 β ν ′ \beta\nu' β ν ′ 可空,并且 S ⇒ ∗ μ ′ α B β ν ′ S\Rightarrow^*\mu'\alpha B\beta\nu' S ⇒ ∗ μ ′ α B β ν ′ ,所以 # ∈ FOLLOW ( B ) \#\in\operatorname{FOLLOW}(B) # ∈ FOLLOW ( B ) 。最后,S ⇒ ∗ S S\Rightarrow^*S S ⇒ ∗ S (μ \mu μ 与 ν \nu ν 皆为空),这使 # \# # 属于 FOLLOW ( S ) \operatorname{FOLLOW}(S) FOLLOW ( S ) 。
该规则对各次出现分别处理:一个非终结符可以有多种不同的上下文,其 FOLLOW 集是这些上下文所给集合的并集。
集合的计算
可空非终结符通过最小不动点获得。起初没有任何标记。反复进行如下操作:若某条产生式 A → X 1 ⋯ X k A\to X_1\cdots X_k A → X 1 ⋯ X k 的每个 X i X_i X i 都已被标记为可空,则标记 A A A ;空的右部立即满足条件。含有终结符的右部不可能是可空的。由于非终结符只有有限多个,这一过程必然停止。
计算 FIRST 时,若某终结符能作为 A A A 的某条产生式右部之首,就把它加入 FIRST ( A ) \operatorname{FIRST}(A) FIRST ( A ) 。从左到右扫描右部:加入每个符号 FIRST 中的非空终结符,仅当该符号可空时才继续越过它。当右部每个符号都可空时,加入 ε \varepsilon ε 。重复直到没有集合再增大,就得到最小不动点。对终结符 a a a ,FIRST ( a ) = { a } \operatorname{FIRST}(a)=\{a\} FIRST ( a ) = { a } ;空串的 FIRST 集为 { ε } \{\varepsilon\} { ε } 。
计算 FOLLOW 时,从 # ∈ FOLLOW ( S ) \#\in\operatorname{FOLLOW}(S) # ∈ FOLLOW ( S ) 出发,对每个右部中每个非终结符的出现反复应用传播定理。永远不要把 ε \varepsilon ε 放入 FOLLOW 集。每个集合都是有限集 Σ ∪ { # } \Sigma\cup\{\#\} Σ ∪ { # } 的子集,所以不动点计算会终止。最小不动点恰好包含由有限推导所证成的符号:每次插入都有推导见证,而对有限推导作归纳可知,每个应当出现的符号最终都会被插入。
解读不动点计算
把各轮计算与最终结果区分开来会有帮助。考虑 A → B C A\to BC A → B C ,B → ε ∣ b B\to\varepsilon\mid b B → ε ∣ b ,C → ε ∣ c C\to\varepsilon\mid c C → ε ∣ c 。第一轮可空性计算因 B B B 、C C C 各有一条空产生式而标记二者;下一轮即可标记 A A A 。于是 A A A 的 FIRST 同时含有 b b b 与 c c c (因为 B B B 可以消失),并含有 ε \varepsilon ε (因为两个组成部分都可以消失)。若 A A A 是开始符号,则其 FOLLOW 含有结束标记。对 B B B 的这次出现,规则把 c c c 与结束标记加入 FOLLOW ( B ) \operatorname{FOLLOW}(B) FOLLOW ( B ) ;而 C C C 得到结束标记。
应当持续计算直到不可能再有变化,而不是在固定遍数后停止。一条产生式链可能涉及许多非终结符,一端的信息可能需要经过若干轮才能传到另一端。终止性来自有限且只增不减的集合,而不是来自“两遍”之类预先规定的数字。反过来,若仅因某终结符出现在产生式后面某处就把它加入 FIRST,则当前面的某个不可空符号将其挡住时,会高估 FIRST。传播的方向以及对可空前缀的条件都很重要。
预测分析器
初始化栈:S S S 在 # \# # 之上;输入为该符号串后接 # \# # 。反复检查栈顶符号与当前输入符号。若二者是相同的终结符,则同时移除并推进输入。若栈顶是非终结符 A A A ,则对当前输入符号 a a a 查表 M [ A , a ] M[A,a] M [ A , a ] 。若其中有产生式 A → X 1 ⋯ X k A\to X_1\cdots X_k A → X 1 ⋯ X k ,就移除 A A A ,并把右部按逆序压栈,使 X 1 X_1 X 1 位于栈顶;若右部为空,则不压入任何符号。空单元格或终结符不匹配则报告失败。当栈与输入都只剩 # \# # 时接受。
在我们的跟踪记录中,栈的书写方式是栈顶在左。例如,把栈顶 A A A 替换为 B C BC B C ,会使栈 A γ # A\gamma\# A γ # 变为 B C γ # BC\gamma\# B C γ # 。只有在前面所有终结符都已匹配之后,才展开最左的待处理非终结符。因此,分析器所做的产生式选择描述的是一个最左推导。
证明
可靠性与完备性
若分析表没有冲突,则上文所述的栈式分析器恰好接受 G G G 所生成的终结符串。对每个被生成的符号串,分析器在有限步内到达接受状态。对于不在语言中的输入,接受永远不会发生;这里并不断言分析器对每个这样的输入都会终止。
关于可靠性,维持如下不变量:已消耗的输入后接栈中的文法符号部分,是一个由 S S S 推导出的句型。产生式步骤对最左的待处理非终结符应用所指示的文法规则;匹配步骤把栈顶终结符转移到已消耗的前缀中,而二者的连接结果不变。当两个结束标记都到达时,栈中已没有文法符号。因此已消耗的输入是由 S S S 推导出的终结符串。
关于完备性,固定一个被生成的符号串及其一个有限的最左推导。假设分析器到目前为止一直沿着该推导进行。若栈顶符号是终结符,则它等于下一个输入终结符。若栈顶是非终结符 A A A ,并且在所选推导中由 A → α A\to\alpha A → α 展开,则有两种情形:要么剩余输入以 α \alpha α 所生成的某个终结符开头,要么 α \alpha α 推导出 ε \varepsilon ε ,而前瞻符号来自 A A A 这次出现之后的延续部分(也可能是 # \# # )。在第一种情形中,该产生式是依据 FIRST 插入表中的;在第二种情形中,是依据 FOLLOW 插入的。分析表没有冲突,所以分析器选中的正是这条产生式。沿着该有限推导作归纳,即可一直到达接受。
这一论证并不要求断言任意表驱动计算在每个被拒绝的输入上都会终止。它证明的是:每个成员都有一个有限的成功计算,并且由于分析表是确定性的,分析器恰好沿着它进行。因此在所述假设下,任何报告的失败都是正确的拒绝。若要另外证明对所有非成员的最坏运行时间或终止保证,则需要对文法和实现作额外分析。
证明透视
前瞻符号从何而来? 完备性论证是对栈顶符号的分情形讨论。栈顶是终结符时不需要查表:推导已决定了它,而输入与之吻合。栈顶是非终结符 A A A ,并由 A → α A\to\alpha A → α 展开时,再依当前前瞻符号 a a a 分情形。若 a a a 是 α \alpha α 所推导符号串之首,则 a ∈ FIRST ( α ) a\in\operatorname{FIRST}(\alpha) a ∈ FIRST ( α ) ,单元格 M [ A , a ] M[A,a] M [ A , a ] 由 FIRST 规则填入。若在所选推导中 α ⇒ ∗ ε \alpha\Rightarrow^*\varepsilon α ⇒ ∗ ε ,则 a a a 来自 A A A 这次出现之后的内容,所以 a ∈ FOLLOW ( A ) a\in\operatorname{FOLLOW}(A) a ∈ FOLLOW ( A ) ,单元格由 FOLLOW 规则填入;这时 a a a 也可以是 # \# # 。两种情形涵盖所有可能,这就是两个集合都不可缺少的原因。
假设在三处被使用。约化文法假设使这里用到的语义 FOLLOW 与不动点所算出的集合一致。无冲突这一假设只在最后使用一次:它把“正确的产生式在单元格内”变成“正确的产生式是单元格内唯一的一条”。没有它,表中仍可含有每个正确的选择,但分析器无从知道该选哪一个。对 S → A a S\to Aa S → A a 、A → a ∣ ε A\to a\mid\varepsilon A → a ∣ ε 与输入 a a a ,单元格 M [ A , a ] M[A,a] M [ A , a ] 含有两条产生式,若分析器选择 A → a A\to a A → a ,便会在 # \# # 处失败,尽管 a a a 是被生成的。最后,归纳沿着一条固定的有限推导进行,所以成功的运行自然是有限的。
例题详解
设 S → A b S\to Ab S → A b 且 A → a ∣ ε A\to a\mid\varepsilon A → a ∣ ε 。则 A A A 可空,FIRST ( A ) = { a , ε } \operatorname{FIRST}(A)=\{a,\varepsilon\} FIRST ( A ) = { a , ε } ,FOLLOW ( A ) = { b } \operatorname{FOLLOW}(A)=\{b\} FOLLOW ( A ) = { b } 。分析表为 M [ S , a ] = M [ S , b ] = S → A b M[S,a]=M[S,b]=S\to Ab M [ S , a ] = M [ S , b ] = S → A b ,M [ A , a ] = A → a M[A,a]=A\to a M [ A , a ] = A → a ,M [ A , b ] = A → ε M[A,b]=A\to\varepsilon M [ A , b ] = A → ε 。没有单元格冲突。该语言为 { b , a b } \{b,ab\} { b , ab } 。
对输入 a b # ab\# ab # ,栈/输入对依次开始于 S # / a b # S\#/ab\# S #/ ab # ,然后是 A b # / a b # Ab\#/ab\# A b #/ ab # ,再然后是 a b # / a b # ab\#/ab\# ab #/ ab # 。匹配 a a a 与 b b b 后到达 # / # \#/\# #/# 。对输入 b # b\# b # ,表项 M [ A , b ] M[A,b] M [ A , b ] 选择空产生式,并允许同样的最终匹配。
对 S → a b ∣ a c S\to ab\mid ac S → ab ∣ a c ,两个右部的 FIRST 集都是 { a } \{a\} { a } ,所以 M [ S , a ] M[S,a] M [ S , a ] 含有两条产生式。仅凭当前前瞻符号,分析表无法在二者之间做出选择。提取左公因子得到 S → a T S\to aT S → a T 与 T → b ∣ c T\to b\mid c T → b ∣ c ,就为同一语言给出了无冲突的分析表。可见原来的表冲突涉及的是所给的文法,而不是正则语言 { a b , a c } \{ab,ac\} { ab , a c } 本身。
例题 3.2.8
(FIRST/FOLLOW 冲突)
设 S → A a S\to Aa S → A a 且 A → a ∣ ε A\to a\mid\varepsilon A → a ∣ ε 。因为 a ∈ FOLLOW ( A ) a\in\operatorname{FOLLOW}(A) a ∈ FOLLOW ( A ) ,单元格 M [ A , a ] M[A,a] M [ A , a ] 既从 FIRST 得到 A → a A\to a A → a ,又从 FOLLOW 得到 A → ε A\to\varepsilon A → ε 。看到第一个 a a a 时,一个前瞻符号无法区分它属于 A A A 还是属于后面的终结符。该语言是 { a , a a } \{a,aa\} { a , aa } ,这再次说明文法冲突并不意味着语言本身难以分析。
对 S → A B C S\to ABC S → A B C ,A → a A\to a A → a ,B → b ∣ ε B\to b\mid\varepsilon B → b ∣ ε ,C → c ∣ ε C\to c\mid\varepsilon C → c ∣ ε ,B B B 与 C C C 都可空。因此 B C BC B C 的 FIRST 含有 b , c , ε b,c,\varepsilon b , c , ε 。FOLLOW 规则把 b b b 与 c c c 放入 FOLLOW ( A ) \operatorname{FOLLOW}(A) FOLLOW ( A ) ;因为整个后缀 B C BC B C 可空,它还把 # \# # 放入其中。若只看紧邻的非终结符 B B B ,就会漏掉终结符 c c c 和结束标记。
反例模式
分析表冲突并不证明语言不可能被分析 断言:若某文法的分析表有冲突,则该语言不可能用一个前瞻符号做确定性分析。对 S → a b ∣ a c S\to ab\mid ac S → ab ∣ a c ,单元格 M [ S , a ] M[S,a] M [ S , a ] 含有两条产生式,所以分析表有冲突。然而语言 { a b , a c } \{ab,ac\} { ab , a c } 是有限的,而提取公因子后的文法 S → a T S\to aT S → a T 、T → b ∣ c T\to b\mid c T → b ∣ c 有 M [ S , a ] = S → a T M[S,a]=S\to aT M [ S , a ] = S → a T 、M [ T , b ] = T → b M[T,b]=T\to b M [ T , b ] = T → b 、M [ T , c ] = T → c M[T,c]=T\to c M [ T , c ] = T → c ,没有任何单元格含有两条产生式。冲突表明的是:这个文法以及这种单符号前瞻的表构造无法做出所需的确定性选择;它并不表明该语言的每个文法都会冲突。
常见错误
一个符号串的 FIRST 并不简单等于该串中各符号的 FIRST 集之并。只有当前面所有符号都消失时,后面的符号才可能成为所推导符号串之首。在 A b Ab A b 中,若 A A A 可空且 FIRST ( A ) = { a , ε } \operatorname{FIRST}(A)=\{a,\varepsilon\} FIRST ( A ) = { a , ε } ,则 FIRST ( A b ) = { a , b } \operatorname{FIRST}(Ab)=\{a,b\} FIRST ( A b ) = { a , b } ;空串不在该集合中,因为终结符 b b b 仍然保留。
常见错误
(FOLLOW 不是 FIRST,# 也不是空串)
FOLLOW 描述的是某次出现之后可能出现的符号,而不是该非终结符自身所生成的符号。应当把可空产生式放入 FOLLOW 对应的列,但不要把 ε \varepsilon ε 加为分析表的一列。结束标记与空串不同:它是一个记账用的符号,表示已无剩余输入。
无冲突的分析表可以含有空单元格。它们是有用的:若分析器到达空单元格,则依据正确性定理,该前瞻符号不可能开启任何成功的延续。把任意规则填入空单元格,可能使分析器出错。
总结
可空性信息控制 FIRST 在右部中向后扫描的范围。FOLLOW 则在可空展开之后提供前瞻符号。无冲突的分析表能确定性地选择产生式;栈不变量证明可靠性,有限的最左推导则证明对每个成员的完备性。表冲突属于所选的文法和前瞻构造,所以等价的文法变换可以消除某些冲突。
练习
快速检查
(对 S → a S ∣ ε S\to aS\mid\varepsilon S → a S ∣ ε ,计算 FIRST ( S ) \operatorname{FIRST}(S) FIRST ( S ) 与 FOLLOW ( S ) \operatorname{FOLLOW}(S) FOLLOW ( S ) ,并给出两个非空的表单元格。)
解答 · 答案 FIRST ( S ) = { a , ε } \operatorname{FIRST}(S)=\{a,\varepsilon\} FIRST ( S ) = { a , ε } ,FOLLOW ( S ) = { # } \operatorname{FOLLOW}(S)=\{\#\} FOLLOW ( S ) = { # } 。单元格 M [ S , a ] M[S,a] M [ S , a ] 含有 S → a S S\to aS S → a S ,M [ S , # ] M[S,\#] M [ S , # ] 含有 S → ε S\to\varepsilon S → ε 。
快速检查
(对 S → A B S\to AB S → A B ,A → a ∣ ε A\to a\mid\varepsilon A → a ∣ ε ,B → b ∣ ε B\to b\mid\varepsilon B → b ∣ ε ,计算 FIRST ( S ) \operatorname{FIRST}(S) FIRST ( S ) 与 FOLLOW ( A ) \operatorname{FOLLOW}(A) FOLLOW ( A ) 。)
解答 · 答案 A A A 与 B B B 都可空,所以 FIRST ( S ) = { a , b , ε } \operatorname{FIRST}(S)=\{a,b,\varepsilon\} FIRST ( S ) = { a , b , ε } 。A A A 之后的后缀是 B B B ,其非空 FIRST 含有 b b b 且 B B B 可空;因此 FOLLOW ( A ) = { b , # } \operatorname{FOLLOW}(A)=\{b,\#\} FOLLOW ( A ) = { b , # } 。
快速检查
(解释 S → a ∣ a S S\to a\mid aS S → a ∣ a S 中的冲突,并给出一个等价的无冲突文法。)
解答 · 答案 两个选择都以 a a a 开头,所以 M [ S , a ] M[S,a] M [ S , a ] 含有两条产生式。文法 S → a T S\to aT S → a T ,T → a T ∣ ε T\to aT\mid\varepsilon T → a T ∣ ε 生成同一语言 a + a^+ a + ,并且表中的选择互不相交:遇 a a a 用 T → a T T\to aT T → a T ,遇 # \# # 用 T → ε T\to\varepsilon T → ε 。
快速检查
(对文法 S → a S ∣ ε S\to aS\mid\varepsilon S → a S ∣ ε ,在输入 a a aa aa 上跟踪分析器,列出各次产生式选择以及最终的标记条件。)
解答 · 答案 对第一个和第二个 a a a ,分析器都选择 S → a S S\to aS S → a S 并匹配该终结符。到达输入末尾时选择 S → ε S\to\varepsilon S → ε ,栈与输入中都只剩 # \# # 。于是接受。推导为 S ⇒ a S ⇒ a a S ⇒ a a S\Rightarrow aS\Rightarrow aaS\Rightarrow aa S ⇒ a S ⇒ aa S ⇒ aa 。