语法分析

语法分析

对于给定的符号串,判断他是否是某个文法的句子

可以通过多次推导和规约来判断

通常使用最左推导和最左规约

分析方法

自顶向下

递归子程序法

对于每一个非终结符,构造一个子程序,用以识别对该非终极符所定义的符号串。

每个子程序以产生式左部非终结符命名,以产生式右部构造子程序的内容

执行步骤

首先读入开始第一个符号,然后扩展文法,判断第一个符号是什么,按照产生式走不同的分支,然后再不同的分支里面,判断如果是非终结符,就调用非终结符的子程序,如果是终结符就直接判断是否符合产生式要求,不符合就报语法错误,符合就直接读入,然后判断下一个符号。直到所有符号都能够按照文法被接受读入。

对文法的要求(局限性)

递归子程序是根据文法各产生式右部的首符号与当前所读单词是否匹配,以决定使用哪个候选产生式进行推导,这就要求文法满足如下两个条件

  • 具有相同左部的各个产生式,右部的首符号不同(反例:$A->a \alpha | a \beta$)
  • 文法不能有左递归(反例:$A-> A \alpha | a $)

其实满足如上两个条件的就算 LL(1) 文法

可以做消除左递归操作

LL(1)文法相关概念

首先设有如下语言
$$
G(Z) = (V_N, V_T, Z, P), A -> \alpha 属于 P
$$

first集合

对于一个产生式 $ A-> \alpha $ 如果有如下
$$
first(\alpha) = { t | \alpha 经过多次推导=>产生 t… , t属于V_T 终结符 }
$$
$first(\alpha)$ 是从 $\alpha$ 能够推导出的所有首符号构成的集合

follow集合

对于一个产生式 $ A-> \alpha $ 如果有如下
$$
follow(A) = { t | Z 经过多次推导=>产生 …At… , t属于V_T 终结符 }
$$
$follow(A)$ 是所有句型中紧跟在 $A$ 之后出现的终结符

求解方法

检查所有右部含有 A 的产生式 $B-> …A \beta$

看 $\beta$ 的情况

  • 如果非空,则 $first(\beta) 属于 follow(A)$
  • 如果可以多步推导到或者直接 $\beta = \epsilon$,则 $follow(B) 属于 follow(A)$

select集合

对于一个产生式 $ A-> \alpha $ 如果有如下
$$
f(x)=
\begin{cases}
first(\alpha) & \alpha 不可以推导出 \epsilon \
first(\alpha) 并运算 follow(\alpha) & \alpha 可以推导出 \epsilon
\end{cases}
$$
如果 $\alpha = \epsilon$ 则 $first(\alpha)={}$

设 # 为输入串的结束符,则 # 属于 $follow(Z)$

LL(1)文法定义以及判定

文法中具有相同左部的各产生式,其选择符集合不相交

LL(1)分析法

第一个 L 指的是从左到右扫描

第二个 L 是最左推导

1 是只查看一个当前符号

又称作预测分析法,属于确定的自顶向下的语法分析法

LL(1)分析器设计

需要设计一个 LL(1)分析表

行:未终结符

列:终结符 | #

通过查询 L(栈顶符号,当前符号) = 产生式序号

流程

  • 求文法选择集合,确认是否是 LL(1) 文法
  • 依次考虑每个产生式,如果 A->\alpha [1] 且 a 属于 select(1) 则 L(A, a) = [1]

自底向上

LR(0)

优点

  • 对文法限制少
  • 分析速度快,可以准确即时定位出语法错误位置

缺点

  • 分析器构造工作量大,实现困难(主要在句柄识别器方面)

LR()分析法

第一个 L 是从左到右扫描

第二个 R 最右推导的逆过程(最左规约)

常用的有 LR(0) 和 LR(1)

括号的数字指的是查看几个当前符号来确定规约过程

基本要点

  • 利用一个分析栈,记录分析过程
  • 当栈顶出现句柄,将句柄归约,否则移进
  • 采用有限自动机作为句柄识别器

句柄一定出现在某一个产生式右边的符号串

归约的时候确定使用哪个产生式很重要