编译原理课程设计
实验内容 设计并实现SNL程序设计语言的编译程序； 四个模块： 词法分析模块 语法分析模块（递归下降方法） 语法分析模块（LL(1)方法） 语义分析模块
实验四模块之间的关系 语义分析模块 词法分析模块 语法分析模块 （递归下降法） （LL(1)方法） SNL源程序 Token序列 语法树
实验目的 通过对SNL编译程序的学习和动手实践，使学生可以更加深入、全面地掌握编译程序的工作原理和实现技术； 培养大型软件的程序设计方法。
SNL语言简介 SNL(Small Nested Language)是自行定义的教学模型语言，它是一种类似Pascal的”高级”程序设计语言 数据类型：整型、字符型，数组、记录 过程允许嵌套定义，允许递归调用
SNL的程序结构 程序头 声明部分 程序体部分 类型声明部分 变量声明部分 过程声明部分 program pp var integer v1; char c; procedure f(); begin v1 :=2 End Begin f(); write(v1) end.
SNL的语法 SNL的上下文无关文法（P9-P12页）
第一个程序： SNL的词法分析程序 输入：SNL源程序 输出：单词的内部表示序列-Token序列 程序设计步骤 确定单词分类；P35 单词的正则表达式定义（词法定义）；P7–P8 构造DFA ； P39 根据DFA生成单词识别函数 对于给定的当前状态和当前字符，决定下一个状态； 如果是结束状态，得到单词的类别和信息； 否则，设置为当前状态；
词法分析程序涉及的一些问题 单词分类 Token表示定义 每类单词的构成 自动机的实现(状态图方法、转换表方法) 一些特殊情形的处理：注释、括号匹配、向前扫描等
第二个程序： SNL的递归下降分析程序 输入：Token序列 输出：语法错误检查信息和语法树 例：S → A u B A → a a B → b b 则各个VN的递归子程序结构如下： S( ) begin A(); match(u); B() end A( ) begin match(a); match(a) end B( ) begin match(b); match(b) end 输入：Token序列 输出：语法错误检查信息和语法树 思想 对文法的每一个VN都编写一个分析程序，当根据文法和当前输入符号预测到要用某个VN去匹配输入串时，就调用该VN的分析程序。
递归下降程序涉及的一些问题 当产生式形如:A1|2|…|n时需要通过predict集确定子程序的调用。P61-P64 如何构建语法树及语法树的内部表示。 Program ProgramHead DeclarePart ProgramBody .
递归下降分析模块 语法树的输出 层次文本输出 图形输出 ProK PheadK p TypeK DecK IntegerK t1 VarK DecK IntegerK v1 v2 ProcDecK q DecK value param: IntegerK i DecK IntegerK a StmLk StmtK Assign ExpK a IdV ExpK i IdV StmtK Write StmtK Read v1 StmtK If ExpK Op < ExpK v1 IdV ExpK Const 10 ExpK Op + ExpK Const 10 ExpK Op - StmtK Call ExpK q IdV 语法树的输出 层次文本输出 图形输出
第三个程序 ： SNL的LL(1)分析程序 输入：Token序列 输出：语法错误检查信息和语法树 Program ProgramHead DeclarePart ProgramBody .
第四个程序： SNL的语义分析程序 输入：语法树 输出：语义错误信息 数据结构： 算法： 语法树 符号表 在扫描声明部分语法树时建立符号表 在扫描语句部分语法树时查表检查语义
SNL的语义错误 （1） 标识符的重复定义； （2） 无声明的标识符； （3） 标识符为非期望的标识符类别（类型标识符，变量标识符，过程名 标识符）； （4） 数组类型下标越界错误； （5） 数组成员变量和域变量的引用不合法； （6） 赋值语句的左右两边类型不相容； （7） 赋值语句左端不是变量标识符； （8） 过程调用中 ，形实参类型不匹配； （9） 过程调用中， 形实参个数不相同； （10）过程调用语句中，标识符不是过程标识符； （11）if 和while 语句的条件部分不是bool类型； （12）表达式中运算符的分量的类型不相容 等等
符号表 符号表：标识符的属性表 属性：种类，类型，名字，参数个数等 符号表项的结构可参考教材175页 符号表的组织：顺序表、二叉树、散列表 符号表的建立：在遍历语法树的过程中，遇到声明类节点时，构造符号表项 符号表的使用：在遍历语法树的过程中，遇到语句类节点时，查找符号表项 需要特殊考虑符号表的局部化问题。
实验报告 本次实验采取三人组成开发小组的形式集体讨论合作完成。要求小组人员分工明确，每个人都要参与，了解整个过程。 报告形式见文件“《编译原理课程设计》总结报告模版”。