基于C++设计简单计算器（LR 分析法）【100012180】

# 简单计算器的设计（LR 分析法） ## 1 课程设计目的 通过设计、编制、调试一个简单计算器程序，加深对语法及语义分析原理的理解， 并实现词法分析程序对单词序列的词法检查和分析。 ## 2 课程设计内容及步骤 本次课程设计需要使用 LR 分析法完成简单计算器的设计，其中算术表达式的文法如下： 〈无符号整数〉∷＝ 〈数字〉{〈数字〉} 〈标志符〉∷＝ 〈字母〉{〈字母〉｜〈数字〉} 〈表达式〉∷＝［＋｜－］〈项〉{〈加法运算符〉〈项〉} 〈项〉∷＝ 〈因子〉{〈乘法运算符〉〈因子〉} 〈因子〉∷＝ 〈标志符〉｜〈无符号整数〉｜‘（’〈表达式〉‘）’ 〈加法运算符〉∷＝ ＋｜－ 〈乘法运算符〉∷＝ \* ｜／ 本次课程设计分为如下步骤完成： 1. 根据题目要求的文法写出产生式； 1. 进行文法拓广，根据产生式画出识别活前缀的 DFA； 1. 根据 DFA 写出 LR(0)或 SLR(1)分析表； 1. 编写程序，对输入串进行分析； 1. 设计若干用例，上机测试并通过所设计的分析程序。 ## 3 翻译方法 ### 3.1词法分析 词法分析是计算机科学中将字符序列转换为单词（Token）序列的过程。进行语法分析的程序或者函数叫作词法分析器（Lexical analyzer，简称 Lexer），也叫扫描器（Scanner）。 词法分析器一般以函数的形式存在，供语法分析器调用。词法分析是编译过程中的第一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。简化设计、改进编译效率、增加编译系统的可移植性。词法分析是编制一个读单词的过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。单词的分类主要分为五类： 1. 关键字：由程序语言定义的具有固定意义的标识符，也称为保留字或基本字。 1. 标识符：用来表示程序中各种名字的字符串。 1. 常 数：常数的类型一般有整型、实型、布尔型、文字型。 1. 运算符：如＋、－、\*、／等。 1. 界限符：如逗号、分号、括号等。 这里将词法分析程序设计成一个子程序，每当语法分析程序需要一个单词时，则调用该子程序。词法分析程序每调用一次，便从源程序文件中读入一些字符，直到识别出一个单词。 ### 3.2语法分析 语法分析是编译程序的核心部分，其主要任务是确定语法结构，检查语法错误，报告错误的性质和位置，并进行适当的纠错工作。 语法分析的主要工作是识别由词法分析给出的单词序列是否是给定的正确句子（程序）。语法分析常用的方法自顶向下的语法分析和自底向上的语法分析两大类。此次设计中语法分析中主要通过 LR 分析法对语法分析处理过程进行控制，使表达式结果能正确得出，同时识别语法分析中的语法错误。 语法分析是编译过程的一个逻辑阶段。语法分析的任务是在的基础上将单词序列组合成各类语法短语，如“程序”、“语句”、“表达式”等等。语法分析程序判断源程序在结构上是否正确。源程序的结构由上下文无关文法描述。语法分析程序可以用 YACC 等工具自动生成。 在语法分析的同时可由语法分析程序调用相应的语义子程序进行语义处理，完成附加在所使用的产生式上的语义规则描述，并完成移进—归约过程。 词法分析程序和语法分析程序的关系如图 1 所示：  图 1 词法与语法分析的关系 ### 3.3中间代码生成 中间代码，也称中间语言，是复杂性介于源程序语言和机器语言的一种表示形式。为了使编译程序有较高的目标程序质量，或要求从编译程序逻辑结构上把与机器无关和与机器有关的工作明显的分开来时，许多编译程序都采用了某种复杂性介于源程序语言和机器语言之间的中间语言。中间代码（语言）是一种特殊结构的语言，编译程序所使用的中间代码有多种形式。按其结构分常见的有逆波兰式（后缀式）、三地址代码（三元式、四元式）和树形表示（抽象语法树）、DAG 表示。 本次课程设计不需要生成中间代码。 ## 4 文法及属性文法描述 ### 4.1文法描述 根据题目要求的文法，产生式如下： 1. *S*′→ *S* （文法拓广） 1. *S* → *E* 1. *E* → *E*＋*T* 1. *E* → *E*－*T* 1. *E* → *T* 1. *T* → *T* \* *F* 1. *T* → *T / F* 1. *T* → *F* 1. *F* → (*E*) 1. *F* → ＋*i* 1. *F* → －*i* 1. *F* → *i* ### 4.2属性文法描述 对该文法的属性文法描述如下： |产生式|语义规则| | :- | :-: | |*S* → *E*|print(*E*.val)| |*E* → *E*＋*T*|*E*.val := *E*.val + *T*.val| |*E* → *E*－*T*|*E*.val := *E*.val - *T*.val| |*E* → *T*|print(*T*.val)| |*T* → *T* \* *F*|*T*.val := *T*.val \* *F*.val| |*T* → *T / F*|*T*.val := *T*.val / *F*.val| |*T* → *F*|print(*F.*val)| |*F* → (*E*)|*F*.val := *E*.val| |*F* → ＋*i*|*F.*val := *i*.lexval| |*F* → －*i*|*F.*val := -*i*.lexval| |*F* → *i*|*F.*val := *i*.lexval| ## 5 LR 分析法 ### 5.1LR 分析法概述 LR 分析法是一种能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的 *k* 个（*k*≥0）符号就可以唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄。LR 分析法的归约过程是规范推导的逆过程， 所以 LR 分析过程是一种规范归约的过程。 LR(*k*)分析方法是 1965 年 Knuth 提出的，括号中的 *k* 表示向右查看输入串符号的个数。这种方法比起自顶向下的 LL(*k*)分析方法和自底向上的优先分析方法对文法的限制要少得多，也就是说对于大多数用无二义性上下文无关文法描述的语言都可以用相应的LR 分析器进行识别，而且这种方法还具有分析速度快，能准确、即时地指出出错位置。它的主要缺点是对于一个实用语言文法的分析器的构造工作量相当大，*k* 愈大构造愈复杂，实现比较困难。因此，目前许多实用的编译程序，都运用了 LR 分析器。 ### 5.2识别活前缀的 DFA 本课程设计根据产生式得到的识别活前缀的 DFA 如图 2 所示：  ### 5.3 SLR(1)分析表 根据图 2 可知，*I*2、*I*3、*I*16、*I*17 存在移进—归约冲突，可用 SLR(1)方法解决冲突。SLR(1)分析表如下：  ### 5.4分析过程 LR 分析法的规约过程是规范推到的逆过程，所以 LR 分析过程是一种规范规约的过 程。其分析过程为：由文法构造出该文法项目集，再根据项目集构造该文法的 DFA，再判断是否有移进—规约和规约—规约冲突，若没有冲突则该文法为 LR(0)的，若有冲突则该文法是 SLR(1)的，最后可以构造出 LR(0)分析表。然后根据 LR(0)分析表进行语法分析，分析过程就是进栈和规约的过程。若能规约出开始符 *S*，则语法正确。反之，语法错误。 LR 分析法过程流程图如下：  图 3 LR 分析法流程图 其中 *S*p 为栈顶指针，*S*[i]为状态栈，*X*[i]为文法符号栈。状态转换表内容按关系GOTO[*S*i, *X*]=*S*j 确定，改关系式是指当前栈顶状态为 *S*i 遇