第 2 章词法分析

Pluveto

Nov 01, 2021 发布

? 次浏览

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