top-down vs bottom-up parsers

>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
like:


x+y*z+a/b


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


*(*(*oop)())[]


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
cases.
[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]




--

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