|
|
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 程序设计语言和语言处理程序知识 > 汇编、编译、解释系统的基本知识和基本工作原理 > 程序语言翻译基础 > 编译程序基本原理 > 语法分析 >
|
|
考试要求：掌握
相关知识点：3个
|
|
|
|
|
常用的自底向上分析方法也称移进-归约分析法，工作模型是下推自动机，如下图所示。其基本思想是对输入序列ω自左向右进行扫描，并将输入符号逐个移进一个栈中，边移进边分析，一旦栈顶符号串形成某个句型的可归约串（即句柄）时，就用某个产生式的左部非终结符来替代，这称为一步归约。重复这一过程，直至栈中只剩下文法的开始符号且输入串也被扫描完时为止，确认输入串ω是文法的句子，表明分析成功；否则，进行出错处理。
|
|
|
|
|
|
|
|
LR分析法是一种规范归约分析法。规范归约是规范推导（最右推导）的逆过程，下面举例说明规范归约的过程。
|
|
|
|
LR分析法根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的k个（k≥0）符号，就可唯一确定分析器的动作是移进还是归约，以及用哪条产生式进行归约，因而也就能唯一地确定句柄。当k=1时，已能满足当前绝大多数高级语言编译程序的需求。常用的LR分析器有LR（0）、SLR（1）、LALR（1）和LR（1）。
|
|
|
|
|
|
（1）驱动器。或称驱动程序。对所有LR分析器，驱动程序都是相同的。
|
|
|
|
（2）分析表。不同的文法具有不同的分析表。同一文法采用不同的LR分析器时，分析表也不同。分析表又可分为动作表（ACTION）和状态转换表（GOTO）两个部分，它们都可用二维数组表示。
|
|
|
|
|
|
分析器的动作由栈顶状态和当前输入符号决定（LR（0）分析器不需向前查看输入符号），LR分析器的模型如下图所示。
|
|
|
|
|
|
|
|
其中SP为栈顶指针，Si为状态，Xi为文法符号。ACTION［Si，a］=Sj规定了栈顶状态为Si且遇到输入符号a时应执行的动作。状态转换表GOTO［Si，X］=Sj表示当状态栈顶为Si且文法符号栈顶为X时应转向状态Sj。
|
|
|
|
LR分析器的工作过程以格局的变化来反映。格局的形式为（栈，剩余输入，动作）。分析是从某个初始格局开始的，经过一系列的格局变化，最终达到接受格局，表明分析成功；或者达到出错格局，表明发现一个语法错误。因此，开始格局的剩余输入应该是全部的输入序列，而接受格局中的剩余输入应该为空，任何其他格局或者出错格局中的剩余输入应该是全部输入序列的一个后缀。
|
|
|
|
|
|
（1）移进（shift）。当ACTION［Si，a］=Sj时，把a移进文法符号栈并转向状态Sj。
|
|
|
|
（2）归约（reduce）。当在文法符号栈顶形成句柄β时，把β归约为相应产生式A→β的非终结符A。若β的长度为r（即｜β｜=r），则弹出文法符号栈顶的r个符号，然后将A压入文法符号栈中。
|
|
|
|
（3）接受（accept）。当文法符号栈中只剩下文法的开始符号S，并且输入符号串已经结束时（当前输入符是“#”），分析成功。
|
|
|
|
（4）报错（error）。当输入串中出现不该有的文法符号时，就报错。
|
|
|
|
LR分析器的核心部分是分析表的构造，这里不再详述。
|
|
|
