编译原理笔记13:自上而下语法分析(3)构造预测分析表、LL(1) 文法

构造预测分析表

预测分析表的作用,是为推导的进行指明方向——我们用当前下推栈栈顶和读写头所指向的符号的组合(即当前的状态),去查询预测分析表,以确定推导的下一步该向着何种方向前进。

推导应该前进的方向,由 FIRST、FOLLOW 集合说明——这两个集合能够说明,我们可以通过怎样的方式来一步步向着终结符靠近。

不懂也能用的构造步骤

预测分析表构造的步骤如下,建议按照例子实操一遍。实在想不通,背下来步骤应该也可以把表构造出来。

  1. 看待填行的行首非终结符 A
  2. 找到左部是上面看到的这个非终结符 A 的产生式,根据产生式右部的不同,按以下三种情况处理:
    1. 如果产生式是以非终结符 B 打头的序列 α ,那么找到 FIRST(B),将 FIRST(B) 集合中每个元素所在列、非终结符 A 所在行确定的位置填写上序列 α
    2. 如果产生式是以终结符 a 打头的序列 β ,那么直接去找终结符 a 所在列,并将 β 填入 A 行 a 列的位置中
    3. 如果产生式是 ε,则找到 FOLLOW(A) ,将 FOLLOW(A) 集合中每个元素所在列、非终结符 A 所在行确定的位置填写上 ε

概括来说,就是:根据产生式左部的非终结符确定本次要构造的分析表行。根据 FIRST、FOLLOW 集合,将产生式右部填入分析表,以此确定每行的内容。比如对于产生式 L → E;L|ε,我们需要把产生出来的右部 E;Lε 填入到分析表 L 行的某些位置中。

实例如下:

FIRST、FOLLOW 和分析表的原理?

FIRST、FOLLOW 集合都能够说明一些东西,比如, FIRST(L) 集合告诉我们:

  • 如果此时栈顶是 L ,而读写头读到了 id,那么我们应该用 E;L 来进行展开,因为这样可以让推导过程向着【把栈顶元素变为id 】的方向前进。这是因为从 E 开始经过数步推导后,E 能够最终展开为 id 而完成匹配
  • 如果此时栈顶是 L ,而读写头读到了 num ,那么我们应该用 E;L 来进行展开,因为这样可以让推导过程向着【把栈顶元素变为 num】的方向前进。这是因为从 E 开始经过数步推导后,E 能够最终展开为 num 而完成匹配
  • 如果此时栈顶是 L ,而读写头读到了 ( ,那么我们应该用 E;L 来进行展开,因为这样可以让推导过程向着【把栈顶元素变为 (】的方向前进。这是因为从 E 开始经过数步推导后,E 能够最终展开为 ( 而完成匹配

而当产生式右部是 ε 时,根据该产生式左部的非终结符所对应的 FOLLOW 集合来确定这个 ε 该填到哪里——也就是说,仅当某个非终结符的产生式右部为 ε 时,我们才需要考虑 FOLLOW 集合

  • 如果此时栈顶是 T',而读写头读到了 + ,那么……嗯,T' 可没有展开为 + 的产生式啊,但 T' 可以被穿透,其 FOLLOW 集合 FOLLOW(T') 是包含 + 的;
  • 同理,如果此时栈顶是 T',而读写头读到了 - ,也可以通过选择将 T' 以 ε 展开而穿透的方式来向着推出 - 的方向前进。

LL(1) 文法

LL(1),第一个 L ,代表从左到右扫描输入序列,第二个 L 代表推导的过程是最左推导。1 则代表只有一个读写头(也就是每次都只向前看一个终结符)

该文法的分析表的每个格子中只能有一个产生式的右部。该文法必须是非二义的,文法的产生式不能包含公共左因子和左递归。

LL(1) 文法使用范围有限,实际主要使用 LR(1) 文法。LR(1) 文法是 LL(1) 文法的真超集

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

推荐阅读更多精彩内容