发布时间 : 星期一 文章LR(0)语法分析更新完毕开始阅读ed0b9161ddccda38376baf2f
编译原理课程设计报告
1 课题综述
1．1 课题来源
编译器设计的编译程序涉及到编译五个阶段中的三个，即词法分析器、语法分析器和中间代码生成器。编译程序的输出结果包括词法分析后的二元式序列、变量名表、状态栈分析过程显示及四元式序列程序。整个编译程序分为三部分：词法分析部分、语法分析处理及四元式生成部分、输出显示部分。
一个程序设计语言就是一个记号系统，如同自然语言一样，它的完整的定义应包括语法和语义两个方面。所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序。目前广泛使用的手段是上下文无关文法，即用上下文无关文法作为程序设计语言语法的描述工具。
自底向上分析方法是一种移进-规约过程，当分析的栈顶符号串形成句柄时就采取归约动作，因而自底向上分析法的关键问题是在分析过程中如何确定句柄。LR分析法正是给出一种能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输人串的k个(k>=0)符号就可惟一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能惟一地确定句柄。LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程。
1．2 意义
LR（0）分析方法虽然对文法的限制比较大，对绝大多数高级语言的语法
分析器不能适用，然而他是构造其他LR类分析器的基础，学习和掌握LR（0）分析的原理和方法是我们掌握更高级语言语法分析的基础。归纳起来，大体上可分为两大类，即自顶向下分析方法和自底向上分析方法。
自底向上分析方法是一种移进-规约过程，当分析的栈顶符号串形成句柄时就采取归约动作，因而自底向上分析法的关键问题是在分析过程中如何确定句柄。LR分析法正是给出一种能根据当前分析栈中的符号串(通常以状态表示)和向右顺序查看输人串的k个(k>=0)符号就可惟一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能惟一地确定句柄。LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程。
1．3 预期目标
1
编译原理课程设计报告
本次课程设计的目标即是利用所学过的编译原理的知识，利用LR(0)分析法，用C语言写出一个简单的LR(0)语法分析器。该语法分析器所要完成的功能是，对录入的文法判断它是否为LR(0)文法，如果是输出LR (0)分析表；在给定文法的情况下，能够利用LR(0)分析表，对用户输入的一串字符串用LR(0)分析法进行分析，判断该字符串是否为符合给定文法的一个句子，建立文法及其LR分析表表示的数据结构，设计并实现一个LR(0)的分析器。
1．4 面对的问题
(1)分析表的构造。 (2)归约还是移进的判断。 (3)接受acc的判断。 (4)编程结果的输出。
在本次课程设计中，主要的是面对的文法的确定，以及分析其工作过程如何进行。对于文法确定的问题，必须找到一个符合LR(0)规范的文法，并且该文法不易太复杂，否则对于初次编写语法分析器的我们来说会比较复杂，否则容易出错。第二个就是分析过程的问题，目前，我们只是了解了理论上LR(0)的分析过程，但如何将该过程用程序去实现，并且能够对一个输入串进行实时的分析是比较复杂的。这涉及到对一个字符串进行一个字符一个字符的读取和操作，并且还要对几个连在一起的字符进行合并等操作，要求比较的高，对我们而言比较困难。
在规范规约的过程中，一方面记住已移进和规约出的整个符号串，另一方面根据所用的产生式推测未来可能碰到的输入符号。当一串句柄的符号串呈现于分析栈的顶端时，希望能够根据上面过程中的数据来确定栈顶的符号串是否构成相对某一产生式的句柄。
能正确初始化状态栈，对栈内元素的进栈和出栈，取栈顶元素以及遍历栈元素，LR分析方法是一种自底向上的分析方法，是一种个移进-归约的过程。当分析的栈顶符号串形成句柄时就采取归约动作，因而自底向上分析法的关键问题是在分析过程忠如何确定句柄。LR（0）分析器是在分析过程中不需要察看输入符号，因而它对文法的限制较大，对绝大多数高级语言的语法分析器是不能使用的，然而，他是构造其他LR类分析器的基础。
1.5 需解决的关键技术
2
编译原理课程设计报告
（1）词法编译器。
（2）交互式面向对象的词法编译器基本功能是。 （3）根据规约规则对字符进行归约。 （4）符合条件时采取移进动作。
2 系统分析
2．1 涉及的基础知识
2.1.1 词法编译器功能
（1）导入任意文法，也可以自己输入。
（2）输出文法的分析过程，以及判断是否为LR (0)文法，输出分析表。 （3）输入句子，进行语法分析。 （4）输出结构树。 2.1.2 词法分析器的设计
方法有如下四个步骤： (1)写出该语言的词法规则。
(2)把词法规则转换为相应的状态转换图。
(3)把各转换图的初态连在一起，构成识别该语言的自动机。
(4)设计扫描器；把扫描器作为语法分析的一个过程，当语法分析需要一个单词时，就调用扫描器。扫描器从初态出发，当识别一个单词后便进入终态，送出二元式。
2.1.3 动态模拟算法的基本功能
（1）输入LR分析表和一个句子。 （2）输出LR总控程序。
（3）输出依据句子构对应的语法树的过程。
（4）设计一个给定LR分析表，输入一个句子，能由依据LR分析表输出与句子对应的语法树，能对语法树生成过程进行模拟。
表 2-1 LR分析表 STATE
ACTION a b c 3
GOTO d # E T F 编译原理课程设计报告
0 1 2 S2 S3 S4 0 S1 acc 1 6 3 4 S5 S4 0 S4 S1 8 7 5 S5 1 S1 9 6 7 8 9 10 11 r1 r2 r3 r5 r4 r6 r1 r2 r3 r5 r4 r6 r1 r2 r3 r5 r4 r6 r1 r2 r3 r5 r4 r6 r1 r2 r3 r5 r4 r6 （5）输入句子：bccd#。
（6）根据文法产生的LR分析表。 （7）输出结果 2.1.4 LR分析器的构成
一个LR分析器由３个部分组成
（1）总控程序，也可以称为驱动程序。对所有的LR分析器，总控程序都是相同的。
（2）分析表或分析函数。不同的文法分析表将不同，同一个文法采用的LR 分析器不同时，分析表也不同，分析表又可以分为动作（ACTION）表和状态转换（GOTO）表两个部分，它们都可用二维数组表示。
（3）分析栈，包括文法符号和相应的状态栈。它们均是先进后出栈。 分析器的动作由栈顶状态和当前输入符号所决定（LR(0)分析器不需向前查看输入符号）。
2.2解决问题的基本思路
4