文法分析小结:自底向上的分析方法和自顶向下的分析方法有哪些

  • Post author:
  • Post category:其他



首先注意一点:

无论是那种语法分析,语法都是

从左至右

的读入符号!





自底向上分析法,也称移进-归约分析法。

它的实现思想是对输入符号串自左向右进行扫描,并将输入符逐个移入一个后进先出栈中,边移入边分析,一旦栈顶符号串形成某个句型的句柄时,(该句柄对应某产生式的右部),就用该产生式的左部非终结符代替相应右部的文法符号串,这称为一步归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功,也就确认输入串是文法的句子。

总结了一下子,方便做题的时候查一下,省的总是翻书找半天,而且书上也没有很明确的总结和说明。

自底向上的分析技术 有:

( 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分析表都是编译原理的重点。

嗯,先总结到这。



版权声明:本文为Chen_dSir原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。