编译原理课程设计.pdf

编译原理课程设计 自顶向下语法分析 学 院（系）： 计算机科学及技术学院 学 生 姓 名： xxxxxxxxx 学 号： xxxxxxxxx 班 级： 电计 1102 大连理工大学 Dalian University of Technology 第 页 目 录 1 系统概论 - 0 - 2 需求分析 - 1 - 3 系统设计 - 1 - 4 系统实现 - 3 - 5 使用说 4 5.1 程序运行平台 4 5.2 程序中所有定义函数 - 4 - 5.3 文档说 6 5.4 调试分析 - 7 - 6 课程设计总结 - 9 - 参考文献 - 10 - 附录：重要代码 - 10 - 1 系统概论 语法分析是编译过程核心部分。它任务是在词法分析识别出单词符号串 基础上，分析并判定程序语法结构是否符合语法规则。语法分析器在编译程 序中地位如图 1 所示： 图 1 语法分析器在编译程序中地位 语言语法结构是用上下文无关文法描述。因此，语法分析器工作本质上 就是按文法产生式，识别输入符号串是否为一个句子。这里所说输入串是指 由单词符号 （文法终结符）组成有限序列。对一个文法，当给你一串 （终结） 符号时，怎样知道它是不是该文法一个句子呢？这就要判断，看是否能从文 法开始符号出发推导出这个输入串。或者，从概念上讲，就是要建立一棵及 输入串相匹配语法分析树。 自顶向下分析法就是语法分析办法中一类。顾名思义，自顶向下就是从 文法开始符号出发，向下推导，推出句子。这种方法是带“回溯”。 自顶向下分析主旨是，对任何输入串，试图用一切可能办法，从文法开 始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者说，为输 入串寻找一个最左推导。这种分析过程本质上是一种试探过程，是反复使用 不同产生式谋求匹配输入串过程。 实现这种自顶向下带回溯试探法一个简单途径是让每个非终结符对应 一个递归子程序。每个这种子程序可作为一个布尔过程。一旦发现它某个 选及输入串相匹配，就用这个候选去扩展语法树，并返回“真”值；否则， 保持原来语法树与 IP 值不变，并返回“假”值。 第 - 0 - 页 2 需求分析 以前，人们对语法分析都建立在人工基础上，人工分析虽然能够做到侧 类旁推，但终究人力有限，再精密分析都会出现或多或少错误。为减少因人 为产生错误，并加快语法分析，故设计了这个自顶向下语法分析器。人们只 要运行程序，输入几个简单命令或语法，就能求出人们所需要各种结果。虽 然程序设计有一定局限性，但在这个局限中却能如人们要求对语法进行分 析，从而在一定程度上帮助人们更好完成工作。 3 系统设计 自顶向下分析算法通过在最左推导中描述出各个步骤来分析记号串输 入。之所以称这样算法为自顶向下是由于分析树隐含编号是一个前序编号， 而 且 其 顺 序 是 由根 到 叶 自顶 向下 分 析 程 序 有 两 类 ： 回溯 分 析 程 序 （backtracking parser）与预测分析程序（predictive parser）。预测分 析程序试图利用一个或多个先行记号来预测出输入串中下一个构造，而回溯 分析程序则试着分析其他可能输入，当一种可能失败时就要求输入中备份任 意数量字符。虽然回溯分析程序比预测分析程序强大许多，但它们都非常慢， 一般都在指数数量级上，所以对于实际编译器并不合适。 递归下降程序分析与 LL(1)分析一般地都要求计算先行集合，它们分别 称作 First 集合与 Follow 集合。由于无需显式地构造出这些集合就可以构 造出简单自顶向下分析程序。 1、LL(1)文法 LL(1)文法是一类可以进行确定自顶向下语法分析文法。就是要求描述 第 - 1 - 页 语言文法是无左递归与无回溯。根据 LL