3.1 介绍

句法分析(syntax analysis,也叫 parsing)将会使用词符作为输入,用来创建一个树状中间层,从而表示词符流的语法结构。

解析算法有两个大类。

自上而下:将输入流与语法生成式进行预测匹配。(推导)

自下而上:从单词序列进行累加,直到显然地与生成式匹配(规约)

3.2 句法的表示

对于多数语言,句法使用 CFG 表示。

为什么不用 RE

RE 只能记忆有限个状态,因此对于类似括号匹配这样状态无限的问题,规则式无能为力。

CFG

歧义问题

如 if-then-else 语句

Stmt -> if Expr then Stmt else Stmt
      | if Expr then Stmt
      | Asmt
      | ...(others)

语句:

if Exp1 then if Exp2 then Asmt1 else Asmt2

会产生歧义,两种理解方式如下:

if Exp1 then
    if Exp2 then
        Asmt1
    else 
        Asmt2
if Exp1 then
    if Exp2 then
        Asmt1
else 
    Asmt2

因此必须增加规则来消歧义。

例如下面的规则:

Stmt -> if Expr then Stmt
     |  if Expr then WithElse else Stmt
     | Asmt
WithElse -> if Expr then WithElse else WithElse
          | Asmt

这样相当于让 else 就近匹配。

运算符优先级的实现

规则:

[图]

增加优先级:

图 3.1

CFG 的分类

CFG 包含 LR (1) 包含 LL (1) 包含 RG

LL 解析器:一类自上而下的解析器,将输入从左向右解析,进行最左推导。

最左推导,即总是展开最左边的展开非终结符

LL (k) 中,k 表示前瞻符号的数量。

前瞻符号(Lookahead symbol):也就是除了目前处理到的输入符号之外,还得再向右引用几个符号

LR:是一类自下而上的解析器。即从左到右读入文本,然后从最右进行反向推导。能够在线性时间内无回溯地进行解析。

LR (k) 中 k 表示前瞻符号的数量

移位归约解析器(Shift-reduce parser):一种表驱动的自下而上解析器。

正规 LR 解析器(Canonical LR parser):即 LR (1) 解析器。

LALR 解析器:Look Ahead LR parser 是一种简化的

3.3 自上而下解析

自上而下分析从解析树的根开始,向下扩展树,直到叶匹配扫描器返回的已分类的的单词。在每个时刻,都可以认为是在构建一棵部分树。

消除左递归

假设规则:$P\to Pa \mid b$,我们反复将 $Pa\mid b$ 代入其中的 $P$。

第一次得到 $(Pa|b) a|b$,去掉不确定的得到 $ba | b$

第二次得到 $((Pa\mid b) a|b) a|b$,去掉不确定的得到 $(ba|b) a|b$,也即 $baa|ba|b$。

后面不用算了,说白了就是 baaaaaaaaaa|baaaa|…..|baa|ba|b,规则式为 ba*

则 $P \to b | P^n a$,即 $P \to b^n a^*$,按教科书写法就是:

$$ P \to bT\\T\to aT \mid \varepsilon $$

这里非常蛋疼地拆成了两步,只是为了表示出匹配 0 或 N 次这个意思。

求解 First 和 Follow 集合

FIRST(α)是指符号串 α 能够推导出的所有符号串中,处于串首的终结符号组成的集合。

举个例子,如果 $a\to bC | dE|f$,那么 assert (First (a) == {b, d, f})

例子:$G:A\to (A) A \mid \varepsilon$

拢共有哪些终结符?( ) epsilonFIRST 集合显然是 (

FOLLOW(A)是指在文法 G [S] 的所有句型中,紧跟在非终结符 A 后的终结符号的集合。

举个例子,如果 TOKEN1 -> KEYWORD1 ;TOKEN2 -> KEYWORD1 {EXPR} ,则 assert (Follow (KEYWORD1)== ; 和 { )

例子:$G:A\to (A) A \mid \varepsilon$,显然 A 后面可以有 )

例题

考虑文法:

bexpr->bexpr or bterm | bterm
bterm->bterm and bfactor | bfactor
bfactor -> not bfactor | (bexpr) | true | false

分析:

消除左递归(bexpr->bexpr or bterm | bterm)

我们把 or bterm 看作一个终结符,所以结果就是 bexpr -> bterm (or bterm)*。按课本写法就是:

bexpr -> bterm TMP
TMP -> or term | epsilon

提取公因式(bexpr->bexpr or bterm | bterm) 得到 bexpr-> bterm {or bterm}}

同样的方法消除左递归(bterm->bterm and bfactor | bfactor) 得到 bterm-> bfactor (and bfactor)*,即 bfactor-> bfactor {and bfactor}

第三个生成式不是左递归,不用化简。

伪代码如下:

def bexpr():
	bterm()
	while lookahead == OR:
		match(OR)
        bterm()
    return

def bterm():
    bfactor()
    while lookahead == AND
    	match(AND)
        bfactor()
    return

def bfactor():
    if lookahead == NOT:
        match(NOT)
        bfactor()
        return
    if lookahead == LPAR
    	match(LPAR)
        bexpr()
        match(RPAR)
        return
    if lookahead == TRUE
    	match(TRUE)
        return
    if lookahead == FALSE
        match(FALSE)
        return
    throw UnexpectedTokenException
        

image-20211017205545194

FIRST: (

FOLLOW: ),$\varepsilon$

  1. 显然不含左递归
  2. 只有一个非终结符,所以不存在相交
  3. FIRST 和 FOLLOW 不相交

因此是 LL1 文法。

image-20211017205554536

解答:

消除左递归 (L -> LE | E) => L -> E+,即 L -> E {E}

first(A) = num, id

first(B) = (

first(E) = first(A) + first(B) = num, id, (

first(L) = first(E) = num, id, (

fo(A) = $

Fo(L) = Fr(E) = num, id, (;

Fo(B) = $

Fo(E) = Fr(E) = num, id, (;

证明 LL1:

  1. 不含左递归
  2. E 的候选式 A, B。Fr (A) 交 Fr (B) = 空
  3. 不存在 unterminal X s.t. epsilon in FIRST (X)

因此是 ll1 文法

LL1 分析表:

num id ( )
E E->A E->A E->B
A A->num A->id
B B->(L)
L L->E L->E L->E