- A grammar is ambiguous if a string can be interpreted in two or more ways by using it.
- In natural languages, ambiguity may concern the meaning of a word, the syntax category of a word, or the syntactic structure of a construct. For example, a word can have multiple meanings or it can be both a noun and a verb and a sentence can have more than one syntactic.
- Moreover, In a formal language grammar, the ambiguity would arise if identical strings can occur on the RHS of two or more productions. For example, if a grammar has the Ambiguous GrammarN1 → α
N2 → α
- The string α can derive from or reduced to either N 1 or N2.
- Ambiguity at the level of the syntactic structure of a string would mean that more than one parse tree can build for the string.
<exp> → <id> | <exp> + <exp> | <exp> * <exp>
<id> → a | b | c
- So, Two parse trees can be built for the source string a+b*c according to this grammar – one I which a+b is first reduced to <exp> and another in which b*c is first reduced to <exp>.
- Eliminating ambiguity in the above grammar can be rewritten as
<exp> → <exp> + <term> | <term>
<term> → <term> * <id> | <id>
<id> → a | b | c
Parsing Ambiguous Grammar
- This top-down parsing is non-recursive. LL(1) – the first L indicates input is scanned from left to right. The second L means it uses leftmost derivation for input string and 1 means it uses only input symbol to predict the parsing process.
- The data structure used by LL(1) parser input buffer, stack and parsing table.
- The parser works as follows,
- The parsing program reads the top of the stack and a current input symbol. With the help of these two symbols parsing action can determine.
- Moreover, The parser consults the LL(1) parsing table each time while taking the parsing actions hence this type of parsing method also called table-driven parsing method.
- The input successfully parsed if the parser reaches the halting configuration. When the stack is empty and next token is $ then it corresponds to successful parsing.
- So, Steps to construct LL(1) parser
1. Remove left recursion / Perform left factoring.
2. Compute FIRST and FOLLOW of nonterminals.
3. Similarly, Construct predictive parsing table.
4. Parse the input string with the help of parsing table.