求指导：计算器语言文法的First集与Follow集计算纠错

Alright, let's work through this step by step. First, I'll fill in the obvious missing pieces of your grammar (since your snippet cut off mid-production for term—I'll assume standard calculator grammar conventions for the factor tail and operators, which makes sense for a calculator language). Then we'll compute First and Follow sets properly, and highlight the common pitfalls where folks usually mess up Follow sets.

Step 1: Complete Grammar (Assumed) #

First, let's formalize the full grammar with reasonable completions for the truncated parts:

program → stmt_list $$$
stmt_list → stmt stmt_list | ε
stmt → id = expr | input id | print expr
expr → term term_tail
term_tail → add_op term term_tail | ε
term → factor factor_tail
factor_tail → mul_op factor factor_tail | ε
factor → id | num | ( expr )

// Where:
// add_op = + | -
// mul_op = * | /
// $$$ = end-of-program marker

Step 2: Calculating First Sets #

First sets are straightforward—they're the set of terminal symbols that can start any string derived from a non-terminal. Here's the breakdown:

• First(program): Derives from stmt_list $$$. Since stmt_list can produce ε, we include First(stmt_list) and $$$. Result: { id, input, print, $$$, ε }
• First(stmt_list): Can be ε or start with any stmt. Result: { id, input, print, ε }
• First(stmt): Has three alternatives, all starting with distinct terminals. Result: { id, input, print }
• First(expr): Starts with whatever term starts with (since term can't be ε). Result: { id, num, ( }
• First(term_tail): Can be ε or start with an add_op. Result: { +, -, ε }
• First(term): Starts with whatever factor starts with (since factor can't be ε). Result: { id, num, ( }
• First(factor_tail): Can be ε or start with a mul_op. Result: { *, /, ε }
• First(factor): Directly maps to its terminal alternatives. Result: { id, num, ( }

Step 3: Calculating Follow Sets (The Tricky Part) #

Follow sets are the terminals that can appear immediately after a non-terminal in a valid derivation. Let's use the standard rules and call out common mistakes as we go:

Key Rules to Remember #

1. For the start symbol (program), its Follow set is empty here—since it's followed directly by $$$ (a terminal end marker) in its only production.
2. If you have A → αBβ, add all non-ε symbols from First(β) to Follow(B). If First(β) includes ε, add all symbols from Follow(A) to Follow(B).
3. If you have A → αB, add all symbols from Follow(A) to Follow(B).

Follow(program)

• No symbols come after program in any valid derivation. Result: ∅

Follow(stmt_list)

• Used in program → stmt_list $$$: Add $$$ to its Follow set.
• Used in stmt_list → stmt stmt_list: Since the right-hand side ends with stmt_list, we add Follow(stmt_list) to itself (no new symbols here).
  Result: { $$$ }

Follow(stmt)

• Used in stmt_list → stmt stmt_list: Add First(stmt_list) - {ε} ({ id, input, print }) to its Follow set. Since First(stmt_list) includes ε, also add Follow(stmt_list) ({ $$$ }).
  Result: { id, input, print, $$$ }

Follow(expr)

• Used in stmt → id = expr and stmt → print expr: Both end with expr, so add Follow(stmt) ({ id, input, print, $$$ }).
• Used in factor → ( expr ): The ) comes right after expr, so add ) to its Follow set.
  Result: { id, input, print, $$$, ) }

Follow(term_tail)

• Used in expr → term term_tail: Ends with term_tail, so add Follow(expr) ({ id, input, print, $$$, ) }).
  Result: { id, input, print, $$$, ) }

Follow(term)

• Used in expr → term term_tail: Add First(term_tail) - {ε} ({ +, - }). Since First(term_tail) includes ε, also add Follow(expr) ({ id, input, print, $$$, ) }).
  Result: { +, -, id, input, print, $$$, ) }

Follow(factor_tail)

• Used in term → factor factor_tail: Ends with factor_tail, so add Follow(term) ({ +, -, id, input, print, $$$, ) }).
  Result: { +, -, id, input, print, $$$, ) }

Follow(factor)

• Used in term → factor factor_tail: Add First(factor_tail) - {ε} ({ *, / }). Since First(factor_tail) includes ε, also add Follow(term) ({ +, -, id, input, print, $$$, ) }).
• Used in factor_tail → mul_op factor factor_tail: Add First(factor_tail) - {ε} ({ *, / }) and (since First(factor_tail) has ε) add Follow(factor_tail) (which is same as Follow(term)—no new symbols here).
  Result: { *, /, +, -, id, input, print, $$$, ) }

Common Mistakes You Might Have Made #

1. Missing Follow set propagation for nullable β: This is the biggest one. For example, in expr → term term_tail, since term_tail can be ε, you must add Follow(expr) to Follow(term)—not just First(term_tail). Many people forget this step.
2. Overlooking parentheses: In factor → ( expr ), the closing ) must be added to Follow(expr). It's easy to miss this if you only focus on top-level statements.
3. Incorrect start symbol Follow set: Since program is followed directly by $$$ (a terminal), its Follow set is empty—not including $$$. If you added $$$ to Follow(program), that's a mistake.
4. Recursive production confusion: For stmt_list → stmt stmt_list, the Follow set of the recursive stmt_list is the same as the parent stmt_list's Follow set. You don't need to loop here—just inherit the set from where stmt_list is used in program.

内容的提问来源于stack exchange，提问作者Felauras