編譯原理-上下無關(guān)文法和文法分析(編輯修改稿)
2024-11-13 02:27 本頁面
【文章內(nèi)容簡介】 ght recursive grammar: ? A a A | a ? A α A | β Equivalent to α* β In the BNF ,there is no repetition operation .Because the recursion can express the repetition . ε Production ? empty ε generates a language consisting of an empty string. ? Such a grammar rule is called an ε –production. ? A grammar that generates a language containing an empty string must have at least one ε –production. ? A A a | ε or A a A | ε are equivalent to the regular expression a*. ? ε productions are useful in defining structures that are optional. Example ? A ( A ) A | ε ? Generates the strings of all “balanced parentheses”. ? ( ( ) ( ( ) ) ) ( ) generated by the derivation ? A = ( A ) A = ( A ) ( A ) A = ( A ) ( A ) ε = ( A ) ( ε ) = ( ( A ) A ) ( ) = ( ( A ) ( A ) A )( ) = ( ( A ) ( A ) ε ) ( ) = ( ( A ) ( ( A ) A ) ) ( ) = ( ( ) ( ( ) ) ) ( ) (ε production is used make A disappear as needed ) Example statement ifstmt | other ifstmt if (exp) statement elsepart elsepart else statement | ε exp 0 | 1 statement ifstmt | other ifstmt if (exp) statement | if (exp) statement else statement exp 0 | 1 A Parse Tree ? A parse tree corresponding to a derivation is a labeled tree – The interior nodes are labeled by nonterminals. – The leave nodes are labeled by terminals. – The children of each node represent the replacement of the nonterminal in one step of derivation. exp exp op exp number + number (1) exp = exp op exp (2) = number op exp (3) = number + exp (4) = number + number 1 2 3 4 Same Tree, Different Numbering exp exp op exp number + number 1 3 2 4 (1) exp = exp op exp (2) = exp + exp (3) = number + exp (4) = number + number exp exp op exp number + number 1 4 3 2 (1) exp = exp op exp (2) = exp op number (3) = exp + number (4) = number + number Leftmost and Rightmost Derivations ? A parse tree corresponds to many derivations. ? It is possible to distinguish particular derivations that are uniquely associated with the parse tree. ? A leftmost derivation: – The leftmost nonterminal is replaced et each step. ? A rightmost derivation: – The rightmost nonterminal is replaced et each step. Examples (1) exp = exp op exp (2) = number op exp (3) = number + exp (4) = number + number exp exp op exp
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1