编译原理 句型的句柄怎么求

Question

已知文法G[S] S::=aB|bA
A::=a|aS|bAA
B::=aBB|bS|b
句型aabbAb的句柄是
A.a B.ab
C.b D.bA

大概说下原因就好

Answer 1

句型aabbAb的句柄是D: bA;
S->aB->aaBB->aabSB->aabbAB->aabbAb
按照最左推导，其中的S->bA这步是最后的直接推导（即它推出的bA不再被继续往下推导），虽然B->b也是这样的，但不是最左的。
其实你根据句型画个语法树就一目了然了，句柄即是最左直接短语，首先要是直接短语（直接推导），再就是最左（按最左的话最先推出的）。