探索编译原理之语法分析中的自顶(底)向下(上)分析、预测分析、推导与归约、LL(1)的介绍

1.前言

词法分析阶段获得的TOKEN即终结符,用于语法分析使用。扫描程序根据文法规则,采取适合的分析策略,根据文法或者产生式进行推导或者规约,下面,我们来介绍下相关涉及的理论知识。

2.本章相关概念介绍

TOKEN:词法分析程序获得的,也称为终结符

产生式:由非终结符和终结符构成

候选式:由相同左部组成的多组产生式

FOLLOW(A):紧跟在非终结符A后面的后继非终结符

SELECT( A→β ):产生式 A→β 在进行推导时的所有输入集合

FIRST(α):从 α 开始推出所有的串首终结符构成的集合,串首终结符指:串首第一个符号是终结符

LL(1)):L:从左往右扫描、L:最左推导、1每执行一步,向前看1个单词,然后做语义动作分析

3.文法的推导与归约

文法也叫语法,是语句的基础规则。从文法到产生式的过程叫推导,反之称为归约。如下所示:

文法:

1<句子>-><名词短语><动词短语>

2<名词短语>-><形容词><名词短语>

3<名词短语>-><名词>

4<动词短语>-><动词><名词短语>

5<形容词>->贪吃的

6<名词>->油画

7<名词>->男孩

8<动词>->临摹

上面流程中,6、7、8为终结符,其他部分为非终结符

自顶向下的过程,称为推导,一般采用从左到右的左推导方式

贪吃的 男孩 临摹 油画

贪吃的 男孩 临摹 <名词>

贪吃的 男孩 临摹 <名词短语>

贪吃的 男孩 <动词> <名词短语>

贪吃的 男孩 <动词短语>

贪吃的 <名词> <动词短语>

贪吃的 <名词短语> <动词短语>

<形容词> <名词短语> <动词短语>

<名词短语> <动词短语> -> 句子

3.1 文法的分类

3.1.1 0型文法

无限制文法,α → β,∀α → β∈P, α中至少包含1个非终结符

3.1.2 1型文法

上下文有关文法,α → β,∀α → β∈P,|α|≤|β|

产生式的一般形式: α1Aα2 → α1βα2 ( β≠ε )

3.1.3 2型文法

上下文无关文法,α → β ,∀α → β∈P,α ∈ VN

3.1.4 3型文法

正则文法:

右线性文法 A→wB 或 A→w

左线性文法 A→Bw 或 A→w

我们上面的例子用到的是0型文法

4.文法中出现的问题

4.1 同一个非终结符的候选式拥有相同前缀时,会产生回溯

S → aAd | aBe
A → c
B → b

输入 a b c

4.2 含有A→Aα形式产生式的文法称为是直接左递归

左递归会使递归下降分析器陷入无限循环

4.2.1 消除左递归的办法是转化成右递归

A → β A′
A′ → α A′|ε

5.自顶向下推导

根据文法,我们可以生成对应的语法分析树,自顶向下,被称为推导、反之则为归约。接着上面的示例,它的语法分析树如下所示:

通过自顶向下分析,我们推导出了 贪吃的男孩临摹油画,对于token来说,是符合语法规则的

6.自底向上归约

上面的语法分析树,在编码实现的环节,我们会采用堆栈的数据结构以及左归约的非递归形式来处理语法的归约过程,如下图所示:

从产生式到文法的归约过程,采用单个字符token扫描的方式

7.预测分析LL(K)

上面的文法会遇到一个二义性问题,比如在分析串:strs 和 strv 的时候,扫描程序因为是单个字符扫描,所以等到它扫描到第一个r时,根据文法规则,它有两个语法分支树。解决的方法是引入预测分析法,就是会预判扫描后面的K位,一般我们会预判一位,称为LL(1)。

8.参考

清华大学 《编译原理》张素琴 吕映芝

哈尔滨工业大学  陈鄞

如无特殊说明,文章均为本站原创,转载请注明出处。如发现有什么不对的地方,希望得到您的指点。

发表评论

电子邮件地址不会被公开。 必填项已用*标注