自顶向下语法分析指北

  • 语法分析
    • 自顶向下语法分析
      • 确定分析
      • 不确定分析
    • 自底向上语法分析
      • 算符优先分析
      • LR分析

自顶向下语法分析

确定分析(LL(1)文法)

例1:

G[S]:

S -> pA | qB

A -> cAd | a

B -> dB | b

W = pccadd。

推导过程如下:S => pA => pcAd => pccAdd => pccadd。

  • ​ S S S S
    ​ / \ / \ / \ / \
    ​ p A => p A => p A => p A
    /   |   \                       /   |   \                      /   |   \
    
    ​ c A d c A d c A d
    /   |   \                      /   |   \
    
    ​ c A d c A d
    ​ |
    a
    

例2:

G[S]:

S->Ap

S->Bq

A->a

A->cA

B->b

B->dB

W = ccap,推导过程:

S => aP => cAp => ccAp => ccap。

FIRST(a)

a的开始符号集或首符号集。

例2:FIRST(Ap) = {a, c}。

FIRST(Bq) = {b, d}。

FIRST(S) = {a, b, c, d}。

###FOLLOW(A)

若Aa,a ∈ FOLLOW(A)。若a = ε,则# ∈ FOLLOW(A)。

SELECT(A->a)

a不为ε,则SELECT(A->a) = FIRST(a)。

否则,SELECT(A->a) = FIRST(a) - ε + FOLLOW(A)。

LL(1)

定义:

第1个L表示从左往右扫描字符串。

第2个L表示采用最左推导。

1表示只需向右看1个字符即可选择哪个产生式。(为了提高效率,最多为2)。

充要条件:

SELLECT(A->a) ∩ SELECT(A->b) = 空集。(a,b不能同时能ε)。

通俗理解就是a和b不能有相同前缀。

LL(1)文法判别步骤

求出能推出 ε 的非终结符。(未定,是,否)

计算FIRST集

计算FOLLOW集

计算SELECT集

方法

递归子程序法

对应文法中每个非终结符编写一个递归过程,每个过程的功能是识别由非终结符推出的串,当某非终结符的产生式有多个候选时能够按LL(1)形式可唯一确定地选择某个候选进行推导。

当文法满足LL(1)条件时,构造不带回溯的自上而下分析程序。

该分析程序由一组递归过程组成,每个过程对应文法的一个非终结符。

注意

不是所有的aij的first集的交集都为空,仅针对一个VN的候选式有如此的约定。

预测分析法

特征 :

根据当前输入符号,为当前要处理的非终结符选择产生式。

表驱动的预测分析器包含:

  • 一个输入缓冲区
  • 一个栈
  • 一张分析表
  • 一个输出流

预测分析表M

预测分析表是一个M[A,a]形式的矩阵。

其中: A为非终结符,a为终结符或#。

M[A,a]中存放着一条关于A的产生式,指出当A面临a时所应采取的候选;

M[A,a]中也可能存放一条“出错标志”,指出A不应该面临a。

例:对于文法G

  1. E→TE’
  2. E’ → +TE’|ε
  3. T →FT’
  4. T’→*FT’| ε
  5. F→(E)|id

其预测分析表为:

1557056948767

解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
FIRST(E)={ (, id }

FIRST(E’)={+, ε}

FIRST(T’)={ *, ε}

FIRST(T)={ (, id }

FIRST(F)={ (, id }

FOLLOW(E) ={#, )}

FOLLOW(E’)={), #}

FOLLOW(T’)={+, ), # }

FOLLOW(T) ={+, ), #}

FOLLOW(F) ={id, ), *, #}
预测分析器

预测分析程序的算法:

  • 输入:串w和文法G的分析表M

  • 输出:如果w属于L(G),则输出w的最左推导,否则报错

  • 方法:开始时,#S在栈里,w#在输入缓冲区

    令ip指向w #的第一个符号,令X是栈顶符号,a是ip指向的符号

预测分析器的工作方式:当前栈顶符号X和当前输入符号为a,则语法分析器的动作为:

  1. 如果X=a≠#,则POP,advance
  2. 如果X ∈VN,查M[X,a]表,若M[X,a]=X→UVW,则用WVU替换栈顶;若M[X,a]=error,则调用错误恢复程序。
  3. 如果X=a=#,分析成功。

句子id+id*id的分析过程:

1557057317524

不确定分析(简)

原理:

匹配,匹配不了回溯继续匹配,直到全部匹配不了或匹配成功为止。(非常暴力)

  1. 由于相同左部的产生式的右部FIRST集交集不为空而引起回溯。

    S->xAy

    S->ab|a

  2. 由于相同左部非终结符的右部可为 ε ,且非终结符的FOLLOW集中含有其他产生式右部FIRST集的元素。

    S->aAS

    S->b

    A->bAS

    A->ε

  3. 由于文法含有左递归。

    S->Sa

    S->b

部分不确定分析转确定分析

左递归消除

直接左递归消除

采用下列变换公式消除直接左递归,把直接左递归改写为右递归。

如:G[S]: S→Sa | b

可改写为:

S→bS’

S’→aS’|ε

改写后的文法所描述的L(G)={ba^n| n>=0}

一般而言,假定关于P的全部产生式是

P→Pa1 | Pa2 | … | Pam | b1 | b2|…|bn 其中,每个a都不等于ε,而每个都不以P开头,那么,消除P的直接左递归性就是改写这些规则:

P→b1P’ | b2P’ | … | bnP’

P’→a1P’ | a2P’ |… | amP’ | ε

间接左递归消除

间接左递归的消除需先将间接左递归变为直接左递归,然后再按第1种方法消除直接左递归。

代入法

将一个产生式规则右部的a中的Vn N替换为N的候选式。如果N有n个候选式,右边a重复n次,而且每一次重复都有N的不同候选式来代替N。

例如:N →a | Bc | ε 在S→Nq中的代入结果S→aq | Bcq | q。

回溯消除

回溯产生的根源:头字符集合的问题。例如A->ab|a。

提取公因子

经过反复提取左因子,就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。

例:考察文法G[S]:

S → iCtS | iCtSeS | aC → b

解:由于S的前两个候选项中含有左因子iCtS,提取左因子之后,等价文法G’如下:

S → iCtSS’ | a

S’ →eS |ε

C → b


文章结束了,但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!