同时伴有表格管理、出错处理
1、词法分析
任务:对构成源程序的字符串进行扫描和分解,识别出单词(如标识符等)符号
输入:源程序
输出:单词符号序列
2、语法分析
任务:根据语言的语法规则对单词符号串(符号序列)进行语法分析,识别出各类语法短语(可表示成语法树的语法单位),判断输入串在语法上是否正确
输入:单词序列
输出:语法分析后的单词序列
3、语义分析
任务:按语义规则对语法分析器归约出的语法单位进行语义分析,审查有无语义错误,为代码生成阶段收集类型信息,并进行类型审查和违背语言规范的报错处理
4、中间代码生成
任务:将语义分析得到的源程序变成一种结构简单,含义明确,容易生成,容易译成目标代码的内在代码形式
常用的中间代码形式是四元式(算符,运算对象1,运算对象2,结果)
5、代码优化
任务:对中间代码或目标代码进行变换改造等优化处理,使生成的代码更高效
6、目标代码生成
任务:将语义分析结果或中间代码生成特定机器上的绝对或可重定位的指令代码或汇编指令代码
1、语言是由句子组成的集合,是由一组符号构成的集合
2、程序设计语言——所有该语言的程序的全体
语法——表示构成语言句子的各个记号之间的组合规律
语义——表示各个记号的特定含义。(各个记号和记号所表示的对象之间的关系)
语用——表示在各个记号所出现的行为中,它们的来源、使用和影响
文法是一些规则的有限集合,它是以有穷规则集来刻划无穷句子集合的工具
BNF是一种广泛采用的( 描述文法)工具。
产生式——设VN ,VT 分别是非空有限的非终结符号集和终结符集。V = VN ∪ VT ,VN ∩ VT = ? 。所谓产生式是一个序偶对(α ,β),其中 α ∈ V+,β ∈ V*,通常表示为:α → β 或 α ::= β,产生式也叫规则、重写规则、生成式。
文法 G 是一个四元组,G = (VN,VT,P,S)。其中,VN,VT 分别是非空有限的非终结符集和终结符集,且 VN ∩ VT = ?;P为产生式集;S ∈ VN 为文法的开始符号(或识别符),它是一个非终结符,至少要在一条规则中作为左部出现。
产生式形如: α → β
其中:α ∈ ( V T ∪ V N ) ?且至少含有一个非终结符;β ∈ ( V T ∪ V N ) ?
α、β都是由终结符和非终结符组成的任意串,但α含有一个非终结符(全是终结符就没法定义了)
2型文法(上下文无关文法是0型文法的一个特例)
产生式形如: α → β
其中:α ∈ ( V T ∪ V N ) ? α∈ (V_T∪V_N)^*α∈(V T∪V N) ?
且至少含有一个非终结符;β ∈ ( V T ∪ V S ) ?
∣ α ∣ ≤ ∣ β ∣ ,仅 S → ε 例外。
左边一定比右边短
产生式形如: A → β A → βA→β
其中:A ∈ V N ; β ∈ ( V T ∪ V N ) ? A∈ V_N;β∈ (V_T ∪ V_N)^*A∈VN;β∈(V T∪V N) ?
左边是一个非终结符,右边是终结符非终结符组成的任意串。
二义性文法是上下文无关文法。
右线性文法
产生式形如: A → α B 或 A → α A → αB 或 A → αA→αB或A→α
其中: α ∈ V T ? ; A , B ∈ V N α∈ V_T^*;A,B∈V_Nα∈V T?;A,B∈V N
右边要么没有非终结符
如果有非终结符的话,只能出现在最右边。
左线性文法
产生式形如: A → B α 或 A → α A → Bα 或 A → αA→Bα或A→α
其中: α ∈ V T ? ; A , B ∈ V N α∈ V_T^*;A,B∈V_Nα∈V T? ;A,B∈V N
右边要么没有非终结符
非终结符要出现,只能在定义式的最左边。
语法树也称推导树,给定文法G=(VN,VT,P,S),对于文法 G 的任意一个句型都存在一个相应的语法树,它满足:
① 树中每一个结点都有一个标记,此标记是 V = VN ∪ VT 中的一个符号
② 根的标记是S
③ 若树的一结点 A 至少有一个子孙,则 A ∈ VN
④ 如结点 A 的子孙结点从左到右次序为 B1,B2 …… Bn,则必有产生式 A → B1B2…Bn
? 同一语法树可以表示对同一句型不同的推导过程
? 如果每一步 α → β 中,都是对 α 中最左(右)非终结符进行替换,则称之为最左(右)推导。最右推导称为规范推导,由规范推导所得的句型称为规范句型
? 同一语法树最多对应唯一的最左(右)推导
? 一个句型有可能对应着不同的语法树
? 如果一个文法存在某个句子对应着两棵不同的语法树,则称此文法是二义的
? 不存在算法判断一个 2 型文法是否是二义的
? 实际应用中,常找出一组无二义性的充分条件来构造无二义性文法
? 句型的分析就是识别一个符号串是否为某文法的一个句型
? 分析算法分为两大类:自顶向下分析和自底向上分析
自顶向下分析:由根向下逐步建立语法树,是一个逐步推导的过程
自底向上分析:自底向上构造语法树,是一个逐步规约的过程
名称 | 概念 |
---|---|
短语 | 在语法树中表示所有分支结点对应子树,短语即子树叶子对应的符号 |
直接短语 | 在语法树中表示为该短语只有上下相邻父子两代 |
句柄 | 句柄表示最左直接短语 |
素短语 | 是指一个短语至少包含一个终结符,并且除它自身之外不再包含其他素短语 |
最左素短语 | 最左素短语就是句型最左边的素短语,是算符优先分析法的规约对象。语法树: 通过语法树分析时,要注意先判断是否为素短语,再找相对最左端的素短语。 |
例题1:求短语,直接短语,句柄
给定句型:
FF↑a
给定文法:
G[T]:
T → T*F|F
F → F↑P|P
P → (T)|i
解析:
推导步骤为:
T ? TF*
? TFF
? TF↑*\F*
? TF↑a
画出语法树为:
1、词法分析程序的输出
2、词法分析程序中如何识别单词
对给定的字母表∑ ∑∑
1)ε εε和Ф ФФ都是∑ ∑∑上的正规式,它们所表示的正规集为{ε εε}和Ф ФФ;
2) 任何a ∈ ∑ a∈ ∑a∈∑,a是∑ ∑∑上的正规式,它所表示的正规集为{a} ;
3) 假定e1和e2都是∑ ∑∑上的正规式,它们所表示的正规集为L(e1)和L(e2),则
仅由有限次使用上述三步骤而定义的表达式才是∑ 上的正规式,仅由这些正规式表示的字集才是∑ 上的正规集
1、确定有限自动机(DFA)
2、不确定的有穷自动机(NFA)
3、NFA转换为等价的DFA
子集算法
步骤:
1、确定列数(有几种弧就有几列),找到起始状态的所有
然后列表,直到出现重复的就停止。
2、重新命名表里的状态,画DFA
状态等价
提取左公共因子
消除左递归
LL(1)分析
1、设有文法G[S]:
S?A
A?B|IF A THEN A ELSE A
B?C|B+C|+C
C?D|C*D|*D
D?x|(A)|- D
求文法的非终结符集合和终结符集合
非终结符集合={S, A, B, C, D}
终结符集合={IF, THEN, ELSE, +, *, x, (, ), -}
2、消除文法G[A]中的多余规则。
G[A]:
A?Bcd|dD
B?AB|b
C?c
D?AD|DB
E?Da|Eb|e
由于有关D的规则推导不出终结符号串,有关C和E的规则不可到达,所以化简后的文法为
A?Bcd
B?AB|b
3、设有文法G[S]:
S?aAb
A?BcA|B
B?idt|e
请问下列符号串是否为文法的句子或句型,如果是,请画出语法树。
①aidtcBcAb
②aidtccb
③ab
④abidt
①②③能由文法识别符号S推导出,且②③均由终结符号组成,所以①②③是句型,②③还是句子。对识别符号S仅有一条右部为aAb的规则,推导出的符号串的最右部不可能是t,所以④不可能是句型,也不可能是句子。(语法树略)
4、设有文法G[S]:
S?bTc|a
T?R
R?R/S|S
请问bR/bTc/bSc/ac是否为该文法的句型?若是,请画出该句型的语法树,并分析其短语、直接短语和句柄。
5、已知文法G[Z]:
Z?aZbZ|aZ|a
证明该文法是二义的。
6、给出描述语言L(G)={a2nbn|n31}的2型文法。
7、试给出描述语言L(G)={a2m+1bm+1|m30}è{a2mbm+2|m30}的文法。
3、字母表∑={a,b}上的正则式R=(ba|a)*,请给出与正则式R等价的正则文法。
思路:1. 求与正则式R等价的NFA;2. 将NFA确定化得到DFA;3. 根据DFA转换为正则文法的方法,得到与正则式等价的正则文法。
至少使用两种不同的形式表示法描述由7/9的一切精度的近似值组成的集合。
提示:
7/9是一个近似值,约等于0.77777…,实际考察如何表示出符号串“0.77777…”。
找出该符号串的特点,可以采用正规文法、正则式及有穷自动机三种方法进行描述。
1、列表
直到某一行的结果全部在第一列出现时结束
2、重新命名表里的状态,画DFA
步骤:
1、
2、找出终态集和初态集,然后分区,去重
3、重新命名表里的状态,画DFA
1、直接左递归
2、间接左递归
通过代入法,变为直接左递归
如果交集为空,不是;反之,是LL(1)文法
文法G[S]=(VN,VT,P,S)
最右推导:规范推导
最左规约:规范规约
分析语言,画状态转换图
项目的分类:
识别活前缀中无冲突项目(移进–归约冲突,归约–归约冲突)
对每个归约项目A->a,求FOLLOW(A)得到的输入处填rn,其余同LR(0)分析一样
FIRSTVT
特殊的: