编译原理 形式语言题+答案

第一篇：编译原理 形式语言题+答案

第2章 形式语言

1．试分别构造产生下列语言的文法：（1）{an#bn|n≥0}∪{cn#dn|n≥0}；

（2）任何不是以0打头的所有奇整数所组成的集合。

答：(1)对应文法为G(S)=({S,X,Y},{a,b,c,d,#}, {S→X, S→Y, X→aXb|#, Y→cYd|# },S)

(2)G(S)=({S,A,B,I,J},{0,1,2,3,4,5,6,7,8,9}, {S→J|IBJ, B→0B|IB|ε, I→J|2|4|6|8, J→1|3|5|7|9},S)

2．对于下列的文法

S→AB|c

A→bA|a

B→aSb|c

试给出句子bbaacb的最右推导。

答：S=>AB=>AaSb=> Aacb=>bAacb=>bbAacb=>bbaacb

3．已知文法G[S]:

S->(AS)|(b)

A->(SaA)|(a)请找出符号串(a)和(A((SaA)(b)))的短语、简单短语和句柄。答：

因为S 不能 (a), 所以(a)不是文法的句型。没有短语、直接短语和句柄。

因为S (AS)(A(AS))(A((SaA)S))(A((SaA)(b))),所以(A((SaA)(b)))是文法的句型。短语：(A((SaA)(b)))，((SaA)(b))，(SaA)，(b)直接短语：(SaA)，(b)句柄：(SaA)S

（A

S)

（A

S)

（S a A)（b)

4．试描述由下列文法所产生的语言的特点：（1）S→10S0

S→aA

A→bA

A→a（2）S→aSS

S→a

答：(1)本文法构成的语言集为：L(G)={(10)nabma0n|n,m≥0}。(2)由L(G)={a2n-1|n≥1}可知，该语言特点是：产生的句子是奇数个a。

附加题：试证明文法

S→AB|DC

A→aA|a

B→bBc|bc

C→cC|c

D→aDb|ab 为二义性文法。

答：因为存在句子：abc，它对应两个最右推导：

S  AB  Abc  abc S  DC  Dc  abc 所以，本文法具有二义性。

第二篇：编译原理 学习心得

国际学院 0802 杨良燕 200819100227

《编译原理》课程学习心得

《编译原理》是计算机专业的一门重要课程，正如教材

第一章的引论所述，“编译程序是现代计算机系统的基本组成部分之一”。“一个编译程序就是一个语言翻译程序，语言翻译程序把一种语言（源语言）书写的程序翻译成另一种语言(目标语言)的等价程序”。

通过这一学期的学习，我觉得编译原理是一门理论性很强的课程，从文法和语言的概念到LL(1)文法和LR（0）文法的分析，几乎都是对具体问题的抽象。因而，我们需要更多的时间来理解、掌握相关的知识，当然在这一过程中也存在很多问题，比如我们后期学习具体文法的分析方法时，对于文法的概念不够清晰，影响了上课的效率，知道老师再次给我们讲解了文法等基础的知识点，我们才慢慢掌握后面所学的LL(1)文法等，也发现了知识点之间的关联。此外，这门课程的课时被安排得很少，一周只有一次，这样很不利于我们对这门重要课程的理解和掌握。但是我觉得我们很幸运，因为老师在有限的课程中尽量将知识点以比较容易接受的方式给我们讲解，教我们用简单的方法理解记忆不同的知识，对于我们提出的问题，无论课上或是课外，老师一直是不厌其烦，甚至利用课余时间为我们讲解重要的难题。

编译原理这门课程不仅仅在于其本身的理论价值，更在于为我们解决问题提供的思维方式和方法。从LL（1）到LR（0），问题不断被解决的同时，又有一个个新的问题提了出来。对计算机语言世界的知识积累，像滚雪球一样越滚越大。这个逐渐递进，逐渐解决问题的过程对我来说是收获很大的。整个过程好像踏着前人研究编译理论的路线，不断感觉他们遇到的问题，更重要的是他们解决问题的思路。编译原理的课程带给我的不只是如何去编译程序这样的理论知识，相信更重要的是一种如何“自动计算”的思路。通过对相关编译问题的具体分析，让我体会最深的是一种“自动计算”的思想，同时完成编译试验后，更是感到了一种“自动计算”的快乐。”然而我明白自己虽然对编译有了一定的了解，我懂得了文法的分析，学会了构造确定和非确定有限自动机，学会了LL(1)文法和LR(0)文法等，但是并没有完全掌握，对于这些知识点的实质性和其他方面，更是认识不深。作为一名学习计算机科学与技术的学生，我明白编译原理是软件工程的基础，课程的结束并不意味着学习的结束，只有通过以后的学习，才能更深入地了解编译原理。

