---
title: "top-down parsing"
type: concept
related: [Building A Parser]
source: https://www.jemoka.com/posts/kbhbuilding_a_parser/
confidence: high
status: active
---

recursive descent parsing Given the grammar:
E -&gt; T | T + E T -&gt; int | int * T | (E) And suppose our token stream is: (int5) We will start top-level non-terminal character E, and will try to apply the rules for E in order&hellip;
(this is exactly how you imagine one builds a parser via recursive backtracking)
when does it break? Consider S -&gt; S a, this becomes S -&gt; S1 a.
Notice it will break into:
bool S1() { return S() &amp;&amp; term(a); } bool S() { return S1(); } This is what we call a left recursive grammar
left recursive grammar That is, the grammar keep recurses to the left without termination.
fixing left recursive grammars for top-down parsing For:
S -&gt; S a1 | ... | S an | b1 | ... | bm We write:
S -&gt; b1 S&#39; | ... | bm S&#39; S&#39; -&gt; a1 S&#39; | ... | an S&#39; | nothing where nothing is the empty string.
example
For the left recursive grammar
S -&gt; S a | b We can refactor as
S -&gt; B S&#39; S&#39; -&gt; a S&#39; | nothing where nothing is \(\epsilon\)
example! We will define boolean functions to check the string for matches.
// gobble up the token string pointer bool term(TOKEN tok) { return *next++ == tok; } Let&rsquo;s now match each of our productions.
bool E1() { return T(); } bool E2() { return T() &amp;&amp; term(PLUS) &amp;&amp; E(); } bool E() { TOKEN *save = next; // that is, if E1 matches, return immediately // otherwise, we return our saved pointer in text (i.e. roll what what // checking E1 could goble), and roll back return ( E1() || (next=save, E2()); ) } bool T1() { return term(INT) }; // ... you get the point
