top-down vs bottom-up parsers

Dennis Taylor <>
5 Dec 1997 01:18:04 -0500

          From comp.compilers

Related articles
Bottom-up versus Top-down (Jack Olsen) (1997-11-23)
Re: Bottom-up versus Top-down (1997-11-29)
top-down vs bottom-up parsers (Dennis Taylor) (1997-12-05)
Re: top-down vs bottom-up parsers tim@wagner.Princeton.EDU (1997-12-10)
Re: top-down vs bottom-up parsers (Chris Clark USG) (1997-12-15)
| List of all articles for this month |

From: Dennis Taylor <>
Newsgroups: comp.compilers
Date: 5 Dec 1997 01:18:04 -0500
Organization: Compilers Central
References: 97-11-123 97-11-155
Keywords: parse

>In top-down parsing you use each incoming token as a decision point to
>determine the next step of the parsing; in bottom-up parsing you group
>the incoming tokens together and look for a group that matches one of
>the known patterns of the grammar. Then you start grouping groups
>together, and when a match is made for the pattern 'program' parsing
>is complete. Top down parsing is much easier to implement, but,
>bottom-up parsing is more efficient. YACC and other code generators
>tend to generate the type of state tables required to do bottom-up
>parsing efficiently...

I guess what's always thrown me off when considering bottom-ups is
visualizing what's happening. With a top-down (recursive descent)
parser, you are usually explicitly building the parser routine by
routine, so you can build as much smarts as you want into it. With a
bottom-up, I have trouble seeing how the parser can handle statements


where there's an operator precedence involved. It would be easy to
implement if all operators had the same precedence. But in this case,
when the parser has recognized x+y, what tells it that it should parse
y*z first?

Or take a situation with right-associative and left-associative
operators, like in c. any declaration like


or some such, must be parse-able, but how? I've read all the "usual"
books, but they just give pat answers and simple examples. None that
I've seen actually explains what happens in the less straightforward
[Bottom-up parsers have a state machine. Each state has a set of rules
about what you do with each possible token that can arrive in that state.
It's similar to a DFA lexer with the addition of rules that pop a bunch
of symbols off the end of the recoginized string and replace that with
a single usually different symbol. -John]


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.