第三篇：编译原理实验报告

编译原理实验报告

报告完成日期 2018.5.30

一． 组内分工与贡献介绍

二． 系统功能概述；

我们使用了自动生成系统来完成我们的实验内容。我们设计的系统在完成了实验基本要求的前提下，进行了一部分的扩展。增加了声明变量类型、类型赋值判定和声明的变量被引用时作用域的判断。从而使得我们的实验结果呈现的更加清晰和易懂。

三． 分系统报告；

一、词法分析子系统

词法的正规式：

标识符

<字母>(<字母>|<数字字符>)* 十进制整数

0 |(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* 八进制整数 0(1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)* 十六进制整数 0x(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f)(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f)* 运算符和分隔符 +| * | / | > | < | = |(|)| <=|>=|==； 对于标识符和关键字: A5—〉 B5C5 B5—〉a | b |⋯⋯| y | z C5—〉(a | b |⋯⋯| y | z |0|1|2|3|4|5|6|7|8|9)C5|ε 综上正规文法为: S—〉I1|I2|I3|A4|A5 I1—〉0|A1 A1—〉B1C1|ε C1—〉E1D1|ε D1—〉E1C1|ε

E1—〉0|1|2|3|4|5|6|7|8|9 B1—〉1|2|3|4|5|6|7|8|9 I2—〉0A2 A2—〉0|B2 B2—〉C2D2 D2—〉F2E2|ε E2—〉F2D2|ε

C2—〉1|2|3|4|5|6|7 F2—〉0|1|2|3|4|5|6|7 I3—〉0xA3 A3—〉B3C3 B3—〉0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f C3—〉(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f)|C3|ε

A4—〉+ |-| * | / | > | < | = |(|)| <=|>=|==； A5—〉 B5C5 B5—〉a | b |⋯⋯| y | z C5—〉(a | b |⋯⋯| y | z |0|1|2|3|4|5|6|7|8|9)C5|ε

状态图

流程图：

词法分析程序的主要数据结构与算法

考虑到报告的整洁性和整体观感，此处我们仅展示主要的程序代码和算法，具体的全部代码将在整体的压缩包中一并呈现

另外我们考虑到后续实验中，如果在bison语法树生成的时候推不出目标的产生式时，我们设计了报错提示，在这个词的位置出现错误提示，将记录切割出来的词在code.txt中保存，并记录他们的位置。

以下是我们的主要代码：

进制的识别：

结果展示：

二、语法分析子系统

根据选择的语法分析方法进行描述

我们使用了递归子程序发，并且对原有的产生式进行了改写，改写后的结果如下： P→LP1|L L→S

S→id=E|{P}|if C then S | if C then S

1else S2 | while C do S1 C→E1C’

C’→>E2|

E→int8E’| int10E’| int16E’| idE’|T E’→+T|-T||+TE’|-TE’

T→int8T’| int10T’| int16T’| idT’|F T’→*F|/F|*FT’|/FT’

F→(E)|int8|int10|int16|id

简化的语法图： S的语法图：

C的语法图：

E的语法图：

T的语法图：

F的语法图：

流程图：

语法分析子系统的主要数据结构与算法

我们采用了自动生成技术，同样在这里也是展示主要的核心功能代码，全部的代码展示在压缩包中：

我们在设计时，实现了产生式对应的字符串同时标识产生式定义的int值 辅助程序：

生成语法树的程序：

1.树节点：

2.创建新节点

3.创建实数类型新节点

4.创建标识符类型新节点

5.输出语法树 三、三地址码生成器

算法的基本思想：

我们增加了声明变量类型、类型赋值判定和声明的变量被引用时作用域的判断。从而使得我们的实验结果呈现的更加清晰和易懂。

在报错的时候，我们会呈现类型、作用域和赋值三种的问题的报错信息。

流程图：

算法展示：

四、实验体会

这次实验其实总的来说是让我们更加清晰的理解到了我们所学的内容。有时候我们上课听讲，课下复习写作业的时候，其实看似掌握了所学内容，但实际上并没有亲身体会的操作很难让我们深刻的理解其中的相关意义。通过这次实验，我们能够从根源处了解到了我们所学的内容，并且基于我们理解之后的输出。比如词法分析不能采用空格来区分单词，因为存在加减乘除等运算符和分隔符，使用空格来区分可能会造成错误的分解。又比如我们再在程序设计中，常常体会到效率的重要性。影响词法分析的效率的主要因素是各个状态的分支如何规划。如果每个进来的单词都能在最短的时间和最少的匹配次数内找到其入口，则效率将得到很大程度上的提高。所以由此我们产生了声明变量类型、赋值和作用域的想法，将其放在最后来进行判断，这样可以提高整体的执行效率。

另外，这次小组成员彼此不在一个班级，这样从某一方面来说，也加强了我们互相快速熟识并团结协作的能力，有了这种体验，我想我们在今后的生活中，面对这种情况的时候，将会变得更加有经验。

五、源程序

词法分析器： 输入结果：

输出结果：

语义分析结果：

输入：

第二组数据的输入：

输出：

三地址码的输入：

第二组数据的输入：

输出：

第四篇：编译原理课程设计

课 程 设 计 报 告

设计题目：一个简单文法的编译器前端的设计与实现

班

级： 计算机1206 组长学号：201239 组长姓名：闫智宣 指导教师：李晓华 设计时间：2014年12月

[在此处键入]

设计分工

组长学号及姓名： 20123974

闫智宣

分工：

语法分析，四元式生成，目标代码优化及生成 组员1学号及姓名：20123977

廖峭 分工：

词法分析，错误处理 组员2学号及姓名：20123959

郭天龙

分工：

符号表生成，语义动作插入，操作界面[在此处键入]

摘要

编译原理课程设计是通过C语言编译器相关子系统的设计，进一步加深对编译器构造的理解；第一部分词法分析，设计各单词的状态转换图，并为不同的单词设计种别码，制作扫描器识别一个个单词，返回值为识别码的序号，返回Token序列。将词法分析器设计成供语法分析器调用的子程序。词法分析器具备预处理功能。将不翻译的注释等符号先滤掉，只保留要翻译的符号串，即要求设计一个供词法分析调用的预处理子程序；第二部分，语法分析，用递归下降法，实现对表达式、各种说明语句、控制语句进行语法分析。若语法正确，则用语法制导翻译法进行语义翻译；生成并打印出语法树；若语法错误，要求指出出错性质和出错位置（行号）。

我们还做了附加功能，即编译后端，有中间代码优化，生成目标代码汇编语言。通过此次课程设计，提高了我们的独立分析问题、解决问题的能力，以及系统软件设计的能力； 提高程序设计能力、程序调试能力，团结协作能力

关键词：词法分析，语法分析，四元式生成，错误处理，符号表生成，语义动作插入，中间代码优化，生成目标代码 [在此处键入]

目录

摘要

1.概述

2.课程设计任务及要求

2.1 设计任务

2.2 设计要求

3.算法及数据结构

3.1算法的总体思想（流程）

3.2 词法分析模块

3.2.1 功能

3.2.2 数据结构

3.2.3 算法

3.3 语法分析模块

3.3.1功能

3.3.2 数据结构

3.3.3算法

3.4 符号表模块

3.4.1功能

3.4.2 数据结构

3.4.3算法

3.5 四元式模块

3.5.1功能

[在此处键入]

3.5.2 数据结构

3.5.3算法

3.6 语义动作分析模块

3.6.1功能 3.6.2 数据结构

3.6.3算法

3.7 错误处理模块

3.7.1功能

3.7.2 数据结构

3.7.3算法

3.8 目标代码模块

3.8.1功能

3.8.2 数据结构

3.8.3算法

4.程序设计与实现

4.1 程序流程图

4.2 程序说明

4.3 实验结果

5.结论 6.参考文献。7.收获、体会和建议。

[在此处键入]

1.概述

编译器是将C语言翻译为汇编语言代码的计算机程序。编译器将源程序（source language）编写的程序作为输入，翻译产生目标语言（target language）机器代码的等价程序。通常地，源程序为高级语言（high-level language），C语言程序，而目标则是 机器语言的目标代码（object code），也就是可以在计算机硬件中运行的机器代码软件程序。这一过程可以表示为：

源程序→编译器 →目标机器代码程序

2.课程设计任务及要求

2.1设计任务

学生在学习《编译原理》课程过程中，结合各章节的构造编译程序的基本理论，要求用C#语言描述及上机调试，实现一个 C编译程序（包括词法分析，语法分析等重要子程序），使学生将理论与实际应用结合起来，受到软件设计等开发过程的全面训练，从而提高学生软件开发的能力。

2.2设计要求 要求：

（1）设计词法分析器

设计各单词的状态转换图，并为不同的单词设计种别码。将词法分析器设计成供语法分析器调用的子程序。功能包括：

a.具备预处理功能。将不翻译的注释等符号先滤掉，只保留要翻译的符号串，即要求设计一个供词法分析调用的预处理子程序；

b.能够拼出语言中的各个单词； [在此处键入]

c.返回（种别码，属性值，行号）。

（2）语法分析

要求用学习过的自底向上或自顶向下的分析方法等，实现对表达式、各种说明语句、控制语句进行语法分析。若语法正确，则用语法制导翻译法进行语义翻译；生成并打印出语法树；若语法错误，要求指出出错性质和出错位置（行号）。

3.算法及数据结构

3.1算法的总体思想（流程）

本节主要分析程序的代码结构和代码工程文件的划分。（程序由几个类组成: Token类和Variable类SymbolTable类ObjectCode类Lexical类Grammar类Four_Yuan类Action类ErrorItem类，分别为词法分析和语法分析类。工程分为几个文件：Form1.cs,Token.cs,Variable.cs,SymbolTable.cs,ObjectCode.cs,Lexical.cs,Grammar.cs,Four_Yuan,cs,Action.cs,ErrorItem.cs分别对应Token类和Variable类SymbolTable类ObjectCode类Lexical类Grammar类Four_Yuan类Action类ErrorItem类的声明和实现文件）。本程序采用C#语言以面向对象的思想编写，程序分为几部分：词法分析（Lexical），语法分析（Grammer），目标代码生成（ObjectCode）。Lexical类主要的工作是词法分析获取Token。Grammer类的主要工作是根据Lexical类词法分析之后的Token进行语法分析，生成语法树，最后并输出语法树。在处理过程中，Token类的对象作为Lexical类的一个成员变量，配合Grammer类进行语法分析。

工程文件总体上是按照九个类的格局分为十个文件，分别是九个类的声明文件和实现文件。十个文件为Form1.cs,Token.cs,Variable.cs,SymbolTable.cs,ObjectCode.cs,Lexical.cs,Grammar.cs,Four_Yuan,cs,Action.cs,ErrorItem.cs，他们分别是Lexical类声明文件、Lexical类实现文件、Grammer类声明文件、Grammer类实现文件。[在此处键入]

程序流程

在程序中，Lexical类的对象(Token)作为Grammer类中的一个成员变量，配合Grammer类进行语法分析。它们的关系是这样的：Grammer类的一个成员变量temp首先对源程序删除注释，然后进行词法分析获取所有Token，并将获取的Token存储在Token对象的tokenList（List类型）中。然后Grammer类的语法分析程序就根据tokenList中的Token进行语法分析，生成语法树，最后打印语法树。同时，这也是程序的流程。[在此处键入]

3.2 词法分析模块 3.2.1功能

Lexical类主要的工作是词法分析获取Token序列。

3.2.2数据结构

词法分析阶段的代码被封装成一个类——Lexical，Token中主要是Lexical类的声明代码，Lexical.cs中主要是Lexical类的实现代码。Lexical类对外提供的函数主要有：

static public int RecogId(string str, int i)，static public int RecogDig(string str,int i)，static public int RecogOperator(string str, int i)，static public int RecogBound(string str, int i)，以上几个函数构成了词法分析的骨架，在Lexical类中还有其他成员变量和函数，主要作为这三个函数处理过程的中间步骤，为这三个函数服务。Lexical类的代码结构和主要的成员变量和函数及其含义如下图所示：

3.2.3算法

算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是[在此处键入]

根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。

主程序示意图：

主程序示意图如图3-1所示。

⑴ 关键字表的初值。

关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。

（2）程序中需要用到的主要变量为type和number 扫描子程序的算法思想：

首先设置3个变量： [在此处键入]

①token用来存放构成单词符号的字符串； ②number用来整型单词；

③type用来存放单词符号的种别码。

Token定义

Token定义:

Token类型（TokenType）:

3.3 语法分析模块

3.3.1功能

语法分析是编译过程的一个逻辑阶段。语法分析的功能是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.3.3.2 数据结构

下图为实现语法分析的类Grammar，属性与方法的作用都已说明 在此处键入]

