CHAPTER 3 Flashcards
Construct a CFG for a simple part of a programming language
consists of a set of rules (productions) that describe a language.
Example CFG for arithmetic expressions:
E → E + T | E - T | T
T → T * F | T / F | F
F → ( E ) | id | num
What is a nonterminal symbol? A terminal symbol? A production? A start symbol? A parse tree?
Nonterminal symbol: A variable that can be replaced by other symbols (e.g., E, T, F in the above CFG).
Terminal symbol: A symbol that appears in the final output (e.g., +, *, num).
Production: A rule of the form A → α, where A is a nonterminal, and α is a sequence of terminals and/or nonterminals.
Start symbol: The initial nonterminal from which derivations begin (e.g., E in our CFG).
Parse tree: A hierarchical tree structure representing how a string is derived from the grammar.
What is the left-hand side (LHS) of a production? The right-hand side (RHS)?
LHS: The nonterminal being defined (E → …, here E is the LHS).
RHS: The sequence that replaces the nonterminal (E → E + T | T, here E + T and T are RHS).
Given a grammar G, what is meant by the language L(G)?
The set of all valid strings derivable from the start symbol using the production rules.
Example: If G is the arithmetic expression grammar, then L(G) includes “id + num”, “num * id + num”, etc.
What is a derivation step? A derivation? A leftmost derivation? A rightmost derivation?
Derivation step: Applying one production rule (e.g., E → E + T).
Derivation: A sequence of steps that produces a string from the start symbol.
Leftmost derivation: Always expands the leftmost nonterminal first.
Rightmost derivation: Always expands the rightmost nonterminal first.
How does a derivation correspond to a parse tree?
Each derivation step expands a node in the parse tree.
A leftmost derivation corresponds to a leftmost expansion of the tree.
What does it mean for a grammar to be ambiguous? Unambiguous?
Ambiguous grammar: A string has more than one valid parse tree.
Unambiguous grammar: Each string has a unique parse tree.
What is the difference between an LL and an LR parser?
LL (Left-to-right, Leftmost derivation):
Top-down parsing (predictive parsing).
Looks ahead to decide which production to apply.
Example: Recursive Descent Parser.
LR (Left-to-right, Rightmost derivation):
Bottom-up parsing (shift-reduce).
Constructs the parse tree in reverse.
Example: YACC, Bison parsers.
Difference between LL(1) and LL(2)? LR(1) and LR(2)?
LL(k): Uses k lookahead tokens.
LL(1) uses 1 lookahead (simpler but weaker).
LL(2) uses 2 lookaheads (handles more complex grammars).
LR(k): Similar but for bottom-up parsers.
LR(1) uses 1 lookahead, LR(2) uses 2 lookaheads for shift-reduce decisions.
Why are context-free grammars more powerful than regular expressions?
Regular expressions only define regular languages (no nested structures).
Context-free grammars can describe recursive structures (like nested parentheses).
In what sense are context-free grammars “context-free”?
The rules apply independently of context (i.e., no dependency on neighboring symbols).
