递归
直接递归:呈现出 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:状态转换表):
图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):
图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、确定开始和终止状态
不合法的状态不在图内显示
今天的文章编译原理-学习记录4分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/87663.html