含贪婪子规则的LL(1)文法修改后是否仍为LL(1)及分析表咨询

现有一初始LL(1)文法（已补充完整ANTLR4文法定义），原规则drc_parser_start和drc_rules为非重复结构；若将其修改为带ANTLR4贪婪子规则*的形式：

drc_parser_start: layer_def* derived_layer_def* drc_rules*;
drc_rules: VAR_NAME_TWO LEFT_BRACKET (derived_layer_def | check_statement)* RIGHT_BRACKET;

请问：

1. 修改前后两种情况的文法是否均为LL(1)？
2. 若修改后仍为LL(1)，如何编写其语法分析表？

1. 修改前后的LL(1)判定 #

• 修改前：已知原文法是LL(1)，无需额外验证。
• 修改后：是否保持LL(1)取决于原文法中各规则的First集和Follow集是否满足LL(1)核心条件：同一非终结符的不同候选式First集无交集，且若某候选式能推导出ε，则其First集与该非终结符的Follow集无交集。
  具体到修改后的规则：
  • 对于drc_parser_start的layer_def* derived_layer_def* drc_rules*结构：需确保First(layer_def)、First(derived_layer_def)、First(drc_rules)两两无交集；若这些规则能推导出ε，后续规则的First集需与前序非终结符的Follow集无冲突。
  • 对于drc_rules内部的(derived_layer_def | check_statement)*：需确保First(derived_layer_def)与First(check_statement)无交集，同时两者的First集都不包含RIGHT_BRACKET（因为RIGHT_BRACKET属于该循环子规则的Follow集，循环到空时要能正确识别结束括号）。
    只要原文法基础规则满足上述First/Follow集无冲突要求，修改后的文法依然是LL(1)；反之则会失去LL(1)特性。

2. 修改后LL(1)语法分析表的构建方法 #

若修改后文法仍为LL(1)，分析表按以下步骤编写：

步骤1：计算所有非终结符的First集和Follow集 #

• First集：对每个非终结符，递归计算其所有候选式能推导出的首个终结符集合；对于带*的规则（如A*），First集等于First(A)加上ε（因为A*可匹配空串）。
• Follow集：
  • 起始符号drc_parser_start的Follow集为{EOF}（文法起始符号默认包含结束符）。
  • drc_rules内部循环子结构(derived_layer_def | check_statement)*的Follow集是{RIGHT_BRACKET}（紧跟右括号）。
  • 其他非终结符的Follow集按标准LL(1)方法推导：若规则为X → αYβ，则First(β)中除ε外的元素加入Follow(Y)；若β能推导出ε，则Follow(X)的元素加入Follow(Y)。

步骤2：填充分析表单元格 #

分析表是二维表，行代表非终结符，列代表终结符（含EOF）：

• 对于规则A → α：
  1. 遍历First(α)中的每个终结符a，在分析表(A, a)位置填入动作“用α替换A”。
  2. 若ε ∈ First(α)，遍历Follow(A)中的每个终结符b，在(A, b)位置填入动作“用ε替换A”（即跳过该非终结符）。
• 针对带*的规则（如layer_def*），可等价转换为layer_def* → ε | layer_def layer_def*，再按上述规则填充；ANTLR4的贪婪*本质是循环匹配，在分析表中体现为：当前终结符属于First(layer_def)时，匹配layer_def后继续循环；当前终结符属于Follow(layer_def*)时，匹配ε结束循环。

示例：drc_rules的分析表项 #

对于drc_rules: VAR_NAME_TWO LEFT_BRACKET (derived_layer_def | check_statement)* RIGHT_BRACKET;：

• 在(drc_rules, VAR_NAME_TWO)位置填入“用VAR_NAME_TWO LEFT_BRACKET (derived_layer_def | check_statement)* RIGHT_BRACKET替换drc_rules”。
• 对于内部循环子规则：
  • 若当前终结符属于First(derived_layer_def)，填入“用derived_layer_def (derived_layer_def | check_statement)*替换该子规则”。
  • 若当前终结符属于First(check_statement)，填入“用check_statement (derived_layer_def | check_statement)*替换该子规则”。
  • 若当前终结符是RIGHT_BRACKET，填入“用ε替换该子规则”。

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