把输入组织为层级

词法记号给出基本单位,语法分析再判断这些单位怎样构成表达式、语句或声明。例如数字、加号和乘号的序列,需要按语言规则确定嵌套关系,才能交给后续阶段处理。

分析器可以直接构建抽象语法树,也可以维护更接近文法的分析树或其他内部状态。识别输入属于文法,与保存全部推导细节不是同一要求,具体输出由工具用途决定。

参考:[1] [2]

从上展开或从下归并

自顶向下方法从期望的较大结构出发,预测接下来需要哪些子结构。预测式递归下降可以让函数对应语法规则;LL方法也能用表与栈实现,不必强制采用宿主语言递归。

自底向上方法先取得输入,再把符合规则的片段归约为更大的结构。LR分析以状态和移进、归约操作组织这种过程。不同方法对文法和所需前瞻有不同限制,不能仅靠输出相似就认定算法相同。

参考:[3] [4]

结构正确仍不等于程序正确

一个字符串可能在同一文法中有多棵分析树。运算优先级、结合性或明确的消歧规则,决定工具应接受哪种解释;分析器报告冲突时,也需分辨文法歧义与所选算法能力的限制。

即使语法接受,名字也可能未定义,类型使用也可能不符合语言要求。语义分析继续检查这些条件;而类型等静态检查成功,又不能自动证明业务逻辑符合人的意图。

参考:[2] [5]