3.3.3算法

1.文法

下面终结符与非终结符意义

B程序开始

Z 数据类型，如int,char,float等

V 标识符

S 语句

P 语句块

E 加减算术表达式

D 逗号表达式

T 乘除算术表达式

C 关系表达式

L 逻辑表达式

Q 标识符或圆括号

e 表示空

i 表示标识符 a)函数文法

B----ZV()S

[

[在此处键入]

b)语句块文法

P----SP|e

S----{P} c)语句文法

表达式语句文法

S----V=E

goto语句文法

S----i:S

S----goto i

if语句文法

S----if(E)S[else S]

while语句文法

S----while(E)S

声明语句文法

S----ZVD

D----,VD|=ED|e d)表达式文法

E----T|E+T|E-T

T----F|T*F|T/F

C----C|CL|C==C|C<= L|C>=L

L----Q|L&&Q|L||Q

Q----i|(E)|!Q

2.递归下降程序流程图

对应于每个文法编写如下递归下降子程序

主程序（B）[在此处键入] [在此处键入]

3.4 符号表模块

3.4.1功能

进行符号表的储存，添加，更新，查找，保存标识符活跃信息以及输出。3.4.2 数据结构

在此处键入]

3.4.3算法

3.5 四元式模块

3.5.1功能

四元式为中间代码，编译程序进行完语义分析后，先生成中间代码作为过渡，此时中间代码与目标代码已经比较相似

