logo资料库

LALR(1)类文法判定及其分析器构造.doc

发布时间：2022-06-12 发布人：admin 分类：说明书 资料大小：1.02M 资料格式：doc 举报 版权申诉
第1页 / 共25页
第2页 / 共25页
第3页 / 共25页
第4页 / 共25页
第5页 / 共25页
第6页 / 共25页
第7页 / 共25页
第8页 / 共25页
资料共25页，剩余部分请下载后查看
    LALR (1) between norms LR analyzer construction me
    LALR(1)类文法判定及其分析器构造 摘要  LALR(1)介于规范 LR 分析器构造法和 SLR 分析器构造之间 的一种方法，LALR 文法能描述大多数常用高级程序语言的语法 结构。LALR 分析表比规范 LR 分析表小很多,当然能力差一点， 它却能处理一些 SLR 分析器难以处理的情况。LALR(1)采用对 LR（1）项目集规范族合并同心集的方法，若合并同心集后不产 生新的冲突，则为 LALR（1）项目集 关键字 规范合并同心集、 不冲突 、 项目集 Abstract LALR (1) between norms LR analyzer construction method and structure of SLR analyzer between a way, LALR grammar describes most advanced programming language commonly used in grammar structure. LALR analysis table than the standard LR analysis of many small table, of course, nearly capacity, it can deal with some SLR Analyzer difficult to deal with the situation. LALR (1) use the LR (1) project set norms Family Care-way merger, if the merger is not of one mind set after the election of a new conflict, compared with LALR (1) project set norms merger Care Set 、Do not conflict、Itemsets KeyWords 第 页
    目录 摘要………………………………………………………………………………………………………………………2 Abstract…………………………………………………………………………………………………………2 一、引言……………………………………………………………………………………………………………4 二、Windows 下的编程环境简介………………………………………………………………5 三、LALR(1)文法判定及分析器构造的分析和设计……………………………6 （一）LALR(1)文法判定及分析器构造的分析…………………………………6 （二）LALR(1)文法判定及分析器构造的设计…………………………………6 1．设计方案……………………………………………………………………………………………6 2．设计内容……………………………………………………………………………………………7 3．设计详细步骤…………………………………………………………………………………7 （1）构造 LR(0)的项目集规范族………………………………………………7 （2）构造 LR(1)的项目集规范族………………………………………………8 （3）构造 LALR(1)的项目集规范族…………………………………………11 四、程序运行与测试………………………………………………………………………………………13 五、小结……………………………………………………………………………………………………………15 六、参考文献列表…………………………………………………………………………………………16 七、附录……………………………………………………………………………………………………………16 第 页
    一、引言 LR(0)文法限制比较严,用起来非常受限制,比如 它难于处理空产生式,因此这种方法很难承担实际程 序设计语言的语法分析工作。LR(1)方法是最好的一种 方法,但它的问题是状态用的太多,以至于有些大语言 难以在微机上实现。因此,必须给出功能较强,但状态 数不多的可行方法,这便是所介绍的 LALR(1)方法。 LALR(1)(Look Ahead _LR)方法由 DeRemer 提出, 它是介于 SLR(1)和 LR(1)之间的一种方法,具有 SLR(1) 状态少的优点和 LR(1)的适用范围广的优点。 主要思想来自这样一个事实: 1)LR(1)状态机从它们所表示的自动机角度看是等价 的; 2) 自 动机 可 通过 合 并等 价 状态 来 减少 状 态个 数 ， LALR(1)状态机通常采用 LR(1)状态机来定义。 因此我们接下来来了解 LALR（1）文法的判定问题 和构造的问题。 第 页
    二、Windows 下的编程环境简介 硬件环境： CPU： AMD Athlon（tm）64*2Dual Core Processor 3800+ 2.01 GHz 内存： 1.00GB 硬盘： 希捷酷鱼 80G 显卡： NVIDIA GeForce 7600 GT 软件环境： 操作系统： Micorosoft Windows XP Professional 版本 2002 Service Pack 2 编程软件： VC++ 6.0 中文版 第 页
    三、LALR(1)文法判定及分析器构造的分析和设计 （一） LALR(1)文法判定及分析器构造的分析 本次课程设计要求的是 LALR(1)文法的判定及其分析器的构造，也就是说 这个题目要求我们做两件事情：第一：要写出 LALR(1)文法的判定的一些规则， 第二：要构造一个分析器，这个分析器能对输入的文法进行判定。 对于一个文法是否为 LALR(1)文法，首先构造它的 LR(1)项目集族，若没任 何冲突，则合并同心集，若仍不产生规约-规约冲突，则是 LALR(1)文法。 但是合并同心集时要注意： 1．同心集是指相同的项目集合并在一起，因此同心集合并后仍相同，只要超 前搜索符集合为各同心集超前搜索符的和集。 2. 对于合并同心集后的项目集经转换函数所达仍为同心集。 3. 若文法 LR(1)文法，合并同心集后若有冲突也只可能是归约—归约冲突， 而不是能产生移进—归约冲突。 4. 合并同心集后对某些错误发现的时间会产生推迟现象，但错误的出现位置 仍是准确的。 LALR(1)分析器由总控程序、分析栈和识别文法活前缀的有限自动机等 3 部分构成.根据上下文无关文法构造 LALR(1)分析器,实质就是构造该文法的 LALR(1)自动机.此过程分为两步:首先根据给定的文法,构造它的 LR(0)自动机;其 次是以 LR(0)自动机和文法为输入,计算 LR(0)项目的 LALR(1)向前看符号集.如果 一个分析器能够用 LALR(1)分析表进行语法分析，分析器称为 LALR(1)分析器。 （二） LALR(1)文法判定及分析器构造的设计 1．设计方案 对于一个文法是否为 LALR(1)文法，首先构造它的 LR(1)项目集族，若没任 何冲突，则合并同心集，若仍不产生规约-规约冲突，则是 LALR(1)文法。可一 根据以下思路来设计： 1 构造文法 G 的 LR(1)项目集族，C={I0，I1……..In}。 2 合并同心集，使 C 变为 C’={J0J1………Jn},便 LALR(1)项目集。 3 若 C’构造动作（ACTION）表，其方法与 LR(1)分析表的构造相同。 ⑴若[A->α·aβ,b]∈JK，且 GO（JK，a）=Jj,其中 a∈Vt 则置 ACTION[k,a]= “Sj”, 其 Sj 的含义是把输入字符号 a 和状态 j 分别移入文法符号栈和状态栈。 第 页
    ⑵若项目[A->α·,a]属于 Jk,则置 ACTION[k,a]=“rj”,其中 a∈Vt,rj 的含义 是设 A->α是文法第 J 个产生式，此时为把栈顶符号串α规约为 A。 ⑶若项目[S->S·，#]属于 Jk,则置 ACTION[k,#]=“acc”,表示分析成功，接受。 ⑷GOTO 表的构造，对于不是同心集的项目集，转换函数的构造与 LR（1）的相同， 对同心集项目，由于合并同心集后，新集的转换函数也是同心集，因此，假定 II1，II2,……Iim 是同心集，合并后的新集为 Jk,转换函数 GO（II1，X），GO （II2, X）,………GO（Im,x）也为同心集，将其合并后记做 Ji,因此有 GO(Jk,x)=Ji, 所以当 X 为非终结符号时 GO（Jk,x）=Ji,则置 GOTO[k,x]=i 表示在 k 的状态下 遇非终结符 X 时，把 X 和 i 分别移到符号栈和状态栈，当 X 为终结符时和 ACTION 表重合。 ⑸分析表中凡不能用⑴-⑷填入信息的空白均填“出错标志” 2．设计内容： 分析文法 G(S)是不是 LALR(1)文法 SL=R|R L*R|i RL 3．设计详细步骤： 首先把文法 G(S)扩展为 G(S’): （0） S’S （1） SL=R （2） SR （3） L*R （4） Li （5） RL (1)构造 LR(0)的项目集规范族为: I0： S’·S I1:S’S S—>·L=R I2:SL·=R 第 页
    S·R L·*R L·I L·L· L·I I5: Li· I6: SL=·R R·L L·*R RL· I3:SR·I4:L*·R R·L L·*R L·i I7:L*R· I8:RL· I9:SL=R· LR(0)项目集及转换函数 不难发现，在项目集 I2 中存在移进项目 SL.=R 和归约项目 RL.因此 该文法不是 LR(0)文法，在考察是不是 SLR(1)方法解决，这就要看 R 的后 跟符集合中是否包含“=”，由文法产生式规则可求出 FOLLOW(R)={#,=},所 以 FOLLOW(R)∩{=}={=，#}∩{=}≠¢，因此在 I2 中存在的移进—归约冲突不 能用 SLR(1)方法解决。说明该文法不是 SLR(1)文法，因此，进一步构造它的 LR(1)项目集规范族，以判定是否是 LR(1)文法或 LALR(1)文法。 第 页
    (2)构造 LR(1)的项目集规范族为: I0：S’·S ,# R·L,=/# S—>·L=R ,# S·R ,# L·*R ,=/# L·I ,=/# L·L ,=/# I1: I2: S’S·,# SL·=R ,# RL·,# I3:SR·,# I4:L*·R ,=/# I10: RL·,# I12:Li · ,# I13:L*R ·,# L·*R,=/# L·i,=/# I5: Li·,=/# I6: SL=·R, # R·L, # L·*R, # L·i, # I7: L*R·,=/# I8: RL·,=/# I9: SL=R·,# I11: L*·R ,# R·L,# L·*R,# L·i,# 第 页
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料