I read the question and answer at Number of nodes of a parse tree when the Grammar is in CNF?, and I'm curious about a related matter: obviously with a unrestrained LR grammar (as opposed to CNF) the relationship between input length and the number of parse tree nodes depends on both the grammar and the input string, but intuitively, it seems to me (please correct me if I'm wrong) there must some linear upper-bound formula derivable from the grammar such that given n input tokens, the number of parse tree nodes needed will be no more than some linear function of n.
It also seems to me with "wider" productions should make it go less steep compared to the CNF case, but then you could have, in your grammar, production chains such as A -> B; B -> C; C -> D; D -> someTerminal that could end up adding a whole bunch of nodes without consuming input, thereby possibly making the upper bound formula more steep? Is there an algorithm for analyzing grammars to figure out such an upper-bound formula?
