编译原理系列之六 自底向上的LR分析法(3) – 其它LR分析技术

其它LR分析技术

一、LR(1)分析

1. SLR(1)分析的问题

  • 无效归约问题:

    在SLR(1)分析中,我们考虑了所归约非终结符的 Follow 符号,这可以分析出怎么选择归约或移进,但是在选择归约的情况中里,我们只是确认了移进符号是属于非终结符的Follow集的,而没有确认移进后是否是表达式文法规范句型的活前缀,也就是未考虑非终结符 Follow 集中的符号是否也是句柄的 Follow 符号;这样虽然不会影响判断结果,但产生了无效归约,减低了效率。

    例:现在符号栈中的元素是βα,移进符号是a,已知有归约项目A->α,并且a属于follow(A)a不属于follow(βα);此时我们的做法是归约然后移进,之后的符号栈中的元素是βAa,而βAa不是文法规范句型的活前缀。

    如果我们能判断出a!∈follow(βA),就可以判断出出错了。

  • 局限性问题:

    SLR(1)分析的要求是:Ii ={A1->α1•b1γ1 ,… , Am->m•bm γm, B1->β 1 • ,…, Bn-> β n • },若集合{b1 ,b2,… ,bm }FOLLOW(B1)FOLLOW(B2) ,…,FOLLOW(Bn)均两两不相交。和上面的道理相似,没有考虑非终结符 Follow 集中的符号是否也是句柄的 Follow 符号,导致虽然follow集出现了相交,但是事实上正确的符号串是不会出现某些 follow集中的符号的,从而不能判断。

    已知:增广文法 G’ [ S ]:
    (0) S -> E
    (1) E -> (L , E )
    (2) E -> F
    (3) L -> L , E
    (4) L -> E
    (5) F -> ( F )
    (6) F -> d

    有G’ [S] 的 LR(0)FSM:

    G’ [S] 的 LR(0)FSM

    在I7中出现了{)}∩follow(E)={)}的情况,所以不能进行SLR(1)分析;但是I7中的情况是(·F,E),此时的follow(E)中没有而应该是,

2.LR(1)分析法原理

我们在求项目集的时候,每个项目的末尾添加一个非终结符并以,分隔开来,来表示在当前情况下用该产生式进行规约时所期望的下一个字符,称之为向前搜索符,来替代follew集。

在检查是否可用.LR(1)分析法的时候,要求是Ii{A1->α1•b1 γ1,a1,… , Am->m•bm γm,amB1->β 1 •,c1,…,Bn-> β n •,cn },若集合{b1}{b2},… ,{bm}{c1}{c2},… ,{cm}均两两不相交。满足这样要求的文法称之为LR(1)文法:。

通过比较``{b1}{b2},… ,{bm}{c1}{c2},… ,{cm}`和待移进字符就能分析出当前应该进行的操作。

例:增广文法 G’ [ S ]:
(0) S -> E
(1) E -> (L , E )
(2) E -> F
(3) L -> L , E
(4) L -> E
(5) F -> ( F )
(6) F -> d

构造增广文法G’ [S] 的 LR(1)FSM:

G’ [S] 的 LR(1)FSM(1)
G’ [S] 的 LR(1)FSM(2)
G’ [S] 的 LR(1)FSM(3)

3. LR(k)分析

同理可推广到LR(k)分析:

形如: [A ->α . β , a1a2…ak ],其中a1a2…ak 为向前搜索符号串。

移进项目形如:[ A ->α . aβ, a1 a2 … ak] ;待约项目形如:[A ->α . Bβ, a1 a2 … ak]; 归约项目形如:[A ->α . ,a1 a2 … ak]

但LR(k)分析只有理论意义,因为LR(1)FSM 的状态数已经很大,k>1 的情形难以想象。

二、LALR(1)分析

1.基本概念

  • LR(1)项目的“心”(core):

    LR(1)项目 [A -> α . β , a] 中的A -> α . β 部分称为该项目的“心“ 。

  • 同心集:

  • 对于LR(1)FSM 的两个状态,如果只考虑每个项目的 “心”,它们是完全相同的项目集合,那么这两个状态互为同心集。

2.LALR(1)分析法原理

我们可以发现LR(1)分析的有限状态机中,项目集的数量十分的多。这是因为许多在LR(0)分析中循环的项目集在LR(1)分析中由于·的位置变化导致向前搜索集也产生了变化,从而产生了许多同心集。而LALR(1)分析法正是对这些同心集进行了合并。

暴风(Brute Force)算法:

  1. 构造增广文法的 LR(1)FSM 状态 。
  2. 合并“同心”的状态(同心项目的搜索符集合相并) 得到LALR(1) FSM 的状态 。
  3. LALR(1) FSM 状态由 GO 函数得到的后继状态是所有被合并的“同心”状态的后继状态之并 。

注意:

  • 合并同心状态后,不会产生新的移进-归约冲突,但可能产生新的归约-归约冲突。

  • 一个LR(1)文法,如果将其LR(1)FSM的 同心状态合并后所得到的新状态无归约-归约 冲突,则该文法是一个 LALR(1)文法 。

    例:增广文法 G’ [ S ]:
    (0) S -> E
    (1) E -> (L , E )
    (2) E -> F
    (3) L -> L , E
    (4) L -> E
    (5) F -> ( F )
    (6) F -> d

    构造增广文法G’ [S] 的 LALR(1) FSM

G’ [S] 的 LALR(1) FSM
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 220,367评论 6 512
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 93,959评论 3 396
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 166,750评论 0 357
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 59,226评论 1 295
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 68,252评论 6 397
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,975评论 1 308
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,592评论 3 420
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,497评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 46,027评论 1 319
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,147评论 3 340
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,274评论 1 352
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,953评论 5 347
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,623评论 3 331
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,143评论 0 23
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,260评论 1 272
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,607评论 3 375
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 45,271评论 2 358

推荐阅读更多精彩内容