3.5.2 数据结构

[ 在此处键入]

3.5.3算法

3.6语义动作分析模块

3.6.1功能

在语法分析中嵌入相应的语义动作，生成四元式 3.6.2 数据结构

[

[在此处键入]

3.6.3算法 GEQ(+)(-)(*)(/)

(+,i1,i2,t)PUSH(i)ASSI(=)

(=,t,_,POP)LABER(i)

(lb,_,_,i)GOTO(i)

(gt,_,_,i)IF(if)

(if,a,_,_)EL(el)

(el,_,_,_)IE(ie)

(ie,_,_,_)WH()

(wh,_,_,_)DO()

(do,a,_,_)WE(we)

(we,_,_,_)

3.7 错误处理模块

3.7.1功能 保存运行时发现的错误，储存行号已经详细信息并输出。

3.7.2 数据结构

3.7.3算法 [在此处键入]

public static void AddErrorMessage(int lineno,string content)函数用作在发现错误时保存错误信息以及行号。

public static string PrintErrorList()把所有发现的错误格式化后统一输出。

错误信息在语法分析，语义分析，符号表检错中添加。3.8 目标代码模块

3.8.1功能

目标代码生成把优化后的中间代码变换成目标代码，此处的目标代码为汇编代码，采用单寄存器生成目标代码 3.8.2 数据结构[在此处键入]

3.8.3算法

对于一个基本块有如下流程图

W：操作符，B：第一操作数，C：第二操作数，R：寄存器

5.结论

网上找一段话抄上 [在此处键入]

6.测试

测试打开文件

测试保存文件

如果没打开文件，直接敲代码，点保存时会弹出另存为窗口[在此处键入]

测试错误检测，程序缺少main函数的类型，错误列表中显示第一行函数缺少错误类型。

测试错误检测，程序缺少分号，错误列表中显示该行缺少语句结束标志';' 单击错误列表，会自动选定错误行

编译成功，生成并显示token串、符号表、四元式与目标代码 [在此处键入]

测试if与while语句，而且while嵌套在if当中

测试goto语句，结果正确。[在此处键入]

测试优化，输入课件中的代码，结果与课件一样

6.参考文献。

1、陈火旺.《程序设计语言编译原理》（第3版）.北京：国防工业出版社.2000.2、美 Alfred V.Aho Ravi Sethi Jeffrey D.Ullman著.李建中，姜守旭译.《编译原理》.24 [在此处键入]

北京：机械工业出版社.2003.3、美 Kenneth C.Louden著.冯博琴等译.《编译原理及实践》.北京：机械工业出版社.2002.4、金成植著.《编译程序构造原理和实现技术》.北京：高等教育出版社.2002.7.收获、体会和建议。

直接拷贝好歹也检查一下错误

对于编译原理的这次课程设计，自己经历了从刚开始的不懂明白任务的要求和内容理论知识的了解开始着手写代码完成基本功能根据DFA及自顶向下等理论修改完善代码等这些过程。

自己着手写词法分析的时候还不清楚词法分析的任务内容，还不知道词法分析的结果是什么，词法分析出错的情况和类型有哪些，也总是将词法分析和语法分析混在一起，不明白哪些错误在词法分析中报，哪些错误在语法分析中判断，后来经过查书、网上资料、请教同学等途径逐步清晰了词法分析的工作内容是从源代码文件中获取出Token，供语法分析使用。在充分了解了语法分析需要哪些信息时，我才真正了解了词法分析的工作内容和目标，才知道词法分析需要完成哪些任务获取到哪些信息。充分了解了词法分析的任务之后，就开始理论知识的学习。经过揣摩书上的例子，自己理解和掌握了怎么设计过滤注释和分析程序中Token的DFA，于是开始根据设计好的DFA进行编码，最后经过调试已经可以正确地完成词法阶段的任务了。这只是词法分析的原始代码，在之后还进行了两次彻底的改动。虽然之前写的词法分析的代码已经完成了词法分析的需求，也是根据DFA的原理编写的，但是在代码结构上却难以体现，在对书上的根据已知DFA写代码的例子进行了详细的研究之后，发现自己的代码并没有像书上那样完全按照所依据的DFA各状态转移的关系进行编写，所以对代码进行了重写，像书上一样严格按照状态之间转移的方式进行编写，将状态划分成11个状态，状态分别按1~11进行标注，程序也按照DFA来编写，也实现了词法分析的功能。再后来写报告的时候，发现分析出Token的那个DFA并不是最简的，有很多多余的状态，完全可以用一个flag标志来标识，从而简化代码结构，于是又重写了一次词法分析函数scan()的代码，将状态缩减为5个，且不再用1-5来表示，而是像书上那样分别取了名字（START、INNUM、INID、INDBSYM、DONE），同时为了简化代码将输出Token到文件的部分从scan()中剥离开来，而在Lexical类中加了一个printToken()的函数，使scan()函数逻辑更加清晰，使读者能够容易地将代码与DFA进行查看比照。

在写语法分析的时候，已经对编译器的语法分析的内容有了一定的了解，所以直接进行了理论的学习。首先自己对递归向下分析法进行了学习，将书上的几个递归向下分析的伪代码看过之后，自己对递归向下的分析方法的原理有了初步的认识，大概知道了根据文法怎么分析，但是对于如何编写代码却还在此处键入]

