Building a simple compiler series(5)

LR

LR is a buttom-up parsing algorithm,the L indicate the input is processed from left, and the R indicates that a rightmost derivation is processed from left to right. A buttom-up parser has  two possible actions: the first one is Shift( a terminal from input string to the top of the stack ), the other is Reduce( a string a at the top of the stack to a nonterminal A, given the BNF choice A->a ). So a buttom-up parser is thus sometimes called shift-reduce parser.

LR(0) item

A LR(0) item of a context-free grammar is a production choice with a distinguished position in its right side. In most of books, it will indicate this distinguished position by a period. For eample A->XYZ would generate four produces. A->.XYZ A->X.YZ A->XY.Z and A->XYZ. .  A->.XYZ means we expect a string that can be derivate from XYZ. A->X.YZ means we already get a string that can be derivate from X, and now we expect a string that can be derivate from YZ.

LR(0) item closure

If I is a item collection for grammar G, then CLOSURE(I) follow these two rules to construct item collection from I:

• At first, add all items in I to CLOSURE(I)
• If A->a.Bb in CLOSURE(I), B->c is a production and B->.c is not in the CLOSURE(I), then add it. Repeat it until no one can be added.

GOTO(I,X), I is a item collection and X is a grammar symbol. GOTO(I,X) indicate all the items of [A->aX.b]’s closure corresponding to  all items whose format is [A->a.Xb] in the I .

LR Parsing Alogrithm

Input：A input string and a LR parsing table which describes grammar G , Action function and GOTO function.

Output: If w in the L(G), then it gives the derivation, otherwise it gives a error.