首先注意一点:
无论是那种语法分析,语法都是
从左至右
的读入符号!
自底向上分析法,也称移进-归约分析法。
它的实现思想是对输入符号串自左向右进行扫描,并将输入符逐个移入一个后进先出栈中,边移入边分析,一旦栈顶符号串形成某个句型的句柄时,(该句柄对应某产生式的右部),就用该产生式的左部非终结符代替相应右部的文法符号串,这称为一步归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功,也就确认输入串是文法的句子。
总结了一下子,方便做题的时候查一下,省的总是翻书找半天,而且书上也没有很明确的总结和说明。
自底向上的分析技术 有:
( 1 )简单优先分析法
( 2 )算符优先分析法
( 3 )优先函数
( 4 ) LR 分析法
确定的自顶向下分析方法
是从某文法的开始符号出发,考虑如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导,或如何构造一棵相应的语法树,其末端结点以从左向右的顺序连接正好为给定的输入符号串,则所给的输入符号串为该文法的句子。
自顶向下的分析技术 有:
( 1 )LL(1)分析法
( 2 )递归下降分析法
其中如何判断是LL(1)文法:
我们可以用 LL(1) 法来解析的语法被称为 LL(1) 语法( LL(1) grammar ),当且仅当一种语法具有以下特性时,此语法才是 LL(1) 语法:
对该语法中的任何非终结符 A ,若其所有产生式为: A -> u1 | u2 | … | un ,则:
(1) First(u1), First(u2), … First(un) 互不相交;
(2) 若有一个 First(ui) 中含 ε ,则 Follow(A), First(u1), First(u2), … First(un) 互不相交。
判别一种语法是否是 LL(1) 语法的方法就是构造其分析表,若构造过程中没有发现冲突,也就是表中的任何元素 M[X, a] 最多只有一个动作,那么此语法就是 LL(1) 语法。
递归下降分析法用的比较少,在自底向上的分析法中,我们用的比较多的是LR分析法,构建LR分析表都是编译原理的重点。
嗯,先总结到这。