第四章 自上而下的分析
第四章 自上而下的分析
4.1 语法分析器功能
语法分析是编译过程的核心部分。
它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。
4.1.1基本思想
对任何一个输入串，试图用一切可能的办法，从文法的开始符号(根节点)出发，根据文法自上而下地为输入串建立一棵语法树，即为输入串寻找一个最左推导。
思想本质：是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。
4.1.2语法分析器的构造方法
让每个非终结符号对应一个递归子程序。每个子程序可以作为一个布尔过程(返回“真”或“假”)。
4.2 自上而下分析面临的问题
自上而下分析面临的问题
文法的左递归问题、回溯的不确定性，要求我们将已经完成工作推倒从来、虚假匹配的问题、不能准确地确定输入串中出错的位置、效率低。
4.3 LL(1) 分析法
LL：L：left->right扫描；L：最左推导
4.3.1 左递归的消除
消除文法的左递归：(1) 将间接左递归改造为直接左递归（2）消除直接左递归（3）化简改写后的文法，即去除那些从开始符号出发却永远无法到达的非终结符的产生规则。
4.3.2 消除回溯
对文法的任何非终结符，当要它去匹配输入串时，能够根据该非终结符所面临的输入符号准确地指派它的一个候选式去匹配，并且此候选式匹配后得到的工作结果应该是确信无疑的，即：
(1)若该候选式匹配成功，那么该匹配不是虚假匹配
(2)若该候选式无法完成最终的匹配任务，则其他任何候选式肯定也无法完成
4.3.3 LL(1)分析条件
不带回溯的自上而下分析的方法
对于LL(1)文法，假设要用非终结符A进行匹配，面临输入符号为a，A的所有产生式为
A→α1|α2|…|αn
(1)若a ∈ FIRST(αi) ，则指派αi去匹配
(2)若a不属于任何一个候选首符集，则：
①若ε属于某个 FIRST(αi)且a∈FOLLOW(A)，则让A与ε自动匹配；
②否则，a的出现是一种语法错误
4.4 递归下降分析程序构造
4.4.1递归子程序法（递归下降分析法）具体做法
对文法的每一个非终结符都编一个分析程序