(1)程序设计语言
?机器语言: 由0、1代码构成，不需翻译就可直接执行其程序。
?汇编语言: 机器指令助记符（伪代码）形式，汇编后才可执行其程序。
?高级程序设计语言: 类自然语言和数学公式形式
(2) 基本术语
?源程序(Source Program)：用源语言写的程序。源语言可以是汇编语言，也可以是高级程序设计语言。
?目标程序(Target Program) ：也称为“结果程序”，是源程序经翻译程序加工以后所生成的程序。目标程序可以用机器语言表示，也可以用汇编语言或其它中间语言表示。
?翻译程序(Translating Program)：是指把一个源程序翻译成逻辑上等价的目标程序的程序。
源程序为其输入，目标程序为其输出。
?汇编程序(Assembler)：是指把一个汇编语言写的源程序转换成等价的机器语言表示的目标程序的翻译程序。
?编译程序(Compiler)：若源程序是用高级程序设计语言所写，经翻译程序加工生成目标程序，则该翻译程序就称为“编译程序”，也可称为编译器。
?解释程序：是高级语言翻译程序的一种，他将源语言书写的源程序作为输入，解释一句后就提交计算机执行一句，并不形成目标程序，就像外语翻译中的“口译”一样，不产生全文的翻译文本。
?运行系统(Running System)：目标程序执行时，需要有一些子程序（如一些连接装配程序及一些连接库等）配合进行工作，由这些子程序组成的一个子程序库称为运行系统。?编译系统(Compiling System)：编译程序和运行系统合称编译系统。
(3) 程序的翻译
?除机器语言程序外，用其它语言书写的程序都必须经过翻译才能被计算机识别。这一过程由翻译程序来完成。
?编译方式是一种分阶段进行的方式，包括翻译和运行两部分。
?前一阶段：翻译
?后一阶段：运行，由运行系统配合完成。
(4) 过程
1、词法分析阶段
这个阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词（也称单词符号或符号TOKEN）。
某源程序片断如下：
begin var sum, first, count: real; sum:=first+count*10 end.
保留字begin var real end
标识符sum first count sum first count
界符.
逗号，逗号, 冒号：分号；加号+ 乘号* 赋值号：= 整数10 10 2、语法分析阶段
是编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。一般这种语法短语，也称语法单位，或语法成分，或语法范畴。
语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。
3、语义分析阶段
依据语言的语义规则，对语法分析得到的语法结构分析其含义以及应进行的运算，审查源程序中有无语义错误，为代码生成阶段收集类型信息。
4、中间代码生成
在进行了上述的语法分析和语义分析阶段的工作之后，有的编译程序将源程序转变成一种内部表示形式，这种内部表示形式叫做中间代码。
所谓“中间代码”是一种结构简单，含义明确的记号系统，这种记号系统可以设计为多种多样的形式。
重要的设计原则：一是容易生成；二是容易将它翻译成目标代码。
5、代码优化
任务：对前阶段产生的中间代码系列进行变换或改造。目的是使生成的目标代码更高效，即省时间省空间。例如上例四个四元式可优化为下面两个四元式。
6、目标代码生成
任务：将中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。它的工作与硬件系统结构和指令含义有关。
7、表格管理
编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；
8、出错处理
如果编译过程中发现源程序有错误，编译程度应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。
(5) 前端与后端
参考上面的图，目的是为了在多种源语言和多种目标语言的开发过程中，可以灵活搭配组合，消除重复开发的工作量，提高编译系统的开发效率。
(6) 遍
所谓遍，是对源程序或源程序的中间形式从头到尾扫视并完成规定任务的过程。
每一遍扫视可完成一个阶段或多个阶段的功能。
一遍的编译程序：以语法分析程序为核心。
多遍扫描的优点：
可以减少内存容量的需求，分遍后，以遍为单位分别调用编译的各个程序，各遍程序可以相互覆盖。
可使各遍的编译程序相互独立，结构清晰。
能够进行充分优化，产生高质量的目标程序。
可将编译程序分为前端和后端，有利于编译程序的移植。
多遍扫描的缺点
每遍都要读符号、送符号，增加了许多重复性的工作，降低编译效率。
(7) 程序设计语言范型（从支持的计算模式）
1. 强制(命令)式语言:是面向动作的，即一个计算过程看做是一系列动作，其动作是命令驱动，以语言形式表示。
也称过程式语言，如C,FORTRAN等;
2. 函数式语言：注重程序表示的功能
也称应用式语言，如ML和LISP等；
3. 基于规则的语言：检查一定的使能条件，满足时执行动作
也称逻辑程序设计语言，如PROLOG。
4. 面向对象语言：提供抽象数据类型，支持封装性、继承性和多态性。
如C++和Java等。
(1)符号和符号串
1、字母表：元素的有穷非空集合。
2、符号串：由字母表中的符号组成的任何有穷序列。
3、符号串的头尾，固有头和固有尾：如果z=xy是一符号串，那么x是z的头，y是z
的尾，如果x是非空的，那么y是固有尾；同样如果y非空，那么x是固有头。
如:设z=abc，那么z的头是ε，a, ab, abc, 除abc外，其它都是固有头；z的尾是ε, c, bc, abc, z的固有尾是ε, c, bc。
4、符号串的运算
（1）符号串的连接：设x和y是符号串，x和y的连接xy是把y的符号写在x的符号ε后得的符号串。
如：x=ST, y=abu, 则xy=STabu 显然有εx=xε=x。
（2）符号串的方幂：设x是符号串，把x自身连接n次得x的几次方幂x n。
如：设x=ab则x0=εx1=ab x2=abab x3=ababab
（3）符号串集合的乘积：设A和B为符号串集合，则A和B的乘积定义为AB={xy|x∈A 且y∈B}
如：a={a, b}, B={00, 11} 则AB={a00, a11, b00, b11} 显然：{ε}A=A{ε}=A （4）符号串集合的方幂：设A为符号串集，则A的n次方幂An定义为:An=AA……A=AAn-1=An-1A
（5）符号串集合的正闭包A+：A+=A1 U A2 U … U An U …
（6）符号串集合的闭包A*：A*=A0 U A+ = {ε} U A+
如：设有正字母表∑={0，1} 则∑*=∑0 U ∑1 U ∑2 U … U ∑n U …={ε, 0, 1, 00, 01, 10, 11, 000, 001,……}
(2)文法
文法G定义为四元组（V N，V T，P，S）其中:
（1）VN 为非终结符号集
非终结符号表示一个语言短语（或语法成分、语法单位）。如程序、语句、表达式等。一般用大写字母或用〈〉括起表示非终结符号。
（2）VT 为终结符号集
终结符号：组成语言的基本符号。是文法中不属于非终结符号集合的符号。一般用小写字母或不带〈〉的符号表示。如程序设计语言的单词符号。
设V=VN U VT，称V为文法G的字母表。
（3）P 为产生式（也称规则）的集合。
产生式的形式：α→β或α∷=β，其中α∈V+，β∈V*
（4）S 称作识别符号或开始符号，是一个非终结符号。
一般表示此文法定义的最大语法短语，至少要在一条产生式中作为左部出现。
句型、句子的定义
设G[S]是一文法，如果符号串x是从识别符号推导出来的，即有S?*x，则称x是文法G[S]的句型。
若x仅由终结符号组成，即S?*x, x∈V T ，则称x为G[S]的句子。
句型：在一棵树生长过程的任何时刻，所有那些端末结点自左至右的排列，就是一个句型。
语言的定义：文法G产生的语言记为L（G），它是文法G产生的全部句子的集合。
文法等价定义：若L（G1）=L（G2）则称文法G1和G2是等价的。
(3)文法的类型N.Chomsky
0型文法：定义0型语言，对应Turing机；
1型文法：定义1型语言，对应线性限界自动机；箭头后面的要比前面的长或相等
2型文法：定义2型语言，对应非确定下推自动机；箭头前面的是非终结符，后面是串3型文法：定义3型语言，对应有限自动机。非终结符可以推出一个终结符或一个终结符和一个非终结符
最右推导也称为规范推导，所得句型称为规范句型。
如果一个文法存在某个句型对应两棵不同的语法树，则说这个文法是二义的。或者说，若一个文法中存在某个句型，它有两个不同的最左（最右）推导，则这个文法是二义的。
上下文无关文法是否具有二义性是不可判定的。
但有些特殊的2型文法[例如LL（1）、LR（0）、LR（1）等文法]是无二义性的。
一个文法兼有左递归和右递归是导致二义性的常见原因。
排除文法二义性通常有两种方法:
（1）在语义上加些限制
（2）重新构造一个无二义性的文法
(4) 句型的分析
句型的分析：就是识别一个符号串是否为某文法的句型。是某个推导的构造过程。
分析方法分两大类：自上而下分析法和自下而上分析法推导与归约，最右推导是规范推导，逆过程为规范规约
若S?*αAδ?+αβδ（由A?+β得）则称β是句型αβδ相对于非终结符A的短语。
若S?*αAδ?αβδ (由A→β得)则称β是句型αβδ相对于A→β的直接短语（也称简单短语）。
一个句型的最左直接短语称为该句型的句柄。
一棵子树（至少要有父子两代）的所有端末结点自左至右排列起来形成相对于子树根的短语。若子树只有父子两代，则得到直接短语。
(5) 有关文法
（1）有害规则文法中含形如U→U的产生式。
它对描述语言没有必要，且会引起文法的二义性。
（2）多余规则文法中任何一个句子的推导都用不到的规则。
（3）无用规则文法中含形如U→V的产生式，即单产生式。
为保证文法G的任一非终结符A在句子推导中出现，必须满足如下两个条件：
（1）A必须在某句型中出现，αAδ。
（2）必须能够从A推导出终结符号串t。
有关文法的化简和改造，包括以下几项工作：
（１）无用符号和无用产生式的删除。
（２）ε－产生式的消除。
（３）单产生式的消除。
（４）左递归的消除。
(1)词法分析输出
单词符号（TOKEN) 是一个程序设计语言的基本语法符号。程序设计语言的单词符号一般可分成下列5种：
1．基本字，也称关键字，如PASCAL语言中的begin，end，if，while和var等。
2．标识符，用来表示各种名字，如常量名、变量名和过程名等。
3．常数，各种类型的常数，如25，3.1415，TRUE和"ABC"等。
4．运算符，如+，*，<= 等。
5．界符，如逗点，分号，括号等。
词法分析程序所输出的单词符号常常采用下二元式表示：（单词种别，单词自身的值）
可用整数码或助记符等表示。
(2)单词的描述工具
程序设计语言中的单词(TOKEN)是基本语法符号。单词符号的语法可以用有效的工具加以描述。
正规式和它所表示的正规集的递归定义如下。设字母表为∑，辅助字母表∑={ |, ·, *, (, ) }
定义（正规式和它所表示的正规集）：
设字母表为Σ，辅助字母表Σ`={Φ，ε，|，·，*，(，}。
②ε和Φ都是Σ上的正规式，它们所表示的正规集分别为{ε}和{ }；
②任何a∈Σ，a是Σ上的一个正规式，它所表示的正规集为{a}；
③假定e1和e2都是Σ上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1|e2, e1·e2, e1*也都是正规式,它们所表示的正规集分别为L(e1), L(e1)∪L(e2), L(e1)L(e2)和(L(e1))*。
④仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式，仅由这些正规式所表示的字集才是Σ上的正规集。
(3)有穷自动机
有穷自动机（也称有限自动机）作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程
序的自动构造寻找特殊的方法和工具。
确定的有穷自动机（DFA）：
定义：一确定的有穷自动机（DFA）M是一个五元组：M=（K，∑，f, S, Z）其中1．K是一个有穷集，它的每个元素称为一个状态；
2．∑是一个有穷字母表，它的每个元素称为一个输入字符，所以也称为输入符号字母表；
3．f是转换函数，是在K×∑ →K上的映像，即，如f(ki,a)= kj, 就意味着，当前状态为ki，输入字符为a时，将转换到下一状态kj，我们把kj称为ki的一个后继状态；
4．S 是唯一的一个初态；
5．Z是一个终态集，终态也称可接受状态或结束状态。
DFA的作用：
对于∑*中的任何字符串t，若存在一条从初态到某一终态结的道路，且这条路上所有弧的标记符连接成的字符串等于t，则称t可为DFA M所接受，若M的初态结同时又是终态结，则空字可为M所识别。
DFA M所能接受的字符串的全体记为L（M）。
不确定的有穷自动机（NFA）
定义：一个不确定的有穷自动机（NFA）M是一个五元组，M=（K，∑，f, S, Z）。
3.f是一个从K×∑*到K的幂集的映象
4.S属于K，是一个非空初态集
5.Z属于K，是一个终态集
区别：
DFA：只有唯一初态。NFA：有初态集。
DFA是NFA的特例。
对于每个NFA M，存在一个DFA M’ ，使得L（M）=L（M’ ）
对于任何两个有穷自动机M和M’ ，如果L（M）=L（M ’ ），则称M与M’ 是等价的。
(1)自顶向下语法分析
语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子。
其中自顶向下分析，就是从文法的开始符号出发企图推导出与输入的单词串完全匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。
FIRST（α）={a|α?aβ, a ∈V T, α, β∈V*}
（1）求FIRST（x），x∈V
（a）若x∈V T，则FIRST（x）={x}
（b）若x是ε，则FIRST（x）={ε}
（c）若x∈VN，且x→y1y2…ym|…|z1z2…zn
则FIRST（x）= FIRST(y1y2…ym) ∪…∪FIRST(z1z2…zn)
（2）求FIRST(y1y2…y m), 其中y1, y2, …, y m∈V。
（a）若y1∈VT, 则FIRST（y1y2…ym）={y1}
（b）若y1∈VN, ε? FIRST(y1)，则FIRST（y1y2…ym）=FIRST(y1)
若ε∈ FIRST(y1)，则FIRST(y1y2…ym)=(FIRST(y1)\{ε})∪FIRST(y2y3…ym)
按上法求FIRST（y2y3…ym），类推下去。
对文法中每一A ∈V N，计算FOLLOW（A）
（a）设S为文法的开始符号，则#∈FOLLOW（S）
（b）若有A→αBβ，则将FIRST（β）－{ε}加入到FOLLOW（B）中，如果其中β?ε，则将FOLLOW（A）加入到FOLLOW（B）中。
计算SELECT集
定义：SELECT ( A→α ) =FIRST ( α ),其中α?ε。
若α?ε，则SELECT ( A→α ) = (FIRST（α）－{ε}) ∪FOLLOW(A)
判定LL（1）文法
对每个非终结符A的两个不同产生式，A→α，A→β，满足SELECTC（A→α）∩SELECT（A→ β）=φ其中α、β不能同时?ε
(2) 非LL（1）文法到LL（1）文法的等价变换
由LL（1）文法的定义可知,若文法中含有直接或间接左递归，或含有左公共因子,则该文法肯定不是LL（1）文法。
参考：https://www.doczj.com/doc/b32261055.html,/comp/cmpl4/4-3.htm
文法含左递归不便于使推导按从左往右的顺序匹配，甚至使分析发生死循环。
（a）消除直接左递归
一般情况下，直接左递归的形式为：
A→A α1|A α2|…|A αm|β1|β2|…|βn
消除左递归后改写为：
A→β1A'|β2A'|…|βnA'
A'→ α1 A'| α2 A'| … | αm A' | ε
（b）消除间接左递归
先通过产生式的替换，将间接左递归变为直接左递归，然后再消除直接左递归。
(3) 确定的自顶向下分析方法
1、基本思想
对每一非终结符构造一个过程，每个过程的功能是识别由该非终结符推出的串。
2、编写程序
IP：是输入串指示器，开始工作前IP指向串的第一个符号，每个程序工作完后，IP指向下一个未处理符号。
sym：表示IP所指符号。
ADVANCE：是过程，让IP指向下一个符号。
ERROR：是出错处理子程序。
(4) 预测分析方法
（1）预测分析表M 如下矩阵形式：矩阵M
?行标题用文法的非终结符表示。
?列标题用文法的终结符号和#表示。
?矩阵元素M[A, a]的内容是产生式A→α（或→α）表明当对A进行推导，面临输入符号a时，应采用候选α进行推导。
出错处理标志（即表中空白项）表明A不该面临输入符号a。
（2）符号栈
用于存放文法符号，栈顶为推导过程中句型尚未匹配部分的开头符号。
分析开始时，栈底先放一个#，然后放进文法开始符号，即S#
（3）预测分析总控程序
总是按栈顶符号x和当前输入符号行事。
对于任何（x,a），总控程序每次都执行下述三种可能动作之一：
（a）若x=a=‘#’，则宣布分析成功。
（b）若x=a≠‘#’，则把x从栈顶逐出，指针指向下一输入符号。
（c）若x是一个非终结符，则查看分析表M。
①如果M[A, a]中存放关于X的一个产生式，那么，首先把X顶出栈，然后把产
生式右部符号串按反序一一推进栈。
②如果M[A, a]中存放“出错标志”，则调用出错处理程序ERROR。
(1)自底向上优先分析法
自底向上分析方法，也称移进—归约分析法，粗略地说它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，（该句柄对应某产生式的右部），就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一步归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。可以看出，移进一归约过程是自顶向下最右推导的逆过程。最右推导称为规范推导。自左向右的归约过程称为规范归约。
如何知道何时在栈顶符号串中已形成某句型的句柄，这是自底向上分析的关键。在自底向上分析方法中，本章主要介绍常用的算符优先分析法和LR类分析法。
(2) 算符优先分析法
算符文法的定义：设有一文法G，如果G中没有形如A→…BC…的产生式，其中B和C为非终结符，则称G为算符文法（Operater Grammar）也称OG文法。（文法中没有两个非终结符相临的情况，则称是算符文法）
性质1 在算符文法中任何句型都不包含两个相邻的非终结符。
性质2 如果Ab或bA出现在算符文法的句型γ中；其中A∈V N，b∈V T，则γ中任何含b的短语必含有A。
算符优先文法的定义：设有一不含ε产生式的算符文法G，如果对任意两个终结符对a, b之间至多只有<、>和=三种关系的一种成立，则称G是一个算符优先文法。（Operator Precedence Grammar）即OPG文法。
(3) 算符优先关系表的构造
FIRSTVT（B）={b|B?b…或B?Cb…}
构造规则：
（1）若B→b…或B→Qb…，则b∈FIRSTVT(B)
（2）若B→Q…，则FIRSTVT(Q)?FIRSTVT（B）
LASTVT（B）={a|B?…a或B?…aC}
构造规则
（1）若B→…a或B→…aQ，则a∈LASTVT(B)
（2）若B→…Q，则LASTVT(Q)?LASTVT（B）
最左素短语：设有文法G[S]，其句型的素短语是一个短语，它至少包含一个终结符，并且除自身外不包含其它素短语，最左边的素短语称最左素短语。
(4) 归约步骤
初始时栈底存#，输入指针指向输入串的首字符。
控制程序根据栈顶终结符a（若栈顶是非终结符，则次栈顶的终结符称为栈顶终结符）和输入指针所指的输入符b，查优先关系表M，可能有四种情况：
（1）M[a, b]为<或=时移进b，即将b进栈，输入指针指向下一输入符。
（2）M[a, b]为>时，则将栈顶含a的素短语按对应的产生式归约，素短语与产生式右部需终
结符对应相同，非终结符位置应相同名称可不同。顶出栈中素短语，非终结符入栈。（3）M[a, b]为空白，语法错，调用相应出错处理程序。
（4）a=b=# 时分析结束。
(5) 优先函数
用关系法构造。构造步骤：
（a）对每一终结符a（包括#），用fa，ga为结点名。
（b）若ai>aj或ai=aj，则从fai到gaj画一条箭弧。若ai （c）给每个结点赋一个数，此数等于从该结点出发所能到达的结点（包括该结点自身在内）的个数。赋给结点f (ai)的数，就是函数f(ai)的值，赋给g (aj)的数，就是函数g(aj)的值。（d）对构造出的优先函数，按优先关系矩阵检查一遍是否满足优先关系的条件，若不满足时，则在关系图中有回路说明不存在优先函数。 优先函数的优缺点 优点：（1）节省存储空间； （2）执行整数比较运算比查优先关系表方便。 缺点：（1）有些优先关系表不存在优先函数。 （2）原先不存在优先关系的两个终结符变成可比较其函数值大小了，需加以克服。 (1) LR分析法 LR分析法是一类对上下文无关文法进行“自左向右的扫描和最左归约（即最右推导的逆过程）”分析的方法，是一种规范归约过程。LR(k)分析方法是1965年Knuth提出的，其中k表示向右查看输入符号串的个数。 （1）总控程序所有LR分析器的总控程序都是相同的，共有四种动作：移进、归约、接受、出错。 （2）分析表常见的有四种: LR（0）分析表适应文法范围小，是其它类型分析表构造的基础。 SLR（1）分析表是LR（0）分析表的改进，适应文法范围强于LR（0）。 LR（1）分析表分析能力强（指适应范围，查错速度），但状态太多。 LALR（1）分析表是LR（1）分析表的改进，分析能力强于SLR而稍弱于LR（1），但状态少于LR（1） （3）分析栈包括文法符号栈和相应的状态栈。 (2) LR(0)分析 可归前缀 规范句型中，包括句柄及句柄以左的部分，称为可归前缀。 有些可归前缀的前缀是相同的，不仅仅属于某一个规范句型。我们把可归前缀的前缀称为活前缀。 进行语法分析时，只要将待分析符号串的当前部分符号与αi[Pi]进行比较，便可知是否归约，以及应按哪条产生式归约。 为了得到所有可归前缀，可以对文法G构造一个有穷自动机，该有穷自动机能识别文法G的所有可归前缀。 构造识别可归前缀的有穷自动机 项目：文法的识别可归前缀的有穷自动机以文法的“项目”作为它的状态，所谓文法的项目，是在文法的每一条规则的右部添加一个圆点而形成。之所以这样构造项目，是受可归前缀的启发。圆点表示在识别可归前缀的过程中，对句柄（即某产生的右部）已识别过的部分。项目分四类 （a）圆点在最右端的项目，形如A→α·，表示已从输入串看到能由一条产生式右部推导出的符号串，即已达一可归前缀末端，已识别出句柄可以归约，这种项目称为归约项目，相应状态称为归约状态。即为可归前缀识别态 （b）对形如S'→S·的项目，其中S是文法开始符号，称为接受项目，相应状态称为接受状态，表明可由S推导的输入串已全部识别完，整个分析过程成功结束。 （c）对于形如A→α·aβ的项目，表明尚未识别一可归前缀，需将a移进符号栈，故称移进项目，相应状态为移进状态。 （d）对于形如A→α·Bβ的项目，表明期待分析由B所推出的串归约到B，从而识别B。故称为待约项目，相应状态为待约状态。 方法一：首先构造识别可归前缀的NFA，然后将NFA确定化，得DFA（部分）。 方法二：根据文法直接构造识别文法可归前缀的DFA。 ①拓广文法 对文法G加一条产生式S'→S 得G'，目的是使开始状态唯一，接受状态易于识别。 ②定义项目集I的闭包CLOSURE(I) a) I的项目均属于CLOSURE( I ); b) 若A→α?Bβ属于CLOSURE（I）,则每一形如B→?γ的项目也属于CLOSURE（I）; c) 重复b），直到CLOSURE（I）不再增大为止。 ③定义状态转换函数GO（I，X） 其中I是项目集，X是文法符号。GO（I，X）=CLOSURE( J )，其中J={任何形如A→αx?β的项目|A→α?xβ∈I}，以上可以避免出现ε弧，避免从同状态射出相同标记弧。 ④构造DFA a) DFA的初态集：CLOSURE({S'→?S}) b) 对初态集或其它所构造的项目集应用转换函数，GO (I, X) =CLOSURE（J）求出新的项目集。 c) 重复b)直到不出现新的项目集为止。DFA中所有状态组成的集合也称为该文法的LR（0）项目集规范族。 构造算法 a) 若项目A→α·aβ属于I k且转换函数GO（I k, a）=I j，当a为终结符时则置ACTION[k, a]为S j， （即当状态k遇a时转向状态j）。其动作含意为将终结符a移进符号栈，状态j进入状态栈， b) 若项目A→α·属于I k，则对a为任何终结符或‘#’号，置ACTION[k,a]为“r j”，j为在文法G'中某产生式A→α的序号。r j动作的含义是把当前文法符号栈顶的符号串α归约为A，且将栈指针从栈顶向下移动|α|的长度（或符号栈中弹出|α|个符号），非终结符A变为当前面临的符号。 c) 若GO（Ik, A）= Ij，则置GOTO[k, A]为“j”，其中A为非终结符，表示当前状态为“k”时，遇文法符号A时状态应转向j，因此A 移入文法符号栈，j 移入状态栈。 d) 若项目S'→S·属于Ik，则置ACTION[k, #]为“acc”，表示接受。 e) 凡不能用上述方法填入的分析表的元素，均应填上“报错标志”。为了表的清晰我们令在表中用空白表示错误标志。 LR（0）分析器的工作过程 （1）若ACTION [q i , a k ] = S j ，则将状态S j , a k 进栈，三元式变化过程: （2）若ACTION [ q i, a k ] = r j ，且第j 条产生式为A → β，|β| = r ，则按第j 条产生式归约。 （3）若ACTION[qi, ak]=acc 则结束分析，输入串被接受。 （4）若ACTION[qi, ak]=ERROR 或表中为空白，表示出错，进行相应出错处理。 (2) 非LR（0）文法的判断 判断方法一： 考察识别文法可归前缀的DFA，若某个状态（即项目集）中既含移进项目又含归约项目；或含不只一个归约项目，则会发生分析动作的冲突，可知该文法不是LR（0）的。 判断方法二： 若文法的LR（0）分析表中含多重定义，即表中某项动作不唯一，则该文法不是LR（0）文法。 (3) SLR（1）分析 用SLR（1）方法，对于当前状态中的归约项目，如A→α·，必须当前输入符号属于FOLLOW （A）时，才可做归约。有望解决LR（0）方法中的分析动作冲突问题。 SLR（1）分析表的构造 将LR（0）分析表构造算法中的b）改为： 若项目A→α·属于I k，则对a为任何终结符或‘#’号，且满足a∈FOLLOW(A)时，置ACTION[k, a]为“rj”，j为在文法G'中某产生式A→α的序号。 (4) 非SLR文法的判断 判断方法一： 对识别文法可归前缀DFA中任一状态下，FOLLOW(B1)…FOLLOW(B n)，两两不相交，否则，文法不是SLR的。只求需要归约Follow集 判断方法二： 若构造的SLR分析表含多重定义，则文法不是SLR的。 (5) LR（1）分析 对某些文法，用SLR（1）方法仍解决不了分析动作的冲突问题，可采取以下措施：若某归约项目A→α·∈I ，当I 为当前状态，面临当前输入符号a 时，只有a 是在I 状态下A 的后继符号时才用 A →α产生式归约，而不是对A的所有后继符号都可以归约。从而有望解决冲突。 A →α·，Follow(A) 是向前搜索符，构造项目集是其他与LR(0)相似，只是加上向前搜索符 将LR（0）分析表构造算法中的b) 中：若项目A →α ·属于I k ，则对 a 为任何终结符或‘#’号，置ACTION[k, a]为r j改为：若项目[A→α·, a] 属于I k ，则置ACTION [k,a] = r j LR（k）分析表 如果用LR（1）方法仍不能解决冲突，则可再向前多搜索几个符号，这时的项目为[A →α·β , a1 a2 … a k ] 称为LR（k）项目，相应的分析表构造方法类似LR（1）分析表的构造。 (6) LALR（1）分析 在LR（1）项目中，有很多状态中的项目除了向前搜索符号不同外，产生式部分是完全相同的，称这样的状态是同心的，为了克服LR（1）分析中状态太多的问题，可以将这些同心集合并。如果合并后得到的新状态没有冲突出现。则按新状态构造分析表。这就是LALR （1）分析法的基本思想。 LR(0) LR(1) SLR(1) 这三种文法很重要。 (1) 语义处理 语义分析：主要检查各种语法成分的语义是否符合语义规定，例如参与运算的表达式类型是否一致，赋值语句的赋值左部和右部类型的一致性，数组元素的维数与数组说明维数的一致性，每一维的下标是否越界，在相同作用域中名字是否被重复说明等。 目前尚无公认的、统一的形式化语义描述工具。但研究者已提出一些针对某些特殊语言的语义描述工具，例如：公理语义、指称语义、代数语义、操作语义等。 中间代码生成：对说明语句，通常将其中定义的名字及其属性信息，在符号表中进行登记；对于执行语句，生成语义上等价的中间语言代码。 属性文法：一个属性文法，包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上。 E→T1+T2{T1·t=int AND T'2·t=int} E→T1 or T2{T1·t=bool AND T2·t=bool} T→num {T·t=int}T→true {T·t:=bool} T→false {T·t:=bool} 语法制导翻译：在语法分析过程中，随着分析的步步进展，根据每个产生式对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。 语法制导翻译的具体实现途径：假定有一个LR语法分析器，现在把它的分析栈扩充，使得每个文法符号都跟有语义值，即把栈的结构看成下图所示那样。同时把LR分析器能力扩大，使它不仅执行语法分析任务，且能在用某个产生式进行归约的同时调用相应的语义子程序，完成有关的语义动作。每步工作后的语义值保存在扩充的分析栈里“语义值”栏中。 (2) 中间代码形式 常见的有逆波兰记号、三元式、四元式和树等。 1.逆波兰表示（也称后缀表示）逆波兰表示的特点： （1）运算符紧跟在运算对象的后面出现，没有括号。 （2）运算对象出现的顺序（从左到右）和原有顺序（中缀）相同。 （3）运算符是按实际运算顺序（从左到右）出现的。 逆波兰表示的最大优点是易于计算机处理表达式，使用栈进行运算很方便。可将逆波兰表示形式扩充，用来描述程序设计语言中的其它语法成分。 2.三元式表示 三元式的形式为：（op，ARG1，ARG2）其中op为运算符，ARG1为运算对象1，ARG2为运算对象2。 三元式出现的先后顺序与表达式的运算顺序一致。 三元式的缺点是不便于优化，动一式，其它式子被牵动，使用间接三元式，可以克服这个缺点。 间接三元式：使用二个表（1）三元式：存放不相同的三元式（2）运算顺序表（也叫间接码表）：按运算的先后顺序列出有关三元式在三元式表中的位置。 3.树形表示三元式表示也可用相应的树形表示。 简单变量或常量的树就是该变量或常量本身，如果表示表达式e1和e2的树为T1和T2 4.四元式：表示形式（op; ARG1, ARG2, RESULT）四元式表示较利于代码优化。 (3) 简单赋值语句翻译 （1）https://www.doczj.com/doc/b32261055.html, 语义变量，表示变量即标识符字符串。 （2）E. place 语义变量，表示存放E值的变量名在符号表中的入口位置或一整数码（临时 变量）。 （3）Lookup(id. name)语义过程(函数），对https://www.doczj.com/doc/b32261055.html,查符号表，若找到，则返回其在符号表中的位置，否则返回nil，体现先定义后使用的原则。 （4）GEN(op, ARG1, ARG2, RESULT)语义过程(函数）,生成四元式，填进四元式表。 （5）newtemp 语义过程，生成一临时变量T i。 (4) 布尔表达式的翻译 布尔表达式的翻译是指转换成最终能计算出该表达式的结果为真或假（1 或0）的四元式序列的过程。 Eg. a or b and not c 的四元式序列为： (1) t1:=not c (2) t2 :=b and t1 (3) t3 :=a or t2 (1) 控制语句的代码结构真出口E.true 假出口E.false (2) “回填”技术 控制语句中布尔表达式翻译成四元式序列时，有的转移地址不能在产生这些四元式的同时得知，需要在适当的时候回填这个地址。 (3) “拉链”技术 为了记录需要回填地址的四元式，常采用“拉链”技术。把需回填E.true 的四元式拉成一条链，称为“真”链；把需回填E.false的四元式拉成一条链，称为“假”链。 (5) 控制结构的翻译 for 循环语句的文法及其相应的语义动作 第八章错误的诊查与校正 对于源程序，由于种种原因，往往含有或多或少的错误，因此，一个好的编译程序应具有较强的查错和改错能力。 1、语法错误 指程序结构、单词和拼写不符合语法要求的规则。都是在词法分析阶段和语法分析阶段发现的。 如关键字拼写错误;某些语法成分未按语言的语法规则编写等。 2、语义错误 指程序不符合语义规则或超越具体计算机系统的限制。包括以下几种类型: ?说明错：对变量未说明就引用，某些量被重复说明，或不符合有关作用域的规定。 ?类型不相容错：某些运算的操作数的类型不相容，形一实参在种属或类型上不相对应等。 ?对某些值超越限制错：如对各类变量数值范围的限制；对数组维数、形参个数、循环嵌套数的限制。 另外，我们将在编译阶段就能发现的错误，称为静态错;到目标代码运行时才能发现的错误称为动态错，如溢出，动态数组的下标越界。 出错处理主要有两种处理方法： 1、校正法 试图对错误进行校正。 当编译程序发现错误时，给用户指出错误的性质、错误的位置，以及如何校正等方面的信息。 2、局部化法 当发现错误时，跳过错误所在的语法单位，继续往下分析。以便把错误限制在尽可能小的局部范围内。只需给用户报告出错误位置，出错性质即可。 一些语义错误的处理： 1、遏止株连错误 株连错误：由于第一次错误，而派生出后面若干额外错误。只要消除第一个错误，后面若干错误也就自动消失。 遏止方法：第一次发现是标识符引起错误时，输出出错信息，并用一个“正确”的标识符代替它，并把此新的标识符填进符号表，尽可能正确地填入各种属性且加上标记。 以后发现一个引起错误的标识符时，查看符号表中相应登记项，如果它已被标记，则不再打印出错信息。 2、遏止重复错误 重复错误：一种错误，发现n次，报n次错。 如：x未被说明，程序中出现n次，则n次报x未被说明。 遏止方法： 设出错标识符为x 1、若x未经说明，则将x填入符号表，并填入鉴别出的属性。 2、若x已被说明，则查错误类表。 如果表中没有同类错误，则输出出错信息，并填进错误类表中。 如果表中有同类错误，则不输出错误信息。 第九章符号表 符号表的作用 编译程序在词法分析到代码生成的各阶段，不断地积累和更新表中的信息，并按各自的需要从表中获取信息。符号表的功能归结为以下三个方面： 1、收集符号属性 在分析语言程序中标识符说明部分时，编译程序根据说明信息收集有关标识符的属性，并在符号表中建立符号的相应属性信息。如PL/0语言编译的符号表。 2、上下文语义的合法性检查的依据 通过符号中属性记录可检查标识符属性在上下文中的一致性和合法性。如：是否未说明就引用，说明与引用，其属性、类型是否一致。是否有重复定义。运算量间运算类型是否一致等。 3、作为目标代码生成阶段地址分配的依据 源程序中的变量在目标代码生成时需要确立其在存储分配的位置（主要是相对位置）。而地址分配主要根据变量的类型，在源程序中被说明的位置。 如在第几层分程序，是静态区还是动态区等，分配其在相应数据区中的相对地址，而这些地址分配的依据都是作为变量的语义信息被收集在该变量的符号表属性中。 符号表的内容： 1、符号名 源程序中一个标识符可以是一个变量名、常量名、函数名或过程名，登记在符号表中，通常把一个标识符在符号表中的位置（通常是一个整数）称之为该标识符的内部代码，从而取代该标识符。 2、符号的类型信息 符号的种类：如常量、变量、数组、标号、函数或过程等，符号的类型，如整型、实型、字符型、布尔型等。 数组：应包括维数、上下界、计算下标地址时涉及的常量等，放在数组信息向量表即内情向量表中，用于确定存储分配时所占空间，确定数组元素的位置。 过程或函数：应包括参数的个数、类型、排列次序等用来作调用过程的匹配处理和语义检查。 记录结构：应包括其成员的类型、个数、排列次序等信息。以便确定结构型变量应分配的空间及结构成员的位置。 3、符号变量的存储分配信息 存储类别：如全局量还是局部量，静态存储变量，还是动态存储变量等，作为存储分配的依据。 地址表示：简单变量或常量，一般是该量在数据区所占单元的绝对或相对地址。数组，是该数组在数据区中的首地址，过程或函数，是该过程或函数的分程序入口地址。 4、层次信息 对于分程序嵌套或过程嵌套结构型程序设计语言，还应包括每个标识符所属分程序（过程）的层次。 符号表的组织： 符号表的组织直接关系到语义功能的实现和语义处理的时空效率，关于符号表的组织可从符号表的总体组织和表项属性信息组织来分别讨论。 1、符号表的总体组织 第一种：按照属性完全相同的那些符号组织在一起。 第二种：把语言中的所有符号都组织在一张符号表中。 优点：总体管理集中单一。 缺点：若各表项相等，则增加了无用的属性空间，从而增加了空间开销。 若各表项不等长，则增加了对符号表管理的复杂度。 第三种：折中方式 根据符号属性相似程度分类组织成若干张表，使管理复杂性及时空效率方面都取得折中的效果。 2、符号表项的排列： 在编译程序的整个工作中，符号表被频繁地用来建立表项，找查表项，填充和引用表项的属性，因此表项的排列组织对该系统运行的效率起着十分重要的作用。 传统上采用三种构造方法: （1）线性组织（按其出现顺序） 表项按它的符号被扫描到的先后顺序建立。 线性组织管理简单但运行效率低。适用于事先能确定符号个数且符号个数不大时。（2）排序组织及二分法（abcd排列） 表项按其符号的字符代码串的值的大小排列。 关于表项的建立和查找通常采用二分法。 排序表的运行效率比线性表高，算法复杂性也高于线性表。 （3）散列组织 表项位置是由对表项的符号值（即字符代码串）进行某种函数操作（通常称为“杂凑”）所得到的函数值来确定的，这种函数通常被称为杂凑函数。 符号表的散列组织具有较高的运行效率，因而绝大多数编译程序中的符号表采用散列组 织。 3、关键字域的组织： 在编译程序中，符号表的关键字域就是符号本身。也称名字域。 （1）等长关键字段 可设置关键字段为标识符的最大长度。由于程序中的标识符不会总是使用很长的拼写字，关键字段的这种组织方式在实际使用中会有很多空间是冗余的。 （2）关键字池的索引结构 符号表中关键字段是指针，指向该关键字在池中的位置， 4、其它域的组织 符号表属性域的组织，根据属性性质大致分成两类： 一类是符号表中符号的该属性值具有相同的类型且是等长的，则该属性域的类型结构就可用这个长度及类型来定义。 另一类属性值可能具有相同类型但长度不同，则该属性域的定义不能用简单的数据类型来定义。 （1）等长属性值域的组织 用于表中符号的该属性值具有相同的类型且是等长的。 ①位向量表示：如表示符号的数据类型可以用3个bit位表示 ②数值表示：表示符号的数据类型也可以用一个整型量来表示 ③用指针链表示：有一些是表示符号之间关系的属性，可用指针或指针链来构造这些属性域。 （2）不等长属性值域组织 符号的某些属性值是不等长的 一个数组的内情向量属性可分成两种值，数组维数的个数及每一个维的元素个数。下标表示了所在维的元素个数。 数组符号在符号表项中可以设立一个指向内情向量空间的指针，而在内情向量空间记录关于该数组的维数个数和每一维的元素个数，下图表示了array1及array2两个数组在符号表中内情向量的组织。 5、下推链表组织 在程序语言的结构中，分程序的分层结构中允许定义同名标识符，则在每进入一个内层结构并发生重名标识符定义时，将此重名标识符链到链首，即原同名链下推。 符号表的管理： 包括表的初始化、符号的登录、符号的查找和有关分程度结构符号表层次管理。 1、符号表的初始化 （1）符号表的表长是渐增变化的情况 （2）符号表的表长是确定的情况 2、符号的登录 对于散列表，新符号的登录是通过杂凑算法决定登录表项的位置。 关于属性，多数可与符号名一起填入，有些根据扫描时所得信息，逐步用前述属性域组织方式（如等长、不等长、属性链）进行填入。 3、符号的查找 根据表的组织方法，可用顺序查找、折半查找或杂凑查找法查找。 4、符号表中分程序结构层次管理 名字作用范围：分程序中说明的名字只局部于此分程序，内层可以引用外层说明的名字（此名字必须在内层未被说明）。 通常对于具有分程序结构的语言用两种方式组织它们的符号表： （1）对每个分程序建立一个独立的符号表 每当编译程序扫描到一个分程序结构时，为该分程序填写符号表。 而当扫描到该分程序结束时，则释放为该分程序所填的符号表内容。即动态建立和动态消亡。 符号的登录是中为该分程序所建立的符号表中进行，而符号的查找是首先在该分程序符号表中进行，若没有查找到，再根据分程序的层次结构，逐层向外地依次查找各层符号表。 特别要注意的是对于并列的分程序，其相应的符号表不会同时存在。 （2）单表结构 只用一张符号表 符号表中可设立一个属性域用来登录符号所在分程序层次，符号表相当于栈的形式。 每当编译程序扫描到一个分程序结构开始时，就在符号表栈顶登录该分程序中说明的符号及其属性，包括分程序层号。 而当编译程序扫描到一个分程序的结束时，就从栈顶退出为该分程序登录的符号及属性。 第10章目标程序运行时的存储组织 运行时的存储区常常划分为：目标区、静态数据区、栈区和堆区。 在大部分现有编译程序中采用的数据空间使用和管理方法主要有两种，即静态存储分配和动态存储分配。 而动态存储分配中又分：栈式动态存储分配、堆式动态存储分配。 静态存储分配： 在编译时就安排好目标程序运行时的全部数据空间，并能确定每个数据项目的存储位置，存储空间的这种分配方法称为静态存储分配。 对语言的要求： （1）不含可变体积数据，如动态数组。 （2）不含递归过程。 （3）数据名的性质完全确定，即不能运行时才确定。 如FORTRAN语言，就可用静态存储分配。 动态存储分配： 在目标代码运行时，动态地为源程序中的数据对象分配存储空间，则称为动态存储分配。 对不能满足静态存储分配的语言，则需用动态存储分配。但并非所有分配工作都放在运行时刻做，在编译阶段就要设计好存储组织形式，并反映在生成的目标代码中。 有两种动态存储方式：栈式和堆式 栈式动态存储分配： 将整个程序的数据空间设计为一个栈(Stack)，每当调用一个过程时，它所需空间就分配在栈顶，每当过程工作结束时，就释放这部分空间。如PASCAL、ALGOL和C语言。 堆式动态存储分配： 所谓堆式动态存储分配，就是在存储空间里专门保留一片连续的存储块（称为堆Heap），在运行程序过程中，对于类似上述情况的语法成分，需要空间时，就由一个运行时刻存储管理程序从堆中分配一块区域给它，不再需要时，又可由此堆管理程序释放该区域，供以后重新分配使用。 栈式存储分配的实现 过程的活动记录（AR）：是一段连续的存储区，用以存放过程的一次执行所需要的信息。 简单的栈式存储分配的实现： 假设语言没有分程序结构，过程定义不允许嵌套，但允许过程的递归调用，如C语言。这样的语言可以直接采用栈式存储分配。 无嵌套定义的过程活动记录内容见下表（设该过程含可变数组） TOP指向栈顶。SP指向现行活动记录起点，老SP指向调用现行过程的过程活动记录的起点。 嵌套过程语言的栈式实现： 假设语言的过程定义允许嵌套，例如PASCAL语言。 由于过程定义是嵌套的，一个过程可以引用包围它的任一外层过程所定义的变量或数组，为了在活动记录中查找非局部量名字所对应的存储空间，必须设法跟踪每个外层过程的最新 一、简答题 1.什么是编译程序 答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。 将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。 2.请写出文法的形式定义 答：一个文法G抽象地表示为四元组 G=（Vn,Vt,P,S） –其中Vn表示非终结符号 –Vt表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ –S是开始符号， –P是产生式，形如：α→β(α∈V+且至少含有一个非终结符号，β∈V*) 3.语法分析阶段的功能是什么 答：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。确定整个输入串是否构成语法上正确的程序。 4.局部优化有哪些常用的技术 答：优化技术1—删除公共子表达式 优化技术2—复写传播 优化技术3—删除无用代码 优化技术4—对程序进行代数恒等变换（降低运算强度） 优化技术5—代码外提 优化技术6—强度削弱 优化技术7—删除归纳变量 优化技术简介——对程序进行代数恒等变换（代数简化） 优化技术简介——对程序进行代数恒等变换（合并已知量） 5．编译过程分哪几个阶段 答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。每个阶段把源程序从一种表示变换成另一种表示。 6. 什么是文法 答：文法是描述语言的语法结构的形式规则。是一种工具，它可用于严格定义句子的结构； 用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。 7. 语义分析阶段的功能是什么 答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)； 并对静态语义进行审查。 8.代码优化须遵循哪些原则 答：等价原则：不改变运行结果 有效原则：优化后时间更短，占用空间更少 合算原则：应用较低的代价取得较好的优化效果 9.词法分析阶段的功能是什么 答： 语义分析实验报告 一、实验目的： 通过上机实习，加深对语法制导翻译原理的理解，掌握将语法分析所识别的语法成分变换为中间代码的语义翻译方法。 二、实验要求： 采用递归下降语法制导翻译法，对算术表达式、赋值语句进行语义分析并生成四元式序列。 三、算法思想： 1、设置语义过程。 （1）emit(char *result,char *ag1,char *op,char *ag2) 该函数的功能是生成一个三地址语句送到四元式表中。 四元式表的结构如下： struct { char result[8]; char ag1[8]; char op[8]; char ag2[8]; }quad[20]; (2) char *newtemp() 该函数回送一个新的临时变量名，临时变量名产生的顺序为T1，T2，… char *newtemp(void) { char *p; char m[8]; p=(char *)malloc(8); k++; itoa(k,m,10); strcpy(p+1,m); p[0]=’t’; return(p); } 2、函数lrparser 在原来语法分析的基础上插入相应的语义动作：将输入串翻译成四元式序列。在实验中我们只对表达式、赋值语句进行翻译。 四、源程序代码： #include 编译原理实验报告语法分析程序的设计 文档编制序号：[KK8UY-LL9IO69-TTO6M3-MTOL89-FTT688] 实验5语法分析程序的设计（2） 一、实验目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中算法优先分析方法。 二、实验内容 设计一个文法的算法优先分析程序，判断特定表达式的正确性。 三、实验要求 1、给出文法如下： G[E] E->T|E+T; T->F|T*F; F->i|(E); +*()i + * ( ) i 21）直接存放，2）为优先关系建立优先函数，这里由学生自己选择一种方式； 1、给出算符优先分析算法如下： k:=1; S[k]:=‘#’; REPEAT 把下一个输入符号读进a中； IF S[k]∈V T THEN j:=k ELSE j:=k-1; WHILE S[j] a DO BEGIN REPEAT Q:=S[j]; IF S[j-1]∈V T THEN j:=j-1 ELSE j:=j-2 UNTIL S[j] Q 把S[j+1]…S[k]归约为某个N； k:=j+1; S[k]:=N; END OF WHILE; IF S[j] a OR S[j] a THEN BEGIN k:=k+1;S[k]:=a END ELSE ERROR UNTIL a=‘#’ 1、根据给出算法，利用适当的数据结构实现算符优先分析程序； 2、利用算符优先分析程序完成下列功能： 1）手工将测试的表达式写入文本文件，每个表达式写一行，用“；”表示结束； 2）读入文本文件中的表达式； 3）调用实验2中的词法分析程序搜索单词； 4）把单词送入算法优先分析程序，判断表达式是否正确（是否是给出文法的语言），若错误，应给出错误信息； 5）完成上述功能，有余力的同学可以对正确的表达式计算出结果。四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 编译原理课程设计心得体会范文（单片机）经过一个星期的编译原理课程设计，本人在刘贞老师的指导下，顺利完成该课程设计。通过该课程设计，收获颇多。 一、对实验原理有更深的理解 通过该课程设计，掌握了什么是编译程序，编译程序工作的基本过程及其各阶段的基本任务，熟悉了编译程序总流程框图，了解了编译程序的生成过程、构造工具及其相关的技术对课本上的知识有了更深的理解，课本上的知识师机械的，表面的。通过把该算法的内容，算法的执行顺序在计算机上实现，把原来以为很深奥的书本知识变的更为简单，对实验原理有更深的理解。 二、对该理论在实践中的应用有深刻的理解 通过把该算法的内容，算法的执行顺序在计算机上实现，知道和理解了该理论在计算机中是怎样执行的，对该理论在实践中的应用有深刻的理解。 三、激发了学习的积极性 通过该课程设计，全面系统的理解了编译原理程序构造的一般原理和基本实现方法。把死板的课本知识变得生动有趣，激发了学习的积极性。把学过的计算机编译原理的知识强化，能够把课堂上学的知识通过自己设计的程序表示出来，加深了对理论知识的理解。以前对与计算机操 作系统的认识是模糊的，概念上的，现在通过自己动手做实验， 从实践上认识了操作系统是如何处理命令的，如何协调计算机内部各个部件运行，对计算机编译原理的认识更加深刻。课程设计中程序比较复杂，在调试时应该仔细，在程序调试时，注意指针，将不必要的命令去除。 在这次课程设计中，我就是按照实验指导的思想来完成。加深了理解文件系统的内部功能及内部实现，培养实践动手能力和程序开发能力的目的。 四、理解了该知识点以及学科之间的融合渗透 本次课程设计程序部分是用c语言编写的，把《计算机操作系统》，《编译原理》，《算法分析与设计》《c语言》四门学科联系起来，把 各个学科之间的知识融合起来，把各门课程的知识联系起来，对计算机整体的认识更加深刻。使我加深了对《计算机操作系统》，《编译原理》，《算法分析与设计》《c语言》四门课程的认识。 嵌入式课程设计心得体会 本学期为期一周的嵌入式课程设计在不知不觉中结束了，虽说这次课程设计时间不是很长，但是感觉自己收获颇丰，不仅学习到了一些新知识，回顾了以前的一些快要遗忘的知识点，而且使自己的学习目标更加明确，学习方法更加完善，也体会到软件开发的趣味，更加清楚地认识到了自己在软件开发及学习上的一些不足之处。下面就来详细写一下我关于此次课程设计的心得体会： 此次课程设计的实训的是由上海杰普公司的楚老师带我们完成的。楚老师看上去比较年轻，给我们很有亲和力，技术上也很强，而 编译原理实验报告 姓名： 学号： 班级： 学院： 南昌大学信息工程学院计算机系 2014年6月 目录 实验一 (3) 实验二 (8) 实验三 (15) 实验1 词法分析程序的设计 学生姓名：学号：专业班级： 实验类型：□验证□综合□设计□创新实验日期：实验成绩： 一、实验目的 掌握计算机语言的词法分析程序的开发方法。 二、实验内容 编制一个能够分析三种整数、标识符、主要运算符和主要关键字的词法分析程序。 三、实验要求 1、根据以下的正规式，编制正规文法，画出状态图； 标识符<字母>(<字母>|<数字字符>)* 十进制整数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）* 运算符和界符+ - * / > < =<= >=( ) ；{ } 关键字main if then else while do int (可根据需要添加) 2、根据状态图，设计词法分析函数int scan( )，完成以下功能： 1）从文本文件中读入测试源代码，根据状态转换图，分析出一个单词， 2）以二元式形式输出单词<单词种类，单词属性> 其中单词种类用整数表示： 0：标识符 1：十进制整数 2：八进制整数 3：十六进制整数 运算符和界符，关键字采用一字一符，不编码 其中单词属性表示如下： 标识符，整数由于采用一类一符，属性用单词表示 运算符和界符，关键字采用一字一符，属性为空 3、编写测试程序，反复调用函数scan( )，输出单词种别和属性。 四、实验环境 PC微机 DOS操作系统或Windows 操作系统 Turbo C 程序集成环境或Visual C++ 程序集成环境 目录 1.绪论 概述 “编译原理”是一门研究设计和构造编译程序原理课程，是计算机各专业的一门重要的专业课。编译原理这门课程蕴含着计算机学科中解决问题的思路和解决问题的方法，对应用软件和系统软件的设计与开发有一定的启发和指导作用。“编译原理”是一门实践性很强的课程，要掌握这门课程中的思想，就必须要把所学到的知识应用于实践当中。而课程设计是将理论与实践相互联系的一种重要方式。 设计目的 课程设计是对学生的一种全面综合素质训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂很多，但也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构解决问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的能力。 设计题目及要求 基于这个学期所学习的内容以及自己所掌握到的知识，本次我所要设计的题目是赋值语句的四元式生成。 要求： （1）设计语法制导生成赋值语句的四元式的算法； （2）编写代码并上机调试运行通过； （3）输入一赋值语句； （4）输出相应的表达式的四元式； 2.背景知识 语法制导翻译方法 语法制导翻译的方法就是为每个产生式配上一个翻译子程序（称语义动作或语义子程序），并在语法分析的同时执行这些子程序。语义动作是为产生式赋予具体意义的手段，它一方面指出了一个产生式所产生的符号串的意义，另一方面又按照这种意义规定了生成某种中间代码应做哪些基本动作。在语法分析的过程中，当一个产生式获得匹配（对于自顶向下分析）或用于规约（对于自底向上分析）时，此产生式相应的语义子程序就进入工作，完成既定的翻译任务。语法制导翻译分为自底向上语法制导翻译和自顶向下语法制导翻译。 属性文法 属性文法是编译技术中用来说明程序语言语义的工具，也是当前实际应用中比较流行的一种语义描述方法。属性是指与文法符号的类型和值等有关的一些信息，在编译中用属性描述处理对象的特征。属性文法是一种 课程实验报告课程名称：《编译原理》 专业班级：信息安全1302 学号： 姓名： 指导教师： 报告日期：2015年11月6日 计算机科学与技术学院 目录 目录 (2) 1 实验一词法分析 (3) 1.1实验目的 (3) 1.2实验要求 (3) 1.3算法思想 (4) 1.4实验程序设计说明 (5) 1.5词法分析实现 (6) 1.6词法实验结果及结果分析 (11) 2 实验二语法分析 (12) 2.1 实验目的 (12) 2.2 实验要求 (12) 2.3 算法思想 (12) 2.4 实验程序设计说明 (14) 2.5 语法分析实现 (14) 4 实验中遇到的问题及解决 (22) 参考资料 (23) 1 实验一词法分析 1.1 实验目的 设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 1.2 实验要求 1、待分析的简单的词法 （1）关键字： main int char if else for while 所有的关键字都是小写。 （2）运算符和界符 ：= + -* / < <= <> > >= = == != ; ( ) [ ] { } #（3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 2、各种单词符号对应的种别码： 表1 各种单词符号对应的种别码 3、词法分析程序的功能： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 例如：对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列： (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 1.3 算法思想 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 1、主程序示意图： 主程序示意图如图1所示。其中初始包括以下两个方面： ⑴关键字表的初值。 关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下： Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,}; 开始 置初值 调用扫描子程序 输出单词二元组 否 输入串结束? 是 结束 图1 主程序示意图 编译原理实验报告 学院: 计算机与通信工程学院专业: 计算机科学与技术 班级: 学号: 姓名: 实验成绩： 词法分析 一、实验目的 设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 二、实验要求 2.1 待分析的简单的词法 （1）关键字： begin if then while do end 所有的关键字都是小写。 （2）运算符和界符 ：= + - * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 2.2 各种单词符号对应的种别码： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 例如：对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列： (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 3.1 主程序示意图： 3.2词法分析程序流程图： 四、词法分析程序的C++语言程序源代码： #include"stdio.h" #include"stdlib.h" #include"string.h" #define _KEY_WORD_END "waiting for your expanding" typedef struct 开始 变量初始化 是否文件结束？ 返回 拼数 Syn=11 返回 拼字符串 是否是关键字？ Syn 为对应关键字的单词种别码 Syn=10 给不同的符号相同的 Syn 值 报错 是 否 数字 字母 是 否 运算符, 界符等 其他 编译原理学习心得 编译原理学习心得1 编译程序在计算机科学与技术的发展历史中发挥了巨大作用，是计算机系统的核心支撑软件。而“编译原理”这门课程一直以来是国内外大学计算机相关专业的重要课程。因为它的知识结构贯穿程序设计语言、系统环境以及体系结构，能以相对的视角体现从软件到硬件以及软硬件协同的整机概念。其理论基础又涉及形式语言与自动机、数据结构与算法等计算机学科的许多重要方面，为联系计算机科学理论和计算机系统的典范。 虽然编译原理这门课程在大多数的人里认为枯燥无味，学起来就像看天书一样。然而学习这门课程还是有一定的好处的。比如可以更加容易的理解在一个语言种哪些写法是等价的，哪些是有差异的，可以更加客观的比较不同语言的差异，并且学习新的语言的效率也会更加高，语言转换也会更加游刃有余。 不学“编译原理”这门课程的话，自己的编程思想会很浅显。而且编程也只仅仅停留在编程上，无法深入理解其中的原理。 学习编译原理的话，从文法、正规式、NFA与DFA的定义，下手，要用心动脑去体会 编译原理学习心得2 从联系最紧密的操作系统来说吧，你写多线程/多进程的程序就得和操作系统的知识打交道。写多线程得加锁吧，临界区、死锁的四个条件之类的标准的操作系统的内容吧(不得不吐槽一下，某国内一线电商干了三年的程序猿，写多线程居然不知道加锁，也是醉了)。进程间通信的几种方式什么管道、socket、共享内存等，这也是操作系统的内容吧。文件系统，这也是经常要打交道的东西。还有内存什么的，你做Android 开发，这些里边有很多东西都在系统层面被封装好了，但是你要是不知道原理，一旦出了错根本无从调试，况且你该不会打算写一辈子写Android 就是填逻辑吧。 然后，是编译原理，普通的程序猿是接触不到编译器或者虚拟机的开发的。但是这并不意味着编译原理就用不到。说个最常见的读取配置文件，只要你的配置文件有自定义的语法，你就要用编译原理的东西。还有类似于自动生成代码啦、正则表达式啦这些都算是编译原理的内容。你既然是写Java 的不了解虚拟机怎么可以，最基本的字节码总是需要能看懂的吧，分析一些疑难杂症的时候字节码还是很有用的。 最后，是计算机原理，如果只是做应用开发的话计算机原理其实不必要掌握的多深入，但是一些基本的概念还是要清楚的。比如寄存器、缓存、中断什么的，关键的时候可以帮助你调试。在一些对性能要求非常高的场合，也是很有作用的。此外，学了 编译原理实验报告 题目构造识别字符串的自动机学院 专业 班级 学号 学生姓名 指导教师 西安思源学院教务处制 二〇一年 实验二构造识别符号串的自动机 一、实验目的 1 掌握形式语言与自动机的概念 2 了解正规集及有穷自动机的关系 3 能构造识别相应符号串的自动机 4 能构造词法分析程序所识别的各类单词的自动机 二、实验环境 Microsoft Visual C++ 6.0 三、实验内容 1 用高级语言编写程序：该程序能接受C++所有的标识符。 2 用高级语言编写程序：该程序能接受C++所有的常数(整数和定点小数)。 3 用高级语言编写程序：该程序能接受C++的所有保留字。 4 用高级语言编写程序：该程序能接受C++的所有界符、运算符。 四、设计说明 void main() { void find_word(); void show_all(); void Input(); Input(); cout<<"运行结果如下"< 编译原理程序设计报告 一个简单文法的编译器的设计与实现专业班级：计算机1406班 组长姓名：宋世波 组长学号： 20143753 指导教师：肖桐 2016年12月 设计分工 组长学号及姓名：宋世波20143753 分工：文法及数据结构设计 词法分析 语法分析（LL1） 基于DAG的中间代码优化 部分目标代码生成 组员1学号及姓名：黄润华20143740 分工：中间代码生成(LR0) 部分目标代码生成 组员2学号及姓名：孙何奇20143754 分工：符号表组织 部分目标代码生成 摘要 编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译是从源代码（通常为高阶语言）到能直接被计算机或虚拟机执行的目标代码（通常为低阶语言或机器语言）的翻译过程。 一．编译器的概述 1.编译器的概念 编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译器将原始程序作为输入，翻译产生使用目标语言的等价程序。源代码一般为高阶语言如Pascal、C++、Java 等，而目标语言则是汇编语言或目标机器的目标代码，有时也称作机器代码。 2．编译器的种类 编译器可以生成用来在与编译器本身所在的计算机和操作系统（平台）相同的环境下运行的目标代码，这种编译器又叫做“本地”编译器。另外，编译器也可以生成用来在其它平台上运行的目标代码，这种编译器又叫做交叉编译器。交叉编译器在生成新的硬件平台时非常有用。“源码到源码编译器”是指用一种高阶语言作为输入，输出也是高阶语言的编译器。例如: 自动并行化编译器经常采用一种高阶语言作为输入，转换其中的代码，并用并行代码注释对它进行注释（如OpenMP）或者用语 词法分析器实验报告 一、实验目的 选择一种编程语言实现简单的词法分析程序，设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 二、实验要求 待分析的简单的词法 （1）关键字： begin if then while do end 所有的关键字都是小写。 （2）运算符和界符 ： = + - * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 各种单词符号对应的种别码： 表各种单词符号对应的种别码 词法分析程序的功能： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 例如：对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列： (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根 据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 主程序示意图： 主程序示意图如图3-1所示。其中初始包括以下两个方面： ⑴关键字表的初值。 关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下： Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,}; 图3-1 （2）程序中需要用到的主要变量为syn,token和sum 扫描子程序的算法思想： 首先设置3个变量：①token用来存放构成单词符号的字符串；②sum用来整型单词；③syn 用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。 编译原理课程设计心得体会 假期期间我参加了由高平市教育局组织的构建高效课堂的培训，课题是三环节问题导学课课堂教学模式，张艳红老师论述了课堂是教学的主要阵地之一，是教师传授知识、学生学习知识的场所，教师和学生交往互动的空间，是教师引导学生发展、探究知识的主渠道，也是实现高效教学的主战场。要提高英语教学质量，就必须重视英语课堂教学，实现有效课堂教学。教师如何优化课堂教学，激发学生学习英语的兴趣，培养学生良好的英语学习习惯，通过这次理论学习和培训,使我对课堂有效教学有了更深刻的认知： 经过一个星期的编译原理课程设计，本人在老师的指导下，顺利完成该课程设计。通过该课程设计，收获颇多。 一、对实验原理有更深的理解 通过该课程设计，掌握了什么是编译程序，编译程序工作的基本过程及其各阶段的基本任务，熟悉了编译程序总流程框图，了解了编译程序的生成过程、构造工具及其相关的技术对课本上的知识有了更深的理解，课本上的知识师机械的，表面的。通过把该算法的内容，算法的执行顺序在计算机上实现，把原来以为很深奥的书本知识变的更为简单，对实验原理有更深的理解。 二、对该理论在实践中的应用有深刻的理解 要养成注释程序的好习惯，一个程序的完美与否不仅仅是实现功能，而应该让人一看就能明白你的思路，这样也为资料的保存和交流提供了方便;在设计课程过程中遇到问题是很正常德，但我们应该将每次遇到的问题记录下来，并分析清楚，以免下次再碰到同样的问题的课程设计结束了，但是从中学到的知识会让我受益终身。 通过把该算法的内容，算法的执行顺序在计算机上实现，知道和理解了该理论在计算机中是怎样执行的，对该理论在实践中的应用有深刻的理解。 自1987年就和程永革一起共事的歌舞话剧团演唱队队长骆汉泉含泪说道：“永革是我的好兄弟，这么多年，我们一起排练、演出，他的敬业精神一直留在我的脑海中，他的艺术才华和人品都给我们留下了深刻的印象。作为艺术人才，他尽职尽责，用自己的生命演绎出人生的追求。虽然他已经离我们而去，但是他难能可贵的责任担当和执着敬业的奉献精神一直感染着我们，我们也将在今后的工作中，以他为榜样，演好戏、做好人。” 月27日，全县《科学》教研会在城内小学召开。与其它学科教研会不同的是，《科学》教研会不是对新课标进行培训，而是科学课高效课堂的培训。原因是新拟定的《科学课程标准》还没有正式颁布。这次会议，全县专兼职老师一共100多人，观摩了三节高效课堂教学，聆听了龚主任所作的“构建自主探究式的高效课堂”专题讲座。 第一章 引论 ? 为什么要用编译器 ? 与编译器相关的程序 ? 翻译步骤 ? 编译器中的主要数据结构 1、语言处理器 1、简单的说，一个编译器就是一个程序，它可以阅读以某一种语言（源语言）编写的程序，并把该程序翻译成一个等价的、用另一种语言（目标语言）编写的程序。 2、编译器的重要任务之一就是报告它在翻译过程中发现的源程序中的错误。 3、使用编译器是为了提高编程的速度和准确度。 4、与编译器相关的程序：解释程序（interpreter ）、汇编程序（assembler ）、连接程序（linker ）、装入程序（loader ）、预处理器（preprocessor ）、编辑器（editor ）、调试程序（debugger ）、描述器（profiler ）、项目管理程序（project manager ）。 5、解释器是另一种常见的语言处理器。它并不通过翻译的方法生成目标程序。从用户的角度来看，解释器直接利用用户提供的输入执行源程序中指定的操作。 6、一个源程序可能被分割成多个模块，并存放于独立的文件中。把源程序聚合在 一起的任务有时会由一个被称为预处理器（preprocessor ）的程序独立完成。预处理器还负责把那些称为宏的缩写形式转换为源语言的语句。 7、连接器（linker ）能够解决外部内存地址的问题。 8、加载器（loader ）把所有的可执行目标文件放到内存中执行。 2、一个编译器的结构 Output Source Program Front end Back end Object 1、将编译器看成黑盒，则源程序映射为在语义上等价的目标程序，而这个映射由两部分组成：分析部分和综合部分。 2、分析部分把源程序分解成多个组成要素，并在这些要素之上加上语法结构。 3、综合部分根据中间表示和符号表中的信息来构造用户期待的目标程序。 4、编译器的第一个步骤：词法分析（lexical）或扫描（scanning）。词法分析器读入组成源程序的字符流，并且将它们组成有意义的词素（lexeme）的序列。词法分析器产生词法单元（token）。 5、分隔词素的空格会被词法分析器忽略掉。 6、编译器的第二个步骤：语法分析（syntax）或解析（parsing）。语法分析器使用由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示。 7、语义分析（static semantic analysis）：语义分析器使用语法树和符号表中的信息 来检查源程序是否和语言定义的语义一致。它同时也收集类型信息，并把这些信息存放在语法树或符号表中，以便在随后的中间代码生成过程中使用。语义分析的一个重要部分是类型检查（type checking）。编译器检查每个运算符是否具有匹配的运算分量。 8、总的说，编译器的翻译步骤是：扫描程序----语法分析程序----语义分析程序---- 源代码优化程序----代码生成器----目标代码优化程序。 3、编译器结构中的主要数据结构 1、记号（token） 2、语法树（syntax tree） 3、符号表（symbol table） 4、常数表（literal table） 5、中间代码（intermediate code） 6、临时文件（temporary file） 4、将编译器分成了只依赖于源语言（前端（ front end））的操作和只依赖于目 标语言（后端（ back end））的操作两部分。 第二章词法分析 ? 扫描处理 ? 正则表达式 ? 有穷自动机 ? 从正则表达式到D FA ? 利用L e x自动生成扫描程序 1、Tokens记号标记：identifiers、keywords、integers、floating-point、symbols、strings、comments 1、使用正则表达式去描述程序语言tokens 2、一个正则表达式是归纳确定 3、一个正则表达式R描述一组字符串集合L(R) 4、L(R) = the language defined by R 5、所有的token都能用正则表达式表示 2、正则表达式： 1、基本正则表达式：他们是字母比哦啊中的单个字符且自身匹配 电子科技大学 实验报告 学生姓名：学号：指导教师： 实验地点：实验时间： 一、实验室名称：计算机学院软件工程实验室 二、实验项目名称：词法分析器的设计与实现 三、实验学时：4学时 四、实验原理 1.编译程序要求对高级语言编写的源程序进行分析和合成，生成目标程序。词法分析是对源程序进行的首次分析，实现词法分析的程序为词法分析程序。 2.词法分析的功能是从左到右逐个地扫描源程序字符串，按照词法规则识别出单词符号作为输出，对识别过程中发现的词法错误，输出相关信息。 3.状态转换图是有限有向图，是设计词法分析器的有效工具。 五、实验目的 通过设计词法分析器的实验，使同学们了解和掌握词法分析程序设计的原理及相应的程序设计方法，同时提高编程能力。 六、实验内容 实现求n！的极小语言的词法分析程序，返回二元式作为输出。 七、实验器材（设备、元器件） 1.操作系统：Windows XP 2.开发工具：VC6.0 3.普通PC即可 八、实验步骤 （1）启动VC6.0，创建空白工程项目。选择菜单中的“文件”->“新建”->“项目”，在弹出的对话框中，左边的“项目类型”框中，选择“Visual C++ 项目”，在右边框中，选择“空项目(.Net)”，在对话框下边，选择工程文件存放目录及输入名称，如Example1，单击“确定”。 （2）建立相应的单词符号与种别对照表； （3）根据状态转换图编写相应的处理函数； （4）完成词法分析器； （5）编译与调试以上程序； （6）生成相应的*.dyd文件，作为后面语法分析的输入文件。 九、实验数据及结果分析 可以对源程序进行词法分析，如果有错给出出错信息和所在行数，如果无错则生成二元式文件。 十、实验结论 本实验程序较好地完成了词法分析程序的设计与实现，能够对所给文法的程序进行词法分析，在没有词法错误的时候生成相应的二元式文件。该实验程序可一次性给出源程序中的词法错误。 十一、总结及心得体会 通过该实验，对词法分析程序的设计，以及运用C语言进行编程有了更深刻的理解，同时加深了自己对词法分析程序的原理的理解与掌握，提高了自己的动手能力。 十二、对本实验过程及方法、手段的改进建议 程序设计合理，代码可进一步优化。 报告评分： 指导教师签字： 学年第学期《编译原理》实验报告 学院（系）：计算机科学与工程学院 班级：11303070A 学号：11303070*** 姓名：无名氏 指导教师：保密式 时间：2016 年7 月 目录 1．实验目的 (1) 2．实验内容及要求 (1) 3．实验方案设计 (1) 3.1 编译系统原理介绍 (1) 3.1.1 编译程序介绍 (2) 3.1.2 对所写编译程序的源语言的描述 (2) 3.2 词法分析程序的设计 (3) 3.3 语法分析程序设计 (4) 3.4 语义分析和中间代码生成程序的设计 (4) 4. 结果及测试分析 (4) 4.1软件运行环境及限制 (4) 4.2测试数据说明 (5) 4.3运行结果及功能说明 (5) 5．总结及心得体会 (7) 1．实验目的 根据Sample语言或者自定义的某种语言，设计该语言的编译前端。包括词法分析，语法分析、语义分析及中间代码生成部分。 2．实验内容及要求 （1）词法分析器 输入源程序，输出对应的token表，符号表和词法错误信息。按规则拼单词，并转换成二元形式；滤掉空白符，跳过注释、换行符及一些无用的符号；进行行列计数，用于指出出错的行列号，并复制出错部分；列表打印源程序；发现并定位词法错误； （2）语法分析器 输入token串，通过语法分析，寻找其中的语法错误。要求能实现Sample 语言或自定义语言中几种最常见的、基本的语法单位的分析：算术表达式、布尔表达式、赋值语句、if语句、for语句、while语句、do while语句等。 （3）语义分析和中间代码生成 输入token串，进行语义分析，修改符号表，寻找其中的语义错误，并生 成中间代码。要求能实现Sample语言或自定义语言中几种最常见的、基本的语法单位的分析：算术表达式、布尔表达式、赋值语句、if语句、for语句、while 语句、do while语句等。 实验要求：功能相对完善，有输入、输出描述，有测试数据，并介绍不足。3．实验方案设计 3.1 编译系统原理介绍 编译器逐行扫描高级语言程序源程序，编译的过程如下： (1).词法分析 识别关键字、字面量、标识符(变量名、数据名)、运算符、注释行(给人看的，一般不处理)、特殊符号(续行、语句结束、数组)等六类符号，分别归类等待处理。 (2).语法分析 一个语句看作一串记号(Token)流，由语法分析器进行处理。按照语言的文法检查判定是否是合乎语法的句子。如果是合法句子就以内部格式保存，否则报错。直至检查完整个程序。 (3).语义分析 语义分析器对各句子的语法做检查：运算符两边类型是否相兼容；该做哪些类型转换(例如，实数向整数赋值要"取整")；控制转移是否到不该去的地方；是 1、简要解释编译程序中的遍（趟）的含义。 就是对源程序或者源程序的中间结果从头到尾扫描一次，并作有 关的加工处理，生成新的中间结果和目标程序.通常,每遍的工作有外存上获得的前一遍的中间结果开始，完成它所含的有关工作之后,再把结果记录于外存..既可以将几个不同阶段合为一遍，也可以把一个阶段的工作分为若干遍。 2、何为“标识符”？何为“名字”？两者的区别是什么？在程序设计语言中，标识符是一个最基本的概念，其定义为：凡以字母开头的字母数字序列（有限个字符）都是标识符。当给予某标识符以确切的含义时，这个标识符就叫做名字。程序语言中各种名字都是用标识符表示的，只是标识符是一个没有意义的字符序列，而名字却有着确切的意义和属性。 3、简述为什么自顶向下的语法分析技术不能处理具有左递归的文法？这是由于在自顶向下的语法分析技术中，要解决的问题是根据当前输入符号判断将栈顶（最左）的非终结符号替换成哪条规则的右部，若文法具有左递归，则在分析过程中，无法判断岀替换的规则，造成无穷递归求解的过程。 4、简述编译程序的工作过程 编译程序的工作过程，是指从输入源程序开始到输岀目标程序为止的整个过程，是非常复杂的，就其过程而言，一般可以划分为五个工作阶段：①词法分析，对构成源程序的字符串进行扫描和分解，识别岀一个个的单词；②语法分析，根据语言的语法规则，把单词符号串分解成各类语法单位；③语义分析与中间代码产生，即对各类语法单位，分析其汉一并进行初步翻译；④代码优化，以期产生更高效的代码；⑤目标代码生成，把中间代码变换成特定机器上的低级语言指令形式。 5、什么是语法制导翻译？ 是指在语法规则的制导下，通过计算语义规则，完成对输入符号的翻译。由于使用属性文法时把语法规则和语义规则分开，但在使用语法规则进行推导或归约的同时又使用这些语义规则来指导翻译与最终产生目标代码，所以称为语法制导翻译。 6、请简要阐述高级程序设计语言参数传递的常用方式 1、传值：计算实参并将其右值传递给被调用过程 2、传地址： 调用过程将实参地址传递给被调用过程3、传值结果：将传值和 传地址两种方式结合4、传名：只有在被调用过程中用到形参时才动态的建立起它与实参的联系 7、什么是自展？什么是交叉编译？ 自展过程就是用低级语言先实现一个简单的编译器，然后用这个编译器的语言再去编写一个更高级的编译器一一' 个新编译器是 旧编译器的扩展一一的过程。编译器的运行环境与产生程序的运行环境不同的编译过程叫做交叉编译 8、计算机执行用高级语言编写的程序有哪些途径？其主要区别 是什么？ 解释和编译。解释不生成目标代码。 9、自顶向下的语法分析方法中需要解决的主要问题？如何表 示？ 主要需要解决回溯与左递归。回溯：匹配多个候选式无法快速匹配；左递归：推导过程无休止。解决：提取公共左因子、消除直接及间接左递归。翻译程序：能够把某种语言转换成另一种语言，而后者与前者在逻辑上是等价的。 语义分析与中间代码产生：对语义分析所识别岀的各类语法范 畴，分析其含义并进行初步翻译（产生中间代码） 编译程序结构：表格管理、岀错处理 编译前端：由与源语言有关但与目标语言无关的那些部分组成，包括词法分析、语义分析、语义分析与中间代码产生。 后端：编译程序中与目标语言有关那些部分，优化与目标代码生 成。后端不依赖于源语言而仅仅依赖于中间语言。 词法规则是指单词符号的形成规则。 语言的语法规则规定了如何从单词符号形成更大的结构（语法单位）。二义性：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。 LL（1）的含义：第一个L表示从左到右扫描输入串，第二个L表示 最左推导，1表示分析时每一步只需向前查看一个符号 自上而下分析的问题：①文法含有左递归时，分析过程会陷入无限循环②回溯浪费分析时间③某一非终结符用某一候选式匹配成功时，可能是暂时的④分析不成功时，难以找到岀错位置 自下而上分析的问题：怎样判断栈顶的符号串的可归约性，以及如 何归约。 一个句型的最左直接短语称为该句型的句柄。 在形式语言中最右推导常被称为规范推导，由规范推导所得的句型称为规范句型，如果文法无二义的，那么规范推导（最右推导）的逆过程必是规范归约（最左归约） 输入串-----语法树——依赖图-------- 语义规则计算次序 最左规约=规范规约：A 最右推导=规范推导：B 短语：子树的末端结点形成的符号串. 短语相对的句型：整个树的末端结点. 简单子树：只有一层分支的子树 简单短语（直接短语）：简单子树的末端结点形成的符号串. 句柄：最左直接短语 素短语：是个短语，并且至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语 上例G〔引：句型Mg的语法时 共有三裸子轲. 三4趣语：血Sfi 简羊範待：H, Sb 勺柄：A 例题1、构造下面文法的LL (1)分析表。 “ TL int | real L 宀id R , id R | ￡ FIRST ( D) =FIRST (T) ={int, real} FOLLOW (D) =FOLLOW ( L) ={#} FIRST ( L) ={id} FOLLOW (T) ={id} FIRST (R) ={ , , ￡} FOLLOW (R) ={#} 注意当FIRST (X)含￡还需要看FOLLOW (X)四川大学编译原理期末复习总结
编译原理语义分析实验报告——免费!
编译原理实验报告语法分析程序的设计
编译原理课程设计心得体会范文(单片机)
编译原理实验报告
编译原理结课论文
编译原理报告 (2)
北京科技大学编译原理实验报告
编译原理学习心得
编译原理实验报告二
编译原理课程设计报告(一个完整的编译器)
编译原理词法分析实验报告
编译原理课程设计心得体会
编译原理概念总结
编译原理标准实验报告
编译原理实验报告总结
北京工业大学编译原理考试一纸开卷【期末复习总结】
相关主题
文本预览