4.1.1 The basic method of Recursive-descent
4.1.1 The Basic Method of Recursive-Descent
The idea of recursive-Descent Parsing Viewing the grammar rule for a non-terminal a as a definition for a procedure to recognize an a The right-hand side of the grammar for a specifies the structure of the code for this procedure The expression grammar exp> exp addo term term dp→+ term- term mulop factor factor mulot factor-exp)I number
The idea of Recursive-Descent Parsing • Viewing the grammar rule for a non-terminal A as a definition for a procedure to recognize an A • The right-hand side of the grammar for A specifies the structure of the code for this procedure • The Expression Grammar: exp → exp addop term∣term addop → + ∣- term → term mulop factor ∣ factor mulop →* factor →(exp) ∣ number
a recursive-descent procedure that recognizes a factor procedure factor The token keeps the current begin next token in the input (one case token of ( match(( symbol of look-ahead) exp match() The match procedure number matches the current next match(number); token with its parameters, else error advances the input if it end case succeeds and declares error end factor if it does not
A recursive-descent procedure that recognizes a factor procedure factor begin case token of ( : match( ( ); exp; match( )); number: match (number); else error; end case; end factor • The token keeps the current next token in the input (one symbol of look-ahead) • The Match procedure matches the current next token with its parameters, advances the input if it succeeds, and declares error if it does not
Match procedure The Match procedure matches the current next token with Its parameters, advances the input if it succeeds and declares error if it does not procedure match( expected Token) begin if token= expected Token then get Token else error end if end match
Match Procedure • The Match procedure matches the current next token with its parameters, – advances the input if it succeeds, and declares error if it does not procedurematch( expectedToken); begin if token = expectedToken then getToken; else error; end if; end match
Requiring the use of ebnf The corresponding ebnf is exp→term{ adop term} adop term> factor& mulop factor/ mlOp→ factor→(exp)| number Writing recursive-decent procedure for the remaining rules in the expression grammar is not as easy for factor
Requiring the Use of EBNF • The corresponding EBNF is exp → term { addop term } addop→ + | - term → factor { mulop factor } mulop→ * factor → ( exp ) | numberr • Writing recursive-decent procedure for the remaining rules in the expression grammar is not as easy for factor