|
|
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 程序设计语言和语言处理程序知识 > 汇编、编译、解释系统的基本知识和基本工作原理 > 程序语言翻译基础 > 编译程序基本原理 > 语法分析 >
|
|
相关知识点：3个
|
|
|
|
|
自顶向下分析法的基本思想是：对于给定的输入串ω，从文法的开始符号S出发进行最左推导，直到得到一个合法的句子或者发现一个非法结构。在推导的过程中试图用一切可能的方法，自上而下、从左到右地为输入串ω建立语法树。整个分析过程是一个试探的过程，是反复使用不同产生式谋求与输入序列匹配的过程。若输入串是给定文法的句子，则必能成功，反之必然出错。
|
|
|
|
文法中存在下述产生式时，自顶向下分析过程中会出现下面的问题：
|
|
|
|
（1）若文法中存在形如A→αβ｜αδ的产生式，即A产生式中有多于一个候选项的前缀相同（称为公共左因子，简称左因子），则可能导致分析过程中的回溯处理。
|
|
|
|
（2）若文法中存在形如A→Aα的产生式，由于采取了最左推导，可能会造成分析过程陷入死循环的情况，产生式的这种形式被称为左递归。
|
|
|
|
因此，需要对文法进行改造，消除其中的左递归，以避免分析陷入死循环；提取左因子，以避免回溯。
|
|
|
|
（3）递归下降分析法。递归下降分析法直接以子程序调用的方法模拟产生式产生语言的过程，其基本思想是：为每一个非终结符构造一个子程序，每个子程序的过程体按该产生式候选项分情况展开，遇到终结符即进行匹配，而遇到非终结符则调用相应的子程序。该分析法从调用文法开始符号的子程序开始，直到所有非终结符都展开为终结符并得到匹配为止。若分析过程可以达到这一步，则表明分析成功，否则表明输入串中有语法错误。递归下降分析法的优点是简单且易于构造，缺点是程序与文法直接相关，对文法的任何改变都需要在程序中进行相应的修改。
|
|
|
|
（4）预测分析法。预测分析法是另一种自顶向下的语法分析方法，其基本模型如下图所示。
|
|
|
|
|
|
|
|
预测分析法的核心是预测分析表，可以用一个二维数组M表示，其元素M［A，a］（A∈VN，a∈VT∪#）存放关于A的产生式，表明当遇到输入符号为a且用A进行推导时，所应采用的产生式；若M［A，a］为error，则表明推导时遇到了不该出现的符号，应进行出错处理。
|
|
|
|
例如，根据文法G［E］=｛E→TE'，E'→+TE'｜ε，T→FT'，T'→*FT'｜ε，F→（E）｜id｜｝的构造的预测分析表如下表所示。
|
|
|
|
|
|
|
|
预测分析法的工作过程是：初始时，将“#”和文法的开始符号依次压入栈中；在分析过程中，根据输入串中的当前输入符号a和当前的栈顶符号X进行处理。
|
|
|
|
若X=a='#'，则分析成功；若X='#'且a≠'#'，则出错。
|
|
|
|
若X∈VT且X=a，则X退栈，并读入下一个符号a；若X∈VT且X≠a，则出错。
|
|
|
|
若X∈VN且M［X，a］='A→α'，则X退栈，α中的符号从右到左依次进栈（ε无须进栈）；若M［X，a］='error'，则调用出错程序进行处理。
|
|
|
