Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· OpenAIAi2 WildChat-4.8M (AI2)

计算follow函数的伪代码

  1. User

    计算follow函数的伪代码

  2. Assistant
    1. 初始化所有非终结符的follow集为∅。
    2. 对于文法的开始符号S,将“$”加入到其follow集中。
    3. 对于文法中每一个右部含有非终结符A的产生式A → αBβ,按照如下规则将follow(B)的集合加入到follow(A)中:
      • 如果β能够推出ε,则将follow(B) – {ε}加入到follow(A)中。
      • 如果β不能推出ε,则将follow(B)加入到follow(A)中。
    4. 重复步骤3,直到不再有follow集合发生变化。
    5. 输出每个非终结符的follow集合。

    注意事项:

    • 在步骤3中,如果B是产生式的最后一个符号,则将follow(A)加入到follow(B)中。
    • ε代表空串。
  3. User

    构建预测分析表的伪代码

  4. Assistant
    1. 初始化预测分析表M为一个二维数组,行表示文法中的所有非终结符,列表示所有可能的终结符和$符号。
    2. 对于每个非终结符A,找到A可以生成的所有产生式A → α,并按照以下步骤处理:
      • 对于每个终结符a,如果a ∈ FIRST(α),则将该产生式加入到M[A, a]中。其中FIRST(α)表示α的FIRST集合。
      • 如果ε ∈ FIRST(α),则对于每个b ∈ FOLLOW(A),将该产生式加入到M[A, b]中。其中FOLLOW(A)表示A的FOLLOW集合。
      • 如果ε ∈ FIRST(α)且∈FOLLOW(A),则将该产生式加入到M[A,∈ FOLLOW(A),则将该产生式加入到M[A,]中。
    3. 如果M中有冲突或某些项为∅,表明该文法不是LL(1)文法,无法构建预测分析表。
    4. 输出预测分析表M。

    注意事项:

    • 在步骤2中,如果α可以推出ε,则需要将Follow(A)的所有元素都加入进分析表中。如果α不能推出ε,则只需要将FIRST(α)的所有元素都加入进分析表中。
    • 在步骤2中,如果α可以推出ε,则需要将M[A, b]中的所有产生式也加入M[A, b]中,其中b为Follow(A)的元素。