Posts Tagged ‘Parsing’

PostHeaderIcon LR Parser

LR parser is a bottom-up parsing technique that can parse a large class of context-free grammars. The technique used by LR parser is LR(k) parsing where L stands for left-to-right scanning of the input, R means constructing a rightmost derivation in reverse, and k for the number of input symbols of lookahead that are used in making parsing decisions. When (k) is assumed to be 1, LR parsing is attractive for many reasons.

LR parsers can be constructed to recognize almost all programming language constructs for which context-free grammar can be written. They can find syntactic error as soon as it is possible to do so on a left-to-right scan of the input. LR parsing is the most general non-backtracking shift-reduce parsing method and can be implemented as efficiently as other shift-reduce methods. The class of grammars that can be parsed using LR methods is a proper superset of the class of grammars that can be parsed with predictive parsers.

Disadvantage

The main drawback is that it needs a lot of work to construct an LR parser by hand for a programming language grammar. So one requires a LR parser generator.

Related Articles

What is parsing?

PostHeaderIcon What is Parsing?

Parsing

Parsing is a process of analyzing a sentence by taking each word and determining its structure from its constituent parts. Parsing process makes use of two components: a parser and a grammar.

Parser and Grammar

Parser is a procedural component and is nothing but a computer program. Grammar is a declarative component. Parser remains unchanged irrespective of the language being used whereas the grammar changes depending on the language. So, a system can parse a different language by changing the grammar. Both the grammar and parser depend on the grammar formalism.

Related Articles

LR Parsing

Natural Language Processing – An Overview

Machine Translation – An Overview

Tokenization – An Overview

POS Tagging