自下而上语法分析.doc

《自下而上语法分析.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、自下而上语法分析对于产生语言来讲，白上而下分析的方法是白然的。对于分析语言来讲，H下而上分析的方法更白然，因为语法分析处理的对象一开始都是终结符组成的输入序列，而不是文法的开始符号。同时，白下而上分析中最一般的方法，LR方法的能力比白上而下分析的LL方法要强，从而使得LR分析成为最为实用的语法分析方法。3.5.1自下而上分析的基本方法思路：从句子3T•始，从左到右扫描3反复用产生式的左部替换产生式的右部、谋求对3的匹配，最终得到文法的开始符号，或者发现一个错误。3.5.1.1规范归约与“剪句柄”定义3.13设咿是文法G的一个句型，若存在

2、S=>aA&则称魄句型邛湘对于A的短语,特别的，若有A-B则称幌句型叩湘对于产生式A-郎J直接短语,一个句型的最左一直接短语被称为句柄。##%1直观上，句型是一个完報结构，短语是句型屮的某部分。S是一个句型，而不是一个短语。%1短语形成的两个要素：1从S可以推导出A,即S^>ciA§2从A至少一次推导出B即特征：%1短语：以非终结符为根的了树屮所有从左到右排列的叶子；%1直接短语：只有父子关系的树屮所有从左到右排列的叶子（树高为2）；%1句柄：最左边父子关系树屮所有从左到右排列的叶子（句柄是唯一的）。问题：H1+H2是句型H1+H2*H

3、3的一个短语吗？答案：不是。因为：%1没有一个E的子树，它的全部叶子是H1+H2或者%1找不到某个E,使得E=>*E*E3E=>4~H1+H2定义3.14若（焊文法G的句子且满足下述条件，则称序列5•••，％是（的一个最左归约。L2Oo=S（S是G的开始符号）3对任何igM=n）,呜是从对巴句柄替换为相应产生式左部非终结符得到的。##注意：最左归约的逆过稈是一个最右推导，分别称最右推导和最左归约为规范推导和规范归约。需要解决的问题：%1确定右句型屮将要归约的了串（确定句柄）；%1确定如何选择正确的产生式进行归约。3.5.1.2移进-归约

4、分析器工作模式解决方法：移进廿1约分析用一个栈“记住”将要归约句柄的前缀，旬柄未形成前移进，形成后归约。移进-归约分析器的工作模式：（不同的分析表决定了不同的分析方法）输入记号流_iptop输出移进约分析表符号状态找驱动器图3.17移进-归约分析器模型工作方法：放幻灯，每个幻灯片是一个格局。格局：（斗栈，当前剩余输入苑改变格局的动作）改变格局的动作：%1移进（曲血:输入序列屮的终结符进栈。（匹配终结符）%1归约（reduce）:将栈顶句柄替换为对应的非终结符。（归约产生式）%1接受（accept）:宣告分析成功。%1报错（eni）D:发

5、现语法错误，调用错误恢复例稈。从移进-归约分析过程中可以看出:%1句柄总是在栈顶形成。这是因为在分析的过程屮一旦形成某产生式的右部就立即进行归约，而从左到右扫描输入，最早形成的白然是最左的直接短语；%1栈屮保留的总是一个右句型的前缀（加上若干终结符形成句型），称为活前缀;%1如果将毎次归约逻辑上认为是构造对应产生式的树，则分析的全过程逻辑上就是从下到上构造一棵分析树；反Z,如果将每次归约逻辑上认为是剪去假想分析树上对应产生式的孩了，则分析的全过稈逻辑上就是从下到上为分析树剪句柄。需要解决的问题：（由分析表确定）%1如何保证栈屮总是活前缀

6、正确移进）；%1如何确定栈顶已经形成句柄并选择正确的产生式进行归约正确归约）。3.5.2LR分析LR分析的特点：%1采用最一般的无冋溯移进坍约方法；%1可分析的文法是LL文法的真超集；%1能够及时发现错误，快到从左到右扫描输入序列的最大可能;%1分析表较复杂，难以手工构造。3.5.2.1LR分析与LR文法<1>移进-归约分析表LR分析器的核心是LR分析表和丞动器。文法：E-ETJTZT疥

7、F

8、idid—*ETF0s4s51231s6acc2r2s7r23rdrdrd4r6r6r65s4s586s4s5937s4s5108r5r5r59r

9、ls7rl10r3r3r3actbngoto动作表（action）与转移表（goto）:两者都是二维数纽.，且行下标由称Z为状态的整型数统一表示。动作表以终结符作为列下标，转移表以非终结符作为列下标。action根据输入确定改变格局的动作，而got。仅指示非终结符的状态转移°故仅有动作表与输入有关。<2>格局与改变格局的动作开始格局：（#Q（曲第一个动作）结朿格局：（#0S#,接受）出错格局：（#§曲报错）改变格局的四个动作：%1actbnaf=si终结符进栈并转向状态i（移进）%1=方用第拎产生式的左部替换栈屮的句柄（与⑤共同完成归约

10、）%1=ace接收%1=blank报错%1goto[s,A]=s'：在劝犬态下遇到A转移到状态i事实上，②和⑤共同完成归约。算法3.8LR分析输入输入序列心和文法G的LR分析表actbn与goto输出若履于