计算机语言的发展：机器语言、汇编语言、高级语言、命令语言。
翻译程序—编译和解释（笔译与口译/整篇提交与单句提交）[解释方式易于查错，执行效率低]区别在于是否生成目标代码
程序语言一般分为低级语言和高级语言两大类
面向机器的语言指的是由0/1代码组成的语言，其特点是计算机可直接识别，但可读性差，理解困难。在此基础上产生了与人类自然语言比较接近的高级语言。 翻译程序能够将源程序转换成与其等价的目标程序。 对编译程序而言，输入数据是源程序，输出数据是目标程序。
如果编译生成的目标程序是机器代码，则源程序的执行分两大阶段（编译）和（执行）；如果目标程序是汇编语言程序，则源程序的执行分三大阶段（编译），（汇编）和（执行）。
? 中序遍历：中缀表示
? 前序遍历：波兰表示/前缀表示 ? 后序遍历：逆波兰表示/后缀表示 中缀表示
(a+①b)*(c+②d)+③e/f
波兰表示——也就是前缀表示
+③*+①a b+②c d/ef
逆波兰表示——也就是后缀表示
a b +①c d +②*ef/+ ③
(x+6)/y-z*p+m 波兰表示+-/+x6y*zpm 逆波兰表示x6+y/zp*-m+
中间代码的特点：简单规范、与机器无关、易于优化与转换
对代码进行等价变换以求提高执行效率，提高运行速度和节省存储空间[与机器无关的优化-与机器有关的优化]
与机器无关的优化：局部优化[常量合并、公共字表达式的提取]、循环优化[强度削减、代码外提] while(i<10){T1=4*I;i=i+1;}==while(i<10){T1=T1+4}
与机器有关的优化：寄存器的利用、体系结构、存储策略、任务划分 目标代码的形式
具有绝对地址的机器指令 汇编语言形式的目标程序 模块结构的机器指令
源程序-前段 目标程序-编译后端
程序设计语言的语言处理程序是一种系统软件
? 编译过程中，语法分析器的任务是（ ）。
? B. 分析单词串是如何构成语句和说明的 ? C. 分析语句和说明是如何构成程序的 ? D. 分析程序的结构
? 编译程序与具体的机器有关，与具体的语言无关。
要在某一机器上为某种语言构造一个编译程序，必须掌握三方面的内容：源语言、目标语言、编译方法
高级语言的分类：
面向过程的语言（非结构化/结构化[顺
序、选择、循环]/程序的层次性和抽象性不高）
词法分析器表格管理语法分析器词义分析与中间代码生成器代码优化器目标代码生成器出错处理面向对象的语言（以对象为核心，具有封装性、多态性和继承性）
面向应用的语言 专用语言
Chomsky—文法 克林—自动机
? 文法
? 阐明词法和语法的一种工具 ? 形式化语言理论的基本概念 ? 以有穷的集合刻画无穷的集合
方幂：x0=ε; x1=x; x2=xx; ……； xn= xn-1 x abc，…}
文法 为一个四元组:Ｇ = (ＶT，ＶN，Ｐ，Ｓ) ＶT：终结符(Terminal)集 ＶN：非终结符集，ＶT∩ＶN=Φ Ｓ：开始符号(Start Symbol)，S∈ＶN P ：产生式集合 {a，b，c，d}* = {ε，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，…，aaa，aab，aac，aad，aba，abb，标识符的文法：Ｇ = (ＶT，ＶN，Ｐ，Ｓ) ＶT={a, b, c, 1, 2, 3} ＶN={N, L,D}
P:N →L| NL | ND L →a|b|c D →1|2|3 N是开始符号
简单算术表达式的文法：G =({id，+，-，*，/，(，)}，{E}，P，E) P：E → E + E | E- E | E * E | E / E | ( E ) | id 二进制整数的文法：B →0|1 B →B0|B1 S →B 正整数的文法：N →1|2|3|4|5|6|7|8|9 N →N0|N1|…|N9
能被5整除的文法：N →1|2|3|4|5|6|7|8|9 N →N0|N1|…|N9 S →N0|N5|0|5 十进制正实数：D →N.T D →0|0.T|N.0 N →1|2|3|4|5|6|7|8|9 N →N0|N1|…|N9 T →1|2|3|4|5|6|7|8|9 T →0T|1T|…|9T
设G[S]是一文法，如果符号串x是从识别符号推导出来的，即S ?* x，则称x是该文法的句型。句型是一种抽象。若x仅由终结符号串组成，即S ?* x，且x∈ＶT* ，则称x为该文法的句子。文法G所产生的语言定义为集合{x|S ?* x ，其中S为文法识别符号，且x∈ＶT*}。可用L(G)表示该集合。文法描述的语言是该文法一切句子的集合。 L(G)={0n1n|n>=1} S→0S1 S→01 L= {0 m 1 n |m,n≥ 1} S→0S|0A A→1A|1
文法G[S]:S → AB A → aA|ε B →bBc|bc 描述的语言L(G)={ambncn|m>=0,n>=1} L(G)={anbmcmdn|n>=0,m>=1} S→A|aSd A→bAc|bc {x|x是长度为偶数的0、1串} S→00S|01S|10S|11S|ε 描述语言L={a m b n |n≥ m ≥ 1}的文法为：A→Ab|aAb|ε 最左推导：每次推导都施加在句型的最左边的语法变量上 不确定的自顶向下句型分析：出现回溯现象、效率低、编程复杂
已知文法G(S):
S →(R)|a|^ R →T T →S,T|S
写出句型k=(a,(T),(S,T))的短语,直接短语和句柄 短语:
a T (T) S,T (S,T) (T),(S,T) a,(T), (S,T) (a,(T), (S,T)) 直接短语:
a T S,T 句柄:a
T(R)(R)SST(R)S,TaS,TS,T文法类型：0型文法、1型文法/上下文有关文法[产生式a→β满足｜a｜≤｜β｜]、2型文法/上下文无关文法[｜a｜≤｜β｜，产生式a→β中的a必须是变元]、3型文法/正规文法[右线性文法Ａ→ａＢ或Ａ→ａ、左线性文法Ａ→Ｂａ或Ａ→ａ] 文法的二义性：E→E+E|E*E| (E) | id
对于句子id+id*id, 有如下两个最左推导：E?E+E ?id+E ?id+E*E ?id+id*E ?id+id*id
E ?E*E ?E+E*E ?id+E*E ?id+id*E ?id+id*id
E→-EE|-E|a|b|c --a-bc是二义性文法
设有文法G[S]：S→dAB A→aA|a B→Bb|ε，G[S]产生的语言是L(G)={danbm|n>=1,m>=0}，等价的正规文法为：S→aA A→aA|aB|a B→bB|ε
S→abcA A→bcB B→a等价的正规文法是：S→aA A→bB B→cC C→bD D→cE E→a
单词一般可以分为5类：关键字、标识符、常数、运算符、界限符
正规文法转换为正规式：A → xB B → y A = xy A → xA A → y A = x*y A → x A → y A = x|y
正规式转换为正规文法：R=a(a|d)* S →aA A →aA A →dA A →ε
(0|1)*11 (0|1)* S→A|0S|1S A→1B B→1E E→0E|1E|ε (0|1)*000 S→A|0S|1S A→0B B→0E E→0 A→[B B→X]|BA X→Xa|Xb|a|b对应的正规表达式：[(a|b)+]+
对于左线性正规文法 对于右线性正规文法 U→a U→Va U→a U→aV
ε
a
空集
e1e2 e1|e2 e*
确定的有穷自动机DFA：当前状态和下一个输入字母唯一地确定了下一个状态 不确定的有穷自动机NFA
NFA可以有若干个初始状态，DFA只有一个；NFA的状态转换函数不是单值，DFA相反。DFA是NFA的特例。
构造以下正规式的NFA： R=(a*|b*) R=(ab)*
构造与正规表达式R=(a*|b*)b(ba)*等价的DFA
1构造NFA 2转换过程
3构造DFA
一个上下文无关文法是LL1文法的充分必要条件是：
? 对每个非终结符A的不同产生式，A→α， A→β满足
? FIRST(A→α)∩ FIRST (A→β)=O
? 对每个非终结符A的不同产生式， A→α， A→ ε满足
? FIRST(A→α)∩ FOLLOW (A)=O
若有文法G[S]：S→aA|d A→bAS|ε证明这是一个LL1文法
FIRST(S→aA)={a} FIRST (S→d)={d} FIRST(S→aA)∩ FIRST (S→d)= O
FIRST(A→ bAS)={b} FOLLOW(A)=FIRST(S)={a,d,# } FIRST(A→ bAS)∩ FOLLOW(A)=O LL1文法的转换：提取左公因子
? A → αβ1| αβ2|…| αβn
? A → α(β1| β2|…| βn) A → αA’ A’= β1| β2|…| βn
消除左递归[直接左递归A→Aβ间接左递归A → Bβ B → Aα] ? S → Sa S → b ? S → bS’ S’ →aS’| ε
将文法G[S] S→ Sa|Nb|c N → Sd|Ne|f改为无左递归的文法：第二个式子转换为N→NbS’d|cS’d|Ne|f 可改写为：S→NbS’|cS’ S’ →aS’|ε N→fN’|cS’dN’ N’ →bS’dN’|eN’|ε
a
? 计算FIRSTVT(A)的方法
? 若有产生式A →a…或A →Ba…，则a∈ FIRSTVT(A)
? 若a∈ FIRSTVT(B)，且有产生式A →B…，则有a∈ FIRSTVT(A)
? 计算LASTVT (A)的方法
? 若有产生式A → … a或A →… aB ，则a∈ LASTVT(A)
? 若a∈ LASTVT(B)，且有产生式A →… B ，则有a∈ LASTVT(A)
FOR 每条产生式P →X1X2X3…Xn DO
FOR i:1 TO n-1 DO BEGIN
①IF Xi和Xi+1均为终结符号，THEN 置Xi=Xi+1
② IF i<=n-2且Xi和Xi+2均为终结符号，但Xi+1为非终结符号 ，THEN 置Xi=Xi+2 ③ IF Xi为终结符号，而Xi+1为非终结符号
THEN FOR FIRSTVT(Xi+1) 中的每个元素a DO 置Xi
THEN FOR LASTVT(Xi) 中的每个元素a DO 置a>Xi+1
END
已知文法G[S]:S →aSb|P P →bPc|bQc Q →Qa|a该文法是否是算符优先文法？请证明。