For example, the following grammar will never stop deriving a complete sentence:
S -> A b
A -> a A
Some other CFGs can derive a complete sentence, but it still is possible to wind up in a infinite loop, e.g.
S -> A b | b
A -> a A
Currently I am writing a LR parser generator. If it doesn't check if the input CFG is invalid like that, the generated parser will just trapped in a loop forever. I tested Bison and it can successfully detect such invalid grammar, how does it do it?
There seem to be some faulty premises here. Those CFGs are not invalid. Grammars themselves don't have a notion of "infinite loop" or "never stop deriving". They either derive a sentence or don't, it's yes or no. In other words, the sentence is either in the language generated by that CFG or it isn't, yes or no. Anything about infinite loops is about a particular parser. There are many ways to parse the same grammar. A correct parsing algorithm will not enter an infinite loop.
Perhaps you are asking whether a given grammar has any derivation of the form $A \stackrel{*}{\Rightarrow} \cdots A \cdots$, i.e., $A$ derives some string that includes $A$. I'm guessing this is what you mean when you talk about "infinite loops". It is possible to test this by building an appropriate directed graph and testing whether the resulting graph has any cycles (e.g., by checking whether it can be topologically sorted). In particular, the graph has a vertex for each non-terminal and an edge $A \to B$ whenever the grammar has a production $A \to \cdots B \cdots$, i.e., a production rule where the left-hand side is $A$ and $B$ appears in the right-hand-side.
You shouldn't need to reduce a grammar in order to apply an LR parsing algorithm. Provided that the grammar is LR parsable (i.e. it has no parsing conflicts), the generated parser should execute without falling into an endless loop.
What bison does is to remove non-productive and non-reachable rules. Although not necessary, it's useful, in part because such rules are almost certainly an indication of a bug in the grammar specification, and in part because it reduces the size of the grammar.
The algorithm uses a workqueue which contains tuples consisting of a production and a point, rather similar to the LR(0) items in the LR algorithm. It also maintains a registry of reachable non-terminals. The output is a new reduced grammar whose non-terminal set and production sets are subsets of the original sets. We assume that there is an O(1) mechanism to determine if a non-terminal appears in the non-terminal set of the new grammar.
The algorithm can be implemented in time and space linear to the size of the grammar.
Initially, the Start symbol is marked as reachable and all of its productions are placed into the workqueue with their points at the beginning. The workqueue is then processed in order; for each item in the queue:
Once the workqueue has been fully scanned, if it still contains productions, it is scanned again, until a complete scan completes without adding any new productions to the reduced grammar. (Subsequent scans only need to consider items whose points immediately precede a non-terminal newly added to the reduced grammar. That optimisation is needed to ensure that the algorithm runs in linear time, although in practice the extra bookkeeping is not really worthwhile.)
There is a remarkable similarity of the above algorithm with the algorithm to identify nullable non-terminals. The only difference is the handling of terminal symbols. When the scan encounters an item whose point immediately precedes a terminal symbol, it removes the production from the workqueue instead of moving the point over the terminal symbol. Thus, the same function can be used for both analyses, with an additional parameter indicating the handling of terminals.
