Question

自顶向下的语法分析和自底向上的语法分析解决的核心问题分别是什么

Answer 1

备忘录方法是动态规划方法的变形。与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上的。
如： 求LCS的问题：
当xi=yj时，求C[i,j]只需知道C[i-1,j-1]，而无需用到C[i,0]～C[i,j-1]及C[i-1,j]～C[i-1,n]。
∴ 当只需求出一个LCS时，可能有一些C[p,q]在整个求解过程中都不会用到。
一般地，当某个问题可以用动态规划法求解，但二维数组中有相当一部分元素在整个计算中都不会被用到。我们就不需要以递推方式逐个计算二维数组中元素。
而采用备忘录方法：数组中的元素只是在需要计算时才去计算，计算采用递归方式，值计算出来之后将其保存起来以备它用。
如：求LCS的问题：
首先将C[i,0](0≤i≤m)与C[0,j](1≤j≤n)初始化为0。其余m×n个C[i,j]全部初始化为-1。
计算C[i,j]的递归算法LCS_L2(X,Y, i,j,C)（备忘录方法）：
若x[i]=y[j]，则去检查C[i-1,j-1]，若C[i-1,j-1]> -1（已经计算出来），就直接把C[i-1,j-1]+1赋给C[i,j]，返回。
若C[i-1,j-1]=-1（尚未计算出来），就递归调用LCS_L2(X,Y, i-1,j-1,C) 计算出C[i-1,j-1]，然后再把C[i-1,j-1]+1赋给C[i,j] ，返回。
若x[i] 1 y[j]，则要检查C[i-1,j]和C[i,j-1]。
若两者均 > -1（已经计算出来），则把max{ C[i-1,j], C[i,j-1]} 赋给C[i,j]，返回。
若C[i-1,j], C[i,j-1] 两者中有一个等于-1（尚未计算出来），或两者均等于-1，就递归调用LCS_L2将其计算出来，然后再把max{ C[i-1,j], C[i,j-1]} 赋给C[i,j]。
∴若有大量的子问题无需求解时，用备忘录方法较省时。
但当无需计算的子问题只有少部分或全部都要计算时，用递推方法比备忘录方法要好（如矩阵连乘，最优二分搜索树）

Answer 2

前一个是 避免回溯和左递归
后面一个 是寻找句柄

Answer 3

中心词为基础