Parser LR

Nell'informatica, un parser LR è un parser di tipo Bottom-up per grammatiche libere da contesto, usate molto di frequente nei compilatori dei linguaggi di programmazione (e degli altri strumenti associati). Un Parser LR legge il proprio input partendo da sinistra (Left) verso destra, producendo una derivazione destra (Rightmost Derivation). A volte questo parser viene anche indicato col nome "Parser LR(k) dove k si riferisce al numero di simboli letti (ma non "consumati") utilizzati per prendere le decisioni di parsing. Tipicamente k ha valore 1 ed è spesso omesso. Una grammatica libera da contesto è chiamata LR(k) se esiste un parser LR(k) adatto ad essa. Nell'uso tipico, quando ci si riferisce a un parser LR significa che si sta parlando di un particolare parser in grado di riconoscere un linguaggio specifico in una grammatica libera da contesto. Non è tuttavia insolito che ci si riferisca a un parser LR intendendo un programma che, fornita una tabella "ad hoc", sia in grado di produrre un ampio numero di LR distinti. Il parsing LR ha parecchi benefici: * Parecchi linguaggi di programmazione possono essere parsificati usando varianti del parser LR. Notevoli eccezioni sono C++ e Perl. * Il parser LR può esser implementato in modo estremamente efficiente. * Tra tutti i tipi di parser che scandiscono il loro input da sinistra verso destra, il parser LR è quello in grado di identificare gli errori sintattici (ovvero quando l'input non è conforme alla grammatica) più rapidamente. Creare un parser LR a mano è parecchio difficile; solitamente essi sono creati usando dei generatori di parser. In base a come la tabella di parsing viene generata, questi parser possono essere anche parser SLR o . Con questi tipi di parser si ha a che fare con un'ampia varietà di grammatiche aumentate; il parser LALR ad esempio è in grado di riconoscere un numero maggiore di grammatiche rispetto ad un SLR. Il famoso Yacc produce parser di tipo LALR.