Ambiguity in Grammars [PYQ 2023, 2024]

A grammar is ambiguous if there exists at least one string that has two or more distinct parse trees (or equivalently, two or more distinct leftmost/rightmost derivations). Ambiguity is a property of the grammar, not the language -- an ambiguous grammar may generate a language that also has an unambiguous grammar.

Classic Example: Dangling Else [PYQ 2023]

Consider the grammar for conditional statements:

$S \to \text{if } E \text{ then } S \mid \text{if } E \text{ then } S \text{ else } S \mid a$

For the string if E then if E then a else a, there are two valid parse trees depending on whether the else associates with the inner or outer if. Most languages resolve this by adopting the rule that else associates with the nearest unmatched if.

Resolving Ambiguity: There are three common strategies:

1. Rewrite the grammar to be unambiguous (often makes the grammar large and unnatural).
2. Use precedence and associativity rules to impose an ordering on operators.
3. Use specialized parsers like the Operator Precedence Parser that inherently encode precedence.

Two Parse Trees for an Ambiguous Expression

Consider the ambiguous grammar $E \to E + E \mid E * E \mid id$ and the string $id + id * id$.

The string $id + id * id$ has two parse trees: one where + is evaluated first (incorrect) and one where * is evaluated first (correct). This ambiguity is exactly what precedence rules resolve.

In the absence of precedence rules, both parse trees are equally valid, making the grammar ambiguous. The Operator Precedence Parser and YACC precedence directives both resolve this by ensuring * binds tighter than +.

Operator Precedence Parser [PYQ 2023, 2024]

Most parsers (LL, LR) absolutely cannot parse ambiguous grammars. The Operator Precedence Parser is the exception [PYQ 2024]. It is a Bottom-Up (Shift-Reduce) parser specifically designed to evaluate mathematical expressions, even if the grammar is ambiguous (like $E \to E + E \mid E * E \mid id$).

What is an Operator Grammar? A grammar is an operator grammar if it has two properties:

1. No $\epsilon$ (empty) productions on the right-hand side of any rule.
2. No two Non-Terminals are adjacent on the right-hand side of any rule (e.g., $A \to BC$ is invalid; $A \to B \text{ op } C$ is valid).

These restrictions ensure that every production contains at least one terminal (operator), which allows us to define precedence relations purely between terminals.

How it works: Instead of using complex DFA state machines, it uses mathematical precedence relations between terminal symbols (operators):

• $a \lessdot b$ : $a$ yields precedence to $b$ (the operator on the stack has lower precedence, so we shift)
• $a \gtrdot b$ : $a$ takes precedence over $b$ (the operator on the stack has higher precedence, so we reduce)
• $a \doteq b$ : $a$ has the same precedence as $b$ (same precedence level; associativity decides shift vs reduce)

If the parser sees $id + id * id$, it compares + and *. Since + $\lessdot$ *, it shifts the * onto the stack, ensuring multiplication is evaluated (reduced) first.

Precedence Relation Table

For a grammar with operators +, *, terminals id, and the end marker $, the precedence relation table is:

Reading the table: To decide between shift or reduce, find the row for the topmost terminal on the stack and the column for the next input symbol. If the relation is $\lessdot$, shift. If $\gtrdot$, reduce. If $\doteq$, shift or reduce depending on associativity. If no relation exists, it is a syntax error.

Note that + $\lessdot$ * (row +, column *) confirms that * has higher precedence -- when + is on the stack and * is next, we shift. Conversely, * $\gtrdot$ + (row *, column +) confirms that when * is on the stack and + is next, we reduce the * first.

YACC (Yet Another Compiler Compiler) [PYQ 2022]

YACC is an industry-standard UNIX tool used to automatically generate C code for a parser.

• Underlying Algorithm: YACC internally uses the LALR(1) parsing algorithm.
• Input/Output: It takes a file containing a Context-Free Grammar (usually with .y extension) and outputs a C program (y.tab.c) containing the parsing table and the shift-reduce logic.
• Lexical Integration: YACC does not scan tokens itself. It is designed to work perfectly alongside Lex (which outputs lex.yy.c). YACC repeatedly calls yylex() to fetch the next token.

Structure of a YACC File: A standard YACC program is strictly divided into three sections separated by %%:

1/* 1. DEFINITIONS SECTION */
2%token ID NUM
3%left '+' '-'
4%left '*' '/'
5%%
6
7/* 2. RULES SECTION (The Context Free Grammar) */
8expr : expr '+' expr  { $$ = $1 + $3; }
9     | expr '*' expr  { $$ = $1 * $3; }
10     | NUM            { $$ = $1; }
11     ;
12%%
13
14/* 3. USER SUBROUTINES (C Code) */
15int main() {
16    yyparse(); // Starts the parser
17    return 0;
18}
19void yyerror(char *s) {
20    printf("Syntax Error");
21}

Precedence Directives in YACC

YACC provides three precedence directives to resolve shift-reduce conflicts:

Conflict Resolution Mechanism: When YACC encounters a shift-reduce conflict, it compares the precedence of:

• The terminal that would be shifted (the look-ahead token)
• The production that would be reduced (whose precedence is set by its rightmost terminal, or by a %prec override)

If the shift terminal has higher precedence, YACC shifts. If the reduce production has higher precedence, YACC reduces. If they have equal precedence, the associativity directive decides: %left causes a reduce, %right causes a shift, %nonassoc causes an error.

Semantic Actions and Pseudo-Variables

In YACC rules, semantic actions are C code enclosed in { } that execute when a production is reduced. YACC provides pseudo-variables:

For example, in the rule expr : expr '+' expr { $$ = $1 + $3; }, $1 holds the value of the first expr, $3 holds the value of the second expr, and $$ is assigned the sum. The values are stored in a value stack parallel to the parsing stack, and their type is controlled by the %union declaration.