清华大学：《编译原理》课程教学资源_语法分析

③苇大 语店分教术小结 ◇自上而下分祈 ◇自下而上分析 ◇比 ◆二义性处理

语法分析技术小结  自上而下分析  自下而上分析  二义性处理  比较

③苇大 自上而下分析 ◇自上而下分祈一般过程 ◇LL(1)文法 ◇预测分析程序 递下障分析故术 表驱动分析技术

自上而下分析  自上而下分析一般过程  LL（1）文法  预测分析程序 − 递归下降分析技术 − 表驱动分析技术

③苇大 自上而下分析一般过程 In the top-down parsing, we begin with the start symbol and at each step, expand one of the remaining nonterminals by replacing it with the right side of one its productions We repeat until only terminals remain. The top down parse prints a leftmost derivation of the sentence

自上而下分析一般过程 In the top-down parsing,we begin with the start symbol and at each step, expand one of the remaining nonterminals by replacing it with the right side of one its productions. We repeat until only terminals remain. The top￾down parse prints a leftmost derivation of the sentence

③苇大 LL(1)文法 The first"L, means we scan the input from left to right; the second L means we create a leftmost derivation and the 1 means one input symbol of lookahead A grammar G is ll(1) iff whenever A->u v are two distinct productions of G, the following conditions hold for no terminal a do both u and v derive strings beginning with a (i. e. first sets are disjoint) at most one of u and v can derive the empty string if v=>*8 then u does not derive any string beginning with a terminal in Follow (A)

LL（1）文法 The first “L” means we scan the input from left to right; the second “L” means we create a leftmost derivation; and the 1 means one input symbol of lookahead. A grammar G is LL(1) iff whenever A –> u | v are two distinct productions of G, the following conditions hold: - for no terminal a do both u and v derive strings beginning with a (i.e. first sets are disjoint) - at most one of u and v can derive the empty string - if v =>*  then u does not derive any string beginning with a terminal in Follow(A)

③苇大 First集 The first set of a sequence of symbols u, written as First(u) is the set of terminals which start all the sequences of symbols derivable from u. a bit more formally, consider all strings derivable from u by a leftmost derivation If u=*v, where v begins with some terminal, that terminal is in First(u). Ifu=>*8 then s is in First(u)

The first set of a sequence of symbols u, written as First(u ) is the set of terminals which start all the sequences of symbols derivable from u. A bit more formally, consider all strings derivable from u by a leftmost derivation. If u =>* v , where v begins with some terminal, that terminal is in First(u). If u =>*  , then  is in First(u ). First 集

③苇大 Fo|low集 The follow set of a nonterminal A is the set of terminal symbols that can appear immediately to the right of a in a valid sentential form a bit more formally for every valid sentential form S ->UAv, where v begins with some terminal that terminal is in FollOw(A)

Follow 集 The follow set of a nonterminal A is the set of terminal symbols that can appear immediately to the right of A in a valid sentential form. A bit more formally, for every valid sentential form S =>*uAv , where v begins with some terminal, that terminal is in Follow(A)

③苇大 计算 First集 To calculate First(u) where u has the form X1X2.Xn, do the following 1. If X1 is a terminal, then add X1 to First(u) otherwise add First(X1)-s to First(u) 2. If X1 is a nullable nonterminal. i e. x1=>c. add First(X2)-8 to First(u). Furthermore if X2 can also go to s, then add First(X3 )-8 and so on, through all xn until the first nonnullable one 3. If X1X2.Xn =>8. add s to the first set

计算First 集 To calculate First(u) where u has the form X1X2...Xn, do the following: 1. If X1 is a terminal, then add X1 to First(u), otherwise add First(X1) -  to First(u ) . 2. If X1 is a nullable nonterminal, i.e., X1 =>*  , add First(X2) -  to First(u). Furthermore, if X2 can also go to  , then add First(X3) -  and so on, through all Xn until the first nonnullable one. 3. If X1X2...Xn =>*  , add  to the first set

③苇大 计算Foow集 For each nonterminal in the grammar, do the following 1. Place# in Follow(s) where S is the start symbol and is the input's right endmarker. The endmarker might be end of file, it might be newline, it might be a special symbol whatever is the expected end of input indication for this grammar. We will typically use as the endmarker 2. For every production A-> uBv where u and v are any string of grammar symbols and B is a nonterminal everything in First(v) except s is placed in Follow(B) 3. For every production A-> uB, or a production A-> u Bv where First(v)contains s(i.e. v is nullable), then everything in Follow (A) is added to Follow (B)

计算Follow 集 For each nonterminal in the grammar, do the following: 1. Place# in Follow(S) where S is the start symbol and # is the input's right endmarker.The endmarker might be end of file, it might be newline, it might be a special symbol, whatever is the expected end of input indication for this grammar. We will typically use # as the endmarker. 2. For every production A –> uBv where u and v are any string of grammar symbols and B is a nonterminal, everything in First(v) except  is placed in Follow(B). 3. For every production A –> uB, or a production A –> u Bv where First(v ) contains  (i.e. v is nullable), then everything in Follow(A) is added to Follow(B)

③苇大 预测分析程序 Predictive parser is a non-backtracking top- down parser. a predictive parser is characterized by its ability to choose the production to apply solely on the basis of the next input symbol and the current nonterminal being processed To enable this the grammar must take a particular form, that is, a grammar LlO

预测分析程序 Predictive parser is a non-backtracking top￾down parser. A predictive parser is characterized by its ability to choose the production to apply solely on the basis of the next input symbol and the current nonterminal being processed. To enable this, the grammar must take a particular form，that is, a grammar LL(1)

③苇大 递归下降分析技术 The first technique for implementing a predictive parser is called recursive-descent A recursive descent parser consists of several small functions(procedures), one for each nonterminal in the grammar. as we parse a sentence we call the functions(procedures) that correspond to the left Side nonterminal of the productions we are applying If these productions are recursive, we end up calling the functions recursively

递归下降分析技术 The first technique for implementing a predictive parser is called recursive-descent. A recursive descent parser consists of several small functions(procedures), one for each nonterminal in the grammar. As we parse a sentence, we call the functions (procedures) that correspond to the left side nonterminal of the productions we are applying. If these productions are recursive, we end up calling the functions recursively