语法分析——自下而上分析.pptx

归约abAb###5.1 自下而上分析基本问题归约 自下而上分析法是“移进——归约”法。 模型：字符串：babA→ba①移进②归约③识别成功④其他出错输入串：programIdVar……#下推栈，初态为#，字符“先进后出”语法分析程序分析表#5.1 自下而上分析基本问题1.输入带记录待识别语句（单词＋结束符#）2.读头自左向右扫描输入串，初态指在最左单词上，栈内仅有#3.语法分析执行动作有：①移进——读入一单词并压入栈内，读头下移一位②归约——检查栈顶若干符号是否为语法表中产生式右部，若是，用左部替换右部③识别成功——栈内为文法开始符号，读头指向#④否则，语法错误SaAcBeAbdb栈内输入带动作0#abbcde#预备1#abbcde#移进2#abbcde#移进3#aAbcde#归约(A→b)4#aAbcde#移进5#aAcde#归约(A→Ab)6#aAcde#移进7#aAcde#移进8#aAcBe#归约(B→b)9#aAcBe#移进10#S#归约(S→aAcBe)11#S#接受(分析成功)如：S→aAcBeA→Ab|bB→d分析：abbcde*＋*5.1.2 规范规约简述1.短语、直接短语、句柄短语：已知文法G[S]，αβδ是文法G的一个句型，若S ?αAδ且A?β，则称β是句型αβδ的相对于非终结符A的短语。直接短语：若有S?αAδ且A?β，称β是句型αβδ的相对于规则A→β的直接短语。句柄：一个句型的最左直接短语称为该句型的句柄。例：G: E → E+T | E-T | T T → T*F | T/F | F F → (E) | i 给出句型E+T*F+i的短语、直接短语和句柄。abbcde A→baAbcde A→baAcde B→daAcBe S→aAcBdS例： G： E→E+T | T句型E+T*F+i T→T*F | F F→(E) | i短语： E+T*F+i， E+T*F， T*F，i直接短语： T*F，i句柄： T*F归约方法：形成句柄则进行归约。SaAcBedAbb2.规范归约： 假定α是文法G的一个句子，称序列αn，αn－1，… α0 是α的一个规范归约，则此序列满足： （1）αn＝α （2）α0为文法开始符，即α0＝S （3）对任何i，0i≤n， αi－1是从αi经把句柄替换为相应产生式的左部符号而得到的。 最左推导的逆过程——最右归约 最右推导的逆过程——最左归约 最右推导称为规范推导 最左归约称为规范归约②③①5.2 算符优先分析直观算符优先法 对于文法，任何两个相继出现的终结符（…ab…或…aQb…），有下列三种关系： a b a的优先性等于b a b a的优先性高于b a b a的优先性低于b注意：这三个关系不同于数学中的“=”，“”，“”，此处a b并不一定意味着b a，a b也不一定意味着 b a。＋＋＋＋5.2.1 算符优先文法及优先表的构造1.算符文法(OG)：文法G，如果G中每条规则不能有形如A→…BC…(A,B,C∈VN)的规则，则称G为算符文法。2.设G是不含ε－产生式的文法，对任何终结符a,b∈VT，A,B,C∈VN， (1)a b?G中含有规则A→…ab…或A→…aBb… (2)a b?G中含有规则A→…aB…，而B?b…或B?Cb… (3)a b?G中含有规则A→…Bb…，而B?…a或B?…aC注意：算符优先文法中允许a b，b a同时存在，但不允许a b ，a b ，a b三种中任何两种同时存在。若一个算符文法G 中任何终结符对(a,b)至多只满足下述三个关系之一： a b ，a b ，a b 则称G是一个算符优先文法(OPG)。如： E→E+E | E*E | (E)| i 为算符文法，但不是算符优先文法。 E→E+E E→E*E +* E→E*EE→E+E +*例： G： E→E+T | T T→T*F | F F→P?F | P P→(E) | i+*?i()#+*?i()#＋＋＋＋3.算符优先关系的构造 FIRSTVT(P)={a | P?a…或P ?Qa…，a∈VT，Q∈VN} LASTVT(P)={a | P?…a或P ?…aQ，a∈VT，Q∈VN}三种关系的计算：① 关系：由产生式右部决定，形如…ab…或…aQb…如：S→aAcBe，A→b，A→Ab，B→d，B→Ab 有 a c c e② 关系：求出每个符号的FIRSTVT，对于形如A→…aB…就有a FIRSTVT(B)如上例：FIRSTVT(S)={a},FIRST