Derivations and parse trees
Deriving a word from the start symbol, leftmost and rightmost derivations, parse trees, ambiguous grammars and removing ambiguity with precedence levels.
- 31 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- The steps
A few cards from the deck
Derivation: what is it?
Show the answer
A sequence of rewrites that starts from the start symbol and applies one grammar rule at each step, until a word with no non-terminal is reached.
A word belongs to the language if and only if at least one such sequence exists. Each step is written with a double arrow: E ⇒ E + T.
With E → E + T | T, T → T * F | F, F → n, n + n * n is derived leftmost. Which string do we have after three steps from E?
- F + T
- T + T
- n + T
- E + T * F
Show the answer
F + T
E ⇒ E + T ⇒ T + T ⇒ F + T. The third step rewrites the leftmost T into F. T + T has only two steps, n + T has four, and E + T * F comes from a rightmost derivation.
In a … derivation, the leftmost non-terminal is always rewritten; in a … derivation, the rightmost one.
Show the answer
In a leftmost derivation, the leftmost non-terminal is always rewritten; in a rightmost derivation, the rightmost one.
Both build the same tree when the grammar is not ambiguous: only the order of the steps changes.
Leftmost derivation: what is it?
Show the answer
A derivation in which every step rewrites the leftmost non-terminal of the current string.
It fixes the order of rewrites: a parse tree corresponds to exactly one leftmost derivation (and exactly one rightmost one).