是难以下手，于是就对照TINY语言的文法看了几遍书后面的TINY语言的递归向下分析的语法分析程序，这样就基本知道了C-语言的语法分析程序怎么写。由于C-语言给出的文法有左递归存在，于是自己将存在左递归的文法改写成EBNF的形式，并据此进行代码编写。由于在编写代码的过程中需要确定分析是否正确或选择多个文法中的某一个文法进行分析，有时必须探测需要的或下一个Token的类型，在这种情况下需要求First集合，在推导中若存在empty，又需要求Follow集合，所以这样又需要我了解First集合和Follow集合，自己在程序中也根据求出的First集合和Follow集合进行判断，以确定程序的走向。在编写过程中，还有一类问题，就是存在公共左因子，如文法expression→ var = expression | simple-expression，左因子为ID，在分析过程中，由于已经取出了一个ID的Token，且生成了一个IdK的节点，但是在当前状态无法确定是哪一个推导，然而IdK节点已经生成，又无法回退，并且是使用自顶向下的分析方法，已经生成的IdK在程序上方无法使用，自己通过查阅资料等途径的学习确定了在这种情形下的处理方式：将已经生成的IdK节点传到下方的处理程序，所以TreeNode * simple_expression(TreeNode * k)、TreeNode * additive_expression(TreeNode * k)等函数都被设计成有节点类型参数的函数，目的就是将已经生成的节点传到下面的分析函数中去。

