Context-Free Grammars

Ambiguity means the grammar admits two distinct parse trees for one string, so the tree — and therefore the meaning the string denotes — is not fixed by the grammar alone. Two conforming parsers may legitimately disagree.

Both rewrite the same nonterminal occurrences by the same rules, but in a different order: a leftmost derivation always rewrites the leftmost nonterminal of the current line, a rightmost derivation always the rightmost one. The intermediate lines differ; the rule applications do not.

The stack is memory that grows with the input, so the machine can match nesting of any depth: push a marker on every opener, pop and compare on every closer, and accept a run whose store ends exhausted.

Split the alternatives: replace A -> A alpha | beta with A -> beta A2 and A2 -> alpha A2 | empty. The recursive part becomes a repeating tail, so the parser consumes the leading beta before re-entering and the recursion terminates.

Because the grammar lets a conditional be a statement with or without an else, the single else can attach to either if, giving two trees. Implementations settle it by convention — nearest unmatched if — and a grammar-level fix splits statements into matched and unmatched forms.

One stack holds one live count and spending it destroys it. Matching the b's pops away the record of how many a's there were, so nothing remains to check the c's against, and two independent matched counts are beyond the model.

Split the single expression rule into one layer per precedence level — expression, term, factor — so a tighter operator is reachable only by descending. Recurse on the left for left-associative operators and on the right for right-associative ones.

A repetition group becomes a fresh nonterminal with two productions: one that consumes a single occurrence and recurses, and one empty alternative that ends the chain. The sugar disappears, the language stays the same.

A parse tree records which production was applied to which symbol occurrence, not the order the rewrites happened in. Many derivations that differ only in ordering describe the same parent-child structure, so they draw one tree.

Accepting by empty stack ends a successful run with the store exhausted, wherever the control sits; accepting in a final state ends it in a designated state, whatever the store holds. For machines that may guess, the two conventions describe the same languages.

A predictive parser chooses an alternative from the next token alone, and both alternatives start with the same one, so the choice is undecidable at that point. Left factoring pulls the shared prefix out and defers the decision until the rules differ.

A deterministic machine must commit at every step, and some languages hide the point where pushing should turn into popping. Even-length words that read the same both ways carry no midpoint marker, so only a machine allowed to guess accepts them.

Look for indirect recursion: a cycle in the can-begin-with relation, where one nonterminal's first symbol is another that eventually leads back. Substitute the intermediate rules inline until the recursion becomes direct, then apply the usual tail rewrite.

Choose the single intended reading deliberately, then make it unforgeable: pin it in the grammar, re-parse every stored rule to find the subset whose two trees differ, review that subset with its owners, and version the language rather than rewriting meanings silently.

Treat depth as untrusted input: measure the deepest legitimate document, set a limit with headroom above it, check it at the push rather than waiting for memory to run out, reject over-deep input with a distinct reason, and publish the number as part of the format contract.

Decide by who reads the rules. If the rule set is a published specification, keep it as authored and let a parser family that accepts left recursion consume it; if it is an internal input to one tool, rewrite it and treat the transformed form as generated output.

Deciding whether an arbitrary context-free grammar is ambiguous is undecidable, so no checker can be both sound and complete. Tools instead search for a witness string, which can only ever find ambiguity, or restrict the grammar to a class whose successful construction proves uniqueness.

Writing out a derivation of the string from the start symbol proves it belongs to the language the grammar defines, so a validator that rejects it disagrees with the specification. Failing to find a derivation proves nothing by itself.

Union needs only one decision at the start: a machine that guesses which of two machines to run accepts exactly their union. Intersection would need two stores at once, and a counterexample settles it - two languages whose intersection demands three equal blocks.

Every production must become two nonterminals or one terminal, so empty and unit productions go, long right-hand sides are split by invented nonterminals, the rule set grows, and the trees the parser returns no longer match the rules anyone authored.