语法分析（二）自顶向下LL(1) parser

发表于 | 分类于

自顶向下语法分析无法parse具有左递归的文法，因此需要首先消除左递归。

1. 左递归消除

  1. 先排个顺序，自小到大将间接左递归（大编号存在指向小编号的边）用小编号的产生式替换了，生成直接左递归。
  2. 对直接左递归进行如下操作
1
2
A -> Abcdefg
  | h

变换成

1
2
3
A -> hA'
A' -> bcdefgA'
   |  epsilon

2. LL(1)表的构造

  • 计算first集合
  • 对可能为epsilon的non-terminal计算follow集合
  • 生成first+集合
  • 生成LL(1)表

2.1. first集合的计算

定义: For a grammar symbol a, FIRST(a) is the set of terminals that can appear at the start of a sentence derived from a.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
for each a ∈ (T∪eof∪ε) {
  First(a) = a;
}
for each a ∈ NT {
  First(a) = 空集;
}
while (First sets 变化) {
  for each production p, where p: A->β {
    if β is β1β2...βk {
      rhs = First(β1) - {ε};
      i = 1;
      while (ε ∈ First(βi) and i <= k - 1) {
        rhs = rhs ∪ (First(βi+1) - {ε});
        i = i + 1;
      }
      if i = k and ε ∈ First(βk) {
        rhs = rhs ∪ {ε};
      }
      First(a) = First(a) ∪ rhs;
    }
  }
}
  • termianl符号的first集合均为自己本身，包括ε，eof符号
  • 非termianl符号的first集合由以自己为head的产生式决定
    • 初始情况为body第一个符号的first集合元素
    • 若当前body符号可为ε，则需要包含下一个body符号的first集合
    • 若每个body符号都可为ε，则需要包含ε

直觉上看，first集合的意义在于匹配lookahead符号。然而若first集合中元素无法匹配lookahead符号但是first集合存在ε时，就需要查看follow集合了。

2.2. follow集合的计算

定义: For a nonterminal $\alpha$, Follow($\alpha$) contains the set of words that can occur immediately after $\alpha$ in a sentence.

  1. Follow(S) = {eof}: 起始符号的follow集合初始化为eof
  2. 对于产生式A $->$ $\alpha$ B $\beta$，除了ε之外First($\beta$)的所有元素都在Follow(B)中
  3. 若A $->$ $\alpha$ B 或者A $->$ $\alpha$ B $\beta$且ε属于First($\beta$)，则所有Follow(A)中元素都在Follow(B)中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for each A ∈ NT {
  Follow(A) = 空集;
}
Follow(S) = {eof};
while (Follow sets 变化) {
  for each production p with form A -> β1β2...βk {
    rhs = Follow(A);
    for i from k to 1 {
      if βi ∈ NT {
        Follow(βi) = Follow(βi) + rhs;
        if ε ∈ First(βi) {
          rhs += {First(βi) - ε};
        } else {
          rhs  = First(βi);
        }
      }
    }
  }
}

2.3. LL(1)表的生成

  • 对每一条产生式 $A->B$ 进行处理
  • 在First(A)中的terminal w，设置T[A, w] = 该产生式
  • 若First(A)含有ε，则对Follow(A)中的terminal w以及可能存在的eof，设置T[A, w] = 该产生式，以及T[A, eof] = 该产生式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
build Fisrt, Follow sets;

for each nonterminal A {
  for each production p with the form A -> β {
    for each terminal w ∈ First(A) {
      Table[A, w] = p;
    }
    if ε ∈ First(A) {
      for each terminal w ∈ Follow(A) {
        Table[A, w] = p;
      }
      if eof ∈ Follow(A) {
        Table[A, eof] = p;
      }
    }
  }
}

2.4. LL(1) parser实现

  • 构造一个parse栈，初始状态为
    • 栈顶：Start符号
    • 栈底：eof
  • 维护两个变量
    • lookahead符号
    • 栈顶待推导符号
  • 推导处理过程：
    1. 待推导符号为terminal：对比和lookahead符号关系
    2. 待推导符号为non-terminal：查表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
word = NextWord(); // lookahead符号
stack.push(eof)
stack.push(Start)
focus = stack.top
loop {
  if focus == eof and word == eof {
    success and break
  }
  else if focus ∈ T or focus == eof {
    // 当前推导符号为terminal
    if focus == word {
      stack.pop();
      word = NextWord();
    }
    else error();
  }
  else {
    // 当前推导符号为non-terminal
    if Table[focus, word] is A -> B1B2...Bk then {
      stack.pop();
      for i from k to 1 {
        if (Bi ≠ ε) stack.push();
      }
    }
    else error();
  }
  focus = stack.top();
}