通过这次的编译原理课程的学习和实践，自己获益良多。首先最基本的成果是完成了课程设计的任务，实现了编译器的词法分析和语法分析阶段的功能，词法分析主要能过滤注释、分析出语法分析阶段需要的Token并满足语法阶段的所有要求，能够判别词法分析阶段是否出错和出错类型和位置。语法分析主要能根据递归向下的分析思想和C-文法对词法分析获取的Token进行语法分析，能够构造出语法树，能够判别语法分析过程中是否出错以及出错位置和错误类型。

由于在编写程序过程中，涉及到了正则表达式、DFA、提取公共左因子、消除左递归、EBNF、求First集合和Follow集合、递归向下分析方法以及编程语言方面的知识，所以，通过本次的课程设计的实践，使得自己对编译原理这门课的许多知识点有了更加深刻和具体的理解，而不再只限制于做题。此外，对以前那些已掌握的知识有了温习和动手锻炼的机会。如：以前在编译原理课上虽然知道First集合和Follow集合怎么求的，却不知道First集合和Follow集合到底是干什么的，通过编写程序自己明白了他们的实际作用，使得自己不仅知其然还知其所以然，从而使得自己加深了对知识点的理解和掌握。由于以前编写代码都是使用JAVA语言，所以C/C++很多内容都忘记了，通过本次的实践，自己又重新拾起了以前的知识。此外，由于在做报告的时候，需要描绘DFA和程序流程图，使得自己初步掌握了使用visio和word画图的能力。此外，对于文档的编写和美化自己也获得了许多有用的经验。[

第五篇：编译原理教学大纲（范文模版）

编译原理教学大纲

一、课程的性质、地位

本课程是计算机专业的重要专业课之一，是一门理论性和实践性较强的课程。主要介绍程序设计语言编译程序构造的基本原理和基本实现方法。本课程主要讲授形式语言、有限自动机、自上而下和自下而上的语法分析、LR分析方法、属性文法和语法制导翻译、语义分析的代码产生、存储器的动态分配与管理、符号表的组织与管理、优化问题、代码生成等内容。通过本课程学习，使学生对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地运用。

二、课程的目的、任务和要求

该课程的目的是让学生掌握程序设计语言编译程序构造的一般原理、基本设计方法、主要实现技术和一些自动构造工具。通过本课程的学习，使学生较好地掌握编译原理的基本原理和基本技术、编译原理中涉及的基本算法、基本结构和主要实现技术，从而让学生了解将高级程序设计语言源程序翻译成计算机能处理的目标代码语言的整个过程，基本掌握计算机系统软件之一 编译程序的构造原理及相关技术，同时，还可提高学生计算机专业素质，培养学生的抽象思维能力。通过学习，学生可基本掌握计算机系统软件之一 编译程序的构造原理及相关技术，同时，还可提高学生计算机专业素质，培养学生的抽象思维能力。

三、与其它课程的关系

要求学生具有较好的计算机基础知识，对计算机的工作原理有一定了解，前导课程包括：高等数学、线性代数、计算机原理、离散数学、高级程序设计语言、数据结构等课程。

四、课程内容(建议理论课时：62 上机课时：18)第一章 编译程序概论

1、教学目的及要求：

本章介绍编译程序在计算机科学中的地位和作用，介绍编译技术的发展历史，讲解编译程序、解释程序的基本概念，概述编译过程，介绍编译程序的逻辑结构和编译程序的组织形式。要求理解编译程序、解释程序和遍的基本概念；掌握编译过程各阶段的任务和编译程序逻辑结构及其各部分的基本功能。

2、教学内容：

编译程序，编译过程概述，编译程序的结构，编译程序与程序设计环境，编译程序生成，学习构造编译程序。

3、教学重点：

重点：编译程序工作的基本过程及其各阶段的基本任务，编译程序总框。

4、教学难点：

编译的遍。

5、教学时间分配及进度安排：

建议本章教学时数2学时。

6、章节内容

1、什么是编译程序

2、编译过程概述

3、编译程序的结构

4、编译技术和软件工具 第二章 文法和语言

1、教学目的及要求：

本章是编译原理课程的理论基础，要求理解文法、语言、规范推导、规范归约和短语、简单短语、句炳的基本概念；掌握语言的求解方法、文法的二义性与递归性的判断方法及句型的分析方法。

2、教学内容：

形式语言的基本概念，包括符号串的基本概念和术语、文法和语言的形式定义、句型分析、文法和语言的Chomsky分类，二义性。

3、教学重点：

上下文无关文法，语言定义。

4、教学难点：

推导，文法与语言的相互转换。

5、教学时间分配及进度安排：

建议本章教学时数5学时。

6、章节内容

1、文法的直观概念

2、符号和符号串

3、文法和语言的形式定义

4、文法的类型

5、语法树和二义性

6、句型的分析

7、文法中的实用限制 第三章 词法分析

1、教学目的及要求：

本章介绍编译程序的第一个阶段词法分析的设计原理和设计方法，要求掌握正则文法、状态转换图、DFA、NFA、正规式和正规集的基本概念和词法分析设计与编写。

2、教学内容：

词法分析的设计原理和设计方法，源程序输入与词法分析程序输出、正则文法及其状态转换图、确定的有限自动机（DFA）不确定的有限自动机（NFA）正则表达式与正规集。

3、教学重点：

重点：词法分析器的任务与设计，状态转换图。

4、教学难点：

正则文法、正规集、DFA、NFA的相互转化。

5、教学时间分配及进度安排：

建议本章教学时数8学时。

6、章节内容

1、词法分析程序的设计

2、单词的描述工具

3、有穷自动机

4、正规式和有穷自动机的等价性

5、正规文法和有穷自动机间的转换 第四章 语法分析—自上而下分析

1、教学目的及要求：

本章介绍编译程序的第二个阶段语法分析的设计方法和实现原理，包括自上而下分析的无回朔的递归下降分析、LL(1)分析法。要求理解递归下降分析、LL(1)文法的基本概念；掌握无回朔的递归下降分析的设计和实现、LL(1)分析表的构造与分析方法。

2、教学内容：

语法分析器的功能，自上而下语法分析（递归下降分析法，预测分析程序），LL（1）分析法，递归下降分析程序构造，预测分析程序。

3、教学重点：

递归下降子程序，预测分析表构造，LL(1)文法。

4、教学难点：

LL(1)文法预测分析表构造。

5、教学时间分配及进度安排：

建议本章教学时数5学时。

6、章节内容

1、确定的自顶向下分析思想

2、LL（1）文法的判别

3、某些非LL（1）文法到LL（1）文法的等价变换

4、不确定的自顶向下分析思想

5、确定的自顶向下分析方法 第五章 语法分析—自下而上分析

1、教学目的及要求：

要求理解算符优先文法、最左素短语、有效项目的基本概念；掌握算符优先分析方法、LR(0)文法的判断及LR(0)分析表的构造与分析方法、SLR(1)文法的判断与SLR(1)分析方法和LR(1)文法的判断与LR(1)分析方法。

2、教学内容：

自下而上语法分析（算符优先分析法），算符优先分析，LR分析器，LR(0)项目集族和LR(0)分析表的构造，SLR分析表的构造，规范LR分析表的构造。

3、教学重点：

归约，算符优先表构造，LR分析法。

4、教学难点：

归约，LR分析法。

5、教学时间分配及进度安排：

建议本章教学时数12学时。

6、章节内容

1、自底向上分析思想

2、算符优先分析法

3、LR分析法 第六章 属性文法和语法制导翻译

1、教学目的及要求：

本章介绍编译程序的第三个阶段语义分析及中间代码生成的设计原理和实现方法，要求理解语法制导翻译、语义动作的基本概念；掌握算数表达式和赋值语句到中间代码的翻译、布尔表达式和几种控制语句的目标代码结构分析和到四元式的语法制导翻译；说明语句的语法制导翻译。

2、教学内容：

语法制导翻译的基本概念、中间代码的形式，可执行语句和说明语句的语法制导翻译方法。

3、教学重点：

语法制导翻译基本思想，语法制导翻译概述，基于属性文法的处理方法，自下而上分析制导翻译概述。

4、教学难点：

属性文法的处理方法

5、教学时间分配及进度安排：

建议本章教学时数9学时。

6、章节内容

1、属性文法

2、语法制导翻译概论

3、中间代码的形式

4、简单赋值语句的翻译

5、布尔表达式的翻译

6、控制语句的翻译 第七章 符号表

1、教学目的及要求：

本章介绍编译程序的组成部分之一符号表的管理，要求掌握符号表管理的基本方法。

2、教学内容：

符号表的作用、建立、符号表栏目的组织、符号表上的操作。

3、教学重点：

符号表的作用与内容。

4、教学难点：

符号表的内容。

5、教学时间分配及进度安排：

建议本章教学时数3学时。

6、章节内容

1、符号表的作用和地位

2、符号表的主要属性及作用

3、符号表的组织

4、符号表的管理 第八章 运行时存储空间组织

1、教学目的及要求：

本章介绍目标程序运行时的存储组织方式，包括静态存储分配和动态存储分配。要求掌握各种存储组织形式的基本方法。

2、教学内容：

目标程序运行时的活动，运行时存储器的划分，静态存储管理，简单的栈式存储分配的实现，嵌套过程语言的栈式实现，堆式动态存储分配。

3、教学重点：

静态分配策略和动态分配策略基本思想，嵌套过程语言栈式分配，活动记录、运行时栈的组织。

4、教学难点：

嵌套过程语言栈式分配，活动记录、运行时栈的组织。

5、教学时间分配及进度安排：

建议本章教学时数9学时。

6、章节内容

1、数据空间的三种不同使用方法

2、栈式存储分配的实现

3、参数传递

第九章 代码优化

1、教学目的及要求：

本章介绍优化的相关知识，要求掌握局部优化，基本块的DAG表示及其应用，控制流分析和循环查找算法，到达定值与引用定值链，循环优化。

2、教学内容：

主要内容：优化概述，局部优化，基本块的DAG表示及其应用，控制流分析和循环查找算法，到达定值与引用定值链，循环优化。

3、教学重点：

局部优化；DAG的构造与应用。

4、教学难点：

循环查找。

5、教学时间分配及进度安排：

建议本章教学时数6学时。

6、章节内容

1、优化技术简介

2、局部优化

3、控制流分析和循环优化 第十章 代码生成

1、教学目的及要求： 本章介绍编译程序的第五阶段目标代码的生成的设计原理和实现方法，要求掌握四元式到汇编语言的目标代码生成方法。

2、教学内容：

目标机器模型，一个简单代码生成器，寄存器分配，DAG目标代码，窥孔优化。

3、教学重点：

简单代码生成器，寄存器分配策略。

4、教学难点：

寄存器分配策略。

5、教学时间分配及进度安排：

建议本章教学时数3学时。

6、章节内容

1、代码生成概述

2、一个计算机模型

3、一个简单的代码生成器

4、代码生成研究现状

注：使用教材－编译原理（第二版）.张素琴，吕映芝，蒋维杜，戴桂兰编著，清华大学出版社，2005.2。参考书：

1）编译原理, 何炎祥, 华中理工大学出版社, 2000.10 2）编译原理, 陈火旺等, 国防工业出版社, 2000.1 3）编译原理, 蒋立源, 西北工业大学出版社, 1999.9