MENU

【编译原理】LL(1)分析算法

June 2, 2020 • Read: 102 • 编程之路,编译原理

概述

  • 从左(L) 向右读入程序,最左(L)推导,采用一个(1)前看符号
  • LL(1)就是向前只搜索1个符号,即与FIRST集匹配,如果FIRST为空则考虑FOLLOW集

算法基本思想:表驱动的分析算法

LL(1)分析算法

tokens[]; // all tokens
i=0;
stack = [S] // S是开始符号
while (stack != [])
  if (stack[top] is a terminal t)
    if (t==tokens[i++])
       pop();
    else error(…);
  else if (stack[top] is a nonterminal T)
    pop()
    push(table[T, tokens[i]])

LL(1)分析表的构造

  • 前提:$NULLABLE$集、$FOLLOW$集
  • 表头:行首是终结符,列首是非终结符,在非终结符 与 FIRST_S集合对应的终结符的交汇处标记上编号。
  • 填写规则:$k: N -> β_1...β_n \ \ \ \{x_1, x_2, ..., x_n\}$,就在表的$(N, x_i),i = 1,2,...,n$上标记k。

案例1:

0: S -> N V N    # {s, t, g, w}
1: N -> s      # {s}
2:    | t      # {t}
3:    | g      # {g}
4:    | w      # {w}
5: V -> e      # {e}
6:    | d      # {d}

例如:对于0: s -> N V N对应的FIRST_S集合是{s, t, g, w}就在(S,s)、(S,t)、(S,g)、(S,w)上标记0,5: V-> e对应的FIRST_S集合是{e},(V, e)标5,6: V -> d对应的FIRST_S集合是{d},(V, d)标6。

NTstgwed
S0000  
N1234  
V    56
栈顶    待预测的串sdt
$ N V N   ●sdt$
$ N V      dt$
$ N      t$
$      $

案例2:

0: Z -> d      # {d}
1:    | X Y Z    # {a, c, d}
2: Y -> c     # {c}
3:    |     # {a, c, d}
4: X -> Y     # {c, a, d}
5:    | a     # {a}
NTacd
Z110, 1
Y32, 33
X4, 544

LL(1)分析表中的冲突

案例3:

稍微修改下文法,加入第5行。

0: S -> N V N    # {s, t, g, w}
1: N -> s      # {s}
2:    | t      # {t}
3:    | g      # {g}
4:    | w      # {w}
5:    | w V   # {w}
6: V -> e      # {e}
7:    | d      # {d}

LL(1)分析表 如下:

NTstgwed
S0000
N1234, 5
V 56

冲突检测: 对N的任意两条产生式规则N->βN->γ,要求FIRST_S(β) ∩ FIRST_S(γ) ={}

通过LL(1)分析表可以很明显的看出 案例2和案例3存在冲突,并且可以很容易看出,是哪两行、对哪一个非终结符存在冲突。

LL(1)分析表冲突处理

一、存在左递归 —— 消除左递归

左递归的分类:

  • 直接左递归:P → Pa
  • 间接左递归:P → Aa, A → …… → Pb

1. 直接左递归的消除

  • 对于 P → Pa | b 形式(b可为空),可以知道,推导结束的时候一定有一个b在最开始位置(如ba),后面是无数多个a,所以可以归纳得出如下的消除方法
P  →  bP';
P'  →  aP' | ε;
  • 更一般化的形如P → PX|Y(其中X和Y看作一个整体,比如:P → Pabc|ab|b,X就是abc,Y就是ab|b),可以归纳成如下形式:
X → abc
Y → ab|b
P  →  YP';        :P  →  abP' | b P'
P'  →  XP' | ε;   : P'  →  abcP' | ε

2. 间接左递归的消除

  • 对于P → Aa | x1, A → …… → Pb | x2的形式
  • 消除规则

    • ① 若消除过程中出现了直接左递归,就按照直接左递归的方法,来消除
    • ② 若产生式右部最左的符号是非终结符,且这个非终结符序号大于等于左部非终结符,则暂不处理(后面会处理到)
    • ③ 若序号小于左部的非终结符,则用之前求到的式子的右部来替换
  • 步骤伪代码

    • 1.把文法G的所有非终结符按任意顺序排列,并编号
    • 2.按顺序对非终结符进行遍历
    • 3.将当前处理的非终结符中的序号小于等于它的非终结符按规则③进行替换(序号大于的按规则②处理)
    • 4.消除i序号的非终结符的直接左递归(如果存在的话)
    • 5.删除其中不可达的非终结符(从开始符开始,无法再推出的非终结符)

注意:

  • 第一步对非终结符进行排序的序列不同,最后结果的产生式有可能不同,但它们是等价的
  • 开始符号不能改变
  • 该算法,能同时消除直接、间接左递归

3. 案例:

存在如下文法,消除左递归

  • S → Qc | c
  • Q → Rb | b
  • R → Sa | a

解:

  1. 把文法G的所有非终结符按任意顺序排列,并编号: 1 R、2 Q、3 S
  2. 按上面的排列顺序,对这些非终结符进行遍历:
  3. 将当前处理的非终结符中的序号小于它的非终结符按规则 ③ 进行替换(序号大于等于的按规则 ② 处理)
R:
R的右部中的非终结符有S;
S的下标大于R,可以暂时不处理;
所以此时R改写为:R  →  Sa | a

----------------------------------------------
Q:
Q的右部中的非终结符有R;
R的下标小于Q,将R的右部替换进来;
所以此时Q改写为:Q  →  Sab | ab | b;
S的下标大于Q,可以暂时不处理;
所以此时Q改写为:Q  →  Sab | ab | b;

-----------------------------------------
S:
S的右部中的非终结符有Q;
Q的下标小于S,将Q的右部替换进来;
所以此时S改写为:S  →  Sabc |abc | bc | c
S的下标等于S,可以暂时不处理;
所以此时S改写为:S  →  Sabc |abc | bc | c
  1. 消除直接左递归(如果存在的话)
S  →  Sabc |abc | bc | c
∴ X = abc,Y = abc | bc | c
∴ 消除直接左递归的结果是:
S  →  abcS' | bcS' | cS'
S'  → abcS' | ε
  1. 删除其中不可达的非终结符,这里就是Q、R了
S  →  abcS' | bcS' | cS'
S'  → abcS' | ε

二、存在左公因子 —— 提取左公因子

文法

0: X -> a Y
1:    | a Z
2: Y -> b
3: Z -> c
 
//修改后:
0: X -> a X’
1: X’-> Y
2:    | Z
3: Y -> b
4: Z -> c

缺点

能分析的文法类型受限、往往需要文法的改写(冲突处理)。解决:→ LR分析算法

- - - 结束 - - -
  • 文章标题:【编译原理】LL(1)分析算法
  • 文章链接:https://blog.canye365.cn/archives/332.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )
  • Last Modified: April 11, 2021