A "left-recursive" grammar means that the parser can get into a loop in the parsing rules without making any progress consuming the input. Imagine that each production is a subroutine that might eat some tokens or call some other subroutines. For example, consider this production:
expr → number '+' number
This means that the expr
parser will first call the number
parser (which might consume some tokens), then try to eat a +
token (and fail if the next token is not of that type) and then call the number
parser again to consume more tokens. If that is all successful, the expr
parser will yield success.
Now consider this left-recursive production:
expr → expr '+' expr
The first thing the expr
parser will do is to call itself recursively, putting itself into an unproductive infinite loop.
In contrast, consider this production, which is not left-recursive:
expr → '(' expr ')'
The first thing the parser will do is try to consume an open parenthesis token, and it will call itself recursively only if that is successful. It can never get into an infinite loop doing this because there are only so many parentheses and it has to eat one each time before it can recurse; eventually it must run out of parentheses and then the recursion will stop. Your Expr = [0-9]+ / '(' Expr ')'
example is similarly safe.
Here is a portion of the left-recursive grammar you showed:
expr → [0-9]+ | sum
sum → expr '*' expr
If the next token is not [0-9]+
, then the expr
parser will call sum
, which will immediately call expr
again, and the parser will be in an infinite loop.
Usually you can rewrite rules like sum
in a non-left-recursive form. In this case it will look something like this:
expr → term more_terms
more_terms → '*' term more_terms | '+' term more_terms | <nothing>
term → [0-9]+ | '(' expr ')'
This is not left-recursive because the more_terms
parser must consume a *
or a +
token before it can call itself recursively; it is impossible for the parser to get into an infinite loop by doing this. Similarly the expr
parser calls term
, but term
will not call back to expr
without consuming a parenthesis.
In general the transformation says to turn a left-recursive grammar like this:
S → S 'p' | 'q'
into a non-left-recursive one like this:
S → 'q' ps
ps → 'p' ps | <nothing>
I don't know if there are any good online resources (I suppose there must be) but if you like Perl, chapter 8 of Higher-Order Perl is available online and discusses precisely this point.
Also, I hope it is not insulting to suggest that you read the Wikipedia article about left recursion, and perhaps the article about recursive descent parsing, which is the name for the technique your parser generator is trying to use.
Rank updates to a matrix are often performed when new data is acquired and needs to be incorporated into a given model.
For example, in the case of regression, in order to compute the coefficient estimates, $\beta$, of linear model, the Normal equations say that we can compute them as $\hat{\beta} = (X^{T}X)^{g}X^{T}y$. If we assume that $X \in R^{n \times p}$ has full column-rank, then $(X^{T}X)^{g} = (X^{T}X)^{-1}$. Now let's say we observe some new samples $x_{n+1},x_{n+2},x_{n+3}... \in R^{p}$, we can define $X^{*} = \begin{bmatrix} X \\ x_{n+1} \\ x_{n+2} \\ ... \end{bmatrix}$. Rather than explicitly computing $(X^{*T}X^{*})^{-1}$, which might be costly if $p$ is large, we can make use of the matrix inversion lemma to simply update $(X^{T}X)^{-1}$ (which we already have stored somewhere from fitting our original model) with our new samples.
Best Answer
The standard form (and example) sections pretty well describe what it is.
It's, well, just another method. However, it is somewhat special in that many other optimization algorithms either use linear programming as part of their solution, or are in reality a specialized solution to a linear programming problem. In fact, integer linear programming is NP-complete, meaning that any problem in NP can be stated as an (integer) linear programming problem.
(this also means solving your typical integer linear programming problem is much more difficult than if we didn't restrict ourselves to integers..)