编译原理-学习记录4
递归
直接递归:呈现出 U → x U y U\rightarrow xUy U→xUy形式的文法产生式
间接递归:具有 U ⇒ ∗ x U y U\mathop\Rightarrow\limits^* xUy U⇒∗xUy形式的推导
(规则)左递归
产生式呈 U → U y U\rightarrow Uy U→Uy形式
如果是经过多步推导得到,则称之为文法/间接左递归
(规则)右递归
产生式呈 U → x U U\rightarrow xU U→xU形式
同左递归,如果是多步推导得到的,则称之为文法/间接右递归
递归的作用
使用有限的产生式,描述无限的句子——用有穷表示无穷
等价文法
对于两个文法 G 1 , G 2 G_1,\ G_2 G1, G2,如果L( G 1 G_1 G1)=L( G 2 G_2 G2),则 G 1 G_1 G1与 G 2 G_2 G2是等价文法
弱等价:符号和顺序相同(此处涉及弱等价)
强等价:符号、顺序和语义都相同
关于文法构造的问题
运算符结合顺序问题
左递归和右递归,对应左结合和右结合
运算符优先级问题
越靠近语法树下端,运算的优先级越高
优先级更高的运算更晚被推导得到
文法的实用限制
二义性
如果文法G在推导某一个句子的过程中,能够得到两种及以上不同的语法树(无论最左最右推导),则称该文法是二义性文法。
消除二义性通常有两种方法:
1、对语义增加限制
2、重新构造一个等价的无二义性文法
通常在if-else语句中,为了提高可理解性,还是使用有二义性文法。通过对语义加上限制来消除二义性
二义性文法不可判定:不存在一个算法,使得能够在有限的步骤内,确切地判定一个文法是否为二义性的
文法的压缩
1、文法不能含有有害产生式:
U
→
U
U\rightarrow U
U→U
2、文法不能含有多余产生式:一种是从开始符号出发的所有推导都不会用到的产生式(不可达非终结符号),另一种是无法推导出终结符号串的产生式
分析方法简介
自上而下分析
从开始符号出发,不断建立直接推导,试图构造一个最左推导序列,最后推导出与输入符号串相同的符号串
自下而上分析
从待输入的符号串开始,利用文法的产生式逐步向上规约,试图规约到文法的开始符号
ch3.词法分析(1)——有穷自动机
自动机
有限状态、有限输入、有开始有结束
是一种能进行运算并实现自我控制的装置
对于2型文法(上下文无关语言),使用下推自动机进行识别;而对于3型文法(正则语言),使用有穷自动机进行识别
有穷自动机的形式定义
确定的有穷自动机(DFA)
定义:DFA=(Q,
Σ
\Sigma
Σ, t,
q
0
q_0
q0, F)
其中,Q是有穷非空的状态集,
Σ
\Sigma
Σ是有穷的输入字母表,t是映射
Q
×
Σ
→
Q
Q\times \Sigma\rightarrow Q
Q×Σ→Q,
q
0
∈
Q
q_0\in Q
q0∈Q是开始状态,而F
⊆
\subseteq
⊆ Q是非空终止状态集合
FA的表示
有状态转换表和状态转换图两种表示方式
例如:DFA A=({ q 1 q_1 q1, q 2 q_2 q2, q 3 q_3 q3, q 4 q_4 q4}, {0, 1}, t, q 1 q_1 q1, { q 3 q_3 q3, q 4 q_4 q4})以及映射t(图1:状态转换表):
表示共有 q 1 q_1 q1, q 2 q_2 q2, q 3 q_3 q3, q 4 q_4 q4这四种状态,输入为0或1,开始状态为 q 1 q_1 q1,结束状态为 q 3 q_3 q3, q 4 q_4 q4。用圆表示状态,start指向开始状态,双圆表示结束状态,输入导致的状态转换使用箭头表示,即可得到状态转换图(图2):
DFA的扩充:扩充为能够接受符号串,接受方式为从左到右逐字符接收
例如:对于上述DFA,输入0011,则:t(
q
1
q_1
q1, 0011)=t(t(
q
1
q_1
q1, 0), 011)=t(
q
1
q_1
q1, 011)=……=t(
q
1
q_1
q1, 11)=……=t(
q
2
q_2
q2, 1)=
q
3
∈
F
q_3\in F
q3∈F
扩充的映射: t : Q × Σ ∗ → Q t:Q\times\Sigma^* \rightarrow Q t:Q×Σ∗→Q,注意到此处原有映射中的 Σ \Sigma Σ被替换为 Σ ∗ \Sigma^* Σ∗,即此时能够接受符号串,而不仅局限于来源于字母表中的单个符号
DFA中的“确定”,代表开始状态时唯一的,且输入字母唯一地确定了下一个状态
非确定的有穷自动机
定义:NFA=(Q,
Σ
\Sigma
Σ, t,
Q
0
Q_0
Q0, F)
其中,Q是有穷非空的状态集,
Σ
\Sigma
Σ是有穷的输入字母表,t是映射
Q
×
Σ
→
Q
Q\times \Sigma\rightarrow Q
Q×Σ→Q的幂集,
Q
0
∈
Q
Q_0\in Q
Q0∈Q是开始状态集,而F
⊆
\subseteq
⊆ Q是非空终止状态集合
注意到与DFA不同的地方:1、映射的右端是Q的幂集(即集合内的元素不再是一个单独的状态,而是可能有多个状态。也就是说,接受输入后,可以到达多个状态);2、开始状态变为了开始状态集,说明开始状态不再仅仅局限于一个
NFA的扩充
扩充的映射:
t
(
q
,
β
)
=
t
(
q
,
a
α
)
=
t
(
q
1
,
α
)
∪
t
(
q
2
,
α
)
.
.
.
t(q,\ \beta)=t(q,\ a\alpha)=t(q_1,\ \alpha)\cup t(q_2,\ \alpha)...
t(q, β)=t(q, aα)=t(q1, α)∪t(q2, α)...。其中,
a
a
a是
β
\beta
β中的第一个元素,
q
1
,
q
2
.
.
.
q_1,\ q_2...
q1, q2...是状态
q
q
q接受输入
a
a
a后可能达到的新状态,这些状态的并集就是全部可能到达的状态
FA的构造
1、确定输入字母
2、确定关键状态(模拟识别过程)
3、确定状态间的转换关系
4、确定开始和终止状态
不合法的状态不在图内显示
NFA到DFA的转换
NFA的确定化
基本思想
到达的状态
FA的构造
1、确定输入字母
2、确定关键状态(模拟识别过程)
3、确定状态间的转换关系
4、确定开始和终止状态
不合法的状态不在图内显示