Practical Top Down Parsing
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Practical Top Down Parsing as PDF for free.
More details
- Words: 595
- Pages: 10
Practical Top Down Parsing Recursive Descent Parser • A recursive descent (RD) parser is a variant of top down parsing without backtracking. • It uses a set of recursive procedures to perform parsing. • Salient advantages of RD parsing is its simplicity and generality • It can implemented in any language that supports recursive procedures
Recursive Descent Parser • To implement recursive descent parsing, a left-factored grammar is modified to make repeated occurrences of strings more explicit E ::= T{+T}* T ::= V {*V}* V ::= • The notation {…}* indicates zero or more occurrences of the enclosed specification
Recursive Descent Parser • A parser procedure is now written for each NT of G. • It handles prediction making, matching and error reporting for that NT • The structure of the parser procedure is dictated by the grammar production for the NT • If A ::= …B… is a production of G, the parser procedure for A contains a call on the procedure for B.
proc_E (tree_root) proc_T (tree_root) { a, b : pointer to a tree node { a, b : pointer to a tree node proc_T (a); proc_V (a); while (nextsymb ==‘+’) while (nextsymb ==‘*’) { match (‘+’); { match (‘*’); proc_T (b); proc_V (b); a = treebuild (‘+’, a, b); a = treebuild (‘*’, a, b); tree_root = a; tree_root = a; } } return; return; } } proc_V (tree_root) { a : pointer to a tree node if (nextsymb ==) tree_root = treebuild (, - , - ); else print “Error!”; return; }
Recursive Descent Parser Example • The parser returns an AST for a valid source string, ad reports an error for an invalid string • The procedures proc_E, proc_T and proc_V handle the parsing for E, T and V, respectively • And build ASTs for these NTs using the procedure treebuild • Procure match increments SSM
An LL(1) Parser • An LL(1) parser is a table driven parser for left-toleft parsing. • The ‘1’ in LL(1) indicates that the grammar uses a look-ahead of one source symbol – that is, the prediction to be made is determined by the next source symbol. • A major advantage of LL(1) parsing is its amenability to automatic construction by the parser generator
An LL(1) Parser Example • Grammar: E ::= TE' E' ::= +TE' | ε T ::= V T' ::= *VT' | ε V ::= • Source String: + *
LL(1) Parser Table Nonterminal E E' T T' V
Source Symbol + *
$
E => TE' E' => +TE'
E' => ε
T=>VT' T' => ε V=>
T' => *VT' T' => ε
LL(1) Parser Table • A parsing table (PT) has a row for each NT∈SNT and a column for each T ∈ Σ . • A parsing table entry PT(ntj, tj) indicates what prediction should be made if ntj is the leftmost NT in a sentential form and tj is the next source symbol • A blank entry in PT indicates an error situation • A source string is assumed to be enclosed between the symbols ‘$’ and ‘$’. Hence the parser starts with the sentential form $E$
Current Sentential Form
Symbol
Prediction
$E$
E => TE'
$TE'$
T => VT'
$VT'E'$
V =>
$T'E'$
+
T' => ε
$E'$
+
E' => +TE'
$+TE'$
T => VT'
$+VT'E'$
V =>
$+T'E'$
*
T' => *VT'
$+*VT'E'$
V =>
$+*T'E'$
$
T' => ε
$+*E'$
$
E' => ε
$+*$
-
-
Recursive Descent Parser • To implement recursive descent parsing, a left-factored grammar is modified to make repeated occurrences of strings more explicit E ::= T{+T}* T ::= V {*V}* V ::=
Recursive Descent Parser • A parser procedure is now written for each NT of G. • It handles prediction making, matching and error reporting for that NT • The structure of the parser procedure is dictated by the grammar production for the NT • If A ::= …B… is a production of G, the parser procedure for A contains a call on the procedure for B.
proc_E (tree_root) proc_T (tree_root) { a, b : pointer to a tree node { a, b : pointer to a tree node proc_T (a); proc_V (a); while (nextsymb ==‘+’) while (nextsymb ==‘*’) { match (‘+’); { match (‘*’); proc_T (b); proc_V (b); a = treebuild (‘+’, a, b); a = treebuild (‘*’, a, b); tree_root = a; tree_root = a; } } return; return; } } proc_V (tree_root) { a : pointer to a tree node if (nextsymb ==
Recursive Descent Parser Example • The parser returns an AST for a valid source string, ad reports an error for an invalid string • The procedures proc_E, proc_T and proc_V handle the parsing for E, T and V, respectively • And build ASTs for these NTs using the procedure treebuild • Procure match increments SSM
An LL(1) Parser • An LL(1) parser is a table driven parser for left-toleft parsing. • The ‘1’ in LL(1) indicates that the grammar uses a look-ahead of one source symbol – that is, the prediction to be made is determined by the next source symbol. • A major advantage of LL(1) parsing is its amenability to automatic construction by the parser generator
An LL(1) Parser Example • Grammar: E ::= TE' E' ::= +TE' | ε T ::= V T' ::= *VT' | ε V ::=
LL(1) Parser Table Nonterminal E E' T T' V
Source Symbol + *
$
E => TE' E' => +TE'
E' => ε
T=>VT' T' => ε V=>
T' => *VT' T' => ε
LL(1) Parser Table • A parsing table (PT) has a row for each NT∈SNT and a column for each T ∈ Σ . • A parsing table entry PT(ntj, tj) indicates what prediction should be made if ntj is the leftmost NT in a sentential form and tj is the next source symbol • A blank entry in PT indicates an error situation • A source string is assumed to be enclosed between the symbols ‘$’ and ‘$’. Hence the parser starts with the sentential form $E$
Current Sentential Form
Symbol
Prediction
$E$
E => TE'
$TE'$
T => VT'
$VT'E'$
V =>
$
+
T' => ε
$
+
E' => +TE'
$
T => VT'
$
V =>
$
*
T' => *VT'
$
V =>
$
$
T' => ε
$
$
E' => ε
$
-
-
Related Documents
Practical Top Down Parsing
June 2020 9
Top Down Parsing
November 2019 22
Top-down
May 2020 14
Parsing
November 2019 20
Compiler Design -- Practical Earley Parsing
June 2020 8
Parsing
July 2020 7More Documents from ""
Hash Table Organization
June 2020 2
Allocation Data Structure
June 2020 4