How does a shift reduce parser know when to reduce?

Question

I am writing a shift reduce parser in c#. I looked at some articles explaining it, but none of them go into much detail. Could someone point me to the direction of detailed explanations of shift reduce parsers, like how does it know when to reduce?

Answer 1

The parser is a state machine. Each state has a action table which maps the next input symbol ("token") into an action (shift, reduce a production, error, or accept). For shift actions, there is a transition table which maps the input symbol to the next state. These two tables are usually combined, since there is room in the action table entry for a state number.

Since there are a relatively small number of possible tokens, the tokens are usually represented as small integers and the action table is a two-dimensional array indexed by current state and by input token. If space is a concern, it's possible to compress the tables.