一、LL(1)分析法

LL(1) 分析法又称预测分析法 ,是 一种不带回溯的非递归自上而下分析法。

在这里插入图片描述


二、LL(1)分析器

在这里插入图片描述

三、LL(1)分析表

在这里插入图片描述

四、LL(1)文法:分析表M不含多重定义入口的文法

在这里插入图片描述

1、一个LL(1)文法所定义得语言恰好就是它的分析表所能识别的全部句子。

2、一个上下文无关文法是LL(1)文法的充要条件(判断一个文法是否是LL(1)文法):对每一个非终结符A的任何两个不同的产生式A→α|β,有下面条件(都是避免了多重入口)成立
(1)FIRST(α) ∩ FIRST(β) = ∅:A 的每个候选是都不存在相同的首字符
(2)假若β ⇒ ∗ \stackrel{*}\Rightarrow ε,则有FIRST(α) ∩ FOLLOW(A) = ∅:避免了在分析表同一栏目内出现A→αA→ε的情况。

五、给出算术表达式文法求某输入串的分析过程求解步骤

1、消除左递归(可利用数学中的分配律)
  • 形如 A → Aα∣β 其中,α、β是任意的符号串且 β 不以 A 开头。这时,可将 A 的产生式改写为右递归形式: { A → β A ′ A ′ → α A ′ ∣ ε \begin{cases} A→βA' \\ A'→αA'| ε \end{cases} {AβAAαAε
  • 一般的,A → A α 1 α_{1} α1∣A α 2 α_{2} α2∣…∣A α m α_{m} αm β 1 β_{1} β1 β 2 β_{2} β2∣…∣ β n β_{n} βn { A → β 1 A ′ ∣ β 2 A ′ ∣ … ∣ β n A ′ A ′ → α 1 A ′ ∣ α 2 A ′ ∣ … ∣ α m A ′ ∣ ε \begin{cases} A→\beta _{1} A'∣\beta _{2}A'∣…∣\beta _{n}A' \\ A'→α_{1} A'∣α_{2}A'∣…∣α_{m}A'∣ε \end{cases} {Aβ1Aβ2AβnAAα1Aα2AαmAε
消除一切左递归

在这里插入图片描述

2、消除回溯
  • 回溯产生的原因:候选式存在公共的左因子

  • 一般的,设文法中关于 A 的产生式为A → δ β 1 β_{1} β1∣δ β 2 β_{2} β2∣…∣δ β i β_{i} βi γ 1 \gamma_{1} γ1∣…∣ γ j \gamma_{j} γj那么,可以把这些产生式改写为: { A → δ A ′ ∣ γ 1 ∣ . . . ∣ γ j A ′ → β 1 ∣ … ∣ β i \begin{cases} A→δA'∣\gamma_{1}∣... |\gamma_{j}\\ A'→\beta _1|…|\beta_i \end{cases} {AδAγ1...∣γjAβ1βi

    ① 提取公共左因子:A → δ( β 1 β_{1} β1 β 2 β_{2} β2∣…∣ β i β_{i} βi)∣ γ 1 \gamma_{1} γ1∣…∣ γ j \gamma_{j} γj
    ② 将产生式中由 “(”“)” 括起的部分以非终结符 A' 命名则得到上述结果。

3、求解文法的FIRST集和FOLLOW集(方法:https://blog.csdn.net/qq_43717303/article/details/110210180
4、构造LL(1)分析表
  • 首先求出每个非终结符的 FIRST 和FOLLOW 集
  • 然后按以下四个步骤构造分析表
    ①对文法 G 的每个产生式 A → α执行 ② 和③ 步;
    ②对每个终结符 a ∈ FIRST(A),把 A → α 加至 M[A, a]中,其中 α 为含有首字符 a 的候选式或唯一的候选式
    ③若ε ∈ FIRST(A),则对任何 b ∈ FOLLOW(A) 把 A → ε 加至 M[A, b]中
    ④把所有无定义的 M[A,a]标“出错 标志”。
5、若预测分析表 M 含有多重定义入口冲突项,则该文法不是LL(1)文法。遵从就近匹配原选定唯一候选式得到无二义的LL(1)分析表。
6、输入串分析过程:分析开始时栈底先放入一个“#”,然后再压入文法的开始符号;当分析栈中仅剩“#”,输入串指针也指向串尾的“#”时,分析成功
符号栈输入串所用产生式
符号栈当前输入符号输入串说明
符号栈当前输入符号输入串所用产生式说明

六、例题

算术表达式文法如下,试给出输入串 i 1 i_{1} i1* i 2 i_{2} i2+ i 3 i_{3} i3的分析过程。

G[E]: E → E+T|T
	  T → T*F|F
	  F → (E)|i

解:
1、文法G[E]消除左递归得

G'[E]: E  → TE'
	   E' → +TE'|ε
	   T  → FT'
	   T' → *FT'|ε
	   F  → (E)|i

2、求FIRST集和FOLLOW集

FIRST(E) = {(,i}
FIRST(E') = {+,ε}
FIRST(T) = {(,i}
FIRST(T') = {*,ε}
FIRST(F) = {(,i}

FOLLOW(E) = {#,)}
FOLLOW(E') = {#,)}
FOLLOW(T) = {+,#,)}
FOLLOW(T') = {+,#,)}
FOLLOW(F) = {*,+,#,)}

3、 算术表达式的LL(1)分析表

i+*()#
EE → TE’E → TE’
E’E’ → +TE’E’ → εE’ → ε
TT → FT’T → FT’
T’T’ → εT’ → *FT’T’ → εT’ → ε
FF → iF → (E)

4、输入串 i 1 i_{1} i1* i 2 i_{2} i2+ i 3 i_{3} i3的分析过程:除第一次出现外将 弹出栈顶符号 X 将M[X,x]中 A → ? 的 ? 逆序压栈 简化语言为 弹出 X 将 ? 逆序压栈 / 压栈

符号栈当前输入符号输入串所用产生式说明
#E i 1 i_{1} i1* i 2 i_{2} i2+ i 3 i_{3} i3##、E先后进栈
#E’T i 1 i_{1} i1 i 1 i_{1} i1* i 2 i_{2} i2+ i 3 i_{3} i3#E → TE’ 弹出栈顶符号 E,将M[E,i]中 E → TE’的TE’逆序压栈
#E’T’F i 1 i_{1} i1 i 1 i_{1} i1* i 2 i_{2} i2+ i 3 i_{3} i3#T → FT’弹出 T,将 FT’ 逆序压栈
#E’T’i i 1 i_{1} i1 i 1 i_{1} i1* i 2 i_{2} i2+ i 3 i_{3} i3#F → i弹出 F,将 i 压栈
#E’T’ i 1 i_{1} i1* i 2 i_{2} i2+ i 3 i_{3} i3# 匹配,弹出栈顶符号 i 并读出输入串的下一个输入符号 *
#E’T’F*** i 2 i_{2} i2+ i 3 i_{3} i3#T’ → *FT’弹出 T’,将 i 压栈 *FT’ 逆序压栈
#E’T’F** i 2 i_{2} i2+ i 3 i_{3} i3#匹配,弹出栈顶符号 * 并读出输入串的下一个输入符号 i 2 i_{2} i2
#E’T’ i i 2 i_{2} i2 i 2 i_{2} i2+ i 3 i_{3} i3#F → i弹出 F,将 i 压栈
#E’T’ i 2 i_{2} i2 i 2 i_{2} i2+ i 3 i_{3} i3#匹配,弹出栈顶符号 i 并读出输入串的下一个输入符号 +
#E’++ i 3 i_{3} i3#T’ → ε弹出 T’, 因M[T,+]中为T’ → ε,故不压栈
#E’T+++ i 3 i_{3} i3#E’ → +TE’弹出 E’,将 +TE’ 逆序压栈
#E’T++ i 3 i_{3} i3#匹配,弹出栈顶符号 + 并读出输入串的下一个输入符号 i 3 i_{3} i3
#E’T’F i 3 i_{3} i3 i 3 i_{3} i3#T → FT’弹出 T,将 FT’ 逆序压栈
#E’T’i i 3 i_{3} i3 i 3 i_{3} i3#F → i弹出 F,将 i 压栈
#E’T’ i 3 i_{3} i3 i 3 i_{3} i3#匹配,弹出栈顶符号 i 3 i_{3} i3 并读出输入串的下一个输入符号 #
#E’##T’ → ε弹出 T’,因M[T,#]中为T’ → ε,故不压栈
###E’ → ε弹出 E’,因M[E,#]中为E’ → ε,故不压栈
分析栈中仅剩“#”,输入串指针也指向串尾的“#”,分析成功
Logo

旨在为数千万中国开发者提供一个无缝且高效的云端环境,以支持学习、使用和贡献开源项目。

更多推荐