递归下降分析 (50).ppt
Compiler ConstrucionS18.1.2 E.W.DIJKSTRA Method There are two stacks in E.W.DIJKSTRA method,one stack storages operands,the other one is for operators,the procedure of it is shown by Figure 8.2,and the step of E.W.DIJKSTRA method is as follows:.Compiler ConstrucionS2 Compiler ConstrucionS3Actually,scanning the expression is from left to right.At the beginning of scanning,we push identifier#to the bottom of operator stack,similarly,we add identifier#to the end of expression to label that it is terminal of expression.When the two identifier#meet,it means the end of scanning.The steps of scanning are:1 If it is operand,go to the operand stack:Compiler ConstrucionS4 Compiler ConstrucionS52 If it is operator,it should be compared with the operator on the top of operator stack.When the priority of operator on the top stack is bigger than the scanning operator,or equal to it,the operator on the top of operator stack would be popped and go to the left side.On the other hand when the priority of operator on the top stack is less than the scanning operator,scanning operator should be pushed into operator stack.Compiler ConstrucionS6 Compiler ConstrucionS73 If it is left parenthesis,just push it into operator stack,and then compare the operators within parentheses.If it is right parenthesis,pop all the operators within parentheses,what is more,parentheses would be disappeared and would not be represented as postfix n o t a t i o n.4 Return to step 1 till two identifier#meet.Compiler ConstrucionS8Example 8.1 There is an expression of a+b*c,its postfix notation is abc*+.From the translating procedure shown by Figure 8.3,we can see that operator order is*+,it is also the pop order of the operator stack and calculating orderCompiler ConstrucionS9Compiler ConstrucionS10Compiler ConstrucionS11The other example,the postfix notation for expression a*b+(c-d)/e is ab*cd-e/+.From examples,we know it is a bit difficult to translate an expression into its postfix notation.So scientist E.W.DIJKSTRA from Holand created a method to solve the problem.
