Handbook of Computer Science(cs) and IT

Parsing

Parsing is a technique to construct a parse (derivation) tree or to check whether there is some left most derivation or right most derivation. Parsing may be classified as.

Top-down Parsing

In this Parsing, start symbol is root, terminals are leaves (inputs symbols) and other nodes are variables. We start from the root and replacing her intermediate nodes one by one from left to right reach the leaves. This approach is also known as recursive descent parsing or predictive descent parsing.

LL Parser is a top-down parser for a subset of the context-free grammars. It parses the input form left to right and constructs a left most derivation of the sentence. LL parser is called an LL (k) parser, if it constructs a left most derivation by looking k symbols ahead.

LL parser consists of

• An input buffer, holding the input string.
• A stack on which to store the terminals and non-terminals from the grammar yet to be parsed.
• A parsing table which tells it what grammar rule to apply given the symbols on top of its stack and the next input token.

Bottom-up Parsing

Bottom-up parser reads the input from left and uses right most derivation in reverse order. Another name of bottom-up parser is shift reduce parser.

LR Grammar

For grammar to be LR, it is sufficient that a left to right shift reduce parser should able to recognize handles when they appear on top of the stack when LR parser is implemented by using a stack. A grammar that can be parsed by an LR parse examining upto ’k’ input symbols (k look ahead symbols) on each move is called an LR (K) grammar.

Point to be Remembered

• For every regular set, there exists a CFG G such that L= L(G).
• Every regular language is a CFL.
• Let G₁ and G₂ be context-free grammar. Then, G₁ and G₂ are equivalent if and only if L (G₁) = L(G₂).
• The Intersection of a context-free language and a regular language is a context-free language.
• The reverse of a context-free language is context-free.
• A DFA can remember only a finite amount of information whereas a PDA can remember an infinite amount of information.
• For every PDA, there is a context-free grammar and for every context-free grammar, there is a PDA.
• If L₁is a DCFL and L₂ is regular then, L₁U L₂ is also DCFL.
• If L₁is a DCFL and L₂ is regular then, L₁∩ L₂ is also DCFL.
• Every regular language is DCFL.
• The Power of non-deterministic pushdown automata and deterministic pushdown automata is not same. But the power of non-deterministic pushdown automata and deterministic push down is same.
• A FSM (Finite State Machine) with one stack is more powerful than FSM without stack.
• If left recursion or left factoring is present, it is not sure that the grammar is ambiguous but there may be chance of ambiguity.

Difference between LL and LR

There is a significant difference between LL and LR grammars. For a grammar to be LR (k), we must be able to recognize the occurance of right side of production having seen all of what is derived from right side with ‘k’ input symbols of look ahead. This requirement of LL (k) grammars is quite different, where we must be able to recognise the use of a production looking only the first ‘k’ symbols of what its right side derives.