|
|
Dictionary definition: LR parsing
- Article from:
- A Dictionary of Computing
- Author:
Copyright© A Dictionary of Computing 2004, originally published by Oxford University Press 2004. (Hide copyright information)
|
LR parsing
A
bottom-up parsing
technique, LR standing for
L
eft-to-right
R
ightmost derivation sequence. Originally developed by D. E. Knuth, it is the most powerful left-to-right, no backtracking parsing method for
context-free grammars
.
An LR parser consists of a pushdown stack, a parsing table, and a driving routine. The driving routine is the same for all grammars. The stack is manipulated by the driving routine using the information contained in the top stack element and the next
k
symbols in the input stream (called the
k lookahead
);
k
is an integer ≥0, but for most practical purposes
k
= 1. The stack consists of a string
s
0
X
0
s
1
X
1
…
s
n
X
n
s
n+1
where each
X
i
is a symbol of the ...