编译原理复习
|
443
|
0
|
学习随笔

1163 字
|
5 分钟

第四章

语法分析器的功能

分析出单词符号串的基础上，程序的语法结构是否符合语法规则。

按文法的产生式识别输入的符号串是否为一个句子。

自上而下分析面临的问题

带回溯的分析，如果有左递归可能会无限循环，效率低，虚假匹配的问题，难以知道出错的位置。

LL(1)文法

左递归的消除

直接左递归

间接左递归

例子

消除回溯，提左公因子

LL(1)分析的思想

求取FOLLOW集

LL(1)文法的定义

递归下降分析程序

终结符：S();

非终结符：if(Sym == “+”) Advance();

预测分析程序

第五章

自下而上分析

基本思想

用文法左部去代替符合的右部

短语、直接短语和句柄

短语

短语是一个字符串的子串

直接短语

句柄

一个句型的最左直接短语

例子

规约的基本思想

形成了句柄就可与规约

规范规约

  • 最左推导（规范推导）的逆过程：最右规约
  • 最右推导的逆过程：最左规约（规范规约）

算符优先文法

用于做自下而上分析

算符优先文法的定义

算符优先关系

因为算符优先性代表着谁会先被规约掉

算符文法

即不可以两个非终结符挨在一起

算符优先关系定义

文法G中任意两个终结符(a,b)最多只能满足三种关系之一就是算符优先文法。

例子

算符优先关系表的构造

构造需要用到两个集合

  • FirstVT集合算法

  • LastVT集算法

例子

构造的如果无冲突，就是算符优先文法。

最左素短语

定义

  • 素短语：是一个短语，至少包含一个终结符，且除自身之外不包含其他的素短语
  • 最左素短语：位于句型最左边的（在树中来看）

例子

算符优先文法的句型

算符优先文法结构如下

算符优先分析算法

优先函数

f(a)：栈内优先函数

g(a)：比较优先函数（栈外（源程序）优先函数）

优先函数不等于优先关系表，有些优先关系表不存在优先函数，如果有一对优先函数f和g，就存在无限多对优先函数。

关系图法构造优先函数

LR分析法

LR分析器

组成

  1. 总控程序：不依赖于文法，依赖于分析表
  2. 分析表
  3. 分析栈：状态栈、符号栈

ACTION表

分析过程中执行的动作，有移进、规约、accept、出错。

GOTO表

用于跳转目标状态

LR(0)项目

前缀

符号串的任意部首，比如在abc中：空、a、ab、abc都是其部首。

活前缀

可归前缀

LR（0）项目

文法G的每条规则右部的任意位置上加上一圆点构成的项目。原点作用是进行分割，左边是在栈内的符号，右边是未进栈的符号。

构造识别文法活前缀的NFA

步骤

1、拓广文法

2、给出文法的所有LR（0）项目

3、将每一个项目连接起来

构造LR(0)项目集规范族

识别一个文法活前缀的DFA的项目集（状态）的全体

步骤

1、拓广文法并且求闭包closeure(I)

2、状态转换函数

例子

LR(0)分析表的构造

如果分析表没有冲突就是LR(0)文法，即每个位置只有一个动作。

LR分析

对上面的分析表进行LR分析

SLR(1)分析表的构造

规约项填的是对应产生式左部非终结符的FOLLOW集。

LR(1)项目集的构造

SLR（1）无法解决的移进、规约冲突，即相关集合相交。

LALR(1)分析表的构造

将LR(1)前部合并

 

上一篇